【比特币】白皮书：一种点对点的电子现金系统

原文作者：中本聪（Satoshi Nakamoto）

作者邮箱：Satoshin@gmx.com

[摘要]：本文提出了一种完全通过点对点技术实现的电子现金系统，它使得在线支付能够直接由一方发起并支付给另外一方，中间不需要通过任何的金融机构。虽然数字签名（Digital signatures）部分解决了这个问题，但是如果仍然需要第三方的支持才能防止双重支付（double-spending）的话，那么这种系统也就失去了存在的价值。我们(we)在此提出一种解决方案，使现金系统在点对点的环境下运行，并防止双重支付问题。该网络通过随机散列（hashing）对全部交易加上时间戳（timestamps），将它们合并入一个不断延伸的基于随机散列的工作量证明（proof-of-work）的链条作为交易记录，除非重新完成全部的工作量证明，形成的交易记录将不可更改。最长的链条不仅将作为被观察到的事件序列（sequence）的证明，而且被看做是来自CPU计算能力最大的池（pool）。只要大多数的CPU计算能力都没有打算合作起来对全网进行攻击，那么诚实的节点将会生成最长的、超过攻击者的链条。这个系统本身需要的基础设施非常少。信息尽最大努力在全网传播即可，节点(nodes)可以随时离开和重新加入网络，并将最长的工作量证明链条作为在该节点离线期间发生的交易的证明。

1. 简介

互联网上的贸易，几乎都需要借助金融机构作为可资信赖的第三方来处理电子支付信息。虽然这类系统在绝大多数情况下都运作良好，但是这类系统仍然内生性地受制于“基于信用的模式”(trust based model)的弱点。我们无法实现完全不可逆的交易，因为金融机构总是不可避免地会出面协调争端。而金融中介的存在，也会增加交易的成本，并且限制了实际可行的最小交易规模，也限制了日常的小额支付交易。并且潜在的损失还在于，很多商品和服务本身是无法退货的，如果缺乏不可逆的支付手段，互联网的贸易就大大受限。因为有潜在的退款的可能，就需要交易双方拥有信任。而商家也必须提防自己的客户，因此会向客户索取完全不必要的个人信息。而实际的商业行为中，一定比例的欺诈性客户也被认为是不可避免的，相关损失视作销售费用处理。而在使用物理现金的情况下，这些销售费用和支付问题上的不确定性却是可以避免的，因为此时没有第三方信用中介的存在。 所以，我们非常需要这样一种电子支付系统，它基于密码学原理而不基于信用，使得任何达成一致的双方，能够直接进行支付，从而不需要第三方中介的参与。杜绝回滚(reverse)支付交易的可能，这就可以保护特定的卖家免于欺诈；而对于想要保护买家的人来说，在此环境下设立通常的第三方担保机制也可谓轻松加愉快。在这篇论文中，我们(we)将提出一种通过点对点分布式的时间戳服务器来生成依照时间前后排列并加以记录的电子交易证明，从而解决双重支付问题。只要诚实的节点所控制的计算能力的总和，大于有合作关系的(cooperating)攻击者的计算能力的总和，该系统就是安全的。

2. 交易(Transactions)

我们定义，一枚电子货币（an electronic coin）是这样的一串数字签名：每一位所有者通过对前一次交易和下一位拥有者的公钥(Public key) 签署一个随机散列的数字签名，并将这个签名附加在这枚电子货币的末尾，电子货币就发送给了下一位所有者。而收款人通过对签名进行检验，就能够验证该链条的所有者。

该过程的问题在于，收款人将难以检验，之前的某位所有者，是否对这枚电子货币进行了双重支付。通常的解决方案，就是引入信得过的第三方权威，或者类似于造币厂(mint)的机构，来对每一笔交易进行检验，以防止双重支付。在每一笔交易结束后，这枚电子货币就要被造币厂回收，而造币厂将发行一枚新的电子货币；而只有造币厂直接发行的电子货币，才算作有效，这样就能够防止双重支付。可是该解决方案的问题在于，整个货币系统的命运完全依赖于运作造币厂的公司，因为每一笔交易都要经过该造币厂的确认，而该造币厂就好比是一家银行。 我们需要收款人有某种方法，能够确保之前的所有者没有对更早发生的交易实施签名。从逻辑上看，为了达到目的，实际上我们需要关注的只是于本交易之前发生的交易，而不需要关注这笔交易发生之后是否会有双重支付的尝试。为了确保某一次交易是不存在的，那么唯一的方法就是获悉之前发生过的所有交易。在造币厂模型里面，造币厂获悉所有的交易，并且决定了交易完成的先后顺序。如果想要在电子系统中排除第三方中介机构，那么交易信息就应当被公开宣布（publicly announced）[1] ，我们需要整个系统内的所有参与者，都有唯一公认的历史交易序列。收款人需要确保在交易期间绝大多数的节点都认同该交易是首次出现。

3. 时间戳服务器(Timestamp server)

本解决方案首先提出一个“时间戳服务器”。时间戳服务器通过对以区块(block)形式存在的一组数据实施随机散列而加上时间戳，并将该随机散列进行广播，就像在新闻或世界性新闻组网络（Usenet）的发帖一样[2][3][4][5] 。显然，该时间戳能够证实特定数据必然于某特定时间是的确存在的，因为只有在该时刻存在了才能获取相应的随机散列值。每个时间戳应当将前一个时间戳纳入其随机散列值中，每一个随后的时间戳都对之前的一个时间戳进行增强(reinforcing)，这样就形成了一个链条（Chain）。

4. 工作量证明（Proof-of-Work）

为了在点对点的基础上构建一组分散化的时间戳服务器，仅仅像报纸或世界性新闻网络组一样工作是不够的，我们还需要一个类似于亚当•柏克（Adam Back）提出的哈希现金（Hashcash）[6] 。在进行随机散列运算时，工作量证明机制引入了对某一个特定值的扫描工作，比方说SHA-256下，随机散列值以一个或多个0开始。那么随着0的数目的上升, 找到这个解所需要的工作量将呈指数增长，而对结果进行检验则仅需要一次随机散列运算。 我们在区块中补增一个随机数(Nonce)，这个随机数要使得该给定区块的随机散列值出现了所需的那么多个0。我们通过反复尝试来找到这个随机数，直到找到为止，这样我们就构建了一个工作量证明机制。只要该CPU耗费的工作量能够满足该工作量证明机制，那么除非重新完成相当的工作量，该区块的信息就不可更改。由于之后的区块是链接在该区块之后的，所以想要更改该区块中的信息，就还需要重新完成之后所有区块的全部工作量。

同时，该工作量证明机制还解决了在集体投票表决时，谁是大多数的问题。如果决定大多数的方式是基于IP地址的，一IP地址一票，那么如果有人拥有分配大量IP地址的权力，则该机制就被破坏了。而工作量证明机制的本质则是一CPU一票。“大多数”的决定表达为最长的链，因为最长的链包含了最大的工作量。如果大多数的CPU为诚实的节点控制，那么诚实的链条将以最快的速度延长，并超越其他的竞争链条。如果想要对业已出现的区块进行修改，攻击者必须重新完成该区块的工作量外加该区块之后所有区块的工作量，并最终赶上和超越诚实节点的工作量。我们将在后文证明，设想一个较慢的攻击者试图赶上随后的区块，那么其成功概率将呈指数化递减。 另一个问题是，硬件的运算速度在高速增长，而节点参与网络的程度则会有所起伏。为了解决这个问题，工作量证明的难度(the proof-of-work difficulty)将采用移动平均目标的方法来确定，即令难度指向令每小时生成区块的速度为某一个预定的平均数。如果区块生成的速度过快，那么难度就会提高。

5. 网络

运行该网络的步骤如下：

• 1. 新的交易向全网进行广播；
• 2. 每一个节点都将收到的交易信息纳入一个区块中；
• 3. 每个节点都尝试在自己的区块中找到一个具有足够难度的工作量证明；
• 4. 当一个节点找到了一个工作量证明，它就向全网进行广播；
• 5. 当且仅当包含在该区块中的所有交易都是有效的且之前未存在过的，其他节点才认同该区块的有效性；
• 6. 其他节点表示他们接受该区块，而表示接受的方法，则是在跟随该区块的末尾，制造新的区块以延长该链条，而将被接受区块的随机散列值视为先于新区快的随机散列值。

节点始终都将最长的链条视为正确的链条，并持续工作和延长它。如果有两个节点同时广播不同版本的新区块，那么其他节点在接收到该区块的时间上将存在先后差别。当此情形，他们将在率先收到的区块基础上进行工作，但也会保留另外一个链条，以防后者变成最长的链条。该僵局（tie）的打破要等到下一个工作量证明被发现，而其中的一条链条被证实为是较长的一条，那么在另一条分支链条上工作的节点将转换阵营，开始在较长的链条上工作。 所谓“新的交易要广播”，实际上不需要抵达全部的节点。只要交易信息能够抵达足够多的节点，那么他们将很快被整合进一个区块中。而区块的广播对被丢弃的信息是具有容错能力的。如果一个节点没有收到某特定区块，那么该节点将会发现自己缺失了某个区块，也就可以提出自己下载该区块的请求。

6. 激励

