聯(lián)合譯者：Wendy, Lise

今天給大家?guī)淼囊廊皇且黄夹g(shù)流的文章财著，該文章是由r/btc在2018年9月9日發(fā)表的，英文原文題目為：《A Technical Dive into CTOR》抓狭。

對CTOR的技術(shù)性解析

在過去幾天里，我一直在深入探究CTOR的各個方面造烁，其針對11月硬分叉所做的調(diào)整可謂聲名狼藉。在這篇文章里午笛，我要對CTOR的基本特質(zhì)惭蟋、代碼形態(tài)、工作性能药磺、算法以及前景進行具體的闡述告组。如果有人覺得CTOR的調(diào)整神秘且含糊不清，希望這篇文章能夠為他們答疑解惑癌佩。

TTOR木缝、CTOR及AOR分別是什么？

目前BCH區(qū)塊的交易排序方式有多種可能围辙。這其中交易拓撲排序規(guī)則（TTOR）指的是：對于有局部排序需求的交易必須依照因果關系進行排序我碟，即如果一筆交易的支出(input)采用了另一筆交易的輸出值（output)，那么這筆交易在區(qū)塊里排序時必須在那一筆交易之后姚建，在數(shù)學上這種排序被描述為區(qū)塊內(nèi)交易圖的拓撲排序矫俺。

然而，將于2018年11月進行的BCH硬分叉計劃將排序規(guī)則變更為交易規(guī)范排序規(guī)則(CTOR)掸冤，將對區(qū)塊內(nèi)一的交易集合厘托，有效排序只有一種（因而稱之為“規(guī)范”），未來任何偏離這一排序規(guī)則的區(qū)塊將被視為無效稿湿。這一被加入到11月的硬分叉的升級功能铅匹，其實質(zhì)是基于交易ID的一種字符排序（按字符順序）。需要注意的是所有的交易均按交易ID的順序排列饺藤，除了幣基交易（coinbase),它必須始終排在最前面包斑。交易規(guī)范排序規(guī)則的精確描述是“幣基交易優(yōu)先流礁，然后根據(jù)交易ID進行升序排列”。

還有一種排規(guī)則被稱為任意排序規(guī)則(AOR)舰始，它則完全取消了對于交易排序的限制（除了幣基交易依然必須在最前）崇棠。雖然尚未有人嚴肅地提出AOR提案，但這個規(guī)則在我們下面的談論中這一排序規(guī)則很重要丸卷。

兩個變化：取消舊有排序(TTOR->AOR)枕稀，安裝新的排序(AOR->CTOR)。

預定于11月的升級將上述兩個變化結(jié)合到一個步驟：

1.????取消舊有的因果規(guī)則：現(xiàn)在支出交易可以排在同一區(qū)塊其使用的輸出數(shù)據(jù)前面谜嫉。

2.????增加修正區(qū)塊中所有交易排序的新規(guī)則萎坷。

在本文當中我將這兩個步驟(TTOR->AOR, AOR->CTOR)區(qū)分開來，因為我覺著這有助于闡明各個元素受到硬分叉調(diào)整的影響沐兰。

Bitcoin ABC的代碼調(diào)整

BitcoinABC對從0.17.1版本升級的0.18.1版本（目前正在編寫的版本）改變了幾千條線的代碼哆档，其差別可以通過github查閱，這些調(diào)整絕大部分看似各種代碼重構(gòu)住闯、代碼風格變化等等瓜浸，通過搜索”MagneticAnomaly"，可以找到11月硬分叉時將會激活的相應代碼比原，變量magneticanomalyactivationtime?設定了新規(guī)將要激活的時間插佛。

在文件?src/validation.cpp中可以找到交易排序相關的主要調(diào)整：

·???????功能ConnectBlock?以前有一個回路，能夠依次處理每筆交易量窘，刪除已達成交易的輸出數(shù)據(jù)雇寇，加入新交易輸出數(shù)據(jù)，該功能僅與TTOR兼容蚌铜。從11月開始锨侯，它將采用雙回路OTI算法（如下），新構(gòu)造并無排序需求冬殃。

·???????功能ApplyBlockUndo用于撤銷孤立塊囚痴，將被調(diào)整為適應任何排序。

·???????功能ContextualCheckBlock將包含直接檢查分類排序（僅有幾行代碼執(zhí)行CTOR）

此外還有其他調(diào)整：

·???????針對挖礦(src/mining.cpp)造壮，?CreateNewBlock將根據(jù)CTOR開始對交易進行分類渡讼。

