🥇Utreexo: kubana UTXO nyingi za Bitcoin

Habari Habr!

Katika mtandao wa Bitcoin, nodes zote, kwa njia ya makubaliano, zinakubaliana juu ya seti ya UTXOs: ni sarafu ngapi zinapatikana kwa matumizi, kwa nani hasa, na chini ya hali gani. Seti ya UTXO ni seti ya chini ya data inayohitajika kwa node ya uthibitishaji, bila ambayo node haitaweza kuthibitisha uhalali wa shughuli zinazoingia na vitalu vyenye.

Katika suala hili, majaribio yanafanywa kwa kila njia iwezekanavyo ili kupunguza uwakilishi uliohifadhiwa wa kuweka hii, ili kuipunguza bila kupoteza dhamana za usalama. Kiasi kidogo cha data iliyohifadhiwa, chini ya mahitaji ya nafasi ya disk ya node ya uthibitishaji, ambayo inafanya kuzindua node ya uthibitishaji nafuu, inakuwezesha kupanua mtandao na hivyo kuongeza utulivu wa mtandao.

Katika chapisho hili tutachapisha mfano wa Rust wa pendekezo la hivi majuzi kutoka kwa mwandishi mwenza Karatasi ya Mtandao wa Umeme, Thaddeus Dryja - Utreexo: kikusanyaji chenye nguvu cha msingi wa heshi kilichoboreshwa kwa seti ya Bitcoin UTXO, ambayo inaruhusu kupunguza mahitaji ya nafasi ya diski kwa nodi za uthibitishaji.

Shida ni nini?

Mojawapo ya shida za kudumu za Bitcoin imekuwa ugumu wake. Wazo la "benki yako mwenyewe" linahitaji washiriki wa mtandao kuweka rekodi za fedha zote zinazopatikana kwa matumizi. Katika Bitcoin, pesa zinazopatikana zinaonyeshwa kama seti ya matokeo ambayo hayajatumika - seti ya UTXO. Ingawa huu si uwakilishi angavu hasa, ni wa manufaa katika suala la utendaji wa utekelezaji juu ya uwakilishi ambapo kila "mkoba" una "salio" kama ingizo tofauti, na pia huongeza faragha (k.m. Sarafu).

Ni muhimu kutofautisha kati ya historia ya shughuli (kile kinachoitwa blockchain) na hali ya sasa ya mfumo. Historia ya muamala wa Bitcoin kwa sasa inachukua takriban 200 GB ya nafasi ya diski, na inaendelea kukua. Hata hivyo, hali ya mfumo ni ndogo zaidi, kwa utaratibu wa GB 4, na inazingatia tu ukweli kwamba mtu kwa sasa anamiliki sarafu. Kiasi cha data hii pia huongezeka kwa muda, lakini kwa kiwango cha polepole zaidi na wakati mwingine hata huelekea kupungua (angalia CDPV).

Wateja nyepesi (SPVs) huhakikisha usalama wa biashara kwa uwezo wa kuhifadhi hakuna hali ya chini kabisa (seti ya UTXO) isipokuwa funguo za kibinafsi.

UTXO na UTXO-set

UTXO (Pato la Muamala Usiotumika) ni pato la muamala ambalo halijatumika, sehemu ya mwisho ya safari ya kila Satoshi inayohamishwa katika miamala. Matokeo ambayo hayajatumika huwa pembejeo za shughuli mpya na kwa hivyo hutumiwa (kutumia) na kuondolewa kutoka kwa seti ya UTXO.

UTXO mpya huundwa kila wakati na shughuli:

miamala ya coinbase bila pembejeo: tengeneza UTXO mpya wakati wachimbaji wanatoa sarafu
shughuli za kawaida: tengeneza UTXO mpya huku ukitumia seti fulani ya UTXO zilizopo

Mchakato wa kufanya kazi na UTXO:

Pochi huhesabu idadi ya sarafu zinazopatikana kwa matumizi (salio) kulingana na kiasi cha UTXO kinachopatikana kwenye pochi hii kwa matumizi.

Kila nodi ya kithibitishaji, ili kuzuia majaribio ya kutumia mara mbili, lazima ifuatilie seti Kila UTXO wakati wa kuangalia kila mmoja shughuli kila mmoja kuzuia.

Nodi lazima iwe na mantiki:

Nyongeza kwa UTXO-set
Ufutaji kutoka kwa UTXO-set
Kuangalia uwepo wa UTXO moja katika seti

Kuna njia za kupunguza mahitaji ya habari iliyohifadhiwa juu ya seti, wakati wa kudumisha uwezo wa kuongeza na kuondoa vitu, angalia na uthibitishe uwepo wa kipengee kwenye seti kwa kutumia. vikusanyaji vya kriptografia.

