Utreexo: daudzu UTXO Bitcoin saspiešana

Čau Habr!

Bitcoin tīklā visi mezgli vienprātīgi vienojas par UTXO komplektu: cik monētu ir pieejams tēriņiem, kam tieši un ar kādiem nosacījumiem. UTXO kopa ir minimālā datu kopa, kas nepieciešama validatora mezglam, bez kuras mezgls nevarēs pārbaudīt ienākošo transakciju un tos saturošo bloku derīgumu.

Šajā sakarā visos iespējamos veidos tiek mēģināts samazināt šīs kopas saglabāto attēlojumu, saspiest to, nezaudējot drošības garantijas. Jo mazāks ir saglabāto datu apjoms, jo zemākas ir diska vietas prasības validatora mezglam, kas padara validatora mezgla palaišanu lētu, ļauj paplašināt tīklu un tādējādi palielināt tīkla stabilitāti.

Šajā ziņā mēs ievietosim Rust prototipu nesenam līdzautora priekšlikumam Zibens tīkla papīrs, Tadejs Dryja Sākot no Utreexo: dinamisks uz hash balstīts akumulators, kas optimizēts Bitcoin UTXO komplektam, kas ļauj samazināt diska vietas prasības validatora mezgliem.

Kāda ir problēma?

Viena no Bitcoin daudzgadīgajām problēmām ir tā mērogojamība. Ideja par “savu banku” pieprasa tīkla dalībniekiem veikt visu lietošanai pieejamo līdzekļu uzskaiti. Bitcoin pieejamie līdzekļi tiek izteikti kā neiztērēto rezultātu kopums - UTXO komplekts. Lai gan tas nav īpaši intuitīvs attēlojums, tas ir izdevīgāks ieviešanas veiktspējas ziņā, salīdzinot ar attēlojumu, kurā katram "makam" ir "līdzsvars" kā atsevišķs ieraksts, un tas arī palielina privātumu (piem., MonētaPievienoties).

Ir svarīgi atšķirt darījumu vēsturi (to sauc par blokķēdi) no sistēmas pašreizējā stāvokļa. Bitcoin darījumu vēsture šobrīd aizņem aptuveni 200 GB diska vietas un turpina augt. Tomēr sistēmas stāvoklis ir daudz mazāks, apmēram 4 GB, un ņem vērā tikai to, ka kādam pašlaik pieder monētas. Arī šo datu apjoms laika gaitā palielinās, taču daudz lēnāk un dažkārt pat mēdz samazināties (sk. CDPV).

Vieglie klienti (SPV) tirgo drošības garantijas spējai saglabāt tikai privātās atslēgas minimālo stāvokli (UTXO-set).

UTXO un UTXO komplekts

UTXO (Unspent Transaction Output) ir neiztērētā darījuma izvade, katra darījumos pārsūtītā Satoshi ceļojuma beigu punkts. Neiztērētie rezultāti kļūst par jaunu transakciju ievadi un tādējādi tiek iztērēti (iztērēti) un noņemti no UTXO kopas.

Jauni UTXO vienmēr tiek izveidoti ar transakcijām:

• monētu bāzes darījumi bez ievades: izveidojiet jaunus UTXO, kad kalnrači izdod monētas
• regulāri darījumi: izveidojiet jaunus UTXO, vienlaikus iztērējot noteiktu esošo UTXO kopu

Darba process ar UTXO:

Maki uzskaita tēriņiem pieejamo monētu skaitu (bilance), pamatojoties uz UTXO apjomu, kas pieejams šim makam tēriņiem.

Katram validatora mezglam, lai novērstu dubultus tēriņu mēģinājumus, ir jāuzrauga kopa viss UTXO pārbaudot katrs darījumiem no katra bloķēt.

Mezglam ir jābūt loģikai:

• Papildinājumi UTXO komplektam
• Svītrojumi no UTXO komplekta
• Viena UTXO klātbūtnes pārbaude komplektā

