B. 交易處理和UTXO模型

去中心化賬本從區(qū)塊鏈或一條包含交易的完全有序區(qū)塊繼承了現(xiàn)在的系統(tǒng)狀態(tài)蚌斩。基于其簡(jiǎn)單性和可并行性范嘱，OmniLedger接受UTXO模型來(lái)代表賬本狀態(tài)送膳。在這個(gè)模型里，一個(gè)交易的輸出創(chuàng)建新的UTXO并授予其信用丑蛤，交易的輸入則完全花費(fèi)已存在的UTXO叠聋。在新的全節(jié)點(diǎn)啟動(dòng)時(shí)，會(huì)同步抓取整個(gè)賬本并建立合法UTXO的數(shù)據(jù)庫(kù)以便用于后續(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)境里可提供無(wú)偏見(jiàn)的、去中心化的隨機(jī)性厦章。RandHound假設(shè)存在一個(gè)外部負(fù)責(zé)任的客戶(hù)镇匀，他想從一大群半信任化的服務(wù)器中獲取可證明的隨機(jī)性。為了產(chǎn)生隨機(jī)性袜啃，RandHound將服務(wù)器組拆分更小的組汗侵，并創(chuàng)建一個(gè)公開(kāi)可驗(yàn)證的先提交后揭示(commit-then-reveal)的協(xié)議[43]，該協(xié)議采用鴿籠原理在包括至少一名誠(chéng)實(shí)參與者貢獻(xiàn)時(shí)來(lái)證明最終的隨機(jī)數(shù)群发，因此完美地實(shí)現(xiàn)了對(duì)RandHound輸出的隨機(jī)化晰韵。

加密抽簽(Cryptographic sortition)[25]用來(lái)根據(jù)驗(yàn)證者權(quán)重函數(shù)對(duì)驗(yàn)證者選擇一個(gè)子集。為了使驗(yàn)證者能夠證明他們屬于某個(gè)選中的子集熟妓，他們需要一個(gè)公鑰和私鑰對(duì)雪猪，(pki, ski)。抽簽通過(guò)一個(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)證者都是已知的，無(wú)權(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開(kāi)頭）产艾。Bitcoin-NG[21]使用同樣的PoW技術(shù)以產(chǎn)生抗女巫攻擊的身份疤剑。PoW機(jī)制本身有一些問(wèn)題，比如浪費(fèi)電力以及導(dǎo)致礦池重新中心化的事實(shí)闷堡。其它的抵抗女巫攻擊的方法還有采用諸如PoS[31][25]隘膘、Proof-of-Burn(PoB)[46]、Proof-of-Personhood[8]等可以克服PoW的問(wèn)題杠览，并且可以兼容ByzCoin的身份區(qū)塊鏈弯菊，當(dāng)然也兼容OmniLedger。

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

OmniLedger和先前探討過(guò)的在無(wú)權(quán)限賬本上實(shí)現(xiàn)分片的Elastico是很接近的踱阿。在每一輪管钳，Elastico利用PoW哈希中最低比特位來(lái)分發(fā)礦工給不同的分片，然后每個(gè)分片運(yùn)行PBFT[13]來(lái)達(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)抗偏見(jiàn)的怀喉，因此礦工可以選擇性的忽視PoW來(lái)得到特定的結(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)證者來(lái)處理交易和保證系統(tǒng)狀態(tài)的一致性;
• 每個(gè)驗(yàn)證者i有公鑰和私鑰對(duì)(pki, ski)回季，我們通過(guò)pki來(lái)識(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è)分片處理從客戶(hù)收集到的交易
• 假設(shè)驗(yàn)證者可以通過(guò)任務(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) 誠(chéng)實(shí)驗(yàn)證者的網(wǎng)絡(luò)是良好連接的；b) 誠(chéng)實(shí)驗(yàn)證者的通信通道是同步的钝吮，也就是說(shuō)一個(gè)誠(chéng)實(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é)議使用樂(lè)觀地部分同步模型[13]醇坝，而?則用來(lái)進(jìn)行諸如身份創(chuàng)建和分片分配之類(lèi)的緩慢操作邑跪。

C. 威脅模型

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

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

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

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

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

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

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