我们约定如此：每个区块的第一笔交易进行特殊化处理，该交易产生一枚由该区块创造者拥有的新的电子货币。这样就增加了节点支持该网络的激励，并在没有中央集权机构发行货币的情况下，提供了一种将电子货币分配到流通领域的一种方法。这种将一定数量新货币持续增添到货币系统中的方法，非常类似于耗费资源去挖掘金矿并将黄金注入到流通领域。此时，CPU的时间和电力消耗就是消耗的资源。 另外一个激励的来源则是交易费（transaction fees）。如果某笔交易的输出值小于输入值，那么差额就是交易费，该交易费将被增加到该区块的激励中。只要既定数量的电子货币已经进入流通，那么激励机制就可以逐渐转换为完全依靠交易费，那么本货币系统就能够免于通货膨胀。 激励系统也有助于鼓励节点保持诚实。如果有一个贪婪的攻击者能够调集比所有诚实节点加起来还要多的CPU计算力，那么他就面临一个选择：要么将其用于诚实工作产生新的电子货币，或者将其用于进行二次支付攻击。那么他就会发现，按照规则行事、诚实工作是更有利可图的。因为该等规则使得他能够拥有更多的电子货币，而不是破坏这个系统使得其自身财富的有效性受损。

7. 回收硬盘空间

如果最近的交易已经被纳入了足够多的区块之中，那么就可以丢弃该交易之前的数据，以回收硬盘空间。为了同时确保不损害区块的随机散列值，交易信息被随机散列时，被构建成一种Merkle树（Merkle tree）[7] 的形态，使得只有根(root)被纳入了区块的随机散列值。通过将该树（tree）的分支拔除（stubbing）的方法，老区块就能被压缩。而内部的随机散列值是不必保存的。

不含交易信息的区块头（Block header）大小仅有80字节。如果我们设定区块生成的速率为每10分钟一个，那么每一年产生的数据位4.2MB。（80 bytes * 6 * 24 * 365 = 4.2MB）。2008年，PC系统通常的内存容量为2GB，按照摩尔定律的预言，即使将全部的区块头存储于内存之中都不是问题。

8. 简化的支付确认（Simplified Payment Verification）

在不运行完整网络节点的情况下，也能够对支付进行检验。一个用户需要保留最长的工作量证明链条的区块头的拷贝，它可以不断向网络发起询问，直到它确信自己拥有最长的链条，并能够通过merkle的分支通向它被加上时间戳并纳入区块的那次交易。节点想要自行检验该交易的有效性原本是不可能的，但通过追溯到链条的某个位置，它就能看到某个节点曾经接受过它，并且于其后追加的区块也进一步证明全网曾经接受了它。

当此情形，只要诚实的节点控制了网络，检验机制就是可靠的。但是，当全网被一个计算力占优的攻击者攻击时，将变得较为脆弱。因为网络节点能够自行确认交易的有效性，只要攻击者能够持续地保持计算力优势，简化的机制会被攻击者焊接的（fabricated）交易欺骗。那么一个可行的策略就是，只要他们发现了一个无效的区块，就立刻发出警报，收到警报的用户将立刻开始下载被警告有问题的区块或交易的完整信息，以便对信息的不一致进行判定。对于日常会发生大量收付的商业机构，可能仍会希望运行他们自己的完整节点，以保持较大的独立完全性和检验的快速性。

9. 价值的组合与分割（Combining and Splitting Value）

虽然可以单个单个地对电子货币进行处理，但是对于每一枚电子货币单独发起一次交易将是一种笨拙的办法。为了使得价值易于组合与分割，交易被设计为可以纳入多个输入和输出。一般而言是某次价值较大的前次交易构成的单一输入，或者由某几个价值较小的前次交易共同构成的并行输入，但是输出最多只有两个：一个用于支付，另一个用于找零（如有）。 需要指出的是，当一笔交易依赖于之前的多笔交易时，这些交易又各自依赖于多笔交易，但这并不存在任何问题。因为这个工作机制并不需要展开检验之前发生的所有交易历史。

10. 隐私（Privacy）

传统的造币厂模型为交易的参与者提供了一定程度的隐私保护，因为试图向可信任的第三方索取交易信息是严格受限的。但是如果将交易信息向全网进行广播，就意味着这样的方法失效了。但是隐私依然可以得到保护：将公钥保持为匿名。公众得知的信息仅仅是有某个人将一定数量的货币发所给了另外一个人，但是难以将该交易同特定的人联系在一起，也就是说，公众难以确信，这些人究竟是谁。这同股票交易所发布的信息是类似的，股票交易发生的时间、交易量是记录在案且可供查询的，但是交易双方的身份信息却不予透露。 作为额外的预防措施，使用者可以让每次交易都生成一个新的地址，以确保这些交易不被追溯到一个共同的所有者。但是由于并行输入的存在，一定程度上的追溯还是不可避免的，因为并行输入表明这些货币都属于同一个所有者。此时的风险在于，如果某个人的某一个公钥被确认属于他，那么就可以追溯出此人的其它很多交易。

11. 计算

设想如下场景：一个攻击者试图比诚实节点产生链条更快地制造替代性区块链。即便它达到了这一目的，但是整个系统也并非就此完全受制于攻击者的独断意志了，比方说凭空创造价值，或者掠夺本不属于攻击者的货币。这是因为节点将不会接受无效的交易，而诚实的节点永远不会接受一个包含了无效信息的区块。一个攻击者能做的，最多是更改他自己的交易信息，并试图拿回他刚刚付给别人的钱。 诚实链条和攻击者链条之间的竞赛，可以用二叉树随机漫步（Binomial Random Walk)来描述。成功事件定义为诚实链条延长了一个区块，使其领先性+1，而失败事件则是攻击者的链条被延长了一个区块，使得差距-1。 攻击者成功填补某一既定差距的可能性，可以近似地看做赌徒破产问题（Gambler’s Ruin problem）。假定一个赌徒拥有无限的透支信用，然后开始进行潜在次数为无穷的赌博，试图填补上自己的亏空。那么我们可以计算他填补上亏空的概率，也就是该攻击者赶上诚实链条，如下所示[8] ：

假定p>q，那么攻击成功的概率就因为区块数的增长而呈现指数化下降。由于概率是攻击者的敌人，如果他不能幸运且快速地获得成功，那么他获得成功的机会随着时间的流逝就变得愈发渺茫。那么我们考虑一个收款人需要等待多长时间，才能足够确信付款人已经难以更改交易了。我们假设付款人是一个支付攻击者，希望让收款人在一段时间内相信他已经付过款了，然后立即将支付的款项重新支付给自己。虽然收款人届时会发现这一点，但为时已晚。 收款人生成了新的一对密钥组合，然后只预留一个较短的时间将公钥发送给付款人。这将可以防止以下情况：付款人预先准备好一个区块链然后持续地对此区块进行运算，直到运气让他的区块链超越了诚实链条，方才立即执行支付。当此情形，只要交易一旦发出，攻击者就开始秘密地准备一条包含了该交易替代版本的平行链条。 然后收款人将等待交易出现在首个区块中，然后在等到z个区块链接其后。此时，他仍然不能确切知道攻击者已经进展了多少个区块，但是假设诚实区块将耗费平均预期时间以产生一个区块，那么攻击者的潜在进展就是一个泊松分布，分布的期望值为：

当此情形，为了计算攻击者追赶上的概率，我们将攻击者取得进展区块数量的泊松分布的概率密度，乘以在该数量下攻击者依然能够追赶上的概率。

化为如下形式，避免对无限数列求和：

写为如下C语言代码：

#include double AttackerSuccessProbability(double q, int z) { double p = 1.0 - q; double lambda = z * (q / p); double sum = 1.0; int i, k; for (k = 0; k <= z; k++) { double poisson = exp(-lambda); for (i = 1; i <= k; i++) poisson *= lambda / i; sum -= poisson * (1 - pow(q / p, z - k)); } return sum; } 

对其进行运算，我们可以得到如下的概率结果，发现概率对z值呈指数下降。

当q=0.1时 z=0 P=1.0000000 z=1 P=0.2045873 z=2 P=0.0509779 z=3 P=0.0131722 z=4 P=0.0034552 z=5 P=0.0009137 z=6 P=0.0002428 z=7 P=0.0000647 z=8 P=0.0000173 z=9 P=0.0000046 z=10 P=0.0000012

当q=0.3时 z=0 P=1.0000000 z=5 P=0.1773523 z=10 P=0.0416605 z=15 P=0.0101008 z=20 P=0.0024804 z=25 P=0.0006132 z=30 P=0.0001522 z=35 P=0.0000379 z=40 P=0.0000095 z=45 P=0.0000024 z=50 P=0.0000006

求解令P<0.1%的z值：

为使P<0.001，则 q=0.10 z=5 q=0.15 z=8 q=0.20 z=11 q=0.25 z=15 q=0.30 z=24 q=0.35 z=41 q=0.40 z=89 q=0.45 z=340

12.结论

