Utreexo: paljude UTXO Bitcoinide tihendamine

Tere Habr!

Bitcoini võrgus lepivad kõik sõlmed konsensuse teel kokku UTXO-de komplektis: kui palju münte on kulutamiseks saadaval, kellele täpselt ja mis tingimustel. UTXO komplekt on validaatori sõlme jaoks vajalik minimaalne andmekogum, ilma milleta ei saa sõlm kontrollida sissetulevate tehingute ja neid sisaldavate plokkide kehtivust.

Sellega seoses püütakse igal võimalikul viisil vähendada selle komplekti salvestatud esitust, tihendada seda ilma turvagarantiid kaotamata. Mida väiksem on salvestatud andmete maht, seda väiksem on validaatori sõlme kettaruumi vajadus, mis muudab validaatori sõlme käivitamise odavaks, võimaldab laiendada võrku ja seeläbi suurendada võrgu stabiilsust.

Selles postituses postitame kaasautori hiljutise ettepaneku Rusti prototüübi Lightning Network Paper, Thaddeus Dryja - Utreexo: dünaamiline räsipõhine aku, mis on optimeeritud Bitcoin UTXO komplekti jaoks, mis võimaldab vähendada validaatori sõlmede kettaruumivajadust.

Milles on probleem?

Bitcoini üheks püsivaks probleemiks on olnud selle mastaapsus. Idee "oma panga" eeldab, et võrgus osalejad peavad pidama arvestust kõigi kasutamiseks saadaolevate vahendite kohta. Bitcoinis väljendatakse saadaolevaid vahendeid kasutamata väljundite kogumina – UTXO-komplektina. Ehkki see ei ole eriti intuitiivne esitus, on see rakenduse jõudluse seisukohalt kasulik võrreldes esitusega, kus igal "rahakotil" on eraldi kirjena "saldo" ja see lisab ka privaatsust (nt. MüntJune).

Oluline on teha vahet tehingute ajalool (mida nimetatakse plokiahelaks) ja süsteemi hetkeseisu. Bitcoini tehingute ajalugu võtab praegu umbes 200 GB kettaruumi ja kasvab jätkuvalt. Süsteemi olek on aga palju väiksem, suurusjärgus 4 GB, ja võtab arvesse ainult seda, et keegi omab hetkel münte. Ka nende andmete maht suureneb aja jooksul, kuid palju aeglasemalt ja mõnikord kipub isegi vähenema (vt CDPV).

Kerged kliendid (SPV-d) kauplevad turvagarantiidega, et nad ei suuda salvestada muid minimaalseid olekuid (UTXO-komplekti) peale privaatvõtmete.

UTXO ja UTXO-komplekt

UTXO (kulutamata tehinguväljund) on kulutamata tehingute väljund, iga tehingutes ülekantud Satoshi teekonna lõpp-punkt. Kulutamata väljundid muutuvad uute tehingute sisenditeks ja seega kulutatakse (kulutatakse) ja eemaldatakse UTXO-komplektist.

Uued UTXO-d luuakse alati tehingutega:

• mündibaasi tehingud ilma sisenditeta: looge uusi UTXO-sid, kui kaevurid münte väljastavad
• regulaarsed tehingud: looge uusi UTXO-sid, kulutades samal ajal teatud olemasolevate UTXO-de komplekti

UTXO-ga töötamise protsess:

Rahakotid arvestavad kulutamiseks saadaolevate müntide arvu (saldo) selle rahakotti kulutamiseks saadaoleva UTXO hulga põhjal.

Topeltkulutamise vältimiseks peab iga valideerimissõlm komplekti jälgima Kõik UTXO kontrollimisel iga tehingud iga blokk.

Sõlmel peab olema loogika:

• Täiendused UTXO-komplektile
• Kustutused UTXO-komplektist
• Ühe UTXO olemasolu kontrollimine komplektis

On olemas viise, kuidas vähendada komplekti kohta salvestatud teabe nõudeid, säilitades samal ajal võimaluse lisada ja eemaldada elemente, kontrollida ja tõestada elemendi olemasolu komplektis, kasutades krüptoakud.

Akud UTXO jaoks

Idee kasutada patareisid mitme UTXO salvestamiseks arutati enne.

UTXO-komplekt ehitatakse käigu pealt, esialgse ploki allalaadimise (IBD) ajal, salvestatakse täielikult ja püsivalt, samas kui selle sisu muutub pärast iga uue ja õige võrguploki tehingute töötlemist. See protsess nõuab umbes 200 GB plokiandmete allalaadimist ja sadade miljonite digitaalallkirjade kontrollimist. Pärast IBD-protsessi lõppu on UTXO-komplekt umbes 4 GB.

Kuid akumulaatorite puhul taanduvad fondide konsensuse reeglid krüptograafiliste tõendite kontrollimisele ja genereerimisele ning vabade vahendite jälgimise koorem nihutatakse nende fondide omanikule, kes tõendab nende olemasolu ja omandiõigust.