我們從安全驗(yàn)證者分配到分片開(kāi)始。允許驗(yàn)證者選擇他們想要驗(yàn)證的分片是不安全的拦宣，因?yàn)楣粽呖梢詫⑺衅潋?yàn)證者集中一個(gè)分片中截粗。因此信姓，我們需要一個(gè)隨機(jī)源來(lái)保證一個(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開(kāi)始參與SLedger的驗(yàn)證者珊蟀，必須先在一個(gè)全局身份區(qū)塊鏈上注冊(cè)身份菊值，在時(shí)間周期e-1內(nèi)他們通過(guò)抗女巫攻擊機(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)者開(kāi)始，該領(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]來(lái)決定將自己分配到SLedger中的其中一個(gè)分片上恩够，然后從相應(yīng)分片的分布式賬本中同步啟動(dòng)內(nèi)部狀態(tài)卒落。那么，他們就準(zhǔn)備好開(kāi)始使用ByzCoin的共識(shí)機(jī)制來(lái)處理交易了蜂桶。隨機(jī)的分片分配機(jī)制保證了在一個(gè)給定分片中惡意和誠(chéng)實(shí)驗(yàn)證者的比例與在所有驗(yàn)證者中的惡意和誠(chéng)實(shí)的比例是最有可能相接近的儡毕。

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

• 首先腰湾，隨機(jī)信標(biāo)是一個(gè)可信任的第三方機(jī)構(gòu)。
• 在每個(gè)時(shí)代開(kāi)始時(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)開(kāi)銷(xiāo)沼死。
• 最后，SLedger不能提供實(shí)時(shí)確認(rèn)和高吞吐量票从。

為解決這些安全問(wè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é)議锥咸。

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

4. 在5-A節(jié)搏予，我們介紹ByzCoinX，一個(gè)ByzCoin的變種弧轧，可利用更加健壯的通信模型來(lái)高效地處理分片內(nèi)部的交易雪侥，即使一些驗(yàn)證者失敗了；可在交易級(jí)別解決依賴(lài)性以實(shí)現(xiàn)更好的區(qū)塊并行化精绎。
5. 在5-C節(jié)速缨，我們介紹狀態(tài)區(qū)塊(state block)，其匯總了一個(gè)時(shí)代的分片狀態(tài)代乃，可為驗(yàn)證者縮減賬本以降低存儲(chǔ)和啟動(dòng)開(kāi)銷(xiāo)旬牲。
6. 在5-D節(jié)，我們展示通過(guò)利用信任但驗(yàn)證的分片內(nèi)交易驗(yàn)證方式(an intra-shard architecture with trust-but-verify transaction validation)搁吓，如何在不犧牲安全性或吞吐量的情況下進(jìn)行樂(lè)觀實(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ù)種子擎浴，我們依賴(lài)于一種由驗(yàn)證者們共同執(zhí)行的分布式隨機(jī)數(shù)生成協(xié)議员咽。

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

因?yàn)镽andHound依靠領(lǐng)導(dǎo)者來(lái)協(xié)調(diào)協(xié)議運(yùn)行，我們需要一個(gè)合理的機(jī)制來(lái)從驗(yàn)證者中選舉一個(gè)出來(lái)银伟。如果我們使用確定性方法來(lái)執(zhí)行領(lǐng)導(dǎo)人選舉你虹，那么攻擊者通過(guò)拒絕運(yùn)行協(xié)議绘搞，在最壞的情況下可能達(dá)到f/n的失敗率，在我們的模型中會(huì)有高達(dá)n/4的失敗率傅物。因此夯辖，領(lǐng)導(dǎo)選舉機(jī)制必須是不可預(yù)測(cè)和無(wú)偏性的，但當(dāng)我們?cè)诘谝淮问褂肦andHound時(shí)董饰，就碰到了先有雞還是現(xiàn)有蛋的問(wèn)題蒿褂。（因?yàn)槲覀冃枰猂andHound來(lái)產(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í)代開(kāi)始，每個(gè)驗(yàn)證者i計(jì)算一張門(mén)票:
   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)證者們開(kāi)始相互傳播他們的門(mén)票诈嘿，持續(xù)一個(gè)時(shí)間?堪旧，之后他們鎖定一個(gè)他們迄今看到的最小的合法門(mén)票，并接收該門(mén)票對(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)證者排除在外，即使他后來(lái)上線了遂蛀。
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]來(lái)計(jì)算1,...,n的π[e]排列谆扎，
   • 再將結(jié)果分配到大小都為m的水桶里(bukets)，因此決定將哪些節(jié)點(diǎn)分配到哪個(gè)分片芹助。

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

