IPDPS 2020 | CycLedger：一个通过分片技术实现的安全分布式账本协议
关键词：分布式账本 分片技术 组长重选机制
导读
第34届并行分布式处理国际研讨会（IEEE International and Distributed Processing Symposium, IPDPS 2020）将于2020年5月18-22日在美国新奥尔良召开，中心邓小铁课题组共有2篇论文被接收。本文为其中一篇《CycLedger：通过分片技术实现的规模化、安全的并行分布式账本协议（CycLedger: A Scalable and Secure Parallel Protocol for Distributed Ledger via Sharding）》的解读。
背景
比特币的出现无疑为人们对数字货币的认识打开了一扇全新的大门。借由区块链技术，其可以在节点分布式的条件下保证交易的安全性、不可篡改性以及可追踪性。这样的设计使得比特币无需一个大型的中心管理机构（如银行等）即可进行管理，而分布式账本的概念也由此而产生。
在比特币之后，利用区块链的去中心化和不可篡改特性而实现的分布式账本大量涌现。但是，在这研发过程中，研究者们意识到一个重要的问题：在这些包括比特币的解决方案中，绝大部分的算力都会被浪费掉，这样的缺点导致这一类分布式账本的速度与中心化的交易存储模式（如万事达、Visa等）的速度相差甚远。一个解决方案就是利用分片技术。通过将所有节点分成若干个并行工作的小组，分布式账本协议的速度可以提高2~3个数量级。
简介
已有的基于分片技术的分布式账本协议都面临以下的问题：首先，在某个小组的组长邪恶时，这些协议的效率都会面临巨大的损失；其次，这些协议并不能给出显式的对网络中节点的激励，即，网络中节点没有充足的动机来执行这些协议。
CycLedger 在保证了已有的最强安全性的前提下解决了第一个问题，并对第二个问题提出了一个已经成型的思路。
协议概述
我们的协议以轮的方式进行。在每一轮中，会产生一个中心裁判委员会。这个委员会负责管理其他所有小组并产生最后的区块。其余所有节点均匀分成若干个小组。每一个小组专门对接某一特定用户群体（每个用户群体被称为一个分片），维护这个群体内所有用户的信息。每一个小组由一个组长、若干个监察员和其余群众构成。组长负责收集与相应分片用户相关的交易并统筹组员的意见，而后将最终决定提交中心裁判委员会进行审核。每组的监察员负责监督本组组长的行为，一旦组长做出违反协议规定的行为，诚实的监察员会向中心裁判委员会进行检举，若检举通过则会将原有组长换下，更替新的组长。一组中的其余群众则负责进行群体决策。整个网络的结构图如下图所示。
同时，我们的协议中采用了声誉（reputation）机制，这一机制用来评价网络中每个节点的算力大小以及诚实程度，在分布各个节点的收入时起到重要作用。简单来说，一个节点算力越高，其声誉越高，其获得奖励也就越多。而一个被确定邪恶的节点（被成功检举的组长）的声誉会大幅下降，进而导致其收益降低。
具体的协议分为以下七个阶段：
1
小组形成阶段
在这一阶段中，所有确定参加的非特殊节点（即一般群众）会被分组。
2
半承诺交换阶段
在这一阶段中，组长之间会交换对各自组员名单的一个半承诺。之所以叫半承诺，是因为其只满足捆绑（binding）的性质，而不满足隐藏（hiding）的性质。但是，后者对我们的协议是无关紧要的。这个半承诺可以使得邪恶的组长无法伪造本组成员名单。
3
小组内共识阶段
在这一阶段中，每个小组会对只涉及到本组对接的用户的合法交易集合达成共识。具体的小组行为如下图所示。
4
小组间共识阶段
在这一阶段中，小组之间会对跨分片的合法交易集合达成共识。在这一阶段中，为保证协议的安全性和高效性，在第二阶段中组长交换的半承诺是至关重要的。
5
声誉更新阶段
在这一阶段中，每个节点的声誉会根据他在本轮中的行为进行更新。粗略地说，其表现出的算力越高，则其声誉的提升就越多；表现出的算力越低，其声誉的提升就越少，其声誉甚至可能降低。同时，被成功检举的邪恶组长会在这一阶段得到惩罚。
6
特殊节点选举阶段
在这一阶段中，下一轮的特殊节点的身份会被确定。其中，声誉较高的节点会被选作组长，因为他们往往拥有更高的算力，从而可以帮助提高整个协议的效率。而为了保证协议安全性，其余特殊节点的身份将会被随机均匀选择。
7
区块广播阶段
在这一阶段中，这一轮最后产生的区块会被广播，同时，用户的状态也会相应得到更新。
创新点和评价
如简介中所述，CycLedger 的创新点在于（1）组长邪恶时仍可保证高效；以及（2）有显式的激励机制。后者是通过声誉机制保证的，而为了达到前者，我们创新性地设计了一个组长重选机制。
具体而言，在协议的任何时刻，当一个诚实的监察员意识到本组的组长作恶时，他可以将自己的证据在组内进行广播。若这一证据被组内多数人所认可，其可以将所有同意者的签名上交给中心裁判委员会进行审核。如果通过审核，则当前的组长会被换下，而一个新的组长会被选出。这一过程如下图所示。
通过这样的机制，做坏事的组长一定会被发现，从而被放逐。这使得我们的协议能够很好应对邪恶的组长。同时，这一机制可以保证一个好的组长不会被恶意检举成功。
最后，我们将 CycLedger 与其他协议的各方面性能对比如下：
从上表中可以看到，CycLedger 在实现以上创新点的同时依然维持了较低的复杂度和较高的安全性。
IPDPS
并行分布式处理国际研讨会（IEEE International and Distributed Processing Symposium, IPDPS）是并行与分布式计算领域的著名会议。该会议是一个面向世界各地工程师和科学家的国际论坛，旨在展示他们在并行计算各个方面的最新研究成果。IPDPS 2020 将于2020年5月18-22日在美国新奥尔良召开。
张梦倩 李济宸 陈炤桦 陈宏崟
EconCS@PKU
近 期 科 研 进 展
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。