原文链接：OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding

摘要

设计一个可与中心化支付系统（比如Visa)的性能对标的 安全无权限的去中心化账本（区块链）是一件极具挑战的事。大多数现存的去中心化账本是不具有高性能或者靠吞吐量的，比如通过增加验证者数量提高处理性能。而那些具有高性能的，要么损失安全性，要么偏中心化方案。我们提出OmniLedger，一种新型的高性能的去中心化账本，它具有无权限性，又保留了长期的安全性。它通过使用一种抗预测(bias-resistant)的公共随机协议(a bias-resistant public-randomness protocol)来选择具有统计代表性的大型分片来处理交易，以及通过引入一种有效的跨分片提交协议(an efficient crossshard commit protocol)来原子性的处理影响多分片的交易，从而保证了安全性和正确性。OmniLedger同时通过在分片内进行并发交易处理优化了性能，通过集体签名的状态区块以及对小额交易进行低延迟的“trust-but-verify”方式验证缩减了账本大小。我们实验原型的一个评估显示OmniLedger的吞吐量与活跃的验证者数量是线性扩展的，可支撑Visa级别的交易量，同时可以在2秒内对一般交易进行确认。

1. 介绍

去中心化账本(DL)关于总交易量和独立处理交易的参与者数量之间的可扩展性问题，是一个被主流认可的主要挑战问题，特别是在与安全性和去中心化挑战对比的时候。有许多办法展示了不同的安全性和性能权衡[10],[11],[21],[32],[40]。比如，通过替换中本聪共识(Nakamoto consensus)[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]和混合共识(Hybrid Consensus)[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接纳了经典的分布式检查点原则( classic distributed checkpointing principles)[20]来定期生成一致的状态区块。

最后，为降低通常情况下的交易延迟，比如小额交易，OmniLedger支持可选的"trust-but-verify"验证方式，即在较小的第一层的验证者快速处理这些交易，然后把它们提交给更大但更慢的第二层来重新验证第一层交易的正确性以及长期的安全性。这种2层解决方案保证任何第一层的不当行为可以在数分钟内被检测，然后以损失押金的形式进行严厉地惩罚。客户可以等待两层处理完大额交易以保证最大的安全性，或者可以只等待第一层处理完小额交易。

为评估OmniLedger的效果，我们用Go语言实现了一个原型版本在商用服务器上运行（12核VM on Deterlab），我们的实验结果显示OmniLedger可以按照验证者数量线性横向扩展，在具有12.5%恶意节点的1800个广泛分布的的主机环境上实现了10秒共识延迟下达到了6000tps。而且，将OmniLedger以”信任但验证“的二层验证模型下部署时，在具有25% 恶意节点时实现了4秒第一层延迟的2250tps吞吐量。最后，一个具有长达一个月陈旧状态视图的比特币验证者会产生40%的带宽流量，由于区块同步。(Finally, a Bitcoin validator with a month-long stale view of the state incurs 40% of the bandwidth, due to state blocks。这句是何意？不太理解)

总的来说，本文做出了以下贡献:

• 介绍了第一个提供水平扩展的不以损害长期安全性或无权限去中心化的去中心化架构。
• 介绍了Atomix，一种原子提交协议，实现跨分片的原子提交交易功能。
• 介绍了ByzCoinX，一种针对DoS攻击时增加性能和健壮性的BFT共识协议。
• 介绍了状态区块(state blocks)，在OmniLedger上部署以减小存储空间和更新开销。
• 介绍了信任但验证二层模型(或者叫乐观验证)来降低小额交易延迟。

2. 知识背景

A. ByzCoin的可扩展拜占庭共识

OmniLedger建立在ByzCoin中的拜占庭共识方案之上，因为它在上千个共识组成员里可以有效扩展。为了使例如PBFT[13]之类的传统共识协议更加可扩展，ByzCoin利用集体签名(collective signing)或群签名(CoSi)[45]，一种可扩展的加密原语来实现多重签名。ByzCoin采用组播树(multicast trees)分发区块以提高性能，但是为了容错却回退使用了扩展性较差的星型拓扑。虽然ByzCoin的共识具有扩展性，但是其总体的处理容量却没有随着参与节点数量而增加，所以它是不能横向扩展的。

B. 交易处理和UTXO模型

去中心化账本从区块链或一条包含交易的完全有序区块继承了现在的系统状态。基于其简单性和可并行性，OmniLedger接受UTXO模型来代表账本状态。在这个模型里，一个交易的输出创建新的UTXO并授予其信用，交易的输入则完全花费已存在的UTXO。在新的全节点启动时，会同步抓取整个账本并建立合法UTXO的数据库以便用于后续验证新区块是否合法。这个UTXO模型是被比特币[36]引入的并且已经被其它去中心账本系统广泛认可。

C. 安全的去中心化随机数生成器

RandHound[44]是一个可扩展的安全的多方计算(MPC)协议，在拜占庭环境里可提供无偏见的、去中心化的随机性。RandHound假设存在一个外部负责任的客户，他想从一大群半信任化的服务器中获取可证明的随机性。为了产生随机性，RandHound将服务器组拆分更小的组，并创建一个公开可验证的先提交后揭示(commit-then-reveal)的协议[43]，该协议采用鸽笼原理在包括至少一名诚实参与者贡献时来证明最终的随机数，因此完美地实现了对RandHound输出的随机化。

加密抽签(Cryptographic sortition)[25]用来根据验证者权重函数对验证者选择一个子集。为了使验证者能够证明他们属于某个选中的子集，他们需要一个公钥和私钥对，(pki, ski)。抽签通过一个VRF(verifiable random function：可验证随机函数)实现：输入x，然后返回一个随机hash(l-bit长的字符串)，和一个基于ski的证明 π。这个证明 π可使任何人知道用pki去验证该hash对应于x。

D. 抗女巫攻击的身份认证(Sybil-Resistant Identities)

不像有权限的区块链[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. 先前的分片式账本: Elastico

OmniLedger和先前探讨过的在无权限账本上实现分片的Elastico是很接近的。在每一轮，Elastico利用PoW哈希中最低比特位来分发矿工给不同的分片，然后每个分片运行PBFT[13]来达到共识，接着领导分片(leader shard)验证所有的签名，然后创建全局区块。

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-policy file）
• 在全局的重配置事件(即验证者到分片的重新分配)中，时间周期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在去中心化、安全和扩展性方面有以下主要目标：

1. 完全去中心化 - OmniLedger不会有任何单点故障问题。(比如信任的第三方机构)
2. 分片的健壮性 - 每个分片都可持续正确地处理分配给它的交易。
3. 安全的交易 - 分片内或跨分片的交易都能原子性的提交确认或最终取消。
4. 横向扩展 - OmniLedger期望的吞吐量随着参与验证者的数量而线性增加。
5. 更低的存储开销 - 验证者不需要存储完整的交易历史，而仅仅需要存储汇总分片状态的定期计算的参考点。
6. 低延迟 - OmniLedger为交易确认提供更低的延迟。

E. 设计路线图

本节介绍SLedger，一种稻草人去中心化系统，我们用它来概述OmniLedger的设计。下面我们来描述SLedger的一个时间周期(epoch)，以及显示其如何从周期e-1转换到周期e。
(备注：在软件开发中，稻草人是指一个粗略的计划或文件，是项目演进的起点。)

我们从安全验证者分配到分片开始。允许验证者选择他们想要验证的分片是不安全的，因为攻击者可以将所有其验证者集中一个分片中。因此，我们需要一个随机源来保证一个分片内的验证者将成为系统总体的一个样本，将具有相同比例的恶意节点。SLedger操作可信随机信标，使其在时间周期e内广播一个随机值rnd[e]给所有参与者。想从时间周期e开始参与SLedger的验证者，必须先在一个全局身份区块链上注册身份，在时间周期e-1内他们通过抗女巫攻击机制创建他们身份，然后在八卦网络(the gossip network)上在时间周期e-1结束前以最多的∆值，连同相应的证据进行广播。

时代e以由rnd[e-1]随机数选举的一个领导者开始，该领导者向从已经注册且活跃的验证者们请求一个区块上的（BFT）签名，这个区块具有已证明被创建的所有身份信息。如果这些验证者如果有2/3的比例拥护该区块，它就变成合法的，然后有领导者将该区块挂入身份区块链。然后，所有注册的验证者们使用rnd[e]来决定将自己分配到SLedger中的其中一个分片上，然后从相应分片的分布式账本中同步启动内部状态。那么，他们就准备好开始使用ByzCoin的共识机制来处理交易了。随机的分片分配机制保证了在一个给定分片中恶意和诚实验证者的比例与在所有验证者中的恶意和诚实的比例是最有可能相接近的。

SLedger已经给OmniLedger提供了类似的功能，但是有几个有意义的安全限制。

• 首先，随机信标是一个可信任的第三方机构。
• 在每个时代开始时的全局重配置期间，系统会停止处理交易，直到有足够的验证者已经启动他们的内部状态。
• 这里不支持跨分片交易。

SLedger设计的性能表现也不佳，由于：

• 第一，ByzCoin的失败处理机制，当验证者失败时，它的性能会恶化。
• 第二，验证者面临很高的存储和启动开销。
• 最后，SLedger不能提供实时确认和高吞吐量。

为解决这些安全问题，我们在第4章介绍OmniLedger的安全设计。

1. 在4-节，我们删除了可信任的随机数信标，并展现验证者如何自主地将RandHound与采用加密抽签方式的基于VRF的领导选举进行安全分片。
2. 在4-B节，我们展现如何在跨时代时安全地处理将验证者分配给分片，同时保证持续的处理交易。
3. 在4-C节，我们展示Atomix，一种在拜占庭环境下自动处理跨分片交易的新型的二步原子提交协议。

为解决性能问题，我们在第5章介绍OmniLedger的性能和可用性设计。

4. 在5-A节，我们介绍ByzCoinX，一个ByzCoin的变种，可利用更加健壮的通信模型来高效地处理分片内部的交易，即使一些验证者失败了；可在交易级别解决依赖性以实现更好的区块并行化。
5. 在5-C节，我们介绍状态区块(state block)，其汇总了一个时代的分片状态，可为验证者缩减账本以降低存储和启动开销。
6. 在5-D节，我们展示通过利用信任但验证的分片内交易验证方式(an intra-shard architecture with trust-but-verify transaction validation)，如何在不牺牲安全性或吞吐量的情况下进行乐观实时的交易确认。

图2阐述了OmniLedger的总体安全架构。

image.png

4. OmniLedger: 安全性设计

A. 采用抗偏性分布式随机数进行分片(Sharding via Bias-Resistant Distributed Randomness)

为使在不用可信任随机数信标[16]或绑定协议到PoW上[34]等方式产生可安全分片的随机数种子，我们依赖于一种由验证者们共同执行的分布式随机数生成协议。

我们要求这个分布式随机数生成协议提供无偏性、不可预测、第三方可验证、和可扩展性，有多种建议参考[7][28][44]。第一种方法依赖比特币，而另外具有很多相同的设计；我们关注RandHound[44]是因为它有更好的文档和开源实现。

因为RandHound依靠领导者来协调协议运行，我们需要一个合理的机制来从验证者中选举一个出来。如果我们使用确定性方法来执行领导人选举，那么攻击者通过拒绝运行协议，在最坏的情况下可能达到f/n的失败率，在我们的模型中会有高达n/4的失败率。因此，领导选举机制必须是不可预测和无偏性的，但当我们在第一次使用RandHound时，就碰到了先有鸡还是现有蛋的问题。（因为我们需要RandHound来产生随机数，但是RandHound自己又需要随机选举的领导者，那么第一次运行时，这个随机领导者怎么产生？）为了克服这个困境，我们将RandHound与基于VRF的领导选举算法[44][25]向结合。

1. e时代开始，每个验证者i计算一张门票:
   ticket[i,e,v] = VRF[ski] ("leader"||config[e]||v)

• config[e]表示包含e时代所有合理注册的验证者的配置信息（保存在身份区块链中(identity blockchain)）
• v是一个视图计数(view counter)

2. 验证者们开始相互传播他们的门票，持续一个时间∆，之后他们锁定一个他们迄今看到的最小的合法门票，并接收该门票对应的节点为运行RandHound协议的领导者.
3. 如果被选举的节点在另一个时间∆内启动RandHound失败，那么验证者们认为本次运行失败，并在本时代之后的时间将该验证者排除在外，即使他后来上线了。
4. 这种情况下，验证者们增加视图计数值为v+1，重新运行选举(抽奖)。
5. 当验证者们成功完成了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中验证者分片分配按照以下步骤工作。

1. 设置参数 k < 1/3 * n/m, 作为批次转出的数量（即特定时间转移出分片的验证者数量）。针对OmniLedger，我们决定设置 k = log(n/m)
2. 然后针对每个分片j，我们获得一个种子H(j || rnd[e])来计算分片验证者的排列π[j,e]，并且我们指定批次排列。
3. 同时计算另一个种子H(0 || rnd[e])，来置换和分散新加入e时代的验证者，并定义按照什么顺序进行（大小也为k）。
4. 定义好随机排列后，每批次等待时间∆再开始启动以保证分散负担到网络上。
5. 当一个验证者准备好后，他发送一个声明给将其转入分片的分片领导者。

安全论据：

• 在转换阶段，我们在每个分片保证BFT共识的安全性，因为在每个分片里总是至少有2/3 * n/m数量的诚实验证者愿意参与共识。
• 我们使用时代随机数rnd[e]来获得批次排列，针对自适应攻击者我们保持分片配置是一个移动目标。
• 只要有2/3 * n/m诚实和保持更新的节点，分片活性就可以保证。
• 反之如果转换期间未达到法定人数(新批次的诚实验证者还没更新完成)，分片活性会暂时不可用直到新验证者更新完成。

C. 跨分片交易

为了启用跨分片的价值转移以实现分片的互操作性，在任何分片型账本系统中支持安全的跨分片交易都是至关重要的。我们期望在传统模型中大多数交易是跨分片的，其中UTXO被自由的分配给分片进行处理[16][34]。具体参考附件C。

针对跨分片交易的一个简单但不完善的稻草人方式，是将一个交易同步地发送给多个分片处理，因为有些分片会提交交易，其它的会取消。这种情况下，这些UTXO在接受交易的分片中被丢失，因为没有一种直接的方式可以回退半提交的交易，在没有添加可利用的竞争条件时。

为解决这个问题，我们提出一种新型的拜占庭分片原子提交协议(Byzantine Shard Atomic Commit (Atomix))来自动处理跨链交易，保证每个交易被完全提交或最终取消。目的是保证跨分片交易的一致性，以阻止双花或者未花费的资金被永久锁住。在分布式计算里，这个问题被称为原子提交[47]或原子提交协议[27][30]被部署到诚实但不可靠的处理器上。

在OmniLedger上部署这类协议是不必要的复杂，因为分片们都是集体诚实的，而且不会无限奔溃，并运行BFT共识。Atomix通过锁和解锁过程改进了稻草人方法。我们故意保持分片逻辑的简单性，并且通过授权客户负责驱动解锁过程，同时当特定交易在提交处理后停滞时允许其它方(验证者或其它客户端)来填写客户端，从而使分片与分片之间的直接通信变得不必要。

Atomix使用UTXO状态模型，整体参考2-B，它可使下面的简单而高效的三步协议成为可能。另外可参考图3.

1. 初始化：客户端创建一个跨分片交易(cross-Tx)，输入UTXO来自输入分片(IS)，输出创建新的UTXO来自输出分片(OS)。客户端八卦(cross-Tx)交易，并最终到达所有的(IS)。
2. 锁定：所有 输入分片(IS)与(cross-Tx)进行关联。
   • 首先，检查输入是否可以被花费，每个(IS)领导者检查本分配内的交易。
   • 如果交易合法，领导者在状态上标记这个输入被花费，在分片账本上记录交易日志，然后八卦接受证明(proof-of-acceptance)，这是一种包含本交易的区块的被签名的默克尔树证明。
   • 如果交易被拒绝，领导者创建一个相似的拒绝证明(proof-of-rejection)，其中特定比特位来表示接受或拒绝。
   • 客户端可以利用每个(IS)账本来检查其证明以确认该交易确实被锁住。
   • 当所有(IS)已经处理了锁请求，客户端就具有足够的证明来提交交易，或取消交易并回收任何锁定的资金。
3. 解锁：根据锁阶段的结果，客户端可以提交交易或取消交易。
   • 解锁提交: 如果所有的(IS)领导者都返回了接受证明，那么对应的交易就可以被提交。客户端(或超时后为其它实体比如IS领导者)创建并八卦一个解锁提交交易(unlock-tocommit transaction)，该交易由每个输入UTXO的锁交易和接受证明组成。相应的，每个介入的(OS)验证交易并包含进下一个其分区账本区块中以更新其状态，并使新资金可被花费。
   • 解锁取消：然而如果只要有一个(IS)返回了拒绝证明，那么该交易就无法提交，必须被取消。为了回收上阶段被锁住的资金，客户端(或其它实体)必须请求介入的(IS)解锁特定的交易，通过八卦一个解锁取消交易(unlock-to-abort transaction)，其中包括至少一个输入UTXO的拒绝证明。输入分片(IS)领导者接收到解锁请求后，会进行类似的步骤并标记原先的UTXO重新可花费。
     
     image.png

我们评论一下，虽然OmniLedger专注在UTXO模型上，但是Atomix可以被扩展到其它的具有锁机制的系统，其中对象是长期活性和保存状态的。(比如智能合约[48]，请参考附件D)。

安全论据：下面我们进行非正式地讨论前面陈述的Atomix的安全性，主要基于下面的观察。

• 基于我们的假设，分片是诚实的，不会失败，最终都收到所有消息并达到BFT共识，那么
  1. 所有分片都忠诚地处理合法交易；
  2. 如果所有输入分片返回接收证明，那么每个输出分片都进行解锁提交；
  3. 即使只有一个输入分片返回拒绝证明，那么所有输入分片都解锁取消；
  4. 即使只有一个输入分片返回拒绝证明，那么没有输出分片需要解锁提交。
• 在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具有更好的健壮性和并行性。另外，我们介绍状态区块(state block)，以实现快速启动和降低存储开销。最后我们提出一种可选的“信任但验证”的二层验证机制来对小风险交易进行实时确认。

A. 拜占庭故障下的容错

原先的ByzCoin设计提供了良好的扩展性，部分归咎于使用了组播树通信模式。长时间维护这样的通信树是非常困难的，因为它们很容易受到故障的影响。在失败的情况下，ByzCoin会回退到更加健壮的全方位通信模式，类似于PBFT。因此，共识性能显著恶化，攻击者可以利用这个弱点来阻碍系统性能。

为实现OmniLedger更好的容错，又不采用PBFT全方位的通信模式，我们引入ByzCoinX作为一种新的通信模式，代价是为了健壮性牺牲掉一些ByzCoin的高性能。方法是通过将共识组内的消息传播机制更改为类似于两级树。OmniLedger在一个时代的设置期间，产生的随机数不仅用来验证者到分片的分配，同时也将验证者分配给分片内的相应组。组的数量g，其中通过考虑保存在分片策略文件中的分片大小可以导出最大的组大小。在ByzCoinX的开始轮次中，协议领导者从每个组中随机地选出一个验证者作为组领导者，其负责管理协议领导者与各小组成员之间的通信。如果组领导者在一个预设时间内没有回复，协议领导者重新随机选择一个组领导者来代替失效的那个。一旦协议领导者接收到超过2/3的验证者认可，他就马上进入协议的下一步。如果协议领导者失效，所有验证者发起一个类似PBFT的视图改变步骤。
(备注：这里的协议领导者是指分片内的领导吗？怎么产生的？)

B. 并行区块提交

我们现在展示ByzCoinX如何在UTXO模型中进行并行区块提交，通过仔细分析和处理交易之间的依赖性。

我们观察到没有相互冲突的交易可以被安全地并行处理。为区分冲突的交易，我们需要分析交易之间可能的依赖性。

• 定义tx[A]和tx[B]表示两个交易，那么两种情况需要被小心处理：
  • 1. tx[A]和tx[B]同时花费了相同的UTXO
  • 2. tx[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。

为了使那些经常重新分配分片的验证者减小存储和启动开销，我们引入状态区块(state blocks)，它和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.png

6. 安全性分析

待补充

7. 实现

待补充

8. 评估

待补充

9. 相关工作

待补充

10. 局限性和未来工作

待补充

11. 结论

待补充

参考资料

1. I. Abraham, D. Malkhi, K. Nayak, L. Ren, and A. Spiegelman.
   Solidus: An Incentive-compatible Cryptocurrency Based on Permissionless Byzantine Consensus.CoRR, abs/1612.02916, 2016.
2. M. Al-Bassam, A. Sonnino, S. Bano, D. Hrycyszyn, and G. Danezis.
   Chainspace: A Sharded Smart Contracts Platform. arXiv preprint arXiv:1708.03778, 2017.
3. M. Apostolaki, A. Zohar, and L. Vanbever. Hijacking Bitcoin: Largescale Network Attacks on Cryptocurrencies. 38th IEEE Symposium on Security and Privacy, May 2017.
4. Bitnodes. Bitcoin Network Snapshot, April 2017.
5. Blockchain.info. Blockchain Size, Feb. 2017.
6. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In International Conference on the Theory and Application of Cryptology and Information Security, pages 514–532. Springer, 2001.
7. J. Bonneau, J. Clark, and S. Goldfeder. On Bitcoin as a public randomness source. IACR eprint archive, Oct. 2015.
8. M. Borge, E. Kokoris-Kogias, P. Jovanovic, N. Gailly, L. Gasser, and B. Ford. Proof-of-Personhood: Redemocratizing Permissionless Cryptocurrencies. In 1st IEEE Security and Privacy On The Blockchain, Apr. 2017.
9. E. Buchman. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains, 2016.
10. V. Buterin, J. Coleman, and M. Wampler-Doty. Notes on Scalable Blockchain Protocols (verson 0.3), 2015.
11. C. Cachin. Architecture of the Hyperledger blockchain fabric. In Workshop on Distributed Cryptocurrencies and Consensus Ledgers, 2016.
12. C. Cachin, K. Kursawe, and V. Shoup. Random Oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. In 19th ACM Symposium on Principles of Distributed Computing (PODC), July 2000
13. M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. In 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI), Feb. 1999.
14. 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, and D. Woodford. Spanner: Google’s Globally Distributed Database. ACM Trans. Comput. Syst., 31(3):8:1–8:22, Aug. 2013.
15. 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, and R. Wattenhofer. On Scaling Decentralized Blockchains (A Position Paper). In 3rd Workshop on Bitcoin and Blockchain Research, 2016.
16. G. Danezis and S. Meiklejohn. Centrally Banked Cryptocurrencies. 23rd Annual Network & Distributed System Security Symposium (NDSS), Feb. 2016.
17. S. Deetman. Bitcoin Could Consume as Much Electricity as Denmark by 2020, May 2016.
18. DeterLab Network Security Testbed, September 2012.
19. J. R. Douceur. The Sybil Attack. In 1st International Workshop on Peer-to-Peer Systems (IPTPS), Mar. 2002.
20. E. N. Elnozahy, D. B. Johnson, and W. Zwaenepoel. The Performance of Consistent Checkpointing. In 11th Symposium on Reliable Distributed Systems, pages 39–47. IEEE, 1992.
21. I. Eyal, A. E. Gencer, E. G. Sirer, and R. van Renesse. BitcoinNG: A Scalable Blockchain Protocol. In 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16), Santa Clara, CA, Mar. 2016. USENIX Association.
22. M. K. Franklin and H. Zhang. A Framework for Unique Ring Signatures. IACR Cryptology ePrint Archive, 2012:577, 2012.
23. A. Gervais, G. Karame, S. Capkun, and V. Capkun. Is Bitcoin a decentralized currency? IEEE security & privacy, 12(3):54–60, 2014.
24. A. Gervais, H. Ritzdorf, G. O. Karame, and S. Capkun. Tampering with the Delivery of Blocks and Transactions in Bitcoin. In 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 692–705. ACM, 2015.
25. Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling Byzantine Agreements for Cryptocurrencies.Cryptology ePrint Archive, Report 2017/454, 2017
26. The Go Programming Language, Sept. 2016
27. R. Guerraoui. Non-blocking atomic commit in asynchronous distributed systems with failure detectors. Distributed Computing, 15(1):17–25, 2002
28. T. Hanke and D. Williams. Intoducing Random Beascons Using Threshold Relay Chains, Sept. 2016.
29. E. G. S. Ittay Eyal. It’s Time For a Hard Bitcoin Fork, June 2014.
30. I. Keidar and D. Dolev. Increasing the resilience of atomic commit, at no additional cost. In Proceedings of the fourteenth ACM SIGACTSIGMOD-SIGART symposium on Principles of database systems, pages 245–254. ACM, 1995.
31. A. Kiayias, A. Russell, B. David, and R. Oliynykov. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol.Cryptology ePrint Archive, Report 2016/889, 2016
32. E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford. Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing. In Proceedings of the 25th USENIX Conference on Security Symposium, 2016.
33. Y. Lewenberg, Y. Sompolinsky, and A. Zohar. Inclusive block chain protocols. In International Conference on Financial Cryptography and Data Security, pages 528–547. Springer, 2015.
34. L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena. A Secure Sharding Protocol For Open Blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, pages 17–30, New York, NY, USA, 2016. ACM.
35. S. Micali, S. Vadhan, and M. Rabin.Verifiable Random Functions. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS ’99, pages 120–130. IEEE Computer Society, 1999.
36. S. Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System, 2008.
37. K. Nikitin, E. Kokoris-Kogias, P. Jovanovic, N. Gailly, L. Gasser, I. Khoffi, J. Cappos, and B. Ford. CHAINIAC: Proactive SoftwareUpdate Transparency via Collectively Signed Skipchains and Verified Builds. In 26th USENIX Security Symposium (USENIX Security 17), pages 1271–1287. USENIX Association, 2017.
38. R. Pass and E. Shi. Hybrid Consensus: Efficient Consensus in the Permissionless Model. Cryptology ePrint Archive, Report 2016/917, 2016.
39. R. Pass, C. Tech, and L. Seeman. Analysis of the Blockchain Protocol in Asynchronous Networks. Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 2017.
40. J. Poon and T. Dryja. The Bitcoin Lightning Network: Scalable OffChain Instant Payments, Jan. 2016.
41. Satoshi.info. Unspent Transaction Output Set, Feb. 2017.
42. C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991.
43. B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In IACR International Cryptology Conference (CRYPTO), pages 784–784, 1999.
44. E. Syta, P. Jovanovic, E. Kokoris-Kogias, N. Gailly, L. Gasser, I. Khoffi, M. J. Fischer, and B. Ford. Scalable Bias-Resistant Distributed Randomness. In 38th IEEE Symposium on Security and Privacy, May 2017.
45. E. Syta, I. Tamas, D. Visher, D. I. Wolinsky, P. Jovanovic, L. Gasser, N. Gailly, I. Khoffi, and B. Ford. Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning. In 37th IEEE Symposium on Security and Privacy, May 2016.
46. B. Wiki. Proof of burn , Sept. 2017.
47. Wikipedia. Atomic commit, Feb. 2017
48. G. Wood. Ethereum: A Secure Decentralised Generalised Transaction Ledger. Ethereum Project Yellow Paper, 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]，该协议使用公开可验证的密钥共享(Publicly Verifiable Secret Sharing )[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

附件D: Atomix对有状态对象的应用

图13描述了第4章Atomix协议实现的一个状态机。

image.png

为了在智能合约中使用这种算法，我们需要考虑智能合约对象是否可变以及正当理由下可并发访问的事实。结果我们需要在两个方面修改算法：

1. 解锁交易需要同时发送给输入分片和输出分片
2. 状态机需要一个新的状态因为分片在需要解锁前等待确认。

这是必要的，因为存在这样的机会使全状态对象被再次访问，这样如果Atomix决定取消时可能会与先输入后输出的依赖相冲突。

image.png

图14，我们看到对象被一个交易(T)锁住，会拒绝任何其它同步交易(T')，直到T被提交并且新的状态S'已经有效，或者被取消后恢复原先的状态S。

(OmniLedger通过客户端来指定分片，分片之间没有直接通信，那么OmniLeger如何处理跨合约调用接口的情况？)