Utreexo: komprimiranje mnogih UTXO Bitcoina

Hej Habr!

U Bitcoin mreži, svi čvorovi se konsenzusom slažu oko skupa UTXO: koliko kovanica je dostupno za potrošnju, kome tačno i pod kojim uslovima. UTXO skup je minimalni skup podataka potrebnih za čvor validatora, bez kojeg čvor neće moći provjeriti valjanost dolaznih transakcija i blokova koji ih sadrže.

S tim u vezi, pokušavaju se na sve moguće načine smanjiti pohranjena reprezentacija ovog skupa, komprimirati bez gubljenja sigurnosnih garancija. Što je manji volumen pohranjenih podataka, manji su zahtjevi za prostorom na disku kod čvora validatora, što čini pokretanje validatorskog čvora jeftinim, omogućava vam da proširite mrežu i time povećate stabilnost mreže.

U ovom postu ćemo objaviti Rust prototip nedavnog prijedloga koautora Lightning Network Paper, Thaddeus Dryja - Utreexo: dinamički akumulator baziran na hash optimiziran za Bitcoin UTXO set, što omogućava smanjenje zahtjeva za prostorom na disku za čvorove validatora.

V čëm problema?

Jedan od stalnih problema Bitcoina je njegova skalabilnost. Ideja “svoje banke” zahtijeva od učesnika mreže da vode evidenciju o svim sredstvima dostupnim za korištenje. U Bitcoin-u, raspoloživa sredstva su izražena kao skup nepotrošenih izlaza - UTXO-set. Iako ovo nije posebno intuitivan prikaz, on je koristan u smislu izvedbe implementacije u odnosu na reprezentaciju u kojoj svaki "novčanik" ima "ravnotežu" kao zaseban unos, a također dodaje privatnost (npr. CoinJoin).

Važno je razlikovati istoriju transakcija (ono što se naziva blockchain) i trenutno stanje sistema. Istorija Bitcoin transakcija trenutno zauzima oko 200 GB prostora na disku i nastavlja da raste. Međutim, stanje sistema je mnogo manje, reda veličine 4 GB, i uzima u obzir samo činjenicu da neko trenutno posjeduje novčiće. Obim ovih podataka se takođe povećava tokom vremena, ali mnogo sporije i ponekad čak ima tendenciju da se smanji (vidi CDPV).

Laki klijenti (SPV) trguju sigurnosnim garancijama za mogućnost skladištenja minimalnog stanja (UTXO-set) osim privatnih ključeva.

UTXO i UTXO-set

UTXO (Unspent Transaction Output) je izlaz nepotrošene transakcije, krajnja tačka putovanja svakog Satoshija prenesenog u transakcijama. Nepotrošeni izlazi postaju ulazi novih transakcija i tako se troše (troše) i uklanjaju iz UTXO skupa.

Novi UTXO se uvijek kreiraju transakcijama:

• coinbase transakcije bez ulaza: kreirajte nove UTXO kada rudari izdaju novčiće
• redovne transakcije: kreirajte nove UTXO dok trošite određeni skup postojećih UTXO

Proces rada sa UTXO:

Novčanici broje broj kovanica dostupnih za potrošnju (bilans) na osnovu količine UTXO dostupnog ovom novčaniku za potrošnju.

Svaki čvor validatora, kako bi se spriječili pokušaji dvostrukog trošenja, mora pratiti skup всех UTXO prilikom provjere svaki transakcije svake od njih blok.

Čvor mora imati logiku:

• Dodaci UTXO-setu
• Brisanja iz UTXO skupa
• Provjera prisustva jednog UTXO u setu

Postoje načini da se smanje zahtjevi za pohranjenim informacijama o skupu, uz zadržavanje mogućnosti dodavanja i uklanjanja elemenata, provjere i dokazivanja postojanja elementa u skupu pomoću kriptografski akumulatori.

Baterije za UTXO

Ideja korištenja baterija za pohranjivanje više UTXO diskutovano ranije.

UTXO-set se gradi u hodu, tokom inicijalnog preuzimanja bloka (IBD), pohranjuje se u potpunosti i trajno, dok se njegov sadržaj mijenja nakon obrade transakcija iz svakog novog i ispravnog bloka mreže. Ovaj proces zahtijeva preuzimanje približno 200 GB blok podataka i provjeru stotina miliona digitalnih potpisa. Nakon što je IBD proces završen, suština je da će UTXO-set zauzimati oko 4 GB.

Međutim, kod akumulatora se pravila konsenzusa za sredstva svode na verifikaciju i generisanje kriptografskih dokaza, a teret praćenja raspoloživih sredstava prebacuje se na vlasnika tih sredstava, koji dokazuje njihovo postojanje i vlasništvo.

