MINISKETCH

RÉSEAU

Bibliothèque de réconciliation d’ensembles (set reconciliation) développée principalement par Pieter Wuille (sipa). Minisketch implémente un algorithme qui permet à deux pairs d’un réseau pair-à-pair de déterminer efficacement les éléments que l’un possède et que l’autre n’a pas, sans que chacun doive transmettre la liste complète de ses éléments.

Le principe repose sur des esquisses (sketches) : chaque pair calcule une représentation compacte de son ensemble d’éléments, dont la taille dépend du nombre de différences attendues et non de la taille totale des ensembles. En échangeant ces esquisses, les deux pairs peuvent identifier les éléments manquants de chaque côté et ne transmettre que ceux-ci. Ce mécanisme réduit considérablement la bande passante consommée par les protocoles de diffusion (gossip).

Minisketch constitue la brique technique fondamentale d’Erlay, une proposition d’amélioration du relais de transactions sur le réseau Bitcoin. Actuellement, chaque noeud annonce chaque transaction à tous ses pairs, ce qui génère une redondance importante. Avec Erlay, les noeuds n’annonceraient les transactions qu’à un petit nombre de pairs, puis utiliseraient la réconciliation via Minisketch pour synchroniser leurs mempools avec les autres. Cette approche pourrait réduire d’environ 84 % la bande passante utilisée pour l’annonce des transactions, et d’environ 40 % la consommation globale de bande passante.