节点总数固定,如何用最少的通信轮数得到共识的不可预测的随机数?

17 小时 53 分钟前
 yodi

节点总数固定,每个节点有自己的私钥和其他所有节点的公钥。 网络通信质量不稳定,有丢包的可能,各个节点间延时不均匀。 用什么方式可以在少数节点宕机、丢包、延时情况下依然能用最少的通信轮次共识出不被预测的随机数?

节点 N 有 i 个。 当 N 得到出上一个已共识的随机数时,将自己产生的随机数 r 的 hash 与签名 Ni(hash(r),sig)广播 N 陆续收到其他节点 Ni(hash,sig),公钥验证后追加保存在 S 里,当 S 中累计到 i/2+1 个 sig 后签名并广播 S N 陆续收到 Si,这时由于网络质量在极端情况下会使每个 N 的 S 是不同的(比如 12347 ,23456 ,13456 )而无法达成共识,我觉得思路不对,原计划在 hash 达成共识后再公示出 r ,但现在 S 无法达成共识。

求老哥们指点一下思路,可以忽略我的想法。

510 次点击
所在节点    程序员
4 条回复
jingniao
17 小时 7 分钟前
分布式共识算法 raft paxos 之类的?
rekulas
15 小时 28 分钟前
有多个节点的话可以走选举模式,例如每 3 个节点一个组,每一个小组内部协商一个种子+salt 例如 5aa9ad69aa9e7ecdca+salt 然后广播计算的 hash,所有组广播完成后再广播种子然后将所有种子排序组装成最终随机数
这种情况下由于每个组有 3 个成员即使其中 1 2 个节点临时不通也不影响结果,不过也存在一定的风险,例如某个组织恰巧控制了某个组所有节点就可能发起攻击,针对这种情况对于节点需要有奖惩机制以尽量降低攻击可能性

还有一种方法,延迟随机数方向,例如各个节点需要在 3 秒内广播自己产生的种子,然后将有效时间内的所有种子进行排序计算最终随机数-但这个计算过程需花费 N 秒,N>>3,通过调整 N 的值即可让攻击成本上升到一个无法接受的水平,从而保证安全性

其他方向还有包括门限签名等分布式算法
yodi
13 小时 17 分钟前
@rekulas 预设的条件是网络质量不佳,把节点分组协商种子的意义是什么?协商会消耗更多的时间。另一种方法中,介于通信质量差,每个节点收到的种子的节点可能不完全一致,甚至于完全不一致。我没懂您的意思,待我多消化消化。


@jingniao 是的,但是我不太确定这种场景下应该用哪种共识算法,raft 的话如果恶意节点做 leader 是否能避免他作恶? BFT 就会好一些,投票机制可以容忍部分节点瞎投或者不投票。但我不知道该用哪种 BFT ,有点难理解。
jingniao
6 小时 14 分钟前
你都用签名了,leader 节点最多不提交共识,跟随节点可以验证数据有效吧,leader 节点不工作的就超时降级重选吧。
另外你这不就是区块链中联盟链吗,可以找资料看看。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://yangjunhui.monster/t/1131798

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX