Utreexo: viel UTXO Bitcoin komprimieren

Hallo Habr!

Im Bitcoin-Netzwerk sind sich alle Knoten einig über die vielen UTXOs: Wie viele Münzen stehen für wen und unter welchen Bedingungen zur Verfügung? Der Satz von UTXOs ist der Mindestdatensatz, der für einen Validierungsknoten erforderlich ist, ohne den der Knoten die Gültigkeit eingehender Transaktionen und der sie enthaltenden Blöcke nicht überprüfen kann.

In dieser Hinsicht wird in jeder Hinsicht versucht, die gespeicherte Darstellung dieses Satzes zu reduzieren und ohne Verlust von Sicherheitsgarantien zu komprimieren. Je kleiner das gespeicherte Datenvolumen ist, desto geringer sind die Anforderungen an den Speicherplatz des Validierungsknotens, wodurch das Starten des Validatorknotens kostengünstig wird. Dadurch können Sie das Netzwerk erweitern und dadurch die Netzwerkstabilität erhöhen.

In diesem Hinweis werden wir den Rust-Prototyp eines aktuellen Vorschlags des Co-Autors von Lightning Network Paper , Thaddeus Dryja - Utreexo, behandeln: einen dynamischen Hash-basierten Akkumulator, der für das Bitcoin UTXO-Set optimiert wurde und den Speicherplatzbedarf für Validatorknoten reduziert.

Was ist das Problem?

Eines der ewigen Probleme von Bitcoin war seine Skalierbarkeit. Die Idee, eine Bank zu besitzen, erfordert, dass die Netzwerkteilnehmer alle verfügbaren Mittel zur Verwendung im Auge behalten. In Bitcoin werden verfügbare Mittel als eine Reihe nicht ausgegebener Ausgaben ausgedrückt - UTXO-Menge. Obwohl dies keine sehr intuitive Ansicht ist, ist sie im Hinblick auf die Implementierungsleistung vorteilhaft im Vergleich zu einer Ansicht, in der jede Brieftasche ein „Guthaben“ als separaten Eintrag hat und außerdem Datenschutz bietet (z. B. bietet CoinJoin Arbeit).

Es ist wichtig, zwischen einem Transaktionsverlauf (einer sogenannten Blockchain) und dem aktuellen Status des Systems zu unterscheiden. Die Transaktionshistorie von Bitcoin belegt derzeit etwa 200 GB Festplattenspeicher und wächst weiter. Der Status des Systems ist jedoch viel kleiner, etwa 4 GB, und berücksichtigt nur die Tatsache, dass derzeit jemand Münzen besitzt. Das Volumen dieser Daten nimmt ebenfalls mit der Zeit zu, jedoch mit einer viel geringeren Rate und nimmt manchmal sogar tendenziell ab (siehe KDPV).

Light Clients (SPVs) tauschen Sicherheitsgarantien für die Fähigkeit aus, keinen Mindeststatus (UTXO-Set) außer privaten Schlüsseln zu speichern.

UTXO und UTXO-Set

UTXO (Unspent Transaction Output) - Nicht ausgegebene Transaktionsausgabe, der Endpunkt der Reise jedes in Transaktionen übertragenen Satoshi. Nicht ausgegebene Ausgaben werden zu Eingaben für neue Transaktionen und werden gleichzeitig ausgegeben und aus dem UTXO-Set entfernt.

Neue UTXOs werden immer durch Transaktionen erstellt:

• Coinbase-Transaktionen ohne Eingaben: Erstellen Sie neue UTXOs während der Ausgabe von Münzen durch Bergleute
• Konventionelle Transaktionen: Erstellen Sie neue UTXOs, während Sie einige vorhandene UTXOs ausgeben

Der Prozess der Arbeit mit UTXO:

Brieftaschen berücksichtigen die Anzahl der für Ausgaben verfügbaren Münzen (Saldo) basierend auf der Menge an UTXO, die für diese Brieftasche für Ausgaben verfügbar ist.

Jeder Validierungsknoten muss die Erfassung aller UTXOs während der Überprüfung jeder Transaktion jedes Blocks verfolgen, um doppelte Ausgabenversuche zu verhindern.

Der Knoten muss logisch sein:

• Ergänzungen zum UTXO-Set
• UTXO-Set-Löschungen
• Überprüft, ob ein einzelnes UTXO im Set vorhanden ist

Es gibt Möglichkeiten, die Anforderungen an gespeicherte Informationen über das Set zu reduzieren und gleichzeitig die Möglichkeit beizubehalten, Elemente hinzuzufügen und zu entfernen sowie die Existenz eines Elements im Set mithilfe kryptografischer Batterien zu überprüfen und nachzuweisen.

Batterien für UTXO

Die Idee, Batterien zum Speichern vieler UTXOs zu verwenden, wurde bereits zuvor erörtert .

UTXO-set wird im laufenden Betrieb erstellt, während das anfängliche Laden der Blockkette (IBD, anfänglicher Blockdownload) vollständig und konstant gespeichert wird, während sich sein Inhalt nach der Verarbeitung von Transaktionen aus jedem neuen und korrekten Netzwerkblock ändert. Für diesen Vorgang müssen ca. 200 GB Datenblöcke heruntergeladen und Hunderte Millionen digitaler Signaturen überprüft werden. Nach Abschluss des IBD-Prozesses nimmt das UTXO-Set im trockenen Rückstand ca. 4 GB ein.

Bei der Verwendung von Batterien besteht die Konsensregel in Bezug auf Fonds jedoch darin, kryptografische Beweise zu überprüfen und zu generieren, und die Last der Verfolgung verfügbarer Fonds liegt auf den Schultern des Eigentümers dieser Fonds, was den Nachweis ihrer Anwesenheit und ihres Eigentums erbringt.

Die Batterie kann als kompakte Darstellung des Sets bezeichnet werden. Die Größe der gespeicherten Ansicht muss in diesem Fall entweder konstant sein $$$O (1)$oder beispielsweise sublinear relativ zur Potenz der Menge und Größe des Elements selbst erhöhen $$$O (log (n))$Dabei ist n die Potenz der gespeicherten Menge.

In diesem Fall sollte der Akkumulator die Erstellung von Nachweisen für die Aufnahme eines Elements in die Menge (Einschlussnachweis) ermöglichen und es ihm ermöglichen, diesen Nachweis effektiv zu überprüfen.

Eine Batterie wird als dynamisch bezeichnet, wenn Sie damit Elemente hinzufügen und Elemente aus dem Set entfernen können.

Ein Beispiel für eine solche Batterie ist die von Boneh, Bunz, Fisch im Dezember 2018 vorgeschlagene RSA-Batterie . Eine solche Batterie hat eine konstante Größe der gespeicherten Ansicht, erfordert jedoch ein gemeinsames Geheimnis (vertrauenswürdiges Setup). Diese Anforderung negiert die Anwendbarkeit eines solchen Akkumulators für vertrauenswürdige Netzwerke wie Bitcoin, da Datenlecks während der Generierung eines Geheimnisses es Angreifern ermöglichen können, gefälschte Beweise für die Existenz von UTXO zu erstellen, indem sie Knoten mit einem UTXO-Satz fälschen, der auf einem solchen Akkumulator basiert.

Utreexo

Mit dem von Utreexo vorgeschlagenen Thaddeus Dryja-Design können Sie eine dynamische Batterie ohne vertrauenswürdige Einrichtung erstellen.

Utreexo ist ein Wald idealer binärer Merkle-Bäume und eine Weiterentwicklung der Ideen, die in Effiziente asynchrone Akkumulatoren für verteilte pki vorgestellt werden , und bietet die Möglichkeit, Elemente aus der Menge zu entfernen.

Die logische Struktur der Batterie

Batteriezellen sind in einem Wald perfekter Binärbäume angeordnet. Bäume sind nach Höhe geordnet. Diese Präsentation wurde als die visuellste ausgewählt und ermöglicht es Ihnen, das Zusammenführen von Bäumen während des Betriebs mit der Batterie zu visualisieren.

Der Autor stellt fest, dass, da alle Bäume im Wald perfekt sind, ihre Höhe durch die Zweierpotenz ausgedrückt wird, genau wie jede natürliche Zahl als Summe der Zweierpotenzen dargestellt werden kann. Dementsprechend kann jeder Satz von Blättern in Form von Binärbäumen gruppiert werden, und in allen Fällen erfordert das Hinzufügen eines neuen Elements nur Kenntnisse über die Wurzelknoten der gespeicherten Bäume .

