B. 交易處理和UTXO模型

去中心化賬本從區(qū)塊鏈或一條包含交易的完全有序區(qū)塊繼承了現(xiàn)在的系統(tǒng)狀態(tài)。基于其簡(jiǎn)單性和可并行性，OmniLedger接受UTXO模型來代表賬本狀態(tài)。在這個(gè)模型里，一個(gè)交易的輸出創(chuàng)建新的UTXO并授予其信用，交易的輸入則完全花費(fèi)已存在的UTXO。在新的全節(jié)點(diǎn)啟動(dòng)時(shí)，會(huì)同步抓取整個(gè)賬本并建立合法UTXO的數(shù)據(jù)庫以便用于后續(xù)驗(yàn)證新區(qū)塊是否合法。這個(gè)UTXO模型是被比特幣[36]引入的并且已經(jīng)被其它去中心賬本系統(tǒng)廣泛認(rèn)可。

C. 安全的去中心化隨機(jī)數(shù)生成器

RandHound[44]是一個(gè)可擴(kuò)展的安全的多方計(jì)算(MPC)協(xié)議，在拜占庭環(huán)境里可提供無偏見的、去中心化的隨機(jī)性。RandHound假設(shè)存在一個(gè)外部負(fù)責(zé)任的客戶，他想從一大群半信任化的服務(wù)器中獲取可證明的隨機(jī)性。為了產(chǎn)生隨機(jī)性，RandHound將服務(wù)器組拆分更小的組，并創(chuàng)建一個(gè)公開可驗(yàn)證的先提交后揭示(commit-then-reveal)的協(xié)議[43]，該協(xié)議采用鴿籠原理在包括至少一名誠實(shí)參與者貢獻(xiàn)時(shí)來證明最終的隨機(jī)數(shù)，因此完美地實(shí)現(xiàn)了對(duì)RandHound輸出的隨機(jī)化。

加密抽簽(Cryptographic sortition)[25]用來根據(jù)驗(yàn)證者權(quán)重函數(shù)對(duì)驗(yàn)證者選擇一個(gè)子集。為了使驗(yàn)證者能夠證明他們屬于某個(gè)選中的子集，他們需要一個(gè)公鑰和私鑰對(duì)，(pki, ski)。抽簽通過一個(gè)VRF(verifiable random function：可驗(yàn)證隨機(jī)函數(shù))實(shí)現(xiàn)：輸入x，然后返回一個(gè)隨機(jī)hash(l-bit長(zhǎng)的字符串)，和一個(gè)基于ski的證明 π。這個(gè)證明 π可使任何人知道用pki去驗(yàn)證該hash對(duì)應(yīng)于x。

D. 抗女巫攻擊的身份認(rèn)證(Sybil-Resistant Identities)

不像有權(quán)限的區(qū)塊鏈[16]驗(yàn)證者都是已知的，無權(quán)限的區(qū)塊鏈需要處理女巫攻擊[19]的潛在威脅以保證安全。比特幣(Bitcoin)[36]建議使用PoW工作量證明，其礦工（驗(yàn)證者）創(chuàng)建一個(gè)合法區(qū)塊需要消耗昂貴的計(jì)算（對(duì)一個(gè)nonce進(jìn)行循環(huán)迭代，對(duì)區(qū)塊頭hash進(jìn)行暴力破解使其以特定數(shù)量的0開頭）。Bitcoin-NG[21]使用同樣的PoW技術(shù)以產(chǎn)生抗女巫攻擊的身份。PoW機(jī)制本身有一些問題，比如浪費(fèi)電力以及導(dǎo)致礦池重新中心化的事實(shí)。其它的抵抗女巫攻擊的方法還有采用諸如PoS[31][25]、Proof-of-Burn(PoB)[46]、Proof-of-Personhood[8]等可以克服PoW的問題，并且可以兼容ByzCoin的身份區(qū)塊鏈，當(dāng)然也兼容OmniLedger。

E. 先前的分片式賬本: Elastico

OmniLedger和先前探討過的在無權(quán)限賬本上實(shí)現(xiàn)分片的Elastico是很接近的。在每一輪，Elastico利用PoW哈希中最低比特位來分發(fā)礦工給不同的分片，然后每個(gè)分片運(yùn)行PBFT[13]來達(dá)到共識(shí)，接著領(lǐng)導(dǎo)分片(leader shard)驗(yàn)證所有的簽名，然后創(chuàng)建全局區(qū)塊。

OmniLedger解決了幾個(gè)Elastico未解決的挑戰(zhàn)。

• 首先，Elastico相對(duì)小的分片(比如實(shí)驗(yàn)中每個(gè)分片100個(gè)驗(yàn)證者)，在低于25%惡意節(jié)點(diǎn)時(shí)會(huì)產(chǎn)生每分片每區(qū)塊2.76%的高失敗率，這在PoW系統(tǒng)中是不能被容忍的。在16個(gè)分片里僅僅6個(gè)周期就有高達(dá)97%的失敗率。
• 第二，Elastico的分片選舉不是強(qiáng)抗偏見的，因此礦工可以選擇性的忽視PoW來得到特定的結(jié)果[7]。
• 第三， Elastico不能保證跨分片時(shí)的原子性交易，當(dāng)另一個(gè)分片拒絕交易時(shí)，資金會(huì)永久鎖定在一個(gè)分片中。
• 第四，驗(yàn)證者總是在切換分片，導(dǎo)致它們需要保存全局狀態(tài)，這可能會(huì)阻礙性能，但可以為自適應(yīng)對(duì)手提供更強(qiáng)的保障。
• 最后，交易確認(rèn)的延遲跟比特幣差不多（10 分鐘），這和OmniLedger的可用性差遠(yuǎn)了。

3. 系統(tǒng)概要

本章主要陳述OmniLedger的系統(tǒng)、網(wǎng)絡(luò)和威脅模型，設(shè)計(jì)目標(biāo)，和路線圖。

A. 系統(tǒng)模型

我們假設(shè)：

• 有n個(gè)驗(yàn)證者來處理交易和保證系統(tǒng)狀態(tài)的一致性;
• 每個(gè)驗(yàn)證者i有公鑰和私鑰對(duì)(pki, ski)，我們通過pki來識(shí)別身份i。
• 驗(yàn)證者被均勻地分配到m個(gè)分片中。
• 分片j的參數(shù)在分片策略文件中匯總（shard-policy file）
• 在全局的重配置事件(即驗(yàn)證者到分片的重新分配)中，時(shí)間周期e表示一個(gè)固定的時(shí)間（比如1天）
• 一個(gè)周期的時(shí)間以r 輪進(jìn)行表示，這個(gè)在不同的分片不需要保證一致
• 在每一輪中，每個(gè)分片處理從客戶收集到的交易
• 假設(shè)驗(yàn)證者可以通過任務(wù)抗女巫攻擊機(jī)制建立身份體系，并且提交到身份區(qū)塊鏈；為參加e時(shí)代的驗(yàn)證者必須在e-1時(shí)代進(jìn)行注冊(cè)。
• 這額身份如何加入到身份區(qū)塊鏈，請(qǐng)參考2-D部分。