Ir veidi, kā samazināt prasības saglabātajai informācijai par kopu, vienlaikus saglabājot iespēju pievienot un noņemt elementus, pārbaudīt un pierādīt elementa esamību komplektā, izmantojot kriptogrāfijas akumulatori.

Baterijas priekš UTXO

Ideja izmantot akumulatorus vairāku UTXO uzglabāšanai tika apspriests pirms tam.

UTXO komplekts tiek veidots lidojuma laikā, sākotnējās bloka lejupielādes (IBD) laikā, tiek saglabāts pilnībā un pastāvīgi, savukārt tā saturs mainās pēc transakciju apstrādes no katra jauna un pareiza tīkla bloka. Šim procesam ir nepieciešams lejupielādēt aptuveni 200 GB bloku datu un pārbaudīt simtiem miljonu ciparparakstu. Pēc IBD procesa pabeigšanas UTXO komplekts aizņems aptuveni 4 GB.

Tomēr, izmantojot akumulatorus, vienprātības noteikumi attiecībā uz līdzekļiem tiek samazināti līdz kriptogrāfisko pierādījumu pārbaudei un ģenerēšanai, un pieejamo līdzekļu izsekošanas slogs tiek pārnests uz šo līdzekļu īpašnieku, kurš sniedz pierādījumus par to esamību un īpašumtiesībām.

Akumulatoru var saukt par kompaktu kopas attēlojumu. Saglabātā attēla izmēram jābūt nemainīgam , vai palielinās sublineāri attiecībā pret kopas kardinalitāti un paša elementa izmēru, piemēram, , kur n ir saglabātās kopas kardinalitāte.

Šādā gadījumā akumulatoram ir jāļauj ģenerēt pierādījumu par elementa iekļaušanu komplektā (iekļaušanas pierādījums) un jārada iespēja efektīvi pārbaudīt šo pierādījumu.

Akumulatoru sauc dinamisks ja ļauj pievienot elementus un noņemt elementus no kopas.

Šāda akumulatora piemērs varētu būt RSA akumulators, ko 2018. gada decembrī ierosināja Boneh, Bunz, Fisch. Šādam akumulatoram ir nemainīgs saglabātā attēlojuma lielums, taču tam ir nepieciešama klātbūtne kopīgs noslēpums (uzticama iestatīšana). Šī prasība noliedz šāda akumulatora piemērojamību neuzticamiem tīkliem, piemēram, Bitcoin, jo datu noplūde slepenās ģenerēšanas laikā var ļaut uzbrucējiem izveidot viltus pierādījumus par UTXO esamību, maldinot mezglus ar UTXO komplektu, kura pamatā ir šāds akumulators.

Utreekso

Thaddeus Dryja piedāvātais Utreexo dizains ļauj radīt dinamisks akumulators bez uzticama iestatīšana.

Utreexo ir perfekta bināra mežs Merkles koki un ir ideju attīstība, kas tika prezentēta Efektīvi asinhronie akumulatori izplatītajiem pki, pievienojot iespēju noņemt elementus no komplekta.

Akumulatora loģiskā struktūra

Akumulatora šūnas ir izvietotas ideālu bināro koku mežā. Koki ir sakārtoti pēc augstuma. Šis attēlojums tika izvēlēts kā vizuālākais un ļauj vizualizēt koku saplūšanu darbības laikā ar akumulatoru.

Autore atzīmē, ka, tā kā visi mežā esošie koki ir ideāli, to augstums tiek izteikts kā pakāpē divi, tāpat kā jebkuru naturālu skaitli var attēlot kā divu pakāpju summu. Attiecīgi jebkuru lapu kopu var grupēt bināros kokos, un visos gadījumos jauna elementa pievienošana prasa zināšanas tikai par glabājamo koku sakņu mezgliem.

Tādējādi saglabātais Utreexo akumulatora attēlojums ir saknes mezglu saraksts (Merkle sakne), un ne viss koku mežs.

Saknes elementu sarakstu attēlosim kā Vec<Option<Hash>>. Izvēles veids Option<Hash> norāda, ka var trūkt saknes elementa, kas nozīmē, ka akumulatorā nav koka ar atbilstošu augstumu.

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

