Ultrain 公众号分三篇文章来阐述 Ultrain 的共识协议理论设计,后续还会推出一系列文章来详细说明 Ultrain 共识协议的工程实现。本文为 Ultrain 共识协议理论设计的第三篇(第 5 章),接上文 技术干货 | Ultrain 共识黄皮书解析(2)

05

安全性证明

5.1 定理
Theorem 5.1 (FLP 不可能性)异步系统下,即使只有一个节点崩溃或者作恶,不可能构造在确定有限时间内的共识算法。
Theorem 5.2 (容错上界)对于部分同步网络,最多容忍 1/3 的恶意节点。异步网络,确定性共识算法不能容错。强同步网络可以达到 100。
Theorem 5.3 (CAP 定理)对于网络分区,无法同时保证一致性和可用性。
5.2 安全假设
Assumption 5.4 (网络连通性)网络不会被超过 1/3 的恶意群体控制,任意两点的消息传播通过 gossip 协议,保证消息在确定时间范围内最终大概率到达。同时消息的源头不会被轻易识别出来,被攻击。
Assumption 5.5 (节点恶意行为)网络上的节点可以发送任意恶意消息或者串谋、拒绝响应,只要总持币数不会被 1/3 的恶意节点控制,那么区块链系统的安全性和活性就能得到保证。
Assumption 5.6 (弱同步时钟)各个节点依赖本地时钟和网络消息判断何时进入下一轮。不同节点的本地时钟可能存在差异,需要定时跟网络时钟服务(如微软)进行矫正。我们的每轮是固定时间宽度,考虑了消息在不同网络拓扑下的传播时间分布和节点处理消息的时间。
Assumption 5.7 (恶意节点数)假设网络上不可能有两个相同的集合,每个集合包含了相同的签名;即假设了足够的恶意节点持有的代币数。
5.3 推论
虽然拜占庭共识能保证全网系统的最终一致性,但是因为我们在公网上,情况比较特殊:

  • 为了扩展性的要求,考虑的是通过委员会 + 阈值的方式,而不是传统的每个节点接收到其他全部节点的消息后做响应。

  • 节点间的信息传输非点对点传输,而是通过公网 gossip 方式传播,恶意节点可能会将消息只广播到部分网络分区,能在超时范围内,影响该网络其他节点的接收消息的完整度。

恶意节点可能会有以下几种攻击的可能性:

  • Case1: 作为 Proposer,有意向一部分网络节点发送 PROPOSE 消息,向另外一部分节点延迟发送,或者根本不发送。

  • Case2:作为 Voter,有意向一部分网络节点发送 ECHO 消息,向另外一部分节点延迟发送,或者根本不发送。

Corollary 5.7.1 可验证延时函数能够解决不提交问题。
证明:对于随机数生成过程中,贡献者有可能拒绝提交的问题,假如能够让提交与否的结果变得不可预测,那么贡献者是否提交已经不是那么重要。考虑到延时函数的不可提前预测的特性,所以能解决上述问题。
Corollary 5.7.2Case1 不会影响区块链的一致性和活性。
证明:VRF 保证了 voter 分布的不可预测性和随机性,所以假如 PROPOSE 消息没有大于 TH1 的网络上传播,大部分节点将无法在足够的超时范围内收到足量 ECHO 消息,从而以空交易批的方式进入第二轮;对于少部分能在超时范围内接收到 ECHO 消息的节点,在第二轮将无法得到足够多的对应交易 hash 的 ECHO 消息,而会在第三轮收到空交易批的 ECHO 消息,所以最后所有节点都会以空的交易批结束。网络的一致性得到保证。同理,假如 Proposer 对不同的网络分区广播不同的 PROPOSE 消息,也会导致所有消息都接收不到足量的 ECHO 消息,最终所有节点以空交易批结束。活性:VRF 会选足够多的 Proposer,另外引入公平的随机性,从而保证所有 Proposer 都是恶意节点的概率非常小,系统会大概率获取一定的交易批次。
Corollary 5.7.3 Case2 不会影响节点的一致性和活性。
证明:voter 在 case2 主要是干扰网络的一致性,VRF 保证了 voter 分布的不可预测性和随机性,所以其实 voter 无法确定其他 voter 的位置,假设全部 voter 在网络的分布是均匀的,恶意 voter 很难通过只广播小部分分区,影响大部分 voter 的目的。即使假定 voter 能控制足够量其他 voter 接收的消息,从而控制分区 1 超过阈值收敛为交易批,分区 2 超时,但是因为我们超时后的行为是随机的,继续提交交易批,或者提交空交易批,所以这种不可预测的行为让 voter 无法控制网络,最后超出固定轮数后,所有 voter 最后以空交易批结束。但是,这属于极端情况,因为恶意节点不能一直作为 voter 存在,所以最后网络还是不受恶意节点控制。
Corollary 5.7.4 强同步网络下,Ultrain 共识第二轮结束后即完成;半同步网络下,Ultrain 需要多轮可以大概率收敛。
证明:在强同步网络下,任何节点在超时范围内,都能收到其他节点发过来的消息。基于假设,网络恶意投票数不会超过 1/3,所以所有节点在第一轮都可以收到所有的共识提议,无论是恶意还是诚实节点发送的。在第二轮过程中,只有诚实节点的提议会收到足够多的票数,所有节点都确定性地执行,并达到相同的结果。在半同步网络下,所有节点依然可以保持确定时间收敛和一致性。
Corollary 5.7.5 Ultrain 可以防御女巫攻击。
女巫攻击主要是利用系统的不公平性,为某一实体谋取利润的方式。我们有如下防御方式

  • 针对利用大量的假名,构造多个伪身份对应一个真实身份的攻击,Ultrain 采用硬件指纹的方式,唯一地对网络上的代币持有者进行标示。

  • Ultrain 采用 VRF 函数,保证即使用户拆分为多个伪身份,依然不能产生超出总持有代币的投票权,所以不能进行女巫攻击。

