Utreexo: vill UTXO Bitcoin kompriméieren

Hey Habr!

Am Bitcoin Netz sinn all Noden, duerch Konsens, averstanen iwwer eng Rei vun UTXOs: wéivill Mënzen sinn verfügbar fir Ausgaben, wiem genee, a wéi eng Konditiounen. Den UTXO Set ass de Minimum Satz vun Daten, déi fir e Validator Node erfuerderlech sinn, ouni deen den Node net fäeg ass d'Gëltegkeet vun erakommen Transaktiounen an de Blocken ze verifizéieren, déi se enthalen.

An dëser Hisiicht gëtt op all méiglech Manéier probéiert d'gespäichert Representatioun vun dësem Set ze reduzéieren, fir se ze kompriméieren ouni Sécherheetsgarantien ze verléieren. Wat de Volume vun de gespäicherten Donnéeën méi kleng ass, dest méi niddereg sinn d'Disk Space Ufuerderunge vum Validator Node, wat de Start vun engem Validator Node bëlleg mécht, erlaabt Iech d'Netzwierk auszebauen an doduerch d'Stabilitéit vum Netz ze erhéijen.

An dësem Post wäerte mir e Rust Prototyp vun enger rezenter Propositioun vun engem Co-Autor posten Lightning Network Pabeier, Thaddeus Dryja - Utreexo: en dynameschen Hash-baséiert Akkumulator optiméiert fir de Bitcoin UTXO Set, wat d'Reduktioun vun Disk Space Ufuerderunge fir Validatornoden erlaabt.

Wat ass de Problem?

Ee vun de méijähreg Probleemer vu Bitcoin ass seng Skalierbarkeet. D'Iddi vun "Är eege Bank" erfuerdert Reseau Participanten Rekorder vun all Fongen sinn fir benotzen ze halen. A Bitcoin ginn verfügbare Fongen ausgedréckt als e Set vun net verbrauchten Ausgänge - en UTXO-Set. Och wann dëst net eng besonnesch intuitiv Representatioun ass, ass et gutt wat d'Implementéierungsleeschtung ugeet iwwer eng Representatioun an där all "Portemonnaie" e "Gläichgewiicht" als separat Entrée huet, an och Privatsphär bäidréit (z. CoinJoin).

Et ass wichteg ze ënnerscheeden tëscht der Geschicht vun Transaktiounen (wat Blockchain genannt gëtt) an dem aktuellen Zoustand vum System. Bitcoin Transaktiounsgeschicht besetzt de Moment ongeféier 200 GB Disk Space, a wiisst weider. Wéi och ëmmer, de Systemstaat ass vill méi kleng, op der Uerdnung vu 4 GB, a berücksichtegt nëmmen d'Tatsaach datt een de Moment Mënzen besëtzt. De Volume vun dësen Donnéeën erhéicht och mat der Zäit, awer mat engem vill méi luesen Taux an heiansdo souguer éischter erof (kuckt CDPV).

Liicht Clienten (SPVs) Handel Sécherheet Garantien fir d'Fähegkeet kee Minimum Staat ze Buttek (UTXO-Set) aner wéi privat Schlësselen.

UTXO an UTXO-Set

UTXO (Unspent Transaction Output) ass den unspent Transaction Output, den Ennpunkt vun der Rees vun all Satoshi, deen an Transaktiounen transferéiert gëtt. Onverbraucht Ausgänge ginn Input vun neien Transaktiounen a ginn domat ausginn (ausginn) an aus dem UTXO-Set geläscht.

Nei UTXOs ginn ëmmer duerch Transaktiounen erstallt:

• Coinbase Transaktiounen ouni Input: erstellt nei UTXOs wann Miner Mënzen erausginn
• regelméisseg Transaktiounen: erstellt nei UTXOs wärend Dir e bestëmmte Set vu bestehend UTXOs verbréngt

Prozess fir mat UTXO ze schaffen:

Portemonnaie zielen d'Zuel vun de Mënzen déi verfügbar sinn fir Ausgaben (Gläichgewiicht) baséiert op der Unzuel vun UTXO verfügbar fir dëse Portemonnaie fir Ausgaben.

All Validator Node, fir duebel Ausgabeversuch ze vermeiden, muss de Set iwwerwaachen всех UTXO beim Iwwerpréiwen jeeweils Transaktiounen vun all eenzel blockéieren.

Den Node muss Logik hunn:

• Ergänzunge fir UTXO-Set
• Läschen aus UTXO-Set
• Iwwerpréift d'Präsenz vun engem eenzegen UTXO an engem Set