·???????當孤立一個區(qū)塊時，交易將通過使用addForBlock返回內(nèi)存池耳璧，現(xiàn)在該功能適用于任何排序(src/txmempool.cpp)成箫。

算法

串行塊處理（一個線程）

確認區(qū)塊的最重要步驟之一是更新未使用交易輸出(UTXO)集合，在這一過程當中如果探測到UTXO的雙重支付旨枯，則宣告其無效蹬昌。

比特幣處理區(qū)塊的標準方式是在交易當中一個接一個地循環(huán)，刪除已用輸出數(shù)據(jù)攀隔，然后加入新的輸出數(shù)據(jù)皂贩。這種簡單粗暴的方式需要精準的拓撲排序栖榨，否則就會失敗（因此它自動校驗了TTOR）明刷。在偽代碼當中：

for tx intransactions:

??? remove_utxos(tx.inputs)

??? add_utxos(tx.outputs)

值得注意的是婴栽，現(xiàn)代的實施方式不會馬上應用這些調(diào)整，而是將增添/刪除存進一個認可用量辈末。在校驗完成后愚争，該認可用量適用于批次UTXO數(shù)據(jù)庫。

通過將它分成兩個回路挤聘，以不在意排序的方式更新UTXO集合成為可能轰枝，這被稱為輸出-然后-輸入(OTI)算法。

for tx in transactions:

???add_utxos(tx.outputs)

for tx in transactions:

???remove_utxos(tx.inputs)

Bitcoin ABC的Jonathan Toomim和ElectrumX的我本人制定的標準表明组去，OTI的兩個回路性能代償（相對于一個回路版本）微不足道鞍陨。

并行塊處理

UTXO更新實際形成一個區(qū)塊處理所需的重要時間片段薯蝎，如果能將它們并行將大有助益肤频。

有一些區(qū)塊校驗并行算法要求擬拓撲排序來正確行使功能饼齿。例如尉共，一開始多個工作人員可以處理上述的標準回路，如果UTXO尚不存在钦扭，一位工作人員就要暫停兔乞，因為可能另一位工作人員將很快生成那個UTXO传透。

這類對排序敏感的并行塊處理算法存在如下問題：

·???????由于TTOR將成為共識規(guī)則艾杏，并行校驗算法也必須在尊重TTOR的基礎上進行驗證。以上所述看似天真的方法實際能夠勝任一些非拓撲排序盅藻，因此為了實行TTOR,需要增添額外的檢驗购桑。

·???????最壞情況下的表現(xiàn)是依次僅一個線程激活，要考慮下區(qū)塊是一個由相互依賴交易組成的長鏈的情況氏淑。

比較而言勃蜘，OTI算法回路是完全可并行的：工作線程可以以任意排序獨立運行，并碰觸交易假残。直到最近缭贡，OTI才被認為無法校驗TTOR，因此撤銷TTOR?的一個理由就是允許調(diào)整為并行OTI辉懒。然而事實證明這并不是真的：Jonathan Toomim已表示阳惹，通過在區(qū)塊內(nèi)記錄新的UTXO索引，然后在撤銷階段比較索引眶俩，TTOR的實施可以輕而易舉地實現(xiàn)莹汤。

無論如何，對我而言任何并行校驗算法都需要這類額外代碼颠印，來確認TTOR的規(guī)則獲得切實遵守纲岭，因此對于并行校驗TTOR?最多算個障礙抹竹。

先進并行技術(shù)

隨著BCH區(qū)塊規(guī)模擴容到一定程度，或許有一天需要升級到包含分片技術(shù)的先進服務器結(jié)構(gòu)止潮，對這種可能性的討論已經(jīng)有很多窃判，但開始為分片進行優(yōu)化還確實尚早，在這種規(guī)模下喇闸，TTOR會沒有幫助袄琳，CTOR能否實現(xiàn)性能優(yōu)化還很難說。

區(qū)塊傳播繁殖（石墨烯）

現(xiàn)在BCH面臨的主要瓶頸是區(qū)塊傳播繁殖仅偎。在壓力測試期間跨蟹，值得注意的是最大區(qū)塊(~20 MB)要耗時數(shù)分鐘在網(wǎng)絡傳播繁殖。由于傳播延遲意味著孤立率升高橘沥，從而令挖礦的經(jīng)濟和激勵機制惡化窗轩，這一點頗令人擔憂。

?“石墨烯”是采用布隆過濾器和可逆布隆查閱數(shù)據(jù)表的一套對賬技術(shù)座咆，它徹底降低了傳輸區(qū)塊所需的帶寬數(shù)量痢艺。不幸的是，核心石墨烯機制并不提供排序信息介陶，因此如果很多排序成為可能堤舒，那么排序信息就需要增添上去。對于大型區(qū)塊而言哺呜，這種排序信息構(gòu)成了石墨烯信息的主體舌缤。