• 每個(gè)參與者在e時(shí)代的每個(gè)視圖v只能產(chǎn)生一個(gè)合法的門(mén)票状土，因?yàn)榛?code>VRF的領(lǐng)導(dǎo)選舉只能在身份區(qū)塊鏈中合法的身份已經(jīng)固定時(shí)才能開(kāi)始无蜂。
• 只要非串通節(jié)點(diǎn)的門(mén)票對(duì)應(yīng)的私鑰(ski)是保密的，VRF的輸出就是不可預(yù)測(cè)的蒙谓。因此最后抽獎(jiǎng)的結(jié)果就是不可預(yù)測(cè)的斥季。
• 同步時(shí)間?保證誠(chéng)實(shí)節(jié)點(diǎn)的門(mén)票可以被所有其它誠(chéng)實(shí)節(jié)點(diǎn)接收看到。
• 如果攻擊者贏得抽獎(jiǎng)累驮，他可以決定遵循并運(yùn)行RandHound協(xié)議酣倾，或者讓其失敗舵揭，這樣該節(jié)點(diǎn)就會(huì)在本時(shí)代接下來(lái)的時(shí)間被排除在外。
• 在成功運(yùn)行RandHound之后躁锡，攻擊者首先掌握了隨機(jī)數(shù)午绳，進(jìn)行分片分配，但是他能得到的好處很小稚铣。
• 攻擊者可以選擇選擇合作并發(fā)布隨機(jī)值箱叁，或者保留它以期望再次贏得抽獎(jiǎng)，并獲得最符合他要求的分片分配任務(wù)惕医。
• 但是耕漱，一個(gè)攻擊者抽獎(jiǎng)連續(xù)贏得a次的的概率是按照公式
  image.png
  指數(shù)級(jí)下降的。
• 因此抬伺，經(jīng)過(guò)幾輪重新抽獎(jiǎng)螟够，誠(ché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ù)給客戶(hù)近忙，同時(shí)新加入的驗(yàn)證者同步進(jìn)行啟動(dòng)竭业。為了實(shí)現(xiàn)這種持續(xù)的操作，我們可以轉(zhuǎn)移出最多1/3分片大小(約為n/m)的驗(yàn)證者數(shù)量及舍，轉(zhuǎn)出數(shù)量越多永品，剩余的誠(chéng)實(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])來(lái)計(jì)算分片驗(yàn)證者的排列π[j,e]肯腕，并且我們指定批次排列献宫。
3. 同時(shí)計(jì)算另一個(gè)種子H(0 || rnd[e])，來(lái)置換和分散新加入e時(shí)代的驗(yàn)證者实撒，并定義按照什么順序進(jìn)行（大小也為k）姊途。
4. 定義好隨機(jī)排列后，每批次等待時(shí)間?再開(kāi)始啟動(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ù)量的誠(chéng)實(shí)驗(yàn)證者愿意參與共識(shí)。
• 我們使用時(shí)代隨機(jī)數(shù)rnd[e]來(lái)獲得批次排列其做，針對(duì)自適應(yīng)攻擊者我們保持分片配置是一個(gè)移動(dòng)目標(biāo)顶考。
• 只要有2/3 * n/m誠(chéng)實(shí)和保持更新的節(jié)點(diǎn)，分片活性就可以保證妖泄。
• 反之如果轉(zhuǎn)換期間未達(dá)到法定人數(shù)(新批次的誠(chéng)實(shí)驗(yàn)證者還沒(méi)更新完成)驹沿，分片活性會(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)闆](méi)有一種直接的方式可以回退半提交的交易，在沒(méi)有添加可利用的競(jìng)爭(zhēng)條件時(shí)雀鹃。

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

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

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

1. 初始化：客戶(hù)端創(chuàng)建一個(gè)跨分片交易(cross-Tx)更胖，輸入U(xiǎn)TXO來(lái)自輸入分片(IS)，輸出創(chuàng)建新的UTXO來(lái)自輸出分片(OS)隔显∪捶粒客戶(hù)端八卦(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ū)塊的被簽名的默克爾樹(shù)證明德频。
   • 如果交易被拒絕苍息，領(lǐng)導(dǎo)者創(chuàng)建一個(gè)相似的拒絕證明(proof-of-rejection)，其中特定比特位來(lái)表示接受或拒絕壹置。
   • 客戶(hù)端可以利用每個(gè)(IS)賬本來(lái)檢查其證明以確認(rèn)該交易確實(shí)被鎖住竞思。
   • 當(dāng)所有(IS)已經(jīng)處理了鎖請(qǐng)求，客戶(hù)端就具有足夠的證明來(lái)提交交易钞护，或取消交易并回收任何鎖定的資金盖喷。