B. 網(wǎng)絡(luò)模型

對(duì)于 底層網(wǎng)絡(luò)，我們假定和其它網(wǎng)絡(luò)一致[31][34][36]。特別地，我們假定：a) 誠實(shí)驗(yàn)證者的網(wǎng)絡(luò)是良好連接的；b) 誠實(shí)驗(yàn)證者的通信通道是同步的，也就是說一個(gè)誠實(shí)驗(yàn)證者廣播一個(gè)消息，那么所有驗(yàn)證者都能在一個(gè)已知的最大延遲?[39]內(nèi)接收到該消息。然而由于?以分鐘計(jì)數(shù)，我們不能在時(shí)間周期內(nèi)使用它，因?yàn)槲覀兊难舆t目標(biāo)是以秒為單位。因此，在一個(gè)時(shí)間周期內(nèi)的所有協(xié)議使用樂觀地部分同步模型[13]，而?則用來進(jìn)行諸如身份創(chuàng)建和分片分配之類的緩慢操作。

C. 威脅模型

我們表述拜占庭驗(yàn)證者的數(shù)量為f，并假定: n=4f，也就是在特定情況下最多25%的驗(yàn)證者可能是惡意的，跟之前其它的去中心化賬本類似[21][32][34]。這些惡意節(jié)點(diǎn)可以任意操作，比如他們可能拒絕參與或者串通來攻擊系統(tǒng)。剩下的驗(yàn)證者都是誠實(shí)的并堅(jiān)定地遵守協(xié)議要求。我們進(jìn)一步假定對(duì)手在時(shí)間周期順序上是溫和適應(yīng)的，比如他可以嘗試串通驗(yàn)證者，但這需要花費(fèi)一些時(shí)間使破壞性嘗試起作用。

我們?cè)偌俣▽?duì)手是有計(jì)算邊界的，那么加密原語是安全的，并且計(jì)算Diffie-Hellman問題是非常困難的。

D. 系統(tǒng)目標(biāo)

OmniLedger在去中心化、安全和擴(kuò)展性方面有以下主要目標(biāo)：

1. 完全去中心化 - OmniLedger不會(huì)有任何單點(diǎn)故障問題。(比如信任的第三方機(jī)構(gòu))
2. 分片的健壯性 - 每個(gè)分片都可持續(xù)正確地處理分配給它的交易。
3. 安全的交易 - 分片內(nèi)或跨分片的交易都能原子性的提交確認(rèn)或最終取消。
4. 橫向擴(kuò)展 - OmniLedger期望的吞吐量隨著參與驗(yàn)證者的數(shù)量而線性增加。
5. 更低的存儲(chǔ)開銷 - 驗(yàn)證者不需要存儲(chǔ)完整的交易歷史，而僅僅需要存儲(chǔ)匯總分片狀態(tài)的定期計(jì)算的參考點(diǎn)。
6. 低延遲 - OmniLedger為交易確認(rèn)提供更低的延遲。

E. 設(shè)計(jì)路線圖

本節(jié)介紹SLedger，一種稻草人去中心化系統(tǒng)，我們用它來概述OmniLedger的設(shè)計(jì)。下面我們來描述SLedger的一個(gè)時(shí)間周期(epoch)，以及顯示其如何從周期e-1轉(zhuǎn)換到周期e。
(備注：在軟件開發(fā)中，稻草人是指一個(gè)粗略的計(jì)劃或文件，是項(xiàng)目演進(jìn)的起點(diǎn)。)

我們從安全驗(yàn)證者分配到分片開始。允許驗(yàn)證者選擇他們想要驗(yàn)證的分片是不安全的，因?yàn)楣粽呖梢詫⑺衅潋?yàn)證者集中一個(gè)分片中。因此，我們需要一個(gè)隨機(jī)源來保證一個(gè)分片內(nèi)的驗(yàn)證者將成為系統(tǒng)總體的一個(gè)樣本，將具有相同比例的惡意節(jié)點(diǎn)。SLedger操作可信隨機(jī)信標(biāo)，使其在時(shí)間周期e內(nèi)廣播一個(gè)隨機(jī)值rnd[e]給所有參與者。想從時(shí)間周期e開始參與SLedger的驗(yàn)證者，必須先在一個(gè)全局身份區(qū)塊鏈上注冊(cè)身份，在時(shí)間周期e-1內(nèi)他們通過抗女巫攻擊機(jī)制創(chuàng)建他們身份，然后在八卦網(wǎng)絡(luò)(the gossip network)上在時(shí)間周期e-1結(jié)束前以最多的?值，連同相應(yīng)的證據(jù)進(jìn)行廣播。

時(shí)代e以由rnd[e-1]隨機(jī)數(shù)選舉的一個(gè)領(lǐng)導(dǎo)者開始，該領(lǐng)導(dǎo)者向從已經(jīng)注冊(cè)且活躍的驗(yàn)證者們請(qǐng)求一個(gè)區(qū)塊上的（BFT）簽名，這個(gè)區(qū)塊具有已證明被創(chuàng)建的所有身份信息。如果這些驗(yàn)證者如果有2/3的比例擁護(hù)該區(qū)塊，它就變成合法的，然后有領(lǐng)導(dǎo)者將該區(qū)塊掛入身份區(qū)塊鏈。然后，所有注冊(cè)的驗(yàn)證者們使用rnd[e]來決定將自己分配到SLedger中的其中一個(gè)分片上，然后從相應(yīng)分片的分布式賬本中同步啟動(dòng)內(nèi)部狀態(tài)。那么，他們就準(zhǔn)備好開始使用ByzCoin的共識(shí)機(jī)制來處理交易了。隨機(jī)的分片分配機(jī)制保證了在一個(gè)給定分片中惡意和誠實(shí)驗(yàn)證者的比例與在所有驗(yàn)證者中的惡意和誠實(shí)的比例是最有可能相接近的。

SLedger已經(jīng)給OmniLedger提供了類似的功能，但是有幾個(gè)有意義的安全限制。

• 首先，隨機(jī)信標(biāo)是一個(gè)可信任的第三方機(jī)構(gòu)。
• 在每個(gè)時(shí)代開始時(shí)的全局重配置期間，系統(tǒng)會(huì)停止處理交易，直到有足夠的驗(yàn)證者已經(jīng)啟動(dòng)他們的內(nèi)部狀態(tài)。
• 這里不支持跨分片交易。

SLedger設(shè)計(jì)的性能表現(xiàn)也不佳，由于：

• 第一，ByzCoin的失敗處理機(jī)制，當(dāng)驗(yàn)證者失敗時(shí)，它的性能會(huì)惡化。
• 第二，驗(yàn)證者面臨很高的存儲(chǔ)和啟動(dòng)開銷。
• 最后，SLedger不能提供實(shí)時(shí)確認(rèn)和高吞吐量。

為解決這些安全問題，我們?cè)诘?章介紹OmniLedger的安全設(shè)計(jì)。

