🥇Utreexo: pag-compress sa daghang UTXO Bitcoin

Hoy Habr!

Sa network sa Bitcoin, ang tanan nga mga node, pinaagi sa consensus, nagkauyon sa usa ka hugpong sa mga UTXO: pila ka mga sensilyo ang magamit alang sa paggasto, kang kinsa eksakto, ug sa ilalum sa unsang mga kondisyon. Ang set sa UTXO mao ang minimum nga set sa datos nga gikinahanglan alang sa validator node, nga kung wala ang node dili mapamatud-an ang balido sa umaabot nga mga transaksyon ug ang mga bloke nga adunay sulod niini.

Niining bahina, ang mga pagsulay gihimo sa tanan nga posible nga paagi aron makunhuran ang gitipig nga representasyon sa kini nga set, aron ma-compress kini nga wala mawala ang mga garantiya sa seguridad. Ang mas gamay nga gidaghanon sa gitipigan nga datos, mas ubos ang gikinahanglan nga disk space sa validator node, nga naghimo sa paglansad sa usa ka validator node nga barato, nagtugot kanimo sa pagpalapad sa network ug sa ingon nagdugang sa kalig-on sa network.

Sa kini nga post mag-post kami usa ka Rust prototype sa usa ka bag-o nga sugyot gikan sa usa ka kauban nga tagsulat Papel sa Lightning Network, Thaddeus Dryja - Utreexo: usa ka dinamikong hash-based accumulator nga gi-optimize alang sa Bitcoin UTXO set, nga nagtugot sa pagkunhod sa mga kinahanglanon sa espasyo sa disk alang sa mga validator node.

Unsay problema?

Usa sa mga perennial nga problema sa Bitcoin mao ang scalability niini. Ang ideya sa "imong kaugalingon nga bangko" nanginahanglan sa mga partisipante sa network nga magtipig mga rekord sa tanan nga mga pondo nga magamit. Sa Bitcoin, ang magamit nga mga pondo gipahayag ingon usa ka hugpong sa wala magamit nga mga output - usa ka UTXO-set. Samtang kini dili usa ka partikular nga intuitive nga representasyon, kini mapuslanon sa mga termino sa pagpatuman sa performance sa usa ka representasyon diin ang matag "pitaka" adunay "balanse" isip usa ka bulag nga entry, ug usab nagdugang sa privacy (eg. CoinJoin).

Importante ang pag-ila tali sa kasaysayan sa mga transaksyon (gitawag nga blockchain) ug sa kasamtangan nga kahimtang sa sistema. Ang kasaysayan sa transaksyon sa Bitcoin sa pagkakaron nag-okupar sa mga 200 GB sa disk space, ug nagpadayon sa pagtubo. Bisan pa, ang estado sa sistema labi ka gamay, sa pagkasunud-sunod nga 4 GB, ug gikonsiderar lamang ang kamatuoran nga adunay usa nga karon adunay tag-iya nga mga sensilyo. Ang gidaghanon sa kini nga datos usab nagdugang sa paglabay sa panahon, apan sa labi ka hinay nga rate ug usahay mahimo pa nga mokunhod (tan-awa ang CDPV).

Ang mga light clients (SPVs) naggarantiya sa seguridad sa pamatigayon alang sa abilidad sa pagtipig nga walay minimum nga estado (UTXO-set) gawas sa pribadong mga yawe.

UTXO ug UTXO-set

Ang UTXO (Unspent Transaction Output) mao ang wala magasto nga transaksyon nga output, ang katapusan nga punto sa panaw sa matag Satoshi nga gibalhin sa mga transaksyon. Ang wala magasto nga mga output nahimong input sa bag-ong mga transaksyon ug sa ingon gigasto (paggasto) ug gikuha gikan sa UTXO-set.

Ang mga bag-ong UTXO kanunay gihimo pinaagi sa mga transaksyon:

mga transaksyon sa coinbase nga walay mga input: paghimo og bag-ong mga UTXO kung ang mga minero mag-isyu og mga sensilyo
regular nga mga transaksyon: paghimo ug bag-ong mga UTXO samtang naggasto ug usa ka set sa kasamtangan nga mga UTXO

Proseso sa pagtrabaho kauban ang UTXO:

Ang mga pitaka nag-ihap sa gidaghanon sa mga sensilyo nga magamit alang sa paggasto (balanse) base sa kantidad sa UTXO nga magamit niini nga pitaka alang sa paggasto.

Ang matag validator node, aron malikayan ang doble nga pagsulay sa paggasto, kinahanglan nga bantayan ang set sa tanan UTXO kung magsusi matag usa mga transaksyon matag usa block.

Ang node kinahanglan adunay lohika:

Mga pagdugang sa UTXO-set
Mga pagtangtang gikan sa UTXO-set
Pagsusi sa presensya sa usa ka UTXO sa usa ka set

Adunay mga paagi aron makunhuran ang mga kinahanglanon alang sa gitipigan nga kasayuran bahin sa usa ka set, samtang gipadayon ang katakus sa pagdugang ug pagtangtang sa mga elemento, susihon ug pamatud-an ang paglungtad sa usa ka elemento sa usa ka set gamit ang cryptographic accumulators.

Baterya alang sa UTXO

Ang ideya sa paggamit sa mga baterya sa pagtipig daghang mga UTXO gihisgutan sa sayo pa.

Ang UTXO-set gitukod sa langaw, sa panahon sa inisyal nga block download (IBD), gitipigan sa bug-os ug permanente, samtang ang mga sulod niini mausab human sa pagproseso sa mga transaksyon gikan sa matag bag-o ug husto nga block sa network. Kini nga proseso nagkinahanglan sa pag-download sa gibana-bana nga 200 GB sa block data ug pag-verify sa gatusan ka milyon nga digital nga mga pirma. Pagkahuman sa proseso sa IBD, ang hinungdan mao nga ang UTXO-set mag-okupar sa mga 4 GB.

Bisan pa, uban sa mga accumulator, ang mga lagda sa consensus alang sa mga pundo gipakunhod ngadto sa pag-verify ug pagmugna sa mga cryptographic nga mga pruweba, ug ang palas-anon sa pagsubay sa anaa nga mga pundo gibalhin ngadto sa tag-iya sa maong mga pundo, nga naghatag og pamatuod sa ilang paglungtad ug pagpanag-iya.

Ang usa ka accumulator mahimong tawgon nga usa ka compact representation sa usa ka set. Ang gidak-on sa gitipigan nga representasyon kinahanglan nga kanunay , o pagdugang sa sublinearly bahin sa kardinalidad sa set ug ang gidak-on sa elemento mismo, pananglitan , diin ang n mao ang cardinality sa gitipigan nga set.

Sa kini nga kaso, ang accumulator kinahanglan nga motugot sa pagmugna og usa ka pruweba sa paglakip sa usa ka elemento sa set (inclusion proof) ug himoong posible nga epektibong mapamatud-an kini nga pruweba.

Gitawag ang baterya dinamiko kung nagtugot kanimo sa pagdugang sa mga elemento ug pagtangtang sa mga elemento gikan sa usa ka set.

Usa ka pananglitan sa ingon nga baterya mao ang Ang RSA accumulator nga gisugyot ni Boneh, Bunz, Fisch kaniadtong Disyembre 2018. Ang ingon nga accumulator adunay kanunay nga gidak-on sa gitipigan nga representasyon, apan nagkinahanglan sa presensya gipaambit nga sekreto (gisaligan nga setup). Kini nga kinahanglanon nagpanghimakak sa paggamit sa ingon nga usa ka accumulator alang sa walay pagsalig nga mga network sama sa Bitcoin, tungod kay ang data leakage sa panahon sa sekreto nga henerasyon makatugot sa mga tig-atake sa paghimo og bakak nga pamatuod sa pagkaanaa sa usa ka UTXO, paglimbong sa mga node nga adunay usa ka UTXO-set base sa ingon nga accumulator.

