🥇Utreexo: UTXO Bitcoin | asko konprimitzen ProHoster

Aupa Habr!

Bitcoin sarean, nodo guztiek, adostasun bidez, UTXO multzo bat adosten dute: zenbat txanpon dauden gastatzeko, nori zehazki eta zein baldintzatan. UTXO multzoa baliozkotzaile-nodo baterako behar den gutxieneko datu-multzoa da, eta hori gabe nodoak ezin izango du egiaztatu sarrerako transakzioen eta horiek dituzten blokeen baliozkotasuna.

Ildo horretan, multzo horren gordetako irudikapena murrizteko modu guztietan saiatzen ari dira, segurtasun-bermeak galdu gabe konprimitzeko. Biltegiratutako datuen bolumena zenbat eta txikiagoa izan, orduan eta balorazio-nodoaren disko-espazio eskakizun txikiagoak izango dira, eta horrek baliozkotze-nodo bat abiarazteko merke bihurtzen du, sarea zabaltzeko eta sarearen egonkortasuna areagotzeko aukera ematen du.

Post honetan egilekide baten azken proposamen baten Rust prototipoa argitaratuko dugu Lightning Network Papera, Thaddeus Dryja - Utreexo: Bitcoin UTXO multzorako optimizatutako hash-en oinarritutako metagailu dinamikoa, baliozkotzaile-nodoen diskoko espazio-eskakizunak murrizteko aukera ematen duena.

Zein da arazoa?

Bitcoin-en betiko arazoetako bat bere eskalagarritasuna izan da. "Zure bankua" ideiak sareko parte-hartzaileek erabilgarri dauden funts guztien erregistroak gordetzea eskatzen du. Bitcoin-en, erabilgarri dauden funtsak gastatu gabeko irteera multzo gisa adierazten dira - UTXO multzo bat. Irudikapen hau bereziki intuitiboa ez den arren, onuragarria da inplementazio-errendimenduari dagokionez "zorro" bakoitzak "oreka" bat duen sarrera bereizi gisa eta pribatutasuna gehitzen duen irudikapen baten aurrean (adibidez. TxanponBatu).

Garrantzitsua da transakzioen historia (blokea deitzen dena) eta sistemaren egungo egoera bereiztea. Bitcoin transakzioen historiak 200 GB inguru okupatzen ditu diskoko espazioa, eta hazten jarraitzen du. Hala ere, sistemaren egoera askoz txikiagoa da, 4 GB-ko ordenakoa, eta gaur egun norbaitek txanponak dituena bakarrik hartzen du kontuan. Datu horien bolumena ere handitu egiten da denborarekin, baina askoz ere astiroagoan eta, batzuetan, behera egin ohi du (ikus CDPV).

Bezero arinak (SPV) merkataritzako segurtasun-bermeak bermatzen ditu gako pribatuak ez diren gutxieneko egoerarik (UTXO-multzoa) gordetzeko.

UTXO eta UTXO-multzoa

UTXO (Gastatu gabeko transakzio-irteera) gastatu gabeko transakzio-irteera da, transakzioetan transferitutako Satoshi bakoitzaren bidaiaren amaiera-puntua. Gastu gabeko irteerak transakzio berrien sarrera bihurtzen dira eta, beraz, gastatu (gastu) eta UTXO multzotik kentzen dira.

UTXO berriak transakzioen bidez sortzen dira beti:

coinbase transakzioak sarrerarik gabe: sortu UTXO berriak meatzariek txanponak igortzen dituztenean
ohiko transakzioak: UTXO berriak sortu lehendik dauden UTXO multzo jakin bat gastatzen duzun bitartean

UTXOrekin lan egiteko prozesua:

Diru-zorroek gastatzeko erabilgarri dagoen txanpon kopurua (saldoa) zenbatzen dute diru-zorro honek gastatzeko duen UTXO kopuruaren arabera.

Balidatzaile-nodo bakoitzak, gastu bikoitza saiakerak saihesteko, multzoa kontrolatu behar du guztiak UTXO egiaztatzean bakoitzeko transakzioak bakoitzeko blokeatu.

