Hej Habr!
U Bitcoin mreži svi čvorovi se putem konsenzusa slažu oko skupa UTXO-a: koliko je kovanica dostupno za trošenje, kome točno i pod kojim uvjetima. UTXO skup je minimalni skup podataka potrebnih za validator čvor, bez kojeg čvor neće moći provjeriti valjanost dolaznih transakcija i blokova koji ih sadrže.
U tom smislu, pokušava se na svaki mogući način smanjiti pohranjeni prikaz ovog skupa, komprimirati ga bez gubitka sigurnosnih jamstava. Što je manja količina pohranjenih podataka, manji su zahtjevi za prostorom na disku čvora validatora, što čini pokretanje čvora validatora jeftinijim, omogućuje vam proširenje mreže i time povećava stabilnost mreže.
U ovom postu objavit ćemo Rust prototip nedavnog prijedloga koautora , - , što omogućuje smanjenje zahtjeva za prostorom na disku za čvorove validatora.
U čemu je problem?
Jedan od vječitih problema Bitcoina je njegova skalabilnost. Ideja "vlastite banke" zahtijeva od sudionika mreže da vode evidenciju o svim raspoloživim sredstvima. U Bitcoinu su raspoloživa sredstva izražena kao skup nepotrošenih rezultata - UTXO-set. Iako ovo nije posebno intuitivan prikaz, koristan je u smislu izvedbe implementacije u odnosu na prikaz u kojem svaki "novčanik" ima "saldo" kao zaseban unos, a također dodaje privatnost (npr. ).
Važno je razlikovati povijest transakcija (ono što se naziva blockchain) i trenutno stanje sustava. Povijest Bitcoin transakcija trenutno zauzima oko 200 GB prostora na disku i nastavlja rasti. Međutim, stanje sustava puno je manje, reda veličine 4 GB, i uzima u obzir samo činjenicu da netko trenutno posjeduje kovanice. Količina ovih podataka također se povećava tijekom vremena, ali puno sporije, a ponekad čak ima tendenciju smanjenja (vidi CDPV).
Laki klijenti (SPV) trguju jamstvima sigurnosti za mogućnost pohranjivanja minimalnog stanja (UTXO-set) osim privatnih ključeva.
UTXO i UTXO-set
UTXO (Unspent Transaction Output) je nepotrošen izlaz transakcije, krajnja točka putovanja svakog Satoshija prenesenog u transakcijama. Nepotrošeni izlazi postaju ulazi novih transakcija i stoga se troše (troše) i uklanjaju iz UTXO-seta.
Novi UTXO uvijek se stvaraju transakcijama:
- coinbase transakcije bez unosa: kreirajte nove UTXO kada rudari izdaju kovanice
- redovite transakcije: kreirajte nove UTXO-e dok trošite određeni skup postojećih UTXO-a
Proces rada s UTXO:
Novčanici broje broj kovanica dostupnih za potrošnju (stanje) na temelju količine UTXO koja je dostupna ovom novčaniku za potrošnju.
Svaki čvor validatora, kako bi se spriječili dvostruki pokušaji trošenja, mora nadzirati skup Sve UTXO prilikom provjere svaki transakcije svaki blok.
Čvor mora imati logiku:
- Dodaci UTXO-setu
- Brisanja iz UTXO-seta
- Provjera prisutnosti jednog UTXO u setu
Postoje načini da se smanje zahtjevi za pohranjenim informacijama o skupu, uz zadržavanje mogućnosti dodavanja i uklanjanja elemenata, provjere i dokazivanja postojanja elementa u skupu pomoću .
Baterije za UTXO
Ideja korištenja baterija za pohranjivanje više UTXO-a .
UTXO-set se gradi u hodu, tijekom preuzimanja početnog bloka (IBD), pohranjuje se u cijelosti i trajno, dok se njegov sadržaj mijenja nakon obrade transakcija iz svakog novog i ispravnog bloka mreže. Ovaj postupak zahtijeva preuzimanje približno 200 GB blok podataka i provjeru stotina milijuna digitalnih potpisa. Nakon dovršetka IBD procesa, krajnji cilj je da će UTXO-set zauzeti oko 4 GB.
Međutim, kod akumulatora se pravila konsenzusa za sredstva svode na provjeru i generiranje kriptografskih dokaza, a teret praćenja raspoloživih sredstava prebacuje se na vlasnika tih sredstava, koji daje dokaz o njihovom postojanju i vlasništvu.
Akumulator se može nazvati kompaktnom reprezentacijom skupa. Veličina pohranjenog prikaza mora biti konstantna , ili rasti sublinearno s obzirom na kardinalnost skupa i veličinu samog elementa, na primjer , gdje je n kardinalitet pohranjenog skupa.
U tom slučaju, akumulator bi trebao omogućiti generiranje dokaza o uključivanju elementa u skup (inclusion proof) i omogućiti učinkovitu provjeru tog dokaza.
Baterija se zove dinamičan if vam omogućuje dodavanje i uklanjanje elemenata iz skupa.
Primjer takve baterije bio bi . Takav akumulator ima konstantnu veličinu pohranjene reprezentacije, ali zahtijeva prisutnost zajednička tajna (pouzdano postavljanje). Ovaj zahtjev negira primjenjivost takvog akumulatora za mreže bez povjerenja poput Bitcoina, budući da curenje podataka tijekom tajnog generiranja može omogućiti napadačima stvaranje lažnog dokaza o postojanju UTXO-a, zavaravajući čvorove s UTXO-setom temeljenim na takvom akumulatoru.
Utreexo
Utreexo dizajn koji je predložio Thaddeus Dryja omogućuje stvaranje dinamičan baterija bez pouzdana postavka.
Utreexo je šuma savršene binarnosti i predstavlja razvoj ideja predstavljenih u , dodajući mogućnost uklanjanja elemenata iz skupa.
Logička struktura baterije
Baterijske ćelije raspoređene su u šumi idealnih binarnih stabala. Stabla su poredana po visini. Ovaj prikaz je odabran kao najvizualniji i omogućuje vizualizaciju spajanja stabala tijekom rada na bateriji.
Autor napominje da, budući da su sva stabla u šumi idealna, njihova se visina izražava kao potencija dvojke, kao što se bilo koji prirodni broj može prikazati kao zbroj potencija dvojke. U skladu s tim, bilo koji skup listova može se grupirati u binarna stabla, au svim slučajevima dodavanje novog elementa zahtijeva znanje samo o korijenskim čvorovima pohranjenih stabala.
Dakle, pohranjeni prikaz Utreexo akumulatora je popis korijenskih čvorova (Merkleov korijen), a ne cijelu šumu drveća.
Predstavimo listu korijenskih elemenata kao Vec<Option<Hash>>. Izborna vrsta Option<Hash> označava da korijenski element možda nedostaje, što znači da u akumulatoru nema stabla odgovarajuće visine.
/// 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],
}
}
}Dodavanje elemenata
Prvo, opišimo funkciju parent(), koji prepoznaje nadređeni čvor za dva dana elementa.
parent() funkcija
Budući da koristimo Merkleova stabla, roditelj svakog od dva čvora je jedan čvor koji pohranjuje hash ulančanih hashova podređenih čvorova:
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[..])
}Autor napominje da bi se spriječili napadi koje su opisali Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir i Sebastien Zimmer u
, osim dva hasha, ulančavanju treba dodati i visinu unutar stabla.
Dok dodajete elemente u akumulator, morate pratiti koji se korijenski elementi mijenjaju. Slijedeći put mijenjanja korijenskih elemenata za svaki element koji dodate, kasnije možete konstruirati dokaz prisutnosti tih elemenata.
Pratite promjene dok ih dodajete
Da bismo pratili učinjene promjene, deklarirajmo strukturu Update, koji će pohraniti podatke o promjenama čvora.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Da biste bateriji dodali element, potrebno vam je:
- Napravite niz košarica korijenskih elemenata
new_rootsi tamo postavite postojeće korijenske elemente, po jedan za svaku kantu:
Šifra
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 koji se dodaju (niz
insertions) u prva kolicanew_roots[0]:
Šifra
new_roots[0].extend_from_slice(insertions);- Spojite stavke dodane u prvu košaru s ostalima:
- Za sva kolica s više od jednog artikla:
- Uzmite dva elementa s kraja košare, izračunajte njihovog roditelja, uklonite oba elementa
- Dodajte izračunati roditelj u sljedeću košaricu
- Za sva kolica s više od jednog artikla:
Šifra
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 });
}
}- Premjestite korijenske elemente iz spremnika u rezultirajuće polje akumulatora
Šifra
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]);
}
}Izrada dokaza za dodane elemente
Dokaz o uključivanju ćelije u bateriju (Proof) služit će kao Merkleov put, koji se sastoji od lanca ProofStep. Ako put ne vodi nikamo, onda je dokaz netočan.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Korištenje ranije dobivenih informacija prilikom dodavanja elementa (strukture Update), možete stvoriti dokaz da je bateriji dodan element. Da bismo to učinili, prolazimo kroz tablicu napravljenih promjena i dodajemo svaki korak Merkleovom putu, što će kasnije poslužiti kao dokaz:
Šifra
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
}
}Proces izrade dokaza
Provjera dokaza za element
Provjera dokaza uključivanja elementa svodi se na praćenje Merkleove staze sve dok ne dovede do postojećeg korijenskog 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:
Proces provjere dokaza za A
Uklanjanje stavki
Da biste uklonili ćeliju iz baterije, morate pružiti valjani dokaz da je ćelija tamo. Pomoću podataka iz dokaza moguće je izračunati nove korijenske elemente akumulatora za koje navedeni dokaz više neće biti istinit.
Algoritam je sljedeći:
- Kao i kod zbrajanja, organiziramo skup praznih košara koje odgovaraju Merkleovim stablima s visinom jednakom potenciji broja dva iz indeksa košare
- U košare umetnemo elemente iz stepenica Merkleove staze; indeks košarice jednak je broju trenutnog koraka
- Uklanjamo korijenski element do kojeg vodi put iz dokaza
- Kao i kod zbrajanja, nove korijenske elemente izračunavamo kombiniranjem elemenata iz košarica u parovima i premještanjem rezultata unije u sljedeću košaricu
Šifra
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;
}
}Postupak uklanjanja elementa "A":
Integracija u postojeću mrežu
Korištenjem predloženog akumulatora, čvorovi mogu izbjeći korištenje DB-a za pohranjivanje svih UTXO-ova dok još uvijek mogu mijenjati UTXO-set. Međutim, javlja se problem rada s dokazima.
Pozovimo čvor validatora koji koristi UTXO akumulator kompaktan (compact-state node), a validator bez akumulatora je potpun (puni čvor). Postojanje dviju klasa čvorova stvara problem za njihovu integraciju u jednu mrežu, jer kompaktni čvorovi zahtijevaju dokaz postojanja UTXO-a koji se troše u transakcijama, dok puni čvorovi ne zahtijevaju. Ako se svi mrežni čvorovi istovremeno i koordinirano ne prebace na korištenje Utreexo-a, tada će kompaktni čvorovi biti zaostali i neće moći raditi na Bitcoin mreži.
Kako bi se riješio problem integracije kompaktnih čvorova u mrežu, predlaže se uvođenje dodatne klase čvorova - mostovi. Premosni čvor je potpuni čvor koji također pohranjuje Utreexo bateriju i dokaz o uključivanju Sve UTXO iz UTXO-seta. Bridges izračunava nove hashove i ažurira akumulator i dokaze kako pristižu novi blokovi transakcija. Održavanje i ažuriranje akumulatora i dokaza ne nameće dodatno računalno opterećenje takvim čvorovima. Mostovi žrtvuju prostor na disku: potrebno je organizirati stvari hash, u usporedbi s hashovi za kompaktne čvorove, gdje je n snaga UTXO skupa.
Mrežna arhitektura
Mostovi omogućuju postupno dodavanje kompaktnih čvorova u mrežu bez mijenjanja softvera postojećih čvorova. Puni čvorovi rade kao i prije, međusobno raspodjeljujući transakcije i blokove. Bridge čvorovi su puni čvorovi koji dodatno pohranjuju Utreexo podatke o bateriji i skup dokaza uključivanja za Sve UTXO za sada. Mostni čvor se ne reklamira kao takav, pretvarajući se da je puni čvor za sve pune čvorove i kompaktni čvor za sve kompaktne. Iako mostovi povezuju obje mreže zajedno, oni ih zapravo trebaju povezati samo u jednom smjeru: od postojećih punih čvorova do kompaktnih čvorova. To je moguće jer se format transakcije ne mora mijenjati, a UTXO dokazi za kompaktne čvorove mogu se odbaciti, tako da svaki kompaktni čvor može na sličan način emitirati transakcije svim sudionicima mreže bez sudjelovanja premosnih čvorova.
Zaključak
Pogledali smo Utreexo bateriju i implementirali njen prototip u Rust. Pogledali smo mrežnu arhitekturu koja će omogućiti integraciju čvorova temeljenih na baterijama. Prednost kompaktnih zahvata je veličina pohranjenih podataka, koja logaritamski ovisi o snazi skupa UTXO-ova, što uvelike smanjuje zahtjeve za prostorom na disku i performansama pohrane za takve čvorove. Nedostatak je dodatni promet čvorova za prijenos dokaza, ali tehnike agregacije dokaza (kada jedan dokaz dokazuje postojanje nekoliko elemenata) i predmemorija mogu pomoći u održavanju prometa unutar prihvatljivih granica.
reference:
- -
Izvor: www.habr.com