zilliqa_network

zilliqa

Zilliqa网络分片篇翻译

英文版本

区块

ZILLIQA协议介绍两种类型的区块（所以存在两条链）：交易区块(TX-Block)和目录服务区块（DS-Block）。TX-Block记录用户的交易，DS-Block为参与共识协议的矿工的元数据。TX-Block存储被DS-Block中的节点同意的交易，每个DS-Block与多个TX-Blocks相关。

…

网络层

ZILLIQA被设计成是交易率按比例决定。主要的想法是，分片。即，将挖矿网络分成小分片，每个小分片处理交易是并行的。在本节中，我们将介绍网络和交易分片。

网络分片

网络分片。将挖矿网络分成小分片是一个两个的过程，首先，一组专用的称为目录服务委员会（或DS委员会）的节点被选举出来，然后他们将将网络和节点分到他们的分片中。在下面，将具体介绍细节。

  • 目录服务委员会（Directory Service Committee）：为了促进网络的切分，我们首先会选举出一组节点，成为目录服务(DS)节点。DS节点形成一个DS委员会。DS节点的选举是基于proof-of-work1算法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //Algorithm 1: PoW1 for DS committee election.
    Input: i: Current DS-epoch, DSi−1: Prev. DS committee
    composition.
    Output: header: DS-Block header.
     On each competing node:
    // get epoch randomness from the DS blockchain
    // DBi−1: Most recent DS-Block before start of i-th epoch
     r1 ← GetEpochRand(DBi−1)
    // get epoch randomness from the transaction blockchain
    // TBj : Most recent TX-Block before start of i-th epoch
     r2 ← GetEpochRand(TBj )
    // pk: node’s public key, IP = node’s IP address
     nonce, mixHash ← Ethash-PoW(pk, IP, r1, r2)
     header ← BuildHeader(nonce, mixHash, pk)
    // header includes pk and nonce among other fields
    // IP, header is multicast to members in the DS committee
     MulticastToDSi−1(IP, header)
     return header

    比其他节点更早成功产生一个有效的随机数的节点，将为新块提供区块头。回想一下DS-Block头和签名部分，当一个节点解决了POW1，它便可以生产仅仅1个区块头，区块头随后会被多点广播给DS委员会的所有节点，DS委员会将对产生的区块头进行共识后生成签名部分。2f个DS节点签名了区块头，这个区块便被确认添加到DS区块链中。

    在成功引导阶段后，在任何时候，规定DS节点的组成为一个预定义的窗口大小n0。在最近n0节点中并成功挖掘DS-Block的节点将加入DS委员会。

    连续挖到两个DS-Block之间的平均时间称为DS-epoch。DS-eposh的值的设置是减小两个竞争块几率的一种方法。在DS-epoch的开始，一个新的DS节点加入DS委员然后DS委员会中最老的成员会被挤出(原文为is churned out..不知道该怎么翻译比较好)。这固定了在DS-eposh期间DS委员会的大小始终是n0。DS委员中最新的成员将成为leader, 并领导该时期的共识协议。 这进一步导致了DS委员会成员的严格排序。

    可以看到的是，如果DS委员会的规模n0足够大（比如说800），那么在n0个委员会成员中极有可能最多有1/3是拜占庭。

  • 冲突解决：我们的共识协议不允许在DS区块链中分叉。 当多个节点大致同时解决难题时，可能会出现分叉。 为了解决冲突，每个DS节点从接收到的头中检索nonce字段，并按递增顺序对它们进行排序。 让我们假设第i个DS节点的最大随机数是max(nⁱ)。

    DS委员会的leader然后提出自己的header（对应于他所见过的最大随机数），并运行一致的协议来就DS- Block header达成一致。 只有当相应的随机数大于或等于max(nⁱ)时，第i个DS节点才同意接受建议的header（没理解上）。 一旦达成共识，DS-Block的签名部分就建立起来了，然后成为领导者

  • 分片生成：一旦选出DS委员会，网络的实际分片就可以开始。 为了使节点参与下面的共识协议，它必须执行工作证明（PoW2）。 分片协议在每个DS时期开始时重复。 算法2给出了PoW2的算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Algorithm 2: PoW2 for shard membership.
    Input: i: Current DS-epoch, DSi: Current DS committee
    composition.
    Output: nonce, mixHash: outputs of Ethash-PoW
     On each competing node:
    // get epoch randomness from the DS blockchain
    // DBi−1: Most recent DS-Block before start of i-th epoch
     r ← GetEpochRand(DBi)
    // pk: node’s public key, IP = node’s IP address
     nonce, mixHash ← Ethash-PoW(pk, IP, r)
    // IP, header is multicast to members in the DS committee
     MulticastToDSi(nonce, mixHash, pk, IP)
     return nonce, mixHash

    然后将计算出的PoW2的有效随机数（和混合散列）多播到DS委员会。 DS节点将共同接受足够的PoW解决方案，以分解为L个共识委员会或分片，每个都具有n0个节点以达成共识。一旦DS委员会负责人收到足够数量的PoW2解决方案，他就启动一个协商一致的协议，以就该组有效的PoW2解决方案达成一致。在共识协议结束时，leader生成由DS节点签名的EC-Schnorr多重签名。为了进一步进行下去，超过2/3的DS节点必须同意一组可接受的PoW2解决方案。
    Sharding利用确定性函数将节点分配给分片。让我们假设我们需要每个都有n0个节点的碎片。随机数值按升序排序，第一个有n0个节点的节点们被分配给第一个分片，下一个n0分配到下一个分片，依此类推。在碎片中提出最大随机数的矿工的身份被宣布为leader。这进一步诱导了对分片成员的严格排序。也可以表明，如果n0足够大（比如800以上），那么在每个碎片内至多有1/3个是具有高概率的拜占庭

