Ħej Habr!
Fin-netwerk Bitcoin, in-nodi kollha, permezz ta 'kunsens, jaqblu fuq sett ta' UTXOs: kemm hemm muniti disponibbli għall-infiq, lil min eżattament, u taħt liema kundizzjonijiet. Is-sett UTXO huwa s-sett minimu ta 'dejta meħtieġ għal nodu validatur, li mingħajru n-nodu ma jkunx jista' jivverifika l-validità tat-tranżazzjonijiet deħlin u l-blokki li jkun fihom.
F'dan ir-rigward, qed isiru tentattivi b'kull mod possibbli biex titnaqqas ir-rappreżentazzjoni maħżuna ta' dan is-sett, biex tiġi kkompressata mingħajr ma jintilfu l-garanziji tas-sigurtà. Iktar ma jkun żgħir il-volum ta 'data maħżuna, inqas ikunu r-rekwiżiti tal-ispazju tad-disk tan-node tal-validatur, li jagħmel it-tnedija ta' nodu tal-validatur irħis, jippermettilek tespandi n-netwerk u b'hekk iżżid l-istabbiltà tan-netwerk.
F'din il-kariga se npoġġu prototip Rust ta' proposta reċenti minn ko-awtur , - , li tippermetti li jitnaqqsu r-rekwiżiti tal-ispazju tad-disk għal nodi tal-validatur.
X'inhi l-problema?
Waħda mill-problemi perenni ta 'Bitcoin kienet l-iskalabbiltà tagħha. L-idea ta '"bank tiegħek stess" teħtieġ li l-parteċipanti tan-netwerk iżommu rekords tal-fondi kollha disponibbli għall-użu. F'Bitcoin, il-fondi disponibbli huma espressi bħala sett ta 'outputs mhux minfuqa - sett UTXO. Filwaqt li din mhix rappreżentazzjoni partikolarment intuwittiva, hija ta' benefiċċju f'termini ta' prestazzjoni tal-implimentazzjoni fuq rappreżentazzjoni li fiha kull "kartiera" għandha "bilanċ" bħala dħul separat, u żżid ukoll il-privatezza (eż. ).
Huwa importanti li ssir distinzjoni bejn l-istorja tat-tranżazzjonijiet (dik li tissejjaħ blockchain) u l-istat attwali tas-sistema. L-istorja tat-tranżazzjonijiet Bitcoin bħalissa tieħu madwar 200 GB ta 'spazju fuq disk, u qed tkompli tikber. Madankollu, l-istat tas-sistema huwa ħafna iżgħar, tal-ordni ta '4 GB, u jqis biss il-fatt li xi ħadd bħalissa għandu muniti. Il-volum ta’ din id-dejta jiżdied ukoll maż-żmien, iżda b’rata ferm aktar bil-mod u xi kultant anke t-tendenza li jonqos (ara CDPV).
Il-klijenti ħfief (SPVs) jinnegozjaw garanziji tas-sigurtà għall-abbiltà li ma jaħżnu l-ebda stat minimu (sett UTXO) għajr ċwievet privati.
UTXO u UTXO-sett
UTXO (Output ta 'Transazzjoni mhux minfuqa) huwa l-output tat-tranżazzjoni mhux minfuq, il-punt tat-tmiem tal-vjaġġ ta' kull Satoshi trasferit fi tranżazzjonijiet. Outputs mhux minfuqa jsiru inputs ta’ tranżazzjonijiet ġodda u għalhekk jintefqu (jonfqu) u jitneħħew mis-sett UTXO.
UTXOs ġodda huma dejjem maħluqa minn tranżazzjonijiet:
- tranżazzjonijiet coinbase mingħajr inputs: oħloq UTXOs ġodda meta l-minaturi joħorġu muniti
- tranżazzjonijiet regolari: toħloq UTXOs ġodda filwaqt li tonfoq ċertu sett ta 'UTXOs eżistenti
Proċess ta' ħidma ma' UTXO:
Kartieri jgħoddu n-numru ta 'muniti disponibbli għall-infiq (bilanċ) ibbażat fuq l-ammont ta' UTXO disponibbli għal din il-kartiera għall-infiq.
Kull nodu validatur, biex jipprevjenu tentattivi ta' infiq doppju, għandu jimmonitorja s-sett Kollha UTXO meta tiċċekkja kull wieħed transazzjonijiet ta 'kull wieħed blokk.
In-nodu għandu jkollu loġika:
- Żidiet għal UTXO-sett
- Tħassir minn UTXO-set
- Iċċekkjar tal-preżenza ta 'UTXO wieħed f'sett
Hemm modi kif jitnaqqsu r-rekwiżiti għall-informazzjoni maħżuna dwar sett, filwaqt li tinżamm il-kapaċità li żżid u tneħħi elementi, tivverifika u tipprova l-eżistenza ta 'element f'sett bl-użu .
Batteriji għal UTXO
L-idea li tuża batteriji biex taħżen UTXO multipli .
L-UTXO-sett huwa mibni fuq il-fly, matul it-tniżżil tal-blokki inizjali (IBD), maħżun b'mod sħiħ u permanenti, filwaqt li l-kontenut tiegħu jinbidel wara l-ipproċessar ta 'tranżazzjonijiet minn kull blokka ġdida u korretta tan-netwerk. Dan il-proċess jeħtieġ it-tniżżil ta' madwar 200 GB ta' dejta tal-blokki u l-verifika ta' mijiet ta' miljuni ta' firem diġitali. Wara li jitlesta l-proċess IBD, il-linja tal-qiegħ hija li l-UTXO-sett se jokkupa madwar 4 GB.
Madankollu, bl-akkumulaturi, ir-regoli ta 'kunsens għall-fondi huma mnaqqsa għall-verifika u l-ġenerazzjoni ta' provi kriptografiċi, u l-piż tat-traċċar tal-fondi disponibbli jiġi mċaqlaq fuq is-sid ta 'dawk il-fondi, li jipprovdi prova tal-eżistenza u s-sjieda tagħhom.
Akkumulatur jista 'jissejjaħ rappreżentazzjoni kompatta ta' sett. Id-daqs tar-rappreżentazzjoni maħżuna għandu jkun jew kostanti , jew żid b'mod sublineari fir-rigward tal-kardinalità tas-sett u d-daqs tal-element innifsu, pereżempju , fejn n hija l-kardinalità tas-sett maħżun.
F'dan il-każ, l-akkumulatur għandu jippermetti li tiġi ġġenerata prova tal-inklużjoni ta' element fis-sett (prova tal-inklużjoni) u jagħmilha possibbli li din il-prova tiġi vverifikata b'mod effettiv.
Il-batterija tissejjaħ dinamiku jekk jippermettilek li żżid elementi u tneħħi elementi minn sett.
Eżempju ta 'tali batterija tkun . Tali akkumulatur għandu daqs kostanti ta 'rappreżentazzjoni maħżuna, iżda jeħtieġ il-preżenza sigriet maqsum (setup affidabbli). Dan ir-rekwiżit jiċħad l-applikabilità ta 'tali akkumulatur għal netwerks bla fiduċja bħal Bitcoin, peress li t-tnixxija tad-dejta matul il-ġenerazzjoni sigrieta tista' tippermetti lill-attakkanti joħolqu prova falza tal-eżistenza ta 'UTXO, iqarraq b'nodes b'UTXO-sett ibbażat fuq tali akkumulatur.
Utreexo
Id-disinn Utreexo propost minn Thaddeus Dryja jagħmilha possibbli li jinħoloq dinamiku akkumulatur mingħajr setup affidabbli.
Utreexo hija foresta ta 'binarju perfett u huwa żvilupp tal-ideat ippreżentati fi , li żżid il-ħila li tneħħi elementi minn sett.
Struttura Loġika tal-batterija
Iċ-ċelloli tal-batterija huma rranġati f'foresta ta 'siġar binarji ideali. Is-siġar huma ordnati skond l-għoli. Din ir-rappreżentazzjoni ntgħażlet bħala l-aktar viżwali u tippermettilek li tara l-għaqda tas-siġar waqt l-operazzjonijiet fuq il-batterija.
L-awtur jinnota li peress li s-siġar kollha fil-foresta huma ideali, l-għoli tagħhom huwa espress bħala qawwa ta 'tnejn, hekk kif kull numru naturali jista' jiġi rappreżentat bħala somma ta 'poteri ta' tnejn. Għaldaqstant, kwalunkwe sett ta 'weraq jista' jinġabar f'siġar binarji, u fil-każijiet kollha, iż-żieda ta 'element ġdid teħtieġ għarfien biss dwar in-nodi ta 'l-għeruq ta' siġar maħżuna.
Għalhekk, ir-rappreżentazzjoni maħżuna ta 'l-akkumulatur Utreexo hija lista ta' nodi ta 'l-għeruq (għerq ta' Merkle), u mhux il-foresta kollha tas-siġar.
Ejja nirrappreżentaw il-lista ta 'elementi ta' l-għeruq bħala Vec<Option<Hash>>. Tip mhux obbligatorju Option<Hash> jindika li l-element għerq jista 'jkun nieqes, li jfisser li m'hemm l-ebda siġra bl-għoli xieraq fl-akkumulatur.
/// 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],
}
}
}Żieda ta 'elementi
L-ewwel, ejja niddeskrivu l-funzjoni parent(), li jirrikonoxxi n-nodu ġenitur għal żewġ elementi mogħtija.
parent() funzjoni
Peress li qed nużaw is-siġar Merkle, il-ġenitur ta 'kull wieħed miż-żewġ nodi huwa nodu wieħed li jaħżen il-hash tal-konkatenazzjoni tal-hashes tan-nodi tfal:
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[..])
}L-awtur jinnota li biex jipprevjenu l-attakki deskritti minn Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, u Sebastien Zimmer f’
, minbarra ż-żewġ hashes, l-għoli ġewwa s-siġra għandu wkoll jiżdied mal-konkatenazzjoni.
Hekk kif iżżid elementi mal-akkumulatur, trid iżżomm kont ta' liema elementi tal-għeruq jinbidlu. Billi ssegwi t-triq li tbiddel l-elementi ta 'l-għeruq għal kull element li żżid, tista' aktar tard tibni prova tal-preżenza ta 'dawn l-elementi.
Issegwi l-bidliet hekk kif iżżidhom
Biex issegwi l-bidliet li saru, ejja tiddikjara l-istruttura Update, li se taħżen data dwar il-bidliet tan-nodi.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Biex iżżid element mal-batterija, għandek bżonn:
- Oħloq firxa ta 'basktijiet ta' elementi ta 'l-għeruq
new_rootsu poġġi l-elementi tal-għeruq eżistenti hemmhekk, wieħed għal kull barmil:
Kodiċi
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);
}- Waħħal l-elementi li għandhom jiżdiedu (array
insertions) għall-ewwel karrettunnew_roots[0]:
Kodiċi
new_roots[0].extend_from_slice(insertions);- Agħlaq l-oġġetti miżjuda mal-ewwel basket mal-bqija:
- Għall-karrettuni kollha b'aktar minn oġġett wieħed:
- Ħu żewġ elementi mit-tarf tal-basket, ikkalkula l-ġenitur tagħhom, neħħi ż-żewġ elementi
- Żid il-ġenitur ikkalkulat mal-karrettun li jmiss
- Għall-karrettuni kollha b'aktar minn oġġett wieħed:
Kodiċi
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 });
}
}- Mexxi l-elementi tal-għeruq mill-bins għall-firxa tal-akkumulaturi li tirriżulta
Kodiċi
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]);
}
}Ħolqien ta 'prova għal elementi miżjuda
Prova tal-inklużjoni taċ-ċellula fil-batterija (Proof) se jservi bħala l-Merkle Path, li tikkonsisti minn katina ProofStep. Jekk it-triq ma twassal imkien, allura l-prova mhix korretta.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}L-użu tal-informazzjoni miksuba qabel meta żżid element (struttura Update), tista 'toħloq prova li element ġie miżjud mal-batterija. Biex tagħmel dan, ngħaddu mit-tabella tal-bidliet li saru u nżidu kull pass mat-triq ta 'Merkle, li sussegwentement isservi bħala prova:
Kodiċi
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
}
}Proċess tal-ħolqien ta' prova
Iċċekkjar tal-prova għal element
L-iċċekkjar tal-prova tal-inklużjoni ta' element jirriżulta biex issegwi l-mogħdija ta' Merkle sakemm twassal għal element għerq eżistenti:
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
}
}Viżwalment:
Proċess ta' verifika tal-prova għal A
Tneħħi oġġetti
Biex tneħħi ċellola minn batterija, trid tipprovdi evidenza valida li ċ-ċellula qiegħda hemm. Bl-użu tad-dejta mill-prova, huwa possibbli li jiġu kkalkolati elementi ta 'għeruq ġodda tal-akkumulatur li għalihom il-prova mogħtija ma tibqax vera.
L-algoritmu huwa kif ġej:
- Bħal ma 'żieda, norganizzaw sett ta' qfief vojta li jikkorrispondu mas-siġar Merkle b'għoli ugwali għall-qawwa ta 'tnejn mill-indiċi tal-basket
- Aħna ndaħħlu elementi mill-passi tal-mogħdija Merkle fil-qfief; l-indiċi tal-basket huwa ugwali għan-numru tal-pass kurrenti
- Aħna nneħħu l-element għerq li għalih twassal il-mogħdija mill-prova
- Bħal maż-żieda, aħna nikkalkulaw elementi ġodda tal-għeruq billi ngħaqqdu elementi minn qfief f'pari u nimxu r-riżultat tal-unjoni għall-basket li jmiss
Kodiċi
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;
}
}Il-proċess tat-tneħħija tal-element "A":
Integrazzjoni f'netwerk eżistenti
Bl-użu tal-akkumulatur propost, in-nodi jistgħu jevitaw li jużaw DB biex jaħżnu l-UTXOs kollha filwaqt li xorta jkunu jistgħu jibdlu l-UTXO-set. Madankollu, tqum il-problema li taħdem bl-evidenza.
Ejja nsejħu n-nodu validatur li juża l-akkumulatur UTXO kompatti (compact-state node), u l-validatur mingħajr akkumulatur huwa kompluta (node sħiħ). L-eżistenza ta 'żewġ klassijiet ta' nodi toħloq problema għall-integrazzjoni tagħhom f'netwerk wieħed, peress li n-nodi kompatti jeħtieġu prova tal-eżistenza ta 'UTXOs, li jintefqu fi tranżazzjonijiet, filwaqt li n-nodi sħaħ ma jagħmlux dan. Jekk in-nodi kollha tan-netwerk ma jaqilbux fl-istess ħin u b'mod koordinat għall-użu ta 'Utreexo, allura n-nodi kompatti jitħallew lura u ma jkunux jistgħu joperaw fuq in-netwerk Bitcoin.
Biex issolvi l-problema tal-integrazzjoni tan-nodi kompatti fin-netwerk, huwa propost li tiġi introdotta klassi addizzjonali ta 'nodi - pontijiet. Nodu tal-pont huwa nodu komplut li jaħżen ukoll il-batterija Utreexo u l-prova tal-qawwa fuq Kollha UTXO minn UTXO-sett. Il-pontijiet jikkalkulaw hashes ġodda u jaġġornaw l-akkumulatur u l-provi hekk kif jaslu blokki ġodda ta 'tranżazzjonijiet. Iż-żamma u l-aġġornament tal-akkumulatur u l-provi ma timponix tagħbija komputazzjonali addizzjonali fuq tali nodi. Il-pontijiet jissagrifikaw l-ispazju tad-diska: jeħtieġ li jżommu l-affarijiet organizzati hashes, meta mqabbla ma ' hashes għal nodi kompatti, fejn n hija l-qawwa tas-sett UTXO.
Arkitettura tan-netwerk
Il-pontijiet jagħmluha possibbli li jiżdiedu gradwalment nodi kompatti man-netwerk mingħajr ma jinbidel is-softwer ta 'nodi eżistenti. Nodi sħaħ joperaw bħal qabel, iqassmu tranżazzjonijiet u blokki bejniethom. Nodi tal-pont huma nodi sħaħ li wkoll jaħżnu d-dejta tal-batterija Utreexo u sett ta 'provi ta' inklużjoni għalihom Kollha UTXO għalissa. In-nodu tal-pont ma jirreklamax lilu nnifsu bħala tali, jippretendi li huwa nodu sħiħ għan-nodi sħaħ kollha u nodu kompatt għal dawk kollha kompatti. Għalkemm il-pontijiet jgħaqqdu ż-żewġ netwerks flimkien, fil-fatt jeħtieġu biss li jgħaqqduhom f'direzzjoni waħda: minn nodi sħaħ eżistenti għal nodi kompatti. Dan huwa possibbli minħabba li l-format tat-tranżazzjoni m'għandux għalfejn jinbidel, u l-provi UTXO għal nodi kompatti jistgħu jintremew, għalhekk kwalunkwe nodu kompatt jista 'jxandar b'mod simili tranżazzjonijiet lill-parteċipanti kollha tan-netwerk mingħajr il-parteċipazzjoni ta' nodi tal-pont.
Konklużjoni
Ħarsa lejn il-batterija Utreexo u implimentajna l-prototip tagħha f'Rut. Ħaresna lejn l-arkitettura tan-netwerk li se tippermetti l-integrazzjoni ta 'nodi bbażati fuq batteriji. Il-vantaġġ tal-qabdiet kompatti huwa d-daqs tad-dejta maħżuna, li jiddependi b'mod logaritmiku fuq il-qawwa tas-sett ta 'UTXOs, li jnaqqas ħafna r-rekwiżiti għall-ispazju tad-diska u l-prestazzjoni tal-ħażna għal tali nodi. L-iżvantaġġ huwa t-traffiku ta 'nodi addizzjonali għat-trażmissjoni tal-provi, iżda tekniki ta' aggregazzjoni tal-evidenza (meta prova waħda tipprova l-eżistenza ta 'diversi elementi) u l-caching jistgħu jgħinu biex iżommu t-traffiku f'limiti aċċettabbli.
referenzi:
- -
Sors: www.habr.com