🥇Utreexo: pag-compress ng maraming UTXO Bitcoin

Hoy Habr!

Sa network ng Bitcoin, ang lahat ng mga node, sa pamamagitan ng pinagkasunduan, ay sumasang-ayon sa isang hanay ng mga UTXO: kung gaano karaming mga barya ang magagamit para sa paggastos, kung kanino eksakto, at sa ilalim ng anong mga kondisyon. Ang set ng UTXO ay ang minimum na hanay ng data na kinakailangan para sa isang validator node, kung wala ito ay hindi mabe-verify ng node ang validity ng mga papasok na transaksyon at ang mga block na naglalaman ng mga ito.

Sa pagsasaalang-alang na ito, ang mga pagtatangka ay ginagawa sa lahat ng posibleng paraan upang bawasan ang nakaimbak na representasyon ng set na ito, upang i-compress ito nang hindi nawawala ang mga garantiya sa seguridad. Ang mas maliit na dami ng naka-imbak na data, mas mababa ang mga kinakailangan sa puwang ng disk ng validator node, na ginagawang mura ang paglulunsad ng validator node, ay nagbibigay-daan sa iyo na palawakin ang network at sa gayon ay mapataas ang katatagan ng network.

Sa post na ito magpo-post kami ng Rust prototype ng isang kamakailang panukala mula sa isang co-author Papel ng Network ng Kidlat, Thaddeus Dryja - Utreexo: isang dynamic na hash-based accumulator na na-optimize para sa Bitcoin UTXO set, na nagbibigay-daan sa pagbabawas ng mga kinakailangan sa espasyo sa disk para sa mga validator node.

Ano ang problema?

Isa sa mga pangmatagalang problema ng Bitcoin ay ang scalability nito. Ang ideya ng "iyong sariling bangko" ay nangangailangan ng mga kalahok sa network na panatilihin ang mga talaan ng lahat ng mga pondong magagamit para magamit. Sa Bitcoin, ang mga magagamit na pondo ay ipinahayag bilang isang set ng mga hindi nagastos na output - isang UTXO-set. Bagama't hindi ito isang partikular na intuitive na representasyon, ito ay kapaki-pakinabang sa mga tuntunin ng pagganap ng pagpapatupad sa isang representasyon kung saan ang bawat "wallet" ay may "balanse" bilang isang hiwalay na entry, at nagdaragdag din ng privacy (hal. CoinJoin).

Mahalagang makilala ang kasaysayan ng mga transaksyon (na tinatawag na blockchain) at ang kasalukuyang estado ng system. Ang kasaysayan ng transaksyon ng Bitcoin ay kasalukuyang sumasakop ng humigit-kumulang 200 GB ng espasyo sa disk, at patuloy na lumalaki. Gayunpaman, ang estado ng system ay mas maliit, sa pagkakasunud-sunod ng 4 GB, at isinasaalang-alang lamang ang katotohanan na ang isang tao ay kasalukuyang nagmamay-ari ng mga barya. Ang dami ng data na ito ay tumataas din sa paglipas ng panahon, ngunit sa isang mas mabagal na rate at kung minsan ay may posibilidad na bumaba (tingnan ang CDPV).

Ang mga light client (SPV) ay nagbibigay ng garantiya sa seguridad sa pangangalakal para sa kakayahang mag-imbak ng walang minimum na estado (UTXO-set) maliban sa mga pribadong key.

UTXO at UTXO-set

Ang UTXO (Unspent Transaction Output) ay ang hindi nagastos na output ng transaksyon, ang dulong punto ng paglalakbay ng bawat Satoshi na inilipat sa mga transaksyon. Ang mga hindi nagastos na output ay nagiging input ng mga bagong transaksyon at sa gayon ay ginagastos (paggastos) at inalis mula sa UTXO-set.

Ang mga bagong UTXO ay palaging nilikha ng mga transaksyon:

mga transaksyon sa coinbase na walang input: lumikha ng mga bagong UTXO kapag nag-isyu ng mga barya ang mga minero
mga regular na transaksyon: lumikha ng mga bagong UTXO habang gumagastos ng isang partikular na hanay ng mga umiiral nang UTXO

Proseso ng pagtatrabaho sa UTXO:

Binibilang ng mga wallet ang bilang ng mga coin na magagamit para sa paggastos (balanse) batay sa halaga ng UTXO na magagamit sa wallet na ito para sa paggastos.

Ang bawat validator node, upang maiwasan ang mga pagtatangka ng dobleng paggastos, ay dapat subaybayan ang set lahat UTXO kapag sinusuri bawat isa mga transaksyon ng bawat isa harangan.

Ang node ay dapat may lohika:

Mga karagdagan sa UTXO-set
Mga pagtanggal mula sa UTXO-set
Sinusuri ang presensya ng isang UTXO sa isang set

