Utreexo: comprimarea multor Bitcoin UTXO

Hei Habr!

În rețeaua Bitcoin, toate nodurile, prin consens, convin asupra unui set de UTXO: câte monede sunt disponibile pentru cheltuială, cui exact și în ce condiții. Setul UTXO este setul minim de date necesare unui nod validator, fără de care nodul nu va putea verifica validitatea tranzacțiilor primite și a blocurilor care le conțin.

În acest sens, se încearcă în toate modurile posibile reducerea reprezentării stocate a acestui set, comprimarea acestuia fără a pierde garanțiile de securitate. Cu cât volumul datelor stocate este mai mic, cu atât sunt mai mici cerințele de spațiu pe disc ale nodului validator, ceea ce face ca lansarea unui nod validator să fie ieftină, vă permite să extindeți rețeaua și, prin urmare, să creșteți stabilitatea rețelei.

În această postare vom posta un prototip Rust al unei propuneri recente a unui coautor Lucrarea de rețea Lightning, Thaddeus Dryja - Utreexo: un acumulator dinamic bazat pe hash optimizat pentru setul Bitcoin UTXO, care permite reducerea cerințelor de spațiu pe disc pentru nodurile validatoare.

Care este problema?

Una dintre problemele perene ale Bitcoin a fost scalabilitatea acestuia. Ideea „propriei bănci” cere participanților la rețea să țină evidența tuturor fondurilor disponibile pentru utilizare. În Bitcoin, fondurile disponibile sunt exprimate ca un set de rezultate necheltuite - un set UTXO. Deși aceasta nu este o reprezentare deosebit de intuitivă, este benefică în ceea ce privește performanța implementării față de o reprezentare în care fiecare „portofel” are un „balanț” ca intrare separată și, de asemenea, adaugă confidențialitate (de ex. CoinJoin).

Este important să se facă distincția între istoricul tranzacțiilor (ceea ce se numește blockchain) și starea actuală a sistemului. Istoricul tranzacțiilor Bitcoin ocupă în prezent aproximativ 200 GB spațiu pe disc și continuă să crească. Cu toate acestea, starea sistemului este mult mai mică, de ordinul a 4 GB, și ține cont doar de faptul că cineva deține în prezent monede. Volumul acestor date crește, de asemenea, în timp, dar într-un ritm mult mai lent și uneori chiar tinde să scadă (vezi CDPV).

Garanții de securitate comercială pentru clienții ușoare (SPV) pentru capacitatea de a nu stoca nicio stare minimă (set UTXO), în afară de cheile private.

UTXO și UTXO-set

UTXO (Ieșirea tranzacției necheltuite) este rezultatul tranzacției necheltuite, punctul final al călătoriei fiecărui Satoshi transferat în tranzacții. Ieșirile necheltuite devin intrări ale unor noi tranzacții și sunt astfel cheltuite (cheltuite) și eliminate din setul UTXO.

Noile UTXO sunt întotdeauna create de tranzacții:

• Tranzacții coinbase fără intrări: creați noi UTXO atunci când minerii emit monede
• tranzacții obișnuite: creați noi UTXO în timp ce cheltuiți un anumit set de UTXO existente

Procesul de lucru cu UTXO:

Portofelele contorizează numărul de monede disponibile pentru cheltuire (sold) în funcție de cantitatea de UTXO disponibilă pentru acest portofel pentru cheltuieli.

Fiecare nod validator, pentru a preveni încercările de dublare a cheltuielilor, trebuie să monitorizeze setul toate UTXO la verificare fiecare tranzacții fiecare bloc.

Nodul trebuie să aibă logică:

• Adăugări la UTXO-set
• Ștergeri din UTXO-set
• Verificarea prezenței unui singur UTXO într-un set

Există modalități de a reduce cerințele pentru informațiile stocate despre un set, menținând în același timp capacitatea de a adăuga și elimina elemente, de a verifica și de a dovedi existența unui element într-un set folosind acumulatori criptografici.

Baterii pentru UTXO

Ideea de a folosi baterii pentru a stoca mai multe UTXO discutat mai devreme.

Setul UTXO este construit din mers, în timpul descărcării inițiale a blocului (IBD), stocat integral și permanent, în timp ce conținutul acestuia se modifică după procesarea tranzacțiilor din fiecare bloc nou și corect al rețelei. Acest proces necesită descărcarea a aproximativ 200 GB de date bloc și verificarea a sute de milioane de semnături digitale. După finalizarea procesului IBD, concluzia este că setul UTXO va ocupa aproximativ 4 GB.

Cu toate acestea, în cazul acumulatorilor, regulile consensului pentru fonduri sunt reduse la verificarea și generarea dovezilor criptografice, iar sarcina urmăririi fondurilor disponibile este transferată către proprietarul acelor fonduri, care oferă dovada existenței și a deținerii acestora.