1. 在4-節(jié)，我們刪除了可信任的隨機(jī)數(shù)信標(biāo)，并展現(xiàn)驗(yàn)證者如何自主地將RandHound與采用加密抽簽方式的基于VRF的領(lǐng)導(dǎo)選舉進(jìn)行安全分片。
2. 在4-B節(jié)，我們展現(xiàn)如何在跨時(shí)代時(shí)安全地處理將驗(yàn)證者分配給分片，同時(shí)保證持續(xù)的處理交易。
3. 在4-C節(jié)，我們展示Atomix，一種在拜占庭環(huán)境下自動(dòng)處理跨分片交易的新型的二步原子提交協(xié)議。

為解決性能問題，我們?cè)诘?章介紹OmniLedger的性能和可用性設(shè)計(jì)。

4. 在5-A節(jié)，我們介紹ByzCoinX，一個(gè)ByzCoin的變種，可利用更加健壯的通信模型來高效地處理分片內(nèi)部的交易，即使一些驗(yàn)證者失敗了；可在交易級(jí)別解決依賴性以實(shí)現(xiàn)更好的區(qū)塊并行化。
5. 在5-C節(jié)，我們介紹狀態(tài)區(qū)塊(state block)，其匯總了一個(gè)時(shí)代的分片狀態(tài)，可為驗(yàn)證者縮減賬本以降低存儲(chǔ)和啟動(dòng)開銷。
6. 在5-D節(jié)，我們展示通過利用信任但驗(yàn)證的分片內(nèi)交易驗(yàn)證方式(an intra-shard architecture with trust-but-verify transaction validation)，如何在不犧牲安全性或吞吐量的情況下進(jìn)行樂觀實(shí)時(shí)的交易確認(rèn)。

圖2闡述了OmniLedger的總體安全架構(gòu)。

image.png

4. OmniLedger: 安全性設(shè)計(jì)

A. 采用抗偏性分布式隨機(jī)數(shù)進(jìn)行分片(Sharding via Bias-Resistant Distributed Randomness)

為使在不用可信任隨機(jī)數(shù)信標(biāo)[16]或綁定協(xié)議到PoW上[34]等方式產(chǎn)生可安全分片的隨機(jī)數(shù)種子，我們依賴于一種由驗(yàn)證者們共同執(zhí)行的分布式隨機(jī)數(shù)生成協(xié)議。

我們要求這個(gè)分布式隨機(jī)數(shù)生成協(xié)議提供無偏性、不可預(yù)測(cè)、第三方可驗(yàn)證、和可擴(kuò)展性，有多種建議參考[7][28][44]。第一種方法依賴比特幣，而另外具有很多相同的設(shè)計(jì)；我們關(guān)注RandHound[44]是因?yàn)樗懈玫奈臋n和開源實(shí)現(xiàn)。

因?yàn)镽andHound依靠領(lǐng)導(dǎo)者來協(xié)調(diào)協(xié)議運(yùn)行，我們需要一個(gè)合理的機(jī)制來從驗(yàn)證者中選舉一個(gè)出來。如果我們使用確定性方法來執(zhí)行領(lǐng)導(dǎo)人選舉，那么攻擊者通過拒絕運(yùn)行協(xié)議，在最壞的情況下可能達(dá)到f/n的失敗率，在我們的模型中會(huì)有高達(dá)n/4的失敗率。因此，領(lǐng)導(dǎo)選舉機(jī)制必須是不可預(yù)測(cè)和無偏性的，但當(dāng)我們?cè)诘谝淮问褂肦andHound時(shí)，就碰到了先有雞還是現(xiàn)有蛋的問題。（因?yàn)槲覀冃枰猂andHound來產(chǎn)生隨機(jī)數(shù)，但是RandHound自己又需要隨機(jī)選舉的領(lǐng)導(dǎo)者，那么第一次運(yùn)行時(shí)，這個(gè)隨機(jī)領(lǐng)導(dǎo)者怎么產(chǎn)生？）為了克服這個(gè)困境，我們將RandHound與基于VRF的領(lǐng)導(dǎo)選舉算法[44][25]向結(jié)合。

1. e時(shí)代開始，每個(gè)驗(yàn)證者i計(jì)算一張門票:
   ticket[i,e,v] = VRF[ski] ("leader"||config[e]||v)

• config[e]表示包含e時(shí)代所有合理注冊(cè)的驗(yàn)證者的配置信息（保存在身份區(qū)塊鏈中(identity blockchain)）
• v是一個(gè)視圖計(jì)數(shù)(view counter)

2. 驗(yàn)證者們開始相互傳播他們的門票，持續(xù)一個(gè)時(shí)間?，之后他們鎖定一個(gè)他們迄今看到的最小的合法門票，并接收該門票對(duì)應(yīng)的節(jié)點(diǎn)為運(yùn)行RandHound協(xié)議的領(lǐng)導(dǎo)者.
3. 如果被選舉的節(jié)點(diǎn)在另一個(gè)時(shí)間?內(nèi)啟動(dòng)RandHound失敗，那么驗(yàn)證者們認(rèn)為本次運(yùn)行失敗，并在本時(shí)代之后的時(shí)間將該驗(yàn)證者排除在外，即使他后來上線了。
4. 這種情況下，驗(yàn)證者們?cè)黾右晥D計(jì)數(shù)值為v+1，重新運(yùn)行選舉(抽獎(jiǎng))。
5. 當(dāng)驗(yàn)證者們成功完成了RandHound的運(yùn)行，并且領(lǐng)導(dǎo)者已經(jīng)成功廣播了rand[e]（攜帶正確性證明），
   • n中的每個(gè)合理注冊(cè)的驗(yàn)證者就可以先驗(yàn)證正確性，
   • 然后用rand[e]來計(jì)算1,...,n的π[e]排列，
   • 再將結(jié)果分配到大小都為m的水桶里(bukets)，因此決定將哪些節(jié)點(diǎn)分配到哪個(gè)分片。

安全論據(jù)： 我們進(jìn)行以下觀察，以非正式的方式論證上述方法的安全性。

• 每個(gè)參與者在e時(shí)代的每個(gè)視圖v只能產(chǎn)生一個(gè)合法的門票，因?yàn)榛?code>VRF的領(lǐng)導(dǎo)選舉只能在身份區(qū)塊鏈中合法的身份已經(jīng)固定時(shí)才能開始。
• 只要非串通節(jié)點(diǎn)的門票對(duì)應(yīng)的私鑰(ski)是保密的，VRF的輸出就是不可預(yù)測(cè)的。因此最后抽獎(jiǎng)的結(jié)果就是不可預(yù)測(cè)的。
• 同步時(shí)間?保證誠實(shí)節(jié)點(diǎn)的門票可以被所有其它誠實(shí)節(jié)點(diǎn)接收看到。
• 如果攻擊者贏得抽獎(jiǎng)，他可以決定遵循并運(yùn)行RandHound協(xié)議，或者讓其失敗，這樣該節(jié)點(diǎn)就會(huì)在本時(shí)代接下來的時(shí)間被排除在外。
• 在成功運(yùn)行RandHound之后，攻擊者首先掌握了隨機(jī)數(shù)，進(jìn)行分片分配，但是他能得到的好處很小。
• 攻擊者可以選擇選擇合作并發(fā)布隨機(jī)值，或者保留它以期望再次贏得抽獎(jiǎng)，并獲得最符合他要求的分片分配任務(wù)。
• 但是，一個(gè)攻擊者抽獎(jiǎng)連續(xù)贏得a次的的概率是按照公式
  image.png
  指數(shù)級(jí)下降的。