Akut võib nimetada komplekti kompaktseks esituseks. Salvestatud esituse suurus peab olema konstantne või suureneb sublineaarselt komplekti kardinaalsuse ja elemendi enda suuruse suhtes, näiteks , kus n on salvestatud hulga kardinaalsus.

Sel juhul peaks akumulaator võimaldama luua tõendi elemendi komplekti kaasamise kohta (kaasamise tõend) ja võimaldama seda tõendit tõhusalt kontrollida.

Akut nimetatakse dünaamiline kui võimaldab teil komplekti elemente lisada ja elemente eemaldada.

Sellise aku näide oleks RSA aku, mille pakkus välja Boneh, Bunz, Fisch 2018. aasta detsembris. Sellisel akumulaatoril on salvestatud kujutise konstantne suurus, kuid see nõuab olemasolu jagatud saladus (usaldusväärne seadistus). See nõue välistab sellise akumulaatori rakendatavuse selliste usaldusväärsete võrkude jaoks nagu Bitcoin, kuna andmete lekkimine salajase genereerimise ajal võib lubada ründajatel luua valetõendeid UTXO olemasolu kohta, pettes sõlmesid sellisel akumulaatoril põhineva UTXO-komplektiga.

Utreexo

Thaddeus Dryja pakutud Utreexo disain võimaldab luua dünaamiline akumulaator ilma usaldusväärne seadistus.

Utreexo on täiusliku kahendsüsteemi mets Merkle puud ja see on aastal esitatud ideede edasiarendus Tõhusad asünkroonsed akud hajutatud pki jaoks, lisades võimaluse komplektist elemente eemaldada.

Aku loogiline struktuur

Akuelemendid on paigutatud ideaalsete kahendpuude metsa. Puud on järjestatud kõrguse järgi. See esitus valiti kõige visuaalsemaks ja võimaldab visualiseerida puude liitumist akuga töötamise ajal.

Autor märgib, et kuna kõik metsas olevad puud on ideaalsed, siis väljendatakse nende kõrgust kahe astmena, nii nagu iga naturaalarvu saab esitada kahe astmete summana. Sellest lähtuvalt saab iga lehtede komplekti rühmitada kahendpuudeks ja igal juhul nõuab uue elemendi lisamine teadmisi ainult ladustatud puude juuresõlmede kohta.

Seega on Utreexo akumulaatori salvestatud esitus juursõlmede loend (Merkle juur), ja mitte kogu puude mets.

Esitame juurelementide loendit kui Vec<Option<Hash>>. Valikuline tüüp Option<Hash> näitab, et juurelement võib puududa, mis tähendab, et akumulaatoris pole sobiva kõrgusega puud.

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

Elementide lisamine

Esiteks kirjeldame funktsiooni parent(), mis tunneb ära kahe antud elemendi vanemsõlme.

vanemate() funktsioon

Kuna me kasutame Merkle'i puid, on mõlema sõlme vanem üks sõlm, mis salvestab alamsõlmede räsiühendite räsi:

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 märgib, et Charles Bouillaguet', Pierre-Alain Fouque'i, Adi Shamiri ja Sebastien Zimmeri poolt aastal kirjeldatud rünnakute ärahoidmiseks.
Teine eelpildi rünnak räsifunktsioonide vastu, lisaks kahele räsile tuleks konkatenatsioonile lisada ka puu sees olev kõrgus.

Kui lisate akumulaatorisse elemente, peate jälgima, milliseid juurelemente muudetakse. Järgides iga lisatava elemendi juurelementide muutmise teed, saate hiljem koostada tõendi nende elementide olemasolu kohta.

Jälgige muudatusi nende lisamisel

Tehtud muudatuste jälgimiseks deklareerime struktuuri Update, mis salvestab andmed sõlme muudatuste kohta.

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

Akule elemendi lisamiseks vajate:

• Looge juurelementide korvide massiiv new_roots ja asetage sinna olemasolevad juurelemendid, üks iga ämbri jaoks:

Kood

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

• Lisage lisatavad elemendid (massiivi insertions) esimesse ostukorvi new_roots[0]:

Kood

new_roots[0].extend_from_slice(insertions);

• Ühendage esimesse korvi lisatud esemed ülejäänutega:
  • Kõigi rohkem kui ühe kaubaga kärude puhul:
    1. Võtke korvi otsast kaks elementi, arvutage nende vanem, eemaldage mõlemad elemendid
    2. Lisa arvutatud vanem järgmisse ostukorvi

Kood

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

• Teisaldage juurelemendid salvedest saadud akumulaatori massiivi

Kood

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

Lisatud elementide tõestuse loomine

Tõend elemendi lisamise kohta akusse (Proof) hakkab toimima Merkle Path, mis koosneb ketist ProofStep. Kui tee ei vii kuhugi, siis on tõestus vale.

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

Varem saadud teabe kasutamine elemendi (struktuuri) lisamisel Update), saate luua tõendi, et akule on lisatud element. Selleks vaatame läbi tehtud muudatuste tabeli ja lisame Merkle teele iga sammu, mis on hiljem tõestuseks:

Kood

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