Utreexo

Ang disenyo sa Utreexo nga gisugyot ni Thaddeus Dryja nagpaposible sa paghimo dinamiko baterya nga walay kasaligan-setup.

Ang Utreexo usa ka lasang sa hingpit nga binary Mga Kahoy nga Merkle ug usa ka kalamboan sa mga ideya nga gipresentar sa Episyente nga asynchronous accumulators alang sa gipang-apod-apod nga pki, pagdugang sa abilidad sa pagtangtang sa mga elemento gikan sa usa ka set.

Baterya Logical Structure

Ang mga selula sa baterya gihan-ay sa usa ka lasang sa maayo nga binary nga mga kahoy. Ang mga kahoy gi-order sumala sa gitas-on. Kini nga representasyon gipili ingon nga labing biswal ug nagtugot kanimo sa paghanduraw sa paghiusa sa mga kahoy sa panahon sa operasyon sa baterya.

Ang tagsulat nag-ingon nga tungod kay ang tanan nga mga kahoy sa lasang mao ang sulundon, ang ilang gitas-on gipahayag ingon sa usa ka gahum sa duha, sama sa bisan unsa nga natural nga numero mahimong representahan ingon nga usa ka sumada sa gahum sa duha. Tungod niini, ang bisan unsang hugpong sa mga dahon mahimong ma-grupo sa binary nga mga punoan, ug sa tanan nga mga kaso, ang pagdugang usa ka bag-ong elemento nanginahanglan kahibalo. mahitungod lamang sa mga ugat sa mga gitipigan nga mga kahoy.

Busa, ang gitipigan nga representasyon sa Utreexo accumulator usa ka lista sa mga ugat nga node (Merkle root), ug dili ang tibuok kalasangan sa mga kahoy.

Atong irepresentar ang lista sa mga elemento sa gamut ingon Vec<Option<Hash>>. Opsyonal nga tipo Option<Hash> nagpakita nga ang gamut nga elemento mahimong nawala, nga nagpasabot nga walay kahoy nga adunay tukma nga gitas-on sa accumulator.

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

Pagdugang mga elemento

Una, atong ihulagway ang function parent(), nga nag-ila sa parent node alang sa duha ka gihatag nga elemento.

parent() function

Tungod kay gigamit namon ang mga kahoy nga Merkle, ang ginikanan sa matag usa sa duha nga mga node usa ka node nga nagtipig sa hash sa concatenation sa mga hash sa mga node sa bata:

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

Ang tagsulat nag-ingon nga aron mapugngan ang mga pag-atake nga gihulagway ni Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, ug Sebastien Zimmer sa
Ikaduha nga pag-atake sa preimage sa dithered hash functions, dugang sa duha ka hash, ang gitas-on sa sulod sa kahoy kinahanglan usab nga idugang sa concatenation.

Samtang imong idugang ang mga elemento sa accumulator, kinahanglan nimo nga bantayan kung unsang mga elemento sa ugat ang giusab. Pinaagi sa pagsunod sa dalan sa pagbag-o sa mga elemento sa gamut alang sa matag elemento nga imong idugang, mahimo ka nga makahimo sa ulahi usa ka pruweba sa presensya niini nga mga elemento.

Pagsubay sa mga pagbag-o samtang gidugang nimo kini

Aron masubay ang mga pagbag-o nga nahimo, ipahayag nato ang istruktura Update, nga magtipig sa datos bahin sa mga pagbag-o sa node.

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

Aron makadugang usa ka elemento sa baterya, kinahanglan nimo:

Paghimo usa ka han-ay sa mga bukag sa mga elemento sa ugat new_roots ug ibutang ang naglungtad nga mga elemento sa ugat didto, usa alang sa matag balde:

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