3. 解鎖：根據(jù)鎖階段的結(jié)果，客戶(hù)端可以提交交易或取消交易难咕。
   • 解鎖提交: 如果所有的(IS)領(lǐng)導(dǎo)者都返回了接受證明课梳，那么對(duì)應(yīng)的交易就可以被提交距辆。客戶(hù)端(或超時(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)返回了拒絕證明雾消，那么該交易就無(wú)法提交灾搏，必須被取消。為了回收上階段被鎖住的資金立润，客戶(hù)端(或其它實(shí)體)必須請(qǐng)求介入的(IS)解鎖特定的交易狂窑，通過(guò)八卦一個(gè)解鎖取消交易(unlock-to-abort transaction)，其中包括至少一個(gè)輸入U(xiǎn)TXO的拒絕證明桑腮。輸入分片(IS)領(lǐng)導(dǎo)者接收到解鎖請(qǐng)求后泉哈，會(huì)進(jìn)行類(lèi)似的步驟并標(biāo)記原先的UTXO重新可花費(fèi)。
     
     image.png

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

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

• 基于我們的假設(shè)，分片是誠(chéng)實(shí)的撑柔，不會(huì)失敗瘸爽，最終都收到所有消息并達(dá)到BFT共識(shí)，那么
  1. 所有分片都忠誠(chéng)地處理合法交易铅忿；
  2. 如果所有輸入分片返回接收證明剪决，那么每個(gè)輸出分片都進(jìn)行解鎖提交；
  3. 即使只有一個(gè)輸入分片返回拒絕證明辆沦，那么所有輸入分片都解鎖取消昼捍；
  4. 即使只有一個(gè)輸入分片返回拒絕證明，那么沒(méi)有輸出分片需要解鎖提交肢扯。
• 在Atomix中妒茬，每個(gè)cross-TX會(huì)被提交或取消∥党浚基于(1)乍钻，每個(gè)分片只返回一個(gè)回應(yīng)：接受證明或拒絕證明肛循。因此客戶(hù)端用后所需數(shù)量的證明時(shí)，那么針對(duì)每個(gè)輸入U(xiǎn)TXO只會(huì)擁有接受證明或拒絕證明银择，而不會(huì)兩者同時(shí)擁有多糠。
• 在Atomix中，沒(méi)有cross-TX會(huì)被雙花浩考。如上所示夹孔，跨分片交易都是原子性，并且只被分配給專(zhuān)門(mén)負(fù)責(zé)它們的特定分片析孽〈钌耍基于(1)，被分配的分片不會(huì)對(duì)同一個(gè)交易處理兩次袜瞬，沒(méi)有其它分片會(huì)進(jìn)行解鎖提交怜俐。
• 在Atomix中，如果一個(gè)交易無(wú)法提交邓尤，那么鎖定的資金會(huì)被回收拍鲤。如果一個(gè)交易無(wú)法提交，說(shuō)明至少有一個(gè)分片返回了拒絕證明汞扎。當(dāng)所有的輸入分片解鎖取消后季稳，所有資金重新可用。

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

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

解鎖交易的大猩秆琛：在Atomix中磁玉，解鎖交易會(huì)比普通的交易更大，由于相應(yīng)的輸入U(xiǎn)TXO的證明需要被包含驾讲。OmniLedger依賴(lài)ByzCoinX來(lái)處理每個(gè)分片內(nèi)的交易蚊伞。當(dāng)分片的驗(yàn)證者對(duì)包含已提交交易的區(qū)塊達(dá)成一致時(shí)，他們產(chǎn)生一個(gè)集體簽名蝎毡，該簽名的大小與驗(yàn)證者的數(shù)量無(wú)關(guān)厚柳。這個(gè)重要的特性可以使我們保持Atomix證明足夠短，即使每個(gè)交易的合法性都是通過(guò)所有輸入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ǔ)開(kāi)銷(xiāo)扇商。最后我們提出一種可選的“信任但驗(yàn)證”的二層驗(yàn)證機(jī)制來(lái)對(duì)小風(fēng)險(xiǎn)交易進(jìn)行實(shí)時(shí)確認(rèn)凤瘦。

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

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