• 因此，經(jīng)過幾輪重新抽獎(jiǎng)，誠實(shí)節(jié)點(diǎn)以高概率贏得抽獎(jiǎng)，然后協(xié)調(diào)分片。
• 最后，我們認(rèn)定攻擊者不能在多輪抽獎(jiǎng)中獲得隨機(jī)數(shù)，然后選擇最符合其利益的那個(gè)，因?yàn)轵?yàn)證者只接受符合視圖計(jì)數(shù)v的最新隨機(jī)值。

在附件B中，我們展示OmniLedger如何擴(kuò)展概率性地檢測(cè)預(yù)期的?不存在，以及如何回退協(xié)議保證安全。

B. 時(shí)代轉(zhuǎn)換時(shí)保證可操作性

我們知道，在每個(gè)時(shí)代e，SLedger改變驗(yàn)證者到分片的分配時(shí)，會(huì)導(dǎo)致一段空閑期，這段時(shí)間系統(tǒng)不能處理交易知道足夠的驗(yàn)證者完成啟動(dòng)。

為保持轉(zhuǎn)換階段的可操作性，OmniLedger在每個(gè)時(shí)代逐漸地將新的驗(yàn)證者切換到新的分片。這可以保證剩下的操作者可以持續(xù)提供服務(wù)給客戶，同時(shí)新加入的驗(yàn)證者同步進(jìn)行啟動(dòng)。為了實(shí)現(xiàn)這種持續(xù)的操作，我們可以轉(zhuǎn)移出最多1/3分片大小(約為n/m)的驗(yàn)證者數(shù)量，轉(zhuǎn)出數(shù)量越多，剩余的誠實(shí)節(jié)點(diǎn)不足夠達(dá)到共識(shí)的風(fēng)險(xiǎn)就更高，而且新節(jié)點(diǎn)時(shí)啟動(dòng)的對(duì)網(wǎng)絡(luò)的壓力也越大。

為平衡臨時(shí)失去活性的可能性，OmniLedger中驗(yàn)證者分片分配按照以下步驟工作。

1. 設(shè)置參數(shù) k < 1/3 * n/m, 作為批次轉(zhuǎn)出的數(shù)量（即特定時(shí)間轉(zhuǎn)移出分片的驗(yàn)證者數(shù)量）。針對(duì)OmniLedger，我們決定設(shè)置 k = log(n/m)
2. 然后針對(duì)每個(gè)分片j，我們獲得一個(gè)種子H(j || rnd[e])來計(jì)算分片驗(yàn)證者的排列π[j,e]，并且我們指定批次排列。
3. 同時(shí)計(jì)算另一個(gè)種子H(0 || rnd[e])，來置換和分散新加入e時(shí)代的驗(yàn)證者，并定義按照什么順序進(jìn)行（大小也為k）。
4. 定義好隨機(jī)排列后，每批次等待時(shí)間?再開始啟動(dòng)以保證分散負(fù)擔(dān)到網(wǎng)絡(luò)上。
5. 當(dāng)一個(gè)驗(yàn)證者準(zhǔn)備好后，他發(fā)送一個(gè)聲明給將其轉(zhuǎn)入分片的分片領(lǐng)導(dǎo)者。

安全論據(jù)：

• 在轉(zhuǎn)換階段，我們?cè)诿總€(gè)分片保證BFT共識(shí)的安全性，因?yàn)樵诿總€(gè)分片里總是至少有2/3 * n/m數(shù)量的誠實(shí)驗(yàn)證者愿意參與共識(shí)。
• 我們使用時(shí)代隨機(jī)數(shù)rnd[e]來獲得批次排列，針對(duì)自適應(yīng)攻擊者我們保持分片配置是一個(gè)移動(dòng)目標(biāo)。
• 只要有2/3 * n/m誠實(shí)和保持更新的節(jié)點(diǎn)，分片活性就可以保證。
• 反之如果轉(zhuǎn)換期間未達(dá)到法定人數(shù)(新批次的誠實(shí)驗(yàn)證者還沒更新完成)，分片活性會(huì)暫時(shí)不可用直到新驗(yàn)證者更新完成。

C. 跨分片交易

為了啟用跨分片的價(jià)值轉(zhuǎn)移以實(shí)現(xiàn)分片的互操作性，在任何分片型賬本系統(tǒng)中支持安全的跨分片交易都是至關(guān)重要的。我們期望在傳統(tǒng)模型中大多數(shù)交易是跨分片的，其中UTXO被自由的分配給分片進(jìn)行處理[16][34]。具體參考附件C。

針對(duì)跨分片交易的一個(gè)簡(jiǎn)單但不完善的稻草人方式，是將一個(gè)交易同步地發(fā)送給多個(gè)分片處理，因?yàn)橛行┓制瑫?huì)提交交易，其它的會(huì)取消。這種情況下，這些UTXO在接受交易的分片中被丟失，因?yàn)闆]有一種直接的方式可以回退半提交的交易，在沒有添加可利用的競(jìng)爭(zhēng)條件時(shí)。

為解決這個(gè)問題，我們提出一種新型的拜占庭分片原子提交協(xié)議(Byzantine Shard Atomic Commit (Atomix))來自動(dòng)處理跨鏈交易，保證每個(gè)交易被完全提交或最終取消。目的是保證跨分片交易的一致性，以阻止雙花或者未花費(fèi)的資金被永久鎖住。在分布式計(jì)算里，這個(gè)問題被稱為原子提交[47]或原子提交協(xié)議[27][30]被部署到誠實(shí)但不可靠的處理器上。

在OmniLedger上部署這類協(xié)議是不必要的復(fù)雜，因?yàn)榉制瑐兌际羌w誠實(shí)的，而且不會(huì)無限奔潰，并運(yùn)行BFT共識(shí)。Atomix通過鎖和解鎖過程改進(jìn)了稻草人方法。我們故意保持分片邏輯的簡(jiǎn)單性，并且通過授權(quán)客戶負(fù)責(zé)驅(qū)動(dòng)解鎖過程，同時(shí)當(dāng)特定交易在提交處理后停滯時(shí)允許其它方(驗(yàn)證者或其它客戶端)來填寫客戶端，從而使分片與分片之間的直接通信變得不必要。

Atomix使用UTXO狀態(tài)模型，整體參考2-B，它可使下面的簡(jiǎn)單而高效的三步協(xié)議成為可能。另外可參考圖3.

