Utreexo: Komprimierung vieler UTXO-Bitcoin

Hey Habr!

Im Bitcoin-Netzwerk einigen sich alle Knoten im Konsens auf eine Reihe von UTXOs: Wie viele Münzen stehen zum Ausgeben zur Verfügung, für wen genau und unter welchen Bedingungen. Der UTXO-Satz ist der für einen Validierungsknoten erforderliche Mindestdatensatz, ohne den der Knoten nicht in der Lage ist, die Gültigkeit eingehender Transaktionen und der sie enthaltenden Blöcke zu überprüfen.

In diesem Zusammenhang wird auf jede erdenkliche Weise versucht, die gespeicherte Darstellung dieser Menge zu reduzieren und zu komprimieren, ohne die Sicherheitsgarantien zu verlieren. Je kleiner das Volumen der gespeicherten Daten ist, desto geringer ist der Speicherplatzbedarf des Validator-Knotens. Dadurch ist der Start eines Validator-Knotens kostengünstiger, Sie können das Netzwerk erweitern und dadurch die Stabilität des Netzwerks erhöhen.

In diesem Beitrag werden wir einen Rust-Prototyp eines aktuellen Vorschlags eines Co-Autors veröffentlichen Lightning Network-Papier, Thaddeus Dryja - Utreexo: ein dynamischer Hash-basierter Akkumulator, der für den Bitcoin UTXO-Satz optimiert ist, was eine Reduzierung des Speicherplatzbedarfs für Validatorknoten ermöglicht.

Was ist das Problem?

Eines der ständigen Probleme von Bitcoin ist seine Skalierbarkeit. Die Idee der „eigenen Bank“ verlangt von den Netzwerkteilnehmern, Aufzeichnungen über alle zur Verwendung verfügbaren Gelder zu führen. In Bitcoin werden die verfügbaren Mittel als eine Menge nicht ausgegebener Ausgaben ausgedrückt – ein UTXO-Set. Obwohl dies keine besonders intuitive Darstellung ist, ist sie im Hinblick auf die Implementierungsleistung vorteilhaft gegenüber einer Darstellung, bei der jede „Brieftasche“ über ein „Guthaben“ als separaten Eintrag verfügt und außerdem Privatsphäre bietet (z. B. CoinJoin).

Es ist wichtig, zwischen der Historie der Transaktionen (der sogenannten Blockchain) und dem aktuellen Zustand des Systems zu unterscheiden. Der Bitcoin-Transaktionsverlauf belegt derzeit etwa 200 GB Speicherplatz und wächst weiter. Allerdings ist der Systemstatus viel kleiner, in der Größenordnung von 4 GB, und berücksichtigt nur die Tatsache, dass jemand aktuell Coins besitzt. Auch die Menge dieser Daten nimmt im Laufe der Zeit zu, jedoch deutlich langsamer und nimmt manchmal sogar tendenziell ab (siehe CDPV).

Light Clients (SPVs) tauschen Sicherheitsgarantien gegen die Möglichkeit, außer privaten Schlüsseln keinen Mindeststatus (UTXO-Set) zu speichern.

UTXO und UTXO-Set

UTXO (Unspent Transaction Output) ist der nicht ausgegebene Transaktionsoutput, der Endpunkt der Reise jedes in Transaktionen übertragenen Satoshi. Nicht ausgegebene Ausgaben werden zu Eingaben neuer Transaktionen und werden somit ausgegeben (ausgegeben) und aus dem UTXO-Set entfernt.

Neue UTXOs werden immer durch Transaktionen erstellt:

• Coinbase-Transaktionen ohne Eingaben: Erstellen Sie neue UTXOs, wenn Miner Münzen ausgeben
• Regelmäßige Transaktionen: Erstellen Sie neue UTXOs und geben Sie gleichzeitig einen bestimmten Satz vorhandener UTXOs aus

Prozess der Arbeit mit UTXO:

Wallets zählen die Anzahl der zum Ausgeben verfügbaren Münzen (Saldo) basierend auf der Menge an UTXO, die diesem Wallet zum Ausgeben zur Verfügung steht.

