利用雪崩算法主动协调交易本地状态

摘要

本文描述一种在中本聪共识机制网络下的节点之间的传播协议,在该协议中节点之间积极地协调各自的本地状态。它使得节点能够对彼此进行采样,以确定一个相冲突的集中哪个选项是在当前大多数节点的选择,并且将相同的选择推向大多数节点。本协议是基于雪崩共识算法改进而来,提供了协议的异步性、亚稳定性和静态终结性。

本文档不会深入讨论在雪崩算法白皮书中描述的细节和知识点,这些是需要读者自己去阅读原白皮书。同时,本文还要求读者已经理解了中本聪共识机制。


 


动机

降低比特币在多网络节点之间的熵的好处被广泛讨论,其中包括将执行成本高的工作移出关键路径来提高可扩展性、更快的交易确认/双花保护,和更强的拜占庭对抗中短期期链重组攻击。

中本聪共识是希望任何节点可以无须信任地参与达成共识,它通过使用工作量证明赋于每个状态一个真实世界权重。不幸的是,这对系统提出了一些不理想的要求,如同步性,刻意的人为延迟,和永久性地需要维护共识。比如,一个状态无法100%地确定。


我们意识到,由挖矿节点构成的大型节点,和大量的支付基础设施始终在线但不参与达成共识,我们可以设计一个协议,允许他们快速达成共享的网络状态,尽管这是主观的。矿工可以继续完成他们的工作,并最终将他们的本地状态固化为全局状态,从而使新加入的节点可以无须信任地加入共识。该协议试图使用预共识技术,以达成更快、更具扩展性和更安全的比特币现金。


 


目标

我们希望在协议上达成如下目标:

· 证明预共识系统在比特币现金上是可行的。


· 挖掘更多需要研究的,或潜在的问题。


· 提供一个可以工作的预共识系统,以允许任何节点都可以加入参与其中,用于实验和收集信息。

此外,协议必须具有以下属性:

· 无须许可:任何人都可以提供或索要采样


· 低延迟:实现秒级达成决策


· 元稳定性:参与者主动参与工作,并将系统状态朝着单一方向坍缩,并且能抵抗状态回撤。


· 平静:一旦做出决定,就不可逆,而且最终状态将不再需要额外的工作。


· 可扩展的成员体系:我们希望任何有兴趣的人都能加入


· 可扩展的资源:我们需要将系统扩展到全球现金系统水平。


· 拜占庭式容错:我们不假设所有参与者都是诚实的,系统能抗恶意行为。

协议概述

基于互斥点(based on points of mutual exclusion)我们认为每个区块和交易都是1个或多个冲突集的成员,比如花费相同的UTXO。我们使用雪崩算法,将每一个冲突集精确地分解为单个项目,并且参与者使用其本地状态参与解决网络冲突集,从而为所有参与节点提供共享的本地状态。

每个客户端在看到的一个未完成的项目时,都会维护一个基于雪球(Snowball-based)投票累加器。一旦看到一个项目,就会创建一个累加器,并开始投票确定最终状态的过程。只要有未解决的冲突集,客户端就会随机选择一个对等节点,询问它对这个项目的投票,并将这些投票输入投票累加器。一旦项目的接受信任度达到阈值,则冲突解决;这个项目被全网接受,并且拒绝所有冲突项目。这个过程会持续工作,直到所有冲突集都被解决为止。

通过将内存池里所有被拒绝的项,替换为被接受的项,网络中的参与者就可以拥有几乎相同的本地状态。结合再有的规范排序规则,这些客户端就可以看到几乎一致的区块。


 


详细规则

安全参数

我们的算法也采用雪崩算法白皮书描述的安全参数,如下:

利用雪崩算法主动协调交易本地状态

发信号支持

客户端应使用以下服务位来表示他们理解协议:

NODE_SNOWGLOBE= (1 << 26)
 
握手

当节点希望提供其采样状态时,它们应该使用适当的服务位给其他节点发送一个连接消息。接收到该消息的客户端应该验证该消息,并且:

1.如果消息是非法的,则禁止其节点
2.如果消息是合法的,则将其节点加入到合作内存参与者之列。

使用币龄抗女巫攻击

使用一组使用币金额乘于区块年龄的UTXO信息,我们称之为“币块”,才能向其他节点发起查询服务,通过该机制可实现抗女巫攻击。如果索要查询服务的节点发出的消息不包含足够的币块阈值,该消息为非法的,并且该节点会被禁止,不能加入Snowglobe内存池中。

初始的币块值设为1440,但需要进一步研究,是否有更合适的值。
 
使用身份和下注(stake)发信号及验证

创建信号

提供查询服务的节点,都必须维护一个secp256k1密钥对,该密钥用于授权

和验证下注消息的身份信息。下注动作是通过下注者使用公钥签署一个包含身份的信息加入连接消息。消息是通过ECDSA签署,使用组成币块的UTXO的公钥和私钥签署。(这一段看不懂,原文如下:Queryable nodes must all maintain an secp256k1 key pair whichis used by queriers to authenticate messages against a stake. Staking is doneby crafting and signing a Joinmessage containingthe Identity public key a list of outpoints controlled by the staker. Thismessage is signed using ECDSA by the Identity private key and by the public keythat controls each UTXO represented by the committed outpoint.)

现在只支持如下UTXO:

· P2PK(Pay-to-Pubkey)
· P2PKH

将来可能支持以下类型:

· 多重签名
· 精心定义的P2SH脚本。

验证

要验证一个连接消息的真伪,及其对应下注的客户端的身份,必须通过将消息的签名移除,并生成规范的序列化。然后验证程序要检查身份签名的正确性。接下来,要在提取公钥的同时,对照匹配输出点。最后,加载每个提交的UTXO,检查它们的类型,检查匹配的公钥是否正确,并确保币块足够大。(这段太复杂了,看不懂,原文是:To validate a Join message and its stake a client must firstgenerate the canonical serialized message by removing the signatures. Then itshould check that the Identity signature correctly signs the canonical message.Next it needs to verify each outpoint signature against its matching committedoutpoint, while simultaneously extracting the public key. Finally it load eachof the committed UTXOs, check their type, check that the matching public key iscorrect, and ensure that Coin Blocks is sufficient.)
 
DAG格式

雪崩算法有效性的核心是DAG(有向无环图),它允许我们通过单个Snowball实例,来接受或拒绝整个链的状态。DAG图的连接性越强,完成所有状态最终确定所需要的Snowball实例就越少,不过,如果DAG图过于复杂,会导致体统效率都会浪费在构造图的边上。

解决方案是使用链中已经存在的所有自然形成的对象边,而不是人为再生成新的。我们通过定义给定顶点,来形成新的边,具体类型取决于如下:

一笔交易会从每一个父交易那里都形成一条边。

一个块,会从它的父块里形成一条边,以及从每一笔被该区块承诺的交易那里形成一条边。
 
冲突集

区块中每一笔存在于冲突集的交易,都要基于互斥排除点。这些要点如下:

· 一个交易的冲突集是所有使用相同UTXO花费的交易
· 一个区块的冲突集是所有相同高度的区块,包含了相同交易,或者包含了相冲突的交易

解决冲突集的过程是最终接受一个项的过程,同时意味着拒绝了所有其他项
 
循环采样

每一个客户端都应该持续为未完成的项进行循环采样,每次循环最多可以达到4096个请求。每次重复采样,客户端们应该随机选择要查询的节点,发送一个项目请求,并且通过投票累加器来返回投票结果。通过伪代码来描述如下:

while items= getItemsToSample():
  peer = getRandomPeer()
  votes = query(peer, items)
  accumulateVotes(votes)

投票累加器

投票有三个选项值:no(0),yes(1),或者弃权(2)。通过将它们放入Snowball投票累加器来处理,该累加器保持最后K张选票,接受状态,以及雪崩白皮书里描述的对该状态的可信度。参数选择为k=8, 关键词: 雪崩算法  共识机制  

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/28157

联系我们

aliyinhang@gmail.com