Betri za UTXO

Wazo la kutumia betri kuhifadhi UTXO nyingi ilijadiliwa mapema.

Seti ya UTXO imejengwa juu ya kuruka, wakati wa upakuaji wa block ya awali (IBD), iliyohifadhiwa kwa ukamilifu na kwa kudumu, wakati yaliyomo yake yanabadilika baada ya shughuli za usindikaji kutoka kwa kila block mpya na sahihi ya mtandao. Mchakato huu unahitaji kupakua takriban GB 200 za data ya kuzuia na kuthibitisha mamia ya mamilioni ya sahihi za dijitali. Baada ya mchakato wa IBD kukamilika, msingi ni kwamba UTXO-set itachukua kuhusu 4 GB.

Hata hivyo, pamoja na wakusanyaji, sheria za makubaliano ya fedha zimepunguzwa kwa uthibitisho na kizazi cha uthibitisho wa cryptographic, na mzigo wa kufuatilia fedha zilizopo huhamishiwa kwa mmiliki wa fedha hizo, ambaye hutoa uthibitisho wa kuwepo kwao na umiliki.

Mkusanyiko unaweza kuitwa uwakilishi wa kompakt wa seti. Saizi ya uwakilishi iliyohifadhiwa lazima iwe sawa , au ongeza chini ya mstari kwa heshima na kardinali ya seti na saizi ya kitu chenyewe, kwa mfano. , ambapo n ni kardinali ya seti iliyohifadhiwa.

Katika kesi hii, mkusanyiko unapaswa kuruhusu kuzalisha uthibitisho wa kuingizwa kwa kipengele katika seti (ushahidi wa kuingizwa) na kufanya iwezekanavyo kuthibitisha uthibitisho huu kwa ufanisi.

Betri inaitwa nguvu ikiwa inakuwezesha kuongeza vipengele na kuondoa vipengele kutoka kwa seti.

Mfano wa betri kama hiyo itakuwa Kikusanyaji cha RSA kilichopendekezwa na Boneh, Bunz, Fisch mnamo Desemba 2018. Mkusanyiko kama huo una saizi ya mara kwa mara ya uwakilishi uliohifadhiwa, lakini inahitaji uwepo siri ya pamoja (mpangilio unaoaminika). Sharti hili linakanusha utumiaji wa kikusanyaji kama hicho kwa mitandao isiyoaminika kama Bitcoin, kwani uvujaji wa data wakati wa uzalishaji wa siri unaweza kuruhusu washambuliaji kuunda uthibitisho wa uwongo wa uwepo wa UTXO, nodi za kudanganya na seti ya UTXO kulingana na kikusanyaji kama hicho.

Utreexo

Muundo wa Utreexo uliopendekezwa na Thaddeus Dryja hufanya iwezekanavyo kuunda nguvu аккумулятор bila usanidi wa kuaminika.

Utreexo ni msitu wa binary kamili Miti ya Merkle na ni maendeleo ya mawazo yaliyowasilishwa ndani Vikusanyaji vya asynchronous vyema kwa pki iliyosambazwa, kuongeza uwezo wa kuondoa vipengele kutoka kwa seti.

Muundo wa Kimantiki wa Betri

Seli za betri zimepangwa katika msitu wa miti bora ya binary. Miti imeagizwa kwa urefu. Uwakilishi huu ulichaguliwa kama unaoonekana zaidi na hukuruhusu kuona jinsi miti inavyounganishwa wakati wa operesheni kwenye betri.

Mwandishi anabainisha kuwa kwa kuwa miti yote msituni ni bora, urefu wake unaonyeshwa kama nguvu ya mbili, kama vile nambari yoyote ya asili inaweza kuwakilishwa kama jumla ya nguvu mbili. Ipasavyo, seti yoyote ya majani inaweza kuunganishwa katika miti ya binary, na katika hali zote, kuongeza kipengele kipya inahitaji ujuzi tu kuhusu nodes za mizizi ya miti iliyohifadhiwa.

Kwa hivyo, uwakilishi uliohifadhiwa wa mkusanyiko wa Utreexo ni orodha ya nodi za mizizi (mzizi wa Merkle), na sio msitu mzima wa miti.

Wacha tuwakilishe orodha ya vitu vya mizizi kama Vec<Option<Hash>>. Aina ya hiari Option<Hash> inaonyesha kuwa kipengele cha mizizi kinaweza kukosa, ambayo ina maana kwamba hakuna mti wenye urefu unaofaa katika mkusanyiko.

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

