Skip to content
Go back

千节点 BFT 吞吐 62 ktx/s:Pando 用 200 人小委员会做共识

Edit page

TL;DR

清华大学团队在 NDSS 2026 上发表的 Pando,把 BFT 共识的规模天花板从约 100 个副本推到了 1000 个:在横跨 4 个大洲区域的 WAN 环境里,1000 个副本跑出 62.57 ktx/s 的峰值吞吐。做法是委员会抽样——每轮只让一小批副本投票,其余副本只管接收结果;抽签用 VRF,委员会身份在投票发出前不公开。最关键的一步在理论上:每轮共识换三批委员会,让安全失败概率从 O(δ)O(\delta) 降到 O(δ2)O(\delta^2);同样 10−910^{-9} 的失败率,委员会只要 200 人,而 Algorand 需要 2000 人。代价是容错从最优的 f<n/3f < n/3 降到 f<(1/3−ϵ)nf < (1/3-\epsilon)n,但 ϵ\epsilon 会随规模增大趋近于 0。

论文信息卡

背景

BFT(拜占庭容错)是许可链的默认共识模型。但它有个出名的扩展性诅咒:副本数 nn 一上去,性能就断崖式下跌。反观以太坊这样的非许可链,验证者数量超过 100 万(2025 年 4 月 beaconcha.in 数据)。一百万对一百,这个差距就是 BFT 研究二十年没填上的坑。

填坑的思路有几条。分片把网络切成多个小 BFT 分片,但跨分片开销和安全假设都不便宜;并行化能榨出一些吞吐,但治标不治本。近几年最有希望的是”解耦”路线:把”传区块”(搬运交易数据)和”定顺序”(对区块顺序达成共识)分开,共识只处理区块哈希或签名证书,不再被大数据拖累。Narwhal/Bullshark、Dumbo-NG、Star 都是这条路线的代表作,其中 Star 在 91 个副本的 WAN 环境下做到 256 ktx/s,是当时最能打的方案。

但解耦路线也有天花板:大约 100 个副本。论文的实验里,Narwhal 和 Star 在低端虚拟机上超过 100 个副本就根本启动不起来,反复报”connection refused”。瓶颈有两个,都和 nn 有关:通信上,所有副本两两直连的 nn-to-nn 模式让消息量随 n2n^2 膨胀;计算上,每个 quorum certificate(QC)要攒 O(n)O(n) 个签名,门限签名又随 nn 变大而变慢。想冲到 1000 个副本,必须把”全员参与”这个前提本身拆掉。

方法拆解

Pando 的思路一句话概括:共识只让委员会干,全网只负责收结果。论文沿用解耦框架,协议分三段流水线:传输——每个副本发提案、收集签名形成 QC;共识——只对 QC 的顺序达成一致;状态同步——没拿到提案的副本事后去补数据。

传输:只让委员会回签名

传统的一致广播(CBC)里,提案者把区块发给所有人,再等 n−fn-f 个签名回来。Pando 只改了一个地方:每轮每个实例抽一个 κ\kappa 人委员会,只有委员会成员才回签名。提案者攒够 κ−t\kappa-t 个签名就形成 QC,其中 t=κ/3t=\kappa/3。

Pando 的整体思路:传统 CBC 要全体副本回签名,Pando 只让 κ 人委员会回签;共识每轮换三批委员会投票(来源:论文原文)

图:Pando 的整体思路:传统 CBC 要全体副本回签名,Pando 只让 κ\kappa 人委员会回签;共识每轮换三批委员会投票(来源:论文原文)

这一改带来两个直接好处:回签名的副本数从 nn 降到 κ\kappa(与 nn 无关的安全参数),通信不再随 nn 膨胀;QC 从 O(n)O(n) 个签名缩到 O(κ)O(\kappa) 个,共识要处理 O(n)O(n) 个 QC,每个 QC 变小,共识的通信量也随之变小。复杂度对比很直观(LL 是区块大小,κ\kappa 是安全参数长度):

