区块链技术六大算法

拜占庭协定

拜占庭的故事大概是这么说的：拜占庭帝国拥有巨大的财富，周围10个邻邦垂诞已久，但拜占庭高墙耸立，固若金汤，没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败，同时也有可能自身被其他9个邻邦入侵。拜占庭帝国防御能力如此之强，至少要有十个邻邦中的一半以上同时进攻，才有可能攻破。然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛，那么入侵者可能都会被歼灭。于是每一方都小心行事，不敢轻易相信邻国。这就是拜占庭将军问题。 在这个分布式网络里：每个将军都有一份实时与其他将军同步的消息账本。账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致，可以知道消息不一致的是哪些将军。尽管有消息不一致的，只要超过半数同意进攻，少数服从多数，共识达成。 由此，在一个分布式的系统中，尽管有坏人，坏人可以做任意事情（不受protocol限制），比如不响应、发送错误信息、对不同节点发送不同决定、不同错误节点联合起来干坏事等等。但是，只要大多数人是好人，就完全有可能去中心化地实现共识。

本文阐述了拜占庭协议共识需要满足的条件、对拜占庭问题中的一些约束（如n>t3n>t3）做了证明，有助于读者理解这些约束条件的产生、随后提出了一个满足拜占庭共识达成条件的协议。分别由净化协议（PP）与拜占庭协议（BG）（中译非官方）组成。
值得注意的是，本文提出的这个协议严重依赖于网络整体拓扑，由于每条路线都被记录，可能会造成更大的通信开销。且由于依赖拓扑结构，网络动态变化时，该协议可能无法很好发挥作用。
对于动态的区块链网络，很明显该协议并不适用。不过可以有一些启发，比如是否可以加入Purify的过程？是否有其他文章类似采用了类似Purify过程。答案肯定是有的。

fault VS Byzantine fault

一般来说，fault就是指一个replica在运行中因为各种原因发生了错误，无法参与接下来的消息交换。fault之后这个replica就退出消息传递过程。byzantine fault是指这个发生了错误的replica不仅不为系统安全性做贡献，反而恶意传递假消息来试图掌控系统中最后达成一致的value。
能忍受byzantine fault的系统一定可以忍受普通的crash，反之不成立。

两种协议

十字军协议（The Crusade Agreement）

达成十字军共识的条件是：

• 如果transmitter是可靠的，那么所有可靠的processor都应该就transmitter发送的值达成一致
• 如果transmitter是不可靠的，那么所有知道transmitter不可靠的processor都应该对同一个值达成一致（只要求是同一个值，并不指定具体的值）

拜占庭协议（The Byzantine Agreement）

达成拜占庭共识的条件是：

• 无论transmitter是否可靠，所有可靠的processor都应该就同一个值达成一致
• 如果transmitter可靠，可靠的processor们应该对transmitter发出的值达成一致

假设

1. 所有processor组成一个k-顶点连通图（k-connected bidirectional network）；——意味着任意去掉k-1个processor，也能保持联通；也意味着两个顶点之间至少有k个定点不相交。
2. 每一个processor都知道整个网络的拓扑结构；
3. processor们传递消息是通过连接（而非广播）传播；通过Link能捕捉到包吗，应该是（和xh确认了，是可以捕捉到的
4. 每一个processor都可以确定传给自己消息的邻居的身份；
5. 每一条消息都包含着自己的确定的传递路径；
6. 一个可靠的processor只会在看到这条消息的既定的传输路径中，自己将要发送给的邻居在自己之后，才会中继这条消息；
7. 一个可靠的processor只会在看到这条消息的既定传输路径中，自己在自己收到包的邻居之后，才会中继这条消息；——也就是说，一个faulty processor如果想把自己的消息传给可靠的processor，一定要在后继者的身份之前加上自己的identity；尽管接下来可能有新的faulty processor抹去了前一个faulty processor的identity，这个新的faulty processor的identity将会在消息路径中；——即，一个经过了faulty的，现在在可靠的processor手中的消息，消息路径中至少包含一个faulty的identity；
8. 可靠的processor收到消息后，不篡改、不窃听地将消息中继出去；
9. 可靠的processor传递消息时间有上界；
10. 系统中faulty processor数目有上界。

