公开/公告号CN113841149A
专利类型发明专利
公开/公告日2021-12-24
原文格式PDF
申请/专利权人 区块链控股有限公司;
申请/专利号CN202080036508.0
申请日2020-04-29
分类号G06F21/64(20060101);H04L9/30(20060101);H04L29/06(20060101);
代理机构11019 北京中原华和知识产权代理有限责任公司;
代理人孙磊;徐民
地址 安提瓜和巴布达圣约翰教堂街44号菲茨杰拉德故居
入库时间 2023-06-19 13:48:08
法律状态公告日
法律状态信息
法律状态
2022-05-27
实质审查的生效 IPC(主分类):G06F21/64 专利申请号:2020800365080 申请日:20200429
实质审查的生效
技术领域
本公开总体涉及改进的区块链网络和相关联的协议,包括用于提高在区块链网络内执行的计算任务的处理效率、可靠性、安全性和资源要求的方法和系统。具体地,本公开涉及一种实现工作量证明协议的区块链网络。
背景技术
在本文中,“区块链”一词涵盖所有形式的基于计算机的电子分布式分类账。这些分类账包括基于共识的区块链和交易链技术、许可和非许可的分类账、共享分类账、公共和私有区块链,及其变型。虽然已提出并开发了其他区块链实施方案,但是区块链技术最广为人知的应用是比特币分类账。为了方便和说明的目的,在本文中可能会提及比特币。但应注意,本公开不限于与落入本公开范围内的比特币区块链以及替代的区块链实施方案和协议一起使用。在本文中,“用户”一词可指人员或基于处理器的资源。在本文中,“比特币”一词可包括源自或基于比特币协议的任何版本或变型。
区块链是一种点对点的电子分类账,其实现为基于计算机的去中心化分布式系统,所述系统由区块组成,而区块又由交易组成。每笔交易是一种数据结构,所述数据结构对所述区块链系统中参与者之间的数字资产/资源控制权的转移进行编码,并且包括至少一个输入和至少一个输出。每个区块都包含前一个区块的哈希值,因此区块被链接在一起,以创建自所述区块链创建以来写入其中的所有交易的永久性的不可更改的记录。交易包含嵌入到其输入和输出中的小程序,称为脚本,这些脚本指定如何以及由谁访问所述交易的输出。在比特币平台上,这些脚本是使用基于堆栈的脚本语言编写的。
为了将交易写入所述区块链,必须对其进行“验证”。网络节点(“矿工”)确保每笔交易均有效,而无效交易则被网络拒绝。安装在所述节点上的软件客户端通过检查未花费的交易是否符合区块链的协议规则,以及通过执行锁定和相应的解锁脚本,对所述未花费的交易执行此验证工作。如果所述锁定和解锁脚本的执行评估为TRUE,则所述交易有效。因此,为了将交易写入所述区块链,所述交易必须:i)由接收所述交易的第一节点进行验证,如果所述交易通过验证,则挖矿节点将其中继到网络中的其他节点;ii)添加到由矿工建造的新区块中;iii)进行挖掘,即添加到过去交易的公共分类账中。
为了建造新区块,矿工通过执行资源密集型工作来竞争,其目的是第一个找到计算(难题puzzle)的解决方案(工作量证明,也称为“PoW”或“随机数nonce”)。所述难题的难度可以随着时间的推移进行调整,以影响向所述区块链添加新区块的速率。在比特币中,矿工使用SHA256哈希算法来查找PoW,所述PoW在哈希时产生的哈希值低于或等于由网络协议设置的当前难度级别。
如果某个矿工是第一个找到当前难题的PoW的矿工,则该矿工就会生成一个新区块,然后将该新区块广播给网络上的其他矿工。如果其他矿工要接受该新区块为有效,该新区块必须包含可验证的PoW。因此,挖掘提供了一种共识机制,所述共识机制确保网络上的节点在所述区块链的合法和当前状态方面同步和一致。此外,所述共识机制还可以防御某些类型的潜在网络攻击,从而为网络提供安全保障。
在比特币的早期,挖掘的计算要求足够低,以至于矿工可以使用由标准CPU组成的通用计算机。然而,拥有性能较高的计算机的矿工比拥有性能较低的计算机的矿工更具竞争优势。这种激励,再加上难题难度的历史性增加,导致了专用集成电路(ASIC)挖掘设备得到广泛使用。此外,还可以将多组ASIC设备链接在一起,以分担查找PoW解决方案所涉及的工作。在这种情况下,可以使用不同的机器来尝试不同的PoW随机数或其范围。因此,可以跨设备并行化挖掘算法。
然而,功能越强大的设备成本越高,运行和冷却所需的能源也越多。一些人还认为,硬件不平等会促进挖掘能力在网络内潜在集中,从而导致可能的缺陷或漏洞。这些问题引发了人们对开发“抗ASIC”挖掘解决方案的兴趣。然而,所提出的解决方案包括修改PoW算法,以将抗冲突SHA256哈希算法更改为所谓的“带宽困难”函数,但成功有限或有争议。
因此,还需要解决这样的技术挑战,即如何保持区块链网络上的竞争节点提供的共识机制和安全性,同时降低所需的成本、能量使用和计算资源,并保持去中心化网络的优势。
本公开通过提供包括使用非并行共识机制的非并行挖掘(NPM)技术、硬件和软件布置、联网技术和方法及其组合的各方面和实施例,至少解决这些技术问题。本公开可以使用固有顺序算法来为区块链的状态提供安全性并建立共识。
在本文中,“顺序算法sequential algorithm”一词是指必须按从开始到结束顺序执行的算法,而不需要并行执行其他处理。示例包括数值迭代方法,例如牛顿法(Lipson,John D.,“牛顿法:一种伟大的代数算法”,《第三届ACM符号与代数计算研讨会论文集》,ACM,1976年),以及可以在数学上使用递归公式表示的算法。
在本文中,“固有顺序inherently sequential”(或“非并行non-parallelisable”)算法是指不能使用可并行例程/子例程优化的顺序算法。应该注意的是,该短语在技术领域内没有严格定义,尽管在本文中使用的定义与文献(Greenlaw,Raymond.,“一种将算法归类为应用于图形搜索的固有顺序算法的模型”,《信息与计算》,97.2(1992年):第133-149页)中存在的术语和定义的直观用法兼容。
此外,还应该注意的是,术语“计算挑战computational challenge”和“挑战challenge”在技术领域内是已知的,本领域技术人员很容易理解。此外,“挑战”在本领域中也可以称为“难题”。
发明内容
本公开的实施例提供了与区块链网络一起使用或在所述区块链网络上使用的计算机实现的协议、方法和系统。所述区块链网络实现工作量证明(PoW)区块链协议。这可以是区块链协议,例如比特币协议的版本。然而,其他区块链协议和实现也将落入本公开范围内。
根据一个或多个实施例的一种方法可以包括:生成多个非并行挑战(或“难题”),并将所述多个挑战中的每个挑战分配给所述网络上的各名矿工。因此,优选地,分配所述挑战,使得每名矿工接收与其他矿工不同的挑战。可以以任何合适的方式执行分配,例如从所述多个挑战中随机选择一个节点作为给定挑战的接收方,尽管也可以使用其他分配方法。挑战可以是抗冲突的,因为所述多个挑战中的每个挑战是唯一的可能性很高。优选地,每个矿工然后试图解决其所分配的挑战。他们可以将数据或输入添加到所述挑战中,使得该解决方案在所述多个挑战的解决方案中是唯一的。
在一些实施例中,所述生成所述多方计算挑战和/或进一步的多方计算挑战中的至少一个包括计算对使用随机或伪随机输入的运算的输出。附加地或替代地,所述生成多方计算挑战中的至少一个可以包括生成RSA密钥对。
优选地,所述挖掘节点必须使用固有顺序(非并行)算法,以便查找其所分配挑战的解决方案。所述固有顺序算法可以包括以下运算中的至少一个:递归运算;模幂运算;和/或重复平方运算。此类算法包括一组预定步骤,必须执行这些步骤才能得到结果。因此,本公开的实施例与已知的PoW布置不同,在已知的PoW布置中,矿工简单地重复哈希函数直到找到解决方案,而不需要执行预定的一组步骤或运算。所述固有顺序算法可能需要将一个运算的输出用作后续运算的输入,以便生成结果(解决方案)。
优选地,由一个节点委员会生成所述挑战,并为每个区块生成一组新挑战。可以有3个或更多节点,每个节点都是可信实体。节点彼此独立,因为它们不能串通。因此,可以执行周期或循环,其中对于每个周期,生成多个进一步的(新的)多方计算挑战。在每个周期的开始,在矿工之间分布每一组新挑战。因此,每个矿工可能会在每个周期开始时接收新挑战。可以重复该循环,以便将新挑战分配给挖掘节点。优选地,对于要添加到区块链的每个新块重复该循环。因此,当所述挖掘节点中的一个挖掘节点在前一个周期期间找到其所分配的挑战的解决方案时(即,它们已经提供了允许它们挖掘下一交易区块的工作量证明),生成一组新挑战,并再次开始该周期。
优选地,至少部分地由多个基于计算机的实体来执行生成所述多个多方计算挑战和/或所述多个进一步的多方计算挑战。这可以是从一组/更大的多个基于计算机的实体中选择的实体的子集。换句话说,可以使用一个节点委员会来生成挑战。根据一个或多个实施例,所述委员会可以是所述网络上的所述挖掘节点的子集。在其他实施例中,只有执行挑战生成的实体中的一些或没有实体可以是挖掘节点。在一些实施例中,通过使用随机或伪随机的过程从所述多个基于计算机的实体中选择基于计算机的实体的子集。
在一个或多个实施例中,可以在预定时间从多个基于计算机的实体/所述较大的多个基于计算机的实体中重新选择生成挑战的所述多个基于计算机的实体。该时间可以基于如上所述的周期的开始(或受其影响)。
有利地,本公开的实施例涉及分配和/或分发固有顺序算法,该算法对于每个矿工是唯一的(而不是所有矿工试图成为第一个解决相同的常见共享问题的矿工)。因此,与现有技术相比,本公开采用完全不同的、相反的挖掘方法。这种新方法提供了矿工试图解决的问题之间的随机差异。该随机差异可以例如由哈希函数的随机输出提供,其中输入会发生变化并随机生成这意味着很难预测,并且对于每个新区块,矿工必须通过重复顺序算法的步骤来找到其新分配问题的解决方案。所需迭代次数在不同的矿工集合之间会有所不同。这意味着可以更可靠地确定哪一名矿工获得了对下一个区块进行挖掘的权利。相比之下,现有方法意味着时钟速度更快的矿工获得了优势。因此,本公开的实施例提供了与传统PoW区块链挖掘方法的显著偏差。因此,提供了一种改进的区块链网络和相关联的协议。在提高效率的同时,维持了区块链网络的安全性。
结合本文所述的实施例,本发明的这些方面和其他方面将是清楚的和阐明的。现将仅通过举例的方式并参考附图对本公开的实施例进行说明,其中:
附图说明
图1是示出本公开的一个实施例的流程图。
图2是示出可实现各个实施例的计算环境的示意图。
具体实施方式
本公开的实施例利用挖掘难题,该挖掘难题包括具有以下特征的“陷门trap-door”计算:
1.如果已知某些秘密信息,则可以快速执行;
2.如果解算器不知道某些秘密信息,则需要执行可配置的时间。
如在Ronald L.Rivest、Adi Shamir和David A.Wagner的“时间锁定难题和定时释放加密”(1996年)(下文称为“Rivest等人”)中所公开的,“陷门”可能涉及RSA私钥的知识,或者至少涉及使用该私钥计算两个独立值的能力。
根据本公开的一个或多个优选实施例,通过一个代理委员会(节点)之间的多方计算(MPC)为每名矿工和每个区块生成新难题。在一些实施例中,所述委员会包括以随机或伪随机方式从所述区块链网络上的所述多个挖掘节点中选择的合格矿工的子集。所述随机生成的RSA模数中的份额由委员会成员持有,使得对应于给定区块的难题的秘密密钥对于任何人来说都是未知的(直到该区块被确认)。在一个或多个实施例中,所述委员会和/或秘密密钥在每个区块之后发生更改。
如图1所示,在步骤1选择一个由可信的独立节点(例如,矿工)组成的委员会。在步骤2,所述委员会中的每个节点生成非并行计算挑战。这种挑战必须使用非并行固有顺序算法来解决。在步骤3,每名矿工都会收到挑战。因此,矿工试图找到自己问题的解决方案,这是他们在步骤4所做的。在矿工找到他们挑战的解决方案之后,对于挖掘到所述区块链中的每个区块重复该循环。
根据本公开提供的装置的组件包括:
1.独立矿工委员会(参见Gilad,Yossi等人,“Algorand算法:关于加密货币的扩展拜占庭协议”,《第26届操作系统原理研讨会论文集》,ACM,2017年)
2.多方素数计算(参见Algesheimer,Joy、Camenisch,Jan和Shoup,Victor,“以共享密钥为模的高效计算及其在生成共享安全素数积中的应用”[线上];Boneh,Dan和Matthew Franklin,“高效生成共享RSA密钥”,国际密码讨论年会,德国柏林施普林格,1997年)
3.作为伪随机数生成器的哈希函数
4.基于重复平方的时间锁定难题(参见Rivest等人)
5.用于验证解决方案区块的MPC(参见Algesheimer,Joy、Camenisch,Jan和Shoup,Victor,“以共享密钥为模的高效计算及其在生成共享安全素数积中的应用”[线上])
挖掘算法
任何挖掘算法,无论是否为非并行挖掘算法,如果要用于就区块链状态达成共识,必须从根本上遵守以下性质:
性质1:通过生成有效的计算证明C来完成挖掘算法的过程必须花费足够长的时间。
性质2:给定候选计算证明C,必须能够在比生成有效计算证明C所需的时间短得多的时间内验证C是有效的计算证明。
一般而言,可以通过两种广泛的方式让挖掘算法实现由这些性质定义的范例:通过使用陷门挖掘函数,或者通过使用同时满足上述两个性质的基于时间的约束。
陷门挖掘函数
一般而言,良好的单向陷门函数很难计算,但在提供一些附加信息时很容易验证,因此可以映射到同时具有性质1和性质2的挖掘过程。
例如,在Rabin密码系统中,从私钥(p,q)生成公钥n=p·q,其中p,q都是素数。在消息m上计算签名(S,U)是单向函数,其解是满足以下等式的值S
H(m||U)=S
用于找到有效S的算法是陷门算法或函数,因为在给定(n,m,U)的情况下很难找到S,但如果n的因式分解已知,则很容易找到S。这里重要的一点是,在了解陷门之前,挖掘应该是困难的,因此需要比网络消息传递延迟足够长的一段时间。但是,一旦找到解决方案,就可以发布或联合计算陷门,从而能够使用该陷门快速验证解决方案。在本文中,利用一种称为时间锁定难题的陷门挖掘函数来构造一种在区块链网络上进行非并行挖掘的共识算法。
时间锁定难题
时间锁定难题是指需要预定时间才能完成的问题。将算法F
F
存在另一种算法F
F
当且仅当s已知,此外,通过输入参数来精确控制计算机完成该算法所花费时间的能力需要F
作为固有顺序算法的重复平方
核心问题是计算a、t和n的指定值,其中
算法1
对于i,i为从0到t-1,计算
W(0)=a
W(i+1)=W(i)
以得到W(t)。在不知道n因式分解的情况下,没有已知的方法可以更有效地执行此计算。
RSA重复平方时间锁定难题
Rivest等人提出了一种基于重复平方的时间锁定难题。考虑一种情景,其中爱丽丝(Alice)为鲍勃(Bob)创建一个要求解的难题
1.爱丽丝生成一个复合模数,
n=pq
其中,p,q是素数。她将(p,q)保密。
2.爱丽丝计算第二模数,
φ(n)=(p-1)(q-1)
将其保密。
3.爱丽丝选择难题计算时间T,并计算
t=TS
其中,S是鲍勃的平方率(计算速度的度量)。
4.爱丽丝选取随机基数a,并通过使用以下算法有效地计算
a.e=2
b.
其中,φ(n)是陷门函数。
5.爱丽丝将时间锁定难题9a,t,n)发送给鲍勃,并要求他找到L=F
可以通过使用费马测试显示,
重复平方被视为“固有顺序”过程,这意味着没有明显的方法可以在很大程度上将其并行化,参见Rivest等人的研究。因此,拥有多台计算机解决难题并不比拥有一台计算机更有优势,计算时间的变化与单台计算机的速度有关,而单台计算机的速度更容易被难题创建者测量。换句话说,爱丽丝发送的难题的求解时间是可控的,与鲍勃的计算资源无关。
素因式分解难度
在时间锁定难题的实现方式中,一个重要的假设是找到n素因式分解是一个难解的问题,不能比难题本身更快地解决。要证明这一假设是合理的,请考虑以下推理。用于求解整数因式分解问题的最佳算法是普通数域筛选法(NFS),其时间复杂度为
例如,256位RSA密钥可以在近似O(exp(46.6))=2.5×10E20运算中进行因子分解。假设NFS中的每个运算等同于1个浮点运算,对于1petaFLOPS(每秒浮点运算)的计算机来说,破解256位密钥仍然需要大约250000秒的时间。
在定期更新的区块链环境中,需要为每个新区块创建不同的RSA模数。因此,仅需在与区块生成时间相同的时间量内(例如,几分钟)找到n的素因式分解是不可行的。通过将RSA密钥设置为512位,可以安全地假设在挖掘周期内RSA模数的因式分解是不可行的。
可验证随机函数
可验证随机函数(VRF)是一种三元组算法(请参见https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61):
·Keygen(r)→(VK,SK)-在随机输入种子r上,密钥生成算法产生验证密钥VK和秘密密钥SK对
·Evaluate(SK,m)→(Y,ρ)-求值算法将秘密密钥SK、消息m作为输入,并生成伪随机输出字符串Y和证明ρ
·Verify(VK,m,Y,ρ)→0/1-验证算法将验证密钥VK、消息m、输出Y和证明ρ作为输入。当且仅当验证Y是对输入SK和m的求值算法生成的输出时,才会输出1。
重要的是,输出Y是唯一的,这意味着除非知道密钥,否则不可能找到。下面提供了使用可验证随机函数的子委员会(subcommittee)遴选的详细实现方式。
唯一且安全的子委员会遴选
根据本公开的一些实施例,子委员会遴选使用ECDSA签名来复制可验证随机函数。该过程可以分为3个阶段:建立、伪随机值创建和子委员会遴选。考虑一个矿工M
建立
步骤1:矿工分别具有公钥PK
步骤2:矿工选择唯一的种子S
步骤3:对于每个新区块,矿工都会创建一条消息。该消息只是矿工种子值的哈希值,与前一个区块头连接在一起。换句话说,对于矿工PK
m
其中,X
步骤4:矿工在他们的消息上生成ECDSA签名,即
ECDSA(sk
矿工记录在区块B
步骤5:每名矿工M
子委员会遴选
步骤6:收到证明后,每个网络节点都会检查以下内容
1)消息m
2)消息m
3)
其中,T
4)矿工K
步骤7:子委员会成员的遴选过程如下
1)具有公钥PK
2)公钥按值V
3)通过选择具有以下三个最低值V
V
为了让矿工就子委员会候选人名单达成一致,需要在整个网络中传播每个证据。假设低延迟和高连通性,网络应该能够快速建立矿工值的全局列表,并因此建立子委员会。此外,网络将仅接受每名矿工的一条证明消息(第一条消息已发送),以防止垃圾邮件攻击的风险。
多方计算
多方计算可以被描述为需要一个以上(独立)实体协作以生成某个最终值的计算。理想情况下,实体在生成最终输出时不共享或传送它们的输入,并保持它们的输入是私有的。在非并行挖掘的上下文中,并且根据本公开的一个或多个实施例,多方计算可以包括计算在重复平方时间锁定难题中使用的RSA模数。在此类实施例中,重要的是RSA模数的素因式分解不受任何单个矿工的控制。
用于生成秘密RSA模的MPC
尽管本领域技术人员可以选择其他算法或方法,但是出于说明性目的,本公开的实施例可以使用由Boneh和Franklin公开的方法来生成共享素数模数(Boneh,Dan和Matthew Franklin,“高效生成共享RSA密钥”,国际密码讨论年会,德国柏林施普林格,1997年,下文称为“Boneh等人”)。在他们的算法3中,独立实体(爱丽丝Alice、鲍勃Bob和亨利Henry)建立任意大小的RSA模数。所述方法是一种五元组算法:
·PickCandidates(k)→(p
·Compute N–通过使用专用和分布式计算(Boneh等人第3页),3台服务器计算
n=(p
而无需明确共享(p
由于n现在是公开的,实体执行试除法以检查n不能被小素数整除的情况,例如,在阈值ECDSA签名实现中的联合可验证随机密钥共享(JVRSS)协议中使用的方法。
·Primality Test–这3台服务器使用专用分布式计算来测试n实际上是两个素数的乘积(参见Boneh等人第4页)。如果测试失败,则从步骤1重新启动协议。
Boneh等人给出了生成512、1024和2048位模数的实验的实验数据(参见Boneh等人第10页表2)。值得注意的是,3方(使用333MHz Pentium II的运行Solaris 2.5.1)生成512位模数的总时间为9秒,总网络流量为0.18Mb。
用于计算n的MPC
对于具有私钥(p,q)的RSA模数n=pq的多方生成,采用了Boneh等人提出的方法。该算法假设随机选择一个由使用最少通信轮数的3名矿工组成的子委员会。
建立
使用唯一、安全的子委员会遴选来选择矿工M
多方计算
步骤1:矿工M
步骤2:矿工M
n=(p
步骤3:矿工M
步骤4:如果步骤3导致找到有效复合n,则将n传播到网络的其余部分用于计算
鉴于多方计算已在上面计算,下一阶段是计算φ(n)。为此,当计算变得不对称时,矿工需要知道谁是矿工M
步骤1:矿工M
φ
步骤2:M
φ
步骤3:每个子委员会成员都可以使用分布式计算来计算
φ(n)=φ
观察到
φ(n)=(φ
=(n-p
=n-(p
=n-p-q+1
=(p-1)(q-1)。
请注意,一旦委员会知道φ(n),所述委员会中的每个人都可以推断(p,q)。可以证明(在不失一般性的情况下)
因此,在提出时间锁定难题的解决方案之前,不能计算φ(n)。因此,特别重要的是,直到找到有效区块之后,所述委员会才能共享φ(n)。
关于在非并行挖掘(NPM)区块链上进行挖掘的时间锁定难题
本公开的实施例以新颖的方式组合可验证随机函数、多方计算和时间锁定难题,以创建用于PoW区块链网络的挖掘算法。该算法的目的是计算一个数字L,该数字很难找到,但在某些秘密信息已知的情况下可以进行验证。
假设:
为了在每个周期内达成全网共识,需要满足以下条件:
·诚实多数:至少51%的矿工必须是诚实的。对所有公共区块链网络存在相同要求。
·诚实多数子委员会:每个子委员会的3名成员中的2名成员必须是诚实的,以防止私钥或陷门函数泄露。可以采用任何合适的激励策略。
·完全连通性:网络中随机的子委员会的遴选需要矿工之间完全连通,以便能够有效地进行多方计算。
方法1:预定平方数
方法
步骤1:一组网络矿工M
步骤2a:矿工M
n=pq
没有任何单个矿工能够计算(p,q)。
步骤2b:矿工M
步骤3a:具有公钥PK
其中,X是前一个区块头的哈希值。
步骤3b:矿工M
a=L
b=L
t
步骤3c(困难问题):矿工M
L是解决方案
步骤4:(假设M
步骤5a:验证者进行检查
L
步骤5b:矿工M
φ(n)=(p-1)(q-1)
使用以下公式高效计算捷径e和e
e=2
步骤5c:每个子委员会成员可以检查
和
步骤6:如果步骤5c通过,则子委员会接受该区块为有效区块。φ(n)可以与有效区块和(L,L
分析:
所提出的方案具有以下关键特征
·使用两个值对难题进行时间锁定:t和t
·只能使用顺序计算来求解难题
·哈希函数摘要充当随机数生成器,因此该难题对于每名矿工是唯一的计算中使用的基数和指数的伪随机性意味着,虽然矿工可以估计求解所需的大致时间,但在开始挖掘之前,他们无法准确判断。
此外,可以对步骤1至步骤2b和步骤5c施加时间限制,此类腐败、缓慢或不诚实的子委员会就会遭到拒绝,并且可以很容易地重新遴选。请注意,该系统在子委员会遴选过程中不需要使用利害关系证明(尽管这在实现中可能是合乎需要的)。
方法2:使用目标阈值重复平方随机数
时间锁定难题挖掘对NPM区块链的另一种应用使用目标,使得矿工不能在计算开始之前预先确定平方数。
目标和难度:
介绍以下目标
目标值表示将被接受为有效求解值的最大值。该值类似于比特币中的目标难度参数(例如,可以在区块头中编码),并且子委员会将在验证时知道该值,参见https://en.bitcoin.it/wiki/Difficulty。
平方分布
请注意,当n是两个素数的乘积时,在{0,…,n-1}范围内的所有值中大约有1/4是二次剩余。该结果根据欧拉准则(Lehmer,Emma,“关于欧拉准则”,《澳大利亚数学学会学报》,1.1(1959年):第64-70页)中存在的术语和定义的直观用法兼容。此外,对于足够大的随机复合模数n,二次剩余的分布近似均匀,这意味着在0,1,…,T
那么
哈希解决方案:对于所感知的平方分布的模糊性,解决方案是针对目标哈希L并测量该值,即检查
H(L)<T
步骤1:一组网络矿工M
步骤2a:矿工M
n=pq
而无需明确计算(p,q)。
步骤2b:矿工M
步骤3a:具有公钥PK
其中,X是前一个区块头的哈希值。
步骤3b(困难问题):矿工M
和
H(L)<T
L是解决方案,T
步骤4:(假设M
步骤5a:验证者进行检查
L
步骤5b:矿工M
φ(n)=(p-1)(q-1)
使用以下公式高效计算捷径e和e
e=2
和
e·e
步骤5c:每个子委员会成员可以检查
和
步骤6:如果步骤5c通过,则子委员会接受该区块为有效区块。φ(n)可以与有效区块和(L,L
分析
该技术具有以下特征
·使用两个值对难题进行时间锁定:t和t
·难题解决方案(类似于比特币中的随机数)只能使用顺序计算来找到
·难题解决方案(随机数)依赖于公钥。这意味着必须为迭代随机数值的每个实体生成新公钥
与方法1一样,可以对步骤1至步骤2b和步骤5c施加时间限制,此类腐败、缓慢或不诚实的子委员会就会遭到拒绝,并且可以很容易地重新遴选。此外,随机数迭代路径本质上是连续的,并且依赖于公钥,导致矿工无法通过在同一区块候选人上进行挖掘来获得任何优势。这大大降低了形成挖掘池的动机。
因此,本公开的实施例提供了一种方法,其使得分布式计算机的平面网络能够通过计算的顺序证明来建立共识。可以使用四种算法:使用可验证随机函数的子委员会遴选、用于建立RSA模数的多方计算、具有伪随机输入的时间锁定难题。本公开的实施例还利用比特币协议原生的密码原语(哈希函数、椭圆曲线密码术)以及基于素因式分解难度的难题。
考虑到低网络延迟和诚实的大多数网络参与者以及诚实的大多数的子委员会遴选的假设,实施例在规模上是经济上可行的,并且强烈抵制挖掘集中化。
现在转到图2,提供了可用于实施本公开的至少一个实施例的计算设备2600的说明性简化框图。在各种实施例中,计算设备2600可用于实现以上示出和说明的任何系统。例如,计算设备2600可配置为用作数据服务器、网络服务器、便携式计算设备、个人计算机或任何电子计算设备。如图2所示,计算设备2600可包括具有一级或多级高速缓存的一个或多个处理器以及存储器控制器(统称为2602),所述存储器控制器可被配置为与包括主存储器2608和永久存储器2610的存储子系统2606通信。如图所示,主存储器2608可以包括动态随机存取存储器(DRAM)2618和只读存储器(ROM)2620。存储子系统2606和高速缓存存储器2602可用于存储信息,诸如与本公开中所描述的交易和区块相关联的细节。处理器2602可用于提供本公开中描述的任何实施例的步骤或功能。
处理器2602还可以与一个或多个用户界面输入设备2612、一个或多个用户界面输出设备2614和网络接口子系统2616通信。
总线子系统2604可以提供用于使计算设备2600的各个组件和子系统能够按预期彼此通信的机制。虽然总线子系统2604示意性地示出为单个总线,但是总线子系统的替代实施例可以利用多个总线。
网络接口子系统2616可以向其他计算设备和网络提供接口。网络接口子系统2616可以作为从计算设备2600接收数据和向其他系统传输数据的接口。例如,网络接口子系统2616可以使数据技术人员能够将设备连接到网络,使得数据技术人员能够在远程位置(例如,数据中心)向设备发送数据并从设备接收数据。
用户界面输入设备2612可以包括一个或多个用户输入设备,例如键盘;指点设备,如集成鼠标、轨迹球、触摸板或图形平板电脑;扫描仪;条形码扫描仪;包含在显示器中的触摸屏;音频输入设备,如语音识别系统、麦克风;以及其他类型的输入设备。一般而言,术语“输入设备”的使用旨在包括用于向计算设备2600输入信息的所有可能类型的设备和机制。
一个或多个用户界面输出设备2614可以包括显示子系统、打印机或非视觉显示器(例如,音频输出设备等)。显示子系统可以是阴极射线管(CRT)、平板设备(例如,液晶显示器(LCD))、发光二极管(LED)显示器或投影或其他显示设备。一般而言,术语“输出设备”的使用旨在包括用于从计算设备2600输出信息的所有可能类型的设备和机制。例如,可以使用一个或多个用户界面输出设备2614来呈现用户界面,以便于用户与执行所描述的过程和其中变型的应用程序进行交互(当这种交互可能合适时)。
存储子系统2606可以提供计算机可读存储介质,该计算机可读存储介质用于存储可提供本公开的至少一个实施例的功能的基本编程和数据构造。当由一个或多个处理器执行时,应用程序(程序、代码模块、指令)可以提供本公开的一个或多个实施例的功能,并且可以存储在存储子系统2606中。这些应用程序模块或指令可以由一个或多个处理器2602执行。存储子系统2606可以另外提供用于存储根据本公开所使用的数据的存储库。例如,主存储器2608和高速缓存存储器2602可以为程序和数据提供易失性存储。永久存储器2610可以提供用于程序和数据的永久(非易失性)存储,且可以包括闪存、一个或多个固态驱动器、一个或多个磁硬盘驱动器、一个或多个具有关联可移动介质的软盘驱动器、一个或多个具有关联可移动介质的光驱动器(例如,CD-ROM或DVD或蓝光)以及其他类似的存储介质。这样的程序和数据可以包括用于执行如在本公开中描述的一个或多个实施例的步骤的程序以及与在本公开中描述的交易和区块相关联的数据。
计算设备2600可以是各种类型的,包括便携式计算机设备、平板电脑、工作站或下文描述的任何其他设备。另外,计算设备2600可以包括可通过一个或多个端口(例如,USB、耳机插孔、闪电连接器等)连接至计算设备2600的另一设备。可以连接到计算设备2600的设备可以包括被配置为接受光纤连接器的多个端口。因此,该设备可以被配置为将光信号转换成电信号,所述电信号可经由将该设备连接至计算设备2600进行处理的端口传输。由于计算机和网络的不断变化的性质,图2所示的计算设备2600的描述仅用作说明设备的优选实施例的特定示例。具有比图2所示系统的组件更多或更少的许多其他配置也是可能的。
需要说明的是,上述实施例说明而不是限制本发明,本领域技术人员能够在不脱离所附权利要求定义的本发明范围的前提下设计出许多替代实施例。在权利要求书中,括号中的任何附图标记都不应解释为对权利要求的限制。词语“包括”等不排除任一项权利要求或说明书中整体列出的元件或步骤之外的元件或步骤的存在。在本说明书中,“包括”是指“包含”或“由......组成”。元件的单数形式并不排除此类元件的复数形式,反之亦然。本发明可以通过包括几个不同元件的硬件以及通过适当编程的计算机来实现。在列举几个装置的设备权利要求中,这些装置中的几个装置可以由同一硬件来体现。在互不相同的从属权利要求中引用某些措施的事实并不意味着不能有利地使用这些措施的组合。
本公开的一个实施例可以提供一种计算机实现的方法,所述方法包括以下步骤:
生成多个多方计算挑战;
为工作量证明区块链网络上的多个挖掘节点中的每个挖掘节点提供来自所述多个多方计算挑战的相应挑战。
优选地,每个挖掘节点接收相对于其他节点的不同挑战。因此,每个挑战对于其所提供的节点来说可能是唯一的,并且在所述多个多方计算挑战中没有两个挑战可以是相同的。
所述多个挖掘节点中的每个挖掘节点试图查找其相应的多方计算挑战的解决方案。这可以包括每个节点生成输出/值。这可以通过使用算法的一个或多个输入来执行。所述输入可以由各个节点保密,因为它们不与所述多个节点中的其他节点共享或传送它们各自的输入值。
优选地,所述多个多方计算挑战中的每个挑战都需要使用固有顺序算法来查找所述挑战的解决方案。所述方法还可以包括以下步骤:
生成多个进一步的多方计算挑战;和/或
为所述多个挖掘节点中的每个挖掘节点提供来自所述多个进一步的多方计算挑战的相应进一步的挑战。
优选地,当由所述多个挖掘节点中的一个挖掘节点找到多方计算挑战或进一步的多方计算挑战的解决方案时,执行这些步骤。
优选地,至少部分地由从多个基于计算机的实体中选择的基于计算机的实体的子集来执行所述多个多方计算挑战和/或所述多个进一步的多方计算挑战的生成。所述基于计算机的实体中的至少一个可以是所述区块链网络上的挖掘节点。可以根据随机或伪随机选择过程从所述多个基于计算机的实体中选择所述基于计算机的实体的子集。
生成所述多方计算挑战和/或进一步的多方计算挑战中的至少一个可以包括计算对使用随机或伪随机输入的运算的输出。生成所述多方计算挑战和/或进一步的多方计算挑战中的至少一个可以包括生成RSA密钥对。
所述挑战包括计算RSA模数。优选地,所述RSA模数用于重复平方时间锁定难题。
所述方法还可以包括以下步骤:使用固有顺序算法来查找所述多方计算挑战和/或进一步的多方计算挑战中的至少一个的解决方案。所述固有顺序算法可以包括以下运算中的至少一个:递归运算;模幂运算;和/或重复平方运算。
本发明还提供了一种系统,包括:
处理器;以及
存储器包括可执行指令,所述指令被处理器执行时,使系统执行本文描述的计算机实现的方法的任何实施例。
优选地,所述系统包括区块链网络上的多个节点,所述节点中的至少一个包括所述处理器、存储器和可执行指令。
本发明还提供了一种非暂时性计算机可读存储介质,其上存储有可执行指令,计算机系统的处理器执行所述可执行指令时,使得所述计算机系统至少执行本文所述的计算机实现的方法的实施例。
机译: 通过区块链工作量证明进行卫生保健交易验证,系统和方法
机译: 通过区块链工作量证明进行卫生保健交易验证,系统和方法
机译: 用于减少垃圾邮件攻击的基于哈希挖掘的工作量证明系统和方法