Um doppelte Ausgabeversuche zu verhindern, muss jeder Validierungsknoten den Satz überwachen alle UTXO beim Überprüfen jeder Transaktionen jeder Block.

Der Knoten muss über Logik verfügen:

• Ergänzungen zum UTXO-Set
• Löschungen aus dem UTXO-Satz
• Überprüfen des Vorhandenseins eines einzelnen UTXO in einem Satz

Es gibt Möglichkeiten, die Anforderungen an gespeicherte Informationen zu einer Menge zu reduzieren und gleichzeitig die Möglichkeit beizubehalten, Elemente hinzuzufügen und zu entfernen sowie die Existenz eines Elements in einer Menge zu überprüfen und zu beweisen kryptografische Akkumulatoren.

Batterien für UTXO

Die Idee, Batterien zum Speichern mehrerer UTXOs zu verwenden diskutiert früher.

Der UTXO-Satz wird im laufenden Betrieb während des anfänglichen Block-Downloads (IBD) erstellt und vollständig und dauerhaft gespeichert, während sich sein Inhalt nach der Verarbeitung von Transaktionen aus jedem neuen und korrekten Block des Netzwerks ändert. Dieser Prozess erfordert das Herunterladen von etwa 200 GB Blockdaten und die Überprüfung von Hunderten Millionen digitalen Signaturen. Nach Abschluss des IBD-Prozesses wird der UTXO-Satz unter dem Strich etwa 4 GB belegen.

Bei Akkumulatoren reduzieren sich die Konsensregeln für Gelder jedoch auf die Überprüfung und Erstellung kryptografischer Beweise, und die Last der Nachverfolgung verfügbarer Gelder wird auf den Eigentümer dieser Gelder verlagert, der deren Existenz und Eigentum nachweisen kann.

Ein Akkumulator kann als kompakte Darstellung einer Menge bezeichnet werden. Die Größe der gespeicherten Darstellung muss entweder konstant sein oder beispielsweise sublinear in Bezug auf die Kardinalität der Menge und die Größe des Elements selbst ansteigen , wobei n die Kardinalität der gespeicherten Menge ist.

In diesem Fall sollte der Akkumulator die Erstellung eines Beweises für die Aufnahme eines Elements in die Menge (Einschlussbeweis) ermöglichen und es ermöglichen, diesen Beweis effektiv zu überprüfen.

Die Batterie heißt dynamisch Mit if können Sie Elemente hinzufügen und Elemente aus einer Menge entfernen.

Ein Beispiel für eine solche Batterie wäre RSA-Akkumulator vorgeschlagen von Boneh, Bunz, Fisch im Dezember 2018. Ein solcher Akkumulator hat eine konstante Größe der gespeicherten Darstellung, erfordert jedoch dessen Anwesenheit geteiltes Geheimnis (vertrauenswürdiges Setup). Diese Anforderung macht die Anwendbarkeit eines solchen Akkumulators für vertrauenswürdige Netzwerke wie Bitcoin zunichte, da Datenlecks während der Geheimgenerierung es Angreifern ermöglichen können, falsche Beweise für die Existenz eines UTXO zu erstellen und Knoten mit einem UTXO-Satz, der auf einem solchen Akkumulator basiert, zu täuschen.

Utreexo

Das von Thaddeus Dryja vorgeschlagene Utreexo-Design ermöglicht die Gestaltung dynamisch Akkumulator без vertrauenswürdiges Setup.

Utreexo ist ein Wald aus perfekter Binärdatei Merkle-Bäume und ist eine Weiterentwicklung der in vorgestellten Ideen Effiziente asynchrone Akkumulatoren für verteilte PKI, wodurch die Möglichkeit hinzugefügt wird, Elemente aus einer Menge zu entfernen.

Logische Struktur der Batterie

Die Batteriezellen sind in einem Wald aus idealen Binärbäumen angeordnet. Bäume werden nach Höhe sortiert. Diese Darstellung wurde als die anschaulichste gewählt und ermöglicht es Ihnen, die Verschmelzung von Bäumen während des Betriebs an der Batterie zu visualisieren.

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