Nodoak logika izan behar du:

UTXO-multzoaren gehigarriak
UTXO-multzotik ezabatzeak
Multzo batean UTXO bakar baten presentzia egiaztatzea

Multzo bati buruzko biltegiratutako informazioaren eskakizunak murrizteko moduak daude, elementuak gehitzeko eta kentzeko gaitasuna mantenduz, multzo batean elementu baten existentzia egiaztatu eta frogatzeko. metagailu kriptografikoak.

UTXOrako bateriak

UTXO anitz gordetzeko bateriak erabiltzearen ideia eztabaidatu zen lehenago.

UTXO-multzoa hegan eraikitzen da, hasierako blokeen deskargan (IBD), osorik eta betirako gordeta, sareko bloke berri eta zuzen bakoitzeko transakzioak prozesatu ondoren bere edukia aldatzen den bitartean. Prozesu honek 200 GB gutxi gorabehera bloke-datu deskargatu eta ehunka milioi sinadura digital egiaztatu behar ditu. IBD prozesua amaitu ondoren, UTXO multzoak 4 GB inguru okupatuko dituela da.

Hala ere, metagailuekin, funtsen adostasun-arauak froga kriptografikoak egiaztatzeko eta sortzera murrizten dira, eta erabilgarri dauden funtsen jarraipenaren zama funts horien jabearen esku uzten da, zeinak haien existentzia eta jabetzaren frogak ematen dituen.

Metagailu bati multzo baten irudikapen trinkoa dei daiteke. Biltegiratutako irudikapenaren tamainak konstantea izan behar du , edo handitu azpilinealki multzoaren kardinalitateari eta elementuaren beraren tamainari dagokionez, adibidez , non n gordetako multzoaren kardinalitatea den.

Kasu honetan, metagailuak elementu bat multzoan sartzearen froga bat sortzea ahalbidetu beharko luke (sartze froga) eta froga hori eraginkortasunez egiaztatzea ahalbidetu beharko luke.

Bateria deitzen da dinamikoa elementuak gehitzeko eta multzo batetik elementuak kentzeko aukera ematen badu.

Bateria horren adibide bat izango litzateke Boneh, Bunz, Fisch-ek proposatutako RSA metagailua 2018ko abenduan. Horrelako metagailu batek gordetako irudikapenaren tamaina konstantea du, baina presentzia eskatzen du partekatutako sekretua (konfigurazio fidagarria). Baldintza honek ezeztatzen du halako metagailu baten aplikagarritasuna Bitcoin bezalako konfiantzarik gabeko sareetarako, sekretua sortzean datu-ihesak erasotzaileek UTXO baten existentziaren froga faltsuak sor ditzaketelako, metagailu batean oinarritutako UTXO multzoa duten nodoak engainatuz.

Utreexo

Thaddeus Dryjak proposatutako Utreexo diseinuak posible egiten du sortzea dinamikoa аккумулятор gabe konfiantzazko konfigurazioa.

Utreexo bitar perfektuko basoa da Merkle Zuhaitzak eta aurkeztutako ideien garapena da Pki banaturako metagailu asinkrono eraginkorrak, multzo batetik elementuak kentzeko gaitasuna gehituz.

Bateriaren Egitura Logikoa

Baterien zelulak zuhaitz bitar idealen baso batean daude antolatuta. Zuhaitzak altueraren arabera ordenatuta daude. Irudikapen hau ikusizkoena bezala aukeratu da eta baterian egindako eragiketetan zuhaitzen bat egitea ikusteko aukera ematen du.

Egileak dio basoko zuhaitz guztiak idealak direnez, haien altuera biren potentzia gisa adierazten dela, edozein zenbaki natural biren potentziaren batura gisa irudika daitekeen bezala. Horren arabera, edozein hosto multzo zuhaitz bitarretan multzoka daiteke, eta, kasu guztietan, elementu berri bat gehitzeak ezagutza eskatzen du. gordetako zuhaitzen erro-nodoei buruz bakarrik.

Horrela, Utreexo metagailuaren gordetako irudikapena erro-nodoen zerrenda bat da (Merkle erroa), eta ez zuhaitzen baso osoa.

