Hey Habr!
Di tora Bitcoin de, hemî girêk, bi riya lihevkirinê, li ser komek UTXO-yan li hev dikin: çend coin ji bo xerckirinê hene, tam ji kê re û di bin çi mercan de. Komela UTXO komek daneya hindiktirîn e ku ji bo girêk erêkerê hewce dike, bêyî ku girêk dê nikaribe rastdariya danûstendinên hatî û blokên ku di nav wan de hene verast bike.
Di vî warî de, bi her awayî hewl tê dayîn ku nûnertiya hilanîn a vê setê kêm bike, bêyî ku garantiyên ewlehiyê winda bike, were çewisandin. Hêjmara daneya hilanîn her ku piçûktir be, ew qas hewcedariyên cîhê dîskê ya girêka erêker kêm dibe, ku destpêkirina girêkek pejirandî erzan dike, dihêle hûn torê berfireh bikin û bi vî rengî aramiya torê zêde bikin.
Di vê postê de em ê prototîpa Rust ya pêşnûmeya vê dawiyê ya ji hev-nivîskar bişînin , - , ku destûrê dide kêmkirina pêdiviyên cîhê dîskê ji bo girêkên erêker.
Di çi pirsgirêkê de ye?
Yek ji pirsgirêkên herheyî yên Bitcoin mezinbûna wê ye. Fikra "banga xweya xwe" ji beşdarên torê hewce dike ku tomarên hemî diravên ku ji bo karanîna têne peyda kirin bigirin. Di Bitcoin de, fonên berdest wekî komek hilberên neçûyî têne diyar kirin - UTXO-set. Digel ku ev ne nûneriyek taybetî ye, ew di warê performansa bicîhkirinê de li ser nûnertiyek ku tê de her "balansek" wekî têketinek cûda "balansek" heye, û nepenîtiyê jî zêde dike (mînak. ).
Girîng e ku meriv di navbera dîroka danûstendinan de (ya ku jê re zincîra blokê tê gotin) û rewşa heyî ya pergalê cûda bike. Dîroka danûstendina Bitcoin naha nêzîkê 200 GB cîhê dîskê digire, û mezin dibe. Lêbelê, dewleta pergalê pir piçûktir e, li ser fermana 4 GB, û tenê vê rastiyê dihesibîne ku kesek niha xwediyê drav e. Hêjmara vê daneyê jî bi demê re zêde dibe, lê bi rêjeyek pir hêdîtir û carinan jî kêm dibe (li CDPV binêre).
Xerîdarên sivik (SPV) garantiya ewlehiya bazirganiyê ji bo kapasîteya hilanîna rewşa herî kêm (UTXO-set) ji bilî bişkojkên taybet.
UTXO û UTXO-set
UTXO (Derketina danûstendinê ya neçûyî) derketina danûstendinê ya neçûyî ye, xala dawiya rêwîtiya her Satoshi ya ku di danûstendinan de hatî veguheztin. Berhemên nebihurî dibin ketina danûstendinên nû û bi vî rengî têne xerc kirin (xerf kirin) û ji UTXO-set têne derxistin.
UTXOyên nû her gav ji hêla danûstendinan ve têne afirandin:
- danûstendinên coinbase bêyî têketinê: Dema ku kanan zêran derdixin UTXOyên nû biafirînin
- danûstendinên birêkûpêk: dema ku komek UTXO-yên heyî xerc dikin UTXO-yên nû biafirînin
Pêvajoya xebata bi UTXO:
Wallet li ser bingeha mîqdara UTXO ya ku ji bo xerckirinê li ser vê berîkê heye, hejmara pereyên ku ji bo lêçûnê (balansek) peyda dibin dihejmêrin.
Her girêk erêker, ji bo pêşîgirtina li hewildanên xerckirina ducarî, pêdivî ye ku setê bişopîne всех UTXO dema ku kontrol dike herkes muamele ji her yekê deste.
Divê girêk xwedî mantiq be:
- Zêdekirinên li UTXO-set
- Jêbirinên ji UTXO-set
- Kontrolkirina hebûna yek UTXO-yê di komekê de
Rêbaz hene ku hewcedariyên agahdariya hilandî ya di derheqê komekê de kêm bikin, di heman demê de şiyana zêdekirin û rakirina hêmanan, kontrolkirin û îsbatkirina hebûna hêmanek di komekê de bi kar tînin. .
Pîl ji bo UTXO
Fikra karanîna bataryayên ji bo hilanîna gelek UTXO-yan .
UTXO-set di firînê de, di dema dakêşana bloka destpêkê (IBD) de hatî çêkirin, bi tevahî û bi domdarî tê hilanîn, dema ku naveroka wê piştî pêvajoyên danûstendinê ji her bloka nû û rast a torê diguhezîne. Ev pêvajo hewce dike ku bi qasî 200 GB daneyên blokê dakêşin û bi sed mîlyonan îmzeyên dîjîtal verast bikin. Piştî ku pêvajoya IBD qediya, xala jêrîn ev e ku UTXO-set dê bi qasî 4 GB dagir bike.
Lêbelê, digel berhevkeran, qaîdeyên lihevhatina fonan bi verastkirin û hilberîna delîlên krîptografî têne kêm kirin, û barê şopandina dravên berdest tê guheztin ser xwediyê wan fonan, ku delîlên hebûn û xwedaniya wan peyda dike.
Acumulatorek dikare wekî nûneriya kompakt a komekê were binav kirin. Mezinahiya nûneriya hilanîn divê an sabit be , an jî li gorî qertafiya setê û mezinahiya hêmanê bi xwe bi rengek jêrîn zêde bibe, mînakî , ku n kardinalîteya set hilanîn e.
Di vê rewşê de, akumulator divê destûrê bide ku delîlek tevlêbûna hêmanek di berhevokê de (belgeya tevlêbûnê) çêbike û verastkirina vê delîlê bi bandor bike.
Pîlê tê gotin dînamîk heke destûrê dide te ku hûn hêmanan lê zêde bikin û hêmanan ji komekê derxînin.
Nimûneyek ji batterek wusa dê bibe . Acumulatorek wusa xwedan mezinahiyek domdar a nûnertiya hilanîn e, lê hebûna hewce dike raza hevpar (sazkirina pêbawer). Ev pêdiviye sepandina berhevkerek wusa ji bo torên bêbawer ên mîna Bitcoin red dike, ji ber ku rijandina daneyê di dema nifşê nepenî de dikare rê bide êrîşkaran ku delîlek derewîn a hebûna UTXO biafirînin, girêkên bi UTXO-setek li ser bingeha berhevkerek wusa bixapînin.
Utreexo
Sêwirana Utreexo ya ku ji hêla Thaddeus Dryja ve hatî pêşniyar kirin afirandina afirandina gengaz dike dînamîk aktîv bêyî pêbawer-sazkirin.
Utreexo daristanek binaryiya bêkêmasî ye û pêşveçûnek ramanên ku tê de têne pêşkêş kirin , zêdekirina şiyana rakirina hêmanan ji komek.
Battery Structure Logical
Hucreyên pîlê di nav daristanek darên binary ên îdeal de hatine rêz kirin. Dar li gorî bilindahiyê têne rêz kirin. Ev nûnertî wekî ya herî dîtbar hate hilbijartin û dihêle hûn di dema operasyonên li ser pîlê de yekbûna daran xuyang bikin.
Nivîskar destnîşan dike ku ji ber ku hemî darên daristanê îdeal in, bilindahiya wan wekî hêza duyan tête diyar kirin, mîna ku her jimarek xwezayî dikare wekî komek hêza duyan were destnîşan kirin. Li gorî vê yekê, her komek pelan dikare di nav darên binary de were kom kirin, û di hemî rewşan de, lê zêdekirina hêmanek nû zanînê hewce dike. tenê li ser girêkên koka darên hilanîn.
Bi vî rengî, nûneriya hilanîn a berhevkarê Utreexo navnîşek girêkên root e (roka Merkle), û ne tevahiya daristana daran.
Werin em navnîşa hêmanên root wekî temsîl bikin Vec<Option<Hash>>. Cureyê Bijarî Option<Hash> destnîşan dike ku dibe ku hêmana root winda bibe, ev tê vê wateyê ku di berhevokê de darek bi bilindahiya guncaw tune.
/// 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],
}
}
}Zêdekirina hêmanan
Pêşîn, em fonksiyonê diyar bikin parent(), ku girêka dêûbav ji bo du hêmanên diyarkirî nas dike.
fonksiyona dê û bav ().
Ji ber ku em darên Merkle bikar tînin, dêûbavê her du girêkan yek girêkek e ku hashê hevgirtina hêmanên girêkên zarokan hilîne:
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[..])
}Nivîskar destnîşan dike ku ji bo pêşîgirtina li êrîşên Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir û Sebastien Zimmer di
, ji bilî du hespan, bilindahiya hundurê darê jî divê li hevgirtinê were zêdekirin.
Gava ku hûn hêmanan li berhevkerê zêde dikin, hûn hewce ne ku bişopînin ka kîjan hêmanên root têne guhertin. Bi şopandina riya guhartina hêmanên root ji bo her hêmanek ku hûn lê zêde dikin, hûn dikarin paşê delîlek hebûna van hêmanan ava bikin.
Gava ku hûn wan lê zêde dikin, guhertinan bişopînin
Ji bo şopandina guhertinên hatine çêkirin, werin em strukturê ragihînin Update, ya ku dê daneyên di derbarê guhertinên nodê de hilîne.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Ji bo ku hêmanek li pîlê zêde bikin, hûn hewce ne:
- Komek selikên hêmanên root biafirînin
new_rootsû hêmanên root yên heyî li wir bi cîh bikin, ji bo her kelekek yek:
code
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);
}- Hêmanên ku werin zêdekirin (array
insertions) selika yekemnew_roots[0]:
code
new_roots[0].extend_from_slice(insertions);- Tiştên ku li selika yekem hatine zêdekirin bi yên mayî re bikin yek:
- Ji bo hemî selikên ku ji yekê zêdetir tişt hene:
- Ji dawiya selikê du hêman bistînin, dêûbavê wan hesab bikin, her du hêmanan jê bikin
- Dêûbavê hesabkirî li selika paşîn zêde bikin
- Ji bo hemî selikên ku ji yekê zêdetir tişt hene:
code
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 });
}
}- Hêmanên kok ji çîtikan veguhezînin rêza berhevkerê ya encam
code
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]);
}
}Afirandina delîlek ji bo hêmanên zêdekirî
Belgeya tevlêbûna hucreyê di pîlê de (Proof) dê wekî Riya Merkle, ku ji zincîrek pêk tê, xizmetê bike ProofStep. Ger rê nagihê tu derê, wê demê delîl nerast e.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Bikaranîna agahdariya ku berê hatî bidestxistin dema ku hêmanek zêde dike (avahî Update), hûn dikarin delîlek biafirînin ku hêmanek li pîlê hatiye zêdekirin. Ji bo vê yekê, em di tabloya guhertinên hatine çêkirin re derbas dibin û her gav li ser riya Merkle zêde dikin, ku dê dûv re wekî delîl be:
code
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
}
}Pêvajoya çêkirina delîlekê
Kontrolkirina delîl ji bo hêmanek
Kontrolkirina delîla tevlêbûna hêmanek bi şopandina riya Merkle vedigere heya ku ew bigihîje hêmanek bingehîn a heyî:
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
}
}Bi dîtbarî:
Pêvajoya kontrolkirina delîlê ji bo A
Rakirina tiştan
Ji bo rakirina şaneyek ji pîlê, divê hûn delîlên derbasdar bidin ku hucre li wir e. Bi karanîna daneyên ji delîlan re, gengaz e ku meriv hêmanên nû yên koka berhevkarê ku ji bo delîlên hatî dayîn êdî ne rast be were hesibandin.
Algorîtmaya jêrîn ev e:
- Wekî din, em komek selikên vala yên ku li gorî darên Merkle-yê bi bilindahiyek wekhev bi hêza duyan ji nîşaneya selikê re têkildar organîze dikin.
- Em hêmanên ji gavên riya Merkle têxin nav selikan; index baskê bi hejmara gavê niha ye
- Em hêmana root ya ku rê ji delîlan ber bi wê ve diçe jê dikin
- Mîna lêzêdekirinê, em hêmanên koka nû dihejmêrin bi berhevkirina hêmanên ji selikan bi cot û veguheztina encama yekîtiyê berbi selika din.
code
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;
}
}Pêvajoya rakirina hêmana "A":
Entegrasyona nav tora heyî
Bi karanîna berhevkarê pêşniyarkirî, girêk dikarin ji karanîna DB-ê dûr bixin da ku hemî UTXO-yan hilînin dema ku hîn jî dikarin UTXO-set biguhezînin. Lêbelê, pirsgirêka xebata bi delîlan derdikeve holê.
Werin em gazî girêka erêkerê bikin ku berhevkarê UTXO bikar tîne gişt (girêk-dewleta kompakt), û erêkerê bê berhevkar e temam (girêka tije). Hebûna du çînên girêkan ji bo entegrekirina wan di yek torê de pirsgirêkek çêdike, ji ber ku girêkên kompakt delîlên hebûna UTXO-yan hewce dikin, yên ku di danûstendinan de têne xerc kirin, dema ku girêkên tijî ne hewce ne. Ger hemî girêkên torê bi hevdemî û bi rengek hevrêzî neçin karanîna Utreexo, wê hingê girêkên kompakt dê li paş bimînin û dê nikaribin li ser tora Bitcoin bixebitin.
Ji bo çareserkirina pirsgirêka yekkirina girêkên kompakt di nav torê de, tê pêşniyar kirin ku çînek pêvek ji girêkan were danîn - pira. Girêk pirek girêkek bêkêmasî ye ku di heman demê de pîlê Utreexo û delîla hêzê jî hilîne всех UTXO ji UTXO-set. Dema ku blokên nû yên danûstendinê digihîjin pira haşên nû hesab dikin û berhevkar û delîlan nûve dikin. Xwedîkirin û nûvekirina akumulator û delîlan barek hesabkerî ya zêde li ser girêkên weha ferz nake. Pira cîhê dîskê dikin qurban: pêdivî ye ku tiştan organîze bikin haş, li gorî haş ji bo girêkên kompakt, ku n hêza set UTXO ye.
mîmarî Network
Piran dihêle ku hêdî hêdî girêkên kompakt li torê zêde bikin bêyî ku nermalava girêkên heyî biguhezînin. Nodên bêkêmasî wekî berê tevdigerin, danûstendin û blokan di nav xwe de belav dikin. Girêkên pirê girêkên tije ne ku wekî din daneya bateriya Utreexo û komek delîlên tevlêbûnê ji bo всех UTXO ji bo niha. Girêka pirê xwe bi vî rengî reklam nake, ji bo hemî girêkên tije girêkek tije û ji bo hemî girêkên tevlihev wekî girêkek tevhev xuya dike. Her çend pirek her du toran bi hev ve girêdide, ew bi rastî hewce ne ku wan bi yek alî ve girêbidin: ji girêkên tijî yên heyî heya girêkên kompakt. Ev mimkun e ji ber ku ne hewce ye ku formata danûstendinê were guheztin, û delîlên UTXO yên ji bo girêkên kompakt dikarin werin avêtin, ji ber vê yekê her girêkek kompakt dikare bi heman rengî danûstandinan ji hemî beşdarên torê re bêyî beşdarbûna girêkên pirê biweşîne.
encamê
Me li pîlê Utreexo nêrî û prototîpa wê li Rust bicîh kir. Me li mîmariya torê nihêrî ku dê destûrê bide yekbûna girêkên bataryayê. Feydeya girtina kompakt mezinahiya daneya hilanîn e, ku bi logarîtmîkî bi hêza koma UTXO-yan ve girêdayî ye, ku ev hewcedariyên cîhê dîskê û performansa hilanînê ji bo girêkên weha pir kêm dike. Kêmasî seyrûsefera nodê ya zêde ye ji bo veguheztina delîlan, lê teknîkên berhevkirina delîlan (gava yek delîl hebûna çend hêmanan îspat dike) û caching dikare bibe alîkar ku seyrûsefer di nav sînorên pejirandî de bimîne.
references:
- -
Source: www.habr.com