Idugang ang mga elemento nga idugang (array insertions) ngadto sa unang kariton new_roots[0]:

code

new_roots[0].extend_from_slice(insertions);

Paghiusa sa mga butang nga gidugang sa unang basket uban sa uban:
- Para sa tanang cart nga adunay labaw sa usa ka butang:
  1. Kuhaa ang duha ka elemento gikan sa tumoy sa bukag, kuwentaha ang ilang ginikanan, kuhaa ang duha ka elemento
  2. Idugang ang kalkulado nga ginikanan sa sunod nga kariton

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

Ibalhin ang mga elemento sa gamut gikan sa mga bins ngadto sa resulta nga accumulator array

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

Paghimo usa ka pruweba alang sa dugang nga mga elemento

Pamatuod sa paglakip sa cell sa baterya (Proof) magsilbi nga Merkle Path, nga naglangkob sa usa ka kadena ProofStep. Kung ang dalan wala’y padulngan, nan ang pamatuod dili husto.

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

Gigamit ang impormasyon nga nakuha sa sayo pa sa pagdugang sa usa ka elemento (structure Update), makahimo ka og pruweba nga adunay elemento nga gidugang sa baterya. Aron mahimo kini, moagi kami sa lamesa sa mga pagbag-o nga gihimo ug idugang ang matag lakang sa agianan ni Merkle, nga sa ulahi magsilbi nga pruweba:

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

Proseso sa paghimo og pruweba

Pagsusi sa pruweba alang sa usa ka elemento

Ang pagsusi sa pamatuod sa paglakip sa usa ka elemento nagsukad sa pagsunod sa agianan sa Merkle hangtod nga kini modala sa usa ka naglungtad nga elemento sa ugat:

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

Biswal:

Proseso sa pagsusi sa pruweba alang sa A

Pagtangtang sa mga butang

Aron makuha ang usa ka cell gikan sa usa ka baterya, kinahanglan ka maghatag ug balido nga ebidensya nga ang cell naa didto. Gamit ang datos gikan sa pruweba, posible nga makalkulo ang bag-ong mga elemento sa ugat sa accumulator diin ang gihatag nga pruweba dili na tinuod.

Ang algorithm mao ang mosunud:

Sama sa dugang, nag-organisar kami og usa ka hugpong sa walay sulod nga mga bukag nga katumbas sa mga punoan sa Merkle nga adunay gitas-on nga katumbas sa gahum sa duha gikan sa indeks sa basket.
Gisulud namon ang mga elemento gikan sa mga lakang sa agianan sa Merkle sa mga bukag; ang indeks sa basket parehas sa gidaghanon sa kasamtangan nga lakang
Gikuha namo ang gamut nga elemento diin ang agianan gikan sa pamatuod nagpadulong
Sama sa pagdugang, among gikalkula ang bag-ong mga elemento sa ugat pinaagi sa paghiusa sa mga elemento gikan sa mga bukag nga pares ug pagbalhin sa resulta sa unyon sa sunod nga basket

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

Ang proseso sa pagtangtang sa elemento "A":

Paghiusa sa usa ka kasamtangan nga network

Gamit ang gisugyot nga accumulator, ang mga node makalikay sa paggamit sa DB aron tipigan ang tanang UTXOs samtang makahimo pa sa pag-usab sa UTXO-set. Bisan pa, ang problema sa pagtrabaho uban ang ebidensya mitungha.

Tawgon nato ang validator node nga naggamit sa UTXO accumulator compact (compact-state node), ug ang validator nga walay accumulator mao kompleto (bug-os nga node). Ang paglungtad sa duha ka mga klase sa mga node nagmugna og problema sa pag-integrate niini ngadto sa usa ka network, tungod kay ang mga compact node nagkinahanglan og pruweba sa paglungtad sa mga UTXO, nga gigasto sa mga transaksyon, samtang ang mga full node wala. Kung ang tanan nga mga node sa network dili dungan ug sa usa ka koordinado nga paagi magbalhin sa paggamit sa Utreexo, nan ang mga compact node mabiyaan ug dili makalihok sa network sa Bitcoin.

