鏈聞消息,公鏈項目 Monoxide 發佈了區塊壓縮算法 Txilm,據該項目創始人王嘉平介紹,Txilm 算法從比特幣提案「BIP152」出發,進行了進一步改進,使用該算法將使區塊傳輸帶寬需求降低到原來的 1/80,同時使得衝突概率控制在 1/1000 左右,其中消解衝突的計算量可以忽略不計。此外,該算法不依賴各個全節點之間的 mempool 是高度一致的,無需額外的協議保持 mempool 的同步。

王嘉平表示,Txilm 協議在設計迭代中得到了原比特大陸區塊鏈團隊王逵的指導和非常有意義的探討,同時得到了孫毅老師主持的中科院計算所區塊鏈實驗室的大力支持。他感謝實驗室中王鑫和姜鑫同學幫助完成了算法的初步模擬驗證。

以下文章翻譯自 Monoxide 團隊的 Medium 博文,獵豹移動區塊鏈團隊王海龍完成翻譯和校對。

原文標題:《Monoxide 公鏈系統中的帶鹽短哈希有損區塊壓縮算法》
作者:王嘉平,創新工場執行董事,Monoxide 論文作者
翻譯:王海龍,獵豹移動區塊鏈團隊

硬核:深入講解 Monoxide 的區塊壓縮算法 Txilm王嘉平,創新工場執行董事,Monoxide 論文作者

1 背景

假設新創建的區塊中大多數交易 TXes 已經存儲在大多數全節點的內存池中,緻密區塊 (compact block) 只攜帶 TXIDs。這是在比特幣改進提案 BIP152 中提出的。更多細節參見 https://bitcoincore.org/en/2016/06/07/compact-blocks-faq/

總的來說,緻密區塊用 32 字節的 TXID(例如,交易 TX 的 SHA256 值) 替代每個交易 TX(大約 300-400 字節)。這可以節省近 10 倍的帶寬。

我們旨在進一步將緻密區塊中每個 TX 表示的大小減小到約 40 比特。我們可以在緻密區塊最初的提案 (6.4=32 字節 /40 比特) 上做到 6.4 倍壓縮。新的提案沒有使用諸如布隆過濾器或 IBLT 這些額外的數據結構。此外,新提案不依賴各個全節點之間有高度一致的內存池 (Mempool)。

通過結合規範的交易排序規則 (canonical transaction ordering rule, CTOR),短哈希可以被進一步降低到 32 比特,這在緻密區塊最初的提案上產生了 8 倍壓縮。做到了總的數據量減小 80 倍。

2 基本原理

我們通過基於 TXID 的小尺寸哈希值在區塊中顯示每個 TX。

TXID-HASH = h(TXID)

其中 h 是一個小尺寸的哈希函數,它可以產生 32 比特到 64 比特的哈希值。該函數可以僅是 CRC32,CRC40 或 CRC64。所提新的緻密區塊方案只包括一個 TXID-HASH 列表,按交易 TX 的初始列表排序。

這種 k 比特的小尺寸哈希可能會產生二義性 (ambiguity),這需要每個全節點解決。一旦從發送方接收到包括 TXID-HASH 列表的新區塊,接收方就在其內存池中的哈希列表中搜索每個接收到的 TXID-HASH。對於每個 TXID-HASH,可能發生三種情況,分別如下:

1、未找到:內存池中沒有交易 TX 可以匹配上接收到的 TXID-HASH。接收方將向發送方或其他 peer 節點索要該 TXID;
2、找到一個匹配的 TX:解析 TXID 成功;
3、找到多個匹配的 TX:接收方將收集所有匹配的 TXIDs 作爲第二階段解析的候選集。

在第二階段,迭代多個 TXID-HASH 的候選者的所有組合來重新計算 Merkle 樹。其正確的組合將產生一個與區塊頭攜帶的 Merkle 根相匹配的值。

如果情況(3)中的任一組合或情況(2)中被解析的 TXID 列表沒能匹配區塊頭中的 Merkle 根,那麼接收方將回退到要求發收方傳輸該區塊的完整 TXID 列表,具體協議在最初的緻密區塊提案中有描述。出現這種情況的原因是在接收方的內存池中至少有一個 TXID 在接收的 TXID-HASH 列表中有相同的 TXID-HASH,而不是包括在區塊中的 TXID-HASH。

對第二階段搜索的一個可選優化是,在實際重新計算 Merkle 根之前,添加輕量級的預檢查。我們提出了一種輕量級的 Merkle 樹,CRC32-Merkle 樹,即用 CRC32 取代 SHA256,4 字節的 Merkle 樹節點和根。當創建一個新區塊,4 字節的 CRC32-Merkle 根將預置到編碼的 TXID-HASH 數據。在搜索正確的組合時,這產生了 40 倍的加速。(在 16 字節上算 SHA256 對比 在 8 字節上算 CRC32)

解決二義性可能引發額外的延遲。對很多有二義性的 TXID-HASH 的組合進行迭代也可能消耗大量的 CPU 時間。本提案的可行性高度依賴哈希碰撞的概率,這一概率同哈希值的長度 (k 比特) 以及內存池的大小是相關的。

3 單個碰撞的概率

單個碰撞被定義爲情況 1 或 3 至少發生 1 次。這種碰撞可以在接收到的 TXID-HASH 之間,或者處於接收到的列表和內存池之間。