我们在此提出了一种不需要信用中介的电子支付系统。我们首先讨论了通常的电子货币的电子签名原理，虽然这种系统为所有权提供了强有力的控制，但是不足以防止双重支付。为了解决这个问题，我们提出了一种采用工作量证明机制的点对点网络来记录交易的公开信息，只要诚实的节点能够控制绝大多数的CPU计算能力，就能使得攻击者事实上难以改变交易记录。该网络的强健之处在于它结构上的简洁性。节点之间的工作大部分是彼此独立的，只需要很少的协同。每个节点都不需要明确自己的身份，由于交易信息的流动路径并无任何要求，所以只需要尽其最大努力传播即可。节点可以随时离开网络，而想重新加入网络也非常容易，因为只需要补充接收离开期间的工作量证明链条即可。节点通过自己的CPU计算力进行投票，表决他们对有效区块的确认，他们不断延长有效的区块链来表达自己的确认，并拒绝在无效的区块之后延长区块以表示拒绝。本框架包含了一个P2P电子货币系统所需要的全部规则和激励措施。

• 1.W Dai（戴伟）,a scheme for a group of untraceable digital pseudonyms to pay each other with money and to enforce contracts amongst themselves without outside help（一种能够借助电子假名在群体内部相互支付并迫使个体遵守规则且不需要外界协助的电子现金机制）, “B-money”, http://www.weidai.com/bmoney.txt, 1998↵
• 2.H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements,"（在最小化信任的基础上设计一种时间戳服务器） In 20th Symposium on Information Theory in the Benelux, May 1999.↵
• 3.S. Haber, W.S. Stornetta, "How to time-stamp a digital document," （怎样为电子文件添加时间戳）In Journal of Cryptology, vol 3, No.2, pages 99-111, 1991.↵
• 4.D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping,"（提升电子时间戳的效率和可靠性） In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.↵
• 5.S. Haber, W.S. Stornetta, "Secure names for bit-strings,"（比特字串的安全命名） In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997. on Computer and Communications Security, pages 28-35, April 1997.↵
• 6.A. Back, "Hashcash - a denial of service counter-measure,"（哈希现金——拒绝服务式攻击的克制方法）http://www.hashcash.org/papers/hashcash.pdf, 2002. ↵
• 7.R.C. Merkle, "Protocols for public key cryptosystems," （公钥密码系统的协议）In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980. S. Haber, W.S. Stornetta, "Secure names for bit-strings,"（比特字串安全命名） In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997. on Computer and Communications Security, pages 28-35, April 1997. H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements,"（在最小化信任的条件下设计一种时间戳服务器） In 20th Symposium on Information Theory in the Benelux, May 1999. ↵
• 8.W. Feller, "An introduction to probability theory and its applications," （概率学理论与应用导论）1957 ↵

【共识机制】区块链共识机制浅谈

前言

本文对区块链中常见的共识机制做了一些介绍和自己的看法，欢迎指教。

区块链解决了在不可信信道上传输可信信息、价值转移的问题，而共识机制解决了区块链如何在分布式场景下达成一致性的问题。所以我认为区块链的伟大之处就是它的共识机制在去中心化的思想上解决了节点间互相信任的问题。区块链能在众多节点达到一种较为平衡的状态也是因为共识机制。尽管密码学占据了区块链的半壁江山，但是共识机制是保障区块链系统不断运行下去的关键。

其实当分布式的思想被提出来时，人们就开始根据FLP定理和CAP定理设计共识算法。

规范的说，理想的分布式系统的一致性应该满足以下三点：

• 1.可终止性（Termination）：一致性的结果可在有限时间内完成。
• 2.共识性(Consensus)：不同节点最终完成决策的结果应该相同。
• 3.合法性(Validity)：决策的结果必须是其他进程提出的提案。

但是在实际的计算机集群中，可能会存在以下问题:

• 1.节点处理事务的能力不同，网络节点数据的吞吐量有差异
• 2.节点间通讯的信道可能不安全
• 3.可能会有作恶节点出现
• 4.当异步处理能力达到高度一致时，系统的可扩展性就会变差（容不下新节点的加入）。

科学家认为，在分布式场景下达成完全一致性是不可能的。但是工程学家可以牺牲一部分代价来换取分布式场景的一致性，上述的两大定理也是这种思想，所以基于区块链设计的各种公式机制都可以看作牺牲那一部分代价来换取多适合的一致性，我的想法是可以在这种思想上进行一个灵活的变换，即在适当的时间空间牺牲一部分代价换取适应于当时场景的一致性，可以实现灵活的区块链系统，即可插拔式的区块链系统。今天就介绍一下我对各种共识机制的看法和分析，分布式系统中有无作恶节点分为拜占庭容错和非拜占庭容错机制。下面先介绍拜占庭容错的共识算法：

POW:比特币莱特币等货币型区块链（公有链）(proof of work)

在比特币等货币型区块链中让各节点达成一致性的共识机制为工作量证明，也是我们说的挖矿。

工作量证明是矿工在处理交易数据（对数据也是进行哈希）的同时不断的进行哈希计算，求得一位前23位为0的哈希值，这个值成为nonce黄金数。

当全网有一位矿工哈希出nonce时，他就会把自己打包的区块公布出去，其他节点收到区块验证区块后就会一致性认为这个区块接到了区块链上，就继续进行下一个区块的打包和哈希计算。在这个过程中，中本聪大神是通过算力的比拼牺牲了一部分最终一致性（因为会有分叉的产生）并且需要等待多个确认，但是这种简单暴力的方法却保证了整个区块链系统的合法性，而且把区块链系统的健壮性提升到极致，就算全网只剩下一个节点运行，这个区块链系统还是会继续运行下去。最后POW也充分提高了区块链系统的安全性，依靠51%攻击理论去破坏区块链系统是只有政府或者疯子才会采取的方法。

优点：

• 完全去中心化
• 节点自由进出，容易实现。
• 破坏系统花费的成本巨大

- 缺点：

• 对节点的性能网络环境要求高
• 无法达成最终一致性
• 最关键的，浪费能源！

POS:Bitshares和qutm等合约型区块链（proof of stake）

如果简单的把POW当作比力量大小的话，POS就是比耐力多少。 POS是根据钱包里面货币的多少以及货币在钱包里存在的天数来合成一个单位（币天）。它根据币天的关系对计算机进行哈希计算降低了难度，降低了计算机的门槛，但是对计算机还是有一定要求的，它把钱包和区块链系统的一致性绑定在一起。谁的钱包里的币天数越大谁拥有记账权的概率就越大。但是它和POW机制一样解决问题的思想也导致了它与POW拥有一样的缺点，也是牺牲了一部分的共识（同样分叉），而且需要等待多个确认。

优点：

• 对节点性能要求低，达成共识时间短（网络环境好的话可实现毫秒级）

缺点：

• 没有最终一致性

DPOS

是基于POS衍生出的更专业的解决方案，他是类似于董事会的投票机制，选举出n个记账节点，在节点中提案者提交的提案被这些记账节点投票决定谁是正确的。

优点：

• 减少记账节点规模，属于弱中心化，效率提高。

缺点：

• 牺牲了去中心化的概念，不适合公有链。

以太坊前三个阶段即Frontier（前沿）、Homestead（家园）、Metropolis（大都会）。第四个阶段，即Serenity（宁静），将采用PoS机制。Casper：以太坊前三个阶段采用的是POW共识机制，第四个阶段将采用自己创建的POS机制，名为投注共识。这种机制增加了惩罚机制，并基于POS的思想在记账节点中选取验证人。详情见以太坊紫皮书。

dBFT：小蚁区块链（delegated BFT，授权拜占庭容错机制）

用权益来选出记账人，然后记账人之间通过拜占庭容错算法达成共识。

优点：

专业化的记账人可以容忍任何类型的错误记账由多人协同完成，每一个区块都有最终性，不会分叉算法的可靠性有 严格的数学证明

缺点：

当三分之一或以上记账人停止工作后，系统将无法提供服务当三分之一或以上记账人联合作恶，且其他所有的记账人恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据

PBFT：Fabric使用的经典算法（拜占庭容错）

这是一种基于消息传递的一致性算法，算法经过三个阶段达成一致性，这些阶段可能因为失败而重复进行。

假设节点总数为3f+1，f为拜占庭错误节点：

当节点发现leader作恶时，通过算法选举其他的replica为leader。 leader通过pre-prepare （第一个协议阶段）消息把它选择的 value广播给其他replica节点，其他的replica节点如果接受则发送 prepare（第二个协议阶段），如果失败则不发送。

一旦2f个节点接受prepare消息，则节点发送commit（第三个协议阶段）消息。 当2f+1个节点接受commit消息后，代表该value值被确定 如下图表示了4个节点，0为leader，同时节点3为fault节点，该节点不响应和发出任何消息。最终节点状态达到commited时，表示该轮共识成功达成。 注：预准备阶段（pre-prepare）： 主节点分配一个序列号n给收到的请求，然后向所有备份节点群发预准备消息，预准备消息的格式为<<PRE-PREPARE,v,n,d>,m>，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。 准备阶段（prepare）： 如果备份节点i接受了预准备消息<<PRE-PREPARE,v,n,d>,m>，则进入准备阶段。在准备阶段的同时，该节点向所有副本节点发送准备消息<PREPARE,v,n,d,i>，并且将预准备消息和准备消息写入自己的消息日志。如果看预准备消息不顺眼，就什么都不做。 确认阶段（commit）： 当(m,v,n,i)条件为真的时候，副本i将<COMMIT,v,n,D(m),i>向其他副本节点广播，于是就进入了确认阶段。

优点：