Aron masulbad ang problema sa paghiusa sa mga compact node sa network, gisugyot nga ipaila ang usa ka dugang nga klase sa mga node - mga tulay. Ang bridge node usa ka kompleto nga node nga nagtipig usab sa Utreexo nga baterya ug power-on nga pruweba para sa sa tanan UTXO gikan sa UTXO-set. Gikalkulo sa mga tulay ang bag-ong mga hash ug gi-update ang accumulator ug mga pruweba sa pag-abot sa bag-ong mga bloke sa mga transaksyon. Ang pagmintinar ug pag-update sa accumulator ug mga pruweba wala magpahamtang ug dugang nga computational load sa maong mga node. Ang mga tulay nagsakripisyo sa disk space: kinahanglan nga huptan nga organisado ang mga butang hash, itandi sa hash alang sa mga compact node, diin ang n mao ang gahum sa UTXO set.

Arkitektura sa network

Ang mga tulay nagpaposible nga anam-anam nga idugang ang mga compact node sa network nga dili usbon ang software sa mga naa na nga node. Ang bug-os nga mga node naglihok sama kaniadto, nag-apod-apod sa mga transaksyon ug mga bloke sa ilang kaugalingon. Ang mga node sa tulay mga bug-os nga node nga nagtipig sa datos sa baterya sa Utreexo ug usa ka hugpong sa mga ebidensya sa paglakip sa tanan UTXO sa pagkakaron. Ang bridge node wala mag-anunsyo sa iyang kaugalingon sa ingon, nagpakaaron-ingnon nga usa ka bug-os nga node alang sa tanan nga puno nga node ug usa ka compact node alang sa tanan nga mga compact. Bisan tuod ang mga taytayan nagkonektar sa duha ka network nga magkauban, sila sa pagkatinuod kinahanglan lamang nga magkonektar kanila sa usa ka direksyon: gikan sa kasamtangan nga puno nga mga node ngadto sa mga compact node. Posible kini tungod kay ang format sa transaksyon dili kinahanglan nga usbon, ug ang mga pruweba sa UTXO alang sa mga compact node mahimong ilabay, mao nga ang bisan unsang compact node parehas nga magsibya sa mga transaksyon sa tanan nga mga partisipante sa network nga wala’y pag-apil sa mga bridge node.

konklusyon

Gitan-aw namon ang baterya sa Utreexo ug gipatuman ang prototype niini sa Rust. Gitan-aw namon ang arkitektura sa network nga magtugot sa paghiusa sa mga node nga nakabase sa baterya. Ang bentaha sa mga compact catches mao ang gidak-on sa gitipigan nga datos, nga nagdepende sa logarithmically sa gahum sa set sa UTXOs, nga makapakunhod pag-ayo sa mga kinahanglanon alang sa disk space ug storage performance alang sa maong mga node. Ang disbentaha mao ang dugang nga trapiko sa node alang sa pagpasa sa mga pruweba, apan ang mga teknik sa pagtipon sa ebidensya (kung ang usa ka pruweba nagpamatuod sa paglungtad sa daghang mga elemento) ug ang pag-cache makatabang sa pagpadayon sa trapiko sulod sa madawat nga mga limitasyon.

mga pakisayran:

Source: www.habr.com

Utreexo: pag-compress sa daghang UTXO Bitcoin

Unsay problema?

UTXO ug UTXO-set

Baterya alang sa UTXO

Utreexo

Baterya Logical Structure

Pagdugang mga elemento

Paghimo usa ka pruweba alang sa dugang nga mga elemento

Pagsusi sa pruweba alang sa usa ka elemento

Pagtangtang sa mga butang

Paghiusa sa usa ka kasamtangan nga network

Arkitektura sa network

konklusyon

Idugang sa usa ka comment Отменить ответ