Utreexo: þjappa mörgum UTXO Bitcoin

Hæ Habr!

Í Bitcoin netinu eru allir hnútar, með samstöðu, sammála um sett af UTXO: hversu margar mynt eru tiltækar til að eyða, hverjum nákvæmlega og við hvaða aðstæður. UTXO settið er lágmarksgagnasafnið sem krafist er fyrir löggildingarhnút, án þess mun hnúturinn ekki geta sannreynt réttmæti komandi viðskipta og kubba sem innihalda þær.

Í þessu sambandi er reynt á allan mögulegan hátt að draga úr geymdri framsetningu þessa setts, þjappa því saman án þess að tapa öryggisábyrgð. Því minna sem geymd gagnamagn er, því lægri eru plásskröfur löggildingarhnútsins, sem gerir uppsetningu á staðfestingarhnút ódýr, gerir þér kleift að stækka netið og auka þar með stöðugleika netsins.

Í þessari færslu munum við birta Rust frumgerð af nýlegri tillögu frá meðhöfundi Lightning Network Paper, Thaddeus Dryja - Utreexo: kraftmikill hass-undirstaða rafgeymir sem er fínstilltur fyrir Bitcoin UTXO settið, sem gerir kleift að draga úr kröfum um pláss fyrir staðfestingarhnúta.

Hvað er vandamálið?

Eitt af ævarandi vandamálum Bitcoin hefur verið sveigjanleiki þess. Hugmyndin um „þinn eigin banka“ krefst þess að þátttakendur netsins haldi skrár yfir alla fjármuni sem eru tiltækir til notkunar. Í Bitcoin er tiltækt fé gefið upp sem mengi ónotaðra úttaka - UTXO-sett. Þó að þetta sé ekki sérlega leiðandi framsetning, þá er það gagnlegt hvað varðar framkvæmd frammistöðu fram yfir framsetningu þar sem hvert „veski“ hefur „jafnvægi“ sem sérstakri færslu og bætir einnig við næði (t.d. CoinJoin).

Mikilvægt er að greina á milli viðskiptasögu (það sem kallast blockchain) og núverandi ástands kerfisins. Bitcoin viðskiptasaga tekur nú um 200 GB af plássi og heldur áfram að stækka. Hins vegar er kerfisástand mun minna, af stærðargráðunni 4 GB, og tekur aðeins tillit til þess að einhver á mynt eins og er. Rúmmál þessara gagna eykst einnig með tímanum, en á mun hægari hraða og hefur stundum tilhneigingu til að minnka (sjá CDPV).

Léttir viðskiptavinir (SPV) versla með öryggisábyrgð fyrir getu til að geyma ekkert lágmarksástand (UTXO-sett) annað en einkalykla.

UTXO og UTXO-sett

UTXO (Unspent Transaction Output) er ónotað viðskiptaúttak, endapunktur ferðar hvers Satoshi sem fluttur er í viðskiptum. Ónýtt framleiðsla verður inntak nýrra viðskipta og er þannig eytt (eyðsla) og fjarlægð úr UTXO-settinu.

Ný UTXO eru alltaf búin til með viðskiptum:

• myntgrunnsviðskipti án inntaks: búðu til nýjar UTXO þegar námumenn gefa út mynt
• regluleg viðskipti: búðu til nýjar UTXO meðan þú eyðir ákveðnu setti af núverandi UTXO

Vinnuferli með UTXO:

Veski telja fjölda mynta sem eru tiltækar til eyðslu (staða) miðað við magn UTXO sem er tiltækt fyrir þetta veski til eyðslu.

Hver staðfestingarhnútur, til að koma í veg fyrir tvöfaldar eyðslutilraunir, verður að fylgjast með settinu allt UTXO þegar athugað er hver viðskipti af hverju blokk.

Hnúturinn verður að hafa rökfræði:

• Viðbætur við UTXO-sett
• Eyðingar úr UTXO-setti
• Athugar tilvist eins UTXO í setti

