Recentelijk heb ik samen met Gleb Naumenko en voormalig collega Greg Maxwell Minisketch onthuld. Minisketch is een software library voor het reduceren van de benodigde bandbreedte tijdens het synchroniseren van gegevens tussen nodes in gedistribueerde systemen.
Minisketch is oorspronkelijk ontwikkeld als onderdeel van een project voor gebruik in set reconciliation voor het samenbrengen van transactiegegevens tussen bitcoin-nodes, ofwel “Set Reconciliation Relay” (SRR). Het doel van SRR is om de benodigde bandbreedte voor full nodes in bitcoin significant te reduceren.
Het team heeft besloten om Minisketch los van SRR uit te brengen, omdat het naar verwachting nuttig zal zijn voor vele andere toepassingen, zowel binnen bitcoin als daarbuiten.
Waarom Minisketch?
Alle gedistribueerde systemen hebben moeite met het synchroniseren van gegevens. Het is een stuk makkelijker voor een gecentraliseerd systeem om aan nodes te vertellen welke gegevens ze wel en niet moeten hebben.
Om een voorbeeld te noemen: bij het synchroniseren van gegevens tussen nodes in gedistribueerde netwerken kan gebruik worden gemaakt van Invertible Bloom Lookup Tables (IBLT). Hoewel IBLT de CPU relatief niet veel belast, wordt dit bereikt ten koste van relatief hoge bandbreedtevereisten. Dit is met name het geval als er geen groot verschil zit tussen de sets. Minisketch maakt gebruik van een efficiënt algoritme genaamd PinSketch.
In vergelijking met andere algoritmes voor set reconciliation die efficiënt zijn qua bandbreedte, zoals CPISync en de originele implementatie van PinSketch, verbruikt Minisketch veel minder rekenkracht. Het is 20 tot 100 keer sneller dan PinSketch, en soms wel 1000 keer sneller dan CPISync.
Hoe zijn deze verbeteringen bereikt?
Set reconciliation, zoals deze is geïmplementeerd door Minisketch, verbruikt minder bandbreedte dan het verzenden van de gehele lijst aan gegevens, omdat het nodes in staat stelt om een “schets” van de lijst uit te rekenen. De node stuurt deze schets vervolgens naar andere nodes, zodat die het verschil tussen de schets en hun eigen lijst kunnen bekijken. De grootte van de schets hangt af van het verwachte aantal verschillen tussen de nodes. De totale grootte van de set heeft er geen invloed op. Toch is het voor nodes alsnog mogelijk om met zekerheid te achterhalen welke gegevens ze nodig hebben van andere nodes.
Als we het probleem versimpelen tot een enkel verschil, dan is het makkelijk om te volgen hoe dit werkt: Stel dat de ene set {3,5,7,11} bevat, en de andere bevat {3,5,7,9,11}, dus het verschil is {9}. We berekenen de som van onze elementen, waardoor de een uitkomt op 3+5+7+11=26, en de ander op 3+5+7+9+11=35. Nu stuurt de een de som 26, en haalt de ander dit van zijn eigen som af, waardoor deze uitkomt op 9. Dit werkt, maar is alleen mogelijk voor het achterhalen van een enkel verschil. Minisketch generaliseert dit door verschillende soorten ‘sommen’ van de gegevens te sturen. Het eindresultaat is dat het mogelijk is om met N verschillende sommen N verschillen te vinden. Zolang het aantal verschillen in de set niet hoger is dan het verstuurde aantal sommen, weet Minisketch altijd de verschillen te achterhalen.
Minisketch voor bitcoin
De robuustheid van het bitcoin-netwerk hangt af van of er genoeg verbindingen zijn tussen full nodes om zogenaamde Sybil en partitioning attacks tegen te gaan.
Helaas komt het merendeel van het bandbreedteverbruik van een bitcoin-node (vaak tussen de 40% en 70%) niet eens door transactiegegevens, maar door het aankondigen van nieuwe transacties om erachter te komen welke er moeten worden doorgestuurd. Dit betekent dat er momenteel proportioneel meer bandbreedte zou worden verbruikt als het aantal verbindingen omhoog gaat. Het aantal verbindingen dat elke node aankan is dus gelimiteerd.
Door gebruik te maken van set reconciliation, is het mogelijk om op efficiënte wijze te achterhalen welke transacties nog niet zijn doorgestuurd, zonder dat elke transactie aan elke verbonden peer hoeft te worden aangekondigd. Het bandbreedteverbruik voor het ontdekken welke transacties moeten worden doorgestuurd wordt zo onafhankelijk van het aantal verbindingen, waardoor het mogelijk wordt om het aantal verbindingen per node te verhogen. Het mooie aan deze oplossing is dat de consensusregels niet hoeven te worden veranderd. SRR kan worden ingezet wanneer de software aan beide kanten van de verbinding het SRR-protocol ondersteunt, en heeft geen negatieve consequenties voor nodes die het niet ondersteunen.
Het SRR-protocol is nog steeds in een vroege fase van ontwikkeling, en het kan lang duren voordat het in gebruik wordt genomen door het bitcoin-netwerk, maar verbeteringen zoals Minisketch zijn een belangrijke stap in het vergemakkelijken en stimuleren van het gebruik van full nodes (en het helpt tevens voor optimalisatie van andere gedistribueerde netwerken). Hou ons in de gaten voor toekomstige updates over dit project!
Om meer te weten te komen over Minisketch, kunt u een kijkje nemen naar de Minisketch GitHub repository.