聯(lián)合作者：Bighead, Algo, Lise

交易規(guī)范排序規(guī)則研究報(bào)告

事件背景

近期比特幣社區(qū)一些開(kāi)發(fā)團(tuán)隊(duì)在11月15日的BCH升級(jí)上，產(chǎn)生了一些技術(shù)上的分歧乏矾。

大體上分為兩派：

以Bitcoin ABC開(kāi)發(fā)團(tuán)隊(duì)為代表的一派主推交易規(guī)范排序（CTOR）替換原有的交易拓樸排序（TTOR），并且引入OP_DATASIGVERIFY腳本操作碼；

以nChain開(kāi)發(fā)團(tuán)隊(duì)為代表的一派主張將區(qū)塊大小的上限提高至128M，并且未來(lái)將逐步提高區(qū)塊上限直至撤銷限制，同時(shí)恢復(fù)更多的比特幣原始操作碼京痢，刪除每個(gè)腳本201個(gè)操作碼的限制。

此次技術(shù)升級(jí)上的分歧必將是POW共識(shí)機(jī)制在去中心化網(wǎng)絡(luò)上的一次實(shí)踐拯田，也將成為比特幣歷史上一次重要的事件历造。

Rawpool.com作為BCH礦池，將深度參與此次各方升級(jí)版本的測(cè)試和評(píng)估船庇，并將積極推動(dòng)社區(qū)對(duì)于新技術(shù)的理解及認(rèn)同吭产，將以對(duì)BCH生態(tài)利益最大化為原則做出客觀、公正的技術(shù)報(bào)告鸭轮。

前提說(shuō)明

通過(guò)對(duì)Bitcoin ABC 0.18.0 的研究發(fā)現(xiàn)臣淤，該版本中新增了CTOR排序，但TTOR排序并未去除窃爷，二者并存于代碼當(dāng)中邑蒋。通常，新增額外代碼只會(huì)造成性能劣化按厘，不可能帶來(lái)性能提升医吊，所以我們放棄了對(duì)這個(gè)版本進(jìn)行性能測(cè)試的計(jì)劃。

對(duì)此逮京，我們第一時(shí)間與ABC的工程師進(jìn)行了溝通卿堂，詢問(wèn)其依然保留了TTOR代碼的用意，他們給出的答復(fù)是：保留TTOR代碼是為了維護(hù)升級(jí)前的兼容性懒棉，否則現(xiàn)有主鏈上的區(qū)塊將無(wú)法校驗(yàn)草描。從維護(hù)兼容性的角度而言，這個(gè)答案有其合理性策严，但同時(shí)也證實(shí)了當(dāng)前版本對(duì)于性能提升并無(wú)助益穗慕。

測(cè)評(píng)內(nèi)容

本篇內(nèi)容為對(duì)Bitcoin ABC發(fā)布的v0.18.0版本中的交易規(guī)范排序（CTOR）功能進(jìn)行的代碼評(píng)估。僅進(jìn)行代碼評(píng)估是由于此版本并未使用充分優(yōu)化后的CTOR代碼實(shí)現(xiàn)妻导，因此無(wú)法進(jìn)行實(shí)測(cè)逛绵。

特別聲明

在關(guān)于CTOR代碼和應(yīng)用層面的一些問(wèn)題，Rawpool與Bitcoin ABC的首席開(kāi)發(fā)人員Amaury進(jìn)行了多次郵件溝通倔韭，Amaury每次均及時(shí)回復(fù)郵件并且作出了詳細(xì)解答暑脆，這里對(duì)Bitcoin ABC團(tuán)隊(duì)對(duì)社區(qū)參與者在技術(shù)上的支持表示贊賞和感謝！

Rawpool BCH Lab的報(bào)告內(nèi)容僅針對(duì)區(qū)塊鏈技術(shù)狐肢，對(duì)任何團(tuán)體或利益相關(guān)方均無(wú)傾向。

歡迎發(fā)送郵件與我們的開(kāi)發(fā)團(tuán)隊(duì)探討交流：Hi@rawpool.com

概念解釋