可疑的processor（Suspicious processors）

Va=a1,a2,...,arVa=a1,a2,...,ar是某一个processor收到的所有的value。（这些value可能由于各种原因可能并不相等）。可疑的processor集合定义为UxUx，其中不包括transmitter，如果去掉了VaVa中经过了UxUx中的所有的processor的value，那么VV中所有的值都相同。

恶意节点的上限

Theorem 1：如果一个网络中的恶意节点不少于（大于等于）n3n3，那么十字军一致不可能满足。

Lemma 1：如果一个包含三个网络节点的网络中有一个节点是faulty节点，那么该网络中不可能达到十字军一致。
Lemma 1 Proof：如图所示，其中处理器X是诚实的，而发送器T以及处理器Y未知是否诚实。该假设一定成立，因为在此网络中只有一个faulty节点，这意味着一定有一个处理器节点是诚实的。假设有一个有效的公式算法，能够达成十字军一致，那么这个协议应该在任何情况下都能满足十字军一致。

现在，T和Y中间一定有一个是恶意的。对X来说，它所能看到的只有自己收到的消息[a:T,b:Y][a:T,b:Y]，如果这个恶意节点干坏事了，那么a≠ba≠b。
现在有两种情况：T是faulty或者Y是faulty。X清楚地知道某一个消息的传递路径，但是X无法通过路径来分辨究竟是T在发送消息的时候就作弊了，即a≠m′a≠m′ && b=m′b=m′还是Y中途修改了T原本的消息，即a=m′a=m′ && b≠m′b≠m′。因此X只能去猜谁是faulty。
从共识设计的角度而非实际情况的角度考虑：

• 如果X无条件选择T的值。因为如果T是可靠的，X必须接受T的值。
  • 如果T确实是可靠的，则Y不可靠。那么所有诚实的节点在transmitter诚实的时候都一致到transmitter的值√
  • 如果T不可靠，则Y可靠。那么X最终选择了aa。而可靠的Y运行同样的共识算法，无条件选择T的值，此时Y选择了bb，这违反了十字军一致的第二条。
  • 这样的策略不可行。
• 如果X无条件选择Y的值。
  • 如果Y确实可靠，则T不可靠。那么X发送给Y的aa将会被Y选择，Y发送给X的bb将会被X选择。这样，可靠的两个processor仍然选择了不同的值。这违反了十字军一致的第二条。
  • 如果Y不可靠，则T可靠。此时X选择了错误的bb而非T发送的aa，违反了十字军一致的第一条。
  • 这样的策略更不可行。
• 随机选择aa或bb。
  • 不用脑子就知道这个肯定不行。

归根究底，还是因为恶意节点给出的干扰信息超过了一定比例，导致诚实的节点无法根据网络中传递的信息来判断究竟哪个信息才是正确的信息。

现在使用Lemma1来证明Theorem1。
Theorem 1 proof：假设一个网络GG中包含有t个恶意节点，且t≥n/3t≥n/3。
我们证明了，如果存在一个有效的共识算法A使得网络GG中能够达成十字军共识，那么也就意味着一定存在一个算法B可以在Lemma1所述网络中达成十字军共识。因为Lemma1说明了算法B不可能存在，因此算法A不可能存在。
现在我们把GG中的节点分为三部分，每一部分⌈n/3⌉⌈n/3⌉。如果不为整，则可能会存在某个set少一两个。每一个set模拟lemma1中提到的T、X、Y。也就是说，由于t≥n/3t≥n/3，每一个lemma1中的processor模拟不到t个GG中的processor。
//剩下的证明有点奇怪...
如果模拟X的processors选择了X选择的内容，那么就等同于需要在Lemma1所述的情况下达成共识。这是不可能的。

