Dans cet article, je décris brièvement le besoin de clients légers dans Bitcoin et pourquoi les "filtres de bloc compacts" répondent mieux à ce besoin que les "filtres Bloom". J'explique ensuite en détail le fonctionnement du filtre de bloc dense, avec une procédure pas à pas pour créer un tel filtre sur un testnet.
Signification du filtre de bloc
Un client bitcoin light (logiciel bitcoin light) est un logiciel dont le but n'est pas de stocker la blockchain bitcoin mais de supporter un portefeuille bitcoin. Cela signifie qu'il doit être capable de diffuser des transactions vers le réseau, mais surtout, il doit être capable de trouver de nouvelles transactions de la chaîne liées à ce portefeuille. Il existe deux types de transactions connexes : envoyer des fonds à ce portefeuille (créer une nouvelle sortie pour une adresse de ce portefeuille) et dépenser l'un des UTXO contrôlés par ce portefeuille.
Qu'est-ce qui ne va pas avec les filtres Bloom ?
Avant le BIP 158, l'approche la plus courante pour les clients légers était le filtre Bloom décrit dans le BIP 371. Le modèle d'un filtre Bloom est que vous prenez tous les objets de données qui vous intéressent (par exemple, les clés publiques de script des UTXO qui ont été dépensés et créés), les hachez un par un plusieurs fois, et ajoutez chaque résultat au In un bitmap appelé "bloom filter". Ce filtre représente ce qui vous intéresse. Ensuite, vous envoyez ce filtre à un nœud Bitcoin en qui vous avez confiance et lui demandez de vous envoyer tout ce qui correspond à ce filtre.
Le problème est que ce processus n'est pas très privé, car vous divulguez encore des informations au nœud Bitcoin qui accepte le filtre. Ils peuvent connaître les offres qui vous intéressent et celles qui ne vous intéressent pas du tout ; ils ne peuvent pas non plus vous envoyer des éléments qui correspondent aux filtres. Donc, ce n'est pas idéal pour les clients légers. Mais en même temps, ce n'est pas idéal pour les nœuds Bitcoin servant des clients légers. Chaque fois que vous envoyez un filtre, ils doivent charger le bloc concerné à partir du disque, puis déterminer si des transactions correspondent à votre filtre. Continuez simplement à envoyer de faux filtres et vous pouvez les bombarder - essentiellement une attaque DOS. Il faut très peu d'énergie pour créer un filtre, mais il en faut beaucoup pour répondre à une telle demande.
Filtre de bloc dense
OK, alors les attributs dont nous avons besoin sont :
Confidentialité renforcée
L'asymétrie de charge client-serveur est moindre. Autrement dit, il devrait y avoir moins de travail à faire côté serveur.
Moins de confiance. Les clients légers n'ont pas à s'inquiéter du fait que le serveur ne renvoie pas les transactions associées.
À l'aide d'un filtre de bloc dense, le serveur (nœud complet) construira un filtre déterministe pour chaque bloc, y compris tous les objets de données de ce bloc. Ce filtre ne doit être calculé qu'une seule fois et stocké pour toujours. Si un client léger demande un filtre pour un certain bloc, il n'y a pas d'asymétrie ici - car le serveur n'a pas besoin de faire plus de travail que le client demandeur. Le client léger peut également choisir plusieurs sources d'informations pour télécharger le bloc complet afin de s'assurer de leur cohérence ; de plus, le client léger peut toujours télécharger le bloc complet pour vérifier si le filtre fourni par le serveur est correct. Correct (correspond au bloc concerné contenu). Un autre avantage est qu'il est plus privé de cette façon. Le client léger n'a plus besoin d'envoyer l'empreinte des données qu'il souhaite au serveur. Il devient également plus difficile d'analyser l'activité d'un client léger. Une fois que le client léger a obtenu un tel filtre du serveur, il vérifie si le filtre contient les données qu'il souhaite, et si c'est le cas, le client léger demande le bloc complet. Il convient également de souligner que pour servir les clients légers de cette manière, les nœuds complets doivent conserver ces filtres, et les clients légers peuvent également vouloir conserver quelques filtres, alors gardez les filtres aussi légers que possible. La quantité est très importante ( c'est pourquoi on l'appelle "filtre à blocs denses").
très bien! Maintenant, nous entrons dans les choses rares. Comment un tel filtre est-il créé ? À quoi cela ressemble-t-il?
Quels sont nos besoins ?
Nous voulons mettre l'empreinte d'un objet spécifique dans le filtre, de sorte que lorsque les clients veulent vérifier si un bloc peut contenir quelque chose qui les concerne, ils peuvent énumérer tous les objets et vérifier si un filtre doit correspondre à ces objets.
Nous voulons que ce filtre soit aussi petit que possible.
En substance, ce que nous voulons, c'est quelque chose qui peut résumer certaines informations d'un bloc avec un volume beaucoup plus petit que le bloc.
Les informations de base contenues dans le filtre sont : la clé publique de script de chaque entrée de chaque transaction (c'est-à-dire la clé publique de script de chaque UTXO dépensé) et la clé publique de script de chaque sortie de chaque transaction. En gros c'est comme ça :
objects = {spk1, spk2, spk3, spk4, ..., spkN} // une liste de N clés publiques de script
Techniquement, nous pouvons nous arrêter ici - une telle liste de clés publiques de script peut également servir de filtre. Il s'agit d'une version condensée d'un bloc contenant les informations nécessaires aux clients légers. Avec une telle liste, un client léger peut confirmer à 100 % s'il existe une transaction intéressante dans un bloc. Mais une telle liste est très longue. Par conséquent, nos prochaines étapes consistent toutes à rendre cette liste aussi compacte que possible. C'est là que les choses deviennent intéressantes.
Tout d'abord, nous pouvons convertir chaque objet en un nombre dans une certaine plage et faire en sorte que chaque numéro d'objet soit uniformément réparti dans cette plage. Supposons que nous ayons 10 objets (N = 10), puis nous avons une sorte de fonction qui convertit chaque objet en nombre. Disons que nous choisissons la plage [0, 10] (puisque nous avons 10 objets). Maintenant, notre fonction "hash to number" prendra chaque objet en entrée et produira un nombre de taille [0, 10] respectivement. Les chiffres sont répartis uniformément sur cette plage. Cela signifie qu'après le tri, nous nous retrouverons avec un graphique comme celui-ci (dans un cas très, très idéal) :
Tout d'abord, c'est génial car nous avons considérablement réduit la taille de l'empreinte digitale de chaque objet. Désormais, chaque objet n'est plus qu'un nombre. Ainsi, notre nouveau filtre ressemble à ceci :
nombres := {1,2,3,4,5,6,7,8,9,10}
Un client léger télécharge un tel filtre, espérant savoir si un objet qu'il recherche correspond au filtre. Ils prennent simplement l'objet qui les intéresse et exécutent la même fonction "hash to number" pour voir si le résultat se trouve dans ce filtre. Où est le problème? Le problème est que les nombres dans le filtre occupent déjà toutes les possibilités dans cet espace ! Cela signifie que quels que soient les objets qui intéressent le client léger, le résultat numérique résultant doit correspondre à ce filtre. En d'autres termes, ce filtre a un "taux de faux positifs" de 1 (NDLR : Le "faux positif" signifie ici que le bloc peut ne pas contenir Le résultat obtenu par le filtre est oui). Ce n'est pas très bon. Cela montre également que dans le processus de compression des données pour générer le filtre, nous avons perdu trop d'informations. Nous avons besoin d'un taux de faux positifs plus élevé. Ensuite, supposons que nous voulions que le taux de faux positifs soit de 5. Ensuite, nous pouvons faire en sorte que les objets du bloc correspondent uniformément aux nombres dans la plage [0, 50] :
Ça a l'air mieux comme ça. Si je suis un client et que je télécharge un tel filtre, je dois vérifier si un objet qui m'intéresse se trouve dans le bloc correspondant à travers le filtre, et la probabilité que le filtre dise oui mais pas dans le bloc (faux positif) diminuera à 1/5. Super, maintenant nous mappons 10 objets sur des nombres entre 0 et 50. Cette nouvelle liste de numéros est notre filtre. Encore une fois, nous pouvons nous arrêter à tout moment, cependant, nous pouvons les compresser encore plus !
Nous avons maintenant une liste ordonnée de nombres uniformément répartis dans l'intervalle [0, 50]. Nous savons qu'il y a 10 numéros dans cette liste. Cela signifie que nous pouvons en déduire que la * différence * entre deux nombres adjacents dans cette liste ordonnée de nombres est très probablement de 5. En général, si nous avons N objets et voulons un taux de faux positifs de M, alors la taille de l'espace devrait être N * M . Autrement dit, la taille de ces nombres doit être comprise entre 0 et N * M, mais (après tri) la probabilité d'interpolation de deux nombres adjacents vérifiés est M. Et M doit être stocké plus petit que le nombre dans l'espace N * M. Ainsi, au lieu de stocker chaque nombre, nous pouvons stocker la différence entre deux nombres adjacents. Dans l'exemple ci-dessus, cela signifie qu'au lieu de stocker [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] comme filtre, nous stockons [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], à partir de laquelle il est trivial de reconstituer la liste initiale. Si vous réduisez la taille, le stockage du nombre 50 prend évidemment plus d'espace que le stockage du nombre 5. Mais pourquoi s'arrêter là ? Compressons un peu plus !
L'étape suivante consiste à utiliser "l'encodage Golomb-Rice". Cette méthode d'encodage peut très bien encoder une liste où chaque nombre du tableau est très proche d'un certain nombre. Et notre liste se trouve être juste cela! Chacun des nombres de notre liste est susceptible d'être proche de 5 (ou proche de notre taux de faux positifs, qui est M), alors prenez le quotient de chaque nombre par M (divisez chaque nombre par 5 et ignorez le reste), sera très probablement 0 (si le nombre est légèrement inférieur à 5) ou 1 (si le nombre est légèrement supérieur à 5). Il est également possible que le quotient soit 2, 3, etc., mais la probabilité est beaucoup plus faible. super! Nous pouvons donc en tirer parti : nous utiliserons le moins de bits possible pour encoder des quotients plus petits, tout en utilisant plus de bitcoins pour encoder des quotients plus grands, mais moins probables. Ensuite, il faut aussi encoder le reste (car on veut pouvoir reconstituer exactement toute la liste), qui sera toujours dans l'intervalle [0, M - 1] (ici [0, 4]). Pour l'encodeur, nous utilisons les mappages suivants :
Le mappage ci-dessus est facile à comprendre : le nombre de chiffres 1 indique le quotient que nous voulons encoder, et 0 indique la fin de l'encodage du quotient. Ainsi, pour chaque nombre de notre liste, nous pouvons utiliser le tableau ci-dessus pour coder le quotient, puis convertir le reste en binaire à l'aide d'un bittruck pouvant représenter une valeur maximale de M-1. Ici, le reste est 4, et seuls 3 bits sont nécessaires. Voici un tableau montrant les restes possibles et leurs encodages pour notre exemple :
Donc, idéalement, notre liste [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] serait codée comme suit :
Avant de passer à un cas plus réaliste, voyons si nous pouvons récupérer notre liste d'origine avec ce filtre.
Maintenant, ce que nous avons est "0000100001000010000100001000010000100001000010000". Nous connaissons le code Golomb-Rice, et nous savons que M vaut 5 (puisque ce sera de notoriété publique, connu de tous ceux qui utilisent cette construction de filtre). Puisque nous savons que M vaut 5, nous savons qu'il y aura 3 bits pour coder le reste. Ainsi, nous pouvons convertir ce filtre dans la liste de tableaux "quotient-reste" suivante :
Sachant que le quotient s'obtient en divisant par M(5), on retrouve :
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
De plus, nous savons que cette liste représente la différence entre deux nombres adjacents, nous pouvons donc restaurer la liste d'origine :
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Un exemple plus réaliste
Nous allons maintenant essayer de construire un filtre pour un vrai bloc de testnet Bitcoin. Je vais utiliser le bloc 2101914. Voyons à quoi ressemble son filtre :
Très bien mon cher, voyons comment nous pouvons construire un tel filtre à partir de blocs.
Le code complet utilisé ici peut être trouvé dans ce référentiel github. Je vais juste montrer quelques extraits de pseudocode ici. Le cœur de ce code est une fonction appelée constructFilter, qui peut être utilisée par les clients bitcoin pour appeler bitcoind et les blocs correspondants. La fonction ressemble à ceci :
func constructFilter(bc *bitcoind.Bitcoind, block bitcoind.Block) ([]octet, erreur) {
// 1 collecte tous les objets du bloc que nous voulons ajouter à un filtre
// 2 Convertit ces objets en nombres et les trie
// 3 Obtenir la différence entre deux nombres adjacents dans la liste de nombres triés
// 4 Utilisez l'encodage Golomb-Rice pour encoder ces différences
}
Ainsi, la première étape consiste à collecter tous les objets du bloc que nous voulons ajouter au filtre. À partir de BIP, nous savons que ces objets incluent toutes les clés publiques de script utilisées et chaque clé publique de script de sortie. Le BIP définit également des règles supplémentaires : nous ignorons les entrées de la transaction coinbase (ce qui n'a pas de sens car elle n'a pas d'entrées), et nous transmettons toutes les sorties OP_RETURN. Nous dédupliquons également les données. S'il existe deux clés publiques de script identiques, nous ne l'ajoutons qu'une seule fois au filtre.
// liste des objets que nous souhaitons ajouter au filtre
// Inclure toutes les clés publiques de script utilisées et chaque clé publique de script de sortie
// Nous utilisons une "map", qui supprime les clés publiques de script en double
objets := créer(carte [string] structure{})
// facilite chaque transaction dans le bloc
for i, tx := range block.Tx {
// Ajoute la clé publique du script pour chaque sortie
// dans notre liste d'objets
for _, txOut := range tx.Vout {
PubKey := txOut.PubKey
si len(PubKey) == 0 {
continuer
}
// Sauter si OP_RETURN (0x6a) est sorti
si spk [0] == 0x6a {
continuer
}
objets [skpStr] = structure{}{}
}
// ne pas ajouter l'entrée de la transaction coinbase
si je == 0 {
continuer
}
// Pour chaque entrée, obtenir sa clé publique de script
pour _, txIn := range tx.Vin {
prevTx, err := bc.GetRawTransaction(txIn.Txid)
si err != néant {
retour nul, erreur
}
PubKey := prevTx.Vout[txIn.Vout].PubKey
si len(PubKey) == 0 {
continuer
}
objets [spkStr] = structure{}{}
}
}
OK, maintenant tous les objets sont collectés. Maintenant, nous définissons la variable N comme étant la longueur du graphe d'objets. Ici, N vaut 85 .
L'étape suivante consiste à convertir notre objet en nombres uniformément répartis sur un intervalle. Encore une fois, la plage dépend du taux de faux positifs souhaité. BIP158 définit la constante M comme 784931. Cela signifie que la probabilité d'un faux positif est de 1 sur 784931. Tout comme nous l'avons fait auparavant, nous prenons le taux de faux positifs M fois N et obtenons la plage de distribution de tous les nombres. Nous définissons cette plage comme F, c'est-à-dire F = M * N . Ici, F = 66719135. Je ne vais pas entrer dans les détails des fonctions qui mappent les objets aux nombres (vous pouvez trouver les détails dans le référentiel github lié ci-dessus). Tout ce que vous devez savoir, c'est qu'il prend en entrée l'objet, la constante F (qui définit la portée à laquelle l'objet doit être mappé) et une clé (le hachage de bloc). Une fois que nous avons tous les nombres, nous trions la liste par ordre croissant, puis créons une nouvelle liste appelée différences qui contient la différence entre deux nombres adjacents dans la liste triée des nombres.
nombres := faire([]uint64, 0, N)
// Itérer à travers tous les objets et les convertir en nombres uniformément répartis dans la plage [0, F]
// et stocker ces nombres sous forme de liste de nombres
pour o := objets de plage {
// En utilisant la clé donnée, le nombre maximum (F) et les octets d'objet (o),
// convertit l'objet en un nombre compris entre 0 et F.
v := convertToNumber(b, F, clé)
nombres = ajouter(nombres, v)
}
// trie la liste des nombres
sort.Slice(numbers, func(i, j int) bool { renvoie des nombres [i] < nombres [j] })
// Convertit la liste de nombres en liste de différences
différences := faire([]uint64, N)
for i, num := gamme de nombres {
si je == 0 {
différences [i] = nombre
continuer
}
différences [i] = nombre - nombres[i-1]
}
super! Voici une image montrant une liste de nombres et de différences.
Lorsque vous effectuez un zoom arrière, les 85 numéros sont répartis uniformément dans l'espace ! Ainsi, les valeurs dans la liste des différences sont également très petites.
La dernière étape consiste à encoder la liste des différences à l'aide de l'encodage Golomb-Rice. Rappelez-vous de l'explication précédente que nous devons diviser chaque différence par la valeur la plus probable, puis encoder le quotient et le reste. Dans notre exemple précédent, j'ai dit que la valeur la plus probable est M, et le reste sera compris entre [0, M]. Cependant, BIP158 ne le fait pas, car nous avons trouvé 2, qui n'est pas le paramètre qui minimise réellement la taille finale du filtre. Ainsi, au lieu d'utiliser M, nous définissons une nouvelle constante P et utilisons 2^P comme paramètre de Golomb-Rice. P est défini comme 19 . Cela signifie que nous divisons chaque différence par 2 ^ 19 pour obtenir le quotient et le reste, et le reste est codé en binaire avec 19 bits.
filtre := bstream.NewBStreamWriter(0)
// Pour chaque valeur de la liste des différences, obtenez le quotient et le reste en divisant par 2^P.
pour _, d := différences de plage {
q := math.Floor(float64(d)/math.Exp2(float64(P)))
r := d - uint64(math.Exp2(float64(P))*q)
// Encodeur
pour je := 0; je < int(q); je++ {
filtre.WriteBit(true)
}
filtre.WriteBit(false)
filtre.WriteBits(r, P)
}
super! Nous pouvons maintenant sortir le filtre, obtenant :
Exactement le même filtre que nous avons obtenu en bitcoind sauf pour les deux premiers octets ! Pourquoi y a-t-il une différence dans les 2 premiers octets ? Parce que BIP dit que la valeur de N doit être encodée au format CompactSize et apparaître devant le filtre pour qu'elle puisse être décodée par le récepteur. Cela se fait par :
Cependant, ma compréhension personnelle est qu'il n'est pas nécessaire d'ajouter N au filtre. Si vous connaissez la valeur de P, alors vous pouvez trouver la valeur de N. Voyons si nous pouvons restaurer la liste originale de nombres en utilisant la sortie du premier filtre :
b := bstream.NewBStreamReader(filtre)
(
nombres []uint64
prevNum uint64
)
pour {
// Lit le quotient de la chaîne d'octets. Le premier 0 rencontré indique la fin du quotient
// Avant de rencontrer 0, le nombre de 1 représente le quotient
q uint64
c, err := b.ReadBit()
si err != néant {
erreur de retour
}
pour c {
q++
c, err = b.ReadBit()
si erreurs.Is(err, io.EOF) {
casser
} sinon si err != néant {
erreur de retour
}
}
// Les P bits suivants encodent le reste
r, err := b.ReadBits(P)
si erreurs.Is(err, io.EOF) {
casser
} sinon si err != néant {
erreur de retour
}
n := q*uint64(math.Exp2(float64(P))) + r
num := n + prevNum
nombres = ajouter(nombres, num)
prevNum = num
}
fmt.Println(nombres)
L'opération ci-dessus produit la même liste de nombres, nous pouvons donc la reconstruire sans connaître N. Je ne sais donc pas quelle est la raison d'être de l'ajout de N au filtre. Si vous savez pourquoi N doit être inclus, faites-le moi savoir !
Merci d'avoir lu!
Voir l'original
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Le filtre à blocs denses BIP 158 expliqué
Par Elle Mouton
Dans cet article, je décris brièvement le besoin de clients légers dans Bitcoin et pourquoi les "filtres de bloc compacts" répondent mieux à ce besoin que les "filtres Bloom". J'explique ensuite en détail le fonctionnement du filtre de bloc dense, avec une procédure pas à pas pour créer un tel filtre sur un testnet.
Signification du filtre de bloc
Un client bitcoin light (logiciel bitcoin light) est un logiciel dont le but n'est pas de stocker la blockchain bitcoin mais de supporter un portefeuille bitcoin. Cela signifie qu'il doit être capable de diffuser des transactions vers le réseau, mais surtout, il doit être capable de trouver de nouvelles transactions de la chaîne liées à ce portefeuille. Il existe deux types de transactions connexes : envoyer des fonds à ce portefeuille (créer une nouvelle sortie pour une adresse de ce portefeuille) et dépenser l'un des UTXO contrôlés par ce portefeuille.
Qu'est-ce qui ne va pas avec les filtres Bloom ?
Avant le BIP 158, l'approche la plus courante pour les clients légers était le filtre Bloom décrit dans le BIP 371. Le modèle d'un filtre Bloom est que vous prenez tous les objets de données qui vous intéressent (par exemple, les clés publiques de script des UTXO qui ont été dépensés et créés), les hachez un par un plusieurs fois, et ajoutez chaque résultat au In un bitmap appelé "bloom filter". Ce filtre représente ce qui vous intéresse. Ensuite, vous envoyez ce filtre à un nœud Bitcoin en qui vous avez confiance et lui demandez de vous envoyer tout ce qui correspond à ce filtre.
Le problème est que ce processus n'est pas très privé, car vous divulguez encore des informations au nœud Bitcoin qui accepte le filtre. Ils peuvent connaître les offres qui vous intéressent et celles qui ne vous intéressent pas du tout ; ils ne peuvent pas non plus vous envoyer des éléments qui correspondent aux filtres. Donc, ce n'est pas idéal pour les clients légers. Mais en même temps, ce n'est pas idéal pour les nœuds Bitcoin servant des clients légers. Chaque fois que vous envoyez un filtre, ils doivent charger le bloc concerné à partir du disque, puis déterminer si des transactions correspondent à votre filtre. Continuez simplement à envoyer de faux filtres et vous pouvez les bombarder - essentiellement une attaque DOS. Il faut très peu d'énergie pour créer un filtre, mais il en faut beaucoup pour répondre à une telle demande.
Filtre de bloc dense
OK, alors les attributs dont nous avons besoin sont :
À l'aide d'un filtre de bloc dense, le serveur (nœud complet) construira un filtre déterministe pour chaque bloc, y compris tous les objets de données de ce bloc. Ce filtre ne doit être calculé qu'une seule fois et stocké pour toujours. Si un client léger demande un filtre pour un certain bloc, il n'y a pas d'asymétrie ici - car le serveur n'a pas besoin de faire plus de travail que le client demandeur. Le client léger peut également choisir plusieurs sources d'informations pour télécharger le bloc complet afin de s'assurer de leur cohérence ; de plus, le client léger peut toujours télécharger le bloc complet pour vérifier si le filtre fourni par le serveur est correct. Correct (correspond au bloc concerné contenu). Un autre avantage est qu'il est plus privé de cette façon. Le client léger n'a plus besoin d'envoyer l'empreinte des données qu'il souhaite au serveur. Il devient également plus difficile d'analyser l'activité d'un client léger. Une fois que le client léger a obtenu un tel filtre du serveur, il vérifie si le filtre contient les données qu'il souhaite, et si c'est le cas, le client léger demande le bloc complet. Il convient également de souligner que pour servir les clients légers de cette manière, les nœuds complets doivent conserver ces filtres, et les clients légers peuvent également vouloir conserver quelques filtres, alors gardez les filtres aussi légers que possible. La quantité est très importante ( c'est pourquoi on l'appelle "filtre à blocs denses").
très bien! Maintenant, nous entrons dans les choses rares. Comment un tel filtre est-il créé ? À quoi cela ressemble-t-il?
Quels sont nos besoins ?
Les informations de base contenues dans le filtre sont : la clé publique de script de chaque entrée de chaque transaction (c'est-à-dire la clé publique de script de chaque UTXO dépensé) et la clé publique de script de chaque sortie de chaque transaction. En gros c'est comme ça :
objects = {spk1, spk2, spk3, spk4, ..., spkN} // une liste de N clés publiques de script
Techniquement, nous pouvons nous arrêter ici - une telle liste de clés publiques de script peut également servir de filtre. Il s'agit d'une version condensée d'un bloc contenant les informations nécessaires aux clients légers. Avec une telle liste, un client léger peut confirmer à 100 % s'il existe une transaction intéressante dans un bloc. Mais une telle liste est très longue. Par conséquent, nos prochaines étapes consistent toutes à rendre cette liste aussi compacte que possible. C'est là que les choses deviennent intéressantes.
Tout d'abord, nous pouvons convertir chaque objet en un nombre dans une certaine plage et faire en sorte que chaque numéro d'objet soit uniformément réparti dans cette plage. Supposons que nous ayons 10 objets (N = 10), puis nous avons une sorte de fonction qui convertit chaque objet en nombre. Disons que nous choisissons la plage [0, 10] (puisque nous avons 10 objets). Maintenant, notre fonction "hash to number" prendra chaque objet en entrée et produira un nombre de taille [0, 10] respectivement. Les chiffres sont répartis uniformément sur cette plage. Cela signifie qu'après le tri, nous nous retrouverons avec un graphique comme celui-ci (dans un cas très, très idéal) :
nombres := {1,2,3,4,5,6,7,8,9,10}
Un client léger télécharge un tel filtre, espérant savoir si un objet qu'il recherche correspond au filtre. Ils prennent simplement l'objet qui les intéresse et exécutent la même fonction "hash to number" pour voir si le résultat se trouve dans ce filtre. Où est le problème? Le problème est que les nombres dans le filtre occupent déjà toutes les possibilités dans cet espace ! Cela signifie que quels que soient les objets qui intéressent le client léger, le résultat numérique résultant doit correspondre à ce filtre. En d'autres termes, ce filtre a un "taux de faux positifs" de 1 (NDLR : Le "faux positif" signifie ici que le bloc peut ne pas contenir Le résultat obtenu par le filtre est oui). Ce n'est pas très bon. Cela montre également que dans le processus de compression des données pour générer le filtre, nous avons perdu trop d'informations. Nous avons besoin d'un taux de faux positifs plus élevé. Ensuite, supposons que nous voulions que le taux de faux positifs soit de 5. Ensuite, nous pouvons faire en sorte que les objets du bloc correspondent uniformément aux nombres dans la plage [0, 50] :
Nous avons maintenant une liste ordonnée de nombres uniformément répartis dans l'intervalle [0, 50]. Nous savons qu'il y a 10 numéros dans cette liste. Cela signifie que nous pouvons en déduire que la * différence * entre deux nombres adjacents dans cette liste ordonnée de nombres est très probablement de 5. En général, si nous avons N objets et voulons un taux de faux positifs de M, alors la taille de l'espace devrait être N * M . Autrement dit, la taille de ces nombres doit être comprise entre 0 et N * M, mais (après tri) la probabilité d'interpolation de deux nombres adjacents vérifiés est M. Et M doit être stocké plus petit que le nombre dans l'espace N * M. Ainsi, au lieu de stocker chaque nombre, nous pouvons stocker la différence entre deux nombres adjacents. Dans l'exemple ci-dessus, cela signifie qu'au lieu de stocker [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] comme filtre, nous stockons [0, 5, 5, 5, 5 , 5, 5, 5, 5, 5], à partir de laquelle il est trivial de reconstituer la liste initiale. Si vous réduisez la taille, le stockage du nombre 50 prend évidemment plus d'espace que le stockage du nombre 5. Mais pourquoi s'arrêter là ? Compressons un peu plus !
L'étape suivante consiste à utiliser "l'encodage Golomb-Rice". Cette méthode d'encodage peut très bien encoder une liste où chaque nombre du tableau est très proche d'un certain nombre. Et notre liste se trouve être juste cela! Chacun des nombres de notre liste est susceptible d'être proche de 5 (ou proche de notre taux de faux positifs, qui est M), alors prenez le quotient de chaque nombre par M (divisez chaque nombre par 5 et ignorez le reste), sera très probablement 0 (si le nombre est légèrement inférieur à 5) ou 1 (si le nombre est légèrement supérieur à 5). Il est également possible que le quotient soit 2, 3, etc., mais la probabilité est beaucoup plus faible. super! Nous pouvons donc en tirer parti : nous utiliserons le moins de bits possible pour encoder des quotients plus petits, tout en utilisant plus de bitcoins pour encoder des quotients plus grands, mais moins probables. Ensuite, il faut aussi encoder le reste (car on veut pouvoir reconstituer exactement toute la liste), qui sera toujours dans l'intervalle [0, M - 1] (ici [0, 4]). Pour l'encodeur, nous utilisons les mappages suivants :
0000 10000 10000 10000 10000 10000 10000 10000 10000 10000
Avant de passer à un cas plus réaliste, voyons si nous pouvons récupérer notre liste d'origine avec ce filtre.
Maintenant, ce que nous avons est "0000100001000010000100001000010000100001000010000". Nous connaissons le code Golomb-Rice, et nous savons que M vaut 5 (puisque ce sera de notoriété publique, connu de tous ceux qui utilisent cette construction de filtre). Puisque nous savons que M vaut 5, nous savons qu'il y aura 3 bits pour coder le reste. Ainsi, nous pouvons convertir ce filtre dans la liste de tableaux "quotient-reste" suivante :
[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1, 0), (1, 0)]
Sachant que le quotient s'obtient en divisant par M(5), on retrouve :
[0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
De plus, nous savons que cette liste représente la différence entre deux nombres adjacents, nous pouvons donc restaurer la liste d'origine :
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
Un exemple plus réaliste
Nous allons maintenant essayer de construire un filtre pour un vrai bloc de testnet Bitcoin. Je vais utiliser le bloc 2101914. Voyons à quoi ressemble son filtre :
$ bitcoin-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "filtre": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df574378640 23833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a6 5a5b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34 b56ade12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "header": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }
Très bien mon cher, voyons comment nous pouvons construire un tel filtre à partir de blocs.
Le code complet utilisé ici peut être trouvé dans ce référentiel github. Je vais juste montrer quelques extraits de pseudocode ici. Le cœur de ce code est une fonction appelée constructFilter, qui peut être utilisée par les clients bitcoin pour appeler bitcoind et les blocs correspondants. La fonction ressemble à ceci :
func constructFilter(bc *bitcoind.Bitcoind, block bitcoind.Block) ([]octet, erreur) { // 1 collecte tous les objets du bloc que nous voulons ajouter à un filtre // 2 Convertit ces objets en nombres et les trie // 3 Obtenir la différence entre deux nombres adjacents dans la liste de nombres triés // 4 Utilisez l'encodage Golomb-Rice pour encoder ces différences }
Ainsi, la première étape consiste à collecter tous les objets du bloc que nous voulons ajouter au filtre. À partir de BIP, nous savons que ces objets incluent toutes les clés publiques de script utilisées et chaque clé publique de script de sortie. Le BIP définit également des règles supplémentaires : nous ignorons les entrées de la transaction coinbase (ce qui n'a pas de sens car elle n'a pas d'entrées), et nous transmettons toutes les sorties OP_RETURN. Nous dédupliquons également les données. S'il existe deux clés publiques de script identiques, nous ne l'ajoutons qu'une seule fois au filtre.
// liste des objets que nous souhaitons ajouter au filtre // Inclure toutes les clés publiques de script utilisées et chaque clé publique de script de sortie // Nous utilisons une "map", qui supprime les clés publiques de script en double objets := créer(carte [string] structure{}) // facilite chaque transaction dans le bloc for i, tx := range block.Tx { // Ajoute la clé publique du script pour chaque sortie // dans notre liste d'objets for _, txOut := range tx.Vout { PubKey := txOut.PubKey si len(PubKey) == 0 { continuer } // Sauter si OP_RETURN (0x6a) est sorti si spk [0] == 0x6a { continuer } objets [skpStr] = structure{}{} } // ne pas ajouter l'entrée de la transaction coinbase si je == 0 { continuer } // Pour chaque entrée, obtenir sa clé publique de script pour _, txIn := range tx.Vin { prevTx, err := bc.GetRawTransaction(txIn.Txid) si err != néant { retour nul, erreur } PubKey := prevTx.Vout[txIn.Vout].PubKey si len(PubKey) == 0 { continuer } objets [spkStr] = structure{}{} } }
OK, maintenant tous les objets sont collectés. Maintenant, nous définissons la variable N comme étant la longueur du graphe d'objets. Ici, N vaut 85 .
L'étape suivante consiste à convertir notre objet en nombres uniformément répartis sur un intervalle. Encore une fois, la plage dépend du taux de faux positifs souhaité. BIP158 définit la constante M comme 784931. Cela signifie que la probabilité d'un faux positif est de 1 sur 784931. Tout comme nous l'avons fait auparavant, nous prenons le taux de faux positifs M fois N et obtenons la plage de distribution de tous les nombres. Nous définissons cette plage comme F, c'est-à-dire F = M * N . Ici, F = 66719135. Je ne vais pas entrer dans les détails des fonctions qui mappent les objets aux nombres (vous pouvez trouver les détails dans le référentiel github lié ci-dessus). Tout ce que vous devez savoir, c'est qu'il prend en entrée l'objet, la constante F (qui définit la portée à laquelle l'objet doit être mappé) et une clé (le hachage de bloc). Une fois que nous avons tous les nombres, nous trions la liste par ordre croissant, puis créons une nouvelle liste appelée différences qui contient la différence entre deux nombres adjacents dans la liste triée des nombres.
nombres := faire([]uint64, 0, N) // Itérer à travers tous les objets et les convertir en nombres uniformément répartis dans la plage [0, F] // et stocker ces nombres sous forme de liste de nombres pour o := objets de plage { // En utilisant la clé donnée, le nombre maximum (F) et les octets d'objet (o), // convertit l'objet en un nombre compris entre 0 et F. v := convertToNumber(b, F, clé) nombres = ajouter(nombres, v) } // trie la liste des nombres sort.Slice(numbers, func(i, j int) bool { renvoie des nombres [i] < nombres [j] }) // Convertit la liste de nombres en liste de différences différences := faire([]uint64, N) for i, num := gamme de nombres { si je == 0 { différences [i] = nombre continuer } différences [i] = nombre - nombres[i-1] }
super! Voici une image montrant une liste de nombres et de différences.
La dernière étape consiste à encoder la liste des différences à l'aide de l'encodage Golomb-Rice. Rappelez-vous de l'explication précédente que nous devons diviser chaque différence par la valeur la plus probable, puis encoder le quotient et le reste. Dans notre exemple précédent, j'ai dit que la valeur la plus probable est M, et le reste sera compris entre [0, M]. Cependant, BIP158 ne le fait pas, car nous avons trouvé 2, qui n'est pas le paramètre qui minimise réellement la taille finale du filtre. Ainsi, au lieu d'utiliser M, nous définissons une nouvelle constante P et utilisons 2^P comme paramètre de Golomb-Rice. P est défini comme 19 . Cela signifie que nous divisons chaque différence par 2 ^ 19 pour obtenir le quotient et le reste, et le reste est codé en binaire avec 19 bits.
filtre := bstream.NewBStreamWriter(0) // Pour chaque valeur de la liste des différences, obtenez le quotient et le reste en divisant par 2^P. pour _, d := différences de plage { q := math.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // Encodeur pour je := 0; je < int(q); je++ { filtre.WriteBit(true) } filtre.WriteBit(false) filtre.WriteBits(r, P) }
super! Nous pouvons maintenant sortir le filtre, obtenant :
71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0 b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade 12fa2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
Exactement le même filtre que nous avons obtenu en bitcoind sauf pour les deux premiers octets ! Pourquoi y a-t-il une différence dans les 2 premiers octets ? Parce que BIP dit que la valeur de N doit être encodée au format CompactSize et apparaître devant le filtre pour qu'elle puisse être décodée par le récepteur. Cela se fait par :
fd := filtre.Bytes() buffer bytes.Buffer buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = wire.WriteInt(&buffer, 0, uint64(N)) si err != néant { retour nul, erreur } _, err = buffer.Write(fd) si err != néant { retour nul, erreur }
Si nous imprimons à nouveau le filtre, nous constaterons qu'il est exactement le même que le résultat de bitcoind :
5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5 b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b5 6ade12fa 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270
succès!
Cependant, ma compréhension personnelle est qu'il n'est pas nécessaire d'ajouter N au filtre. Si vous connaissez la valeur de P, alors vous pouvez trouver la valeur de N. Voyons si nous pouvons restaurer la liste originale de nombres en utilisant la sortie du premier filtre :
b := bstream.NewBStreamReader(filtre) ( nombres []uint64 prevNum uint64 ) pour { // Lit le quotient de la chaîne d'octets. Le premier 0 rencontré indique la fin du quotient // Avant de rencontrer 0, le nombre de 1 représente le quotient q uint64 c, err := b.ReadBit() si err != néant { erreur de retour } pour c { q++ c, err = b.ReadBit() si erreurs.Is(err, io.EOF) { casser } sinon si err != néant { erreur de retour } } // Les P bits suivants encodent le reste r, err := b.ReadBits(P) si erreurs.Is(err, io.EOF) { casser } sinon si err != néant { erreur de retour } n := q*uint64(math.Exp2(float64(P))) + r num := n + prevNum nombres = ajouter(nombres, num) prevNum = num } fmt.Println(nombres)
L'opération ci-dessus produit la même liste de nombres, nous pouvons donc la reconstruire sans connaître N. Je ne sais donc pas quelle est la raison d'être de l'ajout de N au filtre. Si vous savez pourquoi N doit être inclus, faites-le moi savoir !
Merci d'avoir lu!