协议传输过程通信共识过程通信
Narwhal / BullsharkO(Ln2+κn4)O(Ln^2+\kappa n^4)O(κn3)O(\kappa n^3)
Dumbo-NGO(Ln2+κn3)O(Ln^2+\kappa n^3)O(κn3)O(\kappa n^3)
StarO(Ln2+κn3)O(Ln^2+\kappa n^3)O(κn3)O(\kappa n^3)
PandoO(Ln2+κ2n2)O(Ln^2+\kappa^2n^2)O(κ2n2)O(\kappa^2n^2)

改进集中在 κ\kappa 这一项上:原来是 κn3\kappa n^3,现在是 κ2n2\kappa^2n^2。nn 越大,省得越多。

共识:每轮换三批委员会

共识过程是一个原子广播协议,分 New-View、Propose、Prepare、Commit 四个阶段,每轮 leader 按 le mod nle \bmod n 轮换。关键设计在 Prepare 和 Commit 阶段:每轮采样三个委员会 Cc,le1C^1_{c,le}、Cc,le2C^2_{c,le}、Cc,le3C^3_{c,le},分别用于 New-View、Prepare、Commit;每个委员会成员投完票就不再投票。

“投完即走”是整篇论文对付自适应敌手的核心。委员会抽样过去只在静态敌手模型下成立:敌手开局就定好要腐蚀谁。自适应敌手可以在协议运行中途、看到谁进了委员会之后再下手腐蚀。Pando 的回答是让腐蚀”为时已晚”——投票已经发出去了,再腐蚀这个副本也改不了什么。论文假设弱自适应敌手加”原子发送”:副本要么在发消息前被腐蚀,要么在发完之后被腐蚀,不能中途篡改已发出的消息。

三委员会还有一个附带的好处,直接决定了委员会能压多小。安全被攻破需要 Prepare 和 Commit 两个委员会同时”坏人超标”,失败概率从 O(δ)O(\delta) 变成 O(δ2)O(\delta^2)——δ\delta 是单个委员会坏人超标的概率,两个独立的小概率事件同时发生,概率是乘积。论文指出,多加一个阶段还能进一步压到 O(δ3)O(\delta^3),实现里用的是两阶段版本。

数学:Chernoff 界的新用法

委员会到底要多大?论文用 Chernoff 界给了一个新 bound(引理 1):设系统坏副本占比 α=1/3−ϵ\alpha = 1/3-\epsilon,想让委员会内坏人不超过 κ/3\kappa/3 的失败概率低于 δ\delta,委员会规模取 λ=3αϵ2ln⁡1δ\lambda = \frac{3\alpha}{\epsilon^2}\ln\frac{1}{\delta} 即可。直觉是委员会是全网的随机样本,坏人占比偏离全网水平的概率随委员会增大指数衰减。

委员会规模与容错代价 ϵ 的关系(n=2000):委员会越大,ϵ 越小、容错越接近最优 n/3;五条曲线按失败率 10^-3 到 10^-10 分层(来源:论文原文)

图:委员会规模与容错代价 ϵ\epsilon 的关系(n=2000n=2000):委员会越大,ϵ\epsilon 越小、容错越接近最优 n/3n/3;五条曲线按失败率 10−310^{-3} 到 10−1010^{-10} 分层(来源:论文原文)

这张图就是 Pando 的理论底气:同样 10−910^{-9} 失败率,Algorand 要 2000 人委员会,Pando 只要 200 人;同样 10−410^{-4} 失败率和 ϵ=0.067\epsilon=0.067,旧方法要约 400 人。更具体地看论文表 II(失败率 10−410^{-4}):n=1000n=1000、委员会取 0.4n0.4n 时 ϵ=0.041\epsilon=0.041,即容错 f<0.292nf < 0.292n,已经很接近最优的 n/3n/3;而 n=100n=100、委员会取 0.2n0.2n 时 ϵ=0.193\epsilon=0.193,容错只剩 f<0.14nf < 0.14n——小网络的代价明显更大。

抽签:VRF 暗箱