Irudika dezagun erro-elementuen zerrenda gisa Vec<Option<Hash>>. Aukerako mota Option<Hash> erro-elementua falta izan daitekeela adierazten du, hau da, metagailuan altuera egokia duen zuhaitzik ez dagoela adierazten du.

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

Elementuak gehitzea

Lehenik eta behin, deskriba dezagun funtzioa parent(), emandako bi elementuren nodo nagusia ezagutzen duena.

guraso() funtzioa

Merkle zuhaitzak erabiltzen ari garenez, bi nodo bakoitzaren gurasoa nodo haurraren hash-en katearen hash-a gordetzen duen nodo bat da:

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

Egileak ohartarazi du Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir eta Sebastien Zimmer-ek deskribatutako erasoak saihesteko.
Bigarren aurreirudiaren erasoak dithered hash funtzioetan, bi hashez gain, zuhaitzaren barruko altuera ere gehitu behar zaio kateamenduari.

Metagailuari elementuak gehitzen dituzun heinean, zein erro elementu aldatzen diren jarraitu behar duzu. Gehitzen duzun elementu bakoitzaren erro-elementuak aldatzeko bidea jarraituz gero, elementu horien presentziaren froga bat eraiki dezakezu.

Jarraitu aldaketen jarraipena gehitzen dituzun heinean

Egindako aldaketen jarraipena egiteko, deklara dezagun egitura Update, nodoen aldaketei buruzko datuak gordeko dituena.

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

Bateriari elementu bat gehitzeko, behar duzu:

Sortu erro-elementuen saski sorta new_roots eta jarri bertan dauden erro-elementuak, ontzi bakoitzeko bat:

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

Erantsi gehitu beharreko elementuak (array insertions) lehen gurdira new_roots[0]:

Code

new_roots[0].extend_from_slice(insertions);

Lotu lehen saskira gehitutako elementuak gainerakoekin:
- Elementu bat baino gehiago duten gurdi guztietarako:
  1. Hartu bi elementu saskiaren amaieratik, kalkulatu haien gurasoa, kendu bi elementuak
  2. Gehitu kalkulatutako gurasoa hurrengo saskira

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

Eraman erro-elementuak edukiontzietatik ondoriozko metagailu-matrizera

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

Gehitutako elementuen froga bat sortzea

Zelula baterian sartu izanaren froga (Proof) Merkle Bidea izango da, kate batez osatua ProofStep. Bideak inora eramaten ez badu, froga okerra da.

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

Elementu bat gehitzerakoan lehenago lortutako informazioa erabiltzea (egitura Update), bateriari elementu bat gehitu zaion froga egin dezakezu. Horretarako, egindako aldaketen taulatik pasatuko gara eta urrats bakoitza Merkle-ren bideari gehituko diogu, ondoren froga gisa balioko duena:

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

Froga bat sortzeko prozesua

Elementu baten froga egiaztatzea

Elementu baten barne-froga egiaztatzea Merkle-ren bidea jarraitzea da, lehendik dagoen erro-elementu batera eraman arte:

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

Ikusmenean:

A-ren froga egiaztatzeko prozesua

Elementuak kentzea

Bateria batetik zelula bat kentzeko, zelula hor dagoela dioen baliozko froga eman behar duzu. Frogaren datuak erabiliz, metagailuaren erro-elementu berriak kalkulatu daitezke, eta horretarako emandako froga egiazkoa izango ez dena.

Algoritmoa hau da:

Horrez gain, Merkle zuhaitzei dagozkien saski huts multzo bat antolatzen dugu saskiaren indizetik biren potentziaren altuera dutenak.
Merkle bideko eskaileretako elementuak txertatzen ditugu saskietan; saskiaren indizea uneko urratsaren zenbakiaren berdina da
Frogaren bideak eramaten duen erro-elementua kenduko dugu
Gehitzean bezala, erro-elementu berriak kalkulatzen ditugu saskietako elementuak binaka konbinatuz eta batasunaren emaitza hurrengo saskira eramanez.

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

"A" elementua kentzeko prozesua:

Lehendik dagoen sare batean integratzea