為實(shí)現(xiàn)OmniLedger更好的容錯(cuò)壁酬，又不采用PBFT全方位的通信模式次酌，我們引入ByzCoinX作為一種新的通信模式恨课，代價(jià)是為了健壯性犧牲掉一些ByzCoin的高性能。方法是通過(guò)將共識(shí)組內(nèi)的消息傳播機(jī)制更改為類(lèi)似于兩級(jí)樹(shù)岳服。OmniLedger在一個(gè)時(shí)代的設(shè)置期間剂公，產(chǎn)生的隨機(jī)數(shù)不僅用來(lái)驗(yàn)證者到分片的分配，同時(shí)也將驗(yàn)證者分配給分片內(nèi)的相應(yīng)組吊宋。組的數(shù)量g纲辽，其中通過(guò)考慮保存在分片策略文件中的分片大小可以導(dǎo)出最大的組大小。在ByzCoinX的開(kāi)始輪次中璃搜，協(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)沒(méi)有回復(fù)这吻，協(xié)議領(lǐng)導(dǎo)者重新隨機(jī)選擇一個(gè)組領(lǐng)導(dǎo)者來(lái)代替失效的那個(gè)吊档。一旦協(xié)議領(lǐng)導(dǎo)者接收到超過(guò)2/3的驗(yàn)證者認(rèn)可，他就馬上進(jìn)入?yún)f(xié)議的下一步唾糯。如果協(xié)議領(lǐng)導(dǎo)者失效怠硼，所有驗(yàn)證者發(fā)起一個(gè)類(lèi)似PBFT的視圖改變步驟。
(備注：這里的協(xié)議領(lǐng)導(dǎo)者是指分片內(nèi)的領(lǐng)導(dǎo)嗎移怯？怎么產(chǎn)生的香璃？)

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

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

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

• 定義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)(或相反)
• 為解決問(wèn)題1)，兩個(gè)交易只有其中一個(gè)才能被提交
• 為解決問(wèn)題2)堵腹，tx[A]需要比tx[B]優(yōu)先提交炸站，也就是說(shuō)tx[B]所在區(qū)塊必須依賴(lài)tx[A]所在的區(qū)塊。
• 所有不包括以上兩種情況的交易都可以被安全地并行處理疚顷。
• 特別是旱易，我們說(shuō)信任相同地址的交易不會(huì)產(chǎn)生沖突，因?yàn)樗麄儺a(chǎn)生不同的UTXO腿堤。

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

C. 分片賬本削減

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

為了使那些經(jīng)常重新分配分片的驗(yàn)證者減小存儲(chǔ)和啟動(dòng)開(kāi)銷(xiāo)证薇，我們引入狀態(tài)區(qū)塊(state blocks)，它和PBFT[13]中的固定檢查點(diǎn)很類(lèi)似匆篓，就是匯總分片賬本的全部狀態(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è)排序的默克爾樹(shù)，并將樹(shù)根哈希存入sb[j, e]區(qū)塊頭部甩骏。
• 然后分片驗(yàn)證者對(duì)sb[j, e]區(qū)塊頭部運(yùn)行共識(shí)（注意每個(gè)驗(yàn)證者都可以構(gòu)造相同的排序默克爾樹(shù)進(jìn)行驗(yàn)證）窗市。
• 如果共識(shí)成功，領(lǐng)導(dǎo)者將通過(guò)的區(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ū)塊的頭部宪迟，客戶(hù)端通過(guò)提交一個(gè)交易被提交的區(qū)塊的包含證明不能向其它實(shí)體證明一個(gè)過(guò)去交易的存在穿仪。我們解決這個(gè)問(wèn)題通過(guò)移除客戶(hù)端保存交易存在證明的責(zé)任只锻。在e+1時(shí)代期間，客戶(hù)端可以使用e時(shí)代的常規(guī)區(qū)塊和狀態(tài)區(qū)塊來(lái)生成e時(shí)代已驗(yàn)證交易的存在證明。對(duì)于給定交易tx的這種證明包含對(duì)e時(shí)代提交交易'tx'的常規(guī)區(qū)塊B的默克爾樹(shù)包含證明羹膳，以及時(shí)代結(jié)束時(shí)的狀態(tài)區(qū)塊sb[j, e]和區(qū)塊B的順序區(qū)塊頭。為減小這些證明的大小醒颖，狀態(tài)區(qū)塊可包含多個(gè)多跳反向指針指向類(lèi)似skipchains[37]的中間常規(guī)區(qū)塊的頭部。

