Avec Gleb Naumenko et notre ex-collègue Greg Maxwell, nous avons récemment publié Minisketch, une bibliothèque logicielle permettant de réduire les besoins en bande passante lors de la synchronisation de données entre les nœuds d’un système distribué.

Minisketch a été développé à l’origine comme une partie d’un projet de recherche plus large sur l’optimisation du partage des données de transaction entre les nœuds Bitcoin : « Set Reconciliation Relay », ou SRR. L’objectif de SRR est d’obtenir une réduction significative de la consommation de bande passante occasionnée par l’exécution d’un nœud Bitcoin.

L’équipe a décidé de publier Minisketch indépendamment de SRR car ce protocole pourrait être utile pour de nombreuses autres applications liées ou non à Bitcoin.

Pourquoi Minisketch ?

Tous les systèmes distribués ont des difficultés pour synchroniser des données entre différents nœuds -  au contraire d’un système centralisé, où il est très facile de communiquer aux nœuds les données qu’ils doivent avoir ou pas.

Un exemple de solution pour synchroniser des données entre les nœuds sur les réseaux distribués est l’Invertible Bloom Lookup Tables (IBLT). IBLT demande relativement peu de ressources processeur, au prix d’une consommation de bande passante relativement élevée, en particulier quand il n’y a qu’un petit nombre de différences à harmoniser. Minisketch exploite un algorithme plus efficace en ce qui concerne la bande passante, appelé PinSketch. Comparé à d’autres algorithmes de synchronisation qui consomment peu de bande passante, tels que CPISync ou l’implémentation originale de Pinsketch, Minisketch nécessite beaucoup moins de puissance de calcul. Il est 20 à 100 fois plus rapide que PinSketch, et parfois plus de 1 000 fois plus rapide que CPISync.

Comment ça marche ?

La façon dont Minisketch réconcilie des ensembles de données consomme moins de bande passante que l’envoi de la liste complète des données, car il permet aux nœuds de produire une « esquisse » mathématique de leur liste. Le nœud envoie ensuite cette esquisse à d’autres nœuds qui la comparent à leurs propres listes. La taille de l’esquisse dépend uniquement du nombre de différences attendues et non de la taille totale de l’ensemble. Les nœuds peuvent néanmoins déterminer avec certitude les données qu’ils doivent obtenir d’autres nœuds.

Il est possible de comprendre cela plus facilement s’il n’y a qu’une seule différence : admettons que j’ai l’ensemble de données : {3,5,7,11}, et que vous avez {3,5,7,9,11}, la différence est {9}. Si nous calculons tous les deux la somme des éléments en notre possession, j’obtiens donc 3+5+7+11=26, et vous 3+5+7+9+11=35. Je vous envoie ma somme, 26, et vous la soustrayez de la vôtre ; la différence est de 9. Cela fonctionne, mais on ne peut trouver ainsi qu’une seule différence. Minisketch généralise ce procédé en envoyant différents types de « sommes » de données. Le résultat c’est qu’avec N sommes différentes, vous pouvez trouver N différences… Tant que le nombre de différences entre les ensembles n’est pas supérieur au nombre de « sommes » envoyées, Minisketch réussira toujours à trouver toutes les différences.

Minisketch pour Bitcoin

La robustesse du réseau Bitcoin est assurée par un nombre suffisant de connexions entre les nœuds pour contrecarrer une attaque Sybil ou une attaque de partitionnement.

Malheureusement, la majeure partie du flux de données d’un nœud Bitcoin (généralement entre 40% et 70%) n’est pas utilisée pour transmettre les données des transactions, mais simplement pour annoncer les nouvelles transactions afin de déterminer celles qui nécessitent d’être relayées. À l’heure actuelle, augmenter le nombre de connexions entre les nœuds augmente en proportion le coût en bande passante, limitant ainsi le nombre de connexions que chaque nœud peut supporter.

En réconciliant les données entre les nœuds, il est possible de déterminer efficacement les transactions qui n’ont pas encore été relayées, sans avoir à annoncer chaque transaction à chaque pair. Les coûts en bande passante qu’implique la recherche de transactions à relayer sont alors indépendants du nombre de connexions, ce qui permet potentiellement d’augmenter le nombre de connexions établis par chaque nœud. L’intérêt de cette solution c’est qu’elle ne nécessite aucune modification des règles de consensus du réseau Bitcoin. SRR sera activé si les deux nœuds connaissent le protocole SRR et n’a pas d’impact négatif pour les nœuds qui ne le reconnaissent pas.

Le protocole SRR en est encore à ses balbutiements et il faudra peut-être attendre longtemps son adoption sur le réseau Bitcoin. Des propositions comme Minisketch constituent cependant des avancées importantes susceptibles de rendre les nœuds Bitcoin plus accessibles et de favoriser leur adoption (ainsi que d’optimiser d’autres réseaux distribués). Restez à l’écoute pour être informé des progrès du projet !

Si vous souhaitez en savoir plus, consultez le eépôt Github de Minisketch.