Et gi Weeër fir d'Ufuerderunge fir gespäichert Informatioun iwwer e Set ze reduzéieren, wärend d'Fäegkeet erhale fir Elementer ze addéieren an ze läschen, d'Existenz vun engem Element an engem Set z'iwwerpréiwen an ze beweisen kryptografesch Akkumulatoren.

Batterien fir UTXO

D'Iddi fir Batterien ze benotzen fir verschidde UTXOs ze späicheren diskutéiert gouf virdrun.

Den UTXO-Set gëtt op der Flucht gebaut, während dem initialen Block Download (IBD), voll a permanent gespäichert, wärend säin Inhalt no der Veraarbechtung vun Transaktioune vun all neien a korrekten Block vum Netz ännert. Dëse Prozess erfuerdert ongeféier 200 GB Blockdaten erofzelueden an Honnerte vu Millioune digital Ënnerschrëften z'iwwerpréiwen. Nodeems den IBD Prozess ofgeschloss ass, ass déi ënnescht Linn datt den UTXO-Set ongeféier 4 GB besetzt.

Wéi och ëmmer, mat Akkumulatoren, ginn d'Regele vum Konsens fir Fongen reduzéiert op d'Verifizéierung an d'Generatioun vu kryptographesche Beweiser, an d'Belaaschtung fir verfügbare Fongen ze verfolgen gëtt op de Besëtzer vun dëse Fongen geréckelt, deen de Beweis vun hirer Existenz a Besëtzer gëtt.

En Akkumulator kann eng kompakt Representatioun vun engem Set genannt ginn. D'Gréisst vun der gespäichert Representatioun muss entweder konstant sinn , oder sublinear eropgoen mat Bezuch op d'Kardinalitéit vum Set an d'Gréisst vum Element selwer, zum Beispill , wou n d'Kardinalitéit vum gespäicherten Set ass.

An dësem Fall soll den Akkumulator erlaben e Beweis fir d'Inklusioun vun engem Element am Set ze generéieren (Inklusiounsbeweis) an et méiglech ze maachen dës Beweis effektiv z'iwwerpréiwen.

D'Batterie gëtt genannt dynamesch wann erlaabt Iech Elementer ze addéieren an Elementer aus engem Set ze läschen.

E Beispill vun esou enger Batterie wier RSA Akkumulator proposéiert vum Boneh, Bunz, Fisch am Dezember 2018. Sou en Akkumulator huet eng konstant Gréisst vu gespäichert Representatioun, awer erfuerdert d'Präsenz gedeelt Geheimnis (vertrauenswürdege Setup). Dës Fuerderung negéiert d'Uwendbarkeet vun esou engem Akkumulator fir vertrauenslos Netzwierker wéi Bitcoin, well Datelekage während der geheimer Generatioun kann Ugräifer erlaben falsche Beweis vun der Existenz vun engem UTXO ze kreéieren, täuschend Noden mat engem UTXO-Set baséiert op sou engem Akkumulator.

Utreexo

Den Utreexo Design proposéiert vum Thaddeus Dryja mécht et méiglech ze kreéieren dynamesch Akkulator ouni trauen-Setup.

Utreexo ass e Bësch vu perfekt Binär Merkle Trees an ass eng Entwécklung vun den Iddien presentéiert an Effikass asynchronous Akkuen fir verdeelt pki, dobäi d'Fähegkeet Elementer aus engem Set ze läschen.

Batterie logesch Struktur

D'Batteriezellen sinn an engem Bësch vun ideale binäre Beem arrangéiert. Beem ginn no Héicht bestallt. Dës Representatioun gouf als déi visuellst gewielt an erlaabt Iech d'Fusioun vu Beem während Operatiounen op der Batterie ze visualiséieren.

Den Auteur stellt fest, datt well all d'Beem am Bësch ideal sinn, hir Héicht als Kraaft vun zwee ausgedréckt gëtt, sou wéi all natierlech Zuel kann als Zomm vun zwee Muechten duergestallt ginn. Deementspriechend kann all Set vu Blieder a binäre Beem gruppéiert ginn, an an alle Fäll erfuerdert en neit Element derbäi Wëssen. nëmmen iwwer d'Wurzelnoden vu gespäichert Beem.

Also ass déi gespäichert Representatioun vum Utreexo Akkumulator eng Lëscht vu Rootknäppchen (Merkle Root), an net de ganze Bësch vu Beem.

