Haai Habr!
In die Bitcoin-netwerk stem alle nodusse, deur konsensus, ooreen oor 'n stel UTXO's: hoeveel munte is beskikbaar vir besteding, aan wie presies, en onder watter omstandighede. Die UTXO-stel is die minimum stel data wat benodig word vir 'n valideerdernodus, waarsonder die nodus nie die geldigheid van inkomende transaksies en die blokke wat dit bevat sal kan verifieer nie.
In hierdie verband word daar op elke moontlike manier gepoog om die gestoorde voorstelling van hierdie stel te verminder, om dit saam te druk sonder om sekuriteitswaarborge te verloor. Hoe kleiner die volume gestoorde data, hoe laer is die skyfspasievereistes van die validator-nodus, wat die bekendstelling van 'n validator-nodus goedkoop maak, laat jou toe om die netwerk uit te brei en sodoende die stabiliteit van die netwerk te verhoog.
In hierdie pos sal ons 'n Rust-prototipe plaas van 'n onlangse voorstel van 'n mede-outeur , - , wat die vermindering van skyfspasievereistes vir valideerdernodusse moontlik maak.
Wat is die probleem?
Een van Bitcoin se meerjarige probleme was die skaalbaarheid daarvan. Die idee van "jou eie bank" vereis dat netwerkdeelnemers rekord hou van alle fondse wat beskikbaar is vir gebruik. In Bitcoin word beskikbare fondse uitgedruk as 'n stel onbestede uitsette - 'n UTXO-stel. Alhoewel dit nie 'n besonder intuïtiewe voorstelling is nie, is dit voordelig in terme van implementeringsprestasie bo 'n voorstelling waarin elke "beursie" 'n "saldo" as 'n aparte inskrywing het, en ook privaatheid byvoeg (bv. ).
Dit is belangrik om te onderskei tussen die geskiedenis van transaksies (wat die blokketting genoem word) en die huidige toestand van die stelsel. Bitcoin-transaksiegeskiedenis beslaan tans ongeveer 200 GB skyfspasie en groei steeds. Die stelselstatus is egter baie kleiner, in die orde van 4 GB, en neem slegs die feit in ag dat iemand tans munte besit. Die volume van hierdie data neem ook toe met verloop van tyd, maar teen 'n baie stadiger tempo en is soms selfs geneig om af te neem (sien CDPV).
Ligte kliënte (SPV's) verhandel sekuriteitswaarborge vir die vermoë om geen minimum toestand (UTXO-stel) behalwe private sleutels te stoor nie.
UTXO en UTXO-stel
UTXO (Unspent Transaction Output) is die onbestede transaksie-uitset, die eindpunt van die reis van elke Satoshi wat in transaksies oorgedra word. Onbestede uitsette word insette van nuwe transaksies en word dus bestee (bestee) en uit die UTXO-stel verwyder.
Nuwe UTXO's word altyd geskep deur transaksies:
- muntbasistransaksies sonder insette: skep nuwe UTXO's wanneer mynwerkers munte uitreik
- gereelde transaksies: skep nuwe UTXO's terwyl u 'n sekere stel bestaande UTXO's spandeer
Proses om met UTXO te werk:
Beursies tel die aantal munte wat beskikbaar is vir besteding (saldo) gebaseer op die hoeveelheid UTXO wat beskikbaar is vir hierdie beursie vir besteding.
Elke valideerdernodus moet die stel monitor om dubbele bestedingspogings te voorkom alle UTXO wanneer nagegaan word elke transaksies elkeen blok.
Die nodus moet logika hê:
- Byvoegings tot UTXO-stel
- Skrapings van UTXO-stel
- Kontroleer die teenwoordigheid van 'n enkele UTXO in 'n stel
Daar is maniere om die vereistes vir gestoorde inligting oor 'n stel te verminder, terwyl die vermoë behou word om elemente by te voeg en te verwyder, die bestaan van 'n element in 'n stel na te gaan en te bewys deur gebruik te maak van .
Batterye vir UTXO
Die idee om batterye te gebruik om verskeie UTXO's te stoor .
Die UTXO-stel word op die vlug gebou, tydens die aanvanklike blok aflaai (IBD), volledig en permanent gestoor, terwyl die inhoud daarvan verander na die verwerking van transaksies van elke nuwe en korrekte blok van die netwerk. Hierdie proses vereis die aflaai van ongeveer 200 GB se blokdata en die verifikasie van honderde miljoene digitale handtekeninge. Nadat die IBD-proses voltooi is, is die slotsom dat die UTXO-stel ongeveer 4 GB sal beset.
Met akkumuleerders word die reëls van konsensus vir fondse egter verminder tot die verifikasie en generering van kriptografiese bewyse, en die las om beskikbare fondse op te spoor word na die eienaar van daardie fondse verskuif, wat bewys lewer van hul bestaan en eienaarskap.
'n Akkumulator kan 'n kompakte voorstelling van 'n versameling genoem word. Die grootte van die gestoorde voorstelling moet óf konstant wees , of verhoog sublineêr met betrekking tot die kardinaliteit van die versameling en die grootte van die element self, byvoorbeeld , waar n die kardinaliteit van die gestoorde versameling is.
In hierdie geval moet die akkumulator dit moontlik maak om 'n bewys te genereer van die insluiting van 'n element in die stel (insluitingsbewys) en dit moontlik maak om hierdie bewys effektief te verifieer.
Die battery word genoem dinamies as laat jou toe om elemente by te voeg en elemente uit 'n stel te verwyder.
'n Voorbeeld van so 'n battery sou wees . So 'n akkumulator het 'n konstante grootte van gestoorde voorstelling, maar vereis die teenwoordigheid geheime gedeel (betroubare opstelling). Hierdie vereiste ontken die toepaslikheid van so 'n akkumulator vir vertrouelose netwerke soos Bitcoin, aangesien datalekkasie tydens geheime generering aanvallers kan toelaat om valse bewyse van die bestaan van 'n UTXO te skep, wat nodusse mislei met 'n UTXO-stel wat op so 'n akkumulator gebaseer is.
Utreexo
Die Utreexo-ontwerp wat deur Thaddeus Dryja voorgestel is, maak dit moontlik om te skep dinamies battery sonder betroubare-opstelling.
Utreexo is 'n woud van perfekte binêre en is 'n ontwikkeling van die idees wat in , en voeg die vermoë by om elemente uit 'n stel te verwyder.
Battery logiese struktuur
Die batteryselle is in 'n woud van ideale binêre bome gerangskik. Bome word volgens hoogte gerangskik. Hierdie voorstelling is gekies as die mees visuele en laat jou toe om die samesmelting van bome tydens bedrywighede op die battery te visualiseer.
Die skrywer merk op dat aangesien al die bome in die woud ideaal is, word hul hoogte uitgedruk as 'n krag van twee, net soos enige natuurlike getal voorgestel kan word as 'n som van magte van twee. Gevolglik kan enige stel blare in binêre bome gegroepeer word, en in alle gevalle vereis die toevoeging van 'n nuwe element kennis slegs oor die wortelknope van opgebergde bome.
Dus, die gestoorde voorstelling van die Utreexo-akkumulator is 'n lys van wortelknope (Merkle-wortel), en nie die hele woud van bome nie.
Kom ons stel die lys wortelelemente voor as Vec<Option<Hash>>. Opsionele tipe Option<Hash> dui aan dat die wortelelement dalk ontbreek, wat beteken dat daar geen boom met die toepaslike hoogte in die akkumulator is nie.
/// 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],
}
}
}Voeg elemente by
Kom ons beskryf eers die funksie parent(), wat die ouernodus vir twee gegewe elemente herken.
ouer() funksie
Aangesien ons Merkle-bome gebruik, is die ouer van elk van die twee nodusse een nodus wat die hash van die samevoeging van die hashes van die kind nodusse stoor:
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[..])
}Die skrywer merk op dat om die aanvalle te voorkom wat deur Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir en Sebastien Zimmer beskryf is in
, bykomend tot die twee hashes, moet die hoogte binne die boom ook by die aaneenskakeling gevoeg word.
Soos jy elemente by die akkumulator voeg, moet jy tred hou met watter wortelelemente verander word. Deur die pad te volg om die wortelelemente te verander vir elke element wat jy byvoeg, kan jy later 'n bewys van die teenwoordigheid van hierdie elemente saamstel.
Volg veranderinge soos jy dit byvoeg
Om die veranderinge wat gemaak is na te spoor, kom ons verklaar die struktuur Update, wat data oor nodusveranderinge sal stoor.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Om 'n element by die battery te voeg, benodig jy:
- Skep 'n verskeidenheid mandjies van wortelelemente
new_rootsen plaas die bestaande wortelelemente daar, een vir elke emmer:
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);
}- Voeg die elemente by wat bygevoeg moet word (skikking
insertions) na die eerste wanew_roots[0]:
Kode
new_roots[0].extend_from_slice(insertions);- Voeg die items wat by die eerste mandjie gevoeg is saam met die res:
- Vir alle karretjies met meer as een item:
- Neem twee elemente van die einde van die mandjie, bereken hul ouer, verwyder albei elemente
- Voeg die berekende ouer by die volgende mandjie
- Vir alle karretjies met meer as een item:
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 });
}
}- Skuif wortelelemente van bakkies na die resulterende akkumulatorskikking
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]);
}
}Skep 'n bewys vir bygevoegde elemente
Bewys van insluiting van die sel in die battery (Proof) sal dien as die Merkle-pad, wat uit 'n ketting bestaan ProofStep. As die pad nêrens heen lei nie, dan is die bewys verkeerd.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Gebruik die inligting wat vroeër verkry is wanneer 'n element (struktuur Update), kan jy bewys skep dat 'n element by die battery gevoeg is. Om dit te doen, gaan ons deur die tabel van veranderinge wat gemaak is en voeg elke stap by Merkle se pad, wat later as bewys sal dien:
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
}
}Proses om 'n bewys te skep
Kontroleer die bewys vir 'n element
Om 'n element se insluitingbewys na te gaan, kom daarop neer om die Merkle-pad te volg totdat dit na 'n bestaande wortelelement lei:
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 om die bewys vir A na te gaan
Verwyder items
Om 'n sel uit 'n battery te verwyder, moet jy geldige bewyse verskaf dat die sel daar is. Deur die data van die bewys te gebruik, is dit moontlik om nuwe wortelelemente van die akkumulator te bereken waarvoor die gegewe bewys nie meer waar sal wees nie.
Die algoritme is soos volg:
- Soos met byvoeging, organiseer ons 'n stel leë mandjies wat ooreenstem met Merkle-bome met 'n hoogte gelyk aan die krag van twee uit die mandjie-indeks
- Ons voeg elemente van die trappe van die Merkle-pad in die mandjies in; die mandjie-indeks is gelyk aan die nommer van die huidige stap
- Ons verwyder die wortelelement waarheen die pad van die bewys lei
- Soos met byvoeging, bereken ons nuwe wortelelemente deur elemente uit mandjies in pare te kombineer en die resultaat van die vereniging na die volgende mandjie te skuif
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;
}
}Die proses om element "A" te verwyder:
Integrasie in 'n bestaande netwerk
Deur die voorgestelde akkumulator te gebruik, kan nodusse vermy om 'n DB te gebruik om alle UTXO's te stoor terwyl hulle steeds die UTXO-stel kan verander. Die probleem om met bewyse te werk ontstaan egter.
Kom ons noem die valideerdernodus wat die UTXO-akkumulator gebruik kompakte (kompakte toestand nodus), en die valideerder sonder 'n akkumulator is volle (volle nodus). Die bestaan van twee klasse nodusse skep 'n probleem om hulle in 'n enkele netwerk te integreer, aangesien kompakte nodusse bewys vereis van die bestaan van UTXO's, wat in transaksies bestee word, terwyl volle nodusse dit nie doen nie. As alle netwerknodusse nie gelyktydig en op 'n gekoördineerde wyse oorskakel na die gebruik van Utreexo nie, sal kompakte nodusse agterbly en nie op die Bitcoin-netwerk kan werk nie.
Om die probleem van die integrasie van kompakte nodusse in die netwerk op te los, word voorgestel om 'n bykomende klas nodusse in te stel - brûe. 'n Brugnodus is 'n volledige nodus wat ook die Utreexo-battery en aanskakelbewys stoor alle UTXO van UTXO-stel. Bruge bereken nuwe hashes en werk die akkumulator en bewyse op soos nuwe blokke transaksies aankom. Die instandhouding en opdatering van die akkumulator en bewyse plaas nie bykomende berekeningslas op sulke nodusse nie. Brûe offer skyfspasie op: moet dinge georganiseer hou hashes, in vergelyking met hashes vir kompakte nodusse, waar n die krag van die UTXO-stel is.
Netwerk argitektuur
Brûe maak dit moontlik om geleidelik kompakte nodusse by die netwerk te voeg sonder om die sagteware van bestaande nodusse te verander. Volle nodusse werk soos voorheen en versprei transaksies en blokke onder mekaar. Brugnodusse is vol nodusse wat addisioneel Utreexo-batterydata en 'n stel insluitingsbewyse stoor alle UTXO vir nou. Die brugnodus adverteer homself nie as sodanig nie, en gee voor om 'n volledige nodus vir alle vol nodusse en 'n kompakte nodus vir alle kompaktes te wees. Alhoewel brûe albei netwerke met mekaar verbind, hoef hulle hulle eintlik net in een rigting te verbind: van bestaande vol nodusse tot kompakte nodusse. Dit is moontlik omdat die transaksieformaat nie verander hoef te word nie, en UTXO-bewyse vir kompakte nodusse weggegooi kan word, sodat enige kompakte nodus op soortgelyke wyse transaksies na alle netwerkdeelnemers kan uitsaai sonder die deelname van brugnodusse.
Gevolgtrekking
Ons het na die Utreexo-battery gekyk en sy prototipe in Rust geïmplementeer. Ons het gekyk na die netwerkargitektuur wat die integrasie van battery-gebaseerde nodusse sal toelaat. Die voordeel van kompakte vangste is die grootte van die gestoor data, wat logaritmies afhang van die krag van die stel UTXO's, wat die vereistes vir skyfspasie en bergingswerkverrigting vir sulke nodusse aansienlik verminder. Die nadeel is die bykomende nodusverkeer vir die oordrag van bewyse, maar bewyssamevoegingstegnieke (wanneer een bewys die bestaan van verskeie elemente bewys) en kas kan help om verkeer binne aanvaarbare perke te hou.
verwysings:
- -
Bron: will.com