Það eru leiðir til að draga úr kröfum um vistaðar upplýsingar um mengi, en viðhalda getu til að bæta við og fjarlægja þætti, athuga og sanna tilvist frumefnis í mengi með því að nota dulmáls rafgeymir.

Rafhlöður fyrir UTXO

Hugmyndin um að nota rafhlöður til að geyma mörg UTXO var rætt áðan.

UTXO-settið er byggt á flugi, við upphafsblokk niðurhalið (IBD), geymt að fullu og varanlega, á meðan innihald þess breytist eftir að hafa unnið viðskipti úr hverri nýrri og réttri blokk netkerfisins. Þetta ferli krefst þess að hlaðið sé niður um það bil 200 GB af blokkargögnum og að hundruð milljóna stafrænna undirskrifta sé staðfest. Eftir að IBD ferlinu er lokið er niðurstaðan sú að UTXO-settið mun taka um 4 GB.

Hins vegar, með safnara, eru reglur um samstöðu um fjármuni minnkaðar til að sannreyna og búa til dulmálssönnunargögn og byrðina við að fylgjast með tiltækum fjármunum er færð yfir á eiganda þessara fjármuna, sem sýnir sönnun um tilvist þeirra og eignarhald.

Hægt er að kalla rafgeymi samsetta framsetningu mengis. Stærð geymdrar framsetningar verður annaðhvort að vera stöðug , eða aukast undirlínulega með tilliti til aðalgildi mengisins og stærð frumefnisins sjálfs, til dæmis , þar sem n er aðalgildi geymda mengisins.

Í þessu tilviki ætti rafgeymirinn að leyfa að búa til sönnun fyrir því að þáttur sé innifalinn í menginu (inntakssönnun) og gera það mögulegt að sannreyna þessa sönnun á áhrifaríkan hátt.

Rafhlaðan heitir kraftmikil if gerir þér kleift að bæta við þáttum og fjarlægja þætti úr setti.

Dæmi um slíka rafhlöðu væri RSA rafgeymir sem Boneh, Bunz, Fisch lagði til í desember 2018. Slík rafgeymir hefur stöðuga stærð geymdra framsetningar, en krefst nærveru sameiginlegt leyndarmál (traust uppsetning). Þessi krafa dregur úr gildi slíkrar rafsöfnunar fyrir traustlaus netkerfi eins og Bitcoin, þar sem gagnaleki við leyndarframleiðslu getur gert árásarmönnum kleift að búa til rangar sönnun fyrir tilvist UTXO, blekkja hnúta með UTXO-setti sem byggir á slíkum rafgeyma.

Utreexo

Utreexo hönnunin sem Thaddeus Dryja lagði til gerir það mögulegt að búa til kraftmikið аккумулятор без traust-uppsetning.

Utreexo er skógur fullkomins tvíundar Merkle tré og er þróun þeirra hugmynda sem settar eru fram í Skilvirkir ósamstilltir rafgeymir fyrir dreifða pki, bætir við getu til að fjarlægja þætti úr setti.

Rökfræðileg uppbygging rafhlöðunnar

Rafhlöðufrumum er raðað í skógi fullkominna tvítendra trjáa. Tré eru raðað eftir hæð. Þessi framsetning var valin sú sjónrænasta og gerir þér kleift að sjá samruna trjáa við aðgerðir á rafhlöðunni.

Höfundur bendir á að þar sem öll trén í skóginum eru tilvalin er hæð þeirra gefin upp sem veldi tveggja, rétt eins og hægt er að tákna hvaða náttúrulega tölu sem er summu tveggja velda. Í samræmi við það er hægt að flokka hvaða sett af laufum sem er í tvöföld tré og í öllum tilfellum þarf þekkingu til að bæta við nýjum þætti aðeins um rótarhnúta geymdra trjáa.

Þannig er geymd framsetning Utreexo rafgeymisins listi yfir rótarhnúta (Merkle root), og ekki allur skógurinn af trjám.

