ELASTICO-A Secure Sharding Protocol For Open Blockchains

INTRO

在中本聪共识中，通过POW机制来公平的选举leader，不仅非常消耗power，并且拓展性也不好。现在比特币中是7 TPS，和其他的支付系统相比效率相差甚远。

当前的许多拜占庭共识协议，并不支持在一个开放的环境中使用，比如加密货币，主要有两方面的原因：

1. 许多的算法都加上参与共识的节点都已经建立了身份认证，但是这个在一个开放系统中，比如比特币中是不存在的。所以比特币使用pow来竞争出块权。
2. 拜占庭共识，比如PBFT需要二次方规模的消息传输规模，在有限的网络带宽下，限制了拓展性。因此最多支持几百个节点。

我们希望能够有随着节点规模增加，吞吐量线性增长的区块链协议

本文提出了 ELASTICO 分片协议，在一个有拜占庭节点的非许可链上进行拓展。将POW和拜占庭共识进行一个结合。
key idea： 将整个网络划分成更小的委员会，每个委员会处理不相交的交易集合。
我们要保证每个委员会的大小合理，以能够运行拜占庭共识协议。各个委员会并行共识多个交易集合。

本文是第一篇在非许可链上进行拜占庭容错，并执行分片的论文。

• 能容忍拜占庭节点的比例 f = 1/4
• 拓展能力和计算能力几乎程线性比例。委员会的数量和计算能力几乎成线性的拓展。
• 消息的复杂度是 $O(n{c}^3)$

PROBLEM & CHALLENGES

本文的算法并不能直接保证双花问题，而要对他进行额外的检查。

应对女巫攻击

在非许可链中，每个恶意节点都可以虚拟出许多节点，并进行女巫攻击。因此要限制能够建立合法身份的节点数。
在中本聪共识中，为了应对女巫攻击，采用pow来获取记账权。

均匀分配委员会

要保证委员会是均匀分配的，不会使得过多的恶意节点备份到同一个委员会中从而支配该委员会的共识结果。
我们要有极高的概率保证(当然不是100%)在每个委员会中，诚实节点占大多数。

容忍每个成员认为的委员会成员不一致

在每个委员会成员严重，委员会的成员可能都不一致，也就是view不同。这可能是因为网络延迟或者拜占庭节点作恶导致的。但是我们必须要容忍这种情况。

solution overview

将整个网络划分成许多的委员会，每个委员会并行共识一个交易的集合。
final committee 将所有交易的集合进行聚合，并广播给所有的节点。final committe进行聚合时，只需要将各个交易集合的摘要进行聚合就可以了。
最后 final commitee 会生成一组随机字符串，用于下一个epoch的生成身份部分。
final committee 可以有指定 id的普通committee来担任。

流程

每个epoch都需要进行下面的五步：

1. 建立合法身份和形成委员会。

   身份证明由 公钥、IP地址、POW的解构成。如果要建立身份，就需要提供pow的解，因此就会将网络中拥有身份的恶意节点数限制比例在f。
   为了防止每一轮中恶意节点提前解出POW, 我们在pow中设立了随机数 epochRandomness。并且要求在上一轮结束的时候这个随机数才会被公布出来。
   解POW问题就是解下面的问题：

将结果O取后 s 位得到的值 id，就表明了此节点被分配到那个åcommittee中了。

既然这个分配过程是随机的，那么该如何保证分到每committee中的作恶节点不超过 1/3呢？

我们假设 n’个 节点获得了身份，其中诚实节点比例小于 2/3的概率为：

给定一个安全性参数 $\lambda$ , 我们可以计算一个 $n_0$ , $Pr[X\le 2n^{\prime }/3]\le 2^{-\lambda },\forall n^{\prime }\ge n_0$

2. 得知委员会中其他成员。

   如果一个节点获得了合法身份，也知道他在那个委员会中了，该如何得知委员会中其他成员呢？
   最朴素的方法就是将自己的身份和委员会信息进行广播。但是这样消息的复杂度又达到了 $O(n^2)$ .
   我们首先建立一个最初的委员会作为目录。
   在步骤1中，如果一个节点取得了身份，但是目前网络中获取身份的节点还不足 c个，就将自己的身份广播，并加入目录。
   当有目录已经建成了，新的建立身份的节点就将自己的身份发送给目录。
   由于每个节点都会将自己最先看到的c个节点当场目录，因此每个节点收到的委员会成员可能会有差异。
   但是，我们可以证明在同一个委员会中：

   1. 所有的诚实节点都是互相可见的
   2. 委员会中总的节点数不会超过 3/2c，存在差异的成员不会超过 c/2 个

如果一个目录节点，即将知道一个委员会的c个成员时，这时网络中的算力至多产生 c/2 个恶意节点身份。目录节点将这 c/2个恶意节点的身份分发给这个委员会的成员，造成每个委员会成员所取得的成员不一致。

但是这时，整个普通委员会中的作恶节点数量依旧不会超过 1/3，可以运行

这种方式通信复杂度只有 $O(n^2)$

3. 委员会内部进行共识

在委员会内部进行共识，可以运行普通的BFT协议。将少有 $c/2+1$ 个节点签名的分片结果提交给 final committee
这保证了至少有一个诚实节点承认了交易集合。
提交给final comittee 的内容可能只是交易集合的 默克尔根

4. final committee 广播

final committee中的节点将所有committee的结果聚合一个最终的结果，并进行共识。接着将共识的结果广播给所有的节点。

final committee 聚合和共识的内容，可能只是一个委员会共识结果的摘要，这样就将共识和数据传输过程分离。

这里的f=1/4是为了保证每个committee的规模不太大，理论上f只要小于 1/3就能满足PBFT的运行条件。但是这样就会导致每个committee的规模太大，丧失并行性。

5. final committee 计算一组随机字符串

   第一阶段： final committee的各个节点生成一组随机字符串，并将 哈希发送到comittee中进行共识，从而 committee 对一组随机字符串的一组hash $\mathbb{S}$达成共识，并随着上一阶段进行广播。
   第二阶段：每个final committee 中的成员将自己的随机字符串进行广播。

每个节点收到至多 3c/2 个随机字符串，至少 2c/3 个随机字符串。节点会自动忽略和$\mathbb{S}$ 中不相符的随机字符串。

因为每个节点收到的一组字符串都不相同，每个节点都取其中的 c/2+1 个随机字符串进行或运算，作为自己计算 pow的nonce。 c/2+1 就可以保证，至少一个随机字符串来自诚实节点，这就可以保证 nonce的随机性。

如何避免双花

因为每个交易都有 input 和 output，只要保证相同 input的交易在一个分片中达成共识，就可以对双花进行检查。

因此可以让每个 committee 专门负责一部分范围的 input。

因为要对交易进行检查，每个节点需要维护一个 UTXO的数据库，因此需要将其他节点的共识结果下载下来，更新本地的UTXO 数据库。

如果不需要其他节点的数据，则不需要将本地共识的数据进行广播，在这种应用中 ELASTICO 会更有优势。