委员会成员怎么选?用可验证随机函数(VRF)。每个副本对”过程 + epoch + 实例号”做一次 VRF 求值,结果低于难度阈值 DD 就入选,入选后把 VRF 证明附在消息里,其他副本用 ComVerify 验证。身份在投票发出前不公开,发出后可验证。VRF 开销很小:每轮每副本做 O(n)O(n) 次查询,实测 ComProve 每次 2.8ms、ComVerify 每次 0.1ms。

状态同步:O(κn) 条消息

以前的状态同步是全员互查,O(n2)O(n^2) 条消息。Pando 同样用委员会:对每个提案抽一个分发委员会,持有该提案的委员会成员把它广播给所有人,收到者拿哈希校验——QC 里有提案哈希,哈希对不上就拒收。消息量降到 O(κn)O(\kappa n)。

实验与数据

实现是 Go 语言,协议约 1 万行代码、评测约 1000 行,开源在 GitHub;通信用 gRPC,认证用 HMAC、哈希 SHA-256、纠删码 Reed-Solomon。评测在 AWS EC2 上做,最多 500 台虚拟机、1000 个副本,均匀分布在 4 个区域的 WAN 环境;默认交易 250 字节,每组实验重复 5 次取平均。

n=31/61/91 时四种协议的峰值吞吐:Pando(0.8) 在 n=91 达到 344.47 ktx/s,比 Star 高 28.22%(来源:论文原文)

图:n=31/61/91n=31/61/91 时四种协议的峰值吞吐:Pando(0.8) 在 n=91n=91 达到 344.47 ktx/s,比 Star 高 28.22%(来源:论文原文)

先看小规模对照。n=91n=91 时,Pando(0.8) 的峰值吞吐是 344.47 ktx/s,比委员会取全员的 Pando(1) 高 81.01%,比 Star(268.65 ktx/s)高 28.22%。Pando(1) 因用 CBC 而非弱 CBC、又多了 VRF 计算,略低于 Star,但始终高于 Narwhal(116.65 ktx/s)。Narwhal 和 Star 在这组低端机(4 vCPU)上超过 100 副本就启动失败,连跑都跑不起来。

再看规模扩展。委员会取 0.2n0.2n 时,250 字节交易的峰值吞吐随 nn 变化是:n=100n=100 时 2947.44 ktx/s,n=200n=200 时 2812.40,n=300n=300 时 1558.42,n=400n=400 时 600.96,n=500n=500 时 158.25。吞吐随 nn 下滑是符合预期的——提案还是要广播给所有人,O(Ln2)O(Ln^2) 的传输项躲不掉;但关键是它还能跑,而前人到 100 就停了。

重头戏是 1000 副本。同一批 m5.xlarge 机型上跑不出任何吞吐,换成高带宽的 m5n.2(200 台虚拟机),Pando 达到 62.57 ktx/s;加到 500 台虚拟机是 73.2 ktx/s,提升有限,说明瓶颈不在机器数量。而带宽差的 c5.4xlarge 只有 1.6 ktx/s。论文的部署结论很直接:大规模下瓶颈从 CPU 变成了带宽,要高带宽、中等 CPU 的机器。顺带一提,最低配的 t2.micro(1 vCPU、1 GiB 内存)在 n=100n=100 时仍有 95.37 ktx/s——协议对机器要求并不高。

和 Algorand 的对比最能说明委员会缩小 10 倍的价值。同样 10−910^{-9} 失败率,Algorand 论文里用 1000 台虚拟机跑 5 万副本、22 秒才交付 2 MB 交易;Pando(0.4) 1 秒交付 13.84 MB,约 154 倍。本地 7 节点测试网同条件对比:Pando(1) 75.21 ktx/s,Algorand 5.72 ktx/s,约 13.15 倍。差别主要来自 Algorand 每轮只定一个区块提案,而 Pando 每轮至少定 n−fn-f 个。

