Hoi Habr!
Yn it Bitcoin-netwurk binne alle knooppunten, fia konsensus, it iens oer in set fan UTXO's: hoefolle munten binne beskikber foar útjeften, oan wa krekt, en ûnder hokker betingsten. De UTXO-set is de minimale set fan gegevens dy't nedich binne foar in validatorknooppunt, sûnder dat it knooppunt de jildichheid fan ynkommende transaksjes en de blokken dy't se befetsje net kin ferifiearje.
Yn dit ferbân wurdt op alle mooglike manieren besocht om de opsleine fertsjintwurdiging fan dizze set te ferminderjen, om it te komprimearjen sûnder feiligensgarânsjes te ferliezen. Hoe lytser it folume fan opsleine gegevens, hoe leger de skiifromteeasken fan 'e validatorknooppunt, wat it lansearjen fan in validatorknooppunt goedkeap makket, kinne jo it netwurk útwreidzje en dêrmei de stabiliteit fan it netwurk ferheegje.
Yn dizze post sille wy in Rust-prototype pleatse fan in resint foarstel fan in mei-auteur , - , wêrtroch skiifromteeasken foar validatorknooppunten ferminderje kinne.
Wat is it probleem?
Ien fan 'e perennial problemen fan Bitcoin wie syn skalberens. It idee fan "jo eigen bank" fereasket netwurk dielnimmers te hâlden records fan alle fûnsen beskikber foar gebrûk. Yn Bitcoin wurde beskikbere fûnsen útdrukt as in set fan net bestege útgongen - in UTXO-set. Hoewol dit net in bysûnder yntuïtive fertsjintwurdiging is, is it foardielich yn termen fan ymplemintaasjeprestaasjes oer in fertsjintwurdiging wêryn elke "wallet" in "balâns" hat as in aparte yngong, en ek privacy tafoeget (bgl. ).
It is wichtich om te ûnderskieden tusken de skiednis fan transaksjes (wat hjit de blockchain) en de hjoeddeistige steat fan it systeem. Bitcoin-transaksjeskiednis nimt op it stuit sawat 200 GB skiifromte op, en bliuwt groeie. Lykwols, it systeem steat is folle lytser, op 'e folchoarder fan 4 GB, en allinnich hâldt rekken mei it feit dat immen stuit eigner munten. It folume fan dizze gegevens nimt ek yn 'e rin fan' e tiid ta, mar op in folle stadiger taryf en hat soms sels de neiging om te ferminderjen (sjoch CDPV).
Light kliïnten (SPVs) hannel feiligens garânsjes foar de mooglikheid om te bewarjen gjin minimum steat (UTXO-set) oars as privee kaaien.
UTXO en UTXO-set
UTXO (Unspent Transaction Output) is de net bestege transaksjeútfier, it einpunt fan 'e reis fan elke Satoshi oerdroegen yn transaksjes. Net bestege útgongen wurde yngongen fan nije transaksjes en wurde dêrmei bestege (útjaan) en fuortsmiten fan de UTXO-set.
Nije UTXO's wurde altyd makke troch transaksjes:
- coinbase-transaksjes sûnder ynput: meitsje nije UTXO's as mynwurkers munten útjaan
- reguliere transaksjes: meitsje nije UTXOs wylst besteegje in bepaalde set fan besteande UTXOs
Proses fan wurkjen mei UTXO:
Wallets telle it oantal munten beskikber foar útjeften (balâns) basearre op it bedrach fan UTXO beskikber foar dizze portemonnee foar útjeften.
Elke validatorknooppunt, om dûbele bestegingspogingen te foarkommen, moat de set kontrolearje всех UTXO by it kontrolearjen elk transaksjes fan elk blok.
It knooppunt moat logika hawwe:
- Tafoegings oan UTXO-set
- Wiskjes fan UTXO-set
- Kontrolearje de oanwêzigens fan in inkele UTXO yn in set
D'r binne manieren om de easken foar opsleine ynformaasje oer in set te ferminderjen, wylst de mooglikheid behâlde om eleminten ta te foegjen en te ferwiderjen, it bestean fan in elemint yn in set te kontrolearjen en te bewizen mei .
Batterijen foar UTXO
It idee om batterijen te brûken om meardere UTXO's op te slaan .
De UTXO-set is boud op 'e flecht, tidens de earste blokdownload (IBD), folslein en permanint opslein, wylst de ynhâld feroaret nei it ferwurkjen fan transaksjes fan elke nije en korrekte blok fan it netwurk. Dit proses fereasket it downloaden fan sawat 200 GB oan blokgegevens en it ferifiearjen fan hûnderten miljoenen digitale hantekeningen. Nei it IBD-proses is foltôge, is de ûnderste rigel dat de UTXO-set sawat 4 GB sil besette.
Mei accumulators wurde de regels fan konsensus foar fûnsen lykwols fermindere ta de ferifikaasje en generaasje fan kryptografyske bewizen, en de lêst fan it folgjen fan beskikbere fûnsen wurdt ferpleatst nei de eigner fan dy fûnsen, dy't bewiis leveret fan har bestean en eigendom.
In akkumulator kin neamd wurde in kompakte fertsjintwurdiging fan in set. De grutte fan 'e opsleine fertsjintwurdiging moat konstant wêze , of sublineêr ferheegje mei respekt foar de kardinaliteit fan 'e set en de grutte fan it elemint sels, bygelyks , dêr't n is de kardinaliteit fan de opsleine set.
Yn dit gefal moat de accumulator in bewiis meitsje fan it opnimmen fan in elemint yn 'e set (opnimmingsbewiis) en meitsje it mooglik om dit bewiis effektyf te ferifiearjen.
De batterij wurdt neamd dynamysk as kinne jo tafoegje eleminten en fuortsmite eleminten út in set.
In foarbyld fan sa'n batterij soe wêze . Sa'n accumulator hat in konstante grutte fan bewarre fertsjintwurdiging, mar fereasket de oanwêzigens dielde geheim (fertroude opset). Dizze eask negearret de tapasberens fan sa'n accumulator foar trustless netwurken lykas Bitcoin, om't gegevenslekkage tidens geheime generaasje oanfallers kinne meitsje om falsk bewiis te meitsjen fan it bestean fan in UTXO, ferrifeljende knopen mei in UTXO-set basearre op sa'n accumulator.
Utreexo
It Utreexo-ûntwerp foarsteld troch Thaddeus Dryja makket it mooglik om te meitsjen dynamysk аккумулятор sûnder fertroude-opset.
Utreexo is in bosk fan perfekte binary en is in ûntwikkeling fan de ideeën presintearre yn , it tafoegjen fan de mooglikheid om eleminten út in set te ferwiderjen.
Batterij logyske struktuer
De batterijsellen binne arranzjearre yn in bosk fan ideale binêre beammen. Beammen wurde oardere op hichte. Dizze foarstelling waard keazen as de meast fisuele en lit jo de gearfoeging fan beammen sjen by operaasjes op 'e batterij.
De skriuwer merkt op dat, om't alle beammen yn 'e bosk ideaal binne, har hichte wurdt útdrukt as in krêft fan twa, lykas elk natuerlik getal kin wurde fertsjintwurdige as in som fan machten fan twa. Dêrtroch kin elke set blêden wurde groepeare yn binêre beammen, en yn alle gefallen fereasket it tafoegjen fan in nij elemint kennis allinnich oer de woartelknooppunten fan opsleine beammen.
Sa is de opsleine fertsjintwurdiging fan 'e Utreexo-akkumulator in list mei rootknooppunten (Merkle-root), en net it hiele bosk fan beammen.
Litte wy de list mei root-eleminten fertsjintwurdigje as Vec<Option<Hash>>. Opsjoneel type Option<Hash> jout oan dat it root-elemint miskien ûntbrekt, wat betsjut dat der gjin beam is mei de passende hichte yn 'e accumulator.
/// 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],
}
}
}It tafoegjen fan eleminten
Lit ús earst de funksje beskriuwe parent(), dy't it âlderknooppunt erkent foar twa opjûne eleminten.
parent() funksje
Om't wy Merkle-beammen brûke, is de âlder fan elk fan 'e twa knooppunten ien knooppunt dy't de hash fan' e gearhing fan 'e hashes fan 'e berneknooppunten opslaat:
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[..])
}De auteur merkt op dat om de oanfallen te foarkommen beskreaun troch Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, en Sebastien Zimmer yn
, neist de twa hashes, moat de hichte binnen de beam ek tafoege wurde oan de gearhing.
As jo eleminten tafoegje oan 'e accumulator, moatte jo byhâlde hokker root-eleminten feroare wurde. Troch it paad te folgjen om de root-eleminten te feroarjen foar elk elemint dat jo tafoegje, kinne jo letter in bewiis konstruearje foar de oanwêzigens fan dizze eleminten.
Folgje feroarings as jo se tafoegje
Om de makke wizigingen te folgjen, litte wy de struktuer ferklearje Update, dy't gegevens oer knooppuntwizigingen opslaan.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Om in elemint oan 'e batterij ta te foegjen, moatte jo:
- Meitsje in array fan kuorren fan woarteleleminten
new_rootsen pleats de besteande root-eleminten dêr, ien foar elke bak:
koade
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);
}- Foegje de eleminten ta dy't wurde tafoege (array
insertions) nei de earste karrenew_roots[0]:
koade
new_roots[0].extend_from_slice(insertions);- Kombinearje de items tafoege oan 'e earste koer mei de rest:
- Foar alle karren mei mear dan ien artikel:
- Nim twa eleminten út 'e ein fan' e koer, berekkenje harren âlder, fuortsmite beide eleminten
- Foegje de berekkene âlder ta oan de folgjende karre
- Foar alle karren mei mear dan ien artikel:
koade
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 });
}
}- Ferpleats root-eleminten fan bakken nei resultearjende accumulator-array
koade
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]);
}
}It meitsjen fan in bewiis foar tafoege eleminten
Bewiis fan opnimmen fan 'e sel yn' e batterij (Proof) sil tsjinje as it Merkle Paad, besteande út in keatling ProofStep. As it paad nearne hinne liedt, dan is it bewiis ferkeard.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}It brûken fan de earder krigen ynformaasje by it tafoegjen fan in elemint (struktuer Update), kinne jo bewiis meitsje dat in elemint is tafoege oan 'e batterij. Om dit te dwaan, geane wy troch de tabel mei makke wizigingen en foegje elke stap ta oan Merkle's paad, dy't letter as bewiis sil tsjinje:
koade
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
}
}Proses foar it meitsjen fan in bewiis
Kontrolearje it bewiis foar in elemint
It kontrolearjen fan it ynklúzjebewiis fan in elemint komt del op it folgjen fan it Merkle-paad oant it liedt ta in besteande root-elemint:
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
}
}Visueel:
Proses foar it kontrolearjen fan it bewiis foar A
It fuortsmiten fan items
Om in sel fan in batterij te ferwiderjen, moatte jo jildich bewiis leverje dat de sel der is. Mei de gegevens fan it bewiis is it mooglik om nije root-eleminten fan 'e accumulator te berekkenjen wêrfoar it opjûne bewiis net mear wier is.
It algoritme is as folgjend:
- Lykas by tafoeging, organisearje wy in set lege kuorren dy't oerienkomme mei Merkle-beammen mei in hichte gelyk oan de krêft fan twa út 'e basket-yndeks
- Wy ynfoegje eleminten út 'e stappen fan' e Merkle paad yn 'e kuorren; de basket yndeks is lyk oan it nûmer fan de hjoeddeiske stap
- Wy fuortsmite it root elemint dêr't it paad fan it bewiis liedt
- Lykas by it tafoegjen, berekkenje wy nije root-eleminten troch kombinearjen fan eleminten út kuorren yn pearen en ferpleatse it resultaat fan 'e uny nei de folgjende koer
koade
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;
}
}It proses fan it fuortheljen fan elemint "A":
Yntegraasje yn in besteand netwurk
Mei it brûken fan de foarstelde accumulator kinne knopen it brûken fan in DB foarkomme om alle UTXO's op te slaan, wylst se de UTXO-set noch kinne feroarje. It probleem fan wurkjen mei bewiis ûntstiet lykwols.
Litte wy it validatorknooppunt neame dy't de UTXO-akkumulator brûkt kompakt (kompakt-state node), en de validator sûnder in accumulator is folslein (folsleine knooppunt). It bestean fan twa klassen fan knooppunten makket in probleem foar it yntegrearjen fan se yn ien netwurk, om't kompakte knooppunten bewiis fereaskje fan it bestean fan UTXO's, dy't wurde bestege oan transaksjes, wylst folsleine knooppunten net dogge. As alle netwurkknooppunten net tagelyk en op in koördinearre manier oerskeakelje nei it brûken fan Utreexo, dan wurde kompakte knopen efterlitten en kinne net operearje op it Bitcoin-netwurk.
Om it probleem op te lossen fan it yntegrearjen fan kompakte knopen yn it netwurk, wurdt foarsteld om in ekstra klasse fan knopen yn te fieren - brêgen. In brêgeknooppunt is in folsleine knooppunt dat ek de Utreexo-batterij en power-on-bewiis opslacht foar всех UTXO fan UTXO-set. Brêgen berekkenje nije hashes en aktualisearje de accumulator en bewizen as nije blokken fan transaksjes oankomme. It behâlden en bywurkjen fan de accumulator en bewizen leit gjin ekstra berekkeningslast op op sokke knopen. Brêgen offerje skiifromte op: moatte dingen organisearre hâlde hashes, ferlike mei hashes foar kompakte knopen, wêrby't n de krêft is fan 'e UTXO-set.
Netwurk arsjitektuer
Brêgen meitsje it mooglik om stadichoan kompakte knopen ta te foegjen oan it netwurk sûnder de software fan besteande knopen te feroarjen. Folsleine knopen operearje lykas earder, en fersprieden transaksjes en blokken ûnderinoar. Brêge knopen binne folsleine knopen dy't boppedat opslaan Utreexo batterij gegevens en in set fan inclusion bewiis foar всех UTXO foar no. It brêgeknooppunt advertearret himsels net as sadanich, en docht as in folsleine knooppunt foar alle folsleine knooppunten en in kompakt knooppunt foar alle kompakte. Hoewol't brêgen beide netwurken meiinoar ferbine, hoege se se eins mar yn ien rjochting te ferbinen: fan besteande folsleine knopen oant kompakte knopen. Dit is mooglik om't it transaksjeformaat net feroare wurde moat, en UTXO-bewiis foar kompakte knooppunten kinne wurde wegere, sadat elke kompakte knooppunt op deselde manier transaksjes kin útstjoere nei alle netwurkdielnimmers sûnder de dielname fan brêgeknooppunten.
konklúzje
Wy seagen nei de Utreexo-batterij en ymplementearre har prototype yn Rust. Wy seagen nei de netwurkarsjitektuer dy't de yntegraasje fan batterij-basearre knopen mooglik makket. It foardiel fan kompakte fangen is de grutte fan 'e opsleine gegevens, dy't logaritmysk hinget fan' e krêft fan 'e set UTXO's, dy't de easken foar skiifromte en opslachprestaasjes foar sokke knopen sterk ferminderet. It neidiel is it ekstra knooppuntferkear foar it ferstjoeren fan bewizen, mar techniken foar bewiisaggregation (as ien bewiis it bestean fan ferskate eleminten bewiist) en caching kinne helpe om ferkear binnen akseptabele grinzen te hâlden.
referinsjes:
- -
Boarne: www.habr.com