Proposatutako metagailua erabiliz, nodoek DB bat erabiltzea saihestu dezakete UTXO guztiak gordetzeko, UTXO-multzoa alda dezaketen bitartean. Hala ere, frogak lantzeko arazoa sortzen da.

Dei diezaiogun UTXO metagailua erabiltzen duen baliozkotzaile-nodoari trinkoa (egoera trinkoko nodoa), eta metagailurik gabeko baliozkotzailea da osatu (nodo osoa). Bi nodo klase egoteak arazo bat sortzen du sare bakarrean integratzeko, nodo trinkoek UTXOen existentziaren froga behar baitute, transakzioetan gastatzen direnak, nodo osoek ez. Sare-nodo guztiak aldi berean eta modu koordinatuan Utreexo erabiltzera aldatzen ez badira, orduan nodo trinkoak atzean geratuko dira eta ezin izango dute Bitcoin sarean funtzionatu.

Nodo trinkoak sarean integratzeko arazoa konpontzeko, nodo klase gehigarri bat sartzea proposatzen da - zubiak. Zubi-nodoa Utreexo bateria eta pizteko froga ere gordetzen dituen nodo osoa da guztiak UTXO-tik UTXO-set. Bridgesek hash berriak kalkulatzen ditu eta metagailua eta frogak eguneratzen ditu transakzio bloke berriak iristen diren heinean. Metagailua eta frogak mantentzeak eta eguneratzeak ez die halako nodoei karga konputazional gehigarririk ezartzen. Zubiek diskoko espazioa sakrifikatzen dute: gauzak antolatuta mantendu behar dituzte hashekin alderatuta nodo trinkoetarako hashak, non n UTXO multzoaren potentzia den.

Sare arkitektura

Zubiek aukera ematen dute pixkanaka nodo trinkoak sarean gehitzea lehendik dauden nodoen softwarea aldatu gabe. Nodo osoek lehen bezala funtzionatzen dute, transakzioak eta blokeak euren artean banatuz. Zubi-nodoak Utreexo bateriaren datuak eta inklusio-froga multzo bat gordetzen dituzten nodo osoak dira guztiak UTXO oraingoz. Zubi-nodoak ez du bere burua gisa iragartzen, nodo oso guztientzako nodo osoa eta trinko guztientzako nodo trinkoa dela itxuraz. Zubiek bi sareak elkarrekin lotzen dituzten arren, benetan norabide bakarrean konektatu behar dituzte: dauden nodo osoetatik hasi eta nodo trinkoetara. Hau posible da transakzio-formatua ez delako aldatu behar, eta nodo trinkoen UTXO frogak baztertu daitezkeelako, beraz, edozein nodo trinkoek era berean transakzioak igorri ditzake sareko partaide guztiei zubi-nodoen parte-hartzerik gabe.

Ondorioa

Utreexo bateria aztertu eta bere prototipoa Rust-en ezarri genuen. Baterian oinarritutako nodoen integrazioa ahalbidetuko duen sare-arkitektura aztertu dugu. Harrapaketa trinkoen abantaila gordetako datuen tamaina da, UTXO multzoaren potentzia logaritmikoki araberakoa dena, eta horrek asko murrizten ditu diskoko espazioaren eta biltegiratze-errendimenduaren eskakizunak halako nodoetarako. Desabantaila frogak transmititzeko nodoen trafiko gehigarria da, baina frogak agregatzeko teknikak (froga batek hainbat elementuren existentzia frogatzen duenean) eta cacheak trafikoa muga onargarrietan mantentzen lagun dezakete.

Erreferentziak:

Iturria: www.habr.com

Utreexo: UTXO Bitcoin asko konprimitzen

Zein da arazoa?

UTXO eta UTXO-multzoa

UTXOrako bateriak

Utreexo

Bateriaren Egitura Logikoa

Elementuak gehitzea

Gehitutako elementuen froga bat sortzea

Elementu baten froga egiaztatzea

Elementuak kentzea

Lehendik dagoen sare batean integratzea

Sare arkitektura

Ondorioa

Gehitu iruzkin berria Idatzi