状态同步的改进也很直观:n=300n=300 时,Pando(0.4) 的状态同步延迟是 911 ms,而 Pando(1) 是 27203 ms,只有后者的 3.3%。不过 n≥100n \ge 100 后,共识过程的延迟反而超过了传输过程,主因是 QC 用签名集合实现、体积太大,换聚合签名可以缓解,但实现里没做。

相关工作对比

和 Algorand 比,Pando 是”委员会抽样”从理论走向实用的第二步。Algorand 是第一个实用的 VRF 委员会抽样协议,但它解决的是拜占庭 agreement(BA)问题、每次只定一个区块,且委员会要 2000 人。Pando 解决的是带客户端的 BFT/原子广播问题,每轮定 n−fn-f 个提案,委员会 200 人就够。Pando 的带宽利用更均衡:所有副本都能提案,而不是只有一个 leader。

和 King-Saia 的采样器、Abraham 等人的亚二次通信 BA/BC 工作比,Pando 把委员会抽样从理论协议搬进了可部署的 BFT 系统。那些工作聚焦 BA/BC 问题本身,通信复杂度做到亚二次,但没处理 BFT 的客户端模型、传输与共识解耦、状态同步这些工程环节。Pando 的三段式改造——可扩展 CBC、原子广播、状态同步——每一个都可以独立使用。

和 Narwhal、Bullshark、Dumbo-NG、Star 这些解耦路线的前辈比,Pando 不是另起炉灶,而是在它们的框架上把”全员参与”换成了”委员会代劳”。它只是在 Star 的三段流水线上把每一段的 O(n)O(n) 换成 O(κ)O(\kappa)。代价是容错从最优的 n/3n/3 降到 (1/3−ϵ)n(1/3-\epsilon)n,以及安全性从确定性变成概率性(1−10−41-10^{-4} 到 1−10−91-10^{-9} 量级)。

局限与开放问题

  • 容错不是最优:f<(1/3−ϵ)nf < (1/3-\epsilon)n,ϵ\epsilon 只有在 nn 足够大时才趋近于 0。小网络下代价明显:n=100n=100、委员会 0.2n0.2n 时 ϵ=0.193\epsilon=0.193,容错只剩 f<0.14nf < 0.14n,比 n/3n/3 差了一倍多。
  • 安全是概率性的:失败率 10−410^{-4} 到 10−910^{-9} 是可以调的参数,但不是确定性保证。部署时必须按网络规模查表选委员会大小和 ϵ\epsilon,选错就直接牺牲安全性。
  • 依赖 atomic sends 假设:弱自适应敌手模型要求消息”要么发前被腐蚀、要么发后被腐蚀”。真实 TCP 的 transmit-ack-retransmit 模式下,敌手可能提前获知信息,作者把这点列为未来工作。
  • QC 体积仍是瓶颈:实现里 QC 是签名集合而非聚合签名,n≥100n \ge 100 后共识延迟反超传输延迟;聚合签名能缓解,但没有实测数据。
  • 实验上限 1000 副本:受 AWS 账号 500 台虚拟机限制,更大规模的表现论文未披露;状态同步通信仍有 O(Lκn2)O(L\kappa n^2) 的 n2n^2 因子。
  • 只覆盖部分同步网络:异步 BFT 的委员会抽样版本不在本文范围。

一点思考

Pando 最值得学的不是某个具体协议,而是一种”降维”思路:BFT 扩不上去的根因是全员参与,把”谁干活”和”谁验收”分开——委员会干活、全网验哈希——规模瓶颈就从 O(n)O(n) 的参与成本降到了 O(κ)O(\kappa)。判断上说一句:它离真正落地还有两步,一是把概率性安全的参数选择做成开箱即用的默认值,二是补上聚合签名、把共识延迟的尾巴收掉;但作为一篇 NDSS 论文,它把委员会抽样从”理论上可行”推进到了”1000 副本实测可用”,这个跨度本身就够分量。对做联盟链和许可链的团队来说,Pando 的代码开源,值得直接拿来跑一跑。

原文链接


Edit page
Share this post on:

Next Post
当模型学会讨好评分者:Anthropic 的隐藏目标审计实验