Die gespeicherte Ansicht der Utreexo-Batterie ist also eine Liste von Wurzelknoten (Merkle-Wurzel) und nicht der gesamte Wald von Bäumen .

Stellen Sie sich die Liste der Stammelemente als Vec<Option<Hash>> . Der optionale Option<Hash> weist darauf hin, dass das Stammelement möglicherweise fehlt. Dies bedeutet, dass der Baum keinen Baum mit einer angemessenen Höhe hat.

 /// 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], } } } 

Elemente hinzufügen

Zunächst beschreiben wir die Funktion parent() , die den übergeordneten Knoten für zwei bestimmte Elemente erkennt.

 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[..]) } 

Wenn Sie der Batterie Elemente hinzufügen, müssen Sie nachverfolgen, welche Stammelemente geändert werden. Wenn Sie dem Pfad zum Ändern der Stammelemente für jedes hinzugefügte Element folgen, können Sie später einen Beweis für das Vorhandensein dieser Elemente erstellen.

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

Um der Batterie ein Element hinzuzufügen, benötigen Sie:

• Erstellen Sie ein Array von Körben mit new_roots und platzieren Sie die vorhandenen new_roots dort, eines für jeden Korb:

 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); } 

• Fügen Sie die hinzugefügten Elemente ( insertions ) zum ersten Warenkorb hinzu new_roots[0] :

 new_roots[0].extend_from_slice(insertions); 

• Führen Sie das "Zusammenführen" von Artikeln durch, die dem ersten Warenkorb hinzugefügt wurden, mit dem Rest:
  
  • Für alle Körbe mit mehr als einem Artikel:
    
    1. Wir nehmen zwei Elemente vom Ende des Warenkorbs, berechnen ihre übergeordneten Elemente und löschen beide Elemente
    2. Fügen Sie das berechnete übergeordnete Element zum nächsten Warenkorb hinzu.

 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 }); } } 

• Verschieben Sie Wurzelelemente aus Körben in das resultierende Batteriearray

 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]); } } 

Erstellen von Beweisen für hinzugefügte Elemente

Der Nachweis der Aufnahme des Elements in die Batterie ( Proof ) dient als Pfad von Merkle (Merkle Path), der aus einer Kette von ProofStep . Wenn der Weg nirgendwohin führt, ist der Beweis falsch.

 ///         . #[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, } 

Mithilfe der Informationen, die Sie zuvor beim Hinzufügen des Elements erhalten haben (Struktur Update ), können Sie den Nachweis erbringen, dass das Element zur Batterie hinzugefügt wurde. Dazu gehen wir die Tabelle der vorgenommenen Änderungen durch und fügen jeden Schritt dem Pfad von Merkle hinzu, der anschließend als Beweis dienen wird:

 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 } } 

Beweis für einen Gegenstand

Das Überprüfen des Beweises für die Aufnahme eines Elements (Einschlussbeweis) reduziert sich darauf, dem Pfad von Merkle zu folgen, bis es zum vorhandenen Wurzelelement führt:

 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 } } 

Klar:

Elemente löschen

Um ein Element aus der Batterie zu entfernen, müssen Sie einen gültigen Nachweis erbringen, dass das Element vorhanden ist. Mit den Daten aus dem Proof können wir die neuen Wurzelelemente der Batterie berechnen, für die dieser Proof nicht mehr gültig ist.

Der Algorithmus ist wie folgt:

1. Wie bei der Hinzufügung organisieren wir eine Reihe leerer Körbe, die Merkle-Bäumen entsprechen und deren Höhe zwei des Korbindex entspricht
2. Legen Sie Gegenstände von den Stufen des Merkle-Pfades in die Körbe. Der Warenkorbindex entspricht der aktuellen Schrittnummer
3. Wir entfernen das Wurzelelement, zu dem der Pfad vom Beweis führt.
4. Wie bei der Addition berechnen wir die neuen Wurzelelemente, kombinieren die Elemente aus den Körben paarweise und verschieben das Ergebnis der Vereinigung in den nächsten Korb

 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; } } 

