Hej Habr!
Në rrjetin Bitcoin, të gjitha nyjet, përmes konsensusit, bien dakord për një grup UTXO: sa monedha janë të disponueshme për shpenzim, kujt saktësisht dhe në çfarë kushtesh. Seti UTXO është grupi minimal i të dhënave të kërkuara për një nyje vleftësuese, pa të cilën nyja nuk do të jetë në gjendje të verifikojë vlefshmërinë e transaksioneve hyrëse dhe blloqeve që i përmbajnë ato.
Në këtë drejtim, po tentohet në çdo mënyrë për të reduktuar përfaqësimin e ruajtur të këtij grupi, për ta ngjeshur atë pa humbur garancitë e sigurisë. Sa më i vogël të jetë vëllimi i të dhënave të ruajtura, aq më të ulëta janë kërkesat e hapësirës në disk të nyjes së verifikuesit, gjë që e bën të lirë nisjen e një nyje verifikuesi, ju lejon të zgjeroni rrjetin dhe në këtë mënyrë të rrisni stabilitetin e rrjetit.
Në këtë postim do të postojmë një prototip Rust të një propozimi të fundit nga një bashkëautor , - , i cili lejon zvogëlimin e kërkesave të hapësirës në disk për nyjet e verifikuesit.
Cili është problemi?
Një nga problemet e përhershme të Bitcoin ka qenë shkallëzueshmëria e tij. Ideja e "bankës suaj" kërkon që pjesëmarrësit e rrjetit të mbajnë shënime për të gjitha fondet e disponueshme për përdorim. Në Bitcoin, fondet e disponueshme shprehen si një grup rezultatesh të pashpenzuara - një grup UTXO. Ndonëse ky nuk është një paraqitje veçanërisht intuitive, është e dobishme për sa i përket performancës së zbatimit mbi një përfaqësim në të cilin çdo "portofol" ka një "balancë" si një hyrje më vete, dhe gjithashtu shton privatësinë (p.sh. ).
Është e rëndësishme të bëhet dallimi midis historisë së transaksioneve (ajo që quhet blockchain) dhe gjendjes aktuale të sistemit. Historia e transaksioneve të Bitcoin aktualisht zë rreth 200 GB hapësirë në disk dhe vazhdon të rritet. Sidoqoftë, gjendja e sistemit është shumë më e vogël, në rendin e 4 GB, dhe merr parasysh vetëm faktin që dikush aktualisht zotëron monedha. Vëllimi i këtyre të dhënave gjithashtu rritet me kalimin e kohës, por me një ritëm shumë më të ngadaltë dhe ndonjëherë edhe tenton të ulet (shih CDPV).
Klientët e lehtë (SPV) tregtojnë garanci sigurie për aftësinë për të ruajtur asnjë gjendje minimale (UTXO-set) përveç çelësave privatë.
UTXO dhe UTXO-set
UTXO (Unspent Transaction Output) është dalja e transaksionit të pashpenzuar, pika përfundimtare e udhëtimit të çdo Satoshi të transferuar në transaksione. Rezultatet e pashpenzuara bëhen hyrje të transaksioneve të reja dhe kështu shpenzohen (shpenzohen) dhe hiqen nga grupi UTXO.
UTXO-të e reja krijohen gjithmonë nga transaksionet:
- Transaksionet coinbase pa hyrje: krijoni UTXO të reja kur minatorët lëshojnë monedha
- transaksione të rregullta: krijoni UTXO të reja ndërsa shpenzoni një grup të caktuar UTXO ekzistuese
Procesi i punës me UTXO:
Kuletat numërojnë numrin e monedhave të disponueshme për shpenzim (balanca) bazuar në sasinë e UTXO të disponueshme për këtë portofol për shpenzim.
Çdo nyje e vlefshmërisë, për të parandaluar përpjekjet për shpenzime të dyfishta, duhet të monitorojë grupin Të gjithë UTXO kur kontrolloni çdo transaksionet i secilit bllokoj.
Nyja duhet të ketë logjikë:
- Shtesa në grupin UTXO
- Fshirje nga grupi UTXO
- Kontrollimi i pranisë së një UTXO të vetme në një grup
Ka mënyra për të reduktuar kërkesat për informacionin e ruajtur në lidhje me një grup, duke ruajtur aftësinë për të shtuar dhe hequr elementë, për të kontrolluar dhe vërtetuar ekzistencën e një elementi në një grup duke përdorur .
Bateri për UTXO
Ideja e përdorimit të baterive për të ruajtur shumë UTXO .
Seti UTXO ndërtohet në fluturim, gjatë shkarkimit fillestar të bllokut (IBD), ruhet i plotë dhe i përhershëm, ndërsa përmbajtja e tij ndryshon pas përpunimit të transaksioneve nga çdo bllok i ri dhe korrekt i rrjetit. Ky proces kërkon shkarkimin e afërsisht 200 GB të të dhënave të bllokut dhe verifikimin e qindra miliona nënshkrimeve dixhitale. Pasi të përfundojë procesi IBD, në fund të fundit është se grupi UTXO do të zërë rreth 4 GB.
Megjithatë, me akumulatorët, rregullat e konsensusit për fondet reduktohen në verifikimin dhe gjenerimin e provave kriptografike, dhe barra e gjurmimit të fondeve të disponueshme i kalon pronarit të atyre fondeve, i cili siguron prova për ekzistencën dhe pronësinë e tyre.
Një akumulator mund të quhet një paraqitje kompakte e një grupi. Madhësia e paraqitjes së ruajtur duhet të jetë ose konstante , ose rritet në mënyrë nënlineare në lidhje me kardinalitetin e grupit dhe madhësinë e vetë elementit, për shembull , ku n është kardinaliteti i grupit të ruajtur.
Në këtë rast, akumulatori duhet të lejojë gjenerimin e një prove për përfshirjen e një elementi në grup (prova e përfshirjes) dhe të bëjë të mundur verifikimin efektiv të kësaj prove.
Bateria quhet dinamik nëse ju lejon të shtoni elementë dhe të hiqni elementë nga një grup.
Një shembull i një baterie të tillë do të ishte . Një akumulator i tillë ka një madhësi konstante të përfaqësimit të ruajtur, por kërkon praninë sekret i përbashkët (konfigurim i besuar). Kjo kërkesë mohon zbatueshmërinë e një akumuluesi të tillë për rrjetet e pabesueshme si Bitcoin, pasi rrjedhja e të dhënave gjatë gjenerimit të fshehtë mund t'i lejojë sulmuesit të krijojnë prova të rreme të ekzistencës së një UTXO, duke mashtruar nyjet me një grup UTXO të bazuar në një akumulator të tillë.
Utreexo
Dizajni Utreexo i propozuar nga Thaddeus Dryja bën të mundur krijimin dinamike аккумулятор pa konfigurim i besuar.
Utreexo është një pyll i përsosur binare dhe është një zhvillim i ideve të paraqitura në , duke shtuar aftësinë për të hequr elementët nga një grup.
Struktura logjike e baterisë
Qelizat e baterisë janë të vendosura në një pyll me pemë binare ideale. Pemët renditen sipas lartësisë. Ky paraqitje u zgjodh si më vizuale dhe ju lejon të vizualizoni bashkimin e pemëve gjatë operacioneve në bateri.
Autori vëren se meqenëse të gjitha pemët në pyll janë ideale, lartësia e tyre shprehet si fuqia e dy, ashtu si çdo numër natyror mund të përfaqësohet si një shumë e fuqive të dy. Prandaj, çdo grup gjethesh mund të grupohet në pemë binare, dhe në të gjitha rastet, shtimi i një elementi të ri kërkon njohuri vetëm për nyjet rrënjësore të pemëve të ruajtura.
Kështu, përfaqësimi i ruajtur i akumulatorit Utreexo është një listë e nyjeve rrënjësore (rrënja Merkle), dhe jo i gjithë pylli me pemë.
Le të paraqesim listën e elementeve rrënjë si Vec<Option<Hash>>. Lloji opsional Option<Hash> tregon se elementi rrënjë mund të mungojë, që do të thotë se nuk ka pemë me lartësinë e duhur në akumulator.
/// 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],
}
}
}Shtimi i elementeve
Së pari, le të përshkruajmë funksionin parent(), e cila njeh nyjen mëmë për dy elementë të dhënë.
funksioni prind().
Meqenëse po përdorim pemët Merkle, prindi i secilës prej dy nyjeve është një nyje që ruan hash-in e lidhjes së hasheve të nyjeve fëmijë:
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[..])
}Autori vëren se për të parandaluar sulmet e përshkruara nga Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir dhe Sebastien Zimmer në
, përveç dy hasheve, në lidhje duhet t'i shtohet edhe lartësia brenda pemës.
Ndërsa shtoni elementë në akumulator, duhet të mbani shënim se cilët elementë rrënjë janë ndryshuar. Duke ndjekur rrugën e ndryshimit të elementeve rrënjë për çdo element që shtoni, më vonë mund të ndërtoni një provë të pranisë së këtyre elementeve.
Ndiqni ndryshimet ndërsa i shtoni
Për të ndjekur ndryshimet e bëra, le të deklarojmë strukturën Update, i cili do të ruajë të dhënat për ndryshimet e nyjeve.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Për të shtuar një element në bateri, ju duhet:
- Krijo një sërë shportash me elementë rrënjë
new_rootsdhe vendosni elementët rrënjë ekzistues atje, një për çdo kovë:
Kod
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);
}- Shtojini elementet që do të shtohen (array
insertions) në karrocën e parënew_roots[0]:
Kod
new_roots[0].extend_from_slice(insertions);- Bashkoni artikujt e shtuar në shportën e parë me pjesën tjetër:
- Për të gjitha karrocat me më shumë se një artikull:
- Merrni dy elementë nga fundi i shportës, llogarisni prindin e tyre, hiqni të dy elementët
- Shtoni prindin e llogaritur në karrocën tjetër
- Për të gjitha karrocat me më shumë se një artikull:
Kod
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 });
}
}- Zhvendosni elementët rrënjë nga kazanët në grupin akumulues që rezulton
Kod
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]);
}
}Krijimi i një prove për elementët e shtuar
Dëshmia e përfshirjes së qelizës në bateri (Proof) do të shërbejë si Rruga Merkle, e përbërë nga një zinxhir ProofStep. Nëse rruga nuk të çon askund, atëherë prova është e pasaktë.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Përdorimi i informacionit të marrë më herët kur shtoni një element (strukturë Update), mund të krijoni prova që një element është shtuar në bateri. Për ta bërë këtë, ne kalojmë në tabelën e ndryshimeve të bëra dhe shtojmë çdo hap në rrugën e Merkle, e cila më pas do të shërbejë si provë:
Kod
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
}
}Procesi i krijimit të një prove
Kontrollimi i provës për një element
Kontrollimi i provës së përfshirjes së një elementi përfundon në ndjekjen e shtegut Merkle derisa të çojë në një element rrënjë ekzistues:
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
}
}Vizualisht:
Procesi i kontrollit të provës për A
Heqja e artikujve
Për të hequr një qelizë nga një bateri, duhet të siguroni prova të vlefshme që qeliza është atje. Duke përdorur të dhënat nga prova, është e mundur të llogariten elementë të rinj rrënjë të akumulatorit për të cilët prova e dhënë nuk do të jetë më e vërtetë.
Algoritmi është si më poshtë:
- Ashtu si me shtesë, ne organizojmë një grup koshash boshe që korrespondojnë me pemët Merkle me një lartësi të barabartë me fuqinë e dy nga indeksi i shportës
- Ne futim elementë nga hapat e shtegut Merkle në shporta; indeksi i shportës është i barabartë me numrin e hapit aktual
- Ne heqim elementin rrënjë në të cilin të çon rruga nga prova
- Ashtu si me shtimin, ne llogarisim elemente të reja rrënjësore duke kombinuar elementë nga shportat në çifte dhe duke lëvizur rezultatin e bashkimit në shportën tjetër.
Kod
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;
}
}Procesi i heqjes së elementit "A":
Integrimi në një rrjet ekzistues
Duke përdorur akumulatorin e propozuar, nyjet mund të shmangin përdorimin e një DB për të ruajtur të gjitha UTXO-të duke qenë ende në gjendje të ndryshojnë grupin UTXO. Megjithatë, lind problemi i punës me prova.
Le të thërrasim nyjen e vlefshmërisë që përdor akumulatorin UTXO kompakte (nyja e gjendjes kompakte), dhe validatori pa akumulator është i plotë (nyja e plotë). Ekzistenca e dy klasave të nyjeve krijon një problem për integrimin e tyre në një rrjet të vetëm, pasi nyjet kompakte kërkojnë prova të ekzistencës së UTXO-ve, të cilat shpenzohen në transaksione, ndërsa nyjet e plota jo. Nëse të gjitha nyjet e rrjetit nuk kalojnë njëkohësisht dhe në mënyrë të koordinuar në përdorimin e Utreexo, atëherë nyjet kompakte do të lihen pas dhe nuk do të mund të funksionojnë në rrjetin Bitcoin.
Për të zgjidhur problemin e integrimit të nyjeve kompakte në rrjet, propozohet të futet një klasë shtesë e nyjeve - urat. Një nyje urë është një nyje e plotë që ruan gjithashtu baterinë Utreexo dhe provën e ndezjes Të gjithë UTXO nga grupi UTXO. Urat llogaritin hash-et e reja dhe përditësojnë akumulatorin dhe provat ndërsa mbërrijnë blloqe të reja transaksionesh. Mirëmbajtja dhe përditësimi i akumulatorit dhe provave nuk imponon ngarkesë llogaritëse shtesë në nyje të tilla. Urat sakrifikojnë hapësirën në disk: duhet t'i mbani gjërat të organizuara hash, në krahasim me hash për nyjet kompakte, ku n është fuqia e grupit UTXO.
Arkitektura e rrjetit
Urat bëjnë të mundur shtimin gradualisht të nyjeve kompakte në rrjet pa ndryshuar softuerin e nyjeve ekzistuese. Nyjet e plota funksionojnë si më parë, duke shpërndarë transaksione dhe blloqe ndërmjet tyre. Nyjet e urës janë nyje të plota që ruajnë gjithashtu të dhënat e baterisë Utreexo dhe një grup provash përfshirjeje për Të gjithë UTXO tani për tani. Nyja e urës nuk e reklamon veten si e tillë, duke pretenduar të jetë një nyje e plotë për të gjitha nyjet e plota dhe një nyje kompakte për të gjitha ato kompakte. Megjithëse urat lidhin të dy rrjetet së bashku, ato në fakt duhet t'i lidhin ato vetëm në një drejtim: nga nyjet ekzistuese të plota në nyjet kompakte. Kjo është e mundur sepse formati i transaksionit nuk ka nevojë të ndryshohet dhe provat UTXO për nyjet kompakte mund të hidhen poshtë, kështu që çdo nyje kompakte mund të transmetojë transaksione në mënyrë të ngjashme për të gjithë pjesëmarrësit e rrjetit pa pjesëmarrjen e nyjeve të urës.
Përfundim
Ne shikuam baterinë Utreexo dhe zbatuam prototipin e saj në Rust. Ne shikuam arkitekturën e rrjetit që do të lejojë integrimin e nyjeve të bazuara në bateri. Avantazhi i kapjes kompakte është madhësia e të dhënave të ruajtura, e cila varet logaritmikisht nga fuqia e grupit të UTXO-ve, gjë që redukton shumë kërkesat për hapësirën në disk dhe performancën e ruajtjes për nyje të tilla. Disavantazhi është trafiku shtesë i nyjeve për transmetimin e provave, por teknikat e grumbullimit të provave (kur një provë vërteton ekzistencën e disa elementeve) dhe caching mund të ndihmojnë në mbajtjen e trafikut brenda kufijve të pranueshëm.
Referencat:
- -
Burimi: www.habr.com