Við skulum tákna listann yfir frumefni sem Vec<Option<Hash>>. Valfrjáls gerð Option<Hash> gefur til kynna að rótarþáttinn gæti vantað, sem þýðir að ekkert tré er með viðeigandi hæð í rafgeyminum.

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

Bætir við þáttum

Fyrst skulum við lýsa aðgerðinni parent(), sem þekkir móðurhnútinn fyrir tvo tiltekna þætti.

parent() fall

Þar sem við erum að nota Merkle tré, er foreldri hvers hnúta tveggja einn hnút sem geymir kjötkássa samtengingar kjötkássa barnahnútanna:

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

Höfundur bendir á að til að koma í veg fyrir árásirnar sem Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir og Sebastien Zimmer lýstu í
Önnur formyndarárásir á þeyttar kjötkássaaðgerðir, auk kjötkássanna tveggja, ætti einnig að bæta hæðinni inni í trénu við samtenginguna.

Þegar þú bætir þáttum við safnið þarftu að fylgjast með hvaða rótarþáttum er breytt. Með því að fylgja leiðinni til að breyta rótarþáttunum fyrir hvern þátt sem þú bætir við geturðu síðar smíðað sönnun fyrir tilvist þessara þátta.

Fylgstu með breytingum þegar þú bætir þeim við

Til að fylgjast með breytingunum sem gerðar eru skulum við lýsa yfir uppbyggingunni Update, sem mun geyma gögn um breytingar á hnút.

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

Til að bæta þætti við rafhlöðuna þarftu:

• Búðu til úrval af körfum af rótarþáttum new_roots og settu núverandi rótareiningar þar, einn fyrir hverja fötu:

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

• Bættu við þáttunum sem á að bæta við (array insertions) í fyrstu körfu new_roots[0]:

Code

new_roots[0].extend_from_slice(insertions);

• Blandið hlutunum sem bætt er í fyrstu körfuna saman við restina:
  • Fyrir allar kerrur með fleiri en einum hlut:
    1. Taktu tvo þætti frá enda körfunnar, reiknaðu foreldri þeirra, fjarlægðu báða þættina
    2. Bættu útreiknuðu foreldri í næstu körfu

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

• Færðu rótareiningar úr hólfum yfir í safnfylki sem myndast

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

Að búa til sönnun fyrir bættum þáttum

Sönnun fyrir því að fruman sé innifalin í rafhlöðunni (Proof) mun þjóna sem Merkle Path, sem samanstendur af keðju ProofStep. Ef leiðin liggur hvergi, þá er sönnunin röng.

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

Notaðu upplýsingarnar sem fengnar voru áðan þegar frumefni (bygging Update), getur þú búið til sönnun þess að frumefni hafi verið bætt við rafhlöðuna. Til að gera þetta förum við í gegnum töfluna yfir breytingar sem gerðar hafa verið og bætum hverju skrefi við leið Merkle, sem mun síðan þjóna sem sönnun:

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

Aðferð við að búa til sönnun

Athugar sönnun fyrir frumefni

Athugun á inntökusönnun frumefnis snýst um að fylgja Merkle leiðinni þar til hún leiðir til núverandi rótarþáttar:

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

Sjónrænt:

Aðferð við að athuga sönnun fyrir A

Að fjarlægja hluti

Til að fjarlægja klefi úr rafhlöðu verður þú að leggja fram gildar sönnunargögn um að klefinn sé þar. Með því að nota gögnin úr sönnuninni er hægt að reikna út nýja rótarþætti rafgeymisins sem gefin sönnun mun ekki lengur vera sönn fyrir.

Reikniritið er sem hér segir:

1. Eins og með viðbót, skipuleggjum við sett af tómum körfum sem samsvara Merkle trjám með hæð sem er jöfn krafti tveggja úr körfuvísitölunni
2. Við setjum þætti úr þrepum Merkle leiðarinnar í körfurnar; körfuvísitalan er jöfn númeri núverandi þreps
3. Við fjarlægjum rótarþáttinn sem leiðin frá sönnuninni leiðir til
4. Eins og með að bæta við, reiknum við nýja rótarþætti með því að sameina þætti úr körfum í pörum og færa niðurstöðu sameiningarinnar í næstu körfu

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