Elementu pievienošana

Vispirms aprakstīsim funkciju parent(), kas atpazīst divu norādīto elementu vecāku mezglu.

vecāku() funkcija

Tā kā mēs izmantojam Merkles kokus, katra no diviem mezgliem vecāks ir viens mezgls, kas glabā pakārtoto mezglu jaucējvārdu sajaukšanu:

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

Autors atzīmē, ka, lai novērstu uzbrukumus, kurus aprakstīja Čārlzs Buljē, Pjērs Alēns Fouque, Adi Šamirs un Sebastjens Cimmers
Otrais priekšattēla uzbrukums sajauktajām jaucējfunkcijām, papildus divām jaukšanām, savienojumam jāpievieno arī augstums koka iekšpusē.

Pievienojot elementus akumulatoram, jums ir jāseko līdzi, kuri saknes elementi tiek mainīti. Sekojot katra pievienotā elementa saknes elementu maiņas ceļam, vēlāk varat izveidot pierādījumu par šo elementu klātbūtni.

Izsekojiet izmaiņām, kad tās pievienojat

Lai izsekotu veiktajām izmaiņām, deklarēsim struktūru Update, kurā tiks saglabāti dati par mezglu izmaiņām.

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

Lai akumulatoram pievienotu elementu, jums ir nepieciešams:

• Izveidojiet sakņu elementu grozu masīvu new_roots un ievietojiet tur esošos saknes elementus, pa vienam katram spainim:

Kods

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

• Pievienojiet pievienojamos elementus (masīvs insertions) uz pirmo grozu new_roots[0]:

Kods

new_roots[0].extend_from_slice(insertions);

• Apvienojiet pirmajam grozam pievienotās preces ar pārējām:
  • Visiem groziem ar vairākām precēm:
    1. Paņemiet divus elementus no groza gala, aprēķiniet to vecākus, noņemiet abus elementus
    2. Pievienojiet aprēķināto vecāku nākamajam grozam

Kods

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

• Pārvietojiet saknes elementus no tvertnēm uz iegūto akumulatoru masīvu

Kods

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

Pierādījuma izveide pievienotajiem elementiem

Pierādījums par elementa iekļaušanu akumulatorā (Proof) kalpos kā Merkles ceļš, kas sastāv no ķēdes ProofStep. Ja ceļš nekur neved, tad pierādījums ir nepareizs.

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

Iepriekš iegūtās informācijas izmantošana, pievienojot elementu (struktūru Update), varat izveidot pierādījumu, ka akumulatoram ir pievienots elements. Lai to izdarītu, mēs apskatām veikto izmaiņu tabulu un pievienojam Merkles ceļam katru soli, kas vēlāk kalpos kā pierādījums:

Kods

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

Pierādījuma izveides process

Elementa pierādījuma pārbaude

Elementa iekļaušanas pierādījuma pārbaude nozīmē, ka jāseko Merkles ceļam, līdz tas noved pie esoša saknes 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
    }
}

Vizuāli:

A pierādījuma pārbaudes process

Vienumu noņemšana

Lai izņemtu elementu no akumulatora, jums ir jāsniedz derīgs pierādījums tam, ka baterija tur atrodas. Izmantojot pierādījuma datus, var aprēķināt jaunus akumulatora saknes elementus, kuriem dotais pierādījums vairs nebūs patiess.

Algoritms ir šāds:

1. Tāpat kā papildus, mēs organizējam tukšu grozu komplektu, kas atbilst Merkles kokiem ar augstumu, kas vienāds ar divu jaudu no groza indeksa
2. Grozās ievietojam elementus no Merkles takas pakāpieniem; groza indekss ir vienāds ar pašreizējā soļa skaitli
3. Mēs noņemam saknes elementu, uz kuru ved ceļš no pierādījuma
4. Tāpat kā pievienojot, mēs aprēķinām jaunus saknes elementus, apvienojot elementus no groziem pa pāriem un pārvietojot apvienošanas rezultātu uz nākamo grozu

