PLTCRB:基于最优平均通信复杂度的实用分布式随机信标
分布式随机信标(Distributed Randomness Beacon)研究的前沿突破 —— 大规模优化通信复杂度的实用方案
在当今众多技术领域中,可信随机数生成器(Randomness Beacon)是一项关键工具,对密码学、区块链、电子投票及众多应用的安全性具有重要作用。随机数生成器需要满足偏差抗性、不可预测性和公开可验证性。然而,传统的分布式随机信标(Distributed Randomness Beacon,简称DRB)方案通常依赖复杂的通信流程,或借助于公共公告板(Public Bulletin Board,简称PBB)来保障安全性,在参与者规模较大时容易受到性能瓶颈的制约。这一问题促使研究者们寻找更高效、更实用的新方案。
近日,来自上海交通大学电子信息与电气工程学院的Zheyi Wu、Haolin Liu以及Lei Wang在《Science China Information Sciences》期刊上发表了一篇题为“PLTCRB: A Practical Distributed Randomness Beacon with Optimal Amortized Communication Complexity”的研究论文。他们提出了一种全新的DRB协议——PLTCRB(Pipeline Timed Commitment Randomness Beacon),克服了现有方案的通信限制,实现了分布式情况下随机信标生成的最优摊还通信复杂度。
背景介绍:解决偏差抗性、不可预测性和通信复杂问题
随机信标的核心功能在于周期性生成公开可验证的随机数,这些随机数具备不可预测性和偏差抗性,且不依赖任何单一可信方。在区块链技术中,随机信标在领导者选择、分片(Sharding)以及智能合约(Smart Contracts)执行中发挥着不可或缺的作用。但在无权限网络中,参与各方往往相互不信任,设计一个高效鲁棒的协议成为一大挑战。
传统的DRB协议多基于门限签名(Threshold Signature, TS)、门限加密(Threshold Encryption, TE)或公开可验证秘密共享(Publicly Verifiable Secret Sharing, PVSS)等密码学技术。然而,它们通常需要高度交互性的通信步骤,这导致通信复杂度最少为O(n²)。此外,某些方法依赖公共公告板如区块链账本,这虽然提供了消息不可篡改和透明性,但也带来了额外的经济成本。为此,该研究提出使用时间承诺(Timed Commitment, TC)技术,以去除公共公告板的使用,并降低通信复杂度。
论文概述:研究机构及技术路线
这篇论文由上海交通大学的研究团队完成,于2025年2月发表在线《Science China Information Sciences》。论文详细描述并验证了一种基于时间承诺协议的新型DRB方案PLTCRB,该方案特别设计用于支持大量参与者并达到理想的通信性能。
研究设计与实施方法
a) 研究设计:结合时间承诺与多轮共识机制的创新框架
PLTCRB主要借助时间承诺方案以及多轮共识协议,通过整合分布式密码学和时间相关的技术,实现了摊还通信复杂度的最优化。研究流程由以下几部分组成:
时间承诺构建(Publicly Verifiable Timed Commitment, PVTC)
论文对时间承诺方案进行了重新设计,提出了一种公共可验证时间承诺(PVTC)的算法框架,包括以下关键算法:- Setup:生成公用参考字符串(CRS),用于初始化时间参数及设置安全参数。
- Commit:提交方对秘密值进行承诺,并生成承诺字符串及验证辅助信息。
- VerifyCommit:验证承诺的合法性,确保提交方的提交行为可信。
- ForcedOpen:强制公开承诺;如果提交方拒绝解锁承诺值,协议允许通过计算强制解锁。
- VerifyDecommit:提供验证算法,第三方可高效验证解锁值的正确性。
新型分布式随机信标协议(PLTCRB)
PLTCRB的协议设计包括以下步骤:- TC发布:由提交方(Committer)生成时间承诺,并广播至所有节点;若承诺验证通过,各节点对承诺部分签名。
- 多轮共识协议:因时间承诺的强制公开需要多个轮次,算法为每一轮次选取唯一的共识领导者,通过高效的请求-回复方式实现所有节点间的共识。
- 强制公开策略与验证:通过伪随机函数(Verifiable Random Function, VRF)选取一部分节点执行强制公开算法;在非常见情况下,默认值被采用以替代恶意提交方的承诺。
- 随机数输出:产生的随机数输出伴随验证证明,第三方可以依据随机数的来源和证明进行独立验证,确保安全性和公开性。
b) 实验与性能结果
研究团队在实验中分析了PLTCRB的理论性能及实验效率,分别考察了时间参数t和安全参数的位长度对协议运行时间的影响,以及与现有方案的性能比较。
实验结果:
- 强制公开承诺(ForcedOpen)过程的耗时随着时间参数t线性增加。
- 通信和计算复杂度分别均为O(n),当参与者规模较大时性能高于现有方案。
- 相较于头部协议如Headstart、Hydrand及Spurt,PLTCRB的通信带宽开销最低,尤其在参与节点数较大时,其扩展性和效率优势突出。
数据支持:
比较实验显示,在参与节点数增至上千时,PLTCRB的带宽利用率和吞吐量增速最为平稳,维持理想线性表现。
研究结论与价值
研究结论:
PLTCRB协议在分布式随机信标生成中成功实现了最优摊还通信复杂度,且无需依赖公共公告板,是一项在安全性与性能间达到平衡的创新方案。其方法秉持了DRB协议所需的活性、偏差抗性、不可预测性等属性。学术价值:
新构建的PVTC使得时间承诺技术首次应用于无公告板的随机信标生成中,为基于时间密码学的系统设计提供了新的范式。应用价值:
PLTCRB对于区块链、电子投票以及其他需要高效、公开随机数生成的应用场景具有显著价值。此外,它在大规模参与的分布式系统中,提高了系统的扩展性和经济性。
研究亮点与未来展望
通过消除公共公告板需求,PLTCRB克服了经济成本和中心化等限制,是针对参与方规模爆炸性增长的优化解决方案。同时,该方案为研究时间相关密码学工具在其他分布式协议中的应用提供了新方向。未来,随着更多计算资源的优化和分布式网络通信基础设施的改进,PLTCRB和其他类似方法将在实际部署中展现更强的实践潜力。
本项研究以精炼的理论和详实的实验验证,为分布式系统的随机信标设计树立了新的标杆。