Hai Habr!
A cikin hanyar sadarwar Bitcoin, duk nodes, ta hanyar yarjejeniya, sun yarda akan saitin UTXOs: tsabar kudi nawa ne don ciyarwa, ga wanene daidai, da kuma wane yanayi. Saitin UTXO shine mafi ƙarancin saitin bayanan da ake buƙata don kumburin mai inganci, idan ba tare da wanda kumburin ba zai iya tabbatar da ingancin ma'amala mai shigowa da tubalan da ke ɗauke da su.
Dangane da haka, ana ƙoƙarin ta kowace hanya don rage yawan wakilcin wannan saitin, don danne shi ba tare da rasa garantin tsaro ba. Ƙananan ƙarar bayanan da aka adana, ƙananan buƙatun sararin faifai na kullin mai inganci, wanda ke sa ƙaddamar da kumburin mai inganci mai arha, yana ba ku damar faɗaɗa hanyar sadarwa kuma ta haka ƙara kwanciyar hankali na hanyar sadarwa.
A cikin wannan sakon za mu buga samfurin Rust na wani tsari na kwanan nan daga marubucin haɗin gwiwa , - , wanda ke ba da damar rage buƙatun sararin faifai don nodes masu inganci.
Menene fa'ida?
Ɗaya daga cikin matsalolin Bitcoin na shekara-shekara shine haɓakarsa. Tunanin "bankin ku" yana buƙatar mahalarta cibiyar sadarwa su adana bayanan duk kuɗin da ake amfani da su. A cikin Bitcoin, ana bayyana kuɗaɗen da ake samu azaman saitin abubuwan da ba a kashe su ba - saitin UTXO. Duk da yake wannan ba wakilci ba ne na musamman, yana da fa'ida dangane da aiwatar da aiwatarwa akan wakilci wanda kowane "walat" yana da "ma'auni" azaman shigarwa daban, kuma yana ƙara sirri (misali. ).
Yana da mahimmanci a rarrabe tsakanin tarihin ma'amaloli (abin da ake kira blockchain) da kuma halin yanzu na tsarin. Tarihin ma'amala na Bitcoin a halin yanzu yana ɗaukar kusan 200 GB na sararin faifai, kuma yana ci gaba da girma. Koyaya, tsarin tsarin ya fi ƙanƙanta, akan tsari na 4 GB, kuma kawai yana la'akari da gaskiyar cewa wani a halin yanzu yana da tsabar kudi. Ƙarfin wannan bayanan kuma yana ƙaruwa akan lokaci, amma a hankali a hankali kuma wani lokacin ma yakan rage (duba CDPV).
Abokan ciniki masu haske (SPVs) garantin tsaro na kasuwanci don ikon adana mafi ƙarancin jiha (UTXO-set) ban da maɓallan sirri.
UTXO da UTXO-saitin
UTXO (Unspent Transaction Output) shine fitarwar ciniki da ba a kashe ba, ƙarshen tafiya na kowane Satoshi da aka canjawa wuri a cikin ma'amaloli. Abubuwan da ba a kashe ba sun zama abubuwan shigar da sabbin ma'amaloli kuma ana kashe su (kashewa) kuma an cire su daga saitin UTXO.
Sabbin UTXOs koyaushe ana ƙirƙira su ta hanyar ma'amaloli:
- coinbase ma'amaloli ba tare da bayanai ba: ƙirƙirar sabbin UTXO lokacin da masu hakar ma'adinai ke fitar da tsabar kudi
- ma'amaloli na yau da kullun: ƙirƙira sabbin UTXO yayin ciyar da takamaiman saitin UTXOs ɗin da ake da su
Tsarin aiki tare da UTXO:
Wallets suna ƙididdige adadin tsabar kuɗi da ake da su don ciyarwa (ma'auni) dangane da adadin UTXO da ke akwai ga wannan jakar kuɗi don ciyarwa.
Kowane kumburi mai inganci, don hana yunƙurin kashe kuɗi sau biyu, dole ne a saka idanu akan saitin всех UTXO lokacin dubawa kowane ma'amaloli kowane toshe.
Dole ne kullin ya kasance yana da tunani:
- Ƙara zuwa UTXO-saitin
- Sharewa daga UTXO-saitin
- Duban kasancewar UTXO guda ɗaya a cikin saiti
Akwai hanyoyin da za a rage buƙatun bayanan da aka adana game da saiti, yayin da ake kiyaye ikon ƙarawa da cire abubuwa, bincika da tabbatar da kasancewar wani abu a cikin saitin ta amfani da .
Batura don UTXO
Tunanin yin amfani da batura don adana UTXO da yawa .
An gina UTXO-saitin akan tashi, yayin saukar da farkon toshe (IBD), an adana shi cikakke kuma har abada, yayin da abubuwan da ke ciki ke canzawa bayan sarrafa ma'amaloli daga kowane sabon kuma daidai toshe na hanyar sadarwa. Wannan tsari yana buƙatar zazzage kusan 200 GB na bayanan toshewa da kuma tabbatar da ɗaruruwan miliyoyin sa hannun dijital. Bayan an gama aikin IBD, layin ƙasa shine saitin UTXO zai mamaye kusan 4 GB.
Koyaya, tare da masu tara kuɗi, ƙa'idodin yarjejeniya don kuɗi suna raguwa zuwa tabbatarwa da haɓakar bayanan sirri, kuma nauyin bin diddigin kudaden da ake samu an koma ga mai waɗannan kuɗin, wanda ke ba da tabbacin wanzuwarsu da ikon mallakar su.
Ana iya kiran mai tara tarawa taƙaitaccen wakilci na saiti. Girman wakilcin da aka adana dole ne ya kasance ko dai akai , ko ƙara ƙaranci dangane da kadinity na saitin da girman abin da kansa, misali. , inda n shine kadinality na saitin da aka adana.
A wannan yanayin, mai tarawa ya kamata ya ƙyale samar da hujjar haɗa wani abu a cikin saitin (tabbacin haɗawa) kuma ya ba da damar tabbatar da wannan tabbacin yadda ya kamata.
Ana kiran baturin tsauri idan ya baka damar ƙara abubuwa da cire abubuwa daga saiti.
Misalin irin wannan baturi zai kasance . Irin wannan tarawa yana da madaidaicin girman wakilcin da aka adana, amma yana buƙatar kasancewar sirrin raba (amintaccen saitin). Wannan abin da ake buƙata ya hana yin amfani da irin wannan mai tarawa don cibiyoyin sadarwa marasa aminci kamar Bitcoin, tun lokacin da aka zubar da bayanai a lokacin tsararru na asiri na iya ba da damar maharan su haifar da shaidar ƙarya na wanzuwar UTXO, yaudarar nodes tare da UTXO-saitin dangane da irin wannan tarawa.
Utreexo
Tsarin Utreexo wanda Thaddeus Dryja ya gabatar ya ba da damar ƙirƙirar tsauri Ð ° ккумуР»Ñ Ñ,Ð¾Ñ € ba tare da amintaccen saiti.
Utreexo daji ne na cikakken binary kuma shine ci gaban ra'ayoyin da aka gabatar a ciki , ƙara ikon cire abubuwa daga saiti.
Tsarin Hankali na Baturi
Kwayoyin baturi an shirya su a cikin gandun daji na bishiyoyi masu kyau. Ana yin odar bishiyoyi da tsayi. An zaɓi wannan wakilcin a matsayin mafi gani kuma yana ba ku damar ganin haɗewar bishiyoyi yayin aiki akan baturi.
Marubucin ya lura cewa tun da yake duk bishiyoyin da ke cikin daji suna da kyau, ana bayyana tsayin su a matsayin ikon biyu, kamar yadda kowane adadi na halitta zai iya wakiltar jimillar iko biyu. Saboda haka, kowane nau'i na ganye za a iya haɗa shi zuwa bishiyar binaryar, kuma a kowane hali, ƙara sabon abu yana buƙatar ilimi kawai game da tushen nodes na itatuwan da aka adana.
Don haka, wakilcin da aka adana na Utreexo accumulator shine jerin tushen nodes (tushen Merkle), kuma ba duka dajin bishiyoyi ba.
Bari mu wakilci jerin tushen abubuwan kamar Vec<Option<Hash>>. Nau'in zaɓi Option<Hash> yana nuna cewa tushen tushen zai iya ɓacewa, wanda ke nufin cewa babu wata bishiya mai tsayin da ya dace a cikin tarawa.
/// 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],
}
}
}Ƙara abubuwa
Da farko, bari mu kwatanta aikin parent(), wanda ke gane kullin iyaye don abubuwa biyu da aka ba su.
aikin iyaye ().
Tun da muna amfani da bishiyar Merkle, iyayen kowane kumburin biyun kumburi ɗaya ne wanda ke adana hash na haɗin hashes na nodes na yara:
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[..])
}Marubucin ya lura cewa don hana hare-haren da Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, da Sebastien Zimmer suka bayyana a cikin
, ban da hashes guda biyu, tsayin da ke cikin bishiyar ya kamata kuma a ƙara shi a cikin haɗuwa.
Yayin da kuke ƙara abubuwa zuwa mai tarawa, kuna buƙatar ci gaba da bin diddigin abubuwan tushen tushen. Ta hanyar bin hanyar canza tushen abubuwan kowane sinadari da kuka ƙara, zaku iya gina hujjar kasancewar waɗannan abubuwan.
Bibiya canje-canje yayin da kuke ƙara su
Don bin sauye-sauyen da aka yi, bari mu ayyana tsarin Update, wanda zai adana bayanai game da canje-canjen kumburi.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Don ƙara wani abu a baturin, kuna buƙatar:
- Ƙirƙiri tsararrun kwanduna na abubuwan tushen
new_rootskuma sanya tushen abubuwan da ke akwai a wurin, ɗaya ga kowane guga:
Lambar
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);
}- Haɗa abubuwan da za a ƙara (array
insertions) zuwa keken farkonew_roots[0]:
Lambar
new_roots[0].extend_from_slice(insertions);- Haɗa abubuwan da aka haɗa zuwa kwandon farko tare da sauran:
- Ga duk katuna masu abubuwa sama da ɗaya:
- Ɗauki abubuwa biyu daga ƙarshen kwandon, ƙididdige iyayensu, cire abubuwa biyu
- Ƙara iyaye da aka ƙididdige zuwa kuzun na gaba
- Ga duk katuna masu abubuwa sama da ɗaya:
Lambar
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 });
}
}- Matsar da tushen abubuwa daga bins zuwa sakamakon tarawa
Lambar
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]);
}
}Ƙirƙirar hujja don ƙarin abubuwa
Tabbacin haɗa tantanin halitta a cikin baturi (Proof) zai kasance a matsayin hanyar Merkle, wanda ya ƙunshi sarkar ProofStep. Idan hanyar ba ta kai ko'ina ba, to hujjar ba daidai ba ce.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Amfani da bayanin da aka samu a baya lokacin ƙara wani abu (tsarin Update), za ka iya ƙirƙirar hujja cewa an ƙara wani abu a baturi. Don yin wannan, za mu shiga cikin teburin canje-canjen da aka yi kuma muna ƙara kowane mataki zuwa hanyar Merkle, wanda daga baya zai zama hujja:
Lambar
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
}
}Tsarin samar da hujja
Bincika hujja don wani abu
Bincika hujjar haɗa wani abu yana tafasa ƙasa zuwa bin hanyar Merkle har sai ya kai ga tushen tushen tushen:
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
}
}Na gani:
Tsarin duba tabbacin A
Cire abubuwa
Don cire tantanin halitta daga baturi, dole ne ka bayar da ingantaccen shaida cewa tantanin halitta yana nan. Yin amfani da bayanan daga hujja, yana yiwuwa a ƙididdige sabbin abubuwan tushen abubuwan tarawa waɗanda shaidar da aka bayar ba za ta ƙara zama gaskiya ba.
Algorithm shine kamar haka:
- Kamar yadda yake da ƙari, muna tsara saitin kwanduna mara kyau wanda ya dace da bishiyoyin Merkle tare da tsayi daidai da ƙarfin biyu daga ma'aunin kwandon.
- Muna saka abubuwa daga matakan hanyar Merkle cikin kwanduna; fihirisar kwandon daidai yake da adadin matakin yanzu
- Muna cire tushen tushen abin da hanyar daga hujja ke kaiwa
- Kamar yadda ake ƙarawa, muna ƙididdige sababbin abubuwan tushen ta hanyar haɗa abubuwa daga kwanduna a bi-biyu da matsar da sakamakon ƙungiyar zuwa kwando na gaba.
Lambar
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;
}
}Tsarin cire element "A":
Haɗuwa cikin hanyar sadarwa mai wanzuwa
Amfani da samarwa tarawa, nodes iya kauce wa yin amfani da DB don adana duk UTXOs yayin da har yanzu iya canza UTXO-saitin. Duk da haka, matsalar aiki tare da shaida ta taso.
Bari mu kira kumburin mai inganci wanda ke amfani da tarawar UTXO m (karamin-jihar kumburi), kuma mai inganci ba tare da tarawa ba shine cikakke (cikakken kumburi). Kasancewar azuzuwan nodes yana ƙirƙirar matsala don haɗe su cikin hanyar sadarwa ɗaya, tunda ƙananan nodes na buƙatar tabbacin kasancewar, yayin da aka yi nodes. Idan duk nodes na cibiyar sadarwa ba su yi lokaci guda ba kuma a cikin hanyar haɗin gwiwa suna canzawa zuwa amfani da Utreexo, to za a bar ƙananan nodes a baya kuma ba za su iya aiki akan hanyar sadarwar Bitcoin ba.
Don magance matsalar haɗa ƙananan nodes a cikin hanyar sadarwa, an ba da shawarar gabatar da ƙarin nau'in nodes - gadoji. Kullin gada cikakken kulli ne wanda kuma ke adana baturin Utreexo da hujjar wutar lantarki всех UTXO daga UTXO-set. Gada suna lissafin sabbin hashes kuma suna sabunta mai tarawa da hujjoji yayin da sabbin tubalan ma'amaloli suka isa. Kulawa da sabunta mai tarawa da hujjoji baya sanya ƙarin nauyin lissafi akan irin waɗannan nodes. Bridges suna sadaukar da sararin faifai: buƙatar kiyaye abubuwa da tsari hashes, idan aka kwatanta da hashes don ƙananan nodes, inda n shine ikon saitin UTXO.
Gine-ginen hanyar sadarwa
Gada yana ba da damar ƙara ƙananan nodes a hankali zuwa cibiyar sadarwar ba tare da canza software na nodes ɗin da ke akwai ba. Cikakkun nodes suna aiki kamar da, suna rarraba ma'amaloli da tubalan a tsakaninsu. Nodes na gada cikakkun nodes ne waɗanda kuma ke adana bayanan baturin Utreexo da saitin shaidar haɗawa don всех UTXO a halin yanzu. Kullin gada baya tallata kansa kamar haka, yana yin kamar ya zama cikakken kumburi ga duk cikakkun kuɗaɗe da ƙaramin kumburi ga duk ƙaƙƙarfan. Kodayake gadoji suna haɗa hanyoyin sadarwa biyu tare, a zahiri suna buƙatar haɗa su ta hanya ɗaya kawai: daga cikakkun nodes ɗin da ke akwai zuwa ƙananan nodes. Wannan yana yiwuwa saboda tsarin ma'amala baya buƙatar canza canjin, kuma ana iya watsar da hujjojin UTXO don ƙananan nodes, don haka kowane ƙaramin kumburi zai iya watsa ma'amaloli iri ɗaya ga duk mahalarta cibiyar sadarwa ba tare da shigar da nodes ɗin gada ba.
ƙarshe
Mun kalli baturin Utreexo kuma mun aiwatar da samfurinsa a cikin Rust. Mun duba tsarin gine-ginen cibiyar sadarwa wanda zai ba da damar haɗin haɗin tushen baturi. Amfanin ƙananan kamawa shine girman bayanan da aka adana, wanda ya dogara da logarithmically akan ikon saitin UTXOs, wanda ya rage girman buƙatun sararin diski da aikin ajiya don irin waɗannan nodes. Rashin lahani shine ƙarin zirga-zirgar kumburi don watsa hujjoji, amma dabarun tattara shaidu (lokacin da hujja ɗaya ta tabbatar da wanzuwar abubuwa da yawa) kuma caching na iya taimakawa ci gaba da zirga-zirga cikin iyakoki masu karɓuwa.
nassoshi:
- -
source: www.habr.com