Hei Habr!
Yn y rhwydwaith Bitcoin, mae pob nod, trwy gonsensws, yn cytuno ar set o UTXOs: faint o ddarnau arian sydd ar gael i'w gwario, i bwy yn union, ac o dan ba amodau. Y set UTXO yw'r set ddata leiaf sy'n ofynnol ar gyfer nod dilysu, a heb hynny ni fydd y nod yn gallu gwirio dilysrwydd trafodion sy'n dod i mewn a'r blociau sy'n eu cynnwys.
Yn hyn o beth, mae ymdrechion yn cael eu gwneud ym mhob ffordd bosibl i leihau cynrychiolaeth storio'r set hon, i'w gywasgu heb golli gwarantau diogelwch. Po leiaf yw cyfaint y data sydd wedi'i storio, yr isaf yw gofynion gofod disg y nod dilysu, sy'n gwneud lansio nod dilysydd yn rhad, yn caniatáu ichi ehangu'r rhwydwaith a thrwy hynny gynyddu sefydlogrwydd y rhwydwaith.
Yn y swydd hon byddwn yn postio prototeip Rust o gynnig diweddar gan gyd-awdur , - , sy'n caniatáu lleihau gofynion gofod disg ar gyfer nodau dilysydd.
Beth yw'r broblem?
Un o broblemau lluosflwydd Bitcoin fu ei scalability. Mae'r syniad o “eich banc eich hun” yn ei gwneud yn ofynnol i gyfranogwyr y rhwydwaith gadw cofnodion o'r holl arian sydd ar gael i'w ddefnyddio. Yn Bitcoin, mae'r arian sydd ar gael yn cael ei fynegi fel set o allbynnau heb eu gwario - set UTXO. Er nad yw hwn yn gynrychiolaeth arbennig o reddfol, mae'n fuddiol o ran perfformiad gweithredu dros gynrychiolaeth lle mae gan bob "waled" "gydbwysedd" fel cofnod ar wahân, a hefyd yn ychwanegu preifatrwydd (e.e. ).
Mae'n bwysig gwahaniaethu rhwng hanes trafodion (yr hyn a elwir yn blockchain) a chyflwr presennol y system. Ar hyn o bryd mae hanes trafodion Bitcoin yn meddiannu tua 200 GB o ofod disg, ac yn parhau i dyfu. Fodd bynnag, mae cyflwr y system yn llawer llai, tua 4 GB, a dim ond yn ystyried y ffaith bod rhywun yn berchen ar ddarnau arian ar hyn o bryd. Mae cyfaint y data hwn hefyd yn cynyddu dros amser, ond ar gyfradd llawer arafach ac weithiau hyd yn oed yn tueddu i ostwng (gweler CDPV).
Mae cleientiaid ysgafn (SPVs) yn gwarantu diogelwch masnach ar gyfer y gallu i storio dim cyflwr lleiaf (UTXO-set) ac eithrio allweddi preifat.
UTXO ac UTXO-set
UTXO (Allbwn Trafodiad Heb ei Wario) yw'r allbwn trafodion heb ei wario, pwynt diwedd taith pob Satoshi a drosglwyddir mewn trafodion. Mae allbynnau heb eu gwario yn dod yn fewnbynnau o drafodion newydd ac felly'n cael eu gwario (gwariant) a'u tynnu o'r set UTXO.
Mae UTXOs newydd bob amser yn cael eu creu gan drafodion:
- trafodion coinbase heb fewnbynnau: creu UTXOs newydd pan fydd glowyr yn cyhoeddi darnau arian
- trafodion rheolaidd: creu UTXOs newydd wrth wario set benodol o UTXOs presennol
Proses o weithio gydag UTXO:
Mae waledi yn cyfrif nifer y darnau arian sydd ar gael i'w gwario (cydbwysedd) yn seiliedig ar faint o UTXO sydd ar gael i'r waled hon i'w wario.
Rhaid i bob nod dilysu, er mwyn atal ymdrechion gwario dwbl, fonitro'r set holl UTXO wrth wirio yr un trafodion yr un bloc.
Rhaid i'r nod fod â rhesymeg:
- Ychwanegiadau i set UTXO
- Dileadau o UTXO-set
- Gwirio presenoldeb UTXO sengl mewn set
Mae yna ffyrdd i leihau'r gofynion ar gyfer gwybodaeth wedi'i storio am set, tra'n cynnal y gallu i ychwanegu a dileu elfennau, gwirio a phrofi bodolaeth elfen mewn set gan ddefnyddio .
Batris ar gyfer UTXO
Y syniad o ddefnyddio batris i storio UTXO lluosog .
Mae'r set UTXO wedi'i adeiladu ar y hedfan, yn ystod y lawrlwythiad bloc cychwynnol (IBD), wedi'i storio'n llawn ac yn barhaol, tra bod ei gynnwys yn newid ar ôl prosesu trafodion o bob bloc newydd a chywir o'r rhwydwaith. Mae'r broses hon yn gofyn am lawrlwytho tua 200 GB o ddata bloc a gwirio cannoedd o filiynau o lofnodion digidol. Ar ôl i'r broses IBD gael ei chwblhau, y llinell waelod yw y bydd y set UTXO yn meddiannu tua 4 GB.
Fodd bynnag, gyda chronwyr, mae'r rheolau consensws ar gyfer cronfeydd yn cael eu lleihau i ddilysu a chynhyrchu proflenni cryptograffig, ac mae'r baich o olrhain yr arian sydd ar gael yn cael ei symud i berchennog y cronfeydd hynny, sy'n darparu prawf o'u bodolaeth a'u perchnogaeth.
Gellir galw cronadur yn gynrychiolaeth gryno o set. Rhaid i faint y cynrychioliad sydd wedi'i storio fod naill ai'n gyson , neu gynyddu'n islinellol o ran cardinality y set a maint yr elfen ei hun, er enghraifft , lle n yw cardinality y set storio.
Yn yr achos hwn, dylai'r cronadur ganiatáu cynhyrchu prawf o gynnwys elfen yn y set (prawf cynhwysiant) a'i gwneud hi'n bosibl gwirio'r prawf hwn yn effeithiol.
Gelwir y batri deinamig os yn caniatáu ichi ychwanegu elfennau a thynnu elfennau o set.
Enghraifft o fatri o'r fath fyddai . Mae gan gronnwr o'r fath faint cyson o gynrychiolaeth wedi'i storio, ond mae angen presenoldeb arno cyfrinach a rennir (gosodiad dibynadwy). Mae'r gofyniad hwn yn negyddu cymhwysedd cronnwr o'r fath ar gyfer rhwydweithiau di-ymddiriedaeth fel Bitcoin, gan y gall gollwng data yn ystod cynhyrchu cyfrinachol ganiatáu i ymosodwyr greu prawf ffug o fodolaeth UTXO, gan dwyllo nodau gyda set UTXO yn seiliedig ar gronnwr o'r fath.
Utreexo
Mae dyluniad Utreexo a gynigiwyd gan Thaddeus Dryja yn ei gwneud hi'n bosibl ei greu deinamig cronni без ymddiried-setup.
Mae Utreexo yn goedwig o ddeuaidd perffaith ac yn ddatblygiad o'r syniadau a gyflwynir yn , gan ychwanegu'r gallu i dynnu elfennau o set.
Strwythur Rhesymegol Batri
Trefnir y celloedd batri mewn coedwig o goed deuaidd delfrydol. Mae coed yn cael eu harchebu yn ôl uchder. Dewiswyd y gynrychiolaeth hon fel y mwyaf gweledol ac mae'n caniatáu ichi ddelweddu uno coed yn ystod gweithrediadau ar y batri.
Mae'r awdur yn nodi, gan fod yr holl goed yn y goedwig yn ddelfrydol, bod eu huchder yn cael ei fynegi fel pŵer o ddau, yn union fel y gellir cynrychioli unrhyw rif naturiol fel swm o bwerau o ddau. Yn unol â hynny, gellir grwpio unrhyw set o ddail yn goed deuaidd, ac ym mhob achos, mae angen gwybodaeth i ychwanegu elfen newydd dim ond am nodau gwreiddiau coed sydd wedi'u storio.
Felly, mae cynrychiolaeth storio'r cronadur Utreexo yn rhestr o nodau gwraidd (gwreiddyn Merkle), ac nid yr holl goedwig o goed.
Gadewch i ni gynrychioli'r rhestr o elfennau gwraidd fel Vec<Option<Hash>>. Math dewisol Option<Hash> yn nodi y gallai'r elfen wreiddiau fod ar goll, sy'n golygu nad oes unrhyw goeden gyda'r uchder priodol yn y cronadur.
/// 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],
}
}
}Ychwanegu elfennau
Yn gyntaf, gadewch i ni ddisgrifio'r swyddogaeth parent(), sy'n cydnabod y nod rhiant ar gyfer dwy elfen benodol.
swyddogaeth rhiant ().
Gan ein bod yn defnyddio coed Merkle, mae rhiant pob un o'r ddau nod yn un nod sy'n storio stwnsh cydgadwyniad hashes nodau'r plentyn:
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[..])
}Mae'r awdur yn nodi er mwyn atal yr ymosodiadau a ddisgrifiwyd gan Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, a Sebastien Zimmer yn
, yn ychwanegol at y ddau hashes, dylid ychwanegu uchder y tu mewn i'r goeden hefyd at y concatenation.
Wrth i chi ychwanegu elfennau at y cronadur, mae angen i chi gadw golwg ar ba elfennau gwraidd sy'n cael eu newid. Trwy ddilyn y llwybr o newid yr elfennau gwraidd ar gyfer pob elfen rydych chi'n ei ychwanegu, gallwch chi adeiladu prawf o bresenoldeb yr elfennau hyn yn ddiweddarach.
Traciwch newidiadau wrth i chi eu hychwanegu
I olrhain y newidiadau a wnaed, gadewch i ni ddatgan y strwythur Update, a fydd yn storio data am newidiadau nod.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}I ychwanegu elfen at y batri, mae angen:
- Creu amrywiaeth o fasgedi o elfennau gwraidd
new_rootsa gosodwch yr elfennau gwraidd presennol yno, un ar gyfer pob bwced:
Cod
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);
}- Atodwch yr elfennau i'w hychwanegu (arae
insertions) i'r drol gyntafnew_roots[0]:
Cod
new_roots[0].extend_from_slice(insertions);- Cyfunwch yr eitemau a ychwanegwyd at y fasged gyntaf gyda'r gweddill:
- Ar gyfer pob cert sydd â mwy nag un eitem:
- Cymerwch ddwy elfen o ddiwedd y fasged, cyfrifwch eu rhiant, tynnwch y ddwy elfen
- Ychwanegwch y rhiant a gyfrifwyd i'r drol nesaf
- Ar gyfer pob cert sydd â mwy nag un eitem:
Cod
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 });
}
}- Symud elfennau gwraidd o finiau i arae cronadur sy'n deillio o hynny
Cod
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]);
}
}Creu prawf ar gyfer elfennau ychwanegol
Prawf o gynnwys y gell yn y batri (Proof) yn gweithredu fel Llwybr Merkle, sy'n cynnwys cadwyn ProofStep. Os nad yw'r llwybr yn arwain i unman, yna mae'r prawf yn anghywir.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Defnyddio’r wybodaeth a gafwyd yn gynharach wrth ychwanegu elfen (strwythur Update), gallwch greu prawf bod elfen wedi'i hychwanegu at y batri. I wneud hyn, rydym yn mynd trwy'r tabl o newidiadau a wnaed ac yn ychwanegu pob cam at lwybr Merkle, a fydd wedyn yn brawf:
Cod
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 o greu prawf
Gwirio'r prawf am elfen
Mae gwirio prawf cynhwysiant elfen yn dibynnu ar ddilyn llwybr Merkle nes ei fod yn arwain at elfen wreiddiau sy'n bodoli eisoes:
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
}
}Yn weledol:
Y broses o wirio'r prawf ar gyfer A
Tynnu eitemau
I dynnu cell o fatri, rhaid i chi ddarparu tystiolaeth ddilys bod y gell yno. Gan ddefnyddio'r data o'r prawf, mae'n bosibl cyfrifo elfennau gwraidd newydd y cronadur na fydd y prawf a roddir yn wir mwyach.
Mae'r algorithm fel a ganlyn:
- Fel yn ogystal, rydym yn trefnu set o fasgedi gwag sy'n cyfateb i goed Merkle gydag uchder sy'n hafal i bŵer dau o'r mynegai basged
- Rydyn ni'n mewnosod elfennau o risiau llwybr Merkle i'r basgedi; mae'r mynegai basged yn hafal i nifer y cam cyfredol
- Rydyn ni'n tynnu'r elfen wreiddiau y mae'r llwybr o'r prawf yn arwain ato
- Fel gydag adio, rydym yn cyfrifo elfennau gwraidd newydd trwy gyfuno elfennau o fasgedi mewn parau a symud canlyniad yr undeb i'r fasged nesaf
Cod
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;
}
}Y broses o ddileu elfen "A":
Integreiddio i rwydwaith presennol
Gan ddefnyddio'r cronnwr arfaethedig, gall nodau osgoi defnyddio DB i storio'r holl UTXO wrth barhau i allu newid y set UTXO. Fodd bynnag, mae problem gweithio gyda thystiolaeth yn codi.
Gadewch i ni alw'r nod dilysu sy'n defnyddio'r cronadur UTXO cryno (nod compact-state), a'r dilysydd heb gronnwr yw cyflawn (nodyn llawn). Mae bodolaeth dau ddosbarth o nodau yn creu problem ar gyfer eu hintegreiddio i un rhwydwaith, gan fod nodau cryno yn gofyn am brawf o fodolaeth UTXO, sy'n cael eu gwario mewn trafodion, tra nad yw nodau llawn yn gwneud hynny. Os na fydd pob nod rhwydwaith yn newid i ddefnyddio Utreexo ar yr un pryd ac mewn modd cydgysylltiedig, yna bydd nodau cryno yn cael eu gadael ar ôl ac ni fyddant yn gallu gweithredu ar y rhwydwaith Bitcoin.
Er mwyn datrys y broblem o integreiddio nodau cryno i'r rhwydwaith, cynigir cyflwyno dosbarth ychwanegol o nodau - pontydd. Mae nod pont yn nod cyflawn sydd hefyd yn storio batri Utreexo a phrawf pŵer ymlaen ar gyfer holl UTXO o UTXO-set. Mae Pontydd yn cyfrifo hashes newydd ac yn diweddaru'r cronadur a'r proflenni wrth i flociau trafodion newydd gyrraedd. Nid yw cynnal a diweddaru'r cronadur a'r proflenni yn gosod llwyth cyfrifiannol ychwanegol ar nodau o'r fath. Pontydd yn aberthu gofod disg: angen cadw pethau'n drefnus hashes, o gymharu â hashes ar gyfer nodau cryno, lle n yw pŵer y set UTXO.
Pensaernïaeth rhwydwaith
Mae pontydd yn ei gwneud hi'n bosibl ychwanegu nodau cryno i'r rhwydwaith yn raddol heb newid meddalwedd nodau presennol. Mae nodau llawn yn gweithredu fel o'r blaen, gan ddosbarthu trafodion a blociau ymhlith ei gilydd. Mae nodau pont yn nodau llawn sydd hefyd yn storio data batri Utreexo a set o brofion cynhwysiant ar gyfer holl UTXO am y tro. Nid yw nod y bont yn hysbysebu ei hun felly, gan esgus ei fod yn nod llawn ar gyfer pob nod llawn ac yn nod cryno ar gyfer pob un cryno. Er bod pontydd yn cysylltu'r ddau rwydwaith gyda'i gilydd, mewn gwirionedd dim ond mewn un cyfeiriad y mae angen iddynt eu cysylltu: o nodau llawn presennol i nodau cryno. Mae hyn yn bosibl oherwydd nad oes angen newid fformat y trafodion, a gellir taflu proflenni UTXO ar gyfer nodau cryno, felly gall unrhyw nod cryno ddarlledu trafodion yn yr un modd i holl gyfranogwyr y rhwydwaith heb gyfranogiad nodau pont.
Casgliad
Edrychon ni ar y batri Utreexo a gweithredu ei brototeip yn Rust. Gwnaethom edrych ar bensaernïaeth y rhwydwaith a fydd yn caniatáu integreiddio nodau sy'n seiliedig ar batri. Mantais dalfeydd cryno yw maint y data sydd wedi'i storio, sy'n dibynnu'n logarithmig ar bŵer y set o UTXO, sy'n lleihau'n fawr y gofynion ar gyfer gofod disg a pherfformiad storio nodau o'r fath. Yr anfantais yw'r traffig nod ychwanegol ar gyfer trosglwyddo proflenni, ond gall technegau agregu tystiolaeth (pan fydd un prawf yn profi bodolaeth sawl elfen) a caching helpu i gadw traffig o fewn terfynau derbyniol.
cyfeiriadau:
- -
Ffynhonnell: hab.com