Theorem 2：如果网络中的恶意节点不少于该网络连通性（network connectivity）的一半，则十字军共识不可能达成。
Theorem 2 Proof：假设某一个网络GG连通性为k，且t≥k/2t≥k/2。所有k个节点将网络分为三个部分，G1G1、G2G2、bottleneckbottleneck，其中bottleneckbottleneck是这k个瓶颈节点，在bottleneckbottleneck中有至少k/2k/2个恶意节点。如下图所示：

其中，G1G1与G2G2以及bottleneckbottleneck分别连通，而G1G1与G2G2之间只能通过bottleneckbottleneck连通，连通道路并不只有一条。这是可能的，因为假设GG是一个k-顶点连通图。
如果在G1G1中存在一个诚实的transmitter，它发送了值aa，G1G1中大部分可能选择aa，但是反观G2G2，它们至少会接收到k/2k/2个b≠ab≠a以及至多k/2k/2个aa，他们无法辨别出究竟哪个才是transmitter发出的那个值，不可能确定地选择transmitter给出的值。这违反了十字军一致的第一条。

注：ceil：⌈e⌉⌈e⌉，取不小于表达式e的最小整数。如e=0.25，则取1。

净化算法（The Purifying Algorithm）

输入：(t,a1,a2,...,ar,x)(t,a1,a2,...,ar,x)，其中tt时faulty的数目，a1,...,ara1,...,ar是某一个正确节点收到的所有消息，xx是这个节点。
算法过程：

如果 UxUx存在，则净化后的值pv=valuepv=value，valuevalue即为不经过UxUx的消息确定的值。由UxUx的定义，这个值是唯一的。
如果UxUx不存在，则净化后的值不存在，pv=∅pv=∅。

Theorem 3：假设GG是一个(2t+1)-顶点连通图网络，至多有t个恶意节点，如果一个诚实的transmitter将自己选择的值通过2t+1个不相交的路径传播出去，那么每一个诚实的processor节点都能收到transmitter的值。
Theorem 3 Proof：如果诚实的消息通过了2t+1个不相交的路径，也就是说t个恶意节点每个至多只能经过一条传输路径，这其中最坏的情况是，每一条传输路径中都只包含一个恶意节点，这样，有t条传输路径被恶意节点扰乱，可能产生错误的信息。但是仍然有t+1路径是诚实的，包含了transmitter原有的值。因此receiver可以辨别出哪个是诚实的transmitter发送的值，并同意这个值。
另外，由于每一个被恶意节点扰乱的路径都至少包含一个恶意节点的信息，因此可以通过UxUx找出所有未被恶意节点扰乱过的信息。

Remarks 1：如果transmitter是恶意的，那么仅凭净化算法不能使所有诚实的processor达成共识的。

恶意的transmitter

定义：如果一个processor无法找到可能可疑的t个processors集合UxUx，那么这个processor知道（explicit knows），transmitter是恶意的。

Lemma 2：如果恶意的processor最多只有t个，只有transmitter确实是faulty的时候，一个processor才会知道transmitter是faulty的。
Lemma 2 Proof：根据定义，只有一个processor找不到UxUx的时候，他才会知道transmitter是faulty的。但是我们已经知道，如果transmitter是诚实的，那么根据净化算法一定能够找出UxUx。

十字军算法 （CR Algorithm）

输入：boldCR(G,z,V,t)boldCR(G,z,V,t)，其中GG是网络拓扑图，VV是所有网络节点，zz是transmitter，tt是网络中存在的恶意节点的上限。
算法过程：