上述其他算法都脱离不了币的存在，币的存在及它的奖励机制会让区块链这一单一的世界穷者更穷，富者更富。共识效率高，可实现高频交易。

缺点：

当系统只剩下33%的节点运行时，系统会停止运行。

非拜占庭容错的共识机制即不考虑有恶意节点的情况，人们考虑到1990 年由 Leslie Lamport 提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。

Paxos

Paxos被用于分布式系统中典型的例子就是Zookeeper，他是第一个被证明的共识算法，其原理基于两阶段提交并扩展。

Paxos算法中将节点分为三种类型：proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色acceptor：负责对提案进行投票。往往是服务端担任该角色learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。Paxos 能保证在超过50%的正常节点存在时，系统能达成共识。

Paft

Raft算法是对Paxos算法的一种简单实现。

它包括三种角色：leader、candiate 和 follower，其基本过程为：Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选为 leader同步 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记录，这里的log指的是各种事件的发生记录

Pool验证池：布比区块链

基于传统的分布式一致性技术，加上数据验证机制。

优点：不需要代币也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基础上，实现秒级共识验证。缺点：去中心化程度不如bictoin；更适合多方参与的多中心商业模式。

【共识机制】什么是区块链共识？

共识（Consensus）过程是一个非常有趣的过程。

在我们的日常生活中，几乎所有的事情都是达成共识的过程。

达成共识越分散的过程，其效率就越低，但满意度越高，因此也越稳定；相反，达成共识越集中的过程，效率越高，也越容易出现独裁和腐败现象。

• 达成共识常用的一种方法就是通过物质上的激励以对某个事件达成共识；但是这种共识存在的问题就是容易被外界其它更大的物质激励所破坏。
• 还有一种就是群体中的个体按照符合自身利益或整个群体利益的方向来对某个事件自发地达成共识；当然形成这种自发式的以维护群体利益为核心的共识过程还是需要时间和环境因素的，但是一旦达成这样的共识趋势，其共识结果也越稳定，越不容易被破坏。

在比特币和其它区块链币中，也存在如何达成共识的问题。或者说，比特币或其它区块链币最核心的问题也是如何在去中心化的环境中达成共识。

区块链是比特币背后的核心技术，也是支撑比特币的基础架构。因此在谈区块链共识，就必然要谈比特币的共识。

比特币最核心的突破是在去中心化的情况下对交易事件达成了共识，即在没有中心组织的情况下对某个交易的有效性达成了一致。

比特币实现这个共识的方法主要包括两个部分：

• 激励；即通过每个区块产生一定量的新比特币来激励参与者；
• 引入外部资源确保安全；即通过大量的外部计算来确保共识的安全性，也就是工作量证明（Proof of Power）；

这也是几乎所有PoW币种所采用的的方法。

而这套方法要能持续长期运行下去的前提就是：

• 这种激励对参与者要有足够的吸引力；也就是说比特币要一直涨价，才能吸引参与者持续参与挖矿计算，以维护整个网络的运行；否则就会导致参与的人减少，破坏网络安全；
• 没有外部攻击；由于比特币引入了外部计算来确保安全，因此只要有足够的挖矿算力（超过维护系统算力的51%）就能对系统成功进行攻击，这也是比特币长期存在的安全隐患之一；因为只要有钱，就能买到设备和算力。

正是由于比特币存在的问题，例如消耗大量的资源、外部51%攻击等，出现了PoS（Proof of Stake）共识机理。

总体上，PoS共识理论和实践目前仍处在探索阶段。

最原始的PoS机理就是用股权代替PoW中的挖矿算力，来模拟比特币的挖矿过程。请注意，这个过程没有引入外部资源，而是仅仅依靠自身的币种股份来维护网络安全，因此其不需要消耗大量能源来进行计算；而且由于其没有引入外部的资源，因此不会担心外部攻击，例如外界的算力攻击。

看起来PoS是很完美的，但是它存在一个严重漏洞。

PoS存在内部的Nothing-at-Stake攻击。

什么是Nothing-at-Stake（常写作N@S）攻击？

假设系统中出现了两个分支链，那么对于持有币的”挖矿者“来讲，最佳的操作策略就是同时在两个分支上进行“挖矿”，这样，无论哪个分支胜出，对币种持有者来讲，都会获得本属于他的利益，即不会有利益损失。而且由于不需要算力消耗，因此PoS中在两个分支上挖矿是可行的。

这导致的问题是，只要系统存在分叉，“矿工们”都会同时在这几个分支上挖矿；因此在某个情况下，发起攻击的分叉链是极有可能成功的，因为所有人也都在这个分叉链上达成了共识；而且甚至不用持有51%的币量，就可以成功发起分叉攻击；

而这在PoW中是不可行的，因为挖矿需要消耗算力，矿工只能在一个分支上进行挖矿。

第二个问题

重写历史攻击，即攻击者可以通过购买原始持有币种的账户来从头发起攻击，重新分叉一个区块链。因为原始的币种持有者可以将币转移至其它账户，因此他是可以在没有损失的情况下将原始账户出售给攻击者的。攻击者需要的就是有足够数量币的原始账户；当然了，这也只是概率问题，因为有可能原始账户持有者不会出售他们的账户，但是理论上确实存在这种攻击。

第三个问题

尽管PoS中的挖矿不用消耗算力，运行成本很低，但是也存在如何激励矿工的问题。因为一般的PoS系统是没有新币产生的，矿工只能赚取交易费，而且在交易费不高的情况下，对矿工的激励也是很有限的。

当然了，也有很多PoS币种解决这个问题的办法就是持续的再产生新币来激励挖矿者，这导致的问题就是通胀。

上述3个问题是PoS要解决的，尤其是N@S的问题尤为重要，因为如果没有其它约束机制，这种攻击是完全有可能实现的。

从以上可以看出，无论是PoW还是PoS机理的共识过程，其必要条件有两个：

• 信息公开共享；
• 个体参与；

以现实为例，事件的信息越透明、所涉及到的人员参与度越高，最终形成的共识也就越稳定、越持久。这与区块链共识是一致的。

以上是个人的对区块链共识的一些学习心得，期望能看到更多这方面的讨论和研究文章，与爱好者一起分享。

【共识机制】区块链共识机制与分布式一致性算法

咱们在之前的很多篇文章里简单地提起了“共识算法”以及“共识攻击”，大家应该对于我们之前提到的“共识攻击”印象还比较深刻吧，对的，就是我们所说的这和公司占有股份一个道理，当你占有整个公司“51%”的股份时，那就是控股了，岂不是可以为所欲为了呢？在区块链技术这也一样，咱们都知道区块链记账以后是不可以篡改的，就算是合理交易写错地址了也不行！but!当你能说服整个区块链上51%的结点同意你的请求时就能够修改记账信息，当这一方法用到不好的方面，那就是“共识攻击”了。而“共识攻击”就是的原理还是“共识算法”，那么这篇文章就带大家走进共识算法咯！

这篇文章将为大家介绍传统分布式一致性算法和区块链共识模型，以及一些有关两者关系的观点，并且将介绍一些常见的区块链共识模型，读完本文相信大家会对于传统分布式一致性算法和区块链共识过程的异同、关系以及区块链技术的共识算法有一个更加深刻的理解。

本文技术要点：

一、前言

1. 传统分布式一致性算法和区块链共识过程的异同点

相同点：

• Append only
• 强调序列化
• 少数服从多数原则
• 分离覆盖的问题：即长链覆盖短链区块，多节点覆盖少数节点日志

不同点：

传统分布式一致性算法大多不考虑拜占庭容错(Byzanetine Paxos除外)，即假设所有节点只发生宕机、网络故障等非人为问题，并不考虑恶意节点篡改数据的问题； 传统分布式一致性算法是面向日志（数据库）的，即更通用的情况，而区块链共识模型面向交易的，所以严格来说，传统分布式一致性算法应该处于区块链共识模型的下面一层。

2. 区块链共识模型与传统一致性算法的关系

考虑上面的不同点，结合私有链和行业链的性质，我们有：

私有链：封闭生态的存储网络，所有节点都是可信任的，如某大型集团内部多数公司。 行业链：半封闭生态的交易网络，存在对等的不信任节点，如房地产行业A、B、C、D公司。 公有链：开放生态的交易网络，这层主要是为行业链和私有链提供全球交易网络。 由于私有链是封闭生态的存储网络，也就是说使用传统分布式一致性模型应该是最优的；由于联盟行业链其半封闭半开放特性，使用Delegated Proof of XXX 是最优的，可以考虑以传统一致性算法作为基础加入拜占庭容错/安全防护机制进行改进。公有链PoW应该仍然是最优的选择。 如下图所示：

二、传统分布式一致性算法介绍

本文主要讨论主流的Paxos算法家族和Raft算法，这里抛砖引玉，网络上有关两者的资料非常丰富，大家可自行搜索查阅。

1. Paxos 算法家族

1998年Lamport提出Paxos算法，后续又增添多个改进版本的Paxos形成Paxos协议家族，且Paxos都有共同点是不容易工程实现。

• Classic Paxos ：LeaderLess，又名Basic Paxos，以下均为Paxos的变种，基于CAP定律，侧重了不同方向。
• Cheap Paxos
• Egalitarian Paxos ： conflicts rare
• Fast Paxos ： Leader only when needed ，conflicts common
• Multi-Paxos ：Leader driven
• Byzanetine Paxos