Un acumulator poate fi numit o reprezentare compactă a unei mulțimi. Mărimea reprezentării stocate trebuie să fie fie constantă , sau crește subliniar în raport cu cardinalitatea mulțimii și dimensiunea elementului în sine, de exemplu , unde n este cardinalitatea mulțimii stocate.

În acest caz, acumulatorul ar trebui să permită generarea unei dovezi a includerii unui element în set (dovada includerii) și să facă posibilă verificarea efectivă a acestei dovezi.

Se numește bateria dinamic dacă vă permite să adăugați elemente și să eliminați elemente dintr-un set.

Un exemplu de astfel de baterie ar fi Acumulator RSA propus de Boneh, Bunz, Fisch în decembrie 2018. Un astfel de acumulator are o dimensiune constantă a reprezentării stocate, dar necesită prezența secret împărtășit (configurare de încredere). Această cerință anulează aplicabilitatea unui astfel de acumulator pentru rețelele fără încredere precum Bitcoin, deoarece scurgerea de date în timpul generării secrete poate permite atacatorilor să creeze dovezi false ale existenței unui UTXO, înșelând nodurile cu un set UTXO bazat pe un astfel de acumulator.

Utreexo

Designul Utreexo propus de Thaddeus Dryja face posibilă crearea dinamic acumulator fără configurație de încredere.

Utreexo este o pădure de binar perfect Merkle Trees și este o dezvoltare a ideilor prezentate în Acumulatoare asincrone eficiente pentru pki distribuite, adăugând posibilitatea de a elimina elemente dintr-un set.

Structura logică a bateriei

Celulele bateriei sunt aranjate într-o pădure de arbori binari ideali. Copacii sunt ordonați după înălțime. Această reprezentare a fost aleasă ca fiind cea mai vizuală și vă permite să vizualizați îmbinarea copacilor în timpul operațiunilor pe baterie.

Autorul notează că, întrucât toți copacii din pădure sunt ideali, înălțimea lor este exprimată ca o putere a doi, la fel cum orice număr natural poate fi reprezentat ca o sumă a puterilor a doi. În consecință, orice set de frunze poate fi grupat în arbori binari și, în toate cazurile, adăugarea unui nou element necesită cunoștințe. numai despre nodurile rădăcină ale arborilor stocați.

Astfel, reprezentarea stocată a acumulatorului Utreexo este o listă de noduri rădăcină (rădăcină Merkle), și nu întreaga pădure de copaci.

Să reprezentăm lista de elemente rădăcină ca Vec<Option<Hash>>. Tip optional Option<Hash> indică faptul că elementul rădăcină poate lipsi, ceea ce înseamnă că nu există niciun copac cu înălțimea adecvată în acumulator.

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

Adăugarea de elemente

Mai întâi, să descriem funcția parent(), care recunoaște nodul părinte pentru două elemente date.

funcția parent().

Deoarece folosim arbori Merkle, părintele fiecăruia dintre cele două noduri este un nod care stochează hash-ul concatenării hash-urilor nodurilor copil:

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

Autorul notează că pentru a preveni atacurile descrise de Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir și Sebastien Zimmer în
Al doilea atac de preimagine asupra funcțiilor hash ditherate, pe lângă cele două hașuri, la concatenare ar trebui adăugată și înălțimea din interiorul arborelui.

Pe măsură ce adăugați elemente la acumulator, trebuie să urmăriți ce elemente rădăcină sunt modificate. Urmând calea modificării elementelor rădăcină pentru fiecare element pe care îl adăugați, puteți construi ulterior o dovadă a prezenței acestor elemente.

Urmăriți modificările pe măsură ce le adăugați

Pentru a urmări modificările efectuate, să declarăm structura Update, care va stoca date despre modificările nodurilor.

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

Pentru a adăuga un element la baterie, aveți nevoie de:

• Creați o serie de coșuri de elemente rădăcină new_roots și plasați acolo elementele rădăcină existente, câte unul pentru fiecare găleată:

Cod

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

• Adăugați elementele de adăugat (matrice insertions) la primul cărucior new_roots[0]:

Cod

new_roots[0].extend_from_slice(insertions);

• Combinați articolele adăugate la primul coș cu restul:
  • Pentru toate cărucioarele cu mai mult de un articol:
    1. Luați două elemente de la capătul coșului, calculați-le părintele, eliminați ambele elemente
    2. Adăugați părintele calculat la următorul coș

Cod

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

• Mutați elementele rădăcină din coșuri în matricea acumulatoare rezultată

Cod

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

Crearea unei dovezi pentru elementele adăugate

Dovada includerii celulei în baterie (Proof) va servi drept Calea Merkle, constând dintr-un lanț ProofStep. Dacă calea nu duce nicăieri, atunci dovada este incorectă.

/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}