Loosst d'Lëscht vun root Elementer vertrieden als Vec<Option<Hash>>. Fakultativ Typ Option<Hash> weist datt d'Wurzelelement fehlt, dat heescht datt et kee Bam mat der entspriechender Héicht am Akkumulator ass.

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

Elementer dobäizemaachen

Als éischt, loosst eis d'Funktioun beschreiwen parent(), déi den Elterendeel Node fir zwee gegebene Elementer erkennt.

Elterendeel () Funktioun

Well mir Merkle Beem benotzen, ass den Elterendeel vun all eenzel vun den zwee Noden een Node deen den Hash vun der Konkatenatioun vun den Hashes vun de Kannernoden späichert:

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

Den Auteur stellt fest, datt fir d'Attacke vum Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir a Sébastien Zimmer ze verhënneren.
Zweet Preimage Attacken op dithered Hashfunktiounen, Nieft deenen zwee Haschen, soll d'Héicht am Bam och un d'Verbindung bäigefüügt ginn.

Wéi Dir Elementer op den Akkumulator bäidréit, musst Dir verfollegen wéi eng Root Elementer geännert ginn. Andeems Dir de Wee verfollegt fir d'Wurzelelementer fir all Element z'änneren, deen Dir bäidréit, kënnt Dir spéider e Beweis vun der Präsenz vun dësen Elementer konstruéieren.

Verfollegt Ännerungen wéi Dir se derbäigesat

Fir d'Ännerungen ze verfolgen, loosst eis d'Struktur deklaréieren Update, déi Daten iwwer Node Ännerungen späicheren.

#[derive(Debug)]
pub struct Update<'a> {
    pub utreexo: &'a mut Utreexo,
    // ProofStep хранит "соседа" элемента и его положение
    pub updated: HashMap<Hash, ProofStep>,
}

Fir en Element an d'Batterie ze addéieren, braucht Dir:

• Erstellt eng Rei vu Kuerf vu Rootelementer new_roots a plazéiert déi existent Root Elementer do, een fir all Eemer:

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

• Fügt d'Elementer un déi bäigefüügt ginn (Array insertions) an den éischte Weenchen new_roots[0]:

Code

new_roots[0].extend_from_slice(insertions);

• Coalescéieren d'Elementer, déi an den éischte Kuerf bäigefüügt ginn, mam Rescht:
  • Fir all Weenchen mat méi wéi engem Artikel:
    1. Huelt zwee Elementer vum Enn vum Kuerf, berechent hiren Elterendeel, läscht béid Elementer
    2. Füügt de berechent Elterendeel op den nächste Weenchen

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

• Beweegt Root Elementer vu Binsen op déi resultéierend Akkumulatorarray

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

Schafen e Beweis fir dobäi Elementer

Beweis vun der Inklusioun vun der Zell an der Batterie (Proof) wäert als Merkle Path déngen, besteet aus enger Kette ProofStep. Wann de Wee néierens féiert, dann ass de 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,
}

Benotzt d'Informatioun, déi virdru kritt gouf wann Dir en Element (Struktur Update), kënnt Dir Beweis erstellen datt en Element an d'Batterie bäigefüügt gouf. Fir dëst ze maachen, gi mir duerch d'Tabell vun den Ännerungen gemaach an fügen all Schrëtt op de Wee vum Merkle, deen duerno als Beweis déngt:

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 vun engem Beweis schafen

Iwwerpréift de Beweis fir en Element

D'Inklusiounsbeweis vun engem Element iwwerpréiwen kacht erof op de Merkle Wee ze verfollegen bis et zu engem existente Rootelement féiert:

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

Visuell:

Prozess fir de Beweis fir A

Ewechzehuelen Elementer

Fir eng Zell aus enger Batterie ze läschen, musst Dir valabel Beweiser ubidden datt d'Zell do ass. Mat Hëllef vun den Donnéeën vum Beweis ass et méiglech nei Rootelementer vum Akkumulator ze berechnen, fir déi de gegebene Beweis net méi stëmmt.

Den Algorithmus ass wéi follegt:

1. Wéi mat Zousatz organiséieren mir eng Rei vun eidel Kuerf entspriechend Merkle Beem mat enger Héicht gläich wéi d'Muecht vun zwee aus dem Kuerf Index
2. Mir setzen Elementer aus de Schrëtt vum Merkle Wee an d'Kuerf; de Kuerfindex ass gläich wéi d'Zuel vum aktuelle Schrëtt
3. Mir entfernen de Rootelement, op deen de Wee vum Beweis féiert
4. Wéi mat der Zousatz, berechnen mir nei Rootelementer andeems Elementer aus Kuerf a Pairen kombinéiert ginn an d'Resultat vun der Unioun an den nächste Kuerf réckelen

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