"Byzantine Paxos adds an extra message (Verify) which acts to distribute knowledge and verify the actions of the other processors".Lamport 在2011年的论文《Leaderless Byzanetine Paxos》中表示不清楚实践中是否有效，考虑Paxos本身实现的难度，此方案工程角度不是最优，但是系统角度应该是最好的。

本小节参考：

• Wikipedia_Paxos
• Leaderless Byzanetine Paxos

2. Raft 算法

这是一个非常友好的算法，容易理解、实现，不过它是Strong Leadership的，也就是说，任意包含Leader的时刻，Leader拥有完全记账权，如果此Leader节点是恶意的，后果不堪设想。且leadership的一致性算法都有个通病，吞吐量受单个节点的限制，这点在Raft身上体现尤甚。

• Raft算法简介：https://raft.github.io/
• Raft算法动态演示：http://thesecretlivesofdata.com/raft/

3. 其他

VRR(Viewstamped Replication Revisited) 这也是一个基于leadership的一致性算法，相比上述其他算法，它的优点是延迟最小。

三、常见区块链共识模型介绍

转载地址：https://bitsharestalk.org/index.php?topic=4031.0

这是DPoS的白皮书，主要介绍了DPos，但也囊括了其他共识模型的介绍。

摘要

本白皮书介绍一种股权证明机制的新实现方式，该方式可以对交易进行秒级验证，并且能够在更短的时间内提供比现有任何股权证明系统都更好的安全性。在比特币网络产生一个区块的时间过后，一个授权股权证明系统(DPOS)能使你的交易得到20%股东的核实，而在比特币网络声明交易已几乎不可逆(6个区块，约1小时)的时间过后，在DPOS机制下，通过其代表，你的交易已经得到100%股东的核实。

1.0 背景

分布式交易总账需要在尽可能短的时间内做到安全、明确及不可逆，便于提供一个最坚实且去中心化的系统。在实践中，该流程分为两个方面：选择一个独特的节点来产生一个区块，并使得交易总账不可逆。

1.1 工作量证明机制(Proof of Work, POW)

第一个成功解决该问题的尝试是比特币系统(Bitcoin)，比特币系统使用工作量证明机制使更长总账的产生具有计算性难度。工作量证明机制就好比是乐透，平均每10分钟有一个节点找到一个区块。如果两个节点在同一个时间找到区块，那么网络将根据后续节点的决定来确定以哪个区块构建总账。从统计学角度讲，一笔交易在6个区块(约1个小时)后被认为是明确确认且不可逆的。然而，核心开发者认为，需要120个区块(约一天)，才能充分保护网络不受来自潜在更长的已将新产生的币花掉的攻击区块链的威胁。 尽管出现更长的区块链会变得不太可能，但任何拥有巨大经济资源的人都仍有可能制造一个更长的区块链或者具备足够的哈希算力来冻结用户的账户。

1.2 股权证明机制(Proof of Stake, POS)

股权证明机制已有很多不同变种，但基本概念是产生区块的难度应该与你在网络里所占的股权(所有权占比)成比例。到目前为止，已有两个系统开始运行：点点币(Peercoin)和未来币(NXT)。点点币使用一种混合模式，用你的股权调整你的挖矿难度。未来币使用一个确定性算法以随机选择一个股东来产生下一个区块。未来币算法基于你的账户余额来调整你被选中的可能性。 未来币和点点币都分别解决了谁来生产下一个区块的问题，但他们没有找到在适当的时间内使区块链具备不可逆的安全性的方法。根据我们能找到的信息，做到这点，点点币需要至少6个区块(约一小时)，未来币需要10个区块。我们找不到在10个区块后未来币能提供什么级别安全性的根据。

我们之前发布了基于交易的股权证明机制(Transactions as Proof of Stake, TaPOS)的白皮书，在该机制中，每笔交易都包含区块链中前一个区块的哈希值。通过该系统，对任何人而言，网络变得越来越安全而不可逆，因为最终每个区块都经过了股东投票。TaPOS面临的挑战是它没有定义谁来产生下一个区块。

1.3 瑞波共识机制(Ripple Consensus)

瑞波共识算法，使一组节点能够基于特殊节点列表达成共识。初始特殊节点列表就像一个俱乐部，要接纳一个新成员，必须由51%的该俱乐部会员投票通过。共识遵循这核心成员的51%权力，外部人员则没有影响力。由于该俱乐部由“中心化”开始，它将一直是“中心化的”，而如果它开始腐化，股东们什么也做不了。与比特币及点点币一样，瑞波系统将股东们与其投票权隔开，并因此比其他系统更中心化。

2.0 授权股权证明机制(DPOS)

当使用去中心化自治公司(Decentralized Autonomous Company, DAC)这一说法时，去中心化表示每个股东按其持股比例拥有影响力，51%股东投票的结果将是不可逆且有约束力的。其挑战是通过及时而高效的方法达到51%批准。

为达到这个目标，每个股东可以将其投票权授予一名代表。获票数最多的前100位代表按既定时间表轮流产生区块。每名代表分配到一个时间段来生产区块。所有的代表将收到等同于一个平均水平的区块所含交易费的10%作为报酬。如果一个平均水平的区块含有100股作为交易费，一名代表将获得1股作为报酬。 网络延迟有可能使某些代表没能及时广播他们的区块，而这将导致区块链分叉。然而，这不太可能发生，因为制造区块的代表可以与制造前后区块的代表建立直接连接。建立这种与你之后的代表(也许也包括其后的那名代表)的直接连接是为了确保你能得到报酬。

该模式可以每30秒产生一个新区块，并且在正常的网络条件下区块链分叉的可能性极其小，即使发生也可以在几分钟内得到解决。

## 2.1 成为一名代表

成为一名代表，你必须在网络上注册你的公钥，然后分配到一个32位的特有标识符。然后该标识符会被每笔交易数据的“头部”引用。

2.2 授权你的选票

每个钱包有一个参数设置窗口，在该窗口里用户可以选择一个或更多的代表，并将其分级。一经设定，用户所做的每笔交易将把选票从“输入代表”转移至“输出代表”。一般情况下，用户不会创建特别以投票为目的的交易，因为那将耗费他们一笔交易费。但在紧急情况下，某些用户可能觉得通过支付费用这一更积极的方式来改变他们的投票是值得的。

2.3 保持代表诚实

每个钱包将显示一个状态指示器，让用户知道他们的代表表现如何。如果他们错过了太多的区块，那么系统将会推荐用户去换一个新的代表。如果任何代表被发现签发了一个无效的区块，那么所有标准钱包将在每个钱包进行更多交易前要求选出一个新代表。

2.4 解决区块链分叉

和工作量证明系统及其他股权证明系统一样，最佳区块链是最长的有效区块链。任何时候，一名代表错过签发一个区块的机会，该区块链将比潜在竞争对手短。只要在你的交易被写入区块后的100个区块中的51%被生产出来了，那么你就可以安全地认为你在主区块链上。

也许，在防止区块链分叉所导致的损失方面，最重要的事是在事发后第一时间得知消息。因为代表们通过生产区块得到很好的报酬，他们将保持接近100%的在线时间来防止因被投票罢免而损失收入。你可以安全地认为如果在过去的10个区块中，有一两个区块错过生产，则互联网的某些部分可能正发生连接问题，那么用户应该对此特别警觉并要求额外的确认数。如果10区块中有超过5个错过生产，那么这意味着你很可能在一条支链上，因此应该停止所有交易，直到分叉得到解决。

以一种及时的方式(少于5分钟)简单地发现并警示用户网络分叉，是可以最小化潜在损失的非常重要的能力。而知道你是否正处在一条支链上则更为重要。

2.5 100名代表是去中心化的吗？

因为去中心化已经成为一个流行术语，所以其定义很难完全固定。我们将自由市场看作去中心化的基本形式，并将对进入自由市场设置障碍看作是所有中心化的基础。像任何事物一样，中心化有程度之分，所以我们把授权股权证明机制与其它方案的中心化程度进行对比。

2.5.1 比特币

比特币系统目前正以授权工作量证明(Delegated Proof of Work, DPOW)为基础而运行，因此有大约10名代表控制了绝大多数的哈希算力。在那些为其竞争而能使用规模经济进行无收益挖矿的人手中，哈希算力本身就是中心化的。最后，工作量证明机制为进入市场设置障碍，使得“在职”的区块制造者无法轻易被取代。与比特币系统相比，DPOS在区块生产方面至少去中西化了10倍，并且也许在市场竞争方面去中心化了无数倍。

尽管在哈希算力方面有一定量的去中心化，当想到掌控比特币系统的股东(比特币持有者)所持股份的占比，我们认为比特币系统是最中心化的。如果你考虑使用比特币体系的用户总数，其中参与挖矿的人很可能少于百分之一。

2.5.2 点点币

点点币是一个混合系统，所以它由于工作量证明机制而是部分中心化的。和比特币系统一样，它也有矿池。与比特币相比，点点币无疑是更去中心化的，然而，因为股权证明机制矿池需要用户保持他们的电脑在线且钱包解锁，只有一小部分的股东参与了任何形式的挖矿。

2.5.3 未来币

