Utreexo: compresser beaucoup de Bitcoin UTXO

Bonjour, Habr!

Dans le réseau Bitcoin, tous les nœuds s'accordent par consensus sur les nombreux UTXO: combien de pièces sont disponibles pour les dépenses, à qui et dans quelles conditions. Un ensemble d'UTXO est un ensemble de données qui est minimalement nécessaire pour un nœud de validation, sans lequel un nœud ne peut pas vérifier la validité des transactions entrantes et les blocs qui les contiennent.

A cet égard, des efforts sont faits de toutes les manières pour réduire la représentation stockée de cet ensemble, pour le comprimer sans perte de garanties de sécurité. Plus le volume de données stockées est petit, plus les exigences d'espace disque du noeud de validation sont faibles, ce qui rend le lancement du noeud de validation bon marché, vous permet d'étendre le réseau et ainsi d'augmenter la stabilité du réseau.

Dans cette note, nous couvrirons le prototype Rust d'une proposition récente du co-auteur de Lightning Network Paper , Thaddeus Dryja - Utreexo: un accumulateur dynamique basé sur le hachage optimisé pour l'ensemble Bitcoin UTXO , qui réduit les besoins en espace disque pour les nœuds de validation.

Quel est le problème?

L'un des problèmes éternels du Bitcoin était son évolutivité. L'idée de «posséder une banque» oblige les participants au réseau à garder une trace de tous les fonds disponibles à utiliser. Dans Bitcoin, les fonds disponibles sont exprimés comme un ensemble de sorties non dépensées - ensemble UTXO. Bien que ce ne soit pas une vue très intuitive, il est avantageux en termes de performances d'implémentation, par rapport à une vue dans laquelle chaque portefeuille a un «équilibre» en tant qu'entrée distincte, et ajoute également de la confidentialité (par exemple, CoinJoin fournit du travail).

Il est important de faire la distinction entre l'historique des transactions (ce qu'on appelle une blockchain) et l'état actuel du système. L'historique des transactions de Bitcoin occupe actuellement environ 200 Go d'espace disque et continue de croître. Cependant, l'état du système est beaucoup plus petit, environ 4 Go, et ne prend en compte que le fait que quelqu'un possède actuellement des pièces. Le volume de ces données augmente également avec le temps, mais à un rythme beaucoup plus faible et tend même parfois à diminuer (voir KDPV).

Les clients légers (SPV) échangent des garanties de sécurité contre la possibilité de ne stocker aucun état minimum (ensemble UTXO), à l'exception des clés privées.

UTXO et UTXO-set

UTXO (sortie de transaction non dépensée) - sortie de transaction non dépensée, le point final du voyage de chaque satoshi transmis dans les transactions. Les sorties non dépensées deviennent des entrées de nouvelles transactions et passent en même temps et sont supprimées de l'ensemble UTXO.

Les nouveaux UTXO sont toujours créés par des transactions:

• transactions Coinbase sans intrants: créez de nouveaux UTXO lors de l'émission de pièces par les mineurs
• transactions conventionnelles: créez de nouveaux UTXO, tout en dépensant un ensemble d'UTXO existants

Le processus de travail avec UTXO:

Les portefeuilles tiennent compte du nombre de pièces disponibles pour les dépenses (solde) en fonction du montant d'UTXO disponible pour ce portefeuille pour les dépenses.

Chaque nœud de validateur, pour éviter les tentatives de double dépense, doit suivre la collecte de tous les UTXO lors de la vérification de chaque transaction de chaque bloc.

Le nœud doit avoir une logique:

• Ajouts à l'ensemble UTXO
• Suppressions définies par UTXO
• Vérifie la présence d'un seul UTXO dans l'ensemble

Il existe des moyens de réduire les exigences relatives aux informations stockées sur l'ensemble, tout en conservant la possibilité d'ajouter et de supprimer des éléments, de vérifier et de prouver l'existence d'un élément dans l'ensemble à l'aide de batteries cryptographiques .

Batteries pour UTXO

L'idée d'utiliser des batteries pour stocker de nombreux UTXO a été discutée précédemment .

UTXO-set est construit à la volée, pendant le chargement initial de la chaîne de blocs (IBD, téléchargement de bloc initial), est stocké en totalité et en permanence, tandis que son contenu change après le traitement des transactions de chaque nouveau bloc réseau correct. Ce processus nécessite le téléchargement d'environ 200 Go de blocs de données et la vérification de centaines de millions de signatures numériques. Une fois le processus IBD terminé, dans le résidu sec, l'ensemble UTXO occupera environ 4 Go.

