Hei Habr!
I Bitcoin-nettverket er alle noder, gjennom konsensus, enige om et sett med UTXOer: hvor mange mynter er tilgjengelige for utgifter, til hvem nøyaktig, og under hvilke forhold. UTXO-settet er minimumssettet med data som kreves for en validatornode, uten hvilken noden ikke vil være i stand til å verifisere gyldigheten av innkommende transaksjoner og blokkene som inneholder dem.
I denne forbindelse forsøkes det på alle mulige måter å redusere den lagrede representasjonen av dette settet, for å komprimere det uten å miste sikkerhetsgarantier. Jo mindre volumet av lagrede data er, desto lavere er diskplasskravene til validatornoden, noe som gjør lansering av en validatornode billig, lar deg utvide nettverket og dermed øke stabiliteten til nettverket.
I dette innlegget vil vi legge ut en Rust-prototype av et nylig forslag fra en medforfatter , - , som gjør det mulig å redusere krav til diskplass for validatornoder.
Hva er problemet?
Et av Bitcoins mangeårige problemer har vært skalerbarheten. Ideen om "din egen bank" krever at nettverksdeltakere fører oversikt over alle midler som er tilgjengelige for bruk. I Bitcoin uttrykkes tilgjengelige midler som et sett med ubrukte utganger - et UTXO-sett. Selv om dette ikke er en spesielt intuitiv representasjon, er det fordelaktig med tanke på implementeringsytelse fremfor en representasjon der hver "lommebok" har en "saldo" som en separat oppføring, og legger også til personvern (f.eks. ).
Det er viktig å skille mellom historien til transaksjoner (det som kalles blokkjeden) og den nåværende tilstanden til systemet. Bitcoin transaksjonshistorikk opptar for øyeblikket omtrent 200 GB diskplass, og fortsetter å vokse. Systemtilstanden er imidlertid mye mindre, i størrelsesorden 4 GB, og tar kun hensyn til det faktum at noen for øyeblikket eier mynter. Volumet av disse dataene øker også over tid, men med en mye langsommere hastighet og har noen ganger til og med en tendens til å avta (se CDPV).
Lette klienter (SPV-er) bytter sikkerhetsgarantier for muligheten til å ikke lagre noen minimumstilstand (UTXO-sett) annet enn private nøkler.
UTXO og UTXO-sett
UTXO (Unspent Transaction Output) er den ubrukte transaksjonsutgangen, endepunktet på reisen til hver Satoshi som overføres i transaksjoner. Ubrukte utdata blir innganger til nye transaksjoner og blir dermed brukt (spend) og fjernet fra UTXO-settet.
Nye UTXO-er opprettes alltid av transaksjoner:
- myntbase-transaksjoner uten innganger: lag nye UTXO-er når gruvearbeidere utsteder mynter
- vanlige transaksjoner: opprett nye UTXO-er mens du bruker et visst sett med eksisterende UTXO-er
Prosessen med å jobbe med UTXO:
Lommebøker teller antall tilgjengelige mynter (saldo) basert på mengden UTXO som er tilgjengelig for denne lommeboken.
Hver validatornode må overvåke settet for å forhindre dobbeltforbruksforsøk Alle UTXO ved kontroll hver transaksjoner av hver blokkere.
Noden må ha logikk:
- Tillegg til UTXO-sett
- Slettinger fra UTXO-sett
- Kontrollerer tilstedeværelsen av en enkelt UTXO i et sett
Det finnes måter å redusere kravene til lagret informasjon om et sett på, samtidig som man opprettholder muligheten til å legge til og fjerne elementer, sjekke og bevise eksistensen av et element i et sett ved å bruke .
Batterier for UTXO
Ideen om å bruke batterier til å lagre flere UTXO-er .
UTXO-settet bygges på flukt, under den første blokknedlastingen (IBD), lagret i sin helhet og permanent, mens innholdet endres etter behandling av transaksjoner fra hver nye og riktige blokk i nettverket. Denne prosessen krever nedlasting av omtrent 200 GB blokkdata og verifisering av hundrevis av millioner digitale signaturer. Etter at IBD-prosessen er fullført, er konklusjonen at UTXO-settet vil oppta ca. 4 GB.
Med akkumulatorer reduseres imidlertid reglene for konsensus for midler til verifisering og generering av kryptografiske bevis, og byrden med å spore tilgjengelige midler flyttes til eieren av disse midlene, som gir bevis på deres eksistens og eierskap.
En akkumulator kan kalles en kompakt representasjon av et sett. Størrelsen på den lagrede representasjonen må enten være konstant , eller øke sublineært med hensyn til kardinaliteten til settet og størrelsen på selve elementet, for eksempel , hvor n er kardinaliteten til det lagrede settet.
I dette tilfellet bør akkumulatoren tillate å generere et bevis for inkludering av et element i settet (inkluderingsbevis) og gjøre det mulig å effektivt verifisere dette beviset.
Batteriet kalles dynamisk if lar deg legge til elementer og fjerne elementer fra et sett.
Et eksempel på et slikt batteri kan være . En slik akkumulator har en konstant størrelse på lagret representasjon, men krever tilstedeværelse delt hemmelighet (klarert oppsett). Dette kravet negerer anvendeligheten til en slik akkumulator for tillitsløse nettverk som Bitcoin, siden datalekkasje under hemmelig generering kan tillate angripere å skape falske bevis på eksistensen av en UTXO, og lure noder med et UTXO-sett basert på en slik akkumulator.
Utrexo
Utreexo-designet foreslått av Thaddeus Dryja gjør det mulig å lage dynamisk batteri без pålitelig oppsett.
Utreexo er en skog av perfekt binær og er en utvikling av ideene presentert i , og legger til muligheten til å fjerne elementer fra et sett.
Batteriets logiske struktur
Battericellene er arrangert i en skog av ideelle binære trær. Trær er sortert etter høyde. Denne representasjonen ble valgt som den mest visuelle og lar deg visualisere sammenslåingen av trær under operasjoner på batteriet.
Forfatteren bemerker at siden alle trærne i skogen er ideelle, er høyden deres uttrykt som en potens av to, akkurat som ethvert naturlig tall kan representeres som en sum av potenser av to. Følgelig kan ethvert sett med blader grupperes i binære trær, og i alle tilfeller krever å legge til et nytt element kunnskap bare om rotnodene til lagrede trær.
Dermed er den lagrede representasjonen av Utreexo-akkumulatoren en liste over rotnoder (Merkle-rot), og ikke hele skogen av trær.
La oss representere listen over rotelementer som Vec<Option<Hash>>. Valgfri type Option<Hash> indikerer at rotelementet kan mangle, noe som betyr at det ikke er et tre med passende høyde 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],
}
}
}Legge til elementer
Først, la oss beskrive funksjonen parent(), som gjenkjenner overordnet node for to gitte elementer.
parent() funksjon
Siden vi bruker Merkle-trær, er forelderen til hver av de to nodene én node som lagrer hashen til sammenkoblingen av hashen til undernodene:
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 bemerker at for å forhindre angrepene beskrevet av Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir og Sebastien Zimmer i
, i tillegg til de to hashene, bør høyden inne i treet også legges til sammenkoblingen.
Når du legger til elementer i akkumulatoren, må du holde styr på hvilke rotelementer som endres. Ved å følge banen for å endre rotelementene for hvert element du legger til, kan du senere konstruere et bevis på tilstedeværelsen av disse elementene.
Spor endringer etter hvert som du legger dem til
For å spore endringene som er gjort, la oss erklære strukturen Update, som vil lagre data om nodeendringer.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}For å legge til et element til batteriet trenger du:
- Lag en rekke kurver med rotelementer
new_rootsog plasser de eksisterende rotelementene der, en for hver bøtte:
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);
}- Legg til elementene som skal legges til (array
insertions) til den første vognennew_roots[0]:
Kode
new_roots[0].extend_from_slice(insertions);- Kombiner varene som er lagt i den første kurven med resten:
- For alle handlekurver med mer enn én vare:
- Ta to elementer fra enden av kurven, beregn deres overordnede, fjern begge elementene
- Legg til den beregnede forelderen i neste handlekurv
- For alle handlekurver med mer enn é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 });
}
}- Flytt rotelementer fra binger 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]);
}
}Lage et bevis for ekstra elementer
Bevis på inkludering av cellen i batteriet (Proof) vil fungere som Merkle-stien, bestående av en kjede ProofStep. Hvis veien ikke fører noe sted, er beviset feil.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Bruke informasjonen innhentet tidligere når du legger til et element (struktur Update), kan du lage bevis på at et element er lagt til batteriet. For å gjøre dette går vi gjennom tabellen over endringer som er gjort og legger til hvert trinn til Merkles vei, som deretter 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
}
}Prosess for å lage et bevis
Kontroller beviset for et element
Å sjekke et elements inklusjonsbevis koker ned til å følge Merkle-banen til det fører til et eksisterende rotelement:
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:
Prosessen med å kontrollere beviset for A
Fjerning av gjenstander
For å fjerne en celle fra et batteri, må du fremlegge gyldig bevis på at cellen er der. Ved å bruke dataene fra beviset er det mulig å beregne nye rotelementer i akkumulatoren som det gitte beviset ikke lenger vil være sant for.
Algoritmen er som følger:
- Som med tillegg, organiserer vi et sett med tomme kurver som tilsvarer Merkle-trær med en høyde lik kraften av to fra kurvindeksen
- Vi setter inn elementer fra trinnene på Merkle-stien i kurvene; kurvindeksen er lik nummeret på gjeldende trinn
- Vi fjerner rotelementet som banen fra beviset fører til
- Som med å legge til, beregner vi nye rotelementer ved å kombinere elementer fra kurver i par og flytte resultatet av foreningen til neste 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;
}
}Prosessen med å fjerne element "A":
Integrasjon i et eksisterende nettverk
Ved å bruke den foreslåtte akkumulatoren kan noder unngå å bruke en DB for å lagre alle UTXO-er mens de fortsatt kan endre UTXO-settet. Problemet med å jobbe med bevis oppstår imidlertid.
La oss kalle validatornoden som bruker UTXO-akkumulatoren kompakt (compact-state node), og validatoren uten en akkumulator er fullstendig (full node). Eksistensen av to klasser av noder skaper et problem for å integrere dem i et enkelt nettverk, siden kompakte noder krever bevis på eksistensen av UTXO-er, som brukes i transaksjoner, mens fulle noder ikke gjør det. Hvis ikke alle nettverksnoder samtidig og på en koordinert måte går over til å bruke Utreexo, vil kompakte noder bli liggende igjen og vil ikke kunne operere på Bitcoin-nettverket.
For å løse problemet med å integrere kompakte noder i nettverket, foreslås det å introdusere en ekstra klasse noder - broer. En bronode er en komplett node som også lagrer Utreexo-batteriet og oppstartssikkert for Alle UTXO fra UTXO-sett. Broer beregner nye hashes og oppdaterer akkumulatoren og bevisene etter hvert som nye blokker med transaksjoner kommer. Vedlikehold og oppdatering av akkumulatoren og bevisene påfører ikke ytterligere beregningsbelastning på slike noder. Broer ofrer diskplass: trenger å holde ting organisert hasjer, sammenlignet med hasher for kompakte noder, der n er kraften til UTXO-settet.
Nettverksarkitektur
Broer gjør det mulig å gradvis legge til kompakte noder til nettverket uten å endre programvaren til eksisterende noder. Fulle noder fungerer som før, og distribuerer transaksjoner og blokker seg imellom. Bronoder er fulle noder som i tillegg lagrer Utreexo-batteridata og et sett med inkluderingsbevis for Alle UTXO for nå. Bronoden annonserer ikke seg selv som sådan, og utgir seg for å være en full node for alle fulle noder og en kompakt node for alle kompakte. Selv om broer kobler begge nettverkene sammen, trenger de faktisk bare å koble dem i én retning: fra eksisterende fullnoder til kompakte noder. Dette er mulig fordi transaksjonsformatet ikke trenger å endres, og UTXO-bevis for kompakte noder kan forkastes, slik at enhver kompakt node på samme måte kan kringkaste transaksjoner til alle nettverksdeltakere uten deltakelse av bronoder.
Konklusjon
Vi så på Utreexo-batteriet og implementerte prototypen i Rust. Vi så på nettverksarkitekturen som vil tillate integrering av batteribaserte noder. Fordelen med kompakte fangster er størrelsen på de lagrede dataene, som logaritmisk avhenger av kraften til settet med UTXO-er, noe som i stor grad reduserer kravene til diskplass og lagringsytelse for slike noder. Ulempen er den ekstra nodetrafikken for overføring av bevis, men bevisaggregeringsteknikker (når ett bevis beviser eksistensen av flere elementer) og caching kan bidra til å holde trafikken innenfor akseptable grenser.
referanser:
- -
Kilde: www.habr.com