最后腰耙，如果我們天真地去實(shí)現(xiàn)狀態(tài)區(qū)塊的創(chuàng)建，它會(huì)阻礙時(shí)代的啟動(dòng)选侨，因?yàn)橹钡?code>sb[j, e]已經(jīng)被寫(xiě)入賬本交易才開(kāi)始處理。為避免這種停機(jī)時(shí)間隘谣，e+1時(shí)代分片中的所有驗(yàn)證者在時(shí)代開(kāi)始時(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ì)有利于安全性超過(guò)可擴(kuò)展性颅痊，我們悲觀地假設(shè)一個(gè)對(duì)手控制著25％的驗(yàn)證者钳榨，因此营罢，選擇大的分片會(huì)以更高的延遲為代價(jià)，但保證交易的最終性吃型。然而這個(gè)假設(shè)不能恰當(dāng)?shù)胤从衬切┚哂蓄l繁使用、延遲敏感但低價(jià)值交易的客戶(hù)的優(yōu)先級(jí)（比如赐写，雜貨店支付，購(gòu)買(mǎi)汽油或咖啡等），他們喜歡交易處理地越快越好沦补。

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

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

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

image.png

6. 安全性分析

待補(bǔ)充

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

待補(bǔ)充

8. 評(píng)估

待補(bǔ)充

9. 相關(guān)工作

待補(bǔ)充

10. 局限性和未來(lái)工作

待補(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è)問(wèn)題是惡意分片領(lǐng)導(dǎo)者中心化審查交易衣屏。從分片中其它驗(yàn)證者是無(wú)法檢測(cè)這種攻擊的。只要符合狀態(tài)，領(lǐng)導(dǎo)者不提議交易是可以接受的窘俺，但這種攻擊可能會(huì)損害系統(tǒng)公平性或被用作強(qiáng)制工具。

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

image.png

圖12的流程：

• 從(1)開(kāi)始，每個(gè)驗(yàn)證者提出一些盲目的反審查交易肿孵，以啟動(dòng)共識(shí)過(guò)程烙丛。領(lǐng)導(dǎo)者應(yīng)該將所有的交易加入?yún)^(qū)塊寒瓦，然而他能控制f個(gè)誠(chéng)實(shí)提議者。總之乾翔，它對(duì)來(lái)自誠(chéng)實(shí)驗(yàn)證者f個(gè)交易輸入是盲目的，他會(huì)達(dá)成共識(shí)尖殃。一旦共識(shí)結(jié)束，(2)中的交易列表有資格獲得反審查走敌，這些是提議子集拌禾。因?yàn)榻灰资敲つ康钠酶鳎诠沧R(shí)結(jié)束前芳肌，沒(méi)有其它驗(yàn)證者能知道哪些是被提議的。每個(gè)驗(yàn)證者揭示他選擇的交易(3)，驗(yàn)證者檢查交易是合法的，然后對(duì)他們期望領(lǐng)導(dǎo)者提議的交易進(jìn)行共識(shí)右锨。那么瞬测，領(lǐng)導(dǎo)者被迫打包符合狀態(tài)一致的交易(4)横媚，否則誠(chéng)實(shí)驗(yàn)證者會(huì)啟動(dòng)視圖轉(zhuǎn)換[13]。

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

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

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

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

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

這節(jié)探討跨分片交易對(duì)系統(tǒng)性能的影響。當(dāng)將狀態(tài)拆分成不相交的部分時(shí)画拾，通常的實(shí)踐是基于哈希的首比特來(lái)分配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è)分片有問(wèn)題邮屁。結(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ā)訪問(wèn)的事實(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ì)象被再次訪問(wèn)，這樣如果Atomix決定取消時(shí)可能會(huì)與先輸入后輸出的依賴(lài)相沖突殉了。

image.png

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

(OmniLedger通過(guò)客戶(hù)端來(lái)指定分片隔箍，分片之間沒(méi)有直接通信田轧，那么OmniLeger如何處理跨合約調(diào)用接口的情況？)