Cependant, lors de l'utilisation de piles, les règles de consensus concernant les fonds se résument à la vérification et à la génération de preuves cryptographiques, et le fardeau du suivi des fonds disponibles est placé sur les épaules du propriétaire de ces fonds, ce qui fournit la preuve de leur présence et de leur propriété.

La batterie peut être appelée une représentation compacte de l'ensemble. Dans ce cas, la taille de la vue stockée doit être constante $$$O (1)$ , ou augmenter de façon sublinéaire par rapport à la puissance de l'ensemble et à la taille de l'élément lui-même, par exemple $$$O (log (n))$ où n est la puissance de l'ensemble stocké.

Dans ce cas, l'accumulateur doit permettre de générer des preuves de l'inclusion d'un élément dans l'ensemble (preuve d'inclusion) et lui permettre de vérifier efficacement cette preuve.

Une batterie est appelée dynamique si elle vous permet d'ajouter des éléments et de supprimer des éléments de l'ensemble.

Un exemple d'une telle batterie est la batterie RSA proposée par Boneh, Bunz, Fisch en décembre 2018 . Une telle batterie a une taille constante de la vue stockée, mais nécessite un secret partagé (configuration de confiance). Cette exigence annule l'applicabilité d'un tel accumulateur pour les réseaux sans confiance tels que Bitcoin, car les fuites de données lors de la génération d'un secret peuvent permettre aux attaquants de créer de fausses preuves de l'existence d'UTXO en usurpant des nœuds avec un ensemble UTXO basé sur un tel accumulateur.

Utreexo

La conception proposée par Thatredeus Dryja d'Utreexo vous permet de créer une batterie dynamique sans configuration de confiance.

Utreexo est une forêt d' arbres de Merkle binaires idéaux et est un développement des idées présentées dans Accumulateurs asynchrones efficaces pour pki distribué , ajoutant la possibilité de supprimer des éléments de l'ensemble.

La structure logique de la batterie

Les cellules de la batterie sont disposées dans une forêt d'arbres binaires parfaits. Les arbres sont classés par hauteur. Cette présentation a été choisie comme la plus visuelle et permet de visualiser la fusion des arbres lors des opérations sur la batterie.

L'auteur note que puisque tous les arbres de la forêt sont parfaits, leur hauteur est exprimée par la puissance de deux, tout comme n'importe quel nombre naturel peut être représenté comme la somme des puissances de deux. Par conséquent, tout ensemble de feuilles peut être regroupé sous la forme d'arbres binaires et, dans tous les cas, l'ajout d'un nouvel élément nécessite une connaissance uniquement des nœuds racine des arbres stockés .

Ainsi, la vue stockée de la batterie Utreexo est une liste de nœuds racine (racine Merkle), et non la forêt entière d'arbres .

Imaginez la liste des éléments racine comme Vec<Option<Hash>> . Le type Option<Hash> optionnel indique que l'élément racine peut être manquant, ce qui signifie que l'arbre n'a pas d'arbre avec une hauteur appropriée.

 /// SHA-256  #[derive(Copy, Clone, Hash, Eq, PartialEq)] pub struct Hash(pub [u8; 32]); #[derive(Debug, Clone)] pub struct Utreexo { pub roots: Vec<Option<Hash>>, } impl Utreexo { pub fn new(capacity: usize) -> Self { Utreexo { roots: vec![None; capacity], } } } 

Ajout d'éléments

Tout d'abord, nous décrivons la fonction parent() , qui reconnaît le nœud parent pour deux éléments donnés.

 fn hash(bytes: &[u8]) -> Hash { let mut sha = Sha256::new(); sha.input(bytes); let res = sha.result(); let mut res_bytes = [0u8; 32]; res_bytes.copy_from_slice(res.as_slice()); Hash(res_bytes) } fn parent(left: &Hash, right: &Hash) -> Hash { let concat = left .0 .into_iter() .chain(right.0.into_iter()) .map(|b| *b) .collect::<Vec<_>>(); hash(&concat[..]) } 

Lors de l'ajout d'éléments à la batterie, vous devez garder une trace des éléments racine qui sont modifiés. En suivant le chemin de modification des éléments racine pour chaque élément ajouté, vous pourrez ultérieurement construire une preuve de la présence de ces éléments.

 #[derive(Debug)] pub struct Update<'a> { pub utreexo: &'a mut Utreexo, // ProofStep  ""     pub updated: HashMap<Hash, ProofStep>, } 

Pour ajouter un élément à la batterie, vous avez besoin de:

• Créez un tableau de paniers d'éléments racine new_roots et placez-y les éléments racine existants, un pour chaque panier:

 let mut new_roots = Vec::new(); for root in self.roots.iter() { let mut vec = Vec::<Hash>::new(); if let Some(hash) = root { vec.push(*hash); } new_roots.push(vec); } 

• Ajoutez les éléments ajoutés (tableau d' insertions ) au premier panier new_roots[0] :

 new_roots[0].extend_from_slice(insertions); 

• Procéder à la «coalescence» des articles ajoutés au premier panier avec le reste:
  
  • Pour tous les paniers contenant plus d'un article:
    
    1. Nous prenons deux éléments de la fin du panier, calculons leur parent, supprimons les deux éléments
    2. Ajoutez le parent calculé au panier suivant.

 for i in 0..new_roots.len() { while new_roots[i].len() > 1 { //         let a = new_roots[i][new_roots[i].len() - 2]; let b = new_roots[i][new_roots[i].len() - 1]; new_roots[i].pop(); new_roots[i].pop(); let hash = self.parent(&a, &b); //      if new_roots.len() <= i + 1 { new_roots.push(vec![]); } //      new_roots[i + 1].push(hash); //    ; //        updated.insert(a, ProofStep { hash: b, is_left: false }); updated.insert(b, ProofStep {hash: a, is_left: true }); } } 

• Déplacer les éléments racine des paniers vers le réseau de batteries résultant

 for (i, bucket) in new_roots.into_iter().enumerate() { //     if self.roots.len() <= i { self.roots.push(None); } if bucket.is_empty() { self.roots[i] = None; } else { self.roots[i] = Some(bucket[0]); } } 

Création de preuves pour les éléments ajoutés

La preuve de l'inclusion de l'élément dans la batterie ( Proof ) sera le Merkle Path, composé d'une chaîne de ProofStep . Si le chemin ne mène nulle part, alors la preuve est fausse.

 ///         . #[derive(Debug, Copy, Clone)] pub struct ProofStep { pub hash: Hash, pub is_left: bool, } ///   .       . #[derive(Debug, Clone)] pub struct Proof { pub steps: Vec<ProofStep>, pub leaf: Hash, } 

En utilisant les informations obtenues précédemment lors de l'ajout de l'élément (structure de Update ), vous pouvez créer la preuve que l'élément a été ajouté à la batterie. Pour ce faire, nous contournons le tableau des modifications apportées et ajoutons chaque étape au chemin de Merkle, qui servira ensuite de preuve:

 impl<'a> Update<'a> { pub fn prove(&self, leaf: &Hash) -> Proof { let mut proof = Proof { steps: vec![], leaf: *leaf, }; let mut item = *leaf; while let Some(s) = self.updated.get(&item) { proof.steps.push(*s); item = parent(&item, &s); } proof } } 

Preuve de preuve d'un article

La vérification de la preuve de l'inclusion de l'élément (preuve d'inclusion) se réduit à suivre le chemin de Merkle, jusqu'à ce qu'elle mène à l'élément racine existant:

 pub fn verify(&self, proof: &Proof) -> bool { let n = proof.steps.len(); if n >= self.roots.len() { return false; } let expected = self.roots[n]; if let Some(expected) = expected { let mut current_parent = proof.leaf; for s in proof.steps.iter() { current_parent = if s.is_left { parent(&s.hash, &current_parent) } else { parent(&current_parent, &s.hash) }; } current_parent == expected } else { false } } 

Clairement:

Supprimer des éléments

Pour retirer un élément de la batterie, vous devez fournir une preuve valide que l'élément est là. En utilisant les données de la preuve, nous pouvons calculer les nouveaux éléments racine de la batterie pour lesquels cette preuve ne sera plus vraie.

L'algorithme est le suivant:

1. Comme pour l'ajout, nous organisons un ensemble de paniers vides correspondant aux arbres de Merkle avec une hauteur égale à deux de l'indice du panier
2. Insérez des articles des étapes du chemin Merkle dans les paniers l'indice du panier est égal au numéro de pas actuel
3. Nous supprimons l'élément racine auquel mène le chemin de la preuve.
4. Comme pour l'ajout, nous calculons les nouveaux éléments racine, en combinant les éléments des paniers par paires et en déplaçant le résultat de l'union vers le panier suivant

 fn delete(&self, proof: &Proof, new_roots: &mut Vec<Vec<Hash>>) -> Result<(), ()> { if self.roots.len() < proof.steps.len() || self.roots.get(proof.steps.len()).is_none() { return Err(()); } let mut height = 0; let mut hash = proof.leaf; let mut s; loop { if height < new_roots.len() { let (index, ok) = self.find_root(&hash, &new_roots[height]); if ok { // Remove hash from new_roots new_roots[height].remove(index); loop { if height >= proof.steps.len() { if !self.roots[height] .and_then(|h| Some(h == hash)) .unwrap_or(false) { return Err(()); } return Ok(()); } s = proof.steps[height]; hash = self.parent(&hash, &s); height += 1; } } } if height >= proof.steps.len() { return Err(()); } while height > new_roots.len() { new_roots.push(vec![]); } s = proof.steps[height]; new_roots[height].push(s.hash); hash = self.parent(&hash, &s); height += 1; } } 

Le processus de suppression de l'élément "A":

Intégration dans un réseau existant

En utilisant la batterie proposée, les nœuds peuvent refuser d'utiliser la base de données pour stocker tous les UTXO, tout en conservant la possibilité de changer l'ensemble UTXO. Cependant, il y a le problème de travailler avec des preuves.

Nous appellerons un nœud de validation qui utilise un compact de batterie UTXO (nœud à état compact), et un validateur sans batterie - plein (nœud complet). L'existence de deux classes de nœuds pose le problème de leur intégration dans un même réseau, car les nœuds compacts nécessitent une preuve de l'existence d'UTXO, qui est dépensé en transactions, mais pas les nœuds complets. Si tous les nœuds du réseau en même temps et de manière coordonnée ne passent pas à Utreexo, les nœuds compacts seront laissés pour compte et ne pourront pas travailler sur le réseau Bitcoin.

Pour résoudre le problème de l'intégration de nœuds compacts dans le réseau, il est proposé d'introduire une classe supplémentaire de nœuds - ponts . Un nœud de pont est un nœud complet qui, entre autres, stocke la batterie Utreexo et les preuves d'inclusion pour tous les UTXO de l'ensemble UTXO. Les ponts calculent de nouveaux hachages et mettent à jour la batterie et les preuves à mesure que de nouveaux blocs arrivent avec les transactions. La prise en charge et la mise à jour de la batterie et des preuves n'imposent pas de charge de calcul supplémentaire à ces nœuds. Les ponts sacrifient l'espace disque: maintenez l'ordre dans l'ordre $$$2n$ hachage par rapport à $$$log (n)$ hachages pour les nœuds compacts, où n est la puissance de l'ensemble UTXO.

Architecture de réseau

Les ponts permettent d'ajouter progressivement des nœuds compacts au réseau sans changer le logiciel des nœuds existants. Les nœuds complets fonctionnent comme auparavant, répartissant les transactions et les blocs entre eux. Les nœuds de pont sont des nœuds complets qui stockent en outre des données de batterie Utreexo et un ensemble de preuves d'inclusion pour tous les UTXO pour le moment. Le nœud de pont ne se présente pas comme tel, prétendant être un nœud complet pour tous les nœuds complets et un nœud compact pour tous les nœuds compacts. Bien que les ponts relient les deux réseaux ensemble, en réalité, ils doivent être connectés dans une seule direction: des nœuds complets existants aux nœuds compacts. Cela est possible car le format de transaction n'a pas besoin d'être modifié et les preuves pour UTXO pour les nœuds compacts peuvent être rejetées, de sorte que tout nœud compact peut envoyer des transactions à tous les participants du réseau de la même manière sans la participation des nœuds de pont.

Conclusion

Nous avons examiné la batterie Utreexo et mis en œuvre son prototype à Rust. Nous avons examiné l'architecture du réseau, qui intégrera les nœuds basés sur la batterie. L'avantage de la capture compacte est la taille des données stockées, qui dépend logarithmiquement de la puissance de nombreux UTXO, ce qui réduit considérablement les besoins en espace disque et les performances de stockage pour ces nœuds. L'inconvénient est un trafic de nœuds supplémentaire pour le transfert de preuves, mais les techniques d'agrégation de preuves (lorsqu'une preuve prouve l'existence de plusieurs éléments) et la mise en cache peuvent aider à maintenir le trafic dans des limites acceptables.

Références :

• Utreexo Rust Prototype GitHub
• Thaddeus Dryja - Utreexo: un accumulateur dynamique basé sur le hachage optimisé pour l'ensemble Bitcoin UTXO
• Oeuvre animée d'un article