給定 k 比特大小的的 TXID-HASH,碰撞率是 1/2^k。因此在一個新區塊中發生單個碰撞的概率可以被建模爲廣義生日問題 (Generalized Birthday problem)。比如,在內存池中,我們平均有 m 個 TX,而新區塊有 n 個 TX。單個碰撞的概率可近似爲:

PSC = 1 - (1 - 1/2^k) ^ (m * n + n * n/2)

例如,我們取 m=60000,n=10000:
k = 32, PSC = 0.14
k = 40, PSC = 0.00059
k = 64, PSC = 0.00000035

我們建議把 k=40 作爲一個合理值,具備良好的壓縮比和相當低的碰撞率。足夠大的 k 約與 log(m * n +n * n/2) 成比例。

例如,我們放大 100 倍:m = 6000000,n = 1000000:
k = 48, PSC = 0.023
k = 56, PSC = 0.000090
k = 64, PSC = 0.00000035

或者,我們把 m,n 的值取小一點,m = 3000,n = 200
k = 24, PSC = 0.036
k = 32, PSC = 0.00014
k = 40, PSC = 0.00000056

4 結合 CTOR 技術

規範交易排序規則 (CTOR) 是一種排序方案,它根據交易的哈希對一個區塊和內存池中的交易進行排序,該方案已經被部署在 BCH 網絡中。基於 CTOR 方案,所提的方案將實現更低的碰撞率和更高的壓縮率。

因爲交易在區塊和內存池中都是有序的,任何有二義性的 TXID-HASH 的候選空間將被縮小到由其前一個 TXID 和下一個 TXID 限定的範圍,並且具有被解析的 TXID-HASH,而不是整個內存池。假設新確認的 TXID 均勻分佈在已排序的內存池中,則可能的碰撞空間的大小將從 m 降低到 m/n。在排序後,有二義性的 TXID-HASH 只有在相鄰時纔會發生區塊內的碰撞。這顯著降低了碰撞概率和解決二義性的成本,從而允許更短的哈希和更高的壓縮比。

按 CTOR 技術對交易排序,碰撞概率可以被近似爲:

PSC = 1 - (1 - 1/2^k) ^ (m + n/2)

對小尺寸的區塊:m = 3000,n = 200:
K = 16, PSC = 0.046
K = 24, PSC = 0.00018
K = 32, PSC = 0.00000072

對中等尺寸的區塊:m = 60000,,n = 10000:
k = 16, PSC = 0.63
k = 24, PSC = 0.0039
k = 32, PSC = 0.000015

對大尺寸的區塊: m = 6000000,n = 1000000:
k = 24, PSC = 0.32
k = 32, PSC = 0.0015
k = 40, PSC = 0.0000059

5 惡意碰撞攻擊

攻擊者很容易構造一個新交易,其 TXID-HASH 和已有的交易相匹配。大量創建這種惡意交易可能使上述的碰撞概率分析無效並且使新區塊的驗證成本不菲,這最終導致更高的分叉率。我們提出了兩個簡單的策略來應對該攻擊模型。

帶鹽的短哈希

一個簡單的防護策略是在計算 TXID-HASH 時引入一個鹽 (Salt):

TXID-HASH = h( Salt + TXID )

該鹽值該特定於攜帶那些 TXID-HASHes 的區塊並被包括在編碼的數據中。例如,直接將 CRC32-Merkle 的根作爲鹽,或引入另一個 4 字節字段,隨機生成。

加鹽哈希

即便已有的交易對所有人是已知的,攻擊者在一個區塊被礦工廣播之前是無法構造惡意的交易。惡意交易很難比接收並驗證新區塊更早之前到達全節點。這使得攻擊者可能發起攻擊的時間窗口極度受限。同時,這要求攻擊者可以快速地將惡意交易泛洪到整個網絡。理論上講,這有可能(例如,控制大型的僵屍網絡),尤其是當主鏈底層的 P2P 網絡很小的時候。該策略使得惡意交易只能針對單個特定區塊,因此先前傳播的惡意交易將無法攻擊未來的區塊從而使得該攻擊在經濟上很低效。如果想要持續攻擊網絡,需要持續構造惡意交易,隔了一個塊之後,之前的攻擊交易就失效了。但是這些交易的交易費用依舊背會後續區塊獲取,使得攻擊成本相當高昂。

受到攻擊降級到老算法

引入加鹽哈希顯著地提升了碰撞攻擊的成本和失敗率。倘若在極端情況,不計成本,大規模的碰撞攻擊仍然是可能的。當整個網絡受到攻擊時,我們要求礦工回退到 TXID 列表。礦工會願意在這個時候退到老算法,因爲創建孤塊是在浪費哈希算力,礦工會盡可能避免。

在驗證進來的新區塊時,包括礦工在內的所有全節點都可以察覺到此類攻擊。它可以通過簡單地計算每個區塊中帶二義性的 TXID-HASH 的數量來做到。如果數量顯明顯高於預期值並且觀察到分叉。下一個區塊應該回退到 TXID 列表算法。

參考文獻

[1] Compact Blocks FAQ: https://bitcoincore.org/en/2016/06/07/compact-blocks-faq/
[2 ]BIP152: Compact Blocks: https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki
[3] Canonical Transaction Ordering for Bitcoin
https://link.zhihu.com/?target=https%3A//blog.vermorel.com/pdf/canonical-tx-ordering-2018-06-12.pdf
[4] Wiki: Birthday problem
https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem
[5] Big Number Calculation:https://www.ttmath.org/online_calculator

來源鏈接:mp.weixin.qq.com