未来币使用透明锻造，以确定的选出下一个制造节点。可以将其类比为，使用授权股权证明机制但你只能将你的投票权授予你自己，而你获得锻造区块机会的频率直接取决于你的账户余额。在这个意义上来说，未来币比点点币和比特币更为去中心化。但由于对安全风险的顾虑以及事实上大多数常规用户不会整天开启他们的电脑来籍此获得锻造机会方面的优势，它仍然遭受着少的可怜的挖矿参与度。

从这个角度来讲，我们可以断定未来币网络是由一小部分股东来保障网络安全的。事实上，如果你不上线投票，那么你将失去你的选票。为了解决这个问题，一些未来币用户用他们的股权建立股权池，并信任第三方来为他们挖矿。这是以一种形式的授权股权证明来提高股东参与度，但这也使他们的账户余额在他们参加这些矿池时承受风险。

3.0 攻击

一般而言，网络必须抵御两种类型的攻击：拒绝服务攻击和双重支付攻击。一个攻击者通过不把一些或全部的交易加入总账来进行拒绝服务攻击。这种攻击可以由任何拥有51%网络(无论比特币、未来币或其它)的人进行。而利用在网络正试图达成共识时的短期优势，可以进行双重支付攻击。为抵御这些攻击，网络必须使51%的股东尽快达成协议。

3.1 防止排除交易

拥有全部经股东投票选出的100名代表，并且按要求轮流生产区块，意味着任何一笔由至少1%的股东批准的交易能够在30分钟内加入总账。这意味着没有代表可以通过将投票支持其他代表的交易排除在外来获取利益。

3.2 将一些代表的权力中心化

与其所被授权的投票权无关，这前100人所获得的权力权重是相同的，每名代表都有一份相等的投票权。因此，无法通过获得超过1%的选票而将权力集中到一个单一代表手上。 个人或者组织控制区块链的多名代表是有可能的。但是这个过程将需要欺骗很大比例的股东数去支持“傀儡”。即使可以建立这51%傀儡，他们扰乱网络的能力仍将是有限的、能够被快速识别快速纠正的。没有工作量证明机制设置的进入障碍，占据多数的诚实用户会把攻击鉴别出来，然后将代码分叉并无视攻击者生产的区块。这种攻击可以扰乱网络，但不会是致命的。

3.3 针对代表的分布式拒绝服务攻击(DDOS)

因为只有100名代表， 可以想象一个攻击者对每名轮到生产区块的代表依次进行拒绝服务攻击。幸运的是，由于事实上每名代表的标识是其公钥而非IP地址，这种特定攻击的威胁很容易被减轻。这将使确定DDOS攻击目标更为困难。而代表之间的潜在直接连接，将使妨碍他们生产区块变得更为困难。

4.0 基于交易的股权证明机制(TaPOS)

代表制是一个短时间内达成坚固共识的高效方式，而TaPOS为股东们提供了一个长效机制来直接批准他们的代表的行为。平均而言，51%的股东在6个月内会直接确认每个区块。而取决于活跃流通的股份所占的比例，差不多10%的股东可以在几天内确认区块链。这种直接确认保障了网络的长期安全，并使所有的攻击尝试变得极度清晰易见。

5.0 高质量的服务

假设一个DPOS系统拥有100亿美元的市场总量，平均每年的交易费为0.25%，代表们合计获得所有交易费的10%，那么每名代表每年能获得25,000美元以使其节点保持在线。

这是一个利润可观的角色，许多人将为获取它持续竞争。这意味着每个想要获得这份工作的人都会想方设法从拥有这份工作的人那里把它“偷走”。为做到这点，他们将对代表行为进行统计学分析，以找到对于标准算法的任何偏离行为。一旦找到这种偏离，他们就能有希望赢得一些选票。那些拥有这份工作的人，可能会全力以赴地证明他们正在按标准软件运行。他们越有效地证明其对区块生产的正直性，越有可能保住他们的工作。你可以想象开发者会很快制作出系统，代表们可以通过这些系统快速证明哪些交易得到了广泛的散播。

事实上，市场竞争将产生用以证明代表们的正直性与可靠性的最具创造性的解决方案。让网络变得更安全的工作可以获得很多收益，而尝试绕轮网络则得不到什么好处。

6.0 结论

DPOS流程与TaPOS结合所产生的网络，其网络共识的可证明性将至少3倍于比特币、点点币及未来币网络。DPOS能够更快地达成共识，同时消除随机小股东带来小规模干扰的可能性。经济激励确保了代表们致力于证明他们有良好行为，并可能采用类似于瑞波系统的共识算法(来实现这种证明)。DPOS，事实上，是一种通过无网络分叉之虞的去中心化方式来产生瑞波特殊节点列表的方法。

【共识机制】共识算法（POW,POS,DPOS,PBFT）介绍

POW：Proof of Work，工作证明。

比特币在Block的生成过程中使用了POW机制，一个符合要求的Block Hash由N个前导零构成，零的个数取决于网络的难度值。要得到合理的Block Hash需要经过大量尝试计算，计算时间取决于机器的哈希运算速度。当某个节点提供出一个合理的Block Hash值，说明该节点确实经过了大量的尝试计算，当然，并不能得出计算次数的绝对值，因为寻找合理hash是一个概率事件。当节点拥有占全网n%的算力时，该节点即有n/100的概率找到Block Hash。

POS：Proof of Stake，股权证明。

POS：也称股权证明，类似于财产储存在银行，这种模式会根据你持有数字货币的量和时间，分配给你相应的利息。 简单来说，就是一个根据你持有货币的量和时间，给你发利息的一个制度，在股权证明POS模式下，有一个名词叫币龄，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000，这个时候，如果你发现了一个POS区块，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息(假定利息可理解为年利率5%)，那么在这个案例中，利息 = 3000 * 5% / 365 = 0.41个币，这下就很有意思了，持币有利息。

DPOS：Delegated Proof of Stake，委任权益证明。

比特股的DPoS机制，中文名叫做股份授权证明机制（又称受托人机制），它的原理是让每一个持有比特股的人进行投票，由此产生101位代表 , 我们可以将其理解为101个超级节点或者矿池，而这101个超级节点彼此的权利是完全相等的。从某种角度来看，DPOS有点像是议会制度或人民代表大会制度。如果代表不能履行他们的职责（当轮到他们时，没能生成区块），他们会被除名，网络会选出新的超级节点来取代他们。DPOS的出现最主要还是因为矿机的产生，大量的算力在不了解也不关心比特币的人身上，类似演唱会的黄牛，大量囤票而丝毫不关心演唱会的内容。

PBFT：Practical Byzantine Fault Tolerance，实用拜占庭容错算法。

PBFT是一种状态机副本复制算法，即服务作为状态机进行建模，状态机在分布式系统的不同节点进行副本复制。每个状态机的副本都保存了服务的状态，同时也实现了服务的操作。将所有的副本组成的集合使用大写字母R表示，使用0到|R|-1的整数表示每一个副本。为了描述方便，假设|R|=3f+1，这里f是有可能失效的副本的最大个数。尽管可以存在多于3f+1个副本，但是额外的副本除了降低性能之外不能提高可靠性。

以上主要是目前主流的共识算法。

从时间上来看，这个顺序也是按该共识算法从诞生到热门的顺序来定。

对于POW，直接让比特币成为了现实，并投入使用。而POS的存在主要是从经济学上的考虑和创新。而最终由于专业矿工和矿机的存在，让社区对这个标榜去中心化的算法有了实质性的中心化担忧，即传闻60％～70%的算力集中在中国。因此后来又出现DPOS，这种不需要消耗太多额外的算力来进行矿池产出物的分配权益方式。但要说能起到替代作用，DPOS来单独替代POW，POS或者POW＋POS也不太可能，毕竟存在即合理。每种算法都在特定的时间段中有各自的考虑和意义，无论是技术上，还是业务上。

如果跳出技术者的角度，更多结合政治与经济的思考方式在里面，或许还会跳出更多的共识算法，如结合类似PPP概念的共识方式，不仅能达到对恶意者的惩罚性质，还能达到最高效节约算力的目的也说不定。

至于说算法的选择，这里引用季总的这一段话作为结束：



一言以蔽之，共识最好的设计是模块化,例如Notary，共识算法的选择与应用场景高度相关，可信环境使用paxos 或者raft，带许可的联盟可使用pbft ，非许可链可以是pow，pos，ripple共识等，根据对手方信任度分级，自由选择共识机制，这样才是真的最优。

”

【基础知识】Merkle Tree 学习

Merkle Tree概念

Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。[1]

1. Hash

Hash是一个把任意长度的数据映射成固定长度数据的函数[2]。例如，对于数据完整性校验，最简单的方法是对整个数据做Hash运算得到固定长度的Hash值，然后把得到的Hash值公布在网上，这样用户下载到数据之后，对数据再次进行Hash运算，比较运算结果和网上公布的Hash值进行比较，如果两个Hash值相等，说明下载的数据没有损坏。可以这样做是因为输入数据的稍微改变就会引起Hash运算结果的面目全非，而且根据Hash值反推原始输入数据的特征是困难的。[3]

如果从一个稳定的服务器进行下载，采用单一Hash是可取的。但如果数据源不稳定，一旦数据损坏，就需要重新下载，这种下载的效率是很低的。

2. Hash List