1. 初始化：客戶端創(chuàng)建一個(gè)跨分片交易(cross-Tx)，輸入U(xiǎn)TXO來自輸入分片(IS)，輸出創(chuàng)建新的UTXO來自輸出分片(OS)。客戶端八卦(cross-Tx)交易，并最終到達(dá)所有的(IS)。
2. 鎖定：所有 輸入分片(IS)與(cross-Tx)進(jìn)行關(guān)聯(lián)。
   • 首先，檢查輸入是否可以被花費(fèi)，每個(gè)(IS)領(lǐng)導(dǎo)者檢查本分配內(nèi)的交易。
   • 如果交易合法，領(lǐng)導(dǎo)者在狀態(tài)上標(biāo)記這個(gè)輸入被花費(fèi)，在分片賬本上記錄交易日志，然后八卦接受證明(proof-of-acceptance)，這是一種包含本交易的區(qū)塊的被簽名的默克爾樹證明。
   • 如果交易被拒絕，領(lǐng)導(dǎo)者創(chuàng)建一個(gè)相似的拒絕證明(proof-of-rejection)，其中特定比特位來表示接受或拒絕。
   • 客戶端可以利用每個(gè)(IS)賬本來檢查其證明以確認(rèn)該交易確實(shí)被鎖住。
   • 當(dāng)所有(IS)已經(jīng)處理了鎖請(qǐng)求，客戶端就具有足夠的證明來提交交易，或取消交易并回收任何鎖定的資金。
3. 解鎖：根據(jù)鎖階段的結(jié)果，客戶端可以提交交易或取消交易。
   • 解鎖提交: 如果所有的(IS)領(lǐng)導(dǎo)者都返回了接受證明，那么對(duì)應(yīng)的交易就可以被提交。客戶端(或超時(shí)后為其它實(shí)體比如IS領(lǐng)導(dǎo)者)創(chuàng)建并八卦一個(gè)解鎖提交交易(unlock-tocommit transaction)，該交易由每個(gè)輸入U(xiǎn)TXO的鎖交易和接受證明組成。相應(yīng)的，每個(gè)介入的(OS)驗(yàn)證交易并包含進(jìn)下一個(gè)其分區(qū)賬本區(qū)塊中以更新其狀態(tài)，并使新資金可被花費(fèi)。
   • 解鎖取消：然而如果只要有一個(gè)(IS)返回了拒絕證明，那么該交易就無法提交，必須被取消。為了回收上階段被鎖住的資金，客戶端(或其它實(shí)體)必須請(qǐng)求介入的(IS)解鎖特定的交易，通過八卦一個(gè)解鎖取消交易(unlock-to-abort transaction)，其中包括至少一個(gè)輸入U(xiǎn)TXO的拒絕證明。輸入分片(IS)領(lǐng)導(dǎo)者接收到解鎖請(qǐng)求后，會(huì)進(jìn)行類似的步驟并標(biāo)記原先的UTXO重新可花費(fèi)。
     
     image.png

我們?cè)u(píng)論一下，雖然OmniLedger專注在UTXO模型上，但是Atomix可以被擴(kuò)展到其它的具有鎖機(jī)制的系統(tǒng)，其中對(duì)象是長(zhǎng)期活性和保存狀態(tài)的。(比如智能合約[48]，請(qǐng)參考附件D)。

安全論據(jù)：下面我們進(jìn)行非正式地討論前面陳述的Atomix的安全性，主要基于下面的觀察。

• 基于我們的假設(shè)，分片是誠實(shí)的，不會(huì)失敗，最終都收到所有消息并達(dá)到BFT共識(shí)，那么
  1. 所有分片都忠誠地處理合法交易；
  2. 如果所有輸入分片返回接收證明，那么每個(gè)輸出分片都進(jìn)行解鎖提交；
  3. 即使只有一個(gè)輸入分片返回拒絕證明，那么所有輸入分片都解鎖取消；
  4. 即使只有一個(gè)輸入分片返回拒絕證明，那么沒有輸出分片需要解鎖提交。
• 在Atomix中，每個(gè)cross-TX會(huì)被提交或取消?；?1)，每個(gè)分片只返回一個(gè)回應(yīng)：接受證明或拒絕證明。因此客戶端用后所需數(shù)量的證明時(shí)，那么針對(duì)每個(gè)輸入U(xiǎn)TXO只會(huì)擁有接受證明或拒絕證明，而不會(huì)兩者同時(shí)擁有。
• 在Atomix中，沒有cross-TX會(huì)被雙花。如上所示，跨分片交易都是原子性，并且只被分配給專門負(fù)責(zé)它們的特定分片?；?1)，被分配的分片不會(huì)對(duì)同一個(gè)交易處理兩次，沒有其它分片會(huì)進(jìn)行解鎖提交。
• 在Atomix中，如果一個(gè)交易無法提交，那么鎖定的資金會(huì)被回收。如果一個(gè)交易無法提交，說明至少有一個(gè)分片返回了拒絕證明。當(dāng)所有的輸入分片解鎖取消后，所有資金重新可用。

我們說，資金不會(huì)自動(dòng)回收，客戶端或其他實(shí)體必須啟動(dòng)解鎖中止過程。雖然這種方法存在一種風(fēng)險(xiǎn)，就是如果客戶端無限崩潰了，他的資金就被鎖住了，但是它實(shí)現(xiàn)了不需要分片之間直接通信的具有最少邏輯的簡(jiǎn)化協(xié)議?？蛻舳搜h(huán)崩潰和客戶端丟失它的私鑰是一樣的，會(huì)阻止他花費(fèi)響應(yīng)的UTXO。而且，系統(tǒng)中的任何實(shí)體，比如交易所中收費(fèi)的驗(yàn)證者，可以為客戶端填寫一個(gè)解鎖交易，因?yàn)樗械男畔⒍际前素赃^的。
(備注：這里不太理解，客戶端發(fā)起的跨鏈交易被鎖后，系統(tǒng)中其它實(shí)體怎么幫助實(shí)現(xiàn)解鎖？)

為保證更好的健壯性，我們可以指定具有最小輸入U(xiǎn)TXO的分片成為協(xié)調(diào)器來負(fù)責(zé)驅(qū)動(dòng)創(chuàng)建解鎖交易的執(zhí)行。因?yàn)橐粋€(gè)分片領(lǐng)導(dǎo)者有可能是惡意的，f+1個(gè)分片中的驗(yàn)證者需要發(fā)送解鎖交易來保證所有交易最終被解鎖。

解鎖交易的大?。涸?code>Atomix中，解鎖交易會(huì)比普通的交易更大，由于相應(yīng)的輸入U(xiǎn)TXO的證明需要被包含。OmniLedger依賴ByzCoinX來處理每個(gè)分片內(nèi)的交易。當(dāng)分片的驗(yàn)證者對(duì)包含已提交交易的區(qū)塊達(dá)成一致時(shí)，他們產(chǎn)生一個(gè)集體簽名，該簽名的大小與驗(yàn)證者的數(shù)量無關(guān)。這個(gè)重要的特性可以使我們保持Atomix證明足夠短，即使每個(gè)交易的合法性都是通過所有輸入U(xiǎn)TXO的簽名區(qū)塊被檢查。如果ByzCoinX不使用集體簽名，解鎖交易的大小是不切實(shí)際的。比如，具有100個(gè)驗(yàn)證的分片一個(gè)集體簽名只有77字節(jié)，而正常簽名則有98KB，基于比一個(gè)簡(jiǎn)單交易大小大兩個(gè)數(shù)量級(jí)。

