Hei Habr!
I roto i te whatunga Bitcoin, nga pona katoa, na roto i te whakaaetanga, ka whakaae ki te huinga o nga UTXO: e hia nga moni e waatea ana mo te whakapau moni, ki a wai te mea, me te aha nga tikanga. Ko te huinga UTXO ko te huinga iti rawa o nga raraunga e hiahiatia ana mo te node whakamana, me te kore e kore e taea e te node te manatoko i te mana o nga whakawhitinga taumai me nga poraka kei roto.
I runga i tenei ahuatanga, kei te ngana ki nga huarahi katoa ki te whakaiti i te ahua rongoa o tenei huinga, ki te kopiri me te kore e ngaro nga taurangi haumarutanga. Ko te iti ake o te nui o nga raraunga rongoa, ka iti ake nga whakaritenga mokowā kōpae o te node validator, he iti te whakarewatanga o te node validator, ka taea e koe te whakawhänui i te whatunga me te whakanui ake i te pumau o te whatunga.
I roto i tenei pou ka whakairihia e matou he tauira Rust o tetahi tono hou mai i tetahi kaituhi , - , ka taea te whakaiti i nga whakaritenga mokowā kōpae mo nga pona whakamana.
He aha te raruraru?
Ko tetahi o nga raru o Bitcoin ko tona tauineine. Ko te whakaaro o "to koe peeke" me pupuri nga kaiuru whatunga ki te pupuri i nga rekoata o nga moni katoa e waatea ana hei whakamahi. I roto i te Bitcoin, ko nga moni e wātea ana e whakaatuhia ana hei huinga o nga putanga kore - he UTXO-set. Ahakoa ehara tenei i te ahua tino mohio, he painga mo te whakatinanatanga o nga mahi i runga i te whakaaturanga kei roto i ia "pukoro" he "pauna" hei urunga motuhake, me te taapiri i te waahi (hei tauira. ).
He mea nui ki te wehewehe i waenga i te hitori o nga whakawhitinga (he mea e kiia ana ko te poraka) me te ahua o te punaha o naianei. Ko te hitori o te tauwhitinga Bitcoin kei te 200 GB o te mokowā kōpae, me te tipu haere tonu. Engari, he iti ake te ahua o te punaha, i runga i te raupapa o te 4 GB, me te whakaaro noa ko te tangata kei a ia nga moni. Ka piki hoki te rahi o enei raraunga i roto i te waa, engari i te tere tere, i etahi wa ka heke haere (tirohia te CDPV).
Ko nga kaihoko marama (SPV) he taurangi taurangi tauhokohoko mo te kaha ki te penapena i nga ahuatanga iti rawa (UTXO-set) atu i nga taviri motuhake.
UTXO me UTXO-huinga
Ko te UTXO (Whakaahua Whakawhitinga Kaore) ko te whakaputanga tauwhitinga kore utu, ko te mutunga o te haerenga o ia Satoshi i whakawhitia i roto i nga whakawhitinga. Ko nga putanga kaore i whakapaua ka noho hei whakaurunga mo nga tauwhitinga hou, ka whakapaua (whakapaa) ka tangohia mai i te huinga-UTXO.
Ko nga UTXO hou ka hangaia e nga tauwhitinga:
- nga tauwhitinga coinbase kaore he whakaurunga: hangaia he UTXO hou ina tuku moni nga kaikeri
- tauwhitinga auau: hanga UTXO hou i te wa e whakapaua ana etahi huinga o nga UTXO
Te tukanga o te mahi me te UTXO:
Ka tatauhia e nga putea te maha o nga moni e waatea ana mo te whakapaunga (pauna) i runga i te nui o te UTXO e waatea ana ki tenei putea mo te whakapaunga.
Ia kōpuku whaimana, hei aukati i nga nganatanga whakapau rua, me aro turuki i te huinga всех UTXO i te wa e tirotirohia ana ia takitahi hokohoko Tuhinga o mua poraka.
Me whai arorau te node:
- Nga taapiri ki te UTXO-set
- Nga whakakorenga mai i te huinga-UTXO
- Te tirotiro i te aroaro o te UTXO kotahi i roto i te huinga
He huarahi hei whakaiti i nga whakaritenga mo nga korero rongoa mo tetahi huinga, me te pupuri i te kaha ki te taapiri me te tango i nga huānga, tirohia me te whakamatau i te noho o tetahi huānga i roto i te huinga ma te whakamahi .
Nga pākahiko mo te UTXO
Ko te whakaaro mo te whakamahi pākahiko hei penapena UTXO maha .
Ko te UTXO-set ka hangaia i runga i te rere, i te wa o te tangohanga poraka tuatahi (IBD), ka rongoa i roto i te katoa me te pumau tonu, i te mea ka huri nga ihirangi i muri i te tukatuka i nga whakawhitinga mai i ia poraka hou me te tika o te whatunga. Ko tenei tukanga me tango tata ki te 200 GB o nga raraunga poraka me te manatoko i nga rau miriona o nga waitohu mamati. I muri i te otinga o te tukanga IBD, ko te rarangi o raro ko te UTXO-set ka noho mo te 4 GB.
Engari, me te hunga kohikohi, ka whakahekehia nga ture o te whakaaetanga mo nga moni ki te manatoko me te whakatipuranga o nga tohu tohu, a, ko te taumahatanga o te aroturuki i nga moni e waatea ana ka nekehia ki te rangatira o aua moni, e whakaatu ana i to raatau oranga me o raatau mana.
Ka taea te kii he kaikorero he whakaaturanga kiato o te huinga. Me noho tonu te rahi o te whakaaturanga rongoa , te whakanui ake ranei i raro i te raina e pa ana ki te cardinality o te huinga me te rahi o te huānga ake, hei tauira , ko te n ko te cardinality o te huinga penapena.
I roto i tenei take, me whakaae te kaikohikohi ki te whakaputa tohu mo te whakaurunga o tetahi huānga ki roto i te huinga (tohu whakaurunga) ka taea te manatoko tika i tenei tohu.
Ka karangahia te pākahiko hihiri mena ka taea e koe te taapiri i nga huānga me te tango huānga mai i te huinga.
Ko tetahi tauira o te pākahiko penei . Ko taua accumulator he rahi tonu o te ahua rongoa, engari me whai waahi mea ngaro tahi (whakaritenga whakawhirinaki). Ka whakakorehia e tenei whakaritenga te whakaurunga o taua kohikohinga mo nga whatunga whakaponokore penei i te Bitcoin, na te mea ko te rerenga o nga raraunga i te wa o te whakatipuranga huna ka taea e nga kaiwhaiwhai te hanga tohu teka mo te noho o te UTXO, ma te tinihanga i nga pona me te UTXO-huinga i runga i taua kohinga.
Utreexo
Ko te hoahoa Utreexo i whakaarohia e Thaddeus Dryja ka taea te hanga hihiri kamupene kaore whakawhirinaki-setup.
Ko Utreexo he ngahere o te tino rua a he whanaketanga o nga whakaaro e whakaatuhia ana i roto , te taapiri i te kaha ki te tango i nga huānga mai i te huinga.
Hanganga Arorau Pūhiko
Kua whakaritea nga pūtau pākahiko i roto i te ngahere o nga rakau takirua pai. Ka raupapahia nga rakau ma te teitei. I kowhiria tenei whakaaturanga hei tirohanga tino pai ka taea e koe te tiro i te whakakotahitanga o nga rakau i te wa e mahi ana i te pākahiko.
E ai ki te kaituhi, i te mea he pai nga rakau katoa i roto i te ngahere, ka tohuhia to ratou teitei hei mana o te rua, pera i nga tau taiao ka taea te whakaatu hei huinga mana o te rua. Nā reira, ka taea te whakarōpūhia ngā huinga rau ki ngā rākau rua, ā, i ngā wā katoa, me whai mōhiotanga ki te tāpiri huānga hou. mo nga kopuku pakiaka anake o nga rakau rongoa.
No reira, ko te ahua rongoa o te Utreexo accumulator he rarangi o nga node pakiaka (Merkle root), a ehara i te ngahere katoa o nga rakau.
Me whakaatu te rarangi o nga huānga pakiaka hei Vec<Option<Hash>>. Momo whiriwhiri Option<Hash> e tohu ana kei te ngaro pea te huanga pakiaka, ko te tikanga karekau he rakau e tika ana te teitei o te kohinga.
/// 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],
}
}
}Te taapiri huānga
Tuatahi, me whakaahua te mahi parent(), e mohio ana ki te kopuku matua mo nga huānga e rua.
matua() mahi
I te mea kei te whakamahi matou i nga rakau Merkle, ko te matua o ia o nga node e rua he node kotahi e pupuri ana i te hash o te whakakotahitanga o nga hashes o nga pona tamaiti:
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[..])
}Ko te kaituhi e tuhi ana hei aukati i nga whakaeke i whakaahuatia e Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, me Sebastien Zimmer i
, i tua atu i nga hashes e rua, me tapiri ano te teitei o roto o te rakau ki te whakakotahitanga.
I a koe e taapiri ana i nga huānga ki te kaikohikohi, me whai tonu koe ki te whakarereke i nga huānga pakiaka. Ma te whai i te huarahi ki te whakarereke i nga huānga pakiaka mo ia huānga ka taapirihia e koe, ka taea e koe te hanga i tetahi tohu o te noho o enei huānga.
Aroturuki i nga huringa i a koe e taapiri ana
Hei whai i nga huringa, me whakaatu te hanganga Update, ka penapena raraunga mo nga huringa node.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Hei taapiri i tetahi huānga ki te pākahiko, me:
- Waihangahia he kete o nga huānga pakiaka
new_rootska tuu i nga huānga pakiaka o naianei ki reira, kotahi mo ia peere:
Waehere
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);
}- Whakapirihia nga huānga hei taapiri atu (array
insertions) ki te kaata tuatahinew_roots[0]:
Waehere
new_roots[0].extend_from_slice(insertions);- Whakakotahitia nga mea kua tapirihia ki te kete tuatahi me era atu:
- Mo nga kaata katoa neke atu i te kotahi nga mea:
- Tangohia kia rua nga huānga mai i te pito o te kete, tatauhia te matua, tangohia nga huānga e rua
- Tāpirihia te matua tātai ki te kaata e whai ake nei
- Mo nga kaata katoa neke atu i te kotahi nga mea:
Waehere
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 });
}
}- Nekehia nga huānga pakiaka mai i nga ipu ki te huānga whakaemi
Waehere
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]);
}
}Te hanga tohu mo nga huānga taapiri
He tohu mo te whakaurunga o te pūtau ki roto i te pākahiko (Proof) ka noho hei huarahi Merkle, he mekameka ProofStep. Ki te kore te ara e ahu ki hea, ka he te tohu.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Ma te whakamahi i nga korero i whiwhi i mua i te taapiri i tetahi huānga (hanganga Update), ka taea e koe te hanga tohu kua taapirihia he huānga ki te pākahiko. Ki te mahi i tenei, ka haere matou i roto i te ripanga o nga huringa i mahia ka taapirihia ia taahiraa ki te ara o Merkle, ka waiho hei tohu hei tohu:
Waehere
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
}
}Te tukanga o te hanga tohu
Te tirotiro i te tohu mo tetahi huānga
Ko te tirotiro i te tohu whakaurunga o tetahi huānga ka heke ki te whai i te ara Merkle kia tae ra ano ki tetahi huānga putake:
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
}
}Matakite:
Te tukanga o te tirotiro i nga tohu mo A
Te tango i nga taonga
Hei tango i te pūtau mai i te pākahiko, me whakaatu e koe he taunakitanga tika kei reira te pūtau. Ma te whakamahi i nga raraunga mai i te tohu, ka taea te tatau i nga huānga pakiaka hou o te kaikohikohi e kore e tika te tohu kua homai.
Ko te algorithm e whai ake nei:
- I tua atu, ka whakaritehia e matou he huinga kete kore e rite ana ki nga rakau Merkle me te teitei e rite ana ki te kaha o te rua mai i te tohu o te kete.
- Ka whakauruhia e matou nga huānga mai i nga hikoinga o te ara Merkle ki roto i nga kete; he rite te taupū kete ki te tau o te taahiraa o naianei
- Ka tangohia e matou te huānga pakiaka e ahu atu ai te ara mai i te tohu
- Pērā i te tāpiritanga, ka tātaihia ngā huānga pakiaka hōu mā te whakakotahi i ngā huānga mai i ngā kete kia takirua, ka nekehia te hua o te whakakotahitanga ki te kete e whai ake nei.
Waehere
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;
}
}Te tukanga o te tango i te huānga "A":
Te tuitui ki te whatunga o naianei
Ma te whakamahi i te kaiwhakaemi kua whakaarohia, ka taea e nga pona te karo i te whakamahi i te DB ki te penapena i nga UTXO katoa i te wa e kaha tonu ana te huri i te huinga-UTXO. Heoi, ka puta ake te raru o te mahi me nga taunakitanga.
Me karangahia te node whakamana e whakamahi ana i te kaikohiko UTXO kiato (kiato-ahua node), me te whaimana kahore he kaikoi ko oti (kopuku katoa). Ko te noho o nga karaehe e rua o nga pona he raru mo te whakauru i a raatau ki te whatunga kotahi, na te mea ka hiahiatia e nga pona kiato he tohu mo te oranga o nga UTXO, e whakapaua ana i roto i nga whakawhitiwhitinga, engari kaore nga kohanga katoa. Ki te kore nga pona whatunga katoa e huri i te wa kotahi me te huri i runga i te tikanga ruruku ki te whakamahi i te Utreexo, ka waiho nga pona kiato ki muri ka kore e taea te mahi i runga i te whatunga Bitcoin.
Hei whakatau i te raru o te whakauru i nga pona kiato ki roto i te whatunga, e whakaarohia ana kia whakauruhia he akomanga taapiri - piriti. Ko te node piriti he node katoa e pupuri ana hoki i te pākahiko Utreexo me te tohu hiko mo всех UTXO mai i te UTXO-set. Ka tatauhia e nga piriti nga tohu hou me te whakahou i te kaikohikohi me nga tohu ka tae mai nga poraka hou o nga whakawhitinga. Ko te pupuri me te whakahou i te kaikohikohi me nga tohu karekau e utaina atu te utaina rorohiko ki runga i aua pona. Ko nga piriti e patu ana i te mokowā kōpae: me whakarite nga mea Hashes, whakaritea ki Hashes mo nga pona kiato, ko n te mana o te huinga UTXO.
Te hoahoanga whatunga
Ka taea e nga piriti te taapiri i nga pona kiato ki te whatunga me te kore e huri i te rorohiko o nga pona o naianei. Ko nga pona katoa ka mahi pera i mua, ka tohatoha i nga whakawhitiwhitinga me nga poraka ki a raatau ano. Ko nga pona piriti he kohanga ki tonu hei pupuri i nga raraunga pākahiko Utreexo me te huinga tohu whakaurunga mo всех UTXO inaianei. Ko te node piriti e kore e panui i a ia ano, e kii ana he pona katoa mo nga pona katoa me te pona kiato mo nga pona kiato katoa. Ahakoa e hono ana nga piriti i nga hononga e rua, me hono noa ki te huarahi kotahi: mai i nga pona katoa o mua ki nga pona kiato. Ka taea tenei na te mea kaore e tika kia whakarereketia te whakatakotoranga tauwhitinga, ka taea te whakakore i nga tohu UTXO mo nga pona kiato, na reira ka taea e tetahi pona kiato te panui i nga whakawhitiwhitinga ki nga kaiuru whatunga katoa me te kore e uru mai nga pona piriti.
mutunga
I titiro matou ki te pākahiko Utreexo me te whakatinana i tana tauira ki Rust. I titiro matou ki te hoahoanga whatunga ka taea te whakauru o nga pona-a-hiko. Ko te painga o te hopu kiato ko te rahi o nga raraunga rongoa, e whakawhirinaki ana ki te kaha o te huinga o nga UTXO, e tino whakaiti ana i nga whakaritenga mo te mokowā kōpae me te mahi rokiroki mo aua pona. Ko te ngoikoretanga ko te taapiri atu i nga hokohoko node mo te tuku tohu, engari ko nga tikanga whakahiato taunakitanga (ka whakaatu tetahi tohu i te noho o te maha o nga huānga) ka taea e te keteroki te pupuri i nga waka i roto i nga rohe e whakaaetia ana.
tohutoro:
- -
Source: will.com