Hi Habr!
Anns an lìonra Bitcoin, tha a h-uile nod, tro cho-aontachd, ag aontachadh air seata de UTXO: cia mheud buinn a tha rim faighinn airson a chaitheamh, cò dha dìreach, agus fo na suidheachaidhean. Is e an seata UTXO an t-seata dàta as lugha a dh’ fheumar airson nód dearbhaidh, às aonais sin cha bhith e comasach don nód dearbhadh a dhèanamh air èifeachd ghnothaichean a tha a’ tighinn a-steach agus na blocaichean anns a bheil iad.
A thaobh seo, thathas a ’dèanamh oidhirpean anns a h-uile dòigh gus an riochdachadh stòraichte den t-seata seo a lughdachadh, gus a dhlùthadh gun a bhith a’ call barantas tèarainteachd. Mar as lugha an àireamh de dhàta a tha air a stòradh, is ann as ìsle a bhios feumalachdan àite diosc an nòta dearbhaidh, a tha a’ fàgail nòta dearbhaidh saor, a’ leigeil leat an lìonra a leudachadh agus mar sin seasmhachd an lìonra a mheudachadh.
Anns an dreuchd seo cuiridh sinn suas prototype Rust de mholadh o chionn ghoirid bho cho-ùghdar , - , a leigeas le bhith a’ lughdachadh riatanasan àite diosc airson nodan dearbhaidh.
Dè an duilgheadas a th’ ann?
Is e aon de na duilgheadasan maireannach aig Bitcoin a scalability. Tha am beachd air “am banca agad fhèin” ag iarraidh air com-pàirtichean lìonra clàran a chumail den airgead gu lèir a tha ri fhaighinn airson a chleachdadh. Ann am Bitcoin, tha airgead a tha ri fhaotainn air a chur an cèill mar sheata de thoraidhean nach deach a chosg - seata UTXO. Ged nach e riochdachadh gu sònraichte intuitive a tha seo, tha e buannachdail a thaobh coileanadh buileachaidh thairis air riochdachadh anns a bheil “cothromachadh” aig gach “wallet” mar inntrigeadh air leth, agus cuideachd a ’cur prìobhaideachd ris (me. ).
Tha e cudromach eadar-dhealachadh a dhèanamh eadar eachdraidh ghnothaichean (rud ris an canar blockchain) agus staid làithreach an t-siostaim. Tha eachdraidh malairt Bitcoin an-dràsta a’ gabhail thairis mu 200 GB de dh’ àite diosc, agus a’ sìor fhàs. Ach, tha staid an t-siostaim mòran nas lugha, air òrdugh 4 GB, agus chan eil e a’ toirt aire ach don fhìrinn gu bheil buinn aig cuideigin an-dràsta. Bidh meud an dàta seo cuideachd ag àrdachadh thar ùine, ach aig ìre gu math nas slaodaiche agus uaireannan eadhon buailteach a dhol sìos (faic CDPV).
Bidh teachdaichean aotrom (SPVn) a’ toirt barrantas do thèarainteachd airson an comas gun a bhith a’ stòradh stàite as ìsle (UTXO-set) ach a-mhàin iuchraichean prìobhaideach.
UTXO agus UTXO-set
Is e UTXO (Toradh Gluasaid gun Chaith) an toradh malairt nach deach a chaitheamh, puing crìochnachaidh turas gach Satoshi air a ghluasad ann an gnothaichean. Bidh toraidhean nach deach a chaitheamh a’ tighinn a-steach do ghnothaichean ùra agus mar sin air an caitheamh (caitheamh) agus air an toirt air falbh bhon t-seata UTXO.
Bidh UTXOan ùra an-còmhnaidh air an cruthachadh le gnothaichean:
- gnothaichean coinbase gun a bhith a 'toirt a-steach: cruthaich UTXOan ùra nuair a bhios mèinnearan a' toirt seachad bhuinn
- gnothaichean cunbhalach: cruthaich UTXOan ùra fhad ‘s a tha thu a’ cosg seata sònraichte de UTXO a tha ann mar-thà
Pròiseas ag obair le UTXO:
Bidh wallets a’ cunntadh an àireamh de bhuinn a tha rim faighinn airson caitheamh (cothromachadh) stèidhichte air an ìre de UTXO a tha ri fhaighinn don wallet seo airson a chaitheamh.
Feumaidh gach nód dearbhaidh, gus casg a chuir air oidhirpean caitheamh dùbailte, sùil a chumail air an t-seata всех UTXO nuair a nì thu sgrùdadh each gnothaichean gach fear bhac.
Feumaidh loidsig a bhith aig an nód:
- Cur-ris ri seata UTXO
- Sguab às bho UTXO-set
- A’ sgrùdadh làthaireachd aon UTXO ann an seata
Tha dòighean ann air na riatanasan airson fiosrachadh a tha air a stòradh mu sheata a lughdachadh, fhad ‘s a chumas tu an comas eileamaidean a chuir ris agus a thoirt air falbh, sgrùdadh agus dearbhadh gu bheil eileamaid ann an seata a’ cleachdadh .
Bataraidhean airson UTXO
Am beachd a bhith a 'cleachdadh bataraidhean gus iomadh UTXO a stòradh .
Tha an seata UTXO air a thogail air a’ iteig, rè an luchdachadh sìos bloc tùsail (IBD), air a stòradh gu h-iomlan agus gu maireannach, fhad ‘s a bhios an susbaint ag atharrachadh às deidh a bhith a’ giullachd ghnothaichean bho gach bloc ùr agus ceart den lìonra. Feumaidh am pròiseas seo luchdachadh sìos timcheall air 200 GB de dhàta bloc agus dearbhadh ceudan de mhilleanan de ainmean didseatach. Às deidh pròiseas IBD a bhith air a chrìochnachadh, is e an loidhne gu h-ìosal gum bi an seata UTXO timcheall air 4 GB.
Ach, le luchd-cruinneachaidh, tha na riaghailtean co-aontachd airson airgead air an lughdachadh gu bhith a’ dearbhadh agus a’ gineadh dearbhaidhean criptografach, agus tha an t-uallach airson sùil a chumail air airgead a tha ri fhaighinn air a ghluasad gu sealbhadair na maoine sin, a bheir seachad dearbhadh gu bheil iad ann agus gu bheil iad ann.
Faodaidh neach-cruinneachaidh a bhith air ainmeachadh mar riochdachadh teann de sheata. Feumaidh meud an riochdachadh a tha air a stòradh a bhith seasmhach , no àrdachadh gu sublinearally a thaobh cardinality an t-seata agus meud an eileamaid fhèin, mar eisimpleir , far a bheil n mar phrìomhachas an t-seata a tha air a stòradh.
Anns a 'chùis seo, bu chòir don neach-cruinneachaidh leigeil le dearbhadh a bhith a' toirt a-steach eileamaid san t-seata (dearbhadh in-ghabhail) agus a dhèanamh comasach an dearbhadh seo a dhearbhadh gu h-èifeachdach.
Canar am bataraidh fiùghantach ma leigeas leat eileamaidean a chur ris agus eileamaidean a thoirt air falbh bho sheata.
Bhiodh eisimpleir de leithid de bataraidh . Tha meud seasmhach de riochdachadh stòraichte aig a leithid de chruinneadair, ach tha feum air làthaireachd dìomhaireachd co-roinnte (suidheachadh earbsach). Tha an riatanas seo a’ diùltadh iomchaidheachd a leithid de neach-cruinneachaidh airson lìonraidhean earbsach mar Bitcoin, leis gum faod aodion dàta aig àm gineadh dìomhair leigeil le luchd-ionnsaigh dearbhadh meallta a chruthachadh gu bheil UTXO ann, nodan meallta le seata UTXO stèidhichte air a leithid de neach-cruinneachaidh.
Utreexo
Tha an dealbhadh Utreexo a mhol Thaddeus Dryja ga dhèanamh comasach a chruthachadh fiùghantach аккумулятор gun earbsach-shuidheachadh.
Tha Utreexo na choille de dhànachd foirfe agus tha e na leasachadh air na beachdan a tha air an taisbeanadh ann , a 'cur ris a' chomas eileamaidean a thoirt air falbh bho sheata.
Structar loidsigeach bataraidh
Tha na ceallan bataraidh air an rèiteachadh ann an coille de chraobhan dà-chànanach. Tha craobhan air an òrdachadh a rèir àirde. Chaidh an riochdachadh seo a thaghadh mar an fheadhainn as lèirsinneach agus leigidh e leat co-aonadh chraobhan fhaicinn rè gnìomhachd air a’ bhataraidh.
Tha an t-ùghdar a’ toirt fa-near, leis gu bheil a h-uile craobh sa choille air leth freagarrach, gu bheil an àirde aca air a chuir an cèill mar chumhachd dhà, dìreach mar a dh’ fhaodar àireamh nàdarra sam bith a riochdachadh mar shuim chumhachdan dhà. Mar sin, faodar seata sam bith de dhuilleagan a chur ann an craobhan dà-chànanach, agus anns a h-uile suidheachadh, feumar eòlas a chur air eileamaid ùr dìreach mu bhun-nòtaichean craobhan a tha air an stòradh.
Mar sin, tha an riochdachadh stòraichte den neach-cruinneachaidh Utreexo na liosta de nodan freumh (freumh Merkle), agus cha'n e coille nan craobh uile.
Leig leinn liosta de na h-eileamaidean bunaiteach a riochdachadh mar Vec<Option<Hash>>. Seòrsa roghainneil Option<Hash> a 'sealltainn gum faodadh an eileamaid bunaiteach a bhith a dhìth, a tha a' ciallachadh nach eil craobh leis an àirde iomchaidh anns a 'chruinneadair.
/// 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],
}
}
}A 'cur eileamaidean ris
An toiseach, leigidh sinn cunntas air a 'ghnìomh parent(), a tha ag aithneachadh an nód pàrant airson dà eileamaid ainmichte.
pàrant() gnìomh
Leis gu bheil sinn a’ cleachdadh craobhan Merkle, is e pàrant gach aon den dà nód aon nód a bhios a’ stòradh hash co-chòrdadh hashes nodan an leanaibh:
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[..])
}Tha an t-ùghdar a’ toirt fa-near, gus casg a chuir air na h-ionnsaighean a mhìnich Teàrlach Bouillaguet, Pierre-Alain Fouque, Adi Shamir, agus Sebastien Zimmer ann an
, a bharrachd air an dà hashes, bu chòir an àirde taobh a-staigh a 'chraoibh a chur ris a' cho-chòrdadh cuideachd.
Mar a chuireas tu eileamaidean ris a 'chruinneadair, feumaidh tu sùil a chumail air dè na h-eileamaidean bunaiteach a tha air an atharrachadh. Le bhith a’ leantainn an t-slighe gu bhith ag atharrachadh na bun-eileamaidean airson gach eileamaid a chuireas tu ris, faodaidh tu dearbhadh a dhèanamh nas fhaide air adhart air làthaireachd nan eileamaidean sin.
Cum sùil air atharrachaidhean mar a chuireas tu iad ris
Gus sùil a chumail air na h-atharrachaidhean a chaidh a dhèanamh, leig dhuinn an structar ainmeachadh Update, a stòradh dàta mu atharrachaidhean nod.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Gus eileamaid a chur ris a 'bhataraidh, feumaidh tu:
- Cruthaich sreath de bhasgaidean de bhun-eileamaidean
new_rootsagus cuir na bun-eileamaidean a th’ ann an sin, aon airson gach bucaid:
còd a '
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);
}- Cuir ris na h-eileamaidean a tha ri chur ris (sreath
insertions) chun a' chiad chairtnew_roots[0]:
còd a '
new_roots[0].extend_from_slice(insertions);- Co-aonaich na nithean a chaidh a chur ris a’ chiad bhasgaid leis a’ chòrr:
- Airson a h-uile cairt le barrachd air aon rud:
- Gabh dà eileamaid bho dheireadh a 'bhasgaid, obrachadh a-mach am pàrant, a thoirt air falbh an dà eileamaid
- Cuir am pàrant àireamhaichte ris an ath chairt
- Airson a h-uile cairt le barrachd air aon rud:
còd a '
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 });
}
}- Gluais na h-eileamaidean bunaiteach bho bhionaichean gu raon cruinneachaidh a thig às
còd a '
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]);
}
}Cruthachadh dearbhadh airson eileamaidean a bharrachd
Dearbhadh gun deach an cealla a thoirt a-steach don bhataraidh (Proof) bidh e na Shlighe Merkle, air a dhèanamh suas de shlabhraidh ProofStep. Mura h-eil an t-slighe a’ dol gu àite sam bith, tha an dearbhadh ceàrr.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}A’ cleachdadh an fhiosrachaidh a fhuaireadh na bu thràithe nuair a thathar a’ cur eileamaid (structar Update), faodaidh tu dearbhadh a chruthachadh gun deach eileamaid a chuir ris a’ bhataraidh. Gus seo a dhèanamh, thèid sinn tron chlàr de dh’ atharrachaidhean a chaidh a dhèanamh agus cuiridh sinn gach ceum ri slighe Merkle, a bhios mar dhearbhadh an dèidh sin:
còd a '
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
}
}Pròiseas a bhith a 'cruthachadh dearbhadh
A’ sgrùdadh an dearbhaidh airson eileamaid
Bidh sgrùdadh dearbhadh in-ghabhail eileamaid sìos gu bhith a’ leantainn slighe Merkle gus am bi e a’ leantainn gu eileamaid freumhaich a th’ ann mar-thà:
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
}
}Gu lèirsinneach:
Pròiseas sgrùdadh air an dearbhadh airson A
A 'toirt air falbh stuthan
Gus cealla a thoirt air falbh bho bataraidh, feumaidh tu dearbhadh dligheach a thoirt seachad gu bheil an cealla ann. A’ cleachdadh an dàta bhon dearbhadh, tha e comasach obrachadh a-mach bun-eileamaidean ùra den neach-cruinneachaidh far nach bi an dearbhadh a chaidh a thoirt seachad fìor tuilleadh.
Tha an algorithm mar a leanas:
- A bharrachd air an sin, bidh sinn a’ cur air dòigh seata de bhasgaidean falamh a tha co-chosmhail ri craobhan Merkle le àirde co-ionann ri cumhachd dhà bho chlàr-amais a’ bhasgaid
- Bidh sinn a 'toirt a-steach eileamaidean bho staidhre slighe Merkle a-steach do na basgaidean; tha clàr-amais a’ bhasgaid co-ionann ri àireamh a’ cheum làithreach
- Bidh sinn a 'toirt air falbh an eileamaid bunaiteach ris a bheil an t-slighe bhon dearbhadh a' leantainn
- Mar le cur-ris, bidh sinn a’ tomhas eileamaidean freumha ùra le bhith a’ cothlamadh eileamaidean bho bhasgaidean ann an càraidean agus a’ gluasad toradh an aonaidh chun ath bhasgaid.
còd a '
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;
}
}Tha am pròiseas toirt air falbh eileamaid "A":
Amalachadh ann an lìonra a tha ann mar-thà
Le bhith a’ cleachdadh an inneal-cruinneachaidh a thathar a’ moladh, faodaidh nodan DB a sheachnadh gus a h-uile UTXO a stòradh fhad ‘s a tha iad fhathast comasach air an t-seata UTXO atharrachadh. Ach, tha duilgheadas ann a bhith ag obair le fianais ag èirigh.
Canaidh sinn an nód dearbhaidh a chleachdas an inneal-cruinneachaidh UTXO cruinn (nòd compact-state), agus is e an neach-dearbhaidh gun neach-cruinneachaidh coileanta (nòd làn). Tha dà chlas de nodan a 'cruthachadh duilgheadas airson an ceangal a-steach do aon lìonra, oir tha feum air dearbhadh gu bheil nodan cruaidh air dearbhadh gu bheil UTXO ann, a tha air a chosg ann an gnothaichean, fhad' sa tha nodan slàn nach eil. Mura gluais a h-uile nod lìonra aig an aon àm agus ann an dòigh cho-òrdanaichte gu bhith a’ cleachdadh Utreexo, thèid nodan teann fhàgail air chùl agus cha bhith e comasach dhaibh obrachadh air lìonra Bitcoin.
Gus fuasgladh fhaighinn air an duilgheadas a thaobh a bhith ag amalachadh nodan teann a-steach don lìonra, thathas a’ moladh clas a bharrachd de nodan a thoirt a-steach - drochaidean. Tha nód drochaid na nód iomlan a bhios cuideachd a’ stòradh bataraidh Utreexo agus dearbhadh cumhachd air всех UTXO bho UTXO-set. Bidh drochaidean a’ tomhas hashes ùra agus ag ùrachadh an neach-cruinneachaidh agus dearbhaidhean mar a thig blocaichean malairt ùra. Cha bhith cumail suas agus ùrachadh an neach-cruinneachaidh agus dearbhaidhean a’ cur uallach àireamhachd a bharrachd air na nodan sin. Bidh drochaidean ag ìobairt àite diosc: feumar rudan a chumail eagraichte hashes, an coimeas ri hashes airson nodan teann, far a bheil n cumhachd an t-seata UTXO.
Ailtireachd lìonra
Bidh drochaidean ga dhèanamh comasach nodan teann a chuir ris an lìonra mean air mhean gun a bhith ag atharrachadh bathar-bog nan nodan a th’ ann mar-thà. Bidh nodan slàn ag obair mar a bha iad roimhe, a’ cuairteachadh ghnothaichean agus bhlocaichean nam measg fhèin. Tha nodan drochaid nan nodan slàn a bhios cuideachd a’ stòradh dàta bataraidh Utreexo agus seata de dhearbhaidhean in-ghabhail airson всех UTXO airson a-nis. Chan eil nód na drochaid a’ sanasachadh fhèin mar sin, a’ leigeil air gur e làn nód a th’ ann airson a h-uile nod slàn agus nód teann airson a h-uile tè teann. Ged a tha drochaidean a 'ceangal an dà lìonra ri chèile, chan fheum iad ach an ceangal ann an aon taobh: bho nodan slàn a th' ann mar-thà gu nodan cruaidh. Tha seo comasach leis nach fheum an cruth malairt atharrachadh, agus faodar dearbhaidhean UTXO airson nodan teann a thilgeil air falbh, agus mar sin faodaidh nòta teann sam bith gnothaichean a chraoladh gu com-pàirtichean lìonra gun a bhith an sàs ann an nodan drochaid.
co-dhùnadh
Thug sinn sùil air bataraidh Utreexo agus chuir sinn an gnìomh a prototype ann an Rust. Choimhead sinn air ailtireachd an lìonraidh a leigeas le nodan stèidhichte air bataraidh aonachadh. Is e a ’bhuannachd a th’ ann an glacaidhean teann meud an dàta a tha air a stòradh, a tha an urra gu logarithmeach air cumhachd an t-seata de UTXO, a lughdaicheas gu mòr na riatanasan airson àite diosc agus coileanadh stòraidh airson na nodan sin. Is e an ana-cothrom an trafaic nód a bharrachd airson a bhith a’ sgaoileadh dhearbhaidhean, ach faodaidh dòighean cruinneachaidh fianais (nuair a dhearbhas aon dearbhadh gu bheil grunn eileamaidean ann) agus tasgadan cuideachadh gus trafaic a chumail taobh a-staigh crìochan iomchaidh.
iomraidhean:
- -
Source: www.habr.com