在点对点网络中作数据传输的时候，会同时从多个机器上下载数据，而且很多机器可以认为是不稳定或者不可信的。为了校验数据的完整性，更好的办法是把大的文件分割成小的数据块（例如，把分割成2K为单位的数据块）。这样的好处是，如果小块数据在传输过程中损坏了，那么只要重新下载这一快数据就行了，不用重新下载整个文件。

怎么确定小的数据块没有损坏哪？只需要为每个数据块做Hash。BT下载的时候，在下载到真正数据之前，我们会先下载一个Hash列表。那么问题又来了，怎么确定这个Hash列表本事是正确的哪？答案是把每个小块数据的Hash值拼到一起，然后对这个长字符串在作一次Hash运算，这样就得到Hash列表的根Hash(Top Hash or Root Hash)。下载数据的时候，首先从可信的数据源得到正确的根Hash，就可以用它来校验Hash列表了，然后通过校验后的Hash列表校验数据块。

3. Merkle Tree

Merkle Tree可以看做Hash List的泛化（Hash List可以看作一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree）。

在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root[3]。

在p2p网络下载网络之前，先从可信的源获得文件的Merkle Tree树根。一旦获得了树根，就可以从其他从不可信的源获取Merkle tree。通过可信的树根来检查接受到的Merkle Tree。如果Merkle Tree是损坏的或者虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的Merkle Tree。

Merkle Tree和Hash List的主要区别是，可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了。而Hash list只有下载整个hash list才能验证。

Merkle Tree的特点

MT是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点； Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。 非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。[4][5]

通常，加密的hash方法像SHA-2和MD5用来做hash。但如果仅仅防止数据不是蓄意的损坏或篡改，可以改用一些安全性低但效率高的校验和算法，如CRC。

Second Preimage Attack: Merkle tree的树根并不表示树的深度，这可能会导致second-preimage attack，即攻击者创建一个具有相同Merkle树根的虚假文档。一个简单的解决方法在Certificate Transparency中定义：当计算叶节点的hash时，在hash数据前加0x00。当计算内部节点是，在前面加0x01。另外一些实现限制hash tree的根，通过在hash值前面加深度前缀。因此，前缀每一步会减少，只有当到达叶子时前缀依然为正，提取的hash链才被定义为有效。

Merkle Tree的操作

1. 创建Merckle Tree

加入最底层有9个数据块。

- step1：（红色线）对数据块做hash运算，Node0i = hash(Data0i), i=1,2,…,9

- step2: （橙色线）相邻两个hash块串联，然后做hash运算，Node1((i+1)/2) = hash(Node0i+Node0(i+1)), i=1,3,5,7;对于i=9, Node1((i+1)/2) = hash(Node0i)

- step3: （黄色线）重复step2

- step4：（绿色线）重复step2

- step5：（蓝色线）重复step2，生成Merkle Tree Root

易得，创建Merkle Tree是O(n)复杂度(这里指O(n)次hash运算)，n是数据块的大小。得到Merkle Tree的树高是log(n)+1。

2. 检索数据块

为了更好理解，我们假设有A和B两台机器，A需要与B相同目录下有8个文件，文件分别是f1 f2 f3 ....f8。这个时候我们就可以通过Merkle Tree来进行快速比较。假设我们在文件创建的时候每个机器都构建了一个Merkle Tree。具体如下图:

从上图可得知，叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8)，也就是其子节点node7 node8的值得HASH。就是这样表示一个层级运算关系。root节点的value其实是所有叶子节点的value的唯一特征。

假如A上的文件5与B上的不一样。我们怎么通过两个机器的merkle treee信息找到不相同的文件? 这个比较检索过程如下:

- Step1. 首先比较v0是否相同,如果不同，检索其孩子node1和node2.

- Step2. v1 相同，v2不同。检索node2的孩子node5 node6;

- Step3. v5不同，v6相同，检索比较node5的孩子node 11 和node 12

- Step4. v11不同，v12相同。node 11为叶子节点，获取其目录信息。

- Step5. 检索比较完毕。

以上过程的理论复杂度是Log(N)。过程描述图如下:

从上图可以得知真个过程可以很快的找到对应的不相同的文件。

3. 更新，插入和删除

虽然网上有很多关于Merkle Tree的资料，但大部分没有涉及Merkle Tree的更新、插入和删除操作，讨论Merkle Tree的检索和遍历的比较多。我也是非常困惑，一种树结构的操作肯定不仅包括查找，也包括更新、插入和删除的啊。后来查到stackexchange上的一个问题，才稍微有点明白，原文见[6]。

对于Merkle Tree数据块的更新操作其实是很简单的，更新完数据块，然后接着更新其到树根路径上的Hash值就可以了，这样不会改变Merkle Tree的结构。但是，插入和删除操作肯定会改变Merkle Tree的结构，如下图，一种插入操作是这样的：

插入数据块0后(考虑数据块的位置)，Merkle Tree的结构是这样的：

而[6]中的同学在考虑一种插入的算法，满足下面条件：

• re-hashing操作的次数控制在log(n)以内
• • 数据块的校验在log(n)+1以内
• 除非原始树的n是偶数，插入数据后的树没有孤儿，并且如果有孤儿，那么孤儿是最后一个数据块
• 数据块的顺序保持一致
• 插入后的Merkle Tree保持平衡 　　然后上面的插入结果就会变成这样：

根据[6]中回答者所说，Merkle Tree的插入和删除操作其实是一个工程上的问题，不同问题会有不同的插入方法。如果要确保树是平衡的或者是树高是log(n)的，可以用任何的标准的平衡二叉树的模式，如AVL树，红黑树，伸展树，2-3树等。这些平衡二叉树的更新模式可以在O(lgn)时间内完成插入操作，并且能保证树高是O(lgn)的。那么很容易可以看出更新所有的Merkle Hash可以在O((lgn)2)时间内完成（对于每个节点如要更新从它到树根O(lgn)个节点，而为了满足树高的要求需要更新O(lgn)个节点）。如果仔细分析的话，更新所有的hash实际上可以在O(lgn)时间内完成，因为要改变的所有节点都是相关联的，即他们要不是都在从某个叶节点到树根的一条路径上，或者这种情况相近。

[6]的回答者说实际上Merkle Tree的结构(是否平衡，树高限制多少)在大多数应用中并不重要，而且保持数据块的顺序也在大多数应用中也不需要。因此，可以根据具体应用的情况，设计自己的插入和删除操作。一个通用的Merkle Tree插入删除操作是没有意义的。

Merkle Tree的应用

1. 数字签名

最初Merkle Tree目的是高效的处理Lamport one-time signatures。 每一个Lamport key只能被用来签名一个消息，但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架，即Merkle Signature Scheme。

2. P2P网络

在P2P网络中，Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换，甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输，一来可以加快数据下载速度，二来减轻下载服务器的负担。BT即BitTorrent，是一种中心索引式的P2P文件分分析通信协议[7]。

要进下载必须从中心索引服务器获取一个扩展名为torrent的索引文件（即大家所说的种子），torrent文件包含了要共享文件的信息，包括文件名，大小，文件的Hash信息和一个指向Tracker的URL[8]。Torrent文件中的Hash信息是每一块要下载的文件内容的加密摘要，这些摘要也可运行在下载的时候进行验证。大的torrent文件是Web服务器的瓶颈，而且也不能直接被包含在RSS或gossiped around(用流言传播协议进行传播)。一个相关的问题是大数据块的使用，因为为了保持torrent文件的非常小，那么数据块Hash的数量也得很小，这就意味着每个数据块相对较大。大数据块影响节点之间进行交易的效率，因为只有当大数据块全部下载下来并校验通过后，才能与其他节点进行交易。

就解决上面两个问题是用一个简单的Merkle Tree代替Hash List。设计一个层数足够多的满二叉树，叶节点是数据块的Hash，不足的叶节点用0来代替。上层的节点是其对应孩子节点串联的hash。Hash算法和普通torrent一样采用SHA1。其数据传输过程和第一节中描述的类似。

3. Trusted Computing

可信计算是可信计算组为分布式计算环境中参与节点的计算平台提供端点可信性而提出的。可信计算技术在计算平台的硬件层引入可信平台模块(Trusted Platform，TPM)，实际上为计算平台提供了基于硬件的可信根(Root of trust，RoT)。从可信根出发，使用信任链传递机制，可信计算技术可对本地平台的硬件及软件实施逐层的完整性度量，并将度量结果可靠地保存再TPM的平台配置寄存器(Platform configuration register，PCR)中，此后远程计算平台可通过远程验证机制(Remote Attestation)比对本地PCR中度量结果，从而验证本地计算平台的可信性。可信计算技术让分布式应用的参与节点摆脱了对中心服务器的依赖，而直接通过用户机器上的TPM芯片来建立信任，使得创建扩展性更好、可靠性更高、可用性更强的安全分布式应用成为可能[10]。可信计算技术的核心机制是远程验证(remote attestation),分布式应用的参与结点正是通过远程验证机制来建立互信,从而保障应用的安全。

文献[10]提出了一种基于Merkle Tree的远程验证机制，其核心是完整性度量值哈希树。

首先,RAMT 在内核中维护的不再是一张完整性度量值列表(ML),而是一棵完整性度量值哈希树(integrity measurement hash tree,简称IMHT).其中,IMHT的叶子结点存储的数据对象是待验证计算平台上被度量的各种程序的完整性哈希值,而其内部结点则依据Merkle 哈希树的构建规则由子结点的连接的哈希值动态生成。