Corollary 5.7.6 Ultrain 可以抵御 Selfish-mining 攻击
Ultrain 基于的 BFT 系统是保证所有节点的一致性,所以即使外部节点独立生成一条链,也不会被网络诚实节点接受,从而无法影响节点一致性。同时为了保证节点
Corollary 5.7.7Ultrain 可以抵御长程攻击 (Long range attack)
Ultrain 基于 VDF 的共识方式,考虑到 VDF 本身的时间不可缩短性,不可能从 genesis 或者任意一个历史点伪造一条新的链赶上主链,所以可以避免长程攻击。
Corollary 5.7.8 Ultrain 可以抵御 Nothing-at-stake 攻击
Ultrain 中的见证节点相当于投票节点,每个代币持有者的投票能力与代币成正比,低于 1/3 的持有者不会有能力产生分叉。在投票过程中,投票节点可能会对多个块投赞成票,但是诚实节点只会对一个块进行投票,所以即使攻击者会多投,共识过程也会产生唯一的最终块,所有节点达成一致,所以不会受到该攻击的影响。通过硬件指纹的唯一性,Ultrain 也会对双重投票的节点进行一定比例的惩罚。
Corollary 5.7.9Ultrain 可以抵御 DoS 和 DDoS 攻击
DDOS 是通过消耗资源使被攻击者的服务机不工作,DOS 是直接利用对方的漏洞。即使共识代码出现了一定的 bug,系统被攻击崩溃也是有一定难度的,主要基于如下几点:

  • 攻击成本是 o(n²),所以同时攻击多个节点的成本是很高的。

  • 基于 gossip 的话更难被锁定信号源进行攻击。

  • 假如是放在 sandbox,签名放在外面的话,或者用 sgx,那么即使实现有 bug 不会影响到单个节点的安全性,比如是代币被花;应该采用不同的 vote key 和 tx sig key;sandbox 不会让系统其他模块被污染,所以我们需要隔离好用户的钱包和共识代码,特别是针对 PoS 场景,不能采用同样的账户。

  • 假如是有足够的时间窗口,能快速启动的话,那么能保证节点快速启动,不会影响到整个系统的 livenss。

