最近，我和格萊布·諾門科（Gleb Naumenko）以及前同事格雷格·麥克斯韋爾（Greg Maxwell）推出了一個名為miniketch的軟件庫，用于在分布式系統(tǒng)的節(jié)點間同步數(shù)據(jù)時降低帶寬要求。

miniketch最初是作為一個項目的組成部分開發(fā)的，該項目研究使用set reconciliation在比特幣上的節(jié)點之間共享交易數(shù)據(jù)，即“set reconciliation Relay”或SRR。SRR的目標(biāo)是顯著減少與運(yùn)行比特幣全節(jié)點相關(guān)的帶寬。

該團(tuán)隊決定將miniketch與SRR分開發(fā)布，因為它預(yù)計將對比特幣領(lǐng)域內(nèi)外的許多其他應(yīng)用程序有用。

為什么是Minisketch ？

傳統(tǒng)上，所有分布式系統(tǒng)都難以在節(jié)點之間同步數(shù)據(jù)——在集中式系統(tǒng)中，告訴節(jié)點應(yīng)該擁有哪些數(shù)據(jù)，不應(yīng)該擁有哪些數(shù)據(jù)要容易得多。

例如，分布式網(wǎng)絡(luò)中節(jié)點間數(shù)據(jù)同步的一種方法是可逆Bloom查詢表（IBLT）。雖然IBLT的CPU需求相對較低，但這是以相對較高的帶寬需求為代價實現(xiàn)的，特別是在差異數(shù)量較小的情況下。miniketch使用了一種稱為PinSketch的帶寬效率更高的算法。

與CPISync和Pinsketch最初的實現(xiàn)等其他帶寬高效的集協(xié)調(diào)算法相比，miniketch使用的計算能力要小得多。它比PinSketch快20到100倍，有時比CPISync快1000多倍。

如何實現(xiàn)改進(jìn)？

Set reconciliation（由miniketch實現(xiàn)）比簡單地發(fā)送整個數(shù)據(jù)列表的帶寬效率更高，因為它允許主節(jié)點生成其列表的數(shù)學(xué)“草圖”。然后，主節(jié)點將此消息發(fā)送給其他節(jié)點，以便與它們自己的列表進(jìn)行比較。草圖的大小只取決于節(jié)點之間的期望差異數(shù)量，而不取決于集合的總大小。盡管如此，它仍然允許主節(jié)點從其他節(jié)點中確定地區(qū)分它們需要哪些數(shù)據(jù)。

如果我們把它簡化成一個差值，很容易看出它是如何工作的：假設(shè)我有一個集合{3，5，7，11}，你有一個集合{3，5，7，9，11}，那么差值是{9}。我們都計算元素的和，得到3+5+7+11=26，你得到3+5+7+9+11=35。我把26這個和發(fā)給你，你從和中減去它;差是9。這是可行的，但僅限于找到單一的差異。miniketch通過發(fā)送各種類型的數(shù)據(jù)“和”來概括這一點。結(jié)果是，對于N個不同的和，您可以找到N個差異……只要集之間的差異的數(shù)量不超過發(fā)送的“和”的數(shù)量，miniketch總是能夠成功地找到所有的差異。

比特幣上的Minisketch

比特幣網(wǎng)絡(luò)的健壯性依賴于確保完整節(jié)點之間有足夠的連接，以阻止Sybiland分區(qū)攻擊。

不幸的是，比特幣節(jié)點的大部分?jǐn)?shù)據(jù)使用（通常在40%到70%之間）甚至都沒有花在交易數(shù)據(jù)上，而是花在相互宣布新交易以找出要轉(zhuǎn)發(fā)哪些交易上。現(xiàn)在，增加節(jié)點之間的連接數(shù)量會相應(yīng)地增加帶寬開銷。這限制了每個節(jié)點可以支持的連接數(shù)量。

通過使用set reconciliation，可以有效地找出哪些事務(wù)尚未中繼，而不需要向每個對等方宣布每個事務(wù)。查找要中繼的事務(wù)的帶寬開銷。

這種解決方案的美妙之處在于，它不需要對比特幣的網(wǎng)絡(luò)共識規(guī)則進(jìn)行任何修改。當(dāng)雙方的軟件都支持SRR協(xié)議時，SRR將被啟用，不會對不支持SRR協(xié)議的節(jié)點操作人員產(chǎn)生負(fù)面影響。

SRR協(xié)議仍處于研究的早期階段，可能要過很長時間才能在比特幣網(wǎng)絡(luò)中得到采用，但像Minisketch這樣的進(jìn)展代表著在改進(jìn)比特幣完全節(jié)點的采用和可訪問性（以及優(yōu)化其他分布式網(wǎng)絡(luò)）方面的一個非常重要的進(jìn)展。