Ferlið við að fjarlægja frumefni "A":

Samþætting inn í núverandi net

Með því að nota fyrirhugaða rafgeymi geta hnútar forðast að nota DB til að geyma öll UTXO en samt geta breytt UTXO-settinu. Hins vegar kemur upp vandamálið við að vinna með sönnunargögn.

Við skulum kalla á löggildingarhnútinn sem notar UTXO rafgeymann samningur (compact-state hnút), og staðfestingartækið án rafgeyma er heill (fullur hnútur). Tilvist tveggja flokka hnúta skapar vandamál við að samþætta þá í einu neti, þar sem þéttir hnútar krefjast sönnunar fyrir tilvist UTXOs, sem eru eytt í viðskiptum, en fullir hnútar gera það ekki. Ef allir nethnútar skipta ekki samtímis og á samræmdan hátt yfir í að nota Utreexo, þá verða þéttir hnútar skildir eftir og geta ekki starfað á Bitcoin netinu.

Til að leysa vandamálið við að samþætta þétta hnúta í netið er lagt til að kynna viðbótarflokk af hnútum - brýr. Brúarhnútur er heill hnútur sem einnig geymir Utreexo rafhlöðuna og virkjunarsönnun fyrir allt UTXO frá UTXO-setti. Brýr reikna út nýjan kjötkássa og uppfæra safnið og sannanir þegar nýjar færslur koma. Viðhald og uppfærsla á rafgeymi og sönnunargögnum veldur ekki auknu reikniálagi á slíka hnúta. Brýr fórna diskaplássi: þarf að halda hlutunum skipulögðum kjötkássa, miðað við kjötkássa fyrir þétta hnúta, þar sem n er kraftur UTXO settsins.

Netarkitektúr

Brýr gera það mögulegt að bæta smám saman þéttum hnútum við netið án þess að breyta hugbúnaði núverandi hnúta. Fullir hnútar starfa eins og áður og dreifa viðskiptum og blokkum sín á milli. Brúhnútar eru fullir hnútar sem að auki geyma Utreexo rafhlöðugögn og sett af inntökusönnun fyrir allt UTXO í bili. Brúarhnúturinn auglýsir sig ekki sem slíkan, þykist vera fullur hnútur fyrir alla fulla hnúta og samningshnútur fyrir alla samninga. Þó brýr tengi bæði netin saman, þurfa þær í raun aðeins að tengja þau í eina átt: frá núverandi fullum hnútum til þéttra hnúta. Þetta er mögulegt vegna þess að ekki þarf að breyta viðskiptasniðinu og hægt er að henda UTXO sönnunum fyrir samninga hnúta, þannig að allir samningar hnútar geta á sama hátt útvarpað færslum til allra þátttakenda netsins án þátttöku brúarhnúta.

Ályktun

Við skoðuðum Utreexo rafhlöðuna og útfærðum frumgerð hennar í Rust. Við skoðuðum netarkitektúrinn sem mun leyfa samþættingu rafhlöðubundinna hnúta. Kosturinn við þéttan afla er stærð geymdra gagna, sem fer logaritmískt eftir krafti UTXO settsins, sem dregur verulega úr kröfum um pláss og geymsluafköst fyrir slíka hnúta. Ókosturinn er aukin hnútumferð til að senda sannanir, en sönnunarsöfnunartækni (þegar ein sönnun sannar tilvist nokkurra þátta) og skyndiminni geta hjálpað til við að halda umferð innan viðunandi marka.

tilvísanir:

• GitHub af Utreexo frumgerð í Rust
• Thaddeus Dryja - Utreexo: kraftmikill hass-undirstaða rafgeymir sem er fínstilltur fyrir Bitcoin UTXO settið
• Hreyfimyndir úr greininni

Heimild: www.habr.com