区块链论文

这是2018年的论文，发现已经有介绍这篇论文的中文博客，本文跟它们不同地方在于，希望站在高层视角，以问题为导向来分析这篇论文。
这篇论文的作者和Byzcoin来自同一个人，而且前者是后者的拓展，因此，为了更好地理解本文，建议先看Byzcoin，可参考下面链接文章：

https://zhuanlan.zhihu.com/p/166154594

本文主要内容来自论文：

Kokoris-Kogias, Eleftherios, et al. "Omniledger: A secure, scale-out, decentralized ledger via sharding."2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018.
发表在顶会2018 IEEE Symposium on Security and Privacy

正文：

前面本人分析过另外两篇关于区块链分片的论文，所以具体为什么要区块链分片，这里略过。可参考本人写的下面两篇文章。需要注意的是，这篇文章是基于processing的分片，不是基于状态的分片，以此所有的矿工需要保存所有的状态数据，或者说在矿工在不同的时期被随机分配到其它片之后，需要下载新的所在片的状态数据。
Tech之直觉：区块链相关论文研读7：通过分片（Sharding）扩展区块链

https://zhuanlan.zhihu.com/p/89933683

https://zhuanlan.zhihu.com/p/87307292

在这里插入图片描述

先看总体的架构，下面是naive version，然后，论文基于这个版本所存在的问题来改进。

上面图片看起来分为三个层，注意的是这三个层出现的时间呈先后关系。意思是，先生成一个随机数 rnd_e ,那些validators（认证者）再根据这个随机数决定自己在上图第三层中的哪一个片中。每一个片都是一个Byzcoin。本人专门写了一篇文章介绍了Byzcoin，读者可以上面的第一个链接进入。
上面的版本存在几个很大的问题需要解决，分别是：

如何生成无偏差的rnd_e？不能使用可信的第三方，我们要做到在不相信任何一方的情况下生成。
认证者们如何只根据一个随机数rnd_e就能够知道自己属于哪一个片呢？
如何才能成为认证者？我们需要避免女巫攻击，特别是使用PBFT的情况下。
如果一个交易是跨片的，如何实现不同片之间的信息交互？

下面一一解释如何解答上面这些问题。

论文使用分布式的无偏差随机数生成方案RandHound，在使用它的时候，存在一个问题，那么就是RandHound方案需要一个节点当leader这个角色，但是如何选择leader呢？选择leader的时候要无偏差，应避免leader是敌手。原本需要RandHound生成一个无偏差的随机数，但是，现在为了设置和初始化RandHound，需要一个无偏差的随机数。这是一个鸡蛋和鸡谁先出现的问题。因此，文章使用了基于VRF的leader选举算法。具体不深入，我们暂时只需知道rnd_e被在无需信任任何一方的情况下无偏差地生成了。
对于第二个问题：如果每一个认证者都知道总共有n个认证者，且他们都收到了随机数，把这个随机数作为seed，使用下面的以python代码为例子的算法就能得到一个随机全排列，每一个数对应一个认证者的id。如果认证者都知道有m个片，那么根据n/m，他们就知道自己属于哪一个片了。

np.random.seed(seed)
np.random.permutation(10)
output [0 1 8 5 3 4 7 9 6 2]

不是所有的计算机节点都可以成为认证者的，在加入之前需要获得资格。为了避免女巫攻击，可以使用WoP或者SoP的共识算法来做。在每一个时区比如一天都要将一部分认证者从一个片调到另一个片中，避免攻击者将某一个片中的很多（1/3）的节点攻破。因此，如果当前是第e时区，那么新节点需要在e-1的时区获得加入资格。为了专门记录这个，论文使用了identity blockchain。
为了实现跨片交易，这篇论文将这个工作交给client来完成。这样的一个优点是ommiledger协议在跨片上就很简单，片之间不用交流。先上图：

分为三个步骤来实现一个这样的交易：将第一和第二个分片中的账户的钱转到第三个中，如上图所示。

用户要让第一和第二个片的leader生成一个证明，证明用户确实在这个片中有可用的钱。
用户拿到证明之后，锁住第一和第二个分片中的该账户中的钱。
用户将证明发给第三个片的leader，完成交易。

如果第二个leader说该用户没钱在该片，拒绝生成证明，而第一个leader已经成功生成了一个证明，并锁住了该片中的该账号。这时候client是无法让第三个片的leader执行交易的，因此client只能将第一个片中的账号解开。（论文中没有说明如何解开，第一个leader如何判断client没有成功转账？如果client成功转账了，同时恶意地也向第一个leader解开在第一个片中的账号，就会存在重复花费的问题，怎么解决？）
所以跨片交易的责任都交给用户自己来做了，不同片之间不存在信息的交流。在转账交易这个场景上是合理和简单的，解决了要么所有都成功要么所有都失败的效果，但是在其它应用场景上，估计就不够方便了。因为用户会偷懒，只希望点点按钮就能全自动化完成。

其它

在论文中所提到的Trust-but-Verify的认证，是一个很笼统的描述，存在很多没有解决的问题，比如如果惩罚optimistic validators？如何选举optimistic validators和core validators？
经过一定的时区之后，一部分节点需要调换到不同的片中，这就需要这些节点下载和加载好新的片的状态数据。而这些数据可达几百Gb，在短时间内拷贝和加载可不容易。因此我们要裁剪这部分数据，只留下对认证有用的数据。如何裁剪？举一个例子，在UTXO模型中，有 a -> b -> d, 表示三个交易的输入输出关系，为了认证d的钱是来自b的，我们需要使用b来认证。如果我们从b开始生成一个checkpoint，表示b之前的交易都是合法的了，无需再认证了，那么我们就可以不用再保留a的数据，只需要这个checkpoint就可以了。这样子我们就裁剪了a这个数据。裁剪之后，需要生成一个区块，让其它节点认证通过该checkpoint。
论文中提到了ByzCoinX，所谓是byzcoin的改善版本，两者的区别是，前者是一个三层的数，第一层也就是leader，第二层是一个片的group中的一个组长，第三层就是该片的其它成员。后者是一个层数为log（k）的树，可以是二叉树。

如果有理解上的出入，欢迎指出

收起

展开全文