其实并没有什么比特币,我们在交易所里或者钱包里显示的比特币余额其实是UTXO。那到底什么是UTXO呢,UTXO的全称为UnspentTransactionOutput,翻译过来就是未被花费的交易输出。好像觉得还是不太理解。。。。?在比特币区块链账本上记录了一笔一笔的交易,每一笔交易都有若干个交易输入(转账者),也就是资金来源,同时也有若干个交易输出(收款者),也就是资金去向。每一笔交易都要花费一笔输入,产生一笔输出,而产生的这笔输出,就是UTXO。举个简单的例子:A地址下有1个btc,A要把1个btc转给B,则账本上交易的输入就是A,输出为B的地址,这时脚本会校验A地址是否有1个btc(余额都不够怎么会给你转),即在某一笔输出(UTXO)中查询到了A确实有1个btc。所以A可以作为输入转给B一个btc,这时就有一笔价值1个btc的输出指向B地址,直到B进行下一次转账前这笔交易都是B未被花费的输出(UTXO)。后续B要转给C时又重复A转B的操作。再来一个复杂一点的例子:第一个交易#1001号是张三挖矿所得的coinbase交易,coinbase交易就是挖矿交易,当矿机找到一个合格的区块后,它就获得一个特权,能创造一个coinbase交易,并且把交易输出写上自己的地址,张三通过挖矿获得了12.5个btc,即价值12.5个btc的UTXO指向的是他的地址。第二个交易张三转账2.5个btc给李四,张三就发起了#2001号交易,资金的输入为#1001(1),而在本次交易输出的UTXO中,把2.5个btc的收款人地址为李四。但是这笔交易必须把上一个UTXO全部消耗,所以还剩下的10btc的交易输出的收款地址为张三自己。第三个交易张三和李四一起转给王五5个btc,张三或李四发起#3001号交易,输入来源有两个部分,一个是#2001(1)和#2001(2),输出为王五的收款地址。并且张三还剩下的7.5个btc输出到自己的地址。后续王五如果需要花费他的5个btc,输入就需要为#3001(1)一笔交易数据例子如上图是一笔交易,有多个输入TxIn和多个输出TxOut。prevhash,表示该输入是在哪个交易hash输出的。index,表示在prevhash的那个交易的索引。btc,到账btc个数pkScript,即publicKeyScript,锁定脚本,花费该UTXO时需要执行。第一行挖矿收入交易通常被称为coinbase,它没有输入,所以TxIn的hash被标记为00000...000,index为ffff。从第二行开始都是一些转账交易,任何一个TxIn都会唯一追溯到区块链上在本区块之前的某个交易hash,以及索引。上图通过交易hash和索引(从0开始),即可唯一确定一个未花费的交易输出,这样每一个TxIn都和之前某个TxOut关联起来。其中pkScript为锁定脚本,使用该UTXO时需要验证通过该脚本才能花费这笔UTXO。验证交易脚本是如何进行验证的?总结比特币并不是基于账户的方案,而是基于UTXO方案。这个和传统银行账户的思维完全不一样。张三拥有10个btc,其实就是当前区块链账本中,有若干笔交易的输出(UTXO)收款人都是张三的地址,而这些UXTO的总额为10。这个地址一共收了多少UTXO,则是要通过比特币钱包代为跟踪计算,所以钱包里显示的余额其实是有多少价值btc的输出指向你的地址。作者:暴走的K哥哥原文链接:https://www.jianshu.com/p/7071e68c5262
原文链接:OmniLedger:ASecure,Scale-Out,DecentralizedLedgerviaSharding摘要设计一个可与中心化支付系统(比如Visa)的性能对标的安全无权限的去中心化账本(区块链)是一件极具挑战的事。大多数现存的去中心化账本是不具有高性能或者靠吞吐量的,比如通过增加验证者数量提高处理性能。而那些具有高性能的,要么损失安全性,要么偏中心化方案。我们提出OmniLedger,一种新型的高性能的去中心化账本,它具有无权限性,又保留了长期的安全性。它通过使用一种抗预测(bias-resistant)的公共随机协议(abias-resistantpublic-randomnessprotocol)来选择具有统计代表性的大型分片来处理交易,以及通过引入一种有效的跨分片提交协议(anefficientcrossshardcommitprotocol)来原子性的处理影响多分片的交易,从而保证了安全性和正确性。OmniLedger同时通过在分片内进行并发交易处理优化了性能,通过集体签名的状态区块以及对小额交易进行低延迟的“trust-but-verify”方式验证缩减了账本大小。我们实验原型的一个评估显示OmniLedger的吞吐量与活跃的验证者数量是线性扩展的,可支撑Visa级别的交易量,同时可以在2秒内对一般交易进行确认。1.介绍去中心化账本(DL)关于总交易量和独立处理交易的参与者数量之间的可扩展性问题,是一个被主流认可的主要挑战问题,特别是在与安全性和去中心化挑战对比的时候。有许多办法展示了不同的安全性和性能权衡[10],[11],[21],[32],[40]。比如,通过替换中本聪共识(Nakamotoconsensus)[36]为PBFT共识[13],可以提高吞吐量的同时降低交易延迟[1][32]。这些办法仍然要求所有验证者或者共识组成员冗余性的验证和处理所有交易,因此系统总的交易处理容量是无法通过增加参与者而线性增加的,反而事实上会由于协调开销增加而逐渐降低性能。建立可”横向扩展“数据库的成熟有效的方式是实现分片机制(Sharding)[14],通过将状态切分到多个分片由不同子集的验证者进行并行处理。分片可以为每个验证者降低交易处理负担,同时又可以按照参与节点数量同比例增加系统的整体处理容量。然而现有的对实现分片式去中心化账本的建议,要么放弃无权限去中心化[16],要么引入新的安全假设以安全换性能[34],如图1所示(在第2和第4章详细阐述)image.png我们介绍的OmniLedger,是第一个提供可以与中心化支付系统(Visa)竞争的”横向扩展“交易处理能力,同时不以损失安全性或无权限去中心化为代价。为了实现这个目标,OmniLedger面临3个关键正确性和安全性挑战。首先,OmniLedger必须通过可抵御无权限女巫攻击的PoW[36][38][32]或PoS[31][25]机制来周期性地选择具有统计性代表的验证者分组。其次,OmniLedger必须可以通过周期性地形成足够大而且抗预测(bias-resistant)的分片以保证任何分片在长时间受损的概率可以忽略不计。最后,OmniLedger必须可以正确地原子性的处理跨分片交易,或者影响多个分片状态的交易。为了通过PoW选出代表性的验证者,OmniLedger建立在ByzCoin[32]和混合共识(HybridConsensus)[38]之上,使用最近PoW区块矿工的滑动窗口作为其验证者集。为了支持更加节能的替代方案,即直接基于PoS来分配共识组成员,OmniLedger建立在Ouroboros[31]和Algorand[25]之上,采用在一个先前的验证者分组中运行一个公共随机协议或加密抽签协议从账本的当前持币人分布中提取一个后续的验证者分组。为保证代表性验证者的抽取是可扩展和强抗预测性的,OmniLedger采用RandHound[44]协议,这是一种为这种目的在标准t-n阀值假设下服务的协议。适当的利用RandHound为OmniLedger解决第二个安全性挑战提供了依据,即安全地为分片分配验证者,以及当更多验证者介入时周期性地进行循环分配。基于第四章的分析,OmniLedger引入足够大的分片来保证经过几年的运行任何分片被损害的概率可以忽略不计。最后,为保证即使影响多个分片状态的交易进行原子性的提交或取消,OmniLedger引入了Atomix,一种2阶段客户端驱动的"锁/解锁"协议,用来保证客户端可以要么在跨分片完全提交一个交易,要么获取”拒绝证据“来取消或解锁被部分完成交易影响的状态。除了解决上述的关键安全性问题,OmniLedger也引入了几种我们发现的有助于实现其可用性目标的性能和扩展性改进方案。OmniLedger的共识协议,ByzCoinX,增强了ByzCoin中的PBFT共识,通过接受一种更加可靠的组通信模式可使其在处于拜占庭DoS攻击时保证性能。为帮助新的或长期掉线的矿工在不需要下载整个历史数据的情况下赶上最新的账本状态,OmniLedger接纳了经典的分布式检查点原则(classicdistributedcheckpointingprinciples)[20]来定期生成一致的状态区块。最后,为降低通常情况下的交易延迟,比如小额交易,OmniLedger支持可选的"trust-but-verify"验证方式,即在较小的第一层的验证者快速处理这些交易,然后把它们提交给更大但更慢的第二层来重新验证第一层交易的正确性以及长期的安全性。这种2层解决方案保证任何第一层的不当行为可以在数分钟内被检测,然后以损失押金的形式进行严厉地惩罚。客户可以等待两层处理完大额交易以保证最大的安全性,或者可以只等待第一层处理完小额交易。为评估OmniLedger的效果,我们用Go语言实现了一个原型版本在商用服务器上运行(12核VMonDeterlab),我们的实验结果显示OmniLedger可以按照验证者数量线性横向扩展,在具有12.5%恶意节点的1800个广泛分布的的主机环境上实现了10秒共识延迟下达到了6000tps。而且,将OmniLedger以”信任但验证“的二层验证模型下部署时,在具有25%恶意节点时实现了4秒第一层延迟的2250tps吞吐量。最后,一个具有长达一个月陈旧状态视图的比特币验证者会产生40%的带宽流量,由于区块同步。(Finally,aBitcoinvalidatorwithamonth-longstaleviewofthestateincurs40%ofthebandwidth,duetostateblocks。这句是何意?不太理解)总的来说,本文做出了以下贡献:介绍了第一个提供水平扩展的不以损害长期安全性或无权限去中心化的去中心化架构。介绍了Atomix,一种原子提交协议,实现跨分片的原子提交交易功能。介绍了ByzCoinX,一种针对DoS攻击时增加性能和健壮性的BFT共识协议。介绍了状态区块(stateblocks),在OmniLedger上部署以减小存储空间和更新开销。介绍了信任但验证二层模型(或者叫乐观验证)来降低小额交易延迟。2.知识背景A.ByzCoin的可扩展拜占庭共识OmniLedger建立在ByzCoin中的拜占庭共识方案之上,因为它在上千个共识组成员里可以有效扩展。为了使例如PBFT[13]之类的传统共识协议更加可扩展,ByzCoin利用集体签名(collectivesigning)或群签名(CoSi)[45],一种可扩展的加密原语来实现多重签名。ByzCoin采用组播树(multicasttrees)分发区块以提高性能,但是为了容错却回退使用了扩展性较差的星型拓扑。虽然ByzCoin的共识具有扩展性,但是其总体的处理容量却没有随着参与节点数量而增加,所以它是不能横向扩展的。B.交易处理和UTXO模型去中心化账本从区块链或一条包含交易的完全有序区块继承了现在的系统状态。基于其简单性和可并行性,OmniLedger接受UTXO模型来代表账本状态。在这个模型里,一个交易的输出创建新的UTXO并授予其信用,交易的输入则完全花费已存在的UTXO。在新的全节点启动时,会同步抓取整个账本并建立合法UTXO的数据库以便用于后续验证新区块是否合法。这个UTXO模型是被比特币[36]引入的并且已经被其它去中心账本系统广泛认可。C.安全的去中心化随机数生成器RandHound[44]是一个可扩展的安全的多方计算(MPC)协议,在拜占庭环境里可提供无偏见的、去中心化的随机性。RandHound假设存在一个外部负责任的客户,他想从一大群半信任化的服务器中获取可证明的随机性。为了产生随机性,RandHound将服务器组拆分更小的组,并创建一个公开可验证的先提交后揭示(commit-then-reveal)的协议[43],该协议采用鸽笼原理在包括至少一名诚实参与者贡献时来证明最终的随机数,因此完美地实现了对RandHound输出的随机化。加密抽签(Cryptographicsortition)[25]用来根据验证者权重函数对验证者选择一个子集。为了使验证者能够证明他们属于某个选中的子集,他们需要一个公钥和私钥对,(pki,ski)。抽签通过一个VRF(verifiablerandomfunction:可验证随机函数)实现:输入x,然后返回一个随机hash(l-bit长的字符串),和一个基于ski的证明π。这个证明π可使任何人知道用pki去验证该hash对应于x。D.抗女巫攻击的身份认证(Sybil-ResistantIdentities)不像有权限的区块链[16]验证者都是已知的,无权限的区块链需要处理女巫攻击[19]的潜在威胁以保证安全。比特币(Bitcoin)[36]建议使用PoW工作量证明,其矿工(验证者)创建一个合法区块需要消耗昂贵的计算(对一个nonce进行循环迭代,对区块头hash进行暴力破解使其以特定数量的0开头)。Bitcoin-NG[21]使用同样的PoW技术以产生抗女巫攻击的身份。PoW机制本身有一些问题,比如浪费电力以及导致矿池重新中心化的事实。其它的抵抗女巫攻击的方法还有采用诸如PoS[31][25]、Proof-of-Burn(PoB)[46]、Proof-of-Personhood[8]等可以克服PoW的问题,并且可以兼容ByzCoin的身份区块链,当然也兼容OmniLedger。E.先前的分片式账本:ElasticoOmniLedger和先前探讨过的在无权限账本上实现分片的Elastico是很接近的。在每一轮,Elastico利用PoW哈希中最低比特位来分发矿工给不同的分片,然后每个分片运行PBFT[13]来达到共识,接着领导分片(leadershard)验证所有的签名,然后创建全局区块。OmniLedger解决了几个Elastico未解决的挑战。首先,Elastico相对小的分片(比如实验中每个分片100个验证者),在低于25%恶意节点时会产生每分片每区块2.76%的高失败率,这在PoW系统中是不能被容忍的。在16个分片里仅仅6个周期就有高达97%的失败率。第二,Elastico的分片选举不是强抗偏见的,因此矿工可以选择性的忽视PoW来得到特定的结果[7]。第三,Elastico不能保证跨分片时的原子性交易,当另一个分片拒绝交易时,资金会永久锁定在一个分片中。第四,验证者总是在切换分片,导致它们需要保存全局状态,这可能会阻碍性能,但可以为自适应对手提供更强的保障。最后,交易确认的延迟跟比特币差不多(10分钟),这和OmniLedger的可用性差远了。3.系统概要本章主要陈述OmniLedger的系统、网络和威胁模型,设计目标,和路线图。A.系统模型我们假设:有n个验证者来处理交易和保证系统状态的一致性;每个验证者i有公钥和私钥对(pki,ski),我们通过pki来识别身份i。验证者被均匀地分配到m个分片中。分片j的参数在分片策略文件中汇总(shard-policyfile)在全局的重配置事件(即验证者到分片的重新分配)中,时间周期e表示一个固定的时间(比如1天)一个周期的时间以r轮进行表示,这个在不同的分片不需要保证一致在每一轮中,每个分片处理从客户收集到的交易假设验证者可以通过任务抗女巫攻击机制建立身份体系,并且提交到身份区块链;为参加e时代的验证者必须在e-1时代进行注册。这额身份如何加入到身份区块链,请参考2-D部分。B.网络模型对于底层网络,我们假定和其它网络一致[31][34][36]。特别地,我们假定:a)诚实验证者的网络是良好连接的;b)诚实验证者的通信通道是同步的,也就是说一个诚实验证者广播一个消息,那么所有验证者都能在一个已知的最大延迟∆[39]内接收到该消息。然而由于∆以分钟计数,我们不能在时间周期内使用它,因为我们的延迟目标是以秒为单位。因此,在一个时间周期内的所有协议使用乐观地部分同步模型[13],而∆则用来进行诸如身份创建和分片分配之类的缓慢操作。C.威胁模型我们表述拜占庭验证者的数量为f,并假定:n=4f,也就是在特定情况下最多25%的验证者可能是恶意的,跟之前其它的去中心化账本类似[21][32][34]。这些恶意节点可以任意操作,比如他们可能拒绝参与或者串通来攻击系统。剩下的验证者都是诚实的并坚定地遵守协议要求。我们进一步假定对手在时间周期顺序上是温和适应的,比如他可以尝试串通验证者,但这需要花费一些时间使破坏性尝试起作用。我们再假定对手是有计算边界的,那么加密原语是安全的,并且计算Diffie-Hellman问题是非常困难的。D.系统目标OmniLedger在去中心化、安全和扩展性方面有以下主要目标:完全去中心化-OmniLedger不会有任何单点故障问题。(比如信任的第三方机构)分片的健壮性-每个分片都可持续正确地处理分配给它的交易。安全的交易-分片内或跨分片的交易都能原子性的提交确认或最终取消。横向扩展-OmniLedger期望的吞吐量随着参与验证者的数量而线性增加。更低的存储开销-验证者不需要存储完整的交易历史,而仅仅需要存储汇总分片状态的定期计算的参考点。低延迟-OmniLedger为交易确认提供更低的延迟。E.设计路线图本节介绍SLedger,一种稻草人去中心化系统,我们用它来概述OmniLedger的设计。下面我们来描述SLedger的一个时间周期(epoch),以及显示其如何从周期e-1转换到周期e。(备注:在软件开发中,稻草人是指一个粗略的计划或文件,是项目演进的起点。)我们从安全验证者分配到分片开始。允许验证者选择他们想要验证的分片是不安全的,因为攻击者可以将所有其验证者集中一个分片中。因此,我们需要一个随机源来保证一个分片内的验证者将成为系统总体的一个样本,将具有相同比例的恶意节点。SLedger操作可信随机信标,使其在时间周期e内广播一个随机值rnd[e]给所有参与者。想从时间周期e开始参与SLedger的验证者,必须先在一个全局身份区块链上注册身份,在时间周期e-1内他们通过抗女巫攻击机制创建他们身份,然后在八卦网络(thegossipnetwork)上在时间周期e-1结束前以最多的∆值,连同相应的证据进行广播。时代e以由rnd[e-1]随机数选举的一个领导者开始,该领导者向从已经注册且活跃的验证者们请求一个区块上的(BFT)签名,这个区块具有已证明被创建的所有身份信息。如果这些验证者如果有2/3的比例拥护该区块,它就变成合法的,然后有领导者将该区块挂入身份区块链。然后,所有注册的验证者们使用rnd[e]来决定将自己分配到SLedger中的其中一个分片上,然后从相应分片的分布式账本中同步启动内部状态。那么,他们就准备好开始使用ByzCoin的共识机制来处理交易了。随机的分片分配机制保证了在一个给定分片中恶意和诚实验证者的比例与在所有验证者中的恶意和诚实的比例是最有可能相接近的。SLedger已经给OmniLedger提供了类似的功能,但是有几个有意义的安全限制。首先,随机信标是一个可信任的第三方机构。在每个时代开始时的全局重配置期间,系统会停止处理交易,直到有足够的验证者已经启动他们的内部状态。这里不支持跨分片交易。SLedger设计的性能表现也不佳,由于:第一,ByzCoin的失败处理机制,当验证者失败时,它的性能会恶化。第二,验证者面临很高的存储和启动开销。最后,SLedger不能提供实时确认和高吞吐量。为解决这些安全问题,我们在第4章介绍OmniLedger的安全设计。在4-节,我们删除了可信任的随机数信标,并展现验证者如何自主地将RandHound与采用加密抽签方式的基于VRF的领导选举进行安全分片。在4-B节,我们展现如何在跨时代时安全地处理将验证者分配给分片,同时保证持续的处理交易。在4-C节,我们展示Atomix,一种在拜占庭环境下自动处理跨分片交易的新型的二步原子提交协议。为解决性能问题,我们在第5章介绍OmniLedger的性能和可用性设计。在5-A节,我们介绍ByzCoinX,一个ByzCoin的变种,可利用更加健壮的通信模型来高效地处理分片内部的交易,即使一些验证者失败了;可在交易级别解决依赖性以实现更好的区块并行化。在5-C节,我们介绍状态区块(stateblock),其汇总了一个时代的分片状态,可为验证者缩减账本以降低存储和启动开销。在5-D节,我们展示通过利用信任但验证的分片内交易验证方式(anintra-shardarchitecturewithtrust-but-verifytransactionvalidation),如何在不牺牲安全性或吞吐量的情况下进行乐观实时的交易确认。图2阐述了OmniLedger的总体安全架构。image.png4.OmniLedger:安全性设计A.采用抗偏性分布式随机数进行分片(ShardingviaBias-ResistantDistributedRandomness)为使在不用可信任随机数信标[16]或绑定协议到PoW上[34]等方式产生可安全分片的随机数种子,我们依赖于一种由验证者们共同执行的分布式随机数生成协议。我们要求这个分布式随机数生成协议提供无偏性、不可预测、第三方可验证、和可扩展性,有多种建议参考[7][28][44]。第一种方法依赖比特币,而另外具有很多相同的设计;我们关注RandHound[44]是因为它有更好的文档和开源实现。因为RandHound依靠领导者来协调协议运行,我们需要一个合理的机制来从验证者中选举一个出来。如果我们使用确定性方法来执行领导人选举,那么攻击者通过拒绝运行协议,在最坏的情况下可能达到f/n的失败率,在我们的模型中会有高达n/4的失败率。因此,领导选举机制必须是不可预测和无偏性的,但当我们在第一次使用RandHound时,就碰到了先有鸡还是现有蛋的问题。(因为我们需要RandHound来产生随机数,但是RandHound自己又需要随机选举的领导者,那么第一次运行时,这个随机领导者怎么产生?)为了克服这个困境,我们将RandHound与基于VRF的领导选举算法[44][25]向结合。e时代开始,每个验证者i计算一张门票:ticket[i,e,v]=VRF[ski]("leader"||config[e]||v)config[e]表示包含e时代所有合理注册的验证者的配置信息(保存在身份区块链中(identityblockchain))v是一个视图计数(viewcounter)验证者们开始相互传播他们的门票,持续一个时间∆,之后他们锁定一个他们迄今看到的最小的合法门票,并接收该门票对应的节点为运行RandHound协议的领导者.如果被选举的节点在另一个时间∆内启动RandHound失败,那么验证者们认为本次运行失败,并在本时代之后的时间将该验证者排除在外,即使他后来上线了。这种情况下,验证者们增加视图计数值为v+1,重新运行选举(抽奖)。当验证者们成功完成了RandHound的运行,并且领导者已经成功广播了rand[e](携带正确性证明),n中的每个合理注册的验证者就可以先验证正确性,然后用rand[e]来计算1,...,n的π[e]排列,再将结果分配到大小都为m的水桶里(bukets),因此决定将哪些节点分配到哪个分片。安全论据:我们进行以下观察,以非正式的方式论证上述方法的安全性。每个参与者在e时代的每个视图v只能产生一个合法的门票,因为基于VRF的领导选举只能在身份区块链中合法的身份已经固定时才能开始。只要非串通节点的门票对应的私钥(ski)是保密的,VRF的输出就是不可预测的。因此最后抽奖的结果就是不可预测的。同步时间∆保证诚实节点的门票可以被所有其它诚实节点接收看到。如果攻击者赢得抽奖,他可以决定遵循并运行RandHound协议,或者让其失败,这样该节点就会在本时代接下来的时间被排除在外。在成功运行RandHound之后,攻击者首先掌握了随机数,进行分片分配,但是他能得到的好处很小。攻击者可以选择选择合作并发布随机值,或者保留它以期望再次赢得抽奖,并获得最符合他要求的分片分配任务。但是,一个攻击者抽奖连续赢得a次的的概率是按照公式image.png指数级下降的。因此,经过几轮重新抽奖,诚实节点以高概率赢得抽奖,然后协调分片。最后,我们认定攻击者不能在多轮抽奖中获得随机数,然后选择最符合其利益的那个,因为验证者只接受符合视图计数v的最新随机值。在附件B中,我们展示OmniLedger如何扩展概率性地检测预期的∆不存在,以及如何回退协议保证安全。B.时代转换时保证可操作性我们知道,在每个时代e,SLedger改变验证者到分片的分配时,会导致一段空闲期,这段时间系统不能处理交易知道足够的验证者完成启动。为保持转换阶段的可操作性,OmniLedger在每个时代逐渐地将新的验证者切换到新的分片。这可以保证剩下的操作者可以持续提供服务给客户,同时新加入的验证者同步进行启动。为了实现这种持续的操作,我们可以转移出最多1/3分片大小(约为n/m)的验证者数量,转出数量越多,剩余的诚实节点不足够达到共识的风险就更高,而且新节点时启动的对网络的压力也越大。为平衡临时失去活性的可能性,OmniLedger中验证者分片分配按照以下步骤工作。设置参数k<1/3*n/m,作为批次转出的数量(即特定时间转移出分片的验证者数量)。针对OmniLedger,我们决定设置k=log(n/m)然后针对每个分片j,我们获得一个种子H(j||rnd[e])来计算分片验证者的排列π[j,e],并且我们指定批次排列。同时计算另一个种子H(0||rnd[e]),来置换和分散新加入e时代的验证者,并定义按照什么顺序进行(大小也为k)。定义好随机排列后,每批次等待时间∆再开始启动以保证分散负担到网络上。当一个验证者准备好后,他发送一个声明给将其转入分片的分片领导者。安全论据:在转换阶段,我们在每个分片保证BFT共识的安全性,因为在每个分片里总是至少有2/3*n/m数量的诚实验证者愿意参与共识。我们使用时代随机数rnd[e]来获得批次排列,针对自适应攻击者我们保持分片配置是一个移动目标。只要有2/3*n/m诚实和保持更新的节点,分片活性就可以保证。反之如果转换期间未达到法定人数(新批次的诚实验证者还没更新完成),分片活性会暂时不可用直到新验证者更新完成。C.跨分片交易为了启用跨分片的价值转移以实现分片的互操作性,在任何分片型账本系统中支持安全的跨分片交易都是至关重要的。我们期望在传统模型中大多数交易是跨分片的,其中UTXO被自由的分配给分片进行处理[16][34]。具体参考附件C。针对跨分片交易的一个简单但不完善的稻草人方式,是将一个交易同步地发送给多个分片处理,因为有些分片会提交交易,其它的会取消。这种情况下,这些UTXO在接受交易的分片中被丢失,因为没有一种直接的方式可以回退半提交的交易,在没有添加可利用的竞争条件时。为解决这个问题,我们提出一种新型的拜占庭分片原子提交协议(ByzantineShardAtomicCommit(Atomix))来自动处理跨链交易,保证每个交易被完全提交或最终取消。目的是保证跨分片交易的一致性,以阻止双花或者未花费的资金被永久锁住。在分布式计算里,这个问题被称为原子提交[47]或原子提交协议[27][30]被部署到诚实但不可靠的处理器上。在OmniLedger上部署这类协议是不必要的复杂,因为分片们都是集体诚实的,而且不会无限奔溃,并运行BFT共识。Atomix通过锁和解锁过程改进了稻草人方法。我们故意保持分片逻辑的简单性,并且通过授权客户负责驱动解锁过程,同时当特定交易在提交处理后停滞时允许其它方(验证者或其它客户端)来填写客户端,从而使分片与分片之间的直接通信变得不必要。Atomix使用UTXO状态模型,整体参考2-B,它可使下面的简单而高效的三步协议成为可能。另外可参考图3.初始化:客户端创建一个跨分片交易(cross-Tx),输入UTXO来自输入分片(IS),输出创建新的UTXO来自输出分片(OS)。客户端八卦(cross-Tx)交易,并最终到达所有的(IS)。锁定:所有输入分片(IS)与(cross-Tx)进行关联。首先,检查输入是否可以被花费,每个(IS)领导者检查本分配内的交易。如果交易合法,领导者在状态上标记这个输入被花费,在分片账本上记录交易日志,然后八卦接受证明(proof-of-acceptance),这是一种包含本交易的区块的被签名的默克尔树证明。如果交易被拒绝,领导者创建一个相似的拒绝证明(proof-of-rejection),其中特定比特位来表示接受或拒绝。客户端可以利用每个(IS)账本来检查其证明以确认该交易确实被锁住。当所有(IS)已经处理了锁请求,客户端就具有足够的证明来提交交易,或取消交易并回收任何锁定的资金。解锁:根据锁阶段的结果,客户端可以提交交易或取消交易。解锁提交:如果所有的(IS)领导者都返回了接受证明,那么对应的交易就可以被提交。客户端(或超时后为其它实体比如IS领导者)创建并八卦一个解锁提交交易(unlock-tocommittransaction),该交易由每个输入UTXO的锁交易和接受证明组成。相应的,每个介入的(OS)验证交易并包含进下一个其分区账本区块中以更新其状态,并使新资金可被花费。解锁取消:然而如果只要有一个(IS)返回了拒绝证明,那么该交易就无法提交,必须被取消。为了回收上阶段被锁住的资金,客户端(或其它实体)必须请求介入的(IS)解锁特定的交易,通过八卦一个解锁取消交易(unlock-to-aborttransaction),其中包括至少一个输入UTXO的拒绝证明。输入分片(IS)领导者接收到解锁请求后,会进行类似的步骤并标记原先的UTXO重新可花费。image.png我们评论一下,虽然OmniLedger专注在UTXO模型上,但是Atomix可以被扩展到其它的具有锁机制的系统,其中对象是长期活性和保存状态的。(比如智能合约[48],请参考附件D)。安全论据:下面我们进行非正式地讨论前面陈述的Atomix的安全性,主要基于下面的观察。基于我们的假设,分片是诚实的,不会失败,最终都收到所有消息并达到BFT共识,那么所有分片都忠诚地处理合法交易;如果所有输入分片返回接收证明,那么每个输出分片都进行解锁提交;即使只有一个输入分片返回拒绝证明,那么所有输入分片都解锁取消;即使只有一个输入分片返回拒绝证明,那么没有输出分片需要解锁提交。在Atomix中,每个cross-TX会被提交或取消。基于(1),每个分片只返回一个回应:接受证明或拒绝证明。因此客户端用后所需数量的证明时,那么针对每个输入UTXO只会拥有接受证明或拒绝证明,而不会两者同时拥有。在Atomix中,没有cross-TX会被双花。如上所示,跨分片交易都是原子性,并且只被分配给专门负责它们的特定分片。基于(1),被分配的分片不会对同一个交易处理两次,没有其它分片会进行解锁提交。在Atomix中,如果一个交易无法提交,那么锁定的资金会被回收。如果一个交易无法提交,说明至少有一个分片返回了拒绝证明。当所有的输入分片解锁取消后,所有资金重新可用。我们说,资金不会自动回收,客户端或其他实体必须启动解锁中止过程。虽然这种方法存在一种风险,就是如果客户端无限崩溃了,他的资金就被锁住了,但是它实现了不需要分片之间直接通信的具有最少逻辑的简化协议。客户端循环崩溃和客户端丢失它的私钥是一样的,会阻止他花费响应的UTXO。而且,系统中的任何实体,比如交易所中收费的验证者,可以为客户端填写一个解锁交易,因为所有的信息都是八卦过的。(备注:这里不太理解,客户端发起的跨链交易被锁后,系统中其它实体怎么帮助实现解锁?)为保证更好的健壮性,我们可以指定具有最小输入UTXO的分片成为协调器来负责驱动创建解锁交易的执行。因为一个分片领导者有可能是恶意的,f+1个分片中的验证者需要发送解锁交易来保证所有交易最终被解锁。解锁交易的大小:在Atomix中,解锁交易会比普通的交易更大,由于相应的输入UTXO的证明需要被包含。OmniLedger依赖ByzCoinX来处理每个分片内的交易。当分片的验证者对包含已提交交易的区块达成一致时,他们产生一个集体签名,该签名的大小与验证者的数量无关。这个重要的特性可以使我们保持Atomix证明足够短,即使每个交易的合法性都是通过所有输入UTXO的签名区块被检查。如果ByzCoinX不使用集体签名,解锁交易的大小是不切实际的。比如,具有100个验证的分片一个集体签名只有77字节,而正常签名则有98KB,基于比一个简单交易大小大两个数量级。5.对性能的设计改进本章节,我们介绍OmniLedger的性能子协议。首先我们描述ByzCoinX,一种可扩展的BFT共识,它比ByzCoin具有更好的健壮性和并行性。另外,我们介绍状态区块(stateblock),以实现快速启动和降低存储开销。最后我们提出一种可选的“信任但验证”的二层验证机制来对小风险交易进行实时确认。A.拜占庭故障下的容错原先的ByzCoin设计提供了良好的扩展性,部分归咎于使用了组播树通信模式。长时间维护这样的通信树是非常困难的,因为它们很容易受到故障的影响。在失败的情况下,ByzCoin会回退到更加健壮的全方位通信模式,类似于PBFT。因此,共识性能显著恶化,攻击者可以利用这个弱点来阻碍系统性能。为实现OmniLedger更好的容错,又不采用PBFT全方位的通信模式,我们引入ByzCoinX作为一种新的通信模式,代价是为了健壮性牺牲掉一些ByzCoin的高性能。方法是通过将共识组内的消息传播机制更改为类似于两级树。OmniLedger在一个时代的设置期间,产生的随机数不仅用来验证者到分片的分配,同时也将验证者分配给分片内的相应组。组的数量g,其中通过考虑保存在分片策略文件中的分片大小可以导出最大的组大小。在ByzCoinX的开始轮次中,协议领导者从每个组中随机地选出一个验证者作为组领导者,其负责管理协议领导者与各小组成员之间的通信。如果组领导者在一个预设时间内没有回复,协议领导者重新随机选择一个组领导者来代替失效的那个。一旦协议领导者接收到超过2/3的验证者认可,他就马上进入协议的下一步。如果协议领导者失效,所有验证者发起一个类似PBFT的视图改变步骤。(备注:这里的协议领导者是指分片内的领导吗?怎么产生的?)B.并行区块提交我们现在展示ByzCoinX如何在UTXO模型中进行并行区块提交,通过仔细分析和处理交易之间的依赖性。我们观察到没有相互冲突的交易可以被安全地并行处理。为区分冲突的交易,我们需要分析交易之间可能的依赖性。定义tx[A]和tx[B]表示两个交易,那么两种情况需要被小心处理:tx[A]和tx[B]同时花费了相同的UTXOtx[A]创建的一个交易输出被tx[B]作为输入进行花费(或相反)为解决问题1),两个交易只有其中一个才能被提交为解决问题2),tx[A]需要比tx[B]优先提交,也就是说tx[B]所在区块必须依赖tx[A]所在的区块。所有不包括以上两种情况的交易都可以被安全地并行处理。特别是,我们说信任相同地址的交易不会产生冲突,因为他们产生不同的UTXO。为捕获并发处理的区块,我们采纳一种基于区块的有向无环图(blockDAG)[33]作为数据结构,其中每个区块都有多个父区块。ByzCoinX协议领导者强制每个挂起的区块包含没有冲突的交易,并通过添加当前区块中交易所依赖的上个区块的hash来捕获UTXO依赖性。为减少这类hash的数量,我们注意到UTXO依赖性是可传递的,这使得我们可放宽必须直接捕获所有UTXO依赖性的要求。相反,特定的区块可以简单添加反向指针到一个区块集,可传递性的捕获所有依赖性。C.分片账本削减现在我们来解决不断增长的账本问题,以及由此导致的新验证者启动开销过大的问题,这对高性能的去中心化账本尤其紧急。比如,比特币区块链每天增长144MB,目前的总大小是133GB,而下一代VISA级高性能的账本(比如,4000tx/sec和500B/tx)每天就可以产生超过150GB。为了使那些经常重新分配分片的验证者减小存储和启动开销,我们引入状态区块(stateblocks),它和PBFT[13]中的固定检查点很类似,就是汇总分片账本的全部状态。为了在e时代对分片j创建状态区块sb[j,e],分片的验证者执行一下步骤:在e时代结束时,分片的领导者将UTXO保存到一个排序的默克尔树,并将树根哈希存入sb[j,e]区块头部。然后分片验证者对sb[j,e]区块头部运行共识(注意每个验证者都可以构造相同的排序默克尔树进行验证)。如果共识成功,领导者将通过的区块头保存进分片账本中,使sb[j,e]成为e+1时代的创世区块。最后,sb[j,e-1]区块主体中的UTXO可以被安全的丢弃。为了创建交易证明,我们保留e时代的正常区块,直到e+1时代结束。因为OmniLedger的状态是拆分到多个分片的,并且我们仅在分片账本中保存状态区块的头部,客户端通过提交一个交易被提交的区块的包含证明不能向其它实体证明一个过去交易的存在。我们解决这个问题通过移除客户端保存交易存在证明的责任。在e+1时代期间,客户端可以使用e时代的常规区块和状态区块来生成e时代已验证交易的存在证明。对于给定交易tx的这种证明包含对e时代提交交易'tx'的常规区块B的默克尔树包含证明,以及时代结束时的状态区块sb[j,e]和区块B的顺序区块头。为减小这些证明的大小,状态区块可包含多个多跳反向指针指向类似skipchains[37]的中间常规区块的头部。最后,如果我们天真地去实现状态区块的创建,它会阻碍时代的启动,因为直到sb[j,e]已经被写入账本交易才开始处理。为避免这种停机时间,e+1时代分片中的所有验证者在时代开始时需要包含一个空的状态区块作为替代,一旦sb[j,e]准备完成,验证者就将其作为普通的区块提交,并指向上一个替代者和sb[j,e-1]。D.可选的"信任但检查"验证image.png如图4所阐述的,在分片数量、吞吐量和延迟之间有一个继承的代价。具有大量的小分片数量可以获得更好的性能,但是对更强大的攻击者提供的弹性更小。因为OmniLedger的设计有利于安全性超过可扩展性,我们悲观地假设一个对手控制着25%的验证者,因此,选择大的分片会以更高的延迟为代价,但保证交易的最终性。然而这个假设不能恰当地反映那些具有频繁使用、延迟敏感但低价值交易的客户的优先级(比如,杂货店支付,购买汽油或咖啡等),他们喜欢交易处理地越快越好。为满足客户的需求,我们增加一种分片内架构(如图4),通过遵循“信任但检查”模型,使乐观的验证者更快地处理交易,提供临时但不太可能改变的交易提交,然后核心的验证者随后再次核实交易以提供最终结果并确保可验证性。乐观验证者按照常规的步骤来决定哪些交易按哪种顺序提交,但是他们会组成更小的分组,甚至可能一个验证者一个组。因此他们实时地生成更小的区块,但是可能很不安全,因为攻击可能会按比例控制较小数量的验证者来破坏交易。结果,一些不合法的交易被提交,但是最终核心验证者会检查所有临时的提交,检测任何不一致和他们的罪魁祸首,然后惩罚恶意验证者,并赔偿被欺诈的客户的损害。这种“信任但检查”的方法在实时处理小额交易时取得平衡,因为验证者不会因为少量的钱进行作恶。e时代开始时,所有验证者采用每个时代的随机数将自己分配到分片中,从对应分片的上个状态区块启动他们的状态。接着,OmniLedger随机分配每个验证者到多个乐观验证者分组或一个核心验证者分组。分片策略文件制定了乐观和核心验证者的数量,以及乐观验证者分组的数量。最后,为保证任何不当行为都被包含在分片内,策略文件还定义了最大的乐观验证交易的数额必须等于验证者的押金或收入。交易被乐观分组首先处理并生成乐观验证区块,这些区块会作为核心验证者的输入进行重新验证,核心验证者会并行运行,并将乐观分组处理后输入区块进行重新组合以显示最大化系统吞吐量。合法的交易会被打包进行最终区块,然后加入账本并最终被包含进行状态区块。然而,当核心验证者检测到不一致性,那么对应乐观验证的交易就会被排除,对非法区块签名的验证者会被识别并追究其责任,通过扣留任何奖励或将其排除在外。我们认为具体的惩罚细节依赖于经济激励方案,不在本文范围内。给予行为不端的最小激励以及对乐观验证安全性的可量化信任(参考图5),客户可以根据需要选择利用实时处理和乐观的最终保证,或等待交易最终确定。image.png6.安全性分析待补充7.实现待补充8.评估待补充9.相关工作待补充10.局限性和未来工作待补充11.结论待补充参考资料I.Abraham,D.Malkhi,K.Nayak,L.Ren,andA.Spiegelman.Solidus:AnIncentive-compatibleCryptocurrencyBasedonPermissionlessByzantineConsensus.CoRR,abs/1612.02916,2016.M.Al-Bassam,A.Sonnino,S.Bano,D.Hrycyszyn,andG.Danezis.Chainspace:AShardedSmartContractsPlatform.arXivpreprintarXiv:1708.03778,2017.M.Apostolaki,A.Zohar,andL.Vanbever.HijackingBitcoin:LargescaleNetworkAttacksonCryptocurrencies.38thIEEESymposiumonSecurityandPrivacy,May2017.Bitnodes.BitcoinNetworkSnapshot,April2017.Blockchain.info.BlockchainSize,Feb.2017.D.Boneh,B.Lynn,andH.Shacham.ShortsignaturesfromtheWeilpairing.InInternationalConferenceontheTheoryandApplicationofCryptologyandInformationSecurity,pages514–532.Springer,2001.J.Bonneau,J.Clark,andS.Goldfeder.OnBitcoinasapublicrandomnesssource.IACReprintarchive,Oct.2015.M.Borge,E.Kokoris-Kogias,P.Jovanovic,N.Gailly,L.Gasser,andB.Ford.Proof-of-Personhood:RedemocratizingPermissionlessCryptocurrencies.In1stIEEESecurityandPrivacyOnTheBlockchain,Apr.2017.E.Buchman.Tendermint:ByzantineFaultToleranceintheAgeofBlockchains,2016.V.Buterin,J.Coleman,andM.Wampler-Doty.NotesonScalableBlockchainProtocols(verson0.3),2015.C.Cachin.ArchitectureoftheHyperledgerblockchainfabric.InWorkshoponDistributedCryptocurrenciesandConsensusLedgers,2016.C.Cachin,K.Kursawe,andV.Shoup.RandomOraclesinConstantinople:PracticalasynchronousByzantineagreementusingcryptography.In19thACMSymposiumonPrinciplesofDistributedComputing(PODC),July2000M.CastroandB.Liskov.PracticalByzantineFaultTolerance.In3rdUSENIXSymposiumonOperatingSystemsDesignandImplementation(OSDI),Feb.1999.J.C.Corbett,J.Dean,M.Epstein,A.Fikes,C.Frost,J.J.Furman,S.Ghemawat,A.Gubarev,C.Heiser,P.Hochschild,W.Hsieh,S.Kanthak,E.Kogan,H.Li,A.Lloyd,S.Melnik,D.Mwaura,D.Nagle,S.Quinlan,R.Rao,L.Rolig,Y.Saito,M.Szymaniak,C.Taylor,R.Wang,andD.Woodford.Spanner:Google’sGloballyDistributedDatabase.ACMTrans.Comput.Syst.,31(3):8:1–8:22,Aug.2013.K.Croman,C.Decke,I.Eyal,A.E.Gencer,A.Juels,A.Kosba,A.Miller,P.Saxena,E.Shi,E.G.Sirer,D.S.an,andR.Wattenhofer.OnScalingDecentralizedBlockchains(APositionPaper).In3rdWorkshoponBitcoinandBlockchainResearch,2016.G.DanezisandS.Meiklejohn.CentrallyBankedCryptocurrencies.23rdAnnualNetwork&DistributedSystemSecuritySymposium(NDSS),Feb.2016.S.Deetman.BitcoinCouldConsumeasMuchElectricityasDenmarkby2020,May2016.DeterLabNetworkSecurityTestbed,September2012.J.R.Douceur.TheSybilAttack.In1stInternationalWorkshoponPeer-to-PeerSystems(IPTPS),Mar.2002.E.N.Elnozahy,D.B.Johnson,andW.Zwaenepoel.ThePerformanceofConsistentCheckpointing.In11thSymposiumonReliableDistributedSystems,pages39–47.IEEE,1992.I.Eyal,A.E.Gencer,E.G.Sirer,andR.vanRenesse.BitcoinNG:AScalableBlockchainProtocol.In13thUSENIXSymposiumonNetworkedSystemsDesignandImplementation(NSDI16),SantaClara,CA,Mar.2016.USENIXAssociation.M.K.FranklinandH.Zhang.AFrameworkforUniqueRingSignatures.IACRCryptologyePrintArchive,2012:577,2012.A.Gervais,G.Karame,S.Capkun,andV.Capkun.IsBitcoinadecentralizedcurrency?IEEEsecurity&privacy,12(3):54–60,2014.A.Gervais,H.Ritzdorf,G.O.Karame,andS.Capkun.TamperingwiththeDeliveryofBlocksandTransactionsinBitcoin.In22ndACMSIGSACConferenceonComputerandCommunicationsSecurity,pages692–705.ACM,2015.Y.Gilad,R.Hemo,S.Micali,G.Vlachos,andN.Zeldovich.Algorand:ScalingByzantineAgreementsforCryptocurrencies.CryptologyePrintArchive,Report2017/454,2017TheGoProgrammingLanguage,Sept.2016R.Guerraoui.Non-blockingatomiccommitinasynchronousdistributedsystemswithfailuredetectors.DistributedComputing,15(1):17–25,2002T.HankeandD.Williams.IntoducingRandomBeasconsUsingThresholdRelayChains,Sept.2016.E.G.S.IttayEyal.It’sTimeForaHardBitcoinFork,June2014.I.KeidarandD.Dolev.Increasingtheresilienceofatomiccommit,atnoadditionalcost.InProceedingsofthefourteenthACMSIGACTSIGMOD-SIGARTsymposiumonPrinciplesofdatabasesystems,pages245–254.ACM,1995.A.Kiayias,A.Russell,B.David,andR.Oliynykov.Ouroboros:AProvablySecureProof-of-StakeBlockchainProtocol.CryptologyePrintArchive,Report2016/889,2016E.Kokoris-Kogias,P.Jovanovic,N.Gailly,I.Khoffi,L.Gasser,andB.Ford.EnhancingBitcoinSecurityandPerformancewithStrongConsistencyviaCollectiveSigning.InProceedingsofthe25thUSENIXConferenceonSecuritySymposium,2016.Y.Lewenberg,Y.Sompolinsky,andA.Zohar.Inclusiveblockchainprotocols.InInternationalConferenceonFinancialCryptographyandDataSecurity,pages528–547.Springer,2015.L.Luu,V.Narayanan,C.Zheng,K.Baweja,S.Gilbert,andP.Saxena.ASecureShardingProtocolForOpenBlockchains.InProceedingsofthe2016ACMSIGSACConferenceonComputerandCommunicationsSecurity,CCS’16,pages17–30,NewYork,NY,USA,2016.ACM.S.Micali,S.Vadhan,andM.Rabin.VerifiableRandomFunctions.InProceedingsofthe40thAnnualSymposiumonFoundationsofComputerScience,FOCS’99,pages120–130.IEEEComputerSociety,1999.S.Nakamoto.Bitcoin:APeer-to-PeerElectronicCashSystem,2008.K.Nikitin,E.Kokoris-Kogias,P.Jovanovic,N.Gailly,L.Gasser,I.Khoffi,J.Cappos,andB.Ford.CHAINIAC:ProactiveSoftwareUpdateTransparencyviaCollectivelySignedSkipchainsandVerifiedBuilds.In26thUSENIXSecuritySymposium(USENIXSecurity17),pages1271–1287.USENIXAssociation,2017.R.PassandE.Shi.HybridConsensus:EfficientConsensusinthePermissionlessModel.CryptologyePrintArchive,Report2016/917,2016.R.Pass,C.Tech,andL.Seeman.AnalysisoftheBlockchainProtocolinAsynchronousNetworks.AnnualInternationalConferenceontheTheoryandApplicationsofCryptographicTechniques(EUROCRYPT),2017.J.PoonandT.Dryja.TheBitcoinLightningNetwork:ScalableOffChainInstantPayments,Jan.2016.Satoshi.info.UnspentTransactionOutputSet,Feb.2017.C.P.Schnorr.Efficientsignaturegenerationbysmartcards.JournalofCryptology,4(3):161–174,1991.B.Schoenmakers.Asimplepubliclyverifiablesecretsharingschemeanditsapplicationtoelectronicvoting.InIACRInternationalCryptologyConference(CRYPTO),pages784–784,1999.E.Syta,P.Jovanovic,E.Kokoris-Kogias,N.Gailly,L.Gasser,I.Khoffi,M.J.Fischer,andB.Ford.ScalableBias-ResistantDistributedRandomness.In38thIEEESymposiumonSecurityandPrivacy,May2017.E.Syta,I.Tamas,D.Visher,D.I.Wolinsky,P.Jovanovic,L.Gasser,N.Gailly,I.Khoffi,andB.Ford.KeepingAuthorities“HonestorBust”withDecentralizedWitnessCosigning.In37thIEEESymposiumonSecurityandPrivacy,May2016.B.Wiki.Proofofburn,Sept.2017.Wikipedia.Atomiccommit,Feb.2017G.Wood.Ethereum:ASecureDecentralisedGeneralisedTransactionLedger.EthereumProjectYellowPaper,2014.附件A:中心化抵抗协议OmniLedger部分解决的先前工作中存在的一个问题是恶意分片领导者中心化审查交易。从分片中其它验证者是无法检测这种攻击的。只要符合状态,领导者不提议交易是可以接受的,但这种攻击可能会损害系统公平性或被用作强制工具。基于这个原因,我们使验证者请求被提交的交易,因为他们认为交易被审查了。他们可以通过正常的八卦过程或直接从客户端接收请求来收集这些交易。这个协议可以定期执行(比如每10个区块)。我们表示存在N=3f+个验证者,其中最多f个为不诚实的。image.png图12的流程:从(1)开始,每个验证者提出一些盲目的反审查交易,以启动共识过程。领导者应该将所有的交易加入区块,然而他能控制f个诚实提议者。总之,它对来自诚实验证者f个交易输入是盲目的,他会达成共识。一旦共识结束,(2)中的交易列表有资格获得反审查,这些是提议子集。因为交易是盲目的,在共识结束前,没有其它验证者能知道哪些是被提议的。每个验证者揭示他选择的交易(3),验证者检查交易是合法的,然后对他们期望领导者提议的交易进行共识。那么,领导者被迫打包符合状态一致的交易(4),否则诚实验证者会启动视图转换[13]。附件B:破坏网络模型虽然假定非静态验证者分组的去中心账本具有类似的同步[34][36]假设,这里我们讨论如果攻击者成功破坏了网络会发生什么。这种情况下,我们检测到攻击,然后提供备份的已知不可扩展但在异步情况下也保证安全的随机数生成机制。假设RandHound在不需要同步时保证安全,攻击者控制网络最多只能拖慢他没有控制的其它验证者,然后总是赢得领导者。然而这不会是攻击者控制RandHound,这只是给他可以重启协议的优势,如果他不喜欢生成的随机数。这个重启可被网络可见,然后当有多次集体RandHound开始失败时,其它参与者可以怀疑其存在偏向尝试。OmniLedger可以提供一个安全阀门机制来缓解这个问题。当有5次RandHound视图连续失败时,在正常情况下这种情况发生的概率为1%,所有验证者将RandHound切换为运行一个完全异步的掷硬币协议[12],该协议使用公开可验证的密钥共享(PubliclyVerifiableSecretSharing)[43]来生成时代随机数。这个协议扩展性很差(O(n**3)),但是当网络处于被攻击和活性没法保证时,它可以保证工作。这种情况下安全是最重要的。附件C:跨分片交易的可能性这节探讨跨分片交易对系统性能的影响。当将状态拆分成不相交的部分时,通常的实践是基于哈希的首比特来分配UTXO给分片。例如,一个分片管理所有首比特为0的UTXO,第二个分片管理所有首比特为1的UTXO。每个分片由保持状态一致和提交更新的一组验证者管理。对于分片内交易,我们想要交易的所有输入和输出都分配给相同的分片,从密码哈希函数的随机性保证中,随机地分配UTXO到分片中的概率是均匀的。令m为为分片的总数,n为输入和输出UTXO的总素,k为需要参与跨分片交易的验证的分片数。那么能计算的概率为:image.png对一个普通的2个输入和1个输出的交易和3个分片的配置,分片内交易的可能性为P(3,1,3)=3.7%,假设交易只触及一个分片有问题。结果如果所有交易都是这种格式,从一个分片到4个分片配置所期望的提速仅为image.png。总的来讲,我们能看到期望的提速是低于我们在第8章的一个取决于输入输出平均数和分片总数的实验结果的。附件D:Atomix对有状态对象的应用图13描述了第4章Atomix协议实现的一个状态机。image.png为了在智能合约中使用这种算法,我们需要考虑智能合约对象是否可变以及正当理由下可并发访问的事实。结果我们需要在两个方面修改算法:解锁交易需要同时发送给输入分片和输出分片状态机需要一个新的状态因为分片在需要解锁前等待确认。这是必要的,因为存在这样的机会使全状态对象被再次访问,这样如果Atomix决定取消时可能会与先输入后输出的依赖相冲突。image.png图14,我们看到对象被一个交易(T)锁住,会拒绝任何其它同步交易(T'),直到T被提交并且新的状态S'已经有效,或者被取消后恢复原先的状态S。(OmniLedger通过客户端来指定分片,分片之间没有直接通信,那么OmniLeger如何处理跨合约调用接口的情况?)作者:区块鱼原链接:https://www.jianshu.com/p/2cc9cda97a75
分布式账本的核心问题就是随机选择出块人,随机性要被全网认可,不可被操纵更不可被预测。POS这里有一点比PoW的方案要好就是,要实现攻击,先得成为持币大户,如果攻击成功币价大跌,攻击者也会承受最大的损失。(精髓)Ouroboros协议密码学手段:1.承诺(Commitment)和打开(open)2.简单随机数协议(Coin-Tossing)3.可验证秘密共享(VerifiableSecretSharing)最后综合一下整个协议流程:在提交阶段,每个节点本地生成随机数和对应的承诺,同时把随机数拆成n份匹配其他的投票节点,并且用相应投票节点的公钥对每一份信息进行加密,保证它只能被对应的节点解密,然后把承诺和加密后的拆分信息一起广播给区块链。当大家收到大部分节点的承诺和拆分信息后,就进入打开阶段,每个节点把自己的打开发到链上。然后是恢复阶段,每个节点检查是否有节点发送了承诺但没有发送打开,如果有,则解密自己对应的那份拆分信息并发布,然后根据大家发布的拆分信息恢复出该节点的随机数。现在大家就有了所有节点的随机数,把它们异或到一起,最终得到了一个一致的随机数,并用它来选择下一轮的出块人。
股权证明PoS定义:PoS试图解决PoW中大量资源被浪费的缺点。它的安全性不是来自矿机的性能,而是来自提高经济损失的经济价值。区块链维护一个验证人的集合,验证者轮流对块提名并投票,每个验证者的投票权重取决于其存款的大小。持币的节点通过发送某种特定类型的交易把币作为锁定的保障金之后成为一个验证者,然后区块链当前有效的验证者基于某种共识算法产生并确认一个新块。侧链:可以让比特币更加安全的从比特币主链转移到其他区块链,当然,也可以从其他区块链转移到比特币主链的一种协议。“基于链的PoS”:Ouroboros(转载自https://www.jianshu.com/p/10e886cb4cf7)【praos】【genesis】【hydra】Praos的主要改进是采用可验证随机函数(VRF)代替公开伪随机函数进行slotleader选择--计算随机数vrf::PrivateKey->Seed->(a,VrfProof)--验证随机数verifyVrf::PublicKey->Seed->(a,VrfProof)->Bool--区分不同slotslotSeed::SlotIndex->EpochSeed->Seed论文中的Ouroboros是一个理论:按照什么样的一个流程可以设计出一个健壮的PoS算法并给出数学上充分的证明。而Cardano中的Ouroboros是对论文的实现,工程实现上跟论文中的描述有所不同。持久性(persistence)和存活性(liveness)模型:持久性是指区块的确认时间,持久性是指多少个块之后交易不可更改。存活性是指交易的确认时间,从向网络发送交易开始,多长时间被确定,超过了这么长时间,要么被确定了,要么被抛弃了。Algorand协议区块链三元悖论:去中心化、高效率与安全性组成一个不可能三角形,三者不可兼得securemultipartycomputation(MPC)MPC协议:n个参与方必须各自输入信息去计算一个约定的函数。除了计算的正确性,他们还必须保障每个参与方输入数据的隐私。具体来说,现在有n个参与方,每个参与方i都知晓自己录入的xi,他们来共同计算一个预先商定的函数f(x1,…,xn)=y。如此一来,所有的参与方都能获得最终的y值,但无法获知其他参与方输入的具体数据。安全多方计算协议是一种分布式协议,允许各参与方在不泄露自身隐私信息的前提下,通过既定逻辑共同计算出一个结果。基于此提出了一个端到端的MPC框架,以实现隐私保护计算。侧链有两种形式存在:一种是两条链是平等的,一种是侧链是主链的孩子补充说明1、比特币在侧链里流通时还是比特币,侧链的比特币与主链的比特币通常是1比1的汇率,也可能有预定的汇率。2、侧链的挖矿不能产出比特币,侧链可能有自己的币,也可能没有自己的币,仅是为了比特币的流通。3、侧链可能是对等的和非对等的。对等的侧链独立存在,其也可成为主链。主侧是相互的,如果有足够的需求,比特币也可成为莱特币的侧链。非对等侧链依赖主链而存在。4、去中心化没改变,每个人或公司都可创建自己的比特币侧链,用户和矿工认同的会成为主流。5、当然侧链要有足够的算力保证侧链的可靠和安全。6、侧链白皮书提出了清晰的侧链框架,具体侧链怎么实现容许设计者自由发挥。7、滞留费。即长期不移动的币随着时间的推移将减值,减去的金额回馈矿工。比如超过1年不动的币,每年减值10%。现在的比特币网络,时常有大户丢失密钥,相应的币也就丢了。这将降低比特币经济体货币的充足性和流动性,被认为是比特币潜在的一个风险。通过滞留费,鼓励货币流动,激励矿工,也可回收一些因丢失密钥丢掉的币。8、新的挖矿所得约定。矿工的算力如果威胁到网络安全,将扣发挖矿所得。比如,算力超过50%的矿工没有奖励,这样可约束矿工节制算力,防止51%攻击。9、挖矿所得延期支付约定。现在,矿工挖到矿后立即得到奖励和交易费。这个约定把挖矿所得延期支付。比如:在挖到矿的100个区块后支付挖矿所得。这有助于激励矿工维护网络的正常运作。10、定期可动用地址。新增一种与时间有关的地址。只有到了特定的时间才可动用该地址的币。比如人们可以把10个币发到这类型地址,设定10年后用。时间没到时,任何人,包括拥有者,也不能动里面的币。11、侧链收益。侧链矿工的收益可以来源于侧链单独的奖励,也可以是来源于主链的奖励2-waypegPoS设计的挑战基于PoS的区块链协议最基本的一个问题就是模拟领导者选举过程。为了在股东们之间的选举达到一个真正的随机性,系统中就必须要引入熵(entropy),但引入熵的机制可能会容易被敌手操作。例如,一个控制一群股东的敌手可能会试图模拟协议的执行,尝试不同的股东参与者的顺序以此来找到对敌对股东有力的继续者。这会导致一个叫做"grinding"的致命弱点,敌对参与者可能会使用计算资源来倾斜领导者选举。交叉链认证(cross-chaincertification)