Recentemente io e Glab Naumenko, assieme all ex-collega Gregory Maxwell, abbiamo rilasciato Minisketch, una libreria software per ridurre i requisiti di banda per la sincronizzazione di dati fra nodi in sistemi distribuiti.

Originariamente Minisketch era stato sviluppato come componente di un progetto che indagava sulla riconciliazione d’insiemi per la condivisione dei dati delle transazioni su Bitcoin.,”Set Reconciliation relay” SRR. Lo scopo di SRR è ridurre significativamente la banda necessaria per operare un nodo Bitcoin.

Il team ha deciso di rilasciare Minisketch separatamente da SRR perchè ritiene che sia utile per molte altre applicazioni all’infuori dello spazio Bitcoin.

Perchè Minisketch?

Tutti i sistemi distribuiti tradizionalmente hanno sempre avuto difficoltà a sincronizzare i dati fra i suoi nodi - è molto più semplice in un sistema centralizzato dire ai propri nodi quali dati dovrebbero o non dovrebbero avere.

Ad esempio, un approccio usato per sincronizzare dati fra nodi in sistemi distribuiti è Invertible Bloom Lookup Table (IBLT). Sebbene IBLT abbia bassa necessità di CPU, lo ottiene a costo di un’alta necessità di banda, in particolare quando il numero di differenze è basso. Minisketch usa un algoritmo più efficiente in termini di banda, noto come PinSketch.

Confrontato con altri algoritmi per la riconciliazione d’insiemi efficienti in quanto a banda come CPISync e l’implementazione originale di PinSkecth, Minisketch usa molta meno potenza computazionale. E’ infatti dalle 20 alle 100 volte più veloce di PinSketch e in alcuni casi oltre 1000 volte più veloce di CPISync.

Come vengono raggiunti questi risultati?

La riconciliazione d’insiemi , come implementata da Minisketch, è più efficiente in termini di banda rispetto a mandare l’intera lista di dati, perchè consente ai nodi di produrre una “bozza” matematica della propria lista. Ogni nodo in seguito invia la sua lista ad altri nodi affinchè la confrontino con la propria lista. La dimensione della “bozza” dipende dal numero di differenze attese fra le liste dei vari nodi, non dalla dimensione della lista stessa. Ciononostante, Minisketch consente ai nodi di sapere con certezza di quali dati necessitano da altri nodi.

Se semplifichiamo il caso ad una singola differenza fra le liste è semplice capire come funziona: immaginiamo che io abbia l’insieme {3,5,7,11} e tu abbia {3,5,7,9,11}, la differenza è solo {9}. Se calcoliamo la somma dei nostri elementi, io ottengo 3+5+7+11=26, e tu ottieni 3+5+7+9+11=35. Io ti invio la mia somma di 26 e tu la sottrai dalla tua somma, ottenendo come differenza 9. Funzionerebbe, ma solo per trovare una singola differenza. Minisketch generalizza la soluzione inviando vari tipi di “somme” dei dati. Il risultato è che con N somme diverse puoi trovare N differenze. Fintanto che il numero di differenze fra gli insiemi non eccede il numero di somme inviate, Minisketch avrà sempre successo nel trovare tutte le differenze.

Minisketch su Bitcoin

La robustezza del network Bitcoin dipende dal fatto che ci siano abbastanza connessioni fra i full node per vanificare eventuali attacchi Sybil e di partizionamento.

Sfortunatamente, oggi la maggioranza dei dati usati da un nodo Bitcoin (normalmente fra il 40% e il 70%) è spesa solo per annunciare nuove transazioni l’un l’altro e quindi per scoprire quali transazioni trasmettere, quindi nemmeno per trasmettere i dati delle transazioni.  Ora come ora, aumentare il numero di connessioni ad altri nodi Bitcoin, aumenta proporzionalmente le necessità di banda. Ciò limita il numero di connessioni che ogni nodo può supportare.

Utilizzando tecniche per la riconciliazione di insiemi è possibile identificare molto più efficientemente quali transazioni non sono ancora state trasmesse, senza la necessità di annunciare ogni singola transazione ad ogni singolo nodo con cui è connesso.  I costi di banda per identificare le transazioni da trasmettere diventa così indipendente dal numero di connessioni di ogni nodo, potenzialmente consentendo di aumentare il numero di connessioni supportate dai nodi.

La bellezza di questa soluzione è che non richiede nemmeno alcun cambiamento alle regole di consenso del network Bitcoin. SRR potrà essere attivata per qualsiasi coppia di nodi che supporti il protocollo SRR, senza alcun impatto negativo sui nodi che non hanno una versione di Bitcoin con SRR.

Il protocollo SRR è ancora nelle prime fasi di ricerca e potrebbe essere necessario molto tempo prima di poterlo vedere adottato sul network Bitcoin, ma progressi come Minisketch rappresentano uno sviluppo molto importante per aumentare l’accessibilità e l’adozione dei full node Bitcoin (così come l’ottimizzazione di altri network distribuiti). Restate sintonizzati per ulteriori aggiornamenti sui progressi di questo progetto!

Se volessi saperne di più su Minisketch, dai un’occhiata alla repository di Minisketch su GitHub.