公共信道

DS节点在公共信道上发布某些信息，包括DS节点的身份和连接信息，每个分片中的节点列表以及交易的分片逻辑（在第V-D节中解释）。 公共频道不可信，并假定所有节点均可访问。 在我们的实现中，我们的广播原语实现了这样的公共频道。 我们区块链的用户想要提交交易以进行接受，然后可以检查分片信息以获取负责处理其交易的碎片。 在公共频道上发布的信息预计将由任何节点或用户可验证的DS节点的2/3以上进行签名。

新节点加入ZILLIQA

对于新节点加入网络，它可以尝试解决PoW1成为DS节点或PoW2成为分片的成员。 为此，它需要从区块链获得关于PoW1或PoW2所需的随机性的信息。 一旦获得了随机性信息，新节点就可以将其解决方案提交给DS委员会。

交易分片和过程

如以上所述，网络分片创建了每个能够并行处理交易的分片。 在本节中，我们将介绍特定交易如何分配给分片以及如何处理交易。 为此，我们使用以下抽象：A -ⁿ->B来指示从发件人账户A到收件人账户B的n个ZIL的交易

  • 交易分配：任何交易都表示A -ⁿ->B被单个分片处理。 假设有L个分片，编号为0到L-1，事务被分配到由发送者地址的(log₂L + 1)右边的位（bit）标识的碎片。即，实例中A的账户地址。因为账户地址是一个160位(bit)的整型数据，所以L的范围应该为log₂L + 1 ≤ 160。但实际上，它会小于100。

    一旦识别了分配的分片，事务就会被多播到分片中的一些节点，节点然后再进一步广播它。 一旦交易到达指定分片的领导者，它将把交易包含在TX-Block中并运行共识协议。

    双花（或重播攻击）可以使用每笔交易中的随机数轻松检测。 回想一下，每笔交易都有一个随机数，用于统计发件人帐户发送的交易数量。 一旦交易进入交易区块链，nonce在账户状态中更新，从而处于全局状态。 当前值小于或等于全局状态当前值的交易被矿工拒绝。 根据发件人的帐户地址本地分片交易允许分片成员检测双倍支出，因为发件人的每个交易都将在同一分片中处理。

  • 交易处理：委员会内的所有节点都可以提出交易。这些交易被发送给领导者以运行一组协议，其中一组交易形成下一个TX块。由每个分片建议的块称为微块（由类型标记0x00标识）。一个微块包含EC-Schnorr多重签名，由分片中的2/3个节点组成。leader还建立一个标识签名者公钥的位图B。如果分片的第i个成员签署了TX-Block头部，则B [i] = 1。当一个分片在TX块上达成共识时，其领导者将块头和签名多播给一些DS节点。 DS节点然后在DS委员会内广播它，以便该块到达其领导者。块的数据部分可以异步发送到节点。 DS委员会然后汇集从碎片发送的所有块，并且在它们之间运行另一轮共识协议以达成最终块。最后的块是由类型标记0x01标识的TX块。最后一个块包含来自DS委员会的超过2/3个n0节点的EC-Schnorr多重签名。 DS委员会的leader还构建了一个位图B，用于标识签名者的公钥。如果DS委员会的第i个成员签署了TX-Block标题，则B [i] = 1。最后的块头和签名，然后被组播到每个分片中的一些节点。实际的TX块数据不是由DS节点发送的。

    在每个分片中，采取以下步骤来处理最终的块:

    1. 分片中的每个节点使用DS节点的公钥验证EC-Schnorr多重签名。 如果签名对由位图表示的超过2/3个n0公钥有效，则节点执行下一个检查。
    2. 对于包含在最终块头中的每个交易hash，节点检查其相应的交易内容是否可用。 如果相应的交易由节点所属的分片提出，则将交易数据的散列与包含在最后块header中的散列进行比较。 如果交易是由另一个分片提出的，则交易数据跨分片异步共享
    3. 一旦交易数据可用，最终块的data部分被重构并且TX块被附加到本地交易区块链。 账户状态和全局状态相应地被更新。
    4. 如果交易内容不可用，则节点在其本地账户视图中临时使该交易的发送账户失效，以便该账户的任何其他未决交易被拒绝，直到本地交易内容可以与全局状态同步。 这些被拒绝的事务将不得不由发送节点重试

共识层