Utilizarea informațiilor obținute mai devreme la adăugarea unui element (structură Update), puteți crea dovada că un element a fost adăugat la baterie. Pentru a face acest lucru, parcurgem tabelul cu modificările efectuate și adăugăm fiecare pas în calea lui Merkle, care ulterior va servi drept dovadă:

Cod

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

Procesul de creare a unei dovezi

Verificarea dovezii pentru un element

Verificarea dovezii de includere a unui element se rezumă la a urma calea Merkle până când duce la un element rădăcină existent:

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

Clar:

Procesul de verificare a dovezii pentru A

Eliminarea articolelor

Pentru a scoate o celulă dintr-o baterie, trebuie să furnizați dovezi valide că celula este acolo. Folosind datele din demonstrație, este posibil să se calculeze noi elemente rădăcină ale acumulatorului pentru care demonstrația dată nu va mai fi adevărată.

Algoritmul este după cum urmează:

1. Ca și în plus, organizăm un set de coșuri goale corespunzătoare arborilor Merkle cu o înălțime egală cu puterea lui doi din indicele coșului
2. Introducem elemente din treptele potecii Merkle în coșuri; indicele coșului este egal cu numărul pasului curent
3. Îndepărtăm elementul rădăcină la care duce calea de la dovadă
4. Ca și în cazul adăugării, calculăm noi elemente rădăcină combinând elementele din coșuri în perechi și mutând rezultatul unirii la următorul coș

Cod

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

Procesul de eliminare a elementului „A”:

Integrare într-o rețea existentă

Folosind acumulatorul propus, nodurile pot evita utilizarea unei baze de date pentru a stoca toate UTXO-urile, putând în același timp să schimbe setul UTXO. Totuși, se pune problema lucrului cu dovezi.

Să numim nodul validator care folosește acumulatorul UTXO compact (nodul de stare compactă), iar validatorul fără acumulator este complet (nodul complet). Existența a două clase de noduri creează o problemă pentru integrarea lor într-o singură rețea, deoarece nodurile compacte necesită dovada existenței UTXO-urilor, care sunt cheltuite în tranzacții, în timp ce nodurile complete nu. Dacă toate nodurile de rețea nu trec simultan și într-un mod coordonat la utilizarea Utreexo, atunci nodurile compacte vor rămâne în urmă și nu vor putea funcționa în rețeaua Bitcoin.

Pentru a rezolva problema integrării nodurilor compacte în rețea, se propune introducerea unei clase suplimentare de noduri - poduri. Un nod bridge este un nod complet care stochează și bateria Utreexo și dovada de pornire pentru toate UTXO de la UTXO-set. Bridges calculează noi hashuri și actualizează acumulatorul și dovezile pe măsură ce sosesc noi blocuri de tranzacții. Menținerea și actualizarea acumulatorului și a dovezilor nu impune încărcare de calcul suplimentară asupra unor astfel de noduri. Podurile sacrifică spațiul pe disc: trebuie să menținem lucrurile organizate hashes, comparativ cu hashuri pentru noduri compacte, unde n este puterea setului UTXO.

Arhitectura rețelei

Podurile fac posibilă adăugarea treptată a nodurilor compacte în rețea fără a schimba software-ul nodurilor existente. Nodurile complete funcționează ca înainte, distribuind tranzacțiile și blocurile între ele. Nodurile bridge sunt noduri complete care stochează suplimentar datele bateriei Utreexo și un set de dovezi de includere pentru toate UTXO pentru moment. Nodul punte nu se face reclamă ca atare, pretinzând că este un nod plin pentru toate nodurile pline și un nod compact pentru toate cele compacte. Deși punțile conectează ambele rețele împreună, ele trebuie de fapt să le conecteze într-o singură direcție: de la noduri complete existente la noduri compacte. Acest lucru este posibil deoarece formatul tranzacției nu trebuie schimbat, iar dovezile UTXO pentru nodurile compacte pot fi eliminate, astfel încât orice nod compact poate transmite tranzacții în mod similar tuturor participanților la rețea fără participarea nodurilor bridge.

Concluzie

Ne-am uitat la bateria Utreexo și i-am implementat prototipul în Rust. Ne-am uitat la arhitectura de rețea care va permite integrarea nodurilor bazate pe baterie. Avantajul capturilor compacte este dimensiunea datelor stocate, care depinde logaritmic de puterea setului de UTXO, ceea ce reduce foarte mult cerințele de spațiu pe disc și performanța de stocare pentru astfel de noduri. Dezavantajul este traficul suplimentar de noduri pentru transmiterea dovezilor, dar tehnicile de agregare a dovezilor (când o dovadă dovedește existența mai multor elemente) și stocarea în cache pot ajuta la menținerea traficului în limite acceptabile.

referințe:

• Prototipul GitHub al Utreexo în Rust
• Thaddeus Dryja - Utreexo: un acumulator dinamic bazat pe hash optimizat pentru setul Bitcoin UTXO
• Ilustrații animate din articol

Sursa: www.habr.com