Tõenduse loomise protsess

Elemendi tõestuse kontrollimine

Elemendi kaasamise tõendi kontrollimine taandub Merkle'i tee järgimisele, kuni see viib olemasoleva juurelemendini:

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

Visuaalselt:

A tõendi kontrollimise protsess

Üksuste eemaldamine

Patarei akust eemaldamiseks peate esitama kehtiva tõendi selle elemendi olemasolu kohta. Tõestusest saadud andmeid kasutades on võimalik arvutada akumulaatori uusi tüvielemente, mille puhul antud tõestus enam tõeseks ei pea.

Algoritm on järgmine:

1. Nagu lisaks, korraldame Merkle puudele vastavate tühjade korvide komplekti, mille kõrgus on võrdne korviindeksist kahe astmega
2. Korvidesse sisestame Merkle tee astmetelt elemente; korvi indeks võrdub jooksva sammu numbriga
3. Eemaldame juurelemendi, kuhu viib tõestuse tee
4. Sarnaselt lisamisega arvutame uued juurelemendid korvide elemendid paarikaupa kombineerides ja liitmise tulemuse järgmisse korvi liigutades

Kood

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

Elemendi "A" eemaldamise protsess:

Integreerimine olemasolevasse võrku

Pakutud akumulaatorit kasutades saavad sõlmed vältida DB kasutamist kõigi UTXO-de salvestamiseks, kuid siiski saavad UTXO-komplekti muuta. Tõenditega töötamise probleem tekib aga.

Kutsume UTXO akumulaatorit kasutavat validaatori sõlme kompaktne (kompaktse oleku sõlm) ja ilma akumulaatorita validaator on täielik (täissõlm). Kahe klassi sõlmede olemasolu tekitab probleeme nende integreerimisel ühte võrku, kuna kompaktsed sõlmed nõuavad UTXO-de olemasolu tõendamist, mida kulutatakse tehinguteks, täissõlmed aga mitte. Kui kõik võrgusõlmed ei lülitu korraga ja kooskõlastatult üle Utreexo kasutamisele, jäävad kompaktsed sõlmed maha ja ei saa Bitcoini võrgus töötada.

Kompaktsete sõlmede võrku integreerimise probleemi lahendamiseks tehakse ettepanek võtta kasutusele täiendav sõlmede klass - sillad. Sillasõlm on terviklik sõlm, mis salvestab ka Utreexo aku ja sisselülitamise tõendi Kõik UTXO UTXO-komplektist. Sillad arvutavad uusi räsi ja värskendavad akumulaatorit ja tõendeid, kui saabuvad uued tehinguplokid. Akumulaatori ja tõendite hooldamine ja uuendamine ei tekita sellistele sõlmedele täiendavat arvutuskoormust. Sillad ohverdavad kettaruumi: on vaja asju korraldada räsid, võrreldes räsid kompaktsete sõlmede jaoks, kus n on UTXO komplekti võimsus.

Võrgu arhitektuur

Sillad võimaldavad järk-järgult lisada võrku kompaktseid solme ilma olemasolevate sõlmede tarkvara muutmata. Täissõlmed töötavad nagu varem, jaotades tehingud ja plokid omavahel. Sildsõlmed on täissõlmed, mis salvestavad lisaks Utreexo akuandmeid ja komplekti kaasamise tõendeid Kõik UTXO praegu. Sildsõlm ei reklaami ennast sellisena, teeseldes, et see on kõigi täissõlmede jaoks täissõlm ja kõigi kompaktsete sõlmede jaoks kompaktne sõlm. Kuigi sillad ühendavad mõlemad võrgud omavahel, peavad nad neid ühendama ainult ühes suunas: olemasolevatest täissõlmedest kuni kompaktsete sõlmedeni. See on võimalik, kuna tehinguvormingut ei ole vaja muuta ja kompaktsete sõlmede UTXO-tõestused saab ära jätta, nii et iga kompaktne sõlm saab sarnaselt edastada tehinguid kõigile võrgus osalejatele ilma sildsõlmede osaluseta.

Järeldus

Vaatasime Utreexo akut ja rakendasime selle prototüüpi Rustis. Vaatasime võrguarhitektuuri, mis võimaldab akupõhiseid sõlmede integreerimist. Kompaktsete püüdmiste eeliseks on salvestatud andmete suurus, mis sõltub logaritmiliselt UTXO-de komplekti võimsusest, mis vähendab oluliselt selliste sõlmede kettaruumi ja salvestusvõimsuse nõudeid. Puuduseks on täiendav sõlmeliiklus tõendite edastamiseks, kuid tõendite koondamise tehnikad (kui üks tõestus tõendab mitme elemendi olemasolu) ja vahemällu salvestamine võivad aidata liiklust vastuvõetavates piirides hoida.

Viited:

• Utreexo prototüübi GitHub Rustis
• Thaddeus Dryja - Utreexo: dünaamiline räsipõhine aku, mis on optimeeritud Bitcoin UTXO komplekti jaoks
• Animeeritud illustratsioonid artiklist

Allikas: www.habr.com