Kods

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

Elementa "A" noņemšanas process:

Integrācija esošajā tīklā

Izmantojot piedāvāto akumulatoru, mezgli var izvairīties no DB izmantošanas visu UTXO glabāšanai, vienlaikus spējot mainīt UTXO kopu. Tomēr rodas problēma darbā ar pierādījumiem.

Sauksim validatora mezglu, kas izmanto UTXO akumulatoru kompakts (kompaktā stāvokļa mezgls), un validators bez akumulatora ir pabeigts (pilns mezgls). Divu mezglu klašu esamība rada problēmas to integrēšanai vienā tīklā, jo kompaktiem mezgliem ir nepieciešams pierādījums par UTXO esamību, kas tiek iztērēti darījumos, bet pilnajiem mezgliem nav. Ja visi tīkla mezgli vienlaikus un saskaņoti nepāries uz Utreexo lietošanu, tad kompaktie mezgli atpaliks un nespēs darboties Bitcoin tīklā.

Lai atrisinātu kompakto mezglu integrēšanas tīklā problēmu, tiek ierosināts ieviest papildu mezglu klasi - tilti. Tilta mezgls ir pilnīgs mezgls, kurā glabājas arī Utreexo akumulators un ieslēgšanas apliecinājums viss UTXO no UTXO komplekta. Tilti aprēķina jaunus jaucējus un atjaunina akumulatoru un pierādījumus, kad tiek saņemti jauni darījumu bloki. Akumulatora un pierādījumu uzturēšana un atjaunināšana šādiem mezgliem neuzliek papildu skaitļošanas slodzi. Tilti upurē vietu diskā: nepieciešams sakārtot lietas hashes, salīdzinot ar jaucējvērtības kompaktajiem mezgliem, kur n ir UTXO kopas jauda.

Tīkla arhitektūra

Tilti ļauj pakāpeniski pievienot tīklam kompaktus mezglus, nemainot esošo mezglu programmatūru. Pilni mezgli darbojas tāpat kā iepriekš, sadalot darījumus un blokus savā starpā. Tilta mezgli ir pilni mezgli, kas papildus saglabā Utreexo akumulatora datus un iekļaušanas pierādījumu kopu viss Pagaidām UTXO. Tilta mezgls sevi kā tādu nereklamē, izliekoties par pilnu mezglu visiem pilnajiem mezgliem un par kompakto mezglu visiem kompaktajiem. Lai gan tilti savieno abus tīklus kopā, tie faktiski ir jāsavieno tikai vienā virzienā: no esošajiem pilnajiem mezgliem līdz kompaktajiem mezgliem. Tas ir iespējams, jo transakcijas formāts nav jāmaina, un UTXO apliecinājumus kompaktajiem mezgliem var izmest, tāpēc jebkurš kompaktais mezgls var līdzīgi pārraidīt transakcijas visiem tīkla dalībniekiem bez tilta mezglu līdzdalības.

Secinājums

Mēs apskatījām Utreexo akumulatoru un ieviesām tā prototipu Rustā. Mēs apskatījām tīkla arhitektūru, kas ļaus integrēt uz akumulatoru balstītus mezglus. Kompakto nozveju priekšrocība ir saglabāto datu lielums, kas logaritmiski ir atkarīgs no UTXO kopas jaudas, kas ievērojami samazina diska vietas un uzglabāšanas veiktspējas prasības šādiem mezgliem. Trūkums ir papildu mezglu trafika pierādījumu pārsūtīšanai, taču pierādījumu apkopošanas metodes (kad viens pierādījums pierāda vairāku elementu esamību) un kešatmiņa var palīdzēt saglabāt trafiku pieņemamās robežās.

atsauces:

• Utreexo prototipa GitHub Rustā
• Tadejs Dryja Sākot no Utreexo: dinamisks uz hash balstīts akumulators, kas optimizēts Bitcoin UTXO komplektam
• Animētas ilustrācijas no raksta

Avots: www.habr.com