Page 321 - 《软件学报》2025年第9期

4232 软件学报 2025 年第 36 卷第 9 期

21. if r ⩾ τ then
22. r = 0
23. 使用不可随机源置换共识序列得 L = PermutationWithCoinTossing([n])

4.2.3 循环等待断言和 Super-Dumbo
Super-Dumbo 即用以上的 k-RBC 算法和 Opti-MVBA 算法, 替换 Dumbo2 中的广播阶段算法和共识阶段算法.
Q 进行优化, 优化前需要重述 Dumbo2 P i 完成
同时将外部验证断言 中外部验证断言的原理: 此处验证是证明节点
了对其交易的广播, 即至少有 n−2 f 个诚实节点收到了来自 P i 的广播. 为了对这件事进行证明, 在广播阶段,
PRBC 使用 (n−2 f,n) -门限签名算法, 当节点 P j 在收到 READY 消息后, 使用私钥分片 SK j 对消息进行签名生成签
名分片 ss j , 并返回给节点 . 这也就意味着当且仅当 P i 收到了至少 n−2 f 个来自其他节点的签名分片, 才能生成
P i
P i 提交的交易进行验证时, 则提交对应的消息签名进行验证, 即外部验证的本
对于消息的签名. 当在共识阶段对
质是门限签名算法中的签名验证算法.
P i 的广播, 所以优化后
签名验证算法依旧是一个 O(n) 复杂度的算法, 而验证的本质是有足够多的节点收到了
Q 采取直接用本地收到的消息的 Merkle 树的根哈希值进行验证. 对于没有收到消息的节点, 可以
的外部验证断言
进行循环等待, 等到消息后完成验证. 对于没有等到消息的节点, 将处于循环等待状态, 并在本轮共识结束后杀死
循环等待进程.
2
共识阶段的循环等待验证总共减少了 O(n ) 的外部验证的时间复杂度, 同时由于验证不需要门限签名, 使得广
播阶段也省去了门限签名的签名算法和签名分片聚合算法.
其结构示意图如图 5 所示, 具体算法如算法 3 所示.

RBC
…
P 1 P 1 CBC 1 Q 1 P 1
RBC
RBC
P 2 … P 2 CBC 2 Q 2 P 2
RBC
Opti-MVBA
RBC
P 3 … P 3 CBC 3 Q 3 P 3
RBC
… … … …
RBC
…
P n P n CBC n Q n P n
RBC
循环等待断言
k-RBC
广播阶段 共识阶段
图 5 Super-Dumbo 结构示意图

a) 广播阶段: 节点通过 k-RBC 对提交的交易信息进行广播.
b) 共识阶段: 在完成广播阶段, 即接收到 n− f 个 k-RBC 的 Finish 消息后, 将交易加入 Opti-MVBA 中.
c) 输出阶段: 当 Opti-MVBA 返回交易后, 输出该交易, 完成本轮共识.

P l 上第 轮的 Super-Dumbo 算法.
r
算法 3. 节点
1. 外部断言 Q(v) ≡ if v 在本地交易集合 V 中 return True else 等待并循环断言 Q
v l 加入共识 do
2. upon 将交易