May mga paraan upang bawasan ang mga kinakailangan para sa nakaimbak na impormasyon tungkol sa isang set, habang pinapanatili ang kakayahang magdagdag at mag-alis ng mga elemento, suriin at patunayan ang pagkakaroon ng isang elemento sa isang set gamit ang mga cryptographic accumulator.

Mga baterya para sa UTXO

Ang ideya ng paggamit ng mga baterya upang mag-imbak ng maraming UTXO napag-usapan mas maaga.

Ang UTXO-set ay binuo sa mabilisang, sa panahon ng paunang pag-download ng bloke (IBD), na nakaimbak nang buo at permanente, habang nagbabago ang mga nilalaman nito pagkatapos ng pagproseso ng mga transaksyon mula sa bawat bago at tamang bloke ng network. Ang prosesong ito ay nangangailangan ng pag-download ng humigit-kumulang 200 GB ng block data at pag-verify ng daan-daang milyong digital signature. Matapos makumpleto ang proseso ng IBD, ang pangunahing linya ay ang UTXO-set ay sasakupin ng humigit-kumulang 4 GB.

Gayunpaman, sa mga nagtitipon, ang mga patakaran ng pinagkasunduan para sa mga pondo ay binabawasan sa pagpapatunay at pagbuo ng mga cryptographic na patunay, at ang pasanin ng pagsubaybay sa mga magagamit na pondo ay inililipat sa may-ari ng mga pondong iyon, na nagbibigay ng patunay ng kanilang pag-iral at pagmamay-ari.

Ang isang nagtitipon ay maaaring tawaging isang compact na representasyon ng isang set. Ang laki ng nakaimbak na representasyon ay dapat na pare-pareho , o pagtaas ng sublinearly na may paggalang sa cardinality ng set at ang laki ng mismong elemento, halimbawa , kung saan ang n ay ang cardinality ng nakaimbak na set.

Sa kasong ito, dapat payagan ng nagtitipon ang pagbuo ng isang patunay ng pagsasama ng isang elemento sa set (patunay ng pagsasama) at gawing posible na epektibong ma-verify ang patunay na ito.

Ang baterya ay tinatawag pabago-bago kung pinapayagan kang magdagdag ng mga elemento at mag-alis ng mga elemento mula sa isang set.

Ang isang halimbawa ng naturang baterya ay Ang RSA accumulator na iminungkahi ng Boneh, Bunz, Fisch noong Disyembre 2018. Ang nasabing isang nagtitipon ay may pare-parehong laki ng nakaimbak na representasyon, ngunit nangangailangan ng presensya nakabahaging lihim (pinagkakatiwalaang setup). Tinatanggihan ng kinakailangang ito ang pagiging angkop ng naturang accumulator para sa mga walang tiwala na network tulad ng Bitcoin, dahil ang pagtagas ng data sa panahon ng lihim na pagbuo ay maaaring magbigay-daan sa mga umaatake na lumikha ng maling patunay ng pagkakaroon ng isang UTXO, na nanlilinlang sa mga node na may UTXO-set batay sa naturang accumulator.

Utreexo

Ginagawang posible ng disenyo ng Utreexo na iminungkahi ni Thaddeus Dryja na lumikha dinamiko nagtitipon wala pinagkakatiwalaang-setup.

Ang Utreexo ay isang kagubatan ng perpektong binary Mga Puno ng Merkle at ito ay pagbuo ng mga ideyang ipinakita sa Mahusay na asynchronous accumulator para sa distributed pki, pagdaragdag ng kakayahang mag-alis ng mga elemento mula sa isang set.

Logical na Istraktura ng Baterya

Ang mga cell ng baterya ay nakaayos sa isang kagubatan ng perpektong binary tree. Ang mga puno ay inayos ayon sa taas. Ang representasyong ito ay pinili bilang ang pinaka-visual at nagbibigay-daan sa iyo upang mailarawan ang pagsasama ng mga puno sa panahon ng mga operasyon sa baterya.

Sinabi ng may-akda na dahil ang lahat ng mga puno sa kagubatan ay perpekto, ang kanilang taas ay ipinahayag bilang isang kapangyarihan ng dalawa, tulad ng anumang natural na bilang ay maaaring kinakatawan bilang isang kabuuan ng mga kapangyarihan ng dalawa. Alinsunod dito, ang anumang hanay ng mga dahon ay maaaring ipangkat sa mga binary tree, at sa lahat ng kaso, ang pagdaragdag ng bagong elemento ay nangangailangan ng kaalaman. tungkol lamang sa mga node ng ugat ng mga nakaimbak na puno.

Kaya, ang nakaimbak na representasyon ng Utreexo accumulator ay isang listahan ng mga root node (Merkle root), at hindi ang buong kagubatan ng mga puno.

