Čau Habr!
V bitcoinovej sieti sa všetky uzly na základe konsenzu dohodnú na súbore UTXO: koľko mincí je k dispozícii na míňanie, komu presne a za akých podmienok. Sada UTXO je minimálny súbor údajov požadovaných pre uzol validátora, bez ktorého uzol nebude môcť overiť platnosť prichádzajúcich transakcií a blokov, ktoré ich obsahujú.
V tomto ohľade sa všemožne pokúšajú zmenšiť uloženú reprezentáciu tejto sady, komprimovať ju bez straty bezpečnostných záruk. Čím menší je objem uložených dát, tým menšie sú požiadavky na miesto na disku uzla validátora, čo robí spustenie uzla validátora lacným, umožňuje rozširovať sieť a tým zvyšovať stabilitu siete.
V tomto príspevku uverejníme prototyp hrdze nedávneho návrhu od spoluautora , - , čo umožňuje znížiť požiadavky na diskový priestor pre uzly validátora.
Aký je problém?
Jedným z trvalých problémov Bitcoinu je jeho škálovateľnosť. Myšlienka „vašej vlastnej banky“ vyžaduje, aby účastníci siete viedli záznamy o všetkých dostupných finančných prostriedkoch. V bitcoine sú dostupné prostriedky vyjadrené ako súbor nevyčerpaných výstupov – súbor UTXO. Aj keď toto nie je obzvlášť intuitívna reprezentácia, je výhodná z hľadiska výkonu implementácie oproti reprezentácii, v ktorej má každá „peňaženka“ „zostatok“ ako samostatný záznam a tiež pridáva súkromie (napr. ).
Je dôležité rozlišovať medzi históriou transakcií (to, čo sa nazýva blockchain) a aktuálnym stavom systému. História bitcoinových transakcií v súčasnosti zaberá približne 200 GB miesta na disku a neustále rastie. Stav systému je však oveľa menší, rádovo 4 GB, a berie do úvahy len fakt, že niekto momentálne vlastní coiny. Objem týchto údajov sa časom tiež zvyšuje, ale oveľa pomalším tempom a niekedy má dokonca tendenciu klesať (pozri CDPV).
Ľahí klienti (SPV) obchodujú so zárukami bezpečnosti pre schopnosť ukladať žiadny minimálny stav (sada UTXO) okrem súkromných kľúčov.
Sada UTXO a UTXO
UTXO (Nevyčerpaný transakčný výstup) je nevyčerpaný transakčný výstup, koncový bod cesty každého Satoshi prevedeného v transakciách. Nevyčerpané výstupy sa stávajú vstupmi nových transakcií a tým sa míňajú (minú) a odstraňujú zo sady UTXO.
Nové UTXO sa vždy vytvárajú transakciami:
- coinbase transakcie bez vstupov: vytvorte nové UTXO, keď ťažiari vydajú mince
- pravidelné transakcie: vytvorte nové UTXO a zároveň miňte určitý súbor existujúcich UTXO
Postup práce s UTXO:
Peňaženky počítajú počet mincí dostupných na míňanie (zostatok) na základe množstva UTXO, ktoré má táto peňaženka k dispozícii na míňanie.
Každý uzol validátora, aby sa zabránilo pokusom o dvojité výdavky, musí monitorovať množinu všetko UTXO pri kontrole každý transakcií z každého blokovať.
Uzol musí mať logiku:
- Doplnky k súprave UTXO
- Vymazania zo sady UTXO
- Kontrola prítomnosti jedného UTXO v súprave
Existujú spôsoby, ako znížiť požiadavky na uložené informácie o množine, pri zachovaní možnosti pridávať a odstraňovať prvky, kontrolovať a dokazovať existenciu prvku v množine pomocou .
Batérie pre UTXO
Myšlienka použitia batérií na uloženie viacerých UTXO .
UTXO-set je zostavený za behu, počas počiatočného sťahovania bloku (IBD), celý a trvalo uložený, pričom jeho obsah sa mení po spracovaní transakcií z každého nového a správneho bloku siete. Tento proces vyžaduje stiahnutie približne 200 GB blokových údajov a overenie stoviek miliónov digitálnych podpisov. Po dokončení procesu IBD je záverom, že sada UTXO zaberie približne 4 GB.
S akumulátormi sa však pravidlá konsenzu pre fondy obmedzujú na overovanie a generovanie kryptografických dôkazov a bremeno sledovania dostupných prostriedkov sa presúva na vlastníka týchto prostriedkov, ktorý poskytuje dôkaz o ich existencii a vlastníctve.
Akumulátor možno nazvať kompaktným znázornením množiny. Veľkosť uloženej reprezentácie musí byť buď konštantná , alebo zväčšiť sublineárne vzhľadom na mohutnosť množiny a veľkosť samotného prvku, napr. , kde n je mohutnosť uloženej množiny.
V tomto prípade by mal akumulátor umožňovať vygenerovanie dôkazu o zaradení prvku do súboru (inclusion proof) a umožniť efektívne overenie tohto dôkazu.
Batéria je tzv dynamický ak vám umožňuje pridávať prvky a odstraňovať prvky zo sady.
Príkladom takejto batérie by bolo . Takýto akumulátor má konštantnú veľkosť uloženej reprezentácie, ale vyžaduje prítomnosť zdieľané tajomstvo (dôveryhodné nastavenie). Táto požiadavka neguje použiteľnosť takéhoto akumulátora pre nedôveryhodné siete, ako je bitcoin, pretože únik údajov počas generovania tajných informácií môže útočníkom umožniť vytvoriť falošný dôkaz o existencii UTXO, oklamať uzly so sadou UTXO založenou na takomto akumulátore.
Utreexo
Dizajn Utreexo navrhnutý Thaddeusom Dryjom umožňuje tvoriť dynamický batérie bez dôveryhodné nastavenie.
Utreexo je les dokonalej dvojhviezdy a je rozvinutím myšlienok prezentovaných v , pridávajúc možnosť odstraňovať prvky zo sady.
Logická štruktúra batérie
Akumulátorové články sú usporiadané v lese ideálnych binárnych stromov. Stromy sú zoradené podľa výšky. Toto znázornenie bolo zvolené ako najnázornejšie a umožňuje vám vizualizovať spájanie stromov počas operácií na batérii.
Autor poznamenáva, že keďže všetky stromy v lese sú ideálne, ich výška je vyjadrená ako mocnina dvoch, rovnako ako každé prirodzené číslo môže byť vyjadrené ako súčet mocninných dvoch. Podľa toho možno ľubovoľnú sadu listov zoskupiť do binárnych stromov a vo všetkých prípadoch si pridanie nového prvku vyžaduje znalosti len o koreňových uzloch uložených stromov.
Uložená reprezentácia Utreexo akumulátora je teda zoznam koreňových uzlov (Merkle root), a nie celý les stromov.
Predstavme si zoznam koreňových prvkov ako Vec<Option<Hash>>. Voliteľný typ Option<Hash> označuje, že môže chýbať koreňový prvok, čo znamená, že v akumulátore nie je strom s príslušnou výškou.
/// 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],
}
}
}Pridávanie prvkov
Najprv si popíšme funkciu parent(), ktorý rozpoznáva nadradený uzol pre dva dané prvky.
funkcia parent().
Keďže používame stromy Merkle, rodičom každého z dvoch uzlov je jeden uzol, ktorý ukladá hash zreťazenia hashov podradených uzlov:
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 poznamenáva, že zabrániť útokom, ktoré opísali Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir a Sebastien Zimmer v r.
, okrem dvoch hashov treba k zreťazeniu pridať aj výšku vnútri stromu.
Pri pridávaní prvkov do akumulátora musíte sledovať, ktoré koreňové prvky sa zmenili. Sledovaním cesty zmeny koreňových prvkov pre každý prvok, ktorý pridáte, môžete neskôr vytvoriť dôkaz o prítomnosti týchto prvkov.
Sledujte zmeny pri ich pridávaní
Ak chcete sledovať vykonané zmeny, deklarujme štruktúru Update, ktorý bude uchovávať údaje o zmenách uzlov.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Na pridanie prvku do batérie potrebujete:
- Vytvorte pole košov koreňových prvkov
new_rootsa umiestnite tam existujúce koreňové prvky, jeden pre každý vedro:
kód
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);
}- Pripojte prvky, ktoré sa majú pridať (pole
insertions) do prvého košíkanew_roots[0]:
kód
new_roots[0].extend_from_slice(insertions);- Spojte položky pridané do prvého košíka so zvyškom:
- Pre všetky vozíky s viac ako jednou položkou:
- Vezmite dva prvky z konca košíka, vypočítajte ich rodiča, odstráňte oba prvky
- Pridajte vypočítaný rodič do ďalšieho košíka
- Pre všetky vozíky s viac ako jednou položkou:
kód
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 });
}
}- Presuňte koreňové prvky zo zásobníkov do výsledného poľa akumulátorov
kód
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]);
}
}Vytvorenie dôkazu pre pridané prvky
Dôkaz o zahrnutí článku do batérie (Proof) bude slúžiť ako Merkleova cesta pozostávajúca z reťaze ProofStep. Ak cesta nikam nevedie, potom je dôkaz nesprávny.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Použitie informácií získaných skôr pri pridávaní prvku (štruktúry Update), môžete vytvoriť dôkaz, že do batérie bol pridaný prvok. Aby sme to urobili, prejdeme si tabuľku vykonaných zmien a pridáme každý krok do Merkleovej cesty, ktorý bude následne slúžiť ako dôkaz:
kód
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 tvorby dôkazu
Kontrola dôkazu o prvku
Kontrola dôkazu zahrnutia prvku sa scvrkáva na sledovanie cesty Merkle, kým nevedie k existujúcemu koreňovému prvku:
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
}
}Vizuálne:
Proces kontroly dôkazu pre A
Odstraňovanie položiek
Ak chcete vybrať článok z batérie, musíte poskytnúť platný dôkaz, že článok tam je. Pomocou údajov z dôkazu je možné vypočítať nové koreňové prvky akumulátora, pre ktoré daný dôkaz už nebude pravdivý.
Algoritmus je nasledujúci:
- Rovnako ako pri pridávaní, organizujeme sadu prázdnych košov zodpovedajúcich stromom Merkle s výškou rovnou mocnine dvoch z indexu koša
- Do košíkov vkladáme prvky zo stupňov cesta Merkle; index koša sa rovná číslu aktuálneho kroku
- Odstránime koreňový prvok, ku ktorému vedie cesta z dôkazu
- Rovnako ako pri pridávaní vypočítame nové koreňové prvky spojením prvkov z košov do párov a presunom výsledku spojenia do ďalšieho koša
kód
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;
}
}Proces odstraňovania prvku "A":
Integrácia do existujúcej siete
Použitím navrhovaného akumulátora sa uzly môžu vyhnúť používaniu DB na uloženie všetkých UTXO, pričom stále môžu meniť sadu UTXO. Nastáva však problém práce s dôkazmi.
Zavolajme uzol validátora, ktorý používa UTXO akumulátor kompaktný (kompaktný uzol) a validátor bez akumulátora je plne (úplný uzol). Existencia dvoch tried uzlov vytvára problém pre ich integráciu do jednej siete, pretože kompaktné uzly vyžadujú dôkaz o existencii UTXO, ktoré sa vynakladajú na transakcie, zatiaľ čo plné uzly nie. Ak všetky uzly siete neprejdú súčasne a koordinovane na používanie Utreexo, potom kompaktné uzly zostanú pozadu a nebudú môcť fungovať v sieti Bitcoin.
Na vyriešenie problému integrácie kompaktných uzlov do siete sa navrhuje zaviesť ďalšiu triedu uzlov - mosty. Mostový uzol je kompletný uzol, v ktorom je uložená aj batéria Utreexo a dôkaz o zapnutí všetko UTXO zo sady UTXO. Bridges vypočítavajú nové hashe a aktualizujú akumulátor a dôkazy, keď prichádzajú nové bloky transakcií. Údržba a aktualizácia akumulátora a dôkazov nepredstavuje pre takéto uzly dodatočné výpočtové zaťaženie. Mosty obetujú miesto na disku: musia mať veci organizované hash v porovnaní s hash pre kompaktné uzly, kde n je sila sady UTXO.
Architektúra siete
Mosty umožňujú postupne pridávať kompaktné uzly do siete bez zmeny softvéru existujúcich uzlov. Úplné uzly fungujú ako predtým a rozdeľujú transakcie a bloky medzi sebou. Mostové uzly sú úplné uzly, ktoré navyše ukladajú údaje o batérii Utreexo a súbor dôkazov o zahrnutí všetko Zatiaľ UTXO. Mostový uzol sa nepropaguje ako taký a predstiera, že je úplným uzlom pre všetky plné uzly a kompaktným uzlom pre všetky kompaktné uzly. Hoci mosty spájajú obe siete dohromady, v skutočnosti ich potrebujú spojiť iba jedným smerom: od existujúcich úplných uzlov po kompaktné uzly. Je to možné, pretože formát transakcie nie je potrebné meniť a dôkazy UTXO pre kompaktné uzly môžu byť vyradené, takže akýkoľvek kompaktný uzol môže podobne vysielať transakcie všetkým účastníkom siete bez účasti uzlov mosta.
Záver
Pozreli sme sa na batériu Utreexo a implementovali jej prototyp v Ruste. Pozreli sme sa na sieťovú architektúru, ktorá umožní integráciu uzlov na báze batérie. Výhodou kompaktných úlovkov je veľkosť uložených dát, ktorá závisí logaritmicky od výkonu množiny UTXO, čo výrazne znižuje požiadavky na diskový priestor a výkon úložiska pre takéto uzly. Nevýhodou je dodatočná prevádzka uzla na prenos dôkazov, ale techniky agregácie dôkazov (keď jeden dôkaz dokazuje existenciu viacerých prvkov) a ukladanie do vyrovnávacej pamäte môžu pomôcť udržať prevádzku v prijateľných medziach.
referencie:
- -
Zdroj: hab.com