Somit ist die gespeicherte Darstellung des Utreexo-Akkumulators eine Liste von Wurzelknoten (Merkle-Wurzel). und nicht der ganze Wald aus Bäumen.

Stellen wir die Liste der Stammelemente als dar Vec<Option<Hash>>. Optionaler Typ Option<Hash> zeigt an, dass das Wurzelelement möglicherweise fehlt, was bedeutet, dass sich im Akkumulator kein Baum mit der entsprechenden Höhe befindet.

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

Beschreiben wir zunächst die Funktion parent(), das den übergeordneten Knoten für zwei gegebene Elemente erkennt.

parent()-Funktion

Da wir Merkle-Bäume verwenden, ist der übergeordnete Knoten jedes der beiden Knoten ein Knoten, der den Hash der Verkettung der Hashes der untergeordneten Knoten speichert:

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

Der Autor weist darauf hin, dass zur Verhinderung der von Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir und Sebastien Zimmer beschriebenen Angriffe
Zweite Preimage-Angriffe auf geditherte Hash-FunktionenZusätzlich zu den beiden Hashes sollte auch die Höhe innerhalb des Baums zur Verkettung hinzugefügt werden.

Wenn Sie dem Akkumulator Elemente hinzufügen, müssen Sie im Auge behalten, welche Stammelemente geändert werden. Indem 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.

Verfolgen Sie Änderungen, während Sie sie hinzufügen

Um die vorgenommenen Änderungen zu verfolgen, deklarieren wir die Struktur Update, das Daten über Knotenänderungen speichert.

#[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 Wurzelelementen new_roots und platzieren Sie dort die vorhandenen Stammelemente, eines für jeden Bucket:

Code

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

• Hängen Sie die hinzuzufügenden Elemente an (array insertions) zum ersten Warenkorb new_roots[0]:

Code

new_roots[0].extend_from_slice(insertions);

• Fügen Sie die zum ersten Warenkorb hinzugefügten Artikel mit dem Rest zusammen:
  • Für alle Warenkörbe mit mehr als einem Artikel:
    1. Nehmen Sie zwei Elemente vom Ende des Korbs, berechnen Sie deren übergeordnete Elemente und entfernen Sie beide Elemente
    2. Fügen Sie das berechnete übergeordnete Element dem nächsten Warenkorb hinzu

Code

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 Stammelemente aus Bins in das resultierende Akkumulator-Array

Code

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 eines Beweises für hinzugefügte Elemente

Nachweis über den Einbau der Zelle in die Batterie (Proof) dient als Merkle-Pfad, bestehend aus einer Kette 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,
}

Verwenden der zuvor beim Hinzufügen eines Elements (Struktur) erhaltenen Informationen Update) können Sie den Nachweis erbringen, dass der Batterie ein Element hinzugefügt wurde. Dazu gehen wir die Tabelle der vorgenommenen Änderungen durch und fügen jeden Schritt zu Merkles Weg hinzu, der anschließend als Beweis dient:

Code

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

Prozess der Erstellung eines Beweises

Überprüfung des Beweises für ein Element

Die Überprüfung des Inklusionsnachweises eines Elements läuft darauf hinaus, dem Merkle-Pfad zu folgen, bis er zu einem 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:

Prozess der Beweisprüfung für A

Elemente entfernen

Um eine Zelle aus einer Batterie zu entfernen, müssen Sie einen gültigen Nachweis erbringen, dass die Zelle vorhanden ist. Anhand der Daten aus dem Beweis ist es möglich, neue Wurzelelemente des Akkumulators zu berechnen, für die der gegebene Beweis nicht mehr zutrifft.

Der Algorithmus ist der folgende:

1. Wie bei der Addition organisieren wir eine Reihe leerer Körbe, die Merkle-Bäumen entsprechen, deren Höhe der Zweierpotenz des Korbindex entspricht
2. Wir fügen Elemente aus den Stufen des Merkle-Pfades in die Körbe ein; Der Korbindex entspricht der Nummer des aktuellen Schritts
3. Wir entfernen das Wurzelelement, zu dem der Weg aus dem Beweis führt
4. Wie beim Addieren berechnen wir neue Wurzelelemente, indem wir Elemente aus Körben paarweise kombinieren und das Ergebnis der Vereinigung in den nächsten Korb verschieben

Code

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

Mithilfe des vorgeschlagenen Akkumulators können Knoten die Verwendung einer Datenbank zum Speichern aller UTXOs vermeiden und gleichzeitig den UTXO-Satz ändern können. Es stellt sich jedoch das Problem der Arbeit mit Beweisen.

Rufen wir den Validatorknoten auf, der den UTXO-Akkumulator verwendet kompakt (Kompaktzustandsknoten) und der Validator ohne Akkumulator fertig (vollständiger Knoten). Das Vorhandensein zweier Knotenklassen stellt ein Problem für deren Integration in ein einzelnes Netzwerk dar, da kompakte Knoten den Nachweis der Existenz von UTXOs erfordern, die in Transaktionen ausgegeben werden, während dies bei vollständigen Knoten nicht der Fall ist. Wenn nicht alle Netzwerkknoten gleichzeitig und koordiniert auf die Verwendung von Utreexo umsteigen, bleiben kompakte Knoten zurück und können nicht im Bitcoin-Netzwerk operieren.

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 Bridge-Knoten ist ein vollständiger Knoten, der auch die Utreexo-Batterie speichert und für den Einschaltschutz sorgt alle UTXO aus dem UTXO-Set. Bridges berechnen neue Hashes und aktualisieren den Akkumulator und die Beweise, wenn neue Transaktionsblöcke eintreffen. Die Pflege und Aktualisierung des Akkumulators und der Beweise stellt für solche Knoten keine zusätzliche Rechenlast dar. Brücken opfern Speicherplatz: Sie müssen für Ordnung sorgen Hashes im Vergleich zu Hashes für kompakte Knoten, wobei n die Potenz des UTXO-Sets ist.

Netzwerkarchitektur

Bridges ermöglichen es, dem Netzwerk schrittweise kompakte Knoten hinzuzufügen, ohne die Software bestehender Knoten zu ändern. Vollständige Knoten funktionieren 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 speichern alle UTXO vorerst. Der Brückenknoten bewirbt sich nicht als solcher 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 Brücken beide Netzwerke miteinander verbinden, müssen sie sie eigentlich nur in einer Richtung verbinden: von bestehenden Vollknoten zu kompakten Knoten. Dies ist möglich, weil das Transaktionsformat nicht geändert werden muss und UTXO-Proofs für kompakte Knoten verworfen werden können, sodass jeder kompakte Knoten Transaktionen auf ähnliche Weise an alle Netzwerkteilnehmer senden kann, ohne dass Bridge-Knoten beteiligt sind.

Abschluss

Wir haben uns die Utreexo-Batterie angesehen und ihren Prototyp in Rust implementiert. Wir haben uns die Netzwerkarchitektur angesehen, die die Integration batteriebasierter Knoten ermöglicht. Der Vorteil kompakter Catches ist die Größe der gespeicherten Daten, die logarithmisch von der Leistung des Satzes von UTXOs abhängt, was den Bedarf an Speicherplatz und Speicherleistung für solche Knoten erheblich reduziert. Der Nachteil ist der zusätzliche Knotenverkehr für die Übertragung von Beweisen, aber Techniken zur Beweisaggregation (wenn ein Beweis die Existenz mehrerer Elemente beweist) und Caching können dabei helfen, den Verkehr innerhalb akzeptabler Grenzen zu halten.

Referenzen:

• GitHub des Utreexo-Prototyps in Rust
• Thaddeus Dryja - Utreexo: ein dynamischer Hash-basierter Akkumulator, der für den Bitcoin UTXO-Satz optimiert ist
• Animierte Illustrationen aus dem Artikel

Source: habr.com