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

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

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

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

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

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

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

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

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

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

“小飞象”采用PRBC保证交易被正确广播到全网，进而应用MVBA将对交易的共识转换为对证明的共识。（研究团队供图）

在遍布全球四大洲的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