首个实用异步共识算法来了

2021-02-23 11:44 来源：中国科学报

　　如果是在中世纪，强大的拜占庭帝国如何让自己的将军们在一个有叛徒的非信任环境中建立战斗计划共识？现今，在区块链网络环境中，能在不同节点间达成共识的核心算法就是要解决这样的“拜占庭将军问题”。

　　近日，中国科学院软件研究所张振峰团队与美国新泽西理工学院唐强团队在区块链核心技术——拜占庭容错（BFT）共识研究中取得突破，提出了目前国际首个完全实用的异步共识算法——小飞象拜占庭容错（DumboBFT）算法，该成果发表于网络安全旗舰会议ACM CCS（第27届国际计算机与通信安全大会）。在异步BFT共识算法设计领域，我国此前未有重要研究成果在该会议上发表。

　　研究人员表示，这些成果可为我国区块链基础设施建设提供强安全、高性能、可扩展的新一代核心技术。

　　　　持续数十年的异步共识难题

　　1982年，图灵奖得主Leslie Lamport以在有叛徒的情况下，忠诚的拜占庭将军们通过信使远程通信，就共同进攻或后退的作战目标达成一致，来比喻如何解决区块链节点之间的信任问题，这就是拜占庭容错（BFT）共识算法的来由。后来，为了进一步解决信使被敌方俘获而造成的通信中断或延迟问题，另一位图灵奖得主Michael Rabin等又提出了异步BFT算法。

　　张振峰介绍，BFT共识算法是区块链的关键核心技术，它可以确保区块链安全可靠运行、提升区块链扩展能力和运行性能，具有运行性能高、资源消耗低、易于部署等特点，因此得到了工业界的青睐，已经广泛应用于国内外区块链系统中。

　　相较而言，异步BFT可以容忍网络通信故障、抵抗恶意网络节点的任意破环，是保障区块链在互联网环境下良好运行的更理想的共识技术。但如何设计高效的异步BFT共识算法，却是密码学和分布式计算领域的著名难题。

　　“用现有的各类随机化算法解决异步共识，就好比一只健壮却行动迟缓的'大象’，不仅会拖垮运行速度，还会让系统背上沉重的通信代价。”张振峰告诉《中国科学报》，早在20年前，国际密码学会前主席Christian Cachin等人就把“如何提升异步共识的关键性能指标”列为了公开问题。

　　　　“小飞象”成区块链新一代核心技术

　　为了设计完全实用的异步共识算法，中国科学院软件研究所从2015年开始了小飞象拜占庭容错算法研究工作。研究团队在分析了唯一一个接近实用的异步共识算法HoneyBadgerBFT后发现，其性能受限的根源是大量随机化子模块调用导致的运行时间增加。

　　“我们的新算法提出了全新的可证明可靠广播原语（PRBC），并巧妙利用多值共识算法（MVBA）将随机模块的调用从线性减少到常数，大大降低了运行时间，在容忍1/3的恶意节点的同时，突破了异步共识算法在性能上的设计挑战。”张振峰说，它变成了一只既健壮又灵活快速的“小飞象”。

　　在遍布全球四大洲的100个共识节点的测试网络中，小飞象拜占庭容错算法的确认延迟时间为24秒，不到HoneyBadgerBFT算法的1/20；交易吞吐量为每秒近1.8万笔，是HoneyBadgerBFT算法的9倍多。目前研究人员正计划在国内一些主流区块链平台部署该算法。

　　随着深入研究，团队成员路远、卢振亮等人还进一步提出了小飞象多值共识算法（Dumbo-MVBA），在消息数量、通信代价和运行时间等关键性能指标上达到了渐进理论最优，确认了MVBA才是实现异步共识的正确途径，回答了“如何提升异步共识算法的关键性能指标”这一长达20年的公开问题。该成果发表于分布式计算理论的旗舰会议ACM PODC 2020上。

　　相关论文信息：

　　https://dl.acm.org/doi/10.1145/3372297.3417262

　　https://dl.acm.org/doi/10.1145/3382734.3405707