Pozdravljeni, Habr!
V omrežju Bitcoin se vsa vozlišča s soglasjem dogovorijo o naboru UTXO: koliko kovancev je na voljo za porabo, komu natančno in pod kakšnimi pogoji. Nabor UTXO je minimalni nabor podatkov, potrebnih za vozlišče validatorja, brez katerega vozlišče ne bo moglo preveriti veljavnosti dohodnih transakcij in blokov, ki jih vsebujejo.
V zvezi s tem se poskuša na vse možne načine zmanjšati shranjeno predstavitev tega niza, ga stisniti brez izgube varnostnih jamstev. Manjši kot je obseg shranjenih podatkov, nižje je zahteva vozlišča validatorja po prostoru na disku, zaradi česar je zagon vozlišča validatorja poceni, vam omogoča razširitev omrežja in s tem povečanje stabilnosti omrežja.
V tej objavi bomo objavili Rust prototip nedavnega predloga soavtorja , - , ki omogoča zmanjšanje zahtev po prostoru na disku za vozlišča validatorja.
Kaj je problem?
Eden od večnih problemov Bitcoina je njegova razširljivost. Zamisel o "lastni banki" od udeležencev omrežja zahteva, da vodijo evidenco vseh sredstev, ki so na voljo za uporabo. V bitcoinu so razpoložljiva sredstva izražena kot nabor neporabljenih rezultatov – nabor UTXO. Čeprav to ni posebno intuitivna predstavitev, je koristna v smislu izvedbene zmogljivosti v primerjavi s predstavitvijo, v kateri ima vsaka "denarnica" "stanje" kot ločen vnos, dodaja pa tudi zasebnost (npr. ).
Pomembno je razlikovati med zgodovino transakcij (kar imenujemo blockchain) in trenutnim stanjem sistema. Zgodovina transakcij Bitcoin trenutno zaseda okoli 200 GB prostora na disku in še naprej raste. Vendar pa je sistemsko stanje veliko manjše, reda velikosti 4 GB, in upošteva le dejstvo, da ima nekdo trenutno v lasti kovance. Obseg teh podatkov se sčasoma prav tako povečuje, vendar veliko počasneje in se včasih celo zmanjšuje (glejte CDPV).
Lahki odjemalci (SPV) trgujejo z varnostnimi jamstvi za zmožnost shranjevanja nobenega minimalnega stanja (UTXO-set), razen zasebnih ključev.
UTXO in UTXO-set
UTXO (Unspent Transaction Output) je neporabljen izhod transakcije, končna točka potovanja vsakega Satoshija, prenesenega v transakcijah. Neporabljeni izhodi postanejo vhodi novih transakcij in se tako porabijo (porabijo) ter odstranijo iz nabora UTXO.
Novi UTXO so vedno ustvarjeni s transakcijami:
- transakcije coinbase brez vnosov: ustvarite nove UTXO, ko rudarji izdajo kovance
- redne transakcije: ustvarite nove UTXO, medtem ko porabite določen nabor obstoječih UTXO
Postopek dela z UTXO:
Denarnice štejejo število kovancev, ki so na voljo za porabo (stanje) glede na količino UTXO, ki je na voljo tej denarnici za porabo.
Vsako vozlišče validatorja mora nadzorovati nabor, da prepreči dvojne poskuse porabe Vse UTXO pri preverjanju vsak transakcije vsakega blok.
Vozlišče mora imeti logiko:
- Dodatki k UTXO-setu
- Izbrisi iz nabora UTXO
- Preverjanje prisotnosti enega samega UTXO v nizu
Obstajajo načini za zmanjšanje zahtev po shranjenih informacijah o nizu, hkrati pa ohraniti možnost dodajanja in odstranjevanja elementov, preverjanja in dokazovanja obstoja elementa v nizu z .
Baterije za UTXO
Zamisel o uporabi baterij za shranjevanje več UTXO .
UTXO-set je zgrajen sproti, med začetnim prenosom bloka (IBD), shranjen v celoti in trajno, medtem ko se njegova vsebina spremeni po obdelavi transakcij iz vsakega novega in pravilnega bloka omrežja. Ta postopek zahteva prenos približno 200 GB blokovnih podatkov in preverjanje več sto milijonov digitalnih podpisov. Po končanem postopku IBD bo nabor UTXO zasedel približno 4 GB.
Pri akumulatorjih pa se pravila konsenza za sklade zmanjšajo na preverjanje in generiranje kriptografskih dokazov, breme sledenja razpoložljivih sredstev pa se prevali na lastnika teh sredstev, ki predloži dokazila o njihovem obstoju in lastništvu.
Akumulator lahko imenujemo kompaktna predstavitev množice. Velikost shranjene predstavitve mora biti konstantna , ali sublinearno naraščati glede na kardinalnost niza in velikost samega elementa, na primer , kjer je n kardinalnost shranjenega niza.
Akumulator naj bi v tem primeru omogočal generiranje dokaza o vključenosti elementa v množico (inclusion proof) in omogočal učinkovito preverjanje tega dokaza.
Baterija se imenuje dinamično if omogoča dodajanje in odstranjevanje elementov iz nabora.
Primer takšne baterije bi bil . Tak akumulator ima konstantno velikost shranjene reprezentacije, vendar zahteva prisotnost skupna skrivnost (zaupanja vredna nastavitev). Ta zahteva izniči uporabnost takšnega akumulatorja za nezaupljiva omrežja, kot je Bitcoin, saj lahko uhajanje podatkov med skrivnim ustvarjanjem omogoči napadalcem, da ustvarijo lažne dokaze o obstoju UTXO in zavedejo vozlišča z nizom UTXO, ki temelji na takem akumulatorju.
Utreexo
Dizajn Utreexo, ki ga je predlagal Thaddeus Dryja, omogoča ustvarjanje dinamičen akumulator brez zaupanja vredna nastavitev.
Utreexo je gozd popolne binarnosti in je razvoj idej, predstavljenih v , ki doda možnost odstranjevanja elementov iz niza.
Logična struktura baterije
Baterijske celice so razporejene v gozdu idealnih binarnih dreves. Drevesa so razvrščena po višini. Ta predstavitev je bila izbrana kot najbolj vizualna in omogoča vizualizacijo združevanja dreves med delovanjem baterije.
Avtor ugotavlja, da ker so vsa drevesa v gozdu idealna, je njihova višina izražena kot potenca dvojke, tako kot je vsako naravno število mogoče predstaviti kot vsota potenc dvojke. V skladu s tem je mogoče katerikoli niz listov združiti v binarna drevesa in v vseh primerih dodajanje novega elementa zahteva znanje samo o koreninskih vozliščih shranjenih dreves.
Tako je shranjena predstavitev akumulatorja Utreexo seznam korenskih vozlišč (Merkle root), in ne celotnega gozda dreves.
Predstavimo seznam korenskih elementov kot Vec<Option<Hash>>. Izbirni tip Option<Hash> označuje, da korenski element morda manjka, kar pomeni, da v akumulatorju ni drevesa z ustrezno višino.
/// 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],
}
}
}Dodajanje elementov
Najprej opišemo funkcijo parent(), ki prepozna nadrejeno vozlišče za dva dana elementa.
funkcija parent().
Ker uporabljamo drevesa Merkle, je nadrejeno vozlišče vsakega od obeh vozlišč eno vozlišče, ki hrani zgoščeno vrednost veriženja zgoščenih vrednosti podrejenih vozlišč:
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[..])
}Avtor ugotavlja, da je za preprečitev napadov, ki so jih opisali Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir in Sebastien Zimmer v
, poleg dveh zgoščenih vrednosti je treba veriženju dodati tudi višino znotraj drevesa.
Ko dodate elemente v akumulator, morate spremljati, kateri korenski elementi so spremenjeni. Če sledite poti spreminjanja korenskih elementov za vsak element, ki ga dodate, lahko pozneje ustvarite dokaz o prisotnosti teh elementov.
Sledite spremembam, ko jih dodate
Če želite slediti opravljenim spremembam, deklarirajmo strukturo Update, ki bo shranjeval podatke o spremembah vozlišča.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Če želite bateriji dodati element, potrebujete:
- Ustvarite niz košaric korenskih elementov
new_rootsin tja postavite obstoječe korenske elemente, enega za vsako vedro:
Koda:
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);
}- Dodajte elemente, ki jih želite dodati (matrika
insertions) v prvi vozičeknew_roots[0]:
Koda:
new_roots[0].extend_from_slice(insertions);- Predmete, dodane v prvo košarico, združite z ostalimi:
- Za vse vozičke z več kot enim artiklom:
- Vzemite dva elementa s konca košare, izračunajte njunega starša, odstranite oba elementa
- Dodajte izračunani nadrejeni element v naslednji voziček
- Za vse vozičke z več kot enim artiklom:
Koda:
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 });
}
}- Premaknite korenske elemente iz zabojnikov v nastalo polje akumulatorja
Koda:
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]);
}
}Izdelava dokaza za dodane elemente
Dokaz o vključitvi celice v baterijo (Proof) bo služila kot Merklova pot, sestavljena iz verige ProofStep. Če pot ne vodi nikamor, potem je dokaz napačen.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Uporaba prej pridobljenih informacij pri dodajanju elementa (struktura Update), lahko ustvarite dokaz, da je bil bateriji dodan element. Da bi to naredili, gremo skozi tabelo opravljenih sprememb in dodamo vsak korak na Merklovo pot, ki bo kasneje služila kot dokaz:
Koda:
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
}
}Postopek izdelave dokaza
Preverjanje dokaza za element
Preverjanje dokazila o vključitvi elementa se zmanjša na sledenje poti Merkle, dokler ne pripelje do obstoječega korenskega elementa:
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, ¤t_parent)
} else {
parent(¤t_parent, &s.hash)
};
}
current_parent == expected
} else {
false
}
}Vizualno:
Postopek preverjanja dokaza za A
Odstranjevanje predmetov
Če želite odstraniti celico iz baterije, morate zagotoviti veljaven dokaz, da je celica tam. S pomočjo podatkov iz dokaza je možno izračunati nove korenske elemente akumulatorja, za katere podani dokaz ne bo več resničen.
Algoritem je naslednji:
- Tako kot pri seštevanju organiziramo nabor praznih košar, ki ustrezajo Merklovim drevesom z višino, ki je enaka potenci dvojke iz indeksa košare
- V košare vstavimo elemente iz stopnic Merklejeve poti; indeks košarice je enak številki trenutnega koraka
- Odstranimo korenski element, do katerega vodi pot iz dokaza
- Tako kot pri seštevanju nove korenske elemente izračunamo tako, da združimo elemente iz košaric v pare in premaknemo rezultat unije v naslednjo košarico
Koda:
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;
}
}Postopek odstranjevanja elementa "A":
Integracija v obstoječe omrežje
Z uporabo predlaganega akumulatorja se lahko vozlišča izognejo uporabi baze podatkov za shranjevanje vseh UTXO-jev, medtem ko lahko še vedno spreminjajo nabor UTXO. Pojavi pa se problem dela z dokazi.
Pokličimo validatorsko vozlišče, ki uporablja akumulator UTXO kompakten (vozlišče kompaktnega stanja), validator brez akumulatorja pa je dokončana (polno vozlišče). Obstoj dveh razredov vozlišč povzroča težave pri njihovem povezovanju v eno samo omrežje, saj kompaktna vozlišča zahtevajo dokazilo o obstoju UTXO-jev, ki se porabijo v transakcijah, polna vozlišča pa ne. Če vsa omrežna vozlišča ne bodo istočasno in usklajeno prešla na uporabo Utreexo, bodo kompaktna vozlišča zaostala in ne bodo mogla delovati v omrežju Bitcoin.
Za rešitev problema vključevanja kompaktnih vozlišč v omrežje je predlagana uvedba dodatnega razreda vozlišč - mostovi. Premostitveno vozlišče je popolno vozlišče, ki hrani tudi baterijo Utreexo in dokazilo o vklopu za Vse UTXO iz UTXO-seta. Bridges izračuna nove zgoščene vrednosti in posodobi akumulator in dokazila, ko prispejo novi bloki transakcij. Vzdrževanje in posodabljanje akumulatorja in dokazov takim vozliščem ne nalaga dodatne računske obremenitve. Mostovi žrtvujejo prostor na disku: stvari morajo biti organizirane zgoščencev v primerjavi z zgoščene vrednosti za kompaktna vozlišča, kjer je n moč nabora UTXO.
Arhitektura omrežja
Mostovi omogočajo postopno dodajanje kompaktnih vozlišč v omrežje brez spreminjanja programske opreme obstoječih vozlišč. Polna vozlišča delujejo kot prej in med seboj razdeljujejo transakcije in bloke. Vozlišča mostov so polna vozlišča, ki dodatno shranjujejo podatke o bateriji Utreexo in nabor dokazil o vključitvi za Vse UTXO zaenkrat. Mostno vozlišče se ne oglašuje kot tako, temveč se pretvarja, da je polno vozlišče za vsa polna vozlišča in kompaktno vozlišče za vsa kompaktna. Čeprav mostovi povezujejo obe omrežji skupaj, ju morajo dejansko povezati le v eno smer: od obstoječih polnih vozlišč do kompaktnih vozlišč. To je mogoče, ker formata transakcije ni treba spreminjati, dokazila UTXO za kompaktna vozlišča pa je mogoče zavreči, tako da lahko katero koli kompaktno vozlišče podobno oddaja transakcije vsem udeležencem omrežja brez sodelovanja premostitvenih vozlišč.
Zaključek
Ogledali smo si baterijo Utreexo in implementirali njen prototip v Rust. Ogledali smo si omrežno arhitekturo, ki bo omogočala integracijo baterijskih vozlišč. Prednost kompaktnih ulovov je velikost shranjenih podatkov, ki je logaritemsko odvisna od moči niza UTXO, kar močno zmanjša zahteve po prostoru na disku in zmogljivosti shranjevanja za takšna vozlišča. Pomanjkljivost je dodatni promet vozlišč za prenos dokazov, vendar lahko tehnike združevanja dokazov (ko en dokaz dokazuje obstoj več elementov) in predpomnjenje pomagajo ohranjati promet v sprejemljivih mejah.
reference:
- -
Vir: www.habr.com