Katawanin natin ang listahan ng mga elemento ng ugat bilang Vec<Option<Hash>>. Opsyonal na uri Option<Hash> ay nagpapahiwatig na ang elemento ng ugat ay maaaring nawawala, na nangangahulugan na walang puno na may naaangkop na taas sa nagtitipon.

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

Pagdaragdag ng mga elemento

Una, ilarawan natin ang pag-andar parent(), na kinikilala ang parent node para sa dalawang ibinigay na elemento.

parent() function

Dahil gumagamit kami ng mga Merkle tree, ang magulang ng bawat isa sa dalawang node ay isang node na nag-iimbak ng hash ng concatenation ng mga hash ng mga child node:

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

Sinabi ng may-akda na upang maiwasan ang mga pag-atake na inilarawan nina Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, at Sebastien Zimmer sa
Pangalawang preimage na pag-atake sa mga dithered hash function, bilang karagdagan sa dalawang hash, ang taas sa loob ng puno ay dapat ding idagdag sa concatenation.

Habang nagdaragdag ka ng mga elemento sa nagtitipon, kailangan mong subaybayan kung aling mga elemento ng ugat ang binago. Sa pamamagitan ng pagsunod sa landas ng pagpapalit ng mga elemento ng ugat para sa bawat elemento na iyong idaragdag, maaari kang bumuo ng isang patunay ng pagkakaroon ng mga elementong ito sa ibang pagkakataon.

Subaybayan ang mga pagbabago habang idinaragdag mo ang mga ito

Upang subaybayan ang mga pagbabagong ginawa, ideklara natin ang istraktura Update, na mag-iimbak ng data tungkol sa mga pagbabago sa node.

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

Upang magdagdag ng elemento sa baterya, kailangan mo:

Gumawa ng isang hanay ng mga basket ng mga elemento ng ugat new_roots at ilagay ang mga umiiral na elemento ng ugat doon, isa para sa bawat bucket:

Kodigo

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

Idagdag ang mga elementong idaragdag (array insertions) sa unang cart new_roots[0]:

Kodigo

new_roots[0].extend_from_slice(insertions);

Pagsamahin ang mga item na idinagdag sa unang basket sa iba pa:
- Para sa lahat ng cart na may higit sa isang item:
  1. Kumuha ng dalawang elemento mula sa dulo ng basket, kalkulahin ang kanilang magulang, alisin ang parehong mga elemento
  2. Idagdag ang kinakalkula na magulang sa susunod na cart

Kodigo

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

Ilipat ang mga elemento ng ugat mula sa mga bin patungo sa nagreresultang array ng accumulator

Kodigo

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

Paglikha ng isang patunay para sa mga idinagdag na elemento

Katibayan ng pagsasama ng cell sa baterya (Proof) ay magsisilbing Merkle Path, na binubuo ng isang chain ProofStep. Kung ang landas ay walang patutunguhan, kung gayon ang patunay ay hindi tama.

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

Gamit ang impormasyong nakuha kanina kapag nagdadagdag ng elemento (structure Update), maaari kang lumikha ng patunay na may naidagdag na elemento sa baterya. Upang gawin ito, dumaan tayo sa talahanayan ng mga pagbabagong ginawa at idagdag ang bawat hakbang sa landas ni Merkle, na pagkatapos ay magsisilbing patunay:

Kodigo

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 ng paglikha ng isang patunay

Sinusuri ang patunay para sa isang elemento

Ang pagsuri sa patunay ng pagsasama ng isang elemento ay bumababa sa pagsunod sa landas ng Merkle hanggang sa humantong ito sa isang umiiral na elemento ng 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 ng pagsuri sa patunay para sa A

Pag-alis ng mga item

Upang alisin ang isang cell mula sa isang baterya, dapat kang magbigay ng wastong ebidensya na ang cell ay naroroon. Gamit ang data mula sa patunay, posibleng kalkulahin ang mga bagong elemento ng ugat ng nagtitipon kung saan ang ibinigay na patunay ay hindi na magiging totoo.

Ang algorithm ay ang mga sumusunod:

Bilang karagdagan, nag-aayos kami ng isang hanay ng mga walang laman na basket na tumutugma sa mga puno ng Merkle na may taas na katumbas ng kapangyarihan ng dalawa mula sa index ng basket
Nagpasok kami ng mga elemento mula sa mga hakbang ng landas ng Merkle sa mga basket; ang basket index ay katumbas ng bilang ng kasalukuyang hakbang
Inalis namin ang elemento ng ugat kung saan patungo ang landas mula sa patunay
Tulad ng pagdaragdag, kinakalkula namin ang mga bagong elemento ng ugat sa pamamagitan ng pagsasama-sama ng mga elemento mula sa mga basket nang pares at paglipat ng resulta ng unyon sa susunod na basket