5. 對(duì)性能的設(shè)計(jì)改進(jìn)

本章節(jié)，我們介紹OmniLedger的性能子協(xié)議。首先我們描述ByzCoinX，一種可擴(kuò)展的BFT共識(shí)，它比ByzCoin具有更好的健壯性和并行性。另外，我們介紹狀態(tài)區(qū)塊(state block)，以實(shí)現(xiàn)快速啟動(dòng)和降低存儲(chǔ)開銷。最后我們提出一種可選的“信任但驗(yàn)證”的二層驗(yàn)證機(jī)制來對(duì)小風(fēng)險(xiǎn)交易進(jìn)行實(shí)時(shí)確認(rèn)。

A. 拜占庭故障下的容錯(cuò)

原先的ByzCoin設(shè)計(jì)提供了良好的擴(kuò)展性，部分歸咎于使用了組播樹通信模式。長(zhǎng)時(shí)間維護(hù)這樣的通信樹是非常困難的，因?yàn)樗鼈兒苋菀资艿焦收系挠绊?。在失敗的情況下，ByzCoin會(huì)回退到更加健壯的全方位通信模式，類似于PBFT。因此，共識(shí)性能顯著惡化，攻擊者可以利用這個(gè)弱點(diǎn)來阻礙系統(tǒng)性能。

為實(shí)現(xiàn)OmniLedger更好的容錯(cuò)，又不采用PBFT全方位的通信模式，我們引入ByzCoinX作為一種新的通信模式，代價(jià)是為了健壯性犧牲掉一些ByzCoin的高性能。方法是通過將共識(shí)組內(nèi)的消息傳播機(jī)制更改為類似于兩級(jí)樹。OmniLedger在一個(gè)時(shí)代的設(shè)置期間，產(chǎn)生的隨機(jī)數(shù)不僅用來驗(yàn)證者到分片的分配，同時(shí)也將驗(yàn)證者分配給分片內(nèi)的相應(yīng)組。組的數(shù)量g，其中通過考慮保存在分片策略文件中的分片大小可以導(dǎo)出最大的組大小。在ByzCoinX的開始輪次中，協(xié)議領(lǐng)導(dǎo)者從每個(gè)組中隨機(jī)地選出一個(gè)驗(yàn)證者作為組領(lǐng)導(dǎo)者，其負(fù)責(zé)管理協(xié)議領(lǐng)導(dǎo)者與各小組成員之間的通信。如果組領(lǐng)導(dǎo)者在一個(gè)預(yù)設(shè)時(shí)間內(nèi)沒有回復(fù)，協(xié)議領(lǐng)導(dǎo)者重新隨機(jī)選擇一個(gè)組領(lǐng)導(dǎo)者來代替失效的那個(gè)。一旦協(xié)議領(lǐng)導(dǎo)者接收到超過2/3的驗(yàn)證者認(rèn)可，他就馬上進(jìn)入?yún)f(xié)議的下一步。如果協(xié)議領(lǐng)導(dǎo)者失效，所有驗(yàn)證者發(fā)起一個(gè)類似PBFT的視圖改變步驟。
(備注：這里的協(xié)議領(lǐng)導(dǎo)者是指分片內(nèi)的領(lǐng)導(dǎo)嗎？怎么產(chǎn)生的？)

B. 并行區(qū)塊提交

我們現(xiàn)在展示ByzCoinX如何在UTXO模型中進(jìn)行并行區(qū)塊提交，通過仔細(xì)分析和處理交易之間的依賴性。

我們觀察到?jīng)]有相互沖突的交易可以被安全地并行處理。為區(qū)分沖突的交易，我們需要分析交易之間可能的依賴性。

• 定義tx[A]和tx[B]表示兩個(gè)交易，那么兩種情況需要被小心處理：
  • 1. tx[A]和tx[B]同時(shí)花費(fèi)了相同的UTXO
  • 2. tx[A]創(chuàng)建的一個(gè)交易輸出被tx[B]作為輸入進(jìn)行花費(fèi)(或相反)
• 為解決問題1)，兩個(gè)交易只有其中一個(gè)才能被提交
• 為解決問題2)，tx[A]需要比tx[B]優(yōu)先提交，也就是說tx[B]所在區(qū)塊必須依賴tx[A]所在的區(qū)塊。
• 所有不包括以上兩種情況的交易都可以被安全地并行處理。
• 特別是，我們說信任相同地址的交易不會(huì)產(chǎn)生沖突，因?yàn)樗麄儺a(chǎn)生不同的UTXO。

為捕獲并發(fā)處理的區(qū)塊，我們采納一種基于區(qū)塊的有向無環(huán)圖(blockDAG)[33]作為數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)區(qū)塊都有多個(gè)父區(qū)塊。ByzCoinX協(xié)議領(lǐng)導(dǎo)者強(qiáng)制每個(gè)掛起的區(qū)塊包含沒有沖突的交易，并通過添加當(dāng)前區(qū)塊中交易所依賴的上個(gè)區(qū)塊的hash來捕獲UTXO依賴性。為減少這類hash的數(shù)量，我們注意到UTXO依賴性是可傳遞的，這使得我們可放寬必須直接捕獲所有UTXO依賴性的要求。相反，特定的區(qū)塊可以簡(jiǎn)單添加反向指針到一個(gè)區(qū)塊集，可傳遞性的捕獲所有依賴性。

C. 分片賬本削減

現(xiàn)在我們來解決不斷增長(zhǎng)的賬本問題，以及由此導(dǎo)致的新驗(yàn)證者啟動(dòng)開銷過大的問題，這對(duì)高性能的去中心化賬本尤其緊急。比如，比特幣區(qū)塊鏈每天增長(zhǎng)144MB，目前的總大小是133GB，而下一代VISA級(jí)高性能的賬本(比如, 4000tx/sec和500B/tx)每天就可以產(chǎn)生超過150GB。

為了使那些經(jīng)常重新分配分片的驗(yàn)證者減小存儲(chǔ)和啟動(dòng)開銷，我們引入狀態(tài)區(qū)塊(state blocks)，它和PBFT[13]中的固定檢查點(diǎn)很類似，就是匯總分片賬本的全部狀態(tài)。

為了在e時(shí)代對(duì)分片j創(chuàng)建狀態(tài)區(qū)塊sb[j, e]，分片的驗(yàn)證者執(zhí)行一下步驟：