Der Vorgang zum Entfernen von Element "A":

Integration in ein bestehendes Netzwerk

Mit der vorgeschlagenen Batterie können Knoten die Verwendung der Datenbank zum Speichern aller UTXO verweigern, während die Möglichkeit erhalten bleibt, den UTXO-Satz zu ändern. Es besteht jedoch das Problem, mit Beweisen zu arbeiten.

Wir werden einen Validator-Knoten nennen, der den UTXO-Batteriekompakt (Compact-State-Knoten) verwendet, und einen Validator ohne Batterie - voll (Vollknoten). Die Existenz von zwei Knotenklassen führt zu dem Problem, sie in ein einziges Netzwerk zu integrieren, da kompakte Knoten den Nachweis der Existenz von UTXO erfordern, das für Transaktionen verwendet wird, vollständige Knoten jedoch nicht. Wenn nicht alle Knoten des Netzwerks gleichzeitig und auf koordinierte Weise zu Utreexo wechseln, bleiben die kompakten Knoten zurück und können nicht im Bitcoin-Netzwerk arbeiten.

Um das Problem der Integration kompakter Knoten in das Netzwerk zu lösen, wird vorgeschlagen, eine zusätzliche Klasse von Knoten einzuführen - Brücken . Ein Brückenknoten ist ein vollständiger Knoten, der unter anderem die Utreexo-Batterie und Einschlussnachweise für alle UTXOs aus dem UTXO-Set speichert. Bridges berechnen neue Hashes und aktualisieren die Batterie und Beweise, wenn neue Blöcke mit Transaktionen eintreffen. Die Unterstützung und Aktualisierung der Batterie und der Nachweise bedeutet für solche Knoten keine zusätzliche Rechenlast. Bridges opfern Speicherplatz: Ordnung in Ordnung halten $$$2n$Hashes im Vergleich zu $$$log (n)$Hashes für kompakte Knoten, wobei n die Potenz der Menge UTXO ist.

Netzwerkarchitektur

Bridges ermöglichen das schrittweise Hinzufügen kompakter Knoten zum Netzwerk, ohne die Software vorhandener Knoten zu ändern. Vollständige Knoten arbeiten wie zuvor und verteilen Transaktionen und Blöcke untereinander. Bridge-Knoten sind vollständige Knoten, die zusätzlich Utreexo-Batteriedaten und eine Reihe von Einschlussnachweisen für alle UTXOs speichern. Der Brückenknoten kündigt sich nicht als solcher an und gibt vor, ein vollständiger Knoten für alle vollständigen Knoten und ein kompakter Knoten für alle kompakten Knoten zu sein. Obwohl Bridges beide Netzwerke miteinander verbinden, müssen sie in der Realität nur in eine Richtung verbunden werden: von vorhandenen vollständigen Knoten zu kompakten Knoten. Dies ist möglich, da das Transaktionsformat nicht geändert werden muss und der Nachweis für UTXO für kompakte Knoten verworfen werden kann, sodass jeder kompakte Knoten Transaktionen auf die gleiche Weise an alle Netzwerkteilnehmer senden kann, ohne dass Brückenknoten beteiligt sind.

Fazit

Wir haben die Utreexo-Batterie überprüft und ihren Prototyp in Rust implementiert. Wir haben die Netzwerkarchitektur untersucht, die die Knoten basierend auf der Batterie integriert. Der Vorteil von Compact Catch ist die Größe der gespeicherten Daten, die logarithmisch von der Leistung vieler UTXOs abhängt, wodurch der Speicherplatzbedarf und die Speicherleistung für solche Knoten erheblich reduziert werden. Der Nachteil ist zusätzlicher Knotenverkehr für die Beweisübertragung, aber Beweisaggregationstechniken (wenn ein Beweis das Vorhandensein mehrerer Elemente beweist) und Caching können dazu beitragen, den Verkehr innerhalb akzeptabler Grenzen zu halten.

Referenzen :

• Utreexo Rust Prototyp GitHub
• Thaddeus Dryja - Utreexo: Ein dynamischer Hash-basierter Akkumulator, der für das Bitcoin UTXO-Set optimiert wurde
• Animierte Grafik aus einem Artikel