De Prozess fir Element "A" ze läschen:

Integratioun an engem bestehend Reseau

Mat dem proposéierte Akkumulator kënnen Node vermeiden eng DB ze benotzen fir all UTXOs ze späicheren, wärend se ëmmer nach fäeg sinn den UTXO-Set z'änneren. Allerdéngs entsteet de Problem mat Beweiser ze schaffen.

Loosst eis de Validator Node nennen deen den UTXO Akkumulator benotzt kompakt (kompakt-Staat Node), an de Validator ouni Akkumulator ass komplett (voll Node). D'Existenz vun zwou Klassen vun Wirbelen schaaft e Problem fir se an engem eenzegen Netz z'integréieren, well kompakt Wirbelen Beweis vun der Existenz vun UTXOs erfuerderen, déi an Transaktiounen ausginn, während voll Wirbelen net. Wann all Netzknäppchen net gläichzäiteg an op eng koordinéiert Manéier op Utreexo wiesselen, da ginn kompakt Wirbelen hannerlooss a kënnen net am Bitcoin Netz operéieren.

Fir de Problem vun der Integratioun vun kompakten Wirbelen am Netz ze léisen, gëtt proposéiert eng zousätzlech Klasse vu Wirbelen aféieren - Brécken. E Bréck Node ass e komplette Node deen och d'Utreexo Batterie a Power-on Beweis späichert всех UTXO vum UTXO-Set. Brécke berechnen nei Hashes an aktualiséieren den Akkumulator a Beweiser wéi nei Blocks vun Transaktiounen ukommen. D'Erhalen an d'Aktualiséierung vum Akkumulator a Beweiser setzt keng zousätzlech Berechnungslaascht op sou Noden. Brécke opferen Disk Space: brauche Saachen organiséiert ze halen hashes, Verglach mat Hashes fir kompakt Wirbelen, wou n d'Kraaft vum UTXO-Set ass.

Netzwierkarchitektur

Brécke maachen et méiglech, lues a lues kompakt Wirbelen am Netz ze addéieren ouni d'Software vun existente Wirbelen z'änneren. Voll Node funktionnéieren wéi virdrun, verdeelen Transaktiounen a Blocken ënner sech. Bréck Wirbelen sinn voll Wirbelen datt zousätzlech Buttek Utreexo Batterie Daten an eng Rei vun Inklusioun Beweiser fir всех UTXO fir elo. D'Bréck Node Reklamm selwer net als solch, mécht wéi e voll Node fir all voll Node an engem kompakt Node fir all kompakt. Och wann d'Brécke béid Netzwierker matenee verbannen, brauche se se eigentlech nëmmen an eng Richtung ze verbannen: vun existéierende vollen Wirbelen op kompakt Wirbelen. Dëst ass méiglech well d'Transaktiounsformat net geännert muss ginn, an UTXO Beweiser fir kompakt Wirbelen kënne verworf ginn, sou datt all kompakt Node ähnlech Transaktiounen un all Netzwierk Participanten ouni d'Participatioun vu Bréckknäppchen kann iwwerdroen.

Konklusioun

Mir hunn d'Utreexo Batterie gekuckt an hire Prototyp am Rust ëmgesat. Mir hunn d'Netzarchitektur gekuckt, déi d'Integratioun vu Batterie-baséiert Noden erlaabt. De Virdeel vu kompakten Fanger ass d'Gréisst vun de gespäicherten Donnéeën, déi logarithmesch vun der Kraaft vum Set vun UTXOs hänkt, wat d'Ufuerderunge fir Disk Space a Speicherleistung fir sou Noden staark reduzéiert. Den Nodeel ass den zousätzleche Knuetverkéier fir Beweiser ze vermëttelen, awer Beweisaggregatiounstechniken (wann ee Beweis d'Existenz vu verschiddenen Elementer beweist) a Cache kënnen hëllefen, de Verkéier bannent akzeptablen Grenzen ze halen.

Referenze:

• GitHub vum Utreexo Prototyp am Rust
• Thaddeus Dryja - Utreexo: en dynameschen Hash-baséiert Akkumulator optiméiert fir de Bitcoin UTXO Set
• Animéiert Illustratiounen aus dem Artikel

Source: will.com