Hej Habr!
I Bitcoin-netværket er alle noder, gennem konsensus, enige om et sæt UTXO'er: hvor mange mønter er tilgængelige for forbrug, til hvem præcist, og under hvilke betingelser. UTXO-sættet er det minimumssæt af data, der kræves for en valideringsnode, uden hvilken noden ikke vil være i stand til at verificere gyldigheden af indgående transaktioner og de blokke, der indeholder dem.
I denne forbindelse forsøges der på alle mulige måder at reducere den lagrede repræsentation af dette sæt, for at komprimere det uden at miste sikkerhedsgarantier. Jo mindre mængden af lagrede data er, jo lavere er diskpladskravene for validatornoden, hvilket gør lanceringen af en validator node billig, giver dig mulighed for at udvide netværket og derved øge netværkets stabilitet.
I dette indlæg vil vi poste en Rust-prototype af et nyligt forslag fra en medforfatter , — , som gør det muligt at reducere krav til diskplads for validatornoder.
Hvad er problemet?
Et af Bitcoins mangeårige problemer har været dets skalerbarhed. Ideen om "din egen bank" kræver, at netværksdeltagere fører optegnelser over alle midler, der er tilgængelige til brug. I Bitcoin udtrykkes tilgængelige midler som et sæt af ubrugte output - et UTXO-sæt. Selvom dette ikke er en særlig intuitiv repræsentation, er det fordelagtigt med hensyn til implementeringsydelse i forhold til en repræsentation, hvor hver "pung" har en "saldo" som en separat post og tilføjer også privatliv (f.eks. ).
Det er vigtigt at skelne mellem transaktionernes historie (det der kaldes blockchain) og systemets aktuelle tilstand. Bitcoin transaktionshistorik optager i øjeblikket omkring 200 GB diskplads og fortsætter med at vokse. Systemtilstanden er dog meget mindre, i størrelsesordenen 4 GB, og tager kun højde for det faktum, at nogen i øjeblikket ejer mønter. Mængden af disse data stiger også over tid, men med en meget langsommere hastighed og har nogle gange endda tendens til at falde (se CDPV).
Lette klienter (SPV'er) bytter sikkerhedsgarantier for muligheden for at lagre ingen minimumstilstand (UTXO-sæt) ud over private nøgler.
UTXO og UTXO-sæt
UTXO (Unspent Transaction Output) er det ubrugte transaktionsoutput, slutpunktet på rejsen for hver Satoshi, der overføres i transaktioner. Ubrugte output bliver input til nye transaktioner og bliver dermed brugt (forbrug) og fjernet fra UTXO-sættet.
Nye UTXO'er oprettes altid af transaktioner:
- coinbase-transaktioner uden input: Opret nye UTXO'er, når minearbejdere udsteder mønter
- regelmæssige transaktioner: Opret nye UTXO'er, mens du bruger et bestemt sæt eksisterende UTXO'er
Processen med at arbejde med UTXO:
Tegnebøger tæller antallet af tilgængelige mønter (saldo) baseret på mængden af UTXO, der er tilgængelig for denne tegnebog.
Hver valideringsnode skal overvåge sættet for at forhindre dobbelte forbrugsforsøg Alle UTXO ved kontrol hver transaktioner hver blok.
Noden skal have logik:
- Tilføjelser til UTXO-sæt
- Sletninger fra UTXO-sæt
- Kontrol af tilstedeværelsen af en enkelt UTXO i et sæt
Der er måder at reducere kravene til lagret information om et sæt på, samtidig med at man bevarer muligheden for at tilføje og fjerne elementer, kontrollere og bevise eksistensen af et element i et sæt vha. .
Batterier til UTXO
Ideen om at bruge batterier til at opbevare flere UTXO'er .
UTXO-sættet er bygget på farten, under den indledende blokdownload (IBD), gemt fuldt ud og permanent, mens dets indhold ændres efter behandling af transaktioner fra hver ny og korrekt blok af netværket. Denne proces kræver download af cirka 200 GB blokdata og verifikation af hundreder af millioner af digitale signaturer. Efter IBD-processen er afsluttet, er den nederste linje, at UTXO-sættet vil optage omkring 4 GB.
Men med akkumulatorer reduceres reglerne for konsensus for midler til verifikation og generering af kryptografiske beviser, og byrden med at spore tilgængelige midler flyttes til ejeren af disse midler, som beviser deres eksistens og ejerskab.
En akkumulator kan kaldes en kompakt repræsentation af et sæt. Størrelsen af den lagrede repræsentation skal enten være konstant , eller øges sublineært med hensyn til sættets kardinalitet og størrelsen af selve elementet, f.eks. , hvor n er kardinaliteten af det lagrede sæt.
I dette tilfælde bør akkumulatoren gøre det muligt at generere et bevis for inkludering af et element i sættet (inklusionsbevis) og gøre det muligt effektivt at verificere dette bevis.
Batteriet kaldes dynamisk hvis giver dig mulighed for at tilføje elementer og fjerne elementer fra et sæt.
Et eksempel på et sådant batteri ville være . En sådan akkumulator har en konstant størrelse af lagret repræsentation, men kræver tilstedeværelse delt hemmelighed (pålidelig opsætning). Dette krav negerer anvendeligheden af en sådan akkumulator for tillidsløse netværk som Bitcoin, da datalækage under hemmelig generering kan give angribere mulighed for at skabe falske beviser for eksistensen af en UTXO, og bedrage noder med et UTXO-sæt baseret på en sådan akkumulator.
Utreexo
Utreexo-designet foreslået af Thaddeus Dryja gør det muligt at skabe dynamisk batteri без betroet-setup.
Utreexo er en skov af perfekt binær og er en udvikling af de ideer, der præsenteres i , tilføjer muligheden for at fjerne elementer fra et sæt.
Batteriets logiske struktur
Battericellerne er arrangeret i en skov af ideelle binære træer. Træer er sorteret efter højde. Denne repræsentation blev valgt som den mest visuelle og giver dig mulighed for at visualisere sammensmeltningen af træer under operationer på batteriet.
Forfatteren bemærker, at da alle træerne i skoven er ideelle, er deres højde udtrykt som en potens af to, ligesom ethvert naturligt tal kan repræsenteres som en sum af potenser af to. Derfor kan ethvert sæt blade grupperes i binære træer, og i alle tilfælde kræver det viden at tilføje et nyt element kun om rodknuderne på lagrede træer.
Således er den lagrede repræsentation af Utreexo-akkumulatoren en liste over rodknuder (Merkle-rod), og ikke hele skoven af træer.
Lad os repræsentere listen over rodelementer som Vec<Option<Hash>>. Valgfri type Option<Hash> angiver, at rodelementet kan mangle, hvilket betyder, at der ikke er et træ med passende højde i akkumulatoren.
/// 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],
}
}
}Tilføjelse af elementer
Lad os først beskrive funktionen parent(), som genkender den overordnede node for to givne elementer.
parent() funktion
Da vi bruger Merkle-træer, er forælderen til hver af de to noder én node, der gemmer hashen for sammenkædningen af hasherne for de underordnede noder:
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[..])
}Forfatteren bemærker, at for at forhindre angrebene beskrevet af Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir og Sebastien Zimmer i
, ud over de to hashes, skal højden inde i træet også føjes til sammenkædningen.
Når du tilføjer elementer til akkumulatoren, skal du holde styr på, hvilke rodelementer der ændres. Ved at følge stien til at ændre rodelementerne for hvert element, du tilføjer, kan du senere konstruere et bevis for tilstedeværelsen af disse elementer.
Spor ændringer, efterhånden som du tilføjer dem
For at spore ændringerne, lad os erklære strukturen Update, som vil gemme data om nodeændringer.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}For at tilføje et element til batteriet skal du bruge:
- Opret en række kurve af rodelementer
new_rootsog placer de eksisterende rodelementer der, en for hver spand:
Kode
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);
}- Tilføj de elementer, der skal tilføjes (array
insertions) til den første vognnew_roots[0]:
Kode
new_roots[0].extend_from_slice(insertions);- Kombiner de varer, der er tilføjet til den første kurv, med resten:
- For alle vogne med mere end én vare:
- Tag to elementer fra enden af kurven, beregn deres overordnede, fjern begge elementer
- Tilføj den beregnede forælder til den næste indkøbskurv
- For alle vogne med mere end én vare:
Kode
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 });
}
}- Flyt rodelementer fra bins til resulterende akkumulatorarray
Kode
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]);
}
}Oprettelse af et bevis for tilføjede elementer
Bevis for inkludering af cellen i batteriet (Proof) vil fungere som Merkle-stien, der består af en kæde ProofStep. Hvis stien ikke fører nogen vegne, så er beviset forkert.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Brug af de oplysninger, der er opnået tidligere, når du tilføjer et element (struktur Update), kan du oprette bevis for, at et element er blevet tilføjet til batteriet. For at gøre dette gennemgår vi tabellen over foretagne ændringer og tilføjer hvert trin til Merkles vej, som efterfølgende vil tjene som bevis:
Kode
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 med at skabe et bevis
Kontrol af beviset for et element
At kontrollere et elements inklusionsbevis går ned til at følge Merkle-stien, indtil det fører til et eksisterende rodelement:
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
}
}Visuelt:
Processen med at kontrollere beviset for A
Fjernelse af genstande
For at fjerne en celle fra et batteri skal du fremlægge gyldig dokumentation for, at cellen er der. Ved hjælp af data fra beviset er det muligt at beregne nye rodelementer i akkumulatoren, for hvilke det givne bevis ikke længere vil være sandt.
Algoritmen er følgende:
- Som med tilføjelse organiserer vi et sæt tomme kurve svarende til Merkle træer med en højde svarende til to potens fra kurvindekset
- Vi indsætter elementer fra Merkle-stiens trin i kurvene; kurvindekset er lig med nummeret på det aktuelle trin
- Vi fjerner rodelementet, som stien fra beviset fører til
- Som med tilføjelse, beregner vi nye rodelementer ved at kombinere elementer fra kurve i par og flytte resultatet af foreningen til den næste kurv
Kode
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;
}
}Processen med at fjerne element "A":
Integration i et eksisterende netværk
Ved at bruge den foreslåede akkumulator kan noder undgå at bruge en DB til at gemme alle UTXO'er, mens de stadig er i stand til at ændre UTXO-sættet. Men problemet med at arbejde med beviser opstår.
Lad os kalde valideringsnoden, der bruger UTXO-akkumulatoren kompakt (compact-state node), og validatoren uden en akkumulator er komplet (fuld knude). Eksistensen af to klasser af noder skaber et problem for at integrere dem i et enkelt netværk, da kompakte noder kræver bevis for eksistensen af UTXO'er, som bruges i transaktioner, mens fulde noder ikke gør det. Hvis ikke alle netværksknuder samtidig og på en koordineret måde skifter til at bruge Utreexo, vil kompakte noder blive efterladt og vil ikke kunne operere på Bitcoin-netværket.
For at løse problemet med at integrere kompakte noder i netværket foreslås det at indføre en ekstra klasse af noder - broer. En broknude er en komplet node, der også gemmer Utreexo-batteriet og power-on proof for Alle UTXO fra UTXO-sæt. Bridges beregner nye hashes og opdaterer akkumulatoren og beviserne, efterhånden som nye blokke af transaktioner ankommer. Vedligeholdelse og opdatering af akkumulatoren og beviserne pålægger ikke sådanne noder yderligere beregningsbelastning. Broer ofrer diskplads: behov for at holde tingene organiseret hash, i forhold til hashes for kompakte noder, hvor n er UTXO-sættets effekt.
Netværksarkitektur
Broer gør det muligt gradvist at tilføje kompakte noder til netværket uden at ændre softwaren på eksisterende noder. Fuld noder fungerer som før og distribuerer transaktioner og blokke indbyrdes. Bridge noder er fulde noder, der desuden gemmer Utreexo-batteridata og et sæt inklusionsbeviser for Alle UTXO lige nu. Broknuden annoncerer ikke sig selv som sådan, idet den foregiver at være en fuld knude for alle fulde knudepunkter og en kompakt knude for alle kompakte. Selvom broer forbinder begge netværk sammen, behøver de faktisk kun at forbinde dem i én retning: fra eksisterende fulde noder til kompakte noder. Dette er muligt, fordi transaktionsformatet ikke skal ændres, og UTXO-beviser for kompakte noder kan kasseres, så enhver kompakt node kan på samme måde udsende transaktioner til alle netværksdeltagere uden deltagelse af broknuder.
Konklusion
Vi så på Utreexo-batteriet og implementerede dets prototype i Rust. Vi så på netværksarkitekturen, der vil tillade integration af batteribaserede noder. Fordelen ved kompakte fangster er størrelsen af de lagrede data, som logaritmisk afhænger af kraften i sættet af UTXO'er, hvilket i høj grad reducerer kravene til diskplads og lagerydeevne for sådanne noder. Ulempen er den ekstra nodetrafik til overførsel af beviser, men bevisaggregeringsteknikker (når ét bevis beviser eksistensen af flere elementer) og caching kan hjælpe med at holde trafikken inden for acceptable grænser.
RЎSЃS <P "RєRё:
- —
Kilde: www.habr.com