為了縮小排序信息的大小，同時保持TTOR排序某残，礦工們可選擇性決定按照規(guī)范排序（例如Gavin's order）排列交易国撵，并且石墨烯協(xié)議可以是硬編碼，以便這種特殊排序以一個字節(jié)傳輸玻墅，這可能為挖礦軟件（以這種特別不尋常的排序生成區(qū)塊）及石墨烯（必須檢測這一排序介牙，并能夠?qū)⑵渲亟ǎ┰鎏矸敝氐募夹g(shù)負擔。我尚不清楚是否可能有效地將重建這些排序的分類算法并行化澳厢。

采用CTOR可以輕而易舉解決這一切：因為只有一種排序环础，不需要額外增添排序信息，通過并行化優(yōu)于拓撲分類的比較分類恢復排序剩拢，應該也能簡化石墨烯幣基线得，也不再需要開始考慮支持各種可選排序編碼。

可逆性和技術(shù)負債

調(diào)整為CTOR是不是以后也會不了了之徐伐？一切皆有可能框都。

對于檢驗年代久遠區(qū)塊的區(qū)塊驗證器/資源管理器而言，撤銷TTOR將永久取消標準串行處理算法的使用，這其實算不上問題（除了一時的不適）魏保，因為OTI看起來在串行中同并行一樣有效熬尺。

對于涉及處理新區(qū)塊的相關方（如石墨烯、網(wǎng)絡協(xié)議谓罗、挖礦區(qū)塊構(gòu)建器粱哼、新區(qū)塊校驗），以后改變排序不是問題（改成AOR/TTOR檩咱，或再度恢復成CTOR或其他）揭措。這些變化不會增添長期技術(shù)負債，因為它們僅牽涉新區(qū)塊刻蚯。對于過去的區(qū)塊校驗绊含，它可以追溯性宣布舊的區(qū)塊（時間超過幾個月）沒有排序需求。

總結(jié)和前景

·???????由于其他區(qū)塊處理軟件需要進行相應的升級炊汹，以處理按任何排序進來的交易躬充，撤銷TTOR是升級中最具破壞性的部分。但這些調(diào)整非常微小讨便，它們可以自然而然地將軟件轉(zhuǎn)化成并行可以輕而易舉引入的形式充甚。

·??????TTOR/ CTOR近期對于區(qū)塊校驗不會顯現(xiàn)明顯的性能差異。現(xiàn)在明確了這一點霸褒，區(qū)塊校驗不會成為BCH的限制因素伴找。

·???????中期來看，軟件切換為并行區(qū)塊處理可能會更希望采用任意排序算法（例如OTI）废菱。盡管在并行校驗中要實行排序規(guī)則需要一些額外代碼技矮，TTOR / AOR / CTOR三者仍不存在性能差異。

·???????從極其長遠來看殊轴，CTOR 對于配備分片UTXO數(shù)據(jù)庫的全節(jié)點而言展現(xiàn)出優(yōu)勢穆役，如果有必要的話∈崃荩總之，關心這個問題還為時過早梳杏。

·??????隨著TTOR 撤銷韧拒，進一步加入CTOR實際是微乎其微的變化。它并不需要升級任何其他生態(tài)系統(tǒng)軟件（它們并不在意排序）十性。不僅如此叛溢，我們不必非要接受CTOR:未來如果需要，排序可以輕而易舉再度改變劲适。

·??????CTOR近期的基本改進會允許石墨烯協(xié)議簡單楷掉、快速地實施，這將對當前重要的擴容瓶頸-區(qū)塊傳播繁殖造成影響霞势。通過避開復雜自發(fā)性排序方案的話題烹植，讓石墨烯開發(fā)人員不再擔心如何為排序編碼斑鸦，把精力集中在為設定對賬優(yōu)化機制。

廣義上講草雕，石墨烯并非網(wǎng)絡傳播的靈丹妙藥巷屿。即便是經(jīng)過CTOR改良后的石墨烯，性能也不會馬上獲得重大提升墩虹。網(wǎng)絡層也有工作要做嘱巾，以便能實現(xiàn)節(jié)點間信息的快速傳播。在最近的壓力測試中诫钓，我們也看到了內(nèi)存池性能（交易接受和分程傳遞）的局限旬昭。我希望能在下次壓力測試之前看到這些方面獲得優(yōu)化，以便新的瓶頸能夠顯現(xiàn)菌湃。