• 在e時(shí)代結(jié)束時(shí)，分片的領(lǐng)導(dǎo)者將UTXO保存到一個(gè)排序的默克爾樹，并將樹根哈希存入sb[j, e]區(qū)塊頭部。
• 然后分片驗(yàn)證者對(duì)sb[j, e]區(qū)塊頭部運(yùn)行共識(shí)（注意每個(gè)驗(yàn)證者都可以構(gòu)造相同的排序默克爾樹進(jìn)行驗(yàn)證）。
• 如果共識(shí)成功，領(lǐng)導(dǎo)者將通過的區(qū)塊頭保存進(jìn)分片賬本中，使sb[j, e]成為e+1時(shí)代的創(chuàng)世區(qū)塊。
• 最后，sb[j, e-1]區(qū)塊主體中的UTXO可以被安全的丟棄。為了創(chuàng)建交易證明，我們保留e時(shí)代的正常區(qū)塊，直到e+1時(shí)代結(jié)束。

因?yàn)镺mniLedger的狀態(tài)是拆分到多個(gè)分片的，并且我們僅在分片賬本中保存狀態(tài)區(qū)塊的頭部，客戶端通過提交一個(gè)交易被提交的區(qū)塊的包含證明不能向其它實(shí)體證明一個(gè)過去交易的存在。我們解決這個(gè)問題通過移除客戶端保存交易存在證明的責(zé)任。在e+1時(shí)代期間，客戶端可以使用e時(shí)代的常規(guī)區(qū)塊和狀態(tài)區(qū)塊來生成e時(shí)代已驗(yàn)證交易的存在證明。對(duì)于給定交易tx的這種證明包含對(duì)e時(shí)代提交交易'tx'的常規(guī)區(qū)塊B的默克爾樹包含證明，以及時(shí)代結(jié)束時(shí)的狀態(tài)區(qū)塊sb[j, e]和區(qū)塊B的順序區(qū)塊頭。為減小這些證明的大小，狀態(tài)區(qū)塊可包含多個(gè)多跳反向指針指向類似skipchains[37]的中間常規(guī)區(qū)塊的頭部。

最后，如果我們天真地去實(shí)現(xiàn)狀態(tài)區(qū)塊的創(chuàng)建，它會(huì)阻礙時(shí)代的啟動(dòng)，因?yàn)橹钡?code>sb[j, e]已經(jīng)被寫入賬本交易才開始處理。為避免這種停機(jī)時(shí)間，e+1時(shí)代分片中的所有驗(yàn)證者在時(shí)代開始時(shí)需要包含一個(gè)空的狀態(tài)區(qū)塊作為替代，一旦sb[j, e]準(zhǔn)備完成，驗(yàn)證者就將其作為普通的區(qū)塊提交，并指向上一個(gè)替代者和sb[j, e-1]。

D. 可選的"信任但檢查"驗(yàn)證

image.png

如圖4所闡述的，在分片數(shù)量、吞吐量和延遲之間有一個(gè)繼承的代價(jià)。具有大量的小分片數(shù)量可以獲得更好的性能，但是對(duì)更強(qiáng)大的攻擊者提供的彈性更小。因?yàn)镺mniLedger的設(shè)計(jì)有利于安全性超過可擴(kuò)展性，我們悲觀地假設(shè)一個(gè)對(duì)手控制著25％的驗(yàn)證者，因此，選擇大的分片會(huì)以更高的延遲為代價(jià)，但保證交易的最終性。然而這個(gè)假設(shè)不能恰當(dāng)?shù)胤从衬切┚哂蓄l繁使用、延遲敏感但低價(jià)值交易的客戶的優(yōu)先級(jí)（比如，雜貨店支付，購買汽油或咖啡等），他們喜歡交易處理地越快越好。

為滿足客戶的需求，我們?cè)黾右环N分片內(nèi)架構(gòu)（如圖4），通過遵循“信任但檢查”模型，使樂觀的驗(yàn)證者更快地處理交易，提供臨時(shí)但不太可能改變的交易提交，然后核心的驗(yàn)證者隨后再次核實(shí)交易以提供最終結(jié)果并確?？沈?yàn)證性。樂觀驗(yàn)證者按照常規(guī)的步驟來決定哪些交易按哪種順序提交，但是他們會(huì)組成更小的分組，甚至可能一個(gè)驗(yàn)證者一個(gè)組。因此他們實(shí)時(shí)地生成更小的區(qū)塊，但是可能很不安全，因?yàn)楣艨赡軙?huì)按比例控制較小數(shù)量的驗(yàn)證者來破壞交易。結(jié)果，一些不合法的交易被提交，但是最終核心驗(yàn)證者會(huì)檢查所有臨時(shí)的提交，檢測(cè)任何不一致和他們的罪魁禍?zhǔn)祝缓髴土P惡意驗(yàn)證者，并賠償被欺詐的客戶的損害。這種“信任但檢查”的方法在實(shí)時(shí)處理小額交易時(shí)取得平衡，因?yàn)轵?yàn)證者不會(huì)因?yàn)樯倭康腻X進(jìn)行作惡。

e時(shí)代開始時(shí)，所有驗(yàn)證者采用每個(gè)時(shí)代的隨機(jī)數(shù)將自己分配到分片中，從對(duì)應(yīng)分片的上個(gè)狀態(tài)區(qū)塊啟動(dòng)他們的狀態(tài)。接著，OmniLedger隨機(jī)分配每個(gè)驗(yàn)證者到多個(gè)樂觀驗(yàn)證者分組或一個(gè)核心驗(yàn)證者分組。分片策略文件制定了樂觀和核心驗(yàn)證者的數(shù)量，以及樂觀驗(yàn)證者分組的數(shù)量。最后，為保證任何不當(dāng)行為都被包含在分片內(nèi)，策略文件還定義了最大的樂觀驗(yàn)證交易的數(shù)額必須等于驗(yàn)證者的押金或收入。

交易被樂觀分組首先處理并生成樂觀驗(yàn)證區(qū)塊，這些區(qū)塊會(huì)作為核心驗(yàn)證者的輸入進(jìn)行重新驗(yàn)證， 核心驗(yàn)證者會(huì)并行運(yùn)行，并將樂觀分組處理后輸入?yún)^(qū)塊進(jìn)行重新組合以顯示最大化系統(tǒng)吞吐量。合法的交易會(huì)被打包進(jìn)行最終區(qū)塊，然后加入賬本并最終被包含進(jìn)行狀態(tài)區(qū)塊。然而，當(dāng)核心驗(yàn)證者檢測(cè)到不一致性，那么對(duì)應(yīng)樂觀驗(yàn)證的交易就會(huì)被排除，對(duì)非法區(qū)塊簽名的驗(yàn)證者會(huì)被識(shí)別并追究其責(zé)任，通過扣留任何獎(jiǎng)勵(lì)或?qū)⑵渑懦谕?。我們認(rèn)為具體的懲罰細(xì)節(jié)依賴于經(jīng)濟(jì)激勵(lì)方案，不在本文范圍內(nèi)。給予行為不端的最小激勵(lì)以及對(duì)樂觀驗(yàn)證安全性的可量化信任（參考圖5），客戶可以根據(jù)需要選擇利用實(shí)時(shí)處理和樂觀的最終保證，或等待交易最終確定。

image.png

6. 安全性分析

待補(bǔ)充