Kuongeza vipengele

Kwanza, hebu tuelezee kazi parent(), ambayo inatambua nodi ya mzazi kwa vipengele viwili vilivyotolewa.

parent() kazi

Kwa kuwa tunatumia miti ya Merkle, mzazi wa kila nodi mbili ni nodi moja ambayo huhifadhi heshi ya muunganisho wa heshi za nodi za watoto:

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

Mwandishi anabainisha kuwa kuzuia mashambulizi yaliyoelezwa na Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, na Sebastien Zimmer katika.
Mashambulizi ya pili ya taswira ya utendakazi wa heshi iliyoharibika, pamoja na hashes mbili, urefu ndani ya mti unapaswa pia kuongezwa kwa kuunganisha.

Unapoongeza vipengele kwenye mkusanyiko, unahitaji kufuatilia ni vipengele vipi vya mizizi vinabadilishwa. Kwa kufuata njia ya kubadilisha vipengele vya mizizi kwa kila kipengele unachoongeza, unaweza baadaye kujenga uthibitisho wa kuwepo kwa vipengele hivi.

Fuatilia mabadiliko unapoyaongeza

Ili kufuatilia mabadiliko yaliyofanywa, hebu tutangaze muundo Update, ambayo itahifadhi data kuhusu mabadiliko ya nodi.

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

Ili kuongeza kipengee kwenye betri, unahitaji:

Unda safu ya vikapu vya vipengele vya mizizi new_roots na weka vitu vya mizizi vilivyopo hapo, moja kwa kila ndoo:

Kanuni

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

Ongeza vitu vya kuongezwa (safu insertions) kwa mkokoteni wa kwanza new_roots[0]:

Kanuni

new_roots[0].extend_from_slice(insertions);

Unganisha vitu vilivyoongezwa kwenye kikapu cha kwanza na vingine:
- Kwa mikokoteni yote iliyo na zaidi ya bidhaa moja:
  1. Kuchukua vipengele viwili kutoka mwisho wa kikapu, uhesabu mzazi wao, uondoe vipengele vyote viwili
  2. Ongeza mzazi aliyekokotolewa kwenye rukwama inayofuata

Kanuni

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

Hamisha vipengee vya mizizi kutoka kwa mapipa hadi safu ya kikusanyaji inayotokana

Kanuni

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

Kuunda uthibitisho wa vipengele vilivyoongezwa

Uthibitisho wa kuingizwa kwa seli kwenye betri (Proof) itatumika kama Njia ya Merkle, inayojumuisha mnyororo ProofStep. Ikiwa njia haielekei popote, basi uthibitisho sio sahihi.

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

Kutumia habari iliyopatikana hapo awali wakati wa kuongeza kipengee (muundo Update), unaweza kuunda uthibitisho kwamba kipengele kimeongezwa kwenye betri. Ili kufanya hivyo, tunapitia jedwali la mabadiliko yaliyofanywa na kuongeza kila hatua kwenye njia ya Merkle, ambayo baadaye itatumika kama uthibitisho:

Kanuni

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

Mchakato wa kuunda uthibitisho

Kuangalia uthibitisho wa kipengele

Kukagua uthibitisho wa ujumuishaji wa kipengee hupungua hadi kufuata njia ya Merkle hadi kuelekeze kwa kipengele cha mizizi kilichopo:

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

Kuonekana:

Mchakato wa kuangalia uthibitisho wa A

Kuondoa vitu

Ili kuondoa seli kutoka kwa betri, lazima utoe ushahidi halali kwamba seli iko. Kutumia data kutoka kwa uthibitisho, inawezekana kuhesabu vipengele vipya vya mizizi ya mkusanyiko ambayo uthibitisho uliotolewa hautakuwa wa kweli tena.

Algorithm ni kama ifuatavyo:

Kama ilivyo kwa kuongeza, tunapanga seti ya vikapu tupu vinavyolingana na miti ya Merkle yenye urefu sawa na nguvu ya mbili kutoka kwa index ya kikapu.
Tunaingiza vipengele kutoka kwa hatua za njia ya Merkle kwenye vikapu; index ya kikapu ni sawa na idadi ya hatua ya sasa
Tunaondoa kipengele cha mizizi ambayo njia kutoka kwa uthibitisho inaongoza
Kama ilivyo kwa kuongeza, tunahesabu vipengele vipya vya mizizi kwa kuchanganya vipengele kutoka kwa vikapu kwa jozi na kuhamisha matokeo ya muungano hadi kikapu kinachofuata.

Kanuni

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

Mchakato wa kuondoa kipengele "A":

Kuunganishwa kwenye mtandao uliopo