Kodigo

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 ng pag-alis ng elementong "A":

Pagsasama sa isang umiiral na network

Gamit ang iminungkahing accumulator, maiiwasan ng mga node ang paggamit ng DB upang iimbak ang lahat ng UTXO habang nagagawa pa ring baguhin ang UTXO-set. Gayunpaman, lumitaw ang problema sa pagtatrabaho sa ebidensya.

Tawagan natin ang validator node na gumagamit ng UTXO accumulator compact (compact-state node), at ang validator na walang accumulator ay kumpleto (buong node). Ang pagkakaroon ng dalawang klase ng mga node ay lumilikha ng problema para sa pagsasama ng mga ito sa isang network, dahil ang mga compact node ay nangangailangan ng patunay ng pagkakaroon ng mga UTXO, na ginugugol sa mga transaksyon, habang ang mga buong node ay hindi. Kung ang lahat ng network node ay hindi sabay-sabay at sa isang coordinated na paraan ay lumipat sa paggamit ng Utreexo, pagkatapos ay ang mga compact node ay maiiwan at hindi magagawang gumana sa Bitcoin network.

Upang malutas ang problema ng pagsasama ng mga compact node sa network, iminungkahi na ipakilala ang isang karagdagang klase ng mga node - mga tulay. Ang bridge node ay isang kumpletong node na nag-iimbak din ng Utreexo na baterya at power-on proof para sa lahat UTXO mula sa UTXO-set. Kinakalkula ng mga tulay ang mga bagong hash at ina-update ang accumulator at mga patunay habang dumarating ang mga bagong bloke ng mga transaksyon. Ang pagpapanatili at pag-update ng accumulator at proofs ay hindi nagpapataw ng karagdagang computational load sa naturang mga node. Ang mga tulay ay nagsasakripisyo ng espasyo sa disk: kailangang panatilihing maayos ang mga bagay hashes, kumpara sa mga hash para sa mga compact node, kung saan ang n ay ang kapangyarihan ng set ng UTXO.

Arkitektura ng network

Ginagawang posible ng mga tulay na unti-unting magdagdag ng mga compact node sa network nang hindi binabago ang software ng mga umiiral na node. Ang mga buong node ay gumagana tulad ng dati, na namamahagi ng mga transaksyon at mga bloke sa kanilang mga sarili. Ang mga bridge node ay mga full node na nag-iimbak ng data ng baterya ng Utreexo at isang hanay ng mga patunay sa pagsasama lahat UTXO sa ngayon. Ang bridge node ay hindi nag-a-advertise sa sarili nito, na nagpapanggap na isang buong node para sa lahat ng mga full node at isang compact na node para sa lahat ng mga compact. Bagama't pinagsama-sama ng mga tulay ang magkabilang network, kailangan lang talaga nilang ikonekta ang mga ito sa isang direksyon: mula sa mga kasalukuyang full node hanggang sa mga compact node. Posible ito dahil hindi kailangang baguhin ang format ng transaksyon, at maaaring itapon ang mga UTXO proof para sa mga compact node, kaya ang anumang compact node ay maaaring mag-broadcast ng mga transaksyon sa lahat ng kalahok sa network nang walang partisipasyon ng mga bridge node.

Konklusyon

Tiningnan namin ang baterya ng Utreexo at ipinatupad ang prototype nito sa Rust. Tiningnan namin ang arkitektura ng network na magpapahintulot sa pagsasama ng mga node na nakabatay sa baterya. Ang bentahe ng mga compact catch ay ang laki ng nakaimbak na data, na depende sa logarithmically sa kapangyarihan ng hanay ng mga UTXO, na lubos na binabawasan ang mga kinakailangan para sa puwang sa disk at pagganap ng imbakan para sa mga naturang node. Ang kawalan ay ang karagdagang trapiko ng node para sa pagpapadala ng mga patunay, ngunit ang mga diskarte sa pagsasama-sama ng ebidensya (kapag pinatunayan ng isang patunay ang pagkakaroon ng ilang elemento) at ang pag-cache ay makakatulong na panatilihin ang trapiko sa loob ng mga katanggap-tanggap na limitasyon.

sanggunian:

Pinagmulan: www.habr.com

Utreexo: pag-compress ng maraming UTXO Bitcoin

Ano ang problema?

UTXO at UTXO-set

Mga baterya para sa UTXO

Utreexo

Logical na Istraktura ng Baterya

Pagdaragdag ng mga elemento

Paglikha ng isang patunay para sa mga idinagdag na elemento

Sinusuri ang patunay para sa isang elemento

Pag-alis ng mga item

Pagsasama sa isang umiiral na network

Arkitektura ng network

Konklusyon

Magdagdag ng komento Kanselahin ang sumagot