其次,为了维护IMHT 叶子结点的完整性,RAMT 需要使用TPM 中的一段存储器来保存IMHT 可信根哈希的值。

再次,RAMT 的完整性验证过程基于认证路径(authentication path)实施.认证路径是指IMHT 上从待验证叶子结点到根哈希的路径。

4. IPFS

IPFS(InterPlanetary File System)是很多NB的互联网技术的综合体，如DHT( Distributed HashTable，分布式哈希表)，Git版本控制系统，Bittorrent等。它创建了一个P2P的集群，这个集群允许IPFS对象的交换。全部的IPFS对象形成了一个被称作Merkle DAG的加密认证数据结构。

IPFS对象是一个含有两个域的数据结构:

• Data – 非结构的二进制数据，大小小于256kB
• Links – 一个Link数据结构的数组。IPFS对象通过他们链接到其他对象

Link数据结构包含三个域：

• Name – Link的名字
• Hash – Link链接到对象的Hash
• Size – Link链接到对象的累积大小，包括它的Links

通过Name和Links，IPFS的集合组成了一个Merkle DAG（有向无环图）。

对于小文件（<256kB），是一个没有Links的IPFS对象。

对于大文件，被表示为一个文件块(<256kB)的集合。只有拥有最小的Data的对象来代表这个大文件。这个对象的Links的名字都为空字符串。

目录结构：目录是没有数据的IPFS对象，它的链接指向其包含的文件和目录。

IPFS可以表示Git使用的数据结构，Git commit object。Commit Object主要的特点是他有一个或多个名为’parent0’和‘parent1’等的链接（这些链接指向前一个版本），以及一个名为object的对象(在Git中成为tree)指向引用这个commit的文件系统结构。

5. BitCoin和Ethereum[12][13]

Merkle Proof最早的应用是Bitcoin，它是由中本聪在2009年描述并创建的。Bitcoin的Blockchain利用Merkle proofs来存储每个区块的交易。

而这样做的好处，也就是中本聪描述到的“简化支付验证”（Simplified Payment Verification，SPV）的概念:一个“轻客户端”（light client）可以仅下载链的区块头即每个区块中的80byte的数据块，仅包含五个元素，而不是下载每一笔交易以及每一个区块：

• 上一区块头的哈希值
• 时间戳
• 挖矿难度值
• 工作量证明随机数（nonce）
• 包含该区块交易的Merkle Tree的根哈希

如果客户端想要确认一个交易的状态，它只需简单的发起一个Merkle proof请求，这个请求显示出这个特定的交易在Merkle trees的一个之中，而且这个Merkle Tree的树根在主链的一个区块头中。

但是Bitcoin的轻客户端有它的局限。一个局限是，尽管它可以证明包含的交易，但是它不能进行涉及当前状态的证明（如数字资产的持有，名称注册，金融合约的状态等）。

Bitcoin如何查询你当前有多少币？一个比特币轻客户端，可以使用一种协议，它涉及查询多个节点，并相信其中至少会有一个节点会通知你，关于你的地址中任何特定的交易支出，而这可以让你实现更多的应用。但对于其他更为复杂的应用而言，这些远远是不够的。一笔交易影响的确切性质（precise nature），可以取决于此前的几笔交易，而这些交易本身则依赖于更为前面的交易，所以最终你可以验证整个链上的每一笔交易。为了解决这个问题，Ethereum的Merkle Tree的概念，会更进一步。

Ethereum的Merkle Proof

每个以太坊区块头不是包括一个Merkle树，而是为三种对象设计的三棵树：

• 交易Transaction
• 收据Receipts(本质上是显示每个交易影响的多块数据)
• 状态State

-

这使得一个非常先进的轻客户端协议成为了可能，它允许轻客户端轻松地进行并核实以下类型的查询答案：

• 这笔交易被包含在特定的区块中了么？
• 告诉我这个地址在过去30天中，发出X类型事件的所有实例（例如，一个众筹合约完成了它的目标）
• 目前我的账户余额是多少？
• 这个账户是否存在？
• 假如在这个合约中运行这笔交易，它的输出会是什么？

第一种是由交易树（transaction tree）来处理的；第三和第四种则是由状态树（state tree）负责处理，第二种则由收据树（receipt tree）处理。计算前四个查询任务是相当简单的。服务器简单地找到对象，获取Merkle分支，并通过分支来回复轻客户端。

第五种查询任务同样也是由状态树处理，但它的计算方式会比较复杂。这里，我们需要构建一个Merkle状态转变证明（Merkle state transition proof）。从本质上来讲，这样的证明也就是在说“如果你在根S的状态树上运行交易T，其结果状态树将是根为S'，log为L，输出为O” （“输出”作为存在于以太坊的一种概念，因为每一笔交易都是一个函数调用；它在理论上并不是必要的）。

为了推断这个证明，服务器在本地创建了一个假的区块，将状态设为 S，并在请求这笔交易时假装是一个轻客户端。也就是说，如果请求这笔交易的过程，需要客户端确定一个账户的余额，这个轻客户端(由服务器模拟的)会发出一个余额查询请求。如果需要轻客户端在特点某个合约的存储中查询特定的条目，这个轻客户端就会发出这样的请求。也就是说服务器(通过模拟一个轻客户端)正确回应所有自己的请求，但服务器也会跟踪它所有发回的数据。

然后，服务器从上述的这些请求中把数据合并并把数据以一个证明的方式发送给客户端。

然后，客户端会进行相同的步骤，但会将服务器提供的证明作为一个数据库来使用。如果客户端进行步骤的结果和服务器提供的是一样的话，客户端就接受这个证明。

MPT(Merkle Patricia Trees)

前面我们提到，最为简单的一种Merkle Tree大多数情况下都是一棵二叉树。然而，Ethereum所使用的Merkle Tree则更为复杂，我们称之为“梅克尔.帕特里夏树”（Merkle Patricia tree）。

对于验证属于list格式（本质上来讲，它就是一系列前后相连的数据块）的信息而言，二叉Merkle Tree是非常好的数据结构。对于交易树来说，它们也同样是不错的，因为一旦树已经建立，花多少时间来编辑这棵树并不重要，树一旦建立了，它就会永远存在并且不会改变。

但是，对于状态树，情况会更复杂些。以太坊中的状态树基本上包含了一个键值映射，其中的键是地址，而值包括账户的声明、余额、随机数nounce、代码以及每一个账户的存储（其中存储本身就是一颗树）。例如，摩登测试网络（the Morden testnet ）的创始状态如下所示：

然而，不同于交易历史记录，状态树需要经常地进行更新：账户余额和账户的随机数nonce经常会更变，更重要的是，新的账户会频繁地插入，存储的键（ key）也会经常被插入以及删除。我们需要这样的数据结构，它能在一次插入、更新、删除操作后快速计算到树根，而不需要重新计算整个树的Hash。这种数据结构同样得包括两个非常好的第二特征：

• 树的深度是有限制的，即使考虑攻击者会故意地制造一些交易，使得这颗树尽可能地深。不然，攻击者可以通过操纵树的深度，执行拒绝服务攻击（DOS attack），使得更新变得极其缓慢。
• 树的根只取决于数据，和其中的更新顺序无关。换个顺序进行更新，甚至重新从头计算树，并不会改变根。

MPT是最接近同时满足上面的性质的的数据结构。MPT的工作原理的最简单的解释是，值通过键来存储，键被编码到搜索树必须要经过的路径中。每个节点有16个孩子，因此路径又16进制的编码决定：例如，键‘dog’的16进制编码是6 4 6 15 6 7，所以从root开始到第六个分支，然后到第四个，再到第六个，再到第十五个，这样依次进行到达树的叶子。

在实践中，当树稀少时也会有一些额外的优化，我们会使过程更为有效，但这是基本的原则。

6. 其他应用

用到Merkle Tree的应用还有很多，比如Git，Amazon Dynamo，Apache Wave Protocol，Tahoe-LAFS backup system，Certificate Transparency framework，NoSQL systems like Apache Cassadra and Riak等

参考

[1] https://en.wikipedia.org/wiki/Merkle_tree

[2] https://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms

[3] http://www.jianshu.com/p/458e5890662f

[4] http://blog.csdn.net/xtu_xiaoxin/article/details/8148237

[5] http://blog.csdn.net/yuanrxdu/article/details/22474697?utm_source=tuicool&utm_medium=referral

[6] http://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates

[7] https://en.wikipedia.org/wiki/BitTorrent

[8] 梁成仁, 李健勇, 黄道颖, 等. 基于 Merkle 树的 BT 系统 torrent 文件优化策略[J]. 计算机工程, 2008, 34(3): 85-87.

[9] http://bittorrent.org/beps/bep_0030.html

[10] 徐梓耀, 贺也平, 邓灵莉. 一种保护隐私的高效远程验证机制[J]. Journal of Software, 2011, 22(2).

[11] http://whatdoesthequantsay.com/2015/09/13/ipfs-introduction-by-example/

[12] https://www.weusecoins.com/what-is-a-merkle-tree/

[13] http://www.8btc.com/merkling-in-ethereum

访问链接

《Merkle Tree学习》