如以上提到的，每个分片和DS委员会需要分别在微块和终块上跑一个共识协议。在这一块，我们将展示在每一个分片和DS委员会中定义的共识协议的共识层。在讨论中，我们将分片和DS委员会代指为共识组。

实用拜占庭容错

ZILLIQA共识协议的核心依赖于实用拜占庭容错(PBFT)协议。然而我们通过在PBFT中使用EC-Schnorr多签名来提升效率。EC-Schnorr多重签名的使用将正常情况下的通信延迟从O(n*n)降低为O(n)，并将签名大小从O(n)减小到O(1)，其中n是共识组的大小。 在这个部分，我们提供PBFT的概述。

在PBFT中，共识组内的所有节点都按顺序排列，它有一个主节点（或领导者），其他节点称为备份节点。 每轮PBFT都有三个阶段，如下所述：

  • 预准备阶段: 在这个阶段，领导者宣布该小组将应该达成一致共识的下一个记录（在我们的案例中是TX-Block）
  • 准备阶段：在接收到预先准备消息后，每个节点验证其正确性并将准备消息多播给所有其他节点
  • 提交阶段：在收到超过2/3*n准备消息时，节点向组播组发送提交消息。最后，节点等待超过2/3*n的提交消息，以确保有足够数量的节点做出相同的决定。 因此，所有诚实的节点都接受相同的有效记录。

PBFT依靠正确的领导者开始每个阶段，并在足够多节点存在时继续进行。 如果领导是拜占庭，它可能会拖延整个共识协议。 为了应对这一挑战，PBFT提供了视图更改协议来使用另一个取代拜占庭领袖。 如果节点在有限的时间内没有看到任何进展，他们可以独立宣布改变领导者的愿望。 如果超过2/3*n个节点的法定人数决定领导者有问题，那么在已知计划中的下一个领导者就会接管。

由于在准备/提交阶段每个节点的多播，正常情况下PBFT的通信复杂度为O（n*n）

提高效率

经典的PBFT使用消息认证码（MAC）进行节点之间的认证通信。 由于MAC需要在每两个节点之间共享密钥，所以一个共识组中的节点可以在同一个记录上达成一致，其中每个节点的通信复杂度为O（n*n）。 由于二次复杂性，当委员会有20多个节点时，PBFT变得不切实际。

为了提高效率，我们使用来源于ByzCoin的想法：

  • 我们用数字签名替换MAC来有效地减少O（n）的通信开销。
  • 与此同时，为了让其他节点能够验证协议，一种典型的方法是从诚实的多数收集签名并将它们附加到协议中，从而导致协商规模与协商组的大小成线性关系。 为了改善这一点，我们使用EC-Schnorr多重签名来将几个签名聚合成O（1） - 大小多重签名

然而，我们不能直接在PBFT设置中使用经典的EC-Schnorr多重签名方案。 这是因为在古典设置中，所有签名者都同意签署给定的消息，并且签名只有在所有签名者都签名后才有效。 在PBFT设置中，我们只需要在共识组中超过2/3*n个节点签署消息。 所需的主要修改之一是为参与签名过程的签名者维护位图B. 如果第i个节点参与该过程，则B [i] = 1，否则为0。位图由领导者构建。 位图可以被任何验证者用来验证签名。 最终的协议留在附录B中。

Zilliqa共识

在ZILLIQA中，我们使用PBFT作为基础共识协议，并采用两轮EC-Schnorr多重签名来替换PBFT中的准备阶段和提交阶段。 下面将解释对PBFT阶段的不同修改。

  • 预准备阶段: 与标准PBFT中一样，领导者将TX-Block或声明（由领导者签名）分发给共识组中的所有节点。
  • 准备阶段：所有诚实的节点检查TX块的有效性，并且领导者收集来自超过2/3*n个节点的响应。 这保证领导者提出的陈述是安全的并且与以前的所有历史一致。 签名是使用EC-Schnorr多重签名生成的。 领导者还构建签署TX块的节点的位图
  • 提交阶段：为了确保超过2/3*n的节点知道超过2/3*n节点验证了TX-Block的事实。我们进行第二轮EC-Schnorr多重签名。 正在签署的声明是上一轮生成的多重签名。

在三个阶段结束时，就领导者提出的TX-Block将达成共识。

领导者改变

在我们的共识协议中，如果领导者是诚实的，它可以不断的推动共识小组中的节点就新的交易达成协议。 但是，如果领导是拜占庭，它可以有意地延迟或丢弃来自诚实节点的消息，并减慢协议。 为了惩罚这些恶意领导者，我们的协议会定期更改每个分片的领导和DS委员会。 这可以防止拜占庭领袖在无限期的时间内拖延共识协议。 由于所有节点都是有序的，下一个领导者将以循环方式选择。

事实上，每一个微块后分片的领导者都会改变，并且在每个最后一个区块之后DS委员会的领导者也会更改。 让我们假设共识组的大小为n，那么在一个DS-epoch时期内，我们允许的最终块的最大值为n，每个最终块最多在1个分片聚合1个微块。