网络分区将导致区块链系统的可用性和一致性不能同时满足。一般情况,区块链系统都选择中止,或者分叉(比如比特币)。为了及时发现分区,我们的 VRF 函数考虑了在不同地域的采样,比如要求 voter 必须在不同的国家内有一定的比例。因为我们不想在中国和美国都出现脑裂的情况,系统也出现脑裂。
References[1] Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99,pages 173–186, 1999.2 Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery.ACM Transactions on Computer Systems (TOCS), 20(4):398–461, 2002.[3] Jae Kwon. Tendermint: Consensus without mining. URL http://tendermint.com/docs/tendermint {_} v04. pdf, 2014.[4] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft pro?tocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,pages 31–42. ACM, 2016.[5] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand:Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51–68. ACM, 2017.[6] Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In Foundations ofComputer Science, 1999. 40th Annual Symposium on, pages 120–130. IEEE, 1999.[7] Timo Hanke, Mahnush Movahedi, and Dominic Williams. Dfinity technology overview series consensus system, 2018.[8] Andrey Bogdanov, Miroslav Knežević, Gregor Leander, Deniz Toz, Kerem Varıcı, and Ingrid Verbauwhede. Spongent: A lightweight hash function. In International Workshop on Crypto?graphic Hardware and Embedded Systems, pages 312–325. Springer, 2011.[9] Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and María Naya-Plasencia. Quark: A lightweight hash. In International Workshop on Cryptographic Hardware and Embedded Systems,pages 1–15. Springer, 2010.[10] Yong Wang, Sushant Jain, Margaret Martonosi, and Kevin Fall. Erasure-coding based routing for opportunistic networks. In Proceedings of the 2005 ACM SIGCOMM workshop on Delay?tolerant networking, pages 229–236. ACM, 2005.[11] Daniel J Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang. High-speed high-security signatures. Journal of Cryptographic Engineering, 2(2):77–89, 2012.[12] Patrick Longa. Four and four lib.[13] Husen Wang. Random Number Generation Code. https://github.com/wanghs09/randgen,2019.[14] Husen Wang. Layer2 randomness. https://github.com/wanghs09/Layer2Rand, 2019.[15] Scott Aaronson. The limits of quantum computers. Scientific American, 298(3):62–69, 2008.[16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange-a new hope. In USENIX Security Symposium, pages 327–343, 2016.[17] Pierre-Louis Cayrel and Mohammed Meziani. Post-quantum cryptography: code-based signa?tures. In Advances in Computer Science and Information Technology, pages 82–99. Springer,2010.[18] Richard Lindner and Chris Peikert. Better key sizes (and attacks) for lwe-based encryption. In Cryptographers’ Track at the RSA Conference, pages 319–339. Springer, 2011.[19] Brent Waters. Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization. In International Workshop on Public Key Cryptography, pages 53–70.Springer, 2011.[20] Dan Boneh and Matthew Franklin. Identity-based encryption from the weil pairing. SIAM journal on computing, 32(3):586–615, 2003.[21] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. Pinocchio: Nearly practical verifiable computation. In Security and Privacy (SP), 2013 IEEE Symposium on, pages 238–252.IEEE, 2013.[22] Léo Ducas, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystals–dilithium: Digital signatures from module lattices. 2018.[23] Daniel J Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O’Hearn. Sphincs: practical stateless hash-based signatures. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 368–397. Springer, 2015.[24] Jintai Ding and Dieter Schmidt. Rainbow, a new multivariable polynomial signature scheme.In International Conference on Applied Cryptography and Network Security, pages 164–175. Springer, 2005.[25] Dan Boneh, Craig Gentry, Ben Lynn, Hovav Shacham, et al. A survey of two signature aggregation techniques. RSA cryptobytes, 6(2):1–10, 2003.
让信任计算赋能各行各业
技术干货 | Ultrain 共识黄皮书解析(3)Ultrain 团队核心管理人员
技术干货 | Ultrain 共识黄皮书解析(3)
扫二维码下载 UltrainOne APP:
技术干货 | Ultrain 共识黄皮书解析(3)


以下为 Ultrain 各社交媒体账号
欢迎大家加入:
技术干货 | Ultrain 共识黄皮书解析(3)微信用户可关注公众平台:ultrainchain 并可添加管理员微信(Ultrain_Fan-Club)或扫码申请加入超脑链 Ultrain 中文社区技术干货 | Ultrain 共识黄皮书解析(3)
技术干货 | Ultrain 共识黄皮书解析(3)微博用户可关注:@Ultrain 超脑信任计算
技术干货 | Ultrain 共识黄皮书解析(3)Facebook 用户可访问主页:UltraincommunityLink:http://fb.me/Ultraincommunity
技术干货 | Ultrain 共识黄皮书解析(3)Twitter 用户可关注:@UltrainBLink:https://twitter.com/UltrainB
技术干货 | Ultrain 共识黄皮书解析(3)Telegram 用户可加入电报群:Link:https://t.me/UltrainOfficial技术干货 | Ultrain 共识黄皮书解析(3)

-END-

来源链接:mp.weixin.qq.com