Hej Habr!
En la reto Bitcoin, ĉiuj nodoj, per konsento, konsentas pri aro da UTXO-oj: kiom da moneroj estas disponeblaj por elspezi, al kiu ĝuste kaj sub kiaj kondiĉoj. La UTXO-aro estas la minimuma aro de datumoj necesaj por validigilo-nodo, sen kiu la nodo ne povos kontroli la validecon de envenantaj transakcioj kaj la blokoj enhavantaj ilin.
Ĉi-rilate, provoj estas faritaj laŭ ĉiuj eblaj manieroj redukti la konservitan reprezenton de ĉi tiu aro, por kunpremi ĝin sen perdi sekurecajn garantiojn. Ju pli malgranda estas la volumo de stokitaj datumoj, des pli malaltaj estas la postuloj pri diskspaco de la validiga nodo, kio malkaras lanĉi validigilon, ebligas al vi vastigi la reton kaj tiel pliigi la stabilecon de la reto.
En ĉi tiu afiŝo ni afiŝos Rust-prototipon de lastatempa propono de kunaŭtoro , - , kiu permesas redukti diskspacpostulojn por validigilo-nodoj.
Kio estas la problemo?
Unu el la multjaraj problemoj de Bitcoin estis ĝia skaleblo. La ideo de "via propra banko" postulas retajn partoprenantojn konservi registrojn pri ĉiuj disponeblaj financoj por uzo. En Bitcoin, disponeblaj financoj estas esprimitaj kiel aro de neeluzitaj eliroj - UTXO-aro. Kvankam ĉi tio ne estas precipe intuicia reprezentado, ĝi estas utila laŭ efektiviga efikeco super reprezentado en kiu ĉiu "monujo" havas "ekvilibron" kiel apartan eniron, kaj ankaŭ aldonas privatecon (ekz. ).
Gravas distingi inter la historio de transakcioj (kio nomiĝas blokoĉeno) kaj la aktuala stato de la sistemo. La transakcia historio de Bitcoin nuntempe okupas ĉirkaŭ 200 GB da diskospaco, kaj daŭre kreskas. Tamen, la sistema stato estas multe pli malgranda, je la ordo de 4 GB, kaj nur konsideras la fakton, ke iu nuntempe posedas monerojn. La volumo de ĉi tiuj datumoj ankaŭ pliiĝas laŭlonge de la tempo, sed kun multe pli malrapida rapideco kaj foje eĉ emas malpliiĝi (vidu CDPV).
Malpezaj klientoj (SPVs) komercaj sekurecgarantioj por la kapablo konservi neniun minimuman ŝtaton (UTXO-aro) krom privataj ŝlosiloj.
UTXO kaj UTXO-aro
UTXO (Neeluzita Transakcia Eligo) estas la neeluzita transakcia eligo, la fina punkto de la vojaĝo de ĉiu Satoshi translokigita en transakcioj. Neeluzitaj produktaĵoj fariĝas enigaĵoj de novaj transakcioj kaj estas tiel elspezitaj (elspezitaj) kaj forigitaj de la UTXO-aro.
Novaj UTXO-oj ĉiam estas kreitaj per transakcioj:
- coinbase-transakcioj sen enigaĵoj: kreu novajn UTXO-ojn kiam ministoj eldonas monerojn
- regulaj transakcioj: kreu novajn UTXO-ojn dum elspezado de certa aro de ekzistantaj UTXO-oj
Procezo de laborado kun UTXO:
Monujoj kalkulas la nombron da moneroj disponeblaj por elspezo (ekvilibro) surbaze de la kvanto de UTXO disponebla por ĉi tiu monujo por elspezo.
Ĉiu validigilo-nodo, por malhelpi duoblajn elspezajn provojn, devas monitori la aron всех UTXO dum kontrolo ĉiu transakcioj ĉiu bloko.
La nodo devas havi logikon:
- Aldonoj al UTXO-aro
- Forigoj de UTXO-aro
- Kontrolante la ĉeeston de ununura UTXO en aro
Estas manieroj redukti la postulojn por konservitaj informoj pri aro, konservante la kapablon aldoni kaj forigi elementojn, kontroli kaj pruvi la ekziston de elemento en aro uzante .
Baterioj por UTXO
La ideo uzi bateriojn por stoki plurajn UTXO-ojn .
La UTXO-aro estas konstruita sur la flugo, dum la komenca bloka elŝuto (IBD), konservita plene kaj konstante, dum ĝia enhavo ŝanĝiĝas post prilaborado de transakcioj de ĉiu nova kaj ĝusta bloko de la reto. Ĉi tiu procezo postulas elŝuti proksimume 200 GB da blokaj datumoj kaj kontroli centojn da milionoj da ciferecaj subskriboj. Post kiam la IBD-procezo estas kompletigita, la fundo estas, ke la UTXO-aro okupos ĉirkaŭ 4 GB.
Tamen, kun akumuliloj, la reguloj de konsento por financo estas reduktitaj al la konfirmo kaj generacio de kriptaj pruvoj, kaj la ŝarĝo de spurado de disponeblaj financo estas translokita al la posedanto de tiuj financoj, kiu provizas pruvon de ilia ekzisto kaj proprieto.
Akumulilo povas esti nomita kompakta prezento de aro. La grandeco de la stokita reprezentado devas esti aŭ konstanta , aŭ pliiĝi sublinie kun respekto al la kardinaleco de la aro kaj la grandeco de la elemento mem, ekzemple , kie n estas la kardinaleco de la stokita aro.
En ĉi tiu kazo, la akumulilo devus permesi generi pruvon de la inkludo de elemento en la aro (inkludpruvo) kaj ebligi efike kontroli ĉi tiun pruvon.
La baterio nomiĝas dinamika se permesas aldoni elementojn kaj forigi elementojn de aro.
Ekzemplo de tia baterio estus . Tia akumulilo havas konstantan grandecon de stokita reprezentado, sed postulas la ĉeeston dividita sekreto (fidinda aranĝo). Ĉi tiu postulo neas la aplikeblecon de tia akumulilo por senfidaj retoj kiel Bitcoin, ĉar datumfluado dum sekreta generacio povas permesi al atakantoj krei malveran pruvon pri la ekzisto de UTXO, trompante nodojn kun UTXO-aro bazita sur tia akumulilo.
Utreexo
La dezajno Utreexo proponita de Thaddeus Dryja ebligas krei dinamika baterio sen fidinda agordo.
Utreexo estas arbaro de perfekta duuma kaj estas evoluo de la ideoj prezentitaj en , aldonante la kapablon forigi elementojn de aro.
Bateria Logika Strukturo
La bateriaj ĉeloj estas aranĝitaj en arbaro de idealaj binaraj arboj. Arboj estas ordigitaj laŭ alteco. Ĉi tiu reprezento estis elektita kiel la plej vida kaj permesas al vi bildigi la kunfandiĝon de arboj dum operacioj sur la baterio.
La aŭtoro notas ke ĉar ĉiuj arboj en la arbaro estas idealaj, ilia alteco estas esprimita kiel potenco de du, same kiel ajna natura nombro povas esti reprezentita kiel sumo de potencoj de du. Sekve, ajna aro de folioj povas esti grupigita en binarajn arbojn, kaj en ĉiuj kazoj, aldoni novan elementon postulas scion. nur pri la radikaj nodoj de konservitaj arboj.
Tiel, la stokita reprezentado de la Utreexo-akumulilo estas listo de radiknodoj (Merkle-radiko), kaj ne la tuta arbaro de arboj.
Ni reprezentu la liston de radikaj elementoj kiel Vec<Option<Hash>>. Laŭvola tipo Option<Hash> indikas ke la radika elemento eble mankas, kio signifas, ke ne estas arbo kun la taŭga alteco en la akumulilo.
/// 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],
}
}
}Aldonante elementojn
Unue, ni priskribu la funkcion parent(), kiu rekonas la gepatran nodon por du donitaj elementoj.
parent() funkcio
Ĉar ni uzas Merkle-arbojn, la gepatro de ĉiu el la du nodoj estas unu nodo, kiu stokas la haŝon de la kunmetiĝo de la haŝiŝoj de la infannodoj:
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[..])
}La aŭtoro notas, ke por malhelpi la atakojn priskribitajn de Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir kaj Sebastien Zimmer en
, krom la du haŝetoj, la alteco ene de la arbo ankaŭ devus esti aldonita al la kunligado.
Dum vi aldonas elementojn al la akumulilo, vi devas konservi trakon pri kiuj radikaj elementoj estas ŝanĝitaj. Sekvante la vojon ŝanĝi la radikajn elementojn por ĉiu elemento, kiun vi aldonas, vi povas poste konstrui pruvon pri la ĉeesto de ĉi tiuj elementoj.
Spuri ŝanĝojn dum vi aldonas ilin
Por spuri la ŝanĝojn faritajn, ni deklaru la strukturon Update, kiu stokos datumojn pri nodaj ŝanĝoj.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Por aldoni elementon al la kuirilaro, vi bezonas:
- Kreu aron da korboj da radikaj elementoj
new_rootskaj metu la ekzistantajn radikajn elementojn tie, unu por ĉiu sitelo:
Kodo
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);
}- Aldonu la aldonotajn elementojn (tabelo
insertions) al la unua ĉaronew_roots[0]:
Kodo
new_roots[0].extend_from_slice(insertions);- Kunigu la aĵojn aldonitajn al la unua korbo kun la ceteraj:
- Por ĉiuj ĉaroj kun pli ol unu objekto:
- Prenu du elementojn el la fino de la korbo, kalkulu ilian gepatron, forigu ambaŭ elementojn
- Aldonu la kalkulitan gepatron al la sekva ĉaro
- Por ĉiuj ĉaroj kun pli ol unu objekto:
Kodo
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 });
}
}- Movu radikajn elementojn de rubujoj al rezulta akumula tabelo
Kodo
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]);
}
}Kreante pruvon por aldonitaj elementoj
Pruvo de inkludo de la ĉelo en la baterio (Proof) servos kiel la Merkle Vojo, konsistanta el ĉeno ProofStep. Se la vojo kondukas nenien, tiam la pruvo estas malĝusta.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Uzante la informojn akiritajn pli frue aldonante elementon (strukturo Update), vi povas krei pruvon, ke elemento estis aldonita al la baterio. Por fari tion, ni ekzamenas la tabelon de ŝanĝoj faritaj kaj aldonas ĉiun paŝon al la vojo de Merkle, kiu poste servos kiel pruvo:
Kodo
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
}
}Procezo de kreado de pruvo
Kontrolante la pruvon por elemento
Kontroli la inkluzivan pruvon de elemento signifas sekvi la Merkle-vojon ĝis ĝi kondukas al ekzistanta radika elemento:
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
}
}Vide:
Procezo de kontrolado de la pruvo por A
Forigante erojn
Por forigi ĉelon el baterio, vi devas provizi validan pruvon, ke la ĉelo estas tie. Uzante la datumojn de la pruvo, eblas kalkuli novajn radikajn elementojn de la akumulilo por kiuj la donita pruvo ne plu estos vera.
La algoritmo estas kiel sekvas:
- Kiel kun aldono, ni organizas aron da malplenaj korboj respondaj al Merkle-arboj kun alteco egala al la potenco de du el la korba indekso.
- Ni enmetas elementojn de la ŝtupoj de la Merkle-vojo en la korbojn; la korba indekso estas egala al la nombro de la nuna paŝo
- Ni forigas la radikan elementon al kiu kondukas la vojo de la pruvo
- Kiel kun aldonado, ni kalkulas novajn radikajn elementojn kombinante elementojn de korboj duope kaj movante la rezulton de la kuniĝo al la sekva korbo.
Kodo
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;
}
}La procezo por forigi elementon "A":
Integriĝo en ekzistantan reton
Uzante la proponitan akumulilon, nodoj povas eviti uzi DB por stoki ĉiujn UTXO-ojn dum daŭre povante ŝanĝi la UTXO-aro. Tamen, la problemo labori kun indico ekestas.
Ni voku la validigilon nodon kiu uzas la UTXO-akumulilon kompakta (kompakt-ŝtata nodo), kaj la validigilo sen akumulilo estas kompleta (plena nodo). La ekzisto de du klasoj de nodoj kreas problemon por integri ilin en ununuran reton, ĉar kompaktaj nodoj postulas pruvon de la ekzisto de UTXOoj, kiuj estas elspezitaj en transakcioj, dum plenaj nodoj ne faras. Se ĉiuj retaj nodoj ne samtempe kaj kunordigite ŝanĝas al uzado de Utreexo, tiam kompaktaj nodoj restos malantaŭe kaj ne povos funkcii en la reto Bitcoin.
Por solvi la problemon de integri kompaktajn nodojn en la reto, oni proponas enkonduki plian klason de nodoj - pontoj. Ponta nodo estas kompleta nodo, kiu ankaŭ konservas la Utreexo-baterion kaj pruvon pri ŝaltita всех UTXO de UTXO-aro. Pontoj kalkulas novajn haŝojn kaj ĝisdatigas la akumulilon kaj pruvojn kiam alvenas novaj blokoj de transakcioj. Konservi kaj ĝisdatigi la akumulilon kaj pruvojn ne trudas kroman komputilan ŝarĝon sur tiaj nodoj. Pontoj oferas diskospacon: bezonas teni aferojn organizitaj hashes, kompare kun haŝoj por kompaktaj nodoj, kie n estas la potenco de la UTXO-aro.
Reta arkitekturo
Pontoj ebligas iom post iom aldoni kompaktajn nodojn al la reto sen ŝanĝi la programaron de ekzistantaj nodoj. Plenaj nodoj funkcias kiel antaŭe, distribuante transakciojn kaj blokojn inter si. Pontaj nodoj estas plenaj nodoj, kiuj aldone stokas Utreexo-bateriodatenojn kaj aron da inkluzivaj pruvoj por всех UTXO nuntempe. La pontnodo ne reklamas sin kiel tia, ŝajnigante esti plena nodo por ĉiuj plenaj nodoj kaj kompakta nodo por ĉiuj kompaktaj. Kvankam pontoj kunligas ambaŭ retojn kune, ili fakte nur bezonas ligi ilin en unu direkto: de ekzistantaj plenaj nodoj ĝis kompaktaj nodoj. Tio estas ebla ĉar la transakcia formato ne bezonas esti ŝanĝita, kaj UTXO-pruvoj por kompaktaj nodoj povas esti forĵetitaj, tiel ke ĉiu kompakta nodo povas simile dissendi transakciojn al ĉiuj retpartoprenantoj sen la partopreno de pontnodoj.
konkludo
Ni rigardis la Utreexo-baterion kaj efektivigis ĝian prototipon en Rust. Ni rigardis la retan arkitekturon, kiu permesos la integriĝon de baterio-bazitaj nodoj. La avantaĝo de kompaktaj kaptaĵoj estas la grandeco de la stokitaj datumoj, kiu dependas logaritme de la potenco de la aro de UTXO-oj, kiu multe reduktas la postulojn por diskospaco kaj stokado-rendimento por tiaj nodoj. La malavantaĝo estas la kroma nodtrafiko por elsendado de pruvoj, sed pruvaj agregteknikoj (kiam unu pruvo pruvas la ekziston de pluraj elementoj) kaj kaŝmemoro povas helpi konservi trafikon ene de akcepteblaj limoj.
referencoj:
- -
fonto: www.habr.com