1. transmitter z通过2t+12t+1条不相交的路径向每一个receiver发送自己的消息。(偏个题，这个communication开销挺大哈？)
2. 每一个receiver u∈Vu∈V运行净化算法，得到自己接受的那个值auau
3. u把自己拿到的值通过2t+12t+1个不相交路径发送给V∖{u}V∖{u}
4. 假设MuMu是u在步骤2、3中收到的所有的消息值，∅∅代表在步骤3中miss掉的消息值。每一个receiver都能根据MuMu在V∖{z}V∖{z}中找到UxUx，以及那个自己接受的值。如果找不到这样的UxUx，那么transmitter是恶意的，大家都选择value：faultytransmitterfaultytransmitter。

Theorem 4：算法CRCR可以在一个恶意节点t≤n/3t≤n/3，且连通性c≥2t+1c≥2t+1的网络中达成十字军共识。
Theorem 4 Proof：假设两个诚实的processor xx和yy分别找到了可疑的processor集合UxUx以及UyUy，假设实际上TT是恶意节点的集合，则：|T|,|Ux|,|Uy|≤t|T|,|Ux|,|Uy|≤t，则一定存在一个节点不在所有的这三个集合中，假设该节点为ww。
由于ww不在TT中，那么ww实际上是一个诚实的节点。而且由于连通性至少为2t+12t+1，一定存在一条路不经过UxUx和TT，从ww到达xx。存在一条路不经过UyUy和TT，从ww到达yy。
这样xx接收到的a(w)=awa(w)=aw并且选择这个值，同样的，yy接收到的a(w)=awa(w)=aw并且选择这个值。因此xx与yy接受同一个值。（？为啥都会选择这个值？因为不在UxUx和UyUy中吗？
如果transmitter是可靠的，那么每一个可靠的processor都能接收到这个诚实的值，而不会得出结论“transmitter faulty”（根据Lemma 2），当然，他们同意接收器的值，因为z就是上述的w。

拜占庭算法（BG Algorithm）

输入：BGG,v,U,t,mBGG,v,U,t,m，其中GG是整个网络的拓扑图，UU是节点们的子集，vv是transmitter，tt是faulty的数量，mm是一个整型参数。
算法过程：