Akumulator se može nazvati kompaktnom predstavom skupa. Veličina pohranjene reprezentacije mora biti ili konstantna , ili povećati sublinearno u odnosu na kardinalnost skupa i veličinu samog elementa, na primjer , gdje je n kardinalnost pohranjenog skupa.

U ovom slučaju, akumulator treba da omogući generisanje dokaza o uključivanju elementa u skup (dokaz uključivanja) i da omogući efektivnu proveru ovog dokaza.

Baterija se zove dinamičan if vam omogućava dodavanje elemenata i uklanjanje elemenata iz skupa.

Primjer takve baterije bi bio RSA akumulator koji su predložili Boneh, Bunz, Fisch u decembru 2018. Takav akumulator ima konstantnu veličinu pohranjene reprezentacije, ali zahtijeva prisustvo zajednička tajna (pouzdano postavljanje). Ovaj zahtjev negira primjenjivost takvog akumulatora za mreže bez povjerenja kao što je Bitcoin, budući da curenje podataka tokom tajnog generiranja može omogućiti napadačima da stvore lažni dokaz postojanja UTXO, obmanjujući čvorove sa UTXO-setom zasnovanim na takvom akumulatoru.

Utreexo

Dizajn Utreexo koji je predložio Thaddeus Dryja omogućava stvaranje dinamičan akumulâtor bez pouzdano postavljanje.

Utreexo je šuma savršene binarnosti Merkle Trees i predstavlja razvoj ideja predstavljenih u Efikasni asinhroni akumulatori za distribuirane pki, dodajući mogućnost uklanjanja elemenata iz skupa.

Logička struktura baterije

Baterijske ćelije su raspoređene u šumi idealnih binarnih stabala. Stabla su poređana po visini. Ovaj prikaz je odabran kao najvizuelniji i omogućava vam da vizualizirate spajanje stabala tokom rada na bateriji.

Autor napominje da, budući da su sva stabla u šumi idealna, njihova visina se izražava kao stepen dvojke, kao što se svaki prirodni broj može predstaviti kao zbir potencija dva. U skladu s tim, bilo koji skup listova može se grupirati u binarna stabla, a u svim slučajevima dodavanje novog elementa zahtijeva znanje samo o korijenskim čvorovima pohranjenih stabala.

Dakle, pohranjeni prikaz akumulatora Utreexo je lista korijenskih čvorova (Merkle root), a ne cijela šuma drveća.

Predstavimo listu korijenskih elemenata kao Vec<Option<Hash>>. Opcioni tip Option<Hash> označava da možda nedostaje korijenski element, što znači da u akumulatoru ne postoji stablo odgovarajuće visine.

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

Dodavanje elemenata

Prvo, hajde da opišemo funkciju parent(), koji prepoznaje roditeljski čvor za dva data elementa.

funkcija parent().

Pošto koristimo Merkle stabla, roditelj svakog od dva čvora je jedan čvor koji pohranjuje hash konkatenacije hešova podređenih čvorova:

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

Autor napominje da bi se spriječili napadi koje su opisali Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir i Sebastien Zimmer u
Drugi napadi preimage na dithered hash funkcije, pored dva heša, u konkatenaciju treba dodati i visinu unutar stabla.

Dok dodajete elemente u akumulator, morate pratiti koji se korijenski elementi mijenjaju. Prateći put promjene korijenskih elemenata za svaki element koji dodate, kasnije možete konstruirati dokaz prisutnosti ovih elemenata.

Pratite promjene dok ih dodajete

Da bismo pratili napravljene promjene, deklarirajmo strukturu Update, koji će pohraniti podatke o promjenama čvora.

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

Da dodate element u bateriju, potrebno vam je:

• Kreirajte niz korpi korijenskih elemenata new_roots i postavite postojeće korijenske elemente tamo, po jedan za svaku kantu:

Kod

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

• Dodajte elemente za dodavanje (niz insertions) u prva kolica new_roots[0]:

Kod

new_roots[0].extend_from_slice(insertions);

• Spojite stavke dodane u prvu korpu sa ostatkom:
  • Za sva kolica sa više od jedne stavke:
    1. Uzmite dva elementa sa kraja korpe, izračunajte njihov roditelj, uklonite oba elementa
    2. Dodajte izračunatog roditelja u sljedeću košaricu

Kod

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

• Premjestite korijenske elemente iz binova u rezultirajući niz akumulatora

Kod

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

Kreiranje dokaza za dodatne elemente

Dokaz o uključivanju ćelije u bateriju (Proof) služiće kao Merkle staza, koja se sastoji od lanca ProofStep. Ako put ne vodi nikuda, onda je dokaz netačan.

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

Koristeći informacije dobivene ranije prilikom dodavanja elementa (strukture Update), možete stvoriti dokaz da je element dodat u bateriju. Da bismo to učinili, prolazimo kroz tabelu napravljenih promjena i dodajemo svaki korak Merkleovoj stazi, što će nam kasnije poslužiti kao dokaz:

Kod

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

Proces kreiranja dokaza

Provjera dokaza za element

Provjera dokaza uključivanja elementa svodi se na praćenje Merkle putanje sve dok ne dovede do postojećeg korijenskog elementa:

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

Vizuelno:

Proces provjere dokaza za A

Uklanjanje stavki

Da biste uklonili ćeliju iz baterije, morate pružiti valjan dokaz da je ćelija tamo. Koristeći podatke iz dokaza, moguće je izračunati nove korijenske elemente akumulatora za koje dati dokaz više neće biti istinit.

Algoritam je sljedeći:

1. Kao i sa sabiranjem, organiziramo skup praznih korpi koji odgovaraju Merkleovim stablima sa visinom jednakom stepenu dva iz indeksa korpe
2. U korpe ubacujemo elemente sa stepenica Merkle staze; indeks korpe je jednak broju trenutnog koraka
3. Uklanjamo osnovni element do kojeg vodi put od dokaza
4. Kao i kod zbrajanja, nove korijenske elemente izračunavamo kombiniranjem elemenata iz korpi u parovima i premještanjem rezultata sjedinjenja u sljedeću korpu

Kod

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

Proces uklanjanja elementa "A":

Integracija u postojeću mrežu

Koristeći predloženi akumulator, čvorovi mogu izbjeći korištenje DB-a za pohranjivanje svih UTXO-ova, a da i dalje mogu promijeniti UTXO-set. Međutim, javlja se problem rada sa dokazima.

Pozovimo čvor validatora koji koristi UTXO akumulator kompaktan (čvor kompaktnog stanja), a validator bez akumulatora je kompletan (puni čvor). Postojanje dvije klase čvorova stvara problem za njihovu integraciju u jednu mrežu, budući da kompaktni čvorovi zahtijevaju dokaz postojanja UTXO-a koji se troše u transakcijama, dok puni čvorovi ne. Ako svi mrežni čvorovi ne pređu istovremeno i na koordiniran način na korištenje Utreexo, tada će kompaktni čvorovi biti ostavljeni i neće moći raditi na Bitcoin mreži.

Da bi se riješio problem integracije kompaktnih čvorova u mrežu, predlaže se uvođenje dodatne klase čvorova - mostovi. Mostni čvor je kompletan čvor koji također pohranjuje Utreexo bateriju i dokaz za uključenje всех UTXO iz UTXO-seta. Mostovi izračunavaju nove hešove i ažuriraju akumulator i dokaze kako pristižu novi blokovi transakcija. Održavanje i ažuriranje akumulatora i dokaza ne nameće dodatno računarsko opterećenje takvim čvorovima. Mostovi žrtvuju prostor na disku: potrebno je da stvari budu organizovane hashova, u poređenju sa hashovi za kompaktne čvorove, gdje je n snaga UTXO skupa.

Mrežna arhitektura

Mostovi omogućavaju postepeno dodavanje kompaktnih čvorova u mrežu bez promjene softvera postojećih čvorova. Puni čvorovi rade kao i prije, distribuirajući transakcije i blokove među sobom. Mostovi čvorovi su puni čvorovi koji dodatno pohranjuju Utreexo podatke o bateriji i skup dokaza uključivanja za всех UTXO za sada. Mostni čvor se ne oglašava kao takav, pretvarajući se da je pun čvor za sve pune čvorove i kompaktni čvor za sve kompaktne. Iako mostovi povezuju obje mreže zajedno, oni ih zapravo trebaju povezati samo u jednom smjeru: od postojećih punih čvorova do kompaktnih čvorova. Ovo je moguće jer format transakcije nije potrebno mijenjati, a UTXO dokazi za kompaktne čvorove mogu se odbaciti, tako da svaki kompaktni čvor može na sličan način emitirati transakcije svim učesnicima mreže bez sudjelovanja čvorova za premošćivanje.

zaključak

Pogledali smo Utreexo bateriju i implementirali njen prototip u Rust. Pogledali smo mrežnu arhitekturu koja će omogućiti integraciju čvorova baziranih na bateriji. Prednost kompaktnog hvatanja je veličina pohranjenih podataka, koja logaritamski ovisi o snazi ​​skupa UTXO, što uvelike smanjuje zahtjeve za prostorom na disku i performansama skladištenja za takve čvorove. Nedostatak je dodatni promet čvora za prijenos dokaza, ali tehnike agregacije dokaza (kada jedan dokaz dokazuje postojanje više elemenata) i keširanje mogu pomoći da se promet zadrži u prihvatljivim granicama.

reference:

• GitHub prototipa Utreexo u Rustu
• Thaddeus Dryja - Utreexo: dinamički akumulator baziran na hash optimiziran za Bitcoin UTXO set
• Animirane ilustracije iz članka

izvor: www.habr.com