7. 實(shí)現(xiàn)

待補(bǔ)充

8. 評(píng)估

待補(bǔ)充

9. 相關(guān)工作

待補(bǔ)充

10. 局限性和未來工作

待補(bǔ)充

11. 結(jié)論

待補(bǔ)充

參考資料

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: 中心化抵抗協(xié)議

OmniLedger部分解決的先前工作中存在的一個(gè)問題是惡意分片領(lǐng)導(dǎo)者中心化審查交易。從分片中其它驗(yàn)證者是無法檢測(cè)這種攻擊的。只要符合狀態(tài)，領(lǐng)導(dǎo)者不提議交易是可以接受的，但這種攻擊可能會(huì)損害系統(tǒng)公平性或被用作強(qiáng)制工具。

基于這個(gè)原因，我們使驗(yàn)證者請(qǐng)求被提交的交易，因?yàn)樗麄冋J(rèn)為交易被審查了。他們可以通過正常的八卦過程或直接從客戶端接收請(qǐng)求來收集這些交易。這個(gè)協(xié)議可以定期執(zhí)行（比如每10個(gè)區(qū)塊）。我們表示存在 N = 3f+個(gè)驗(yàn)證者，其中最多f個(gè)為不誠實(shí)的。

image.png

圖12的流程：

• 從(1)開始，每個(gè)驗(yàn)證者提出一些盲目的反審查交易，以啟動(dòng)共識(shí)過程。領(lǐng)導(dǎo)者應(yīng)該將所有的交易加入?yún)^(qū)塊，然而他能控制f個(gè)誠實(shí)提議者?？傊鼘?duì)來自誠實(shí)驗(yàn)證者f個(gè)交易輸入是盲目的，他會(huì)達(dá)成共識(shí)。一旦共識(shí)結(jié)束，(2)中的交易列表有資格獲得反審查，這些是提議子集。因?yàn)榻灰资敲つ康?，在共識(shí)結(jié)束前，沒有其它驗(yàn)證者能知道哪些是被提議的。每個(gè)驗(yàn)證者揭示他選擇的交易(3)，驗(yàn)證者檢查交易是合法的，然后對(duì)他們期望領(lǐng)導(dǎo)者提議的交易進(jìn)行共識(shí)。那么，領(lǐng)導(dǎo)者被迫打包符合狀態(tài)一致的交易(4)，否則誠實(shí)驗(yàn)證者會(huì)啟動(dòng)視圖轉(zhuǎn)換[13]。

附件B: 破壞網(wǎng)絡(luò)模型

雖然假定非靜態(tài)驗(yàn)證者分組的去中心賬本具有類似的同步[34][36]假設(shè)，這里我們討論如果攻擊者成功破壞了網(wǎng)絡(luò)會(huì)發(fā)生什么。這種情況下，我們檢測(cè)到攻擊，然后提供備份的已知不可擴(kuò)展但在異步情況下也保證安全的隨機(jī)數(shù)生成機(jī)制。

假設(shè)RandHound在不需要同步時(shí)保證安全，攻擊者控制網(wǎng)絡(luò)最多只能拖慢他沒有控制的其它驗(yàn)證者，然后總是贏得領(lǐng)導(dǎo)者。然而這不會(huì)是攻擊者控制RandHound，這只是給他可以重啟協(xié)議的優(yōu)勢(shì)，如果他不喜歡生成的隨機(jī)數(shù)。這個(gè)重啟可被網(wǎng)絡(luò)可見，然后當(dāng)有多次集體RandHound開始失敗時(shí)，其它參與者可以懷疑其存在偏向嘗試。

OmniLedger可以提供一個(gè)安全閥門機(jī)制來緩解這個(gè)問題。當(dāng)有5次RandHound視圖連續(xù)失敗時(shí)，在正常情況下這種情況發(fā)生的概率為1%，所有驗(yàn)證者將RandHound切換為運(yùn)行一個(gè)完全異步的擲硬幣協(xié)議[12]，該協(xié)議使用公開可驗(yàn)證的密鑰共享(Publicly Verifiable Secret Sharing )[43]來生成時(shí)代隨機(jī)數(shù)。這個(gè)協(xié)議擴(kuò)展性很差(O(n**3))，但是當(dāng)網(wǎng)絡(luò)處于被攻擊和活性沒法保證時(shí)，它可以保證工作。這種情況下安全是最重要的。

附件C: 跨分片交易的可能性

這節(jié)探討跨分片交易對(duì)系統(tǒng)性能的影響。當(dāng)將狀態(tài)拆分成不相交的部分時(shí)，通常的實(shí)踐是基于哈希的首比特來分配UTXO給分片。例如， 一個(gè)分片管理所有首比特為0的UTXO，第二個(gè)分片管理所有首比特為1的UTXO。每個(gè)分片由保持狀態(tài)一致和提交更新的一組驗(yàn)證者管理。

對(duì)于分片內(nèi)交易，我們想要交易的所有輸入和輸出都分配給相同的分片，從密碼哈希函數(shù)的隨機(jī)性保證中，隨機(jī)地分配UTXO到分片中的概率是均勻的。

令m為為分片的總數(shù)，n為輸入和輸出UTXO的總素，k為需要參與跨分片交易的驗(yàn)證的分片數(shù)。那么能計(jì)算的概率為：

image.png

對(duì)一個(gè)普通的2個(gè)輸入和1個(gè)輸出的交易和3個(gè)分片的配置，分片內(nèi)交易的可能性為P(3,1,3) = 3.7%，假設(shè)交易只觸及一個(gè)分片有問題。結(jié)果如果所有交易都是這種格式，從一個(gè)分片到4個(gè)分片配置所期望的提速僅為

image.png

附件D: Atomix對(duì)有狀態(tài)對(duì)象的應(yīng)用

圖13描述了第4章Atomix協(xié)議實(shí)現(xiàn)的一個(gè)狀態(tài)機(jī)。

image.png

為了在智能合約中使用這種算法，我們需要考慮智能合約對(duì)象是否可變以及正當(dāng)理由下可并發(fā)訪問的事實(shí)。結(jié)果我們需要在兩個(gè)方面修改算法：

1. 解鎖交易需要同時(shí)發(fā)送給輸入分片和輸出分片
2. 狀態(tài)機(jī)需要一個(gè)新的狀態(tài)因?yàn)榉制谛枰怄i前等待確認(rèn)。

這是必要的，因?yàn)榇嬖谶@樣的機(jī)會(huì)使全狀態(tài)對(duì)象被再次訪問，這樣如果Atomix決定取消時(shí)可能會(huì)與先輸入后輸出的依賴相沖突。

image.png

圖14，我們看到對(duì)象被一個(gè)交易(T)鎖住，會(huì)拒絕任何其它同步交易(T')，直到T被提交并且新的狀態(tài)S'已經(jīng)有效，或者被取消后恢復(fù)原先的狀態(tài)S。

(OmniLedger通過客戶端來指定分片，分片之間沒有直接通信，那么OmniLeger如何處理跨合約調(diào)用接口的情況？)