1. vv向UU中的所有节点发送消息，通过2t+12t+1条disjoint path
2. 每个节点都运行净化算法，净化收到的消息，假设净化后的值为auau，其中uu为这个节点
3. 如果m>0m>0，则继续运行下面的：
   (a. uu作为transmitter，运行BG(G,u,U∖u,t,m−1)BG(G,u,U∖u,t,m−1)，发出的消息是auau
   (b. 对任意UU中不包括uu的节点ww，使用aw(u)aw(u)表示他收到的上一步中uu发出的消息的值，ww将使用它们确定zz的值，zz是下一集合中大多数的值：z=majority(aw(u)|x∈U)z=majority(aw(u)|x∈U)

Lemma 3：GG为一个网络，UU是一个包含基数至少为2r+m2r+m、恶意节点至多rr个的GG的子集，假设vv是不在UU中的一个processor，那么算法boldBG(G,v,U,t,m)boldBG(G,v,U,t,m)关于UU满足拜占庭一致的第二条要求：transmitter reliable时。
Lemma 3 Proof：在transmitter诚实的情况下，对m进行归纳。

• m=0m=0时：根据定理3。一共至少1+2r+m=2r+11+2r+m=2r+1个节点，其中最多rr个恶意节点。当transmitter reliable的时候，通过2r+12r+1个不相交路径发送自己的值，诚实节点一定能一致到transmitter的值。
• 假如m−1≥0m−1≥0的时候成立。根据定理3，诚实的transmitter把自己的值经过2r+12r+1个不相交路径发送给所有UU中的节点，则每一个UU中的节点都能确认拿到这个正确的值。每一个receiver u都执行算法BG(G,u,U∖{u},t,m−1)BG(G,u,U∖{u},t,m−1)，由于UU包含至少2r+m2r+m个节点，那么U∖{u}U∖{u}包含2r+m−12r+m−1个节点。通过归纳，每一个UU中的诚实的节点都能确认收到同为UU中诚实节点发出的诚实的值，假设为aa。大多数receiver接收到2r+m2r+m个值，其中有一个值是本receiver自己发出的值。由于m>0m>0，且至多rr个恶意节点，则拿到的正确值aa一定占大多数。
  //诚实节点变多，为啥会不成立呢？

Theorem 5：GG为一个网络，UU是一个包含基数至少为3m3m的GG的子集，假设vv是不在UU中的一个processor，如果U∖{v}U∖{v}包含至多mm个faulty processors，那么算法boldBG(G,v,U,t,m)boldBG(G,v,U,t,m)关于UU满足拜占庭一致的两个条件。
Theorem 5 Proof：对m进行归纳。

• m=0m=0时：此时没有恶意节点在U∖{v}U∖{v}（接收者集合）中，根据定理3。
• 假如m−1≥0m−1≥0的时候成立。
  • 如果vv诚实，那么根据Lemma 3。
  • 如果vv不诚实，那么U∖{u}U∖{u}（其中uu是一个接收者）中包含至少3m−13m−1个processor，其中至多m−1m−1个恶意节点（？），少于1/31/3的总节点个数。如果uu诚实，那么所有的U∖{u}U∖{u}会一致到同一个值（3a，根据Lemma 3），如果uu不诚实，他们会一致到某一个值，于是，每一个可靠的processor在3b在同一个set上计算大多数值，最终得到同样的值。

Theorem 5 Proof原文：

Corollary 1（推论）：如果一个有n个节点的网络GG中恶意节点t<n/3t<n/3且连通性c≥2t+1c≥2t+1，那么算法BGBG满足拜占庭共识的要求。

参考文献

非对称加密技术

在上述拜占庭协定中，如果10个将军中的几个同时发起消息，势必会造成系统的混乱，造成各说各的攻击时间方案，行动难以一致。谁都可以发起进攻的信息，但由谁来发出呢？其实这只要加入一个成本就可以了，即：一段时间内只有一个节点可以传播信息。当某个节点发出统一进攻的消息后，各个节点收到发起者的消息必须签名盖章，确认各自的身份。 在如今看来，非对称加密技术完全可以解决这个签名问题。非对称加密算法的加密和解密使用不同的两个密钥，这两个密钥就是我们经常听到的“公钥”和“私钥”。公钥和私钥一般成对出现，如果消息使用公钥加密，那么需要该公钥对应的私钥才能解密；同样，如果消息使用私钥加密，那么需要该私钥对应的公钥才能解密。

容错问题

我们假设在此网络中，消息可能会丢失、损坏、延迟、重复发送，并且接受的顺序与发送的顺序不一致。此外，节点的行为可以是任意的：可以随时加入、退出网络，可以丢弃消息、伪造消息、停止工作等，还可能发生各种人为或非人为的故障。我们的算法对由共识节点组成的共识系统，提供的容错能力，这种容错能力同时包含安全性和可用性，并适用于任何网络环境。

Paxos 算法（一致性算法）

Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模型的一致性算法。

共识机制

区块链共识算法主要是工作量证明和权益证明。拿比特币来说，其实从技术角度来看可以把PoW看做重复使用的Hashcash，生成工作量证明在概率上来说是一个随机的过程。开采新的机密货币，生成区块时，必须得到所有参与者的同意，那矿工必须得到区块中所有数据的PoW工作证明。与此同时矿工还要时时观察调整这项工作的难度，因为对网络要求是平均每10分钟生成一个区块。

分布式存储

分布式存储是一种数据存储技术，通过网络使用每台机器上的磁盘空间，并将这些分散的存储资源构成一个虚拟的存储设备，数据分散的存储在网络中的各个角落。所以，分布式存储技术并不是每台电脑都存放完整的数据，而是把数据切割后存放在不同的电脑里。就像存放100个鸡蛋，不是放在同一个篮子里，而是分开放在不同的地方，加起来的总和是100个。

最后

以上就是迷路大船为你收集整理的区块链技术六大算法的全部内容，希望文章能够帮你解决区块链技术六大算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。