Kwa kutumia kikusanyaji kilichopendekezwa, nodi zinaweza kuzuia kutumia DB kuhifadhi UTXO zote huku zikiwa bado na uwezo wa kubadilisha UTXO-seti. Hata hivyo, tatizo la kufanya kazi na ushahidi hutokea.

Wacha tuite nodi ya kihalalishaji inayotumia kikusanyaji cha UTXO kompakt (nodi ya hali ya kompakt), na kihalalisha bila kikusanyaji ni kamili (nodi kamili). Uwepo wa madarasa mawili ya nodes hujenga tatizo la kuunganisha kwenye mtandao mmoja, kwani nodes za compact zinahitaji uthibitisho wa kuwepo kwa UTXOs, ambazo hutumiwa katika shughuli, wakati nodes kamili hazifanyi. Ikiwa nodi zote za mtandao hazifanyi wakati huo huo na kwa njia iliyoratibiwa kubadili kutumia Utreexo, basi nodi za kompakt zitaachwa nyuma na hazitaweza kufanya kazi kwenye mtandao wa Bitcoin.

Ili kutatua shida ya kuunganisha nodi za kompakt kwenye mtandao, inapendekezwa kuanzisha darasa la ziada la nodi - madaraja. Nodi ya daraja ni nodi kamili ambayo pia huhifadhi betri ya Utreexo na uthibitisho wa kuwasha Kila UTXO kutoka UTXO-set. Madaraja hukokotoa heshi mpya na kusasisha kikusanyaji na uthibitisho kadiri vizuizi vipya vya miamala vinapowasili. Kudumisha na kusasisha kikusanyaji na uthibitisho hautoi mzigo wa ziada wa hesabu kwenye nodi kama hizo. Madaraja hutoa nafasi ya diski: haja ya kuweka mambo kwa mpangilio heshi, ikilinganishwa na heshi kwa nodi za kompakt, ambapo n ni nguvu ya seti ya UTXO.

Usanifu wa mtandao

Madaraja hufanya iwezekanavyo kuongeza hatua kwa hatua nodes za compact kwenye mtandao bila kubadilisha programu ya nodes zilizopo. Nodi kamili hufanya kazi kama hapo awali, kusambaza miamala na vizuizi kati yao wenyewe. Nodi za daraja ni nodi kamili ambazo huhifadhi data ya betri ya Utreexo na seti ya vithibitisho vya kujumuishwa Kila UTXO kwa sasa. Nodi ya daraja haijitangazi kama hivyo, ikijifanya kuwa nodi kamili kwa nodi zote kamili na nodi ya kompakt kwa zote zilizoshikamana. Ingawa madaraja huunganisha mitandao yote miwili pamoja, kwa kweli yanahitaji tu kuiunganisha katika mwelekeo mmoja: kutoka nodi kamili zilizopo hadi nodi za kompakt. Hii inawezekana kwa sababu muundo wa shughuli hauhitaji kubadilishwa, na uthibitisho wa UTXO kwa nodi za kompakt zinaweza kutupwa, kwa hivyo nodi yoyote ya kompakt inaweza vile vile kutangaza shughuli kwa washiriki wote wa mtandao bila ushiriki wa nodi za daraja.

Hitimisho

Tuliangalia betri ya Utreexo na kutekeleza mfano wake huko Rust. Tuliangalia usanifu wa mtandao ambao utaruhusu kuunganishwa kwa nodi za betri. Faida ya upatikanaji wa compact ni ukubwa wa data iliyohifadhiwa, ambayo inategemea logarithmically juu ya nguvu ya seti ya UTXOs, ambayo inapunguza sana mahitaji ya nafasi ya disk na utendaji wa kuhifadhi kwa nodes hizo. Ubaya ni trafiki ya ziada ya nodi ya kusambaza uthibitisho, lakini mbinu za kujumlisha ushahidi (wakati uthibitisho mmoja unathibitisha kuwepo kwa vipengele kadhaa) na uakibishaji unaweza kusaidia kuweka trafiki ndani ya mipaka inayokubalika.

marejeo:

Chanzo: mapenzi.com

Utreexo: kubana UTXO Bitcoin nyingi

Shida ni nini?

UTXO na UTXO-set

Betri za UTXO

Utreexo

Muundo wa Kimantiki wa Betri

Kuongeza vipengele

Kuunda uthibitisho wa vipengele vilivyoongezwa

Kuangalia uthibitisho wa kipengele

Kuondoa vitu

Kuunganishwa kwenye mtandao uliopo

Usanifu wa mtandao

Hitimisho

Kuongeza maoni Kufuta kujibu