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

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

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

為什么是Minisketch ？

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

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

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

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

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

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

比特幣上的Minisketch

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

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

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

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

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