1?TTOR（Topological Transaction Ordering Rule)：稱為交易拓樸排序規(guī)則沥曹，即交易之間形成依賴關(guān)系網(wǎng)份名。如下圖的示例碟联，如果B交易的輸入用到了A交易的輸出，那顯而易見(jiàn)B交易是依賴A交易的僵腺。內(nèi)存池中的交易之間普遍存在著錯(cuò)綜復(fù)雜的依賴關(guān)系鲤孵，可以用有向無(wú)環(huán)圖來(lái)表示這種數(shù)據(jù)結(jié)構(gòu)，也就是所說(shuō)的拓?fù)鋱D辰如，如下：

圖中的A交易叫做祖先交易(ancestor tx)普监，BCD都是他的子孫交易(descendant tx)，因?yàn)锽CD的輸入都用到了A交易的輸出琉兜。同時(shí)可以看到C也是D的祖先交易凯正，因?yàn)镈的輸入會(huì)用到C的輸出。

如果對(duì)圖中的4個(gè)交易進(jìn)行排序的話豌蟋，一個(gè)合理的排序可以是ABCD或ACDB或ACBD廊散，但是絕對(duì)不可能是ABDC，因?yàn)樽訉O交易不允許出現(xiàn)排在祖先交易之前梧疲。

2?CTOR（ Canonical?Transaction Ordering Rule）: 稱為交易規(guī)范排序規(guī)則允睹。這種排序規(guī)則非常簡(jiǎn)單直觀，僅參考交易ID幌氮，即按照交易ID（十六進(jìn)制的一串?dāng)?shù)字）的升序排序缭受。

代碼分析

1、CTOR的廣泛評(píng)價(jià)

曼谷會(huì)議結(jié)束后该互，Rawpool的開(kāi)發(fā)團(tuán)隊(duì)對(duì)Bitcoin ABC的v0.18.0版本中CTOR及TTOR的代碼進(jìn)行了分析米者。

在目前網(wǎng)絡(luò)可以搜集到的關(guān)于CTOR的一些論文及其他技術(shù)文獻(xiàn)中，幾乎都提到了CTOR的性能更優(yōu)慢洋，尤其在大量交易及大區(qū)塊的情況下塘雳，比TTOR的優(yōu)勢(shì)更明顯。另外還排除了一些攻擊方法普筹，但這是一個(gè)附加優(yōu)勢(shì)败明，因?yàn)榻刂聊壳埃琓TOR并沒(méi)有出現(xiàn)過(guò)安全問(wèn)題太防。

因此我們的研究主要集中在CTOR是否實(shí)現(xiàn)了交易排序的優(yōu)化妻顶，并且它是否對(duì)整個(gè)網(wǎng)絡(luò)有益或節(jié)約了資源。

在《Canonical Transaction Ordering for Bitcoin》這篇論文中蜒车，對(duì)時(shí)間復(fù)雜度給出了足夠清晰的分析讳嘱，論文中的結(jié)論是CTOR明顯優(yōu)于TTOR。

2酿愧、TTOR的排序處理

但是軟件開(kāi)發(fā)人員都會(huì)熟知沥潭，對(duì)于算法設(shè)計(jì)而言，針對(duì)不同需求嬉挡，計(jì)算速度與存儲(chǔ)空間的使用可以互換（trade off between speed and memory usage）钝鸽。因此要使計(jì)算速度充分優(yōu)化汇恤，必然導(dǎo)致存儲(chǔ)空間的大量占用。

通俗地說(shuō)：在代碼實(shí)現(xiàn)層面為了追求更快的計(jì)算速度拔恰，往往會(huì)做很多優(yōu)化因谎，其中比較常見(jiàn)的一種就是用存儲(chǔ)換取時(shí)間。比如原始數(shù)據(jù)按照需要存好幾份颜懊，每一份可能結(jié)構(gòu)都不一樣财岔，然后中間數(shù)據(jù)也有可能被存儲(chǔ)下來(lái)，這樣的好處就是每次需要計(jì)算的時(shí)候并不需要從頭開(kāi)始計(jì)算河爹，只需要借助存儲(chǔ)的力量匠璧，使計(jì)算量大幅度精簡(jiǎn)并且提升了整體計(jì)算速度。但是這種方式的缺點(diǎn)就是會(huì)占用較多的存儲(chǔ)空間昌抠。

基于上述結(jié)論患朱，我們可以推斷在比特幣交易的拓?fù)渑判虻奶幚碇校灰自趦?nèi)存中的存儲(chǔ)方式至關(guān)重要炊苫，直接決定了排序處理的速度裁厅。

下面我們來(lái)看一下bitcoind是如何實(shí)現(xiàn)排序的，以及他的交易數(shù)據(jù)是如何存儲(chǔ)的侨艾。

首先定位到區(qū)塊打包功能相關(guān)代碼执虹，如下：

對(duì)于排序的功能，只有這一句代碼唠梨，簡(jiǎn)潔地調(diào)用了std::sort 袋励，這個(gè)模版方法的最后一個(gè)參數(shù)是一個(gè)比較操作符，來(lái)確定優(yōu)先級(jí)当叭，跟蹤到這個(gè)函數(shù)可以看到：

這里用到了CtxMemPool::GetCountWithAncestors方法茬故，此方法只是一個(gè)屬性讀取符。

這里小結(jié)一下：被論述為性能開(kāi)銷很大的TTOR排序蚁鳖，在代碼層面只是根據(jù)“祖先交易的數(shù)量”這個(gè)非常普通的整數(shù)進(jìn)行排序磺芭，即哪筆交易的祖先多，就被認(rèn)為交易輩分低醉箕，在排列中的次序也就靠后钾腺。

3、CTOR的排序處理

而被論述為性能比較好的CTOR排序規(guī)則讥裤，又是如何執(zhí)行的呢放棒？

CTOR的代碼如下圖所示：

CTOR排序是僅參考交易的ID，交易ID是一串?dāng)?shù)字己英，我們也可以把它認(rèn)定為是一個(gè)整數(shù)值燕锥。

4苟穆、初步對(duì)比結(jié)論

CTOR排序算法與TTOR非常相似宛乃，區(qū)別僅在于CTOR依據(jù)“交易ID”排序，而TTOR依據(jù)“祖先數(shù)量”排序邮府，但兩者都是對(duì)“整數(shù)排序”而已。由此可以推斷溉奕，就排序過(guò)程本身而言，二者的性能幾乎完全一致忍啤。

然而加勤，維護(hù)“交易ID”與維護(hù)“祖先數(shù)量”的性能差異，將成為這兩種排序方法整體性能差異的決定性因素同波。

5鳄梅、維護(hù)交易ID

“交易ID”本身就是一個(gè)隨機(jī)值，沒(méi)什么工作量未檩，讓我們深度看一看“祖先個(gè)數(shù)”這個(gè)值戴尸，便于更好的理解代碼，先給出一個(gè)抽象總結(jié)后的圖：

這里面涉及2個(gè)核心數(shù)據(jù)結(jié)構(gòu)冤狡，一個(gè)是mapTx孙蒙，是真正用來(lái)存儲(chǔ)交易的字典，字典的Value是CtxMempoolEntry悲雳，Key有四個(gè)挎峦，分別是ID, fee, time, score

先來(lái)探討“交易ID”，當(dāng)前版本（0.18）的“交易ID”等價(jià)于交易的哈希值合瓢，不需要額外的工作量來(lái)維護(hù)坦胶。

6、維護(hù)祖先數(shù)量

再來(lái)探討“祖先數(shù)量”晴楔，與此相關(guān)的數(shù)據(jù)結(jié)構(gòu)有兩個(gè)顿苇，mapTx和mapLinks，二者均為字典結(jié)構(gòu)税弃。我們下面會(huì)詳細(xì)闡述這兩個(gè)結(jié)構(gòu)的代碼：

（1) mapTx的Value是CtxMempoolEntry纪岁，Key有四個(gè)，分別是ID, fee, time, score

具體聲明如下：

（2) 接下來(lái)為了便于更好的找到交易的祖先以及子孫钙皮，引入了另一個(gè)變量:mapLinks蜂科。

這也是一個(gè)字典，Key是交易ID短条，Value是一個(gè)結(jié)構(gòu)體导匣，其中包含了parents和children，這兩個(gè)成員是集合類型茸时，其中存放的是交易的迭代器即0號(hào)索引贡定，這樣的話，當(dāng)我們知道一個(gè)交易的ID可都，第一時(shí)間就可以把此交易的祖先和子孫全部找出來(lái)缓待，可謂非常高效蚓耽，時(shí)間復(fù)雜度是O(1)。

那么這些數(shù)據(jù)信息什么時(shí)候會(huì)進(jìn)行更新呢旋炒？那就是新的交易進(jìn)入內(nèi)存池或已存的交易離開(kāi)內(nèi)存池的時(shí)候步悠。

當(dāng)內(nèi)存池有交易進(jìn)出時(shí)，系統(tǒng)需要頻繁的遍歷當(dāng)前交易的祖先交易瘫镇，子孫交易鼎兽，然后更新這些交易的信息，更新的內(nèi)容就包含了之前說(shuō)的“祖先個(gè)數(shù)”铣除。這一套數(shù)據(jù)結(jié)構(gòu)是非常優(yōu)雅的設(shè)計(jì)谚咬，很好的用存儲(chǔ)空間換取了計(jì)算時(shí)間。

Rawpool Lab結(jié)論

通過(guò)CTOR與TTOR二者代碼層面的對(duì)比尚粘，我們注意到择卦，TTOR排序算法隱含了維護(hù)交易祖孫關(guān)系的功能，而這恰恰是在UTXO共識(shí)模式下郎嫁，必須要實(shí)現(xiàn)的基本功能秉继。因此，在Bitcoin ABC 0.18.0版本代碼中行剂，即使新增了CTOR排序算法秕噪，只要尚未將維護(hù)祖孫關(guān)系的代碼從TTOR排序代碼當(dāng)中剝離出來(lái)，就不能貿(mào)然移除TTOR代碼厚宰。

當(dāng)前的TTOR代碼經(jīng)歷了長(zhǎng)久的版本迭代過(guò)程腌巾，已積累了大量經(jīng)驗(yàn)，形成了良好的算法設(shè)計(jì)铲觉，使得這部分代碼非常高效澈蝙，并且在當(dāng)前的運(yùn)行中，并未體現(xiàn)出它繁冗的計(jì)算給節(jié)點(diǎn)造成了負(fù)擔(dān)撵幽。

針對(duì)CTOR與TTOR排序性能的比較灯荧，前提應(yīng)是二者功能一致。TTOR排序隱含了維護(hù)交易祖孫關(guān)系功能盐杂，而CTOR排序并未包含維護(hù)交易祖孫關(guān)系功能逗载。在不滿足功能一致的前提下，就此進(jìn)行比較沒(méi)有意義链烈。

不過(guò)厉斟，不能否認(rèn)隨著區(qū)塊越來(lái)越大，交易越來(lái)越多强衡，傳統(tǒng)的TTOR排序必然會(huì)面臨內(nèi)存開(kāi)銷上漲擦秽、運(yùn)算時(shí)間增大等問(wèn)題。另一方面，充分優(yōu)化后的CTOR排序（即包含了維護(hù)交易祖孫關(guān)系的CTOR排序感挥，并且移除了TTOR排序）應(yīng)是一套全新的數(shù)據(jù)維護(hù)體系缩搅，勢(shì)必具有相當(dāng)?shù)膹?fù)雜度，其能否在內(nèi)存開(kāi)銷触幼、運(yùn)算速度等方面取得性能提升硼瓣，目前無(wú)論在理論層面還是具體代碼實(shí)現(xiàn)層面，均無(wú)法給出確定性結(jié)論置谦。

探討至此巨双，我們不能忽視一個(gè)事實(shí)：UTXO共識(shí)模式下，交易祖孫關(guān)系的維護(hù)扎根于Bitcoind的骨髓霉祸，從TTOR算法到存儲(chǔ)以及數(shù)據(jù)結(jié)構(gòu)，均服務(wù)于UTXO共識(shí)袱蜡。因此交易的祖孫關(guān)系會(huì)始終存在丝蹭，而TTOR只是順勢(shì)而為進(jìn)行排序操作。這就說(shuō)明想要在維持祖孫關(guān)系的情況下坪蚁，去除TTOR功能奔穿，應(yīng)該需要對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行大規(guī)模整改，必須慎之又慎敏晤，ABC工程師也坦言近期不會(huì)大規(guī)模更改代碼贱田。

最后，如果Bitcoin ABC能夠在升級(jí)時(shí)間點(diǎn)之前推出充分優(yōu)化的CTOR測(cè)試版本嘴脾，Rawpool將會(huì)第一時(shí)間進(jìn)行評(píng)測(cè)男摧。

Rawpool會(huì)持續(xù)與Bitcoin ABC和nChain的開(kāi)發(fā)團(tuán)隊(duì)保持溝通，目前已完成測(cè)試節(jié)點(diǎn)的布署译打，將會(huì)積極參與新升級(jí)版本的測(cè)試及全網(wǎng)壓力測(cè)試耗拓。

感謝閱讀。