Эй Ҳабр!
Дар шабакаи Bitcoin, ҳама гиреҳҳо тавассути консенсус дар бораи маҷмӯи UTXOҳо мувофиқат мекунанд: чанд танга барои харҷ кардан дастрас аст, маҳз ба кӣ ва дар кадом шароит. Маҷмӯи UTXO маҷмӯи ҳадди ақали маълумотест, ки барои гиреҳи валидатор лозим аст, ки бе он гиреҳ дурустии транзаксияҳои воридотӣ ва блокҳои дорои онҳоро тафтиш карда наметавонад.
Дар робита ба ин, барои кам кардани намоиши захирашудаи ин маҷмӯа, фишурдани он бидуни аз даст додани кафолатҳои амниятӣ бо ҳар роҳ кӯшиш карда мешавад. Ҳаҷми маълумоти захирашуда ҳар қадар хурдтар бошад, талаботи фазои диски гиреҳи валидатор ҳамон қадар камтар мешавад, ки оғоз кардани гиреҳи валидаторро арзон мекунад, ба шумо имкон медиҳад, ки шабакаро васеъ кунед ва ба ин васила устувории шабакаро зиёд кунед.
Дар ин паём мо як прототипи Rust-ро аз пешниҳоди охирини ҳаммуаллиф интишор хоҳем кард , - , ки имкон медиҳад, ки талаботи фазои дискро барои гиреҳҳои валидатор кам кунад.
Мушкил чист?
Яке аз мушкилоти бисёрсолаи Bitcoin ин миқёспазирии он буд. Идеяи "бонки шахсии шумо" аз иштирокчиёни шабака талаб мекунад, ки ҳамаи маблағҳои барои истифода дастрасро сабт кунанд. Дар Bitcoin, маблағҳои мавҷуда ҳамчун маҷмӯи натиҷаҳои истифоданашуда ифода карда мешаванд - маҷмӯи UTXO. Гарчанде ки ин як муаррифии махсусан беихтиёрона нест, он аз ҷиҳати иҷрои татбиқ нисбат ба намояндагӣ муфид аст, ки дар он ҳар як "ҳамён" ҳамчун вуруди алоҳида "тавозун" дорад ва инчунин махфиятро илова мекунад (масалан. ).
Байни таърихи транзаксияҳо (он чизе ки блокчейн номида мешавад) ва ҳолати кунунии системаро фарқ кардан муҳим аст. Таърихи транзаксияҳои Bitcoin дар айни замон тақрибан 200 ГБ фазои дискро ишғол мекунад ва афзоишро идома медиҳад. Бо вуҷуди ин, ҳолати система хеле хурдтар аст, аз рӯи тартиби 4 ГБ, ва танҳо ба инобат мегирад, ки касе дар айни замон соҳиби танга. Ҳаҷми ин маълумот низ бо мурури замон афзоиш меёбад, аммо бо суръати хеле сусттар ва баъзан ҳатто майл ба кам шудан дорад (ниг. CDPV).
Мизоҷони сабук (SPVs) кафолатҳои амниятиро барои қобилияти нигоҳ доштани ҳолати ҳадди аққал (UTXO-маҷмӯа) ғайр аз калидҳои хусусӣ тиҷорат мекунанд.
UTXO ва UTXO маҷмӯи
UTXO (Баромади транзаксияҳои истифоданашуда) натиҷаи муомилоти сарфнашуда, нуқтаи ниҳоии сафари ҳар як Сатоши дар транзаксияҳо мебошад. Натиҷаҳои истифоданашуда ба воридоти транзаксияҳои нав табдил меёбанд ва аз ин рӯ сарф мешаванд (харҷ мекунанд) ва аз маҷмӯи UTXO хориҷ карда мешаванд.
UTXO-ҳои нав ҳамеша тавассути транзаксияҳо сохта мешаванд:
- амалиёти coinbase бе воридот: эҷод UTXO-ҳои нав ҳангоми конканҳо тангаҳо
- муомилоти муқаррарӣ: ҳангоми харҷ кардани маҷмӯи муайяни UTXO-ҳои мавҷуда UTXO-ҳои нав эҷод кунед
Раванди кор бо UTXO:
Ҳамёнҳо шумораи тангаҳои барои харҷ (тавозун) мавҷудбударо дар асоси маблағи UTXO барои харҷ дар ин ҳамён ҳисоб мекунанд.
Ҳар як гиреҳи валидатор, барои пешгирӣ кардани кӯшишҳои дукарата хароҷот бояд маҷмӯи назоратро назорат кунад всех UTXO ҳангоми тафтиш ҳар як муомилот ҳар яке блок.
Гиреҳ бояд мантиқ дошта бошад:
- Иловаҳо ба маҷмӯи UTXO
- Нест кардан аз UTXO-маҷмӯи
- Санҷиши мавҷудияти як UTXO дар маҷмӯи
Роҳҳои кам кардани талабот ба иттилооти захирашуда дар бораи маҷмӯа вуҷуд доранд, дар ҳоле ки қобилияти илова кардан ва хориҷ кардани элементҳо, тафтиш ва исботи мавҷудияти элемент дар маҷмӯи истифода .
Батареяҳо барои UTXO
Идеяи истифодаи батареяҳо барои нигоҳ доштани якчанд UTXO .
Маҷмӯи UTXO дар парвоз, ҳангоми зеркашии ибтидоии блок (IBD) сохта мешавад, ки пурра ва доимӣ нигоҳ дошта мешавад, дар ҳоле ки мундариҷаи он пас аз коркарди транзаксияҳо аз ҳар як блоки нав ва дурусти шабака тағир меёбад. Ин раванд зеркашии тақрибан 200 ГБ маълумоти блок ва тафтиши садҳо миллион имзоҳои рақамиро талаб мекунад. Пас аз ба итмом расидани раванди IBD, сатри поён ин аст, ки маҷмӯи UTXO тақрибан 4 ГБ-ро ишғол мекунад.
Бо вуҷуди ин, бо аккумуляторҳо қоидаҳои консенсус барои маблағҳо ба тафтиш ва тавлиди далелҳои криптографӣ кам карда мешаванд ва бори пайгирии маблағҳои мавҷуда ба зиммаи соҳиби он маблағҳо гузошта мешавад, ки далели мавҷудият ва моликияти онҳоро пешниҳод мекунад.
Аккумуляторро метавон тасвири паймоне аз маҷмӯа номид. Андозаи намоиши захирашуда бояд доимӣ бошад , ё ба таври зерхаттӣ нисбат ба ҷиддии маҷмӯа ва андозаи худи элемент афзоиш меёбад, масалан , ки дар он n кардиналияти маҷмӯи захирашуда аст.
Дар ин ҳолат, аккумулятор бояд имкон диҳад, ки далели дохил кардани элемент ба маҷмӯи (inclusion proof) тавлид шавад ва имкон диҳад, ки ин далелро самаранок тафтиш кунад.
Батарея номида мешавад динамикӣ агар ба шумо имкон медиҳад, ки элементҳоро илова кунед ва элементҳоро аз маҷмӯа хориҷ кунед.
Намунаи чунин батарея метавонад бошад . Чунин аккумулятор дорои андозаи доимии намояндагии захирашуда, аммо мавҷудияти онро талаб мекунад сирри муштарак (Танзимоти боэътимод). Ин талабот татбиқи чунин аккумуляторро барои шабакаҳои беэътимод ба монанди Bitcoin рад мекунад, зеро ихроҷи додаҳо ҳангоми тавлиди махфӣ метавонад ба ҳамлагарон имкон диҳад, ки далели бардурӯғи мавҷудияти UTXO эҷод кунанд ва гиреҳҳоро бо маҷмӯи UTXO дар асоси чунин аккумулятор фиреб диҳанд.
Утреехо
Тарҳи Utreexo, ки аз ҷониби Thaddeus Dryja пешниҳод шудааст, имкон медиҳад, ки эҷод кунед динамикӣ аккумулятор бе он боэътимод-настрой.
Utreexo як ҷангали бинарии комил аст ва рушди идеяҳои пешниҳодшуда мебошад , илова кардани қобилияти хориҷ кардани унсурҳо аз маҷмӯи.
Сохтори мантиқии батарея
Ҳуҷайраҳои батарея дар ҷангали дарахтони идеалии бинарӣ ҷойгир шудаанд. Дарахтон аз рӯи баландӣ тартиб дода мешаванд. Ин намояндагӣ ҳамчун визуалӣ интихоб шудааст ва ба шумо имкон медиҳад, ки якҷояшавии дарахтонро ҳангоми амалиёт дар батарея тасаввур кунед.
Муаллиф қайд мекунад, ки азбаски тамоми дарахтони ҷангал идеалӣ мебошанд, баландии онҳо ҳамчун қувваи ду ифода карда мешавад, чунон ки ҳар адади натуралӣ метавонад ҳамчун ҷамъи қувваҳои ду ифода карда шавад. Мувофиқи он, ҳама гуна маҷмӯи баргҳоро метавон ба дарахтони бинарӣ гурӯҳбандӣ кард ва дар ҳама ҳолатҳо илова кардани унсури нав донишро талаб мекунад. танҳо дар бораи гиреҳҳои решаи дарахтони захирашуда.
Ҳамин тариқ, намояндагии захирашудаи аккумулятори Utreexo рӯйхати гиреҳҳои реша (Merkle root) мебошад. ва на тамоми чангали дарахтон.
Биёед рӯйхати унсурҳои решаро ҳамчун Vec<Option<Hash>>. Навъи ихтиёрӣ Option<Hash> нишон медиҳад, ки элементи реша мумкин нест, яъне дар аккумулятор ягон дарахти баландии мувофиқ вуҷуд надорад.
/// 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],
}
}
}Илова кардани элементҳо
Аввалан, биёед функсияро тавсиф кунем parent(), ки гиреҳи волидайнро барои ду унсури додашуда эътироф мекунад.
Функсияи волидайн ().
Азбаски мо дарахтони Merkle-ро истифода мебарем, волидайни ҳар ду гиреҳ як гиреҳ аст, ки хэши пайвастшавии ҳаэшҳои гиреҳҳои кӯдакро нигоҳ медорад:
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[..])
}Муаллиф қайд мекунад, ки барои ҷилавгирӣ аз ҳамлаҳое, ки Чарлз Буйлоге, Пьер-Ален Фуке, Ади Шамир ва Себастьян Зиммер тавсиф кардаанд.
, ба гайр аз ду хэш, баландии даруни дарахт низ бояд ба конкатенатсия илова карда шавад.
Ҳангоми илова кардани элементҳо ба аккумулятор, шумо бояд пайгирӣ кунед, ки кадом унсурҳои реша иваз карда мешаванд. Бо пайравӣ кардани роҳи тағир додани унсурҳои реша барои ҳар як элементе, ки шумо илова мекунед, шумо метавонед баъдтар далели мавҷудияти ин элементҳоро созед.
Ҳангоми илова кардани онҳо тағиротро пайгирӣ кунед
Барои пайгирии тағиротҳои воридшуда, биёед сохторро эълон кунем Update, ки маълумотро дар бораи тағироти гиреҳ нигоҳ медорад.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Барои илова кардани элемент ба батарея, ба шумо лозим аст:
- Як қатор сабадҳои элементҳои решаро эҷод кунед
new_rootsва унсурҳои решаи мавҷударо дар он ҷо ҷойгир кунед, барои ҳар як сатил:
рамз
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);
}- Элементҳои иловашавандаро замима кунед (массив
insertions) ба аробаи якумnew_roots[0]:
рамз
new_roots[0].extend_from_slice(insertions);- Чизҳои ба сабади якум иловашударо бо боқимонда якҷоя кунед:
- Барои ҳама аробаҳои дорои зиёда аз як ашё:
- Аз охири сабад ду элементро гиред, волидайни онҳоро ҳисоб кунед, ҳарду элементро хориҷ кунед
- Волидони ҳисобшударо ба аробаи навбатӣ илова кунед
- Барои ҳама аробаҳои дорои зиёда аз як ашё:
рамз
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 });
}
}- Элементҳои решаро аз зарфҳо ба массиви аккумулятори натиҷавӣ интиқол диҳед
рамз
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]);
}
}Эҷоди далел барои унсурҳои иловашуда
Исботи дохил кардани ҳуҷайра ба батарея (Proof) ҳамчун роҳи Меркле хидмат хоҳад кард, ки аз занҷир иборат аст ProofStep. Агар роҳ ба ҳеҷ куҷо набарад, далел нодуруст аст.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Истифодаи маълумоти қаблан гирифташуда ҳангоми илова кардани элемент (структур Update), шумо метавонед далели ба батарея илова карда шудани элементро эҷод кунед. Барои ин, мо ҷадвали тағиротҳои воридшударо мегузарем ва ҳар як қадамро ба роҳи Меркл илова мекунем, ки минбаъд ҳамчун далел хидмат хоҳад кард:
рамз
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
}
}Раванди эҷоди далел
Санҷиши далел барои элемент
Санҷиши далели дохилшавии элемент ба пайравӣ аз роҳи Merkle то он даме ки ба як унсури решаи мавҷуда оварда мерасонад, поён меёбад:
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
}
}Ба таври визуалӣ:
Раванди тафтиши далели А
Хориҷ кардани ашё
Барои хориҷ кардани ячейка аз батарея, шумо бояд далели дурусти мавҷуд будани ҳуҷайраро пешниҳод кунед. Бо истифода аз маълумотҳои далел метавон унсурҳои решаи нави аккумуляторро ҳисоб кард, ки далели додашуда барои онҳо дигар ҳақиқӣ нахоҳад буд.
Алгоритм чунин аст:
- Ба монанди илова, мо маҷмӯи сабадҳои холиро, ки ба дарахтони Merkle мувофиқанд, бо баландии баробар ба қувваи ду аз индекси сабад ташкил мекунем.
- Мо элементҳоро аз қадамҳои роҳи Merkle ба сабадҳо дохил мекунем; индекси сабад ба рақами қадами ҷорӣ баробар аст
- Мо унсури решаро, ки роҳ аз далел ба он мебарад, хориҷ мекунем
- Тавре ки ҳангоми илова кардан, мо унсурҳои решаи навро тавассути омезиши элементҳои сабадҳо ба ҷуфтҳо ва интиқоли натиҷаи иттифоқро ба сабади дигар ҳисоб мекунем.
рамз
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;
}
}Раванди хориҷ кардани элементи "А":
Интегратсия ба шабакаи мавҷуда
Бо истифода аз аккумулятори пешниҳодшуда, гиреҳҳо метавонанд аз истифодаи DB барои нигоҳ доштани ҳамаи UTXOҳо худдорӣ кунанд, дар ҳоле ки қобилияти тағир додани маҷмӯи UTXO-ро доранд. Вале проблемам кор бо далелхо ба миён меояд.
Биёед гиреҳи валидаторро даъват кунем, ки аккумулятори UTXO-ро истифода мебарад паймон (гиреҳи ҳолати паймон), ва валидатор бе аккумулятор аст пурра (гиреҳи пурра). Мавҷудияти ду синфи гиреҳҳо барои ҳамгироии онҳо ба як шабакаи ягона мушкилот эҷод мекунад, зеро гиреҳҳои паймон далели мавҷудияти UTXO-ро талаб мекунанд, ки дар транзаксияҳо сарф мешаванд, дар ҳоле ки гиреҳҳои пурра ин тавр нестанд. Агар ҳама гиреҳҳои шабакавӣ дар як вақт ва ба таври ҳамоҳангшуда ба истифодаи Utreexo нагузаранд, он гоҳ гиреҳҳои паймон дар паси худ боқӣ мемонанд ва дар шабакаи Bitcoin кор карда наметавонанд.
Барои ҳалли масъалаи ҳамгироии гиреҳҳои паймон ба шабака пешниҳод карда мешавад, ки синфи иловагии гиреҳҳо - бригадахое. Гиреҳи пул як гиреҳи мукаммалест, ки инчунин батареяи Utreexo ва далели фаъолкуниро нигоҳ медорад всех UTXO аз UTXO маҷмӯи. Пулҳо хэшҳои навро ҳисоб мекунанд ва аккумулятор ва далелҳоро ҳангоми ворид шудани блокҳои нави транзаксия нав мекунанд. Нигоҳдорӣ ва навсозии аккумулятор ва далелҳо ба чунин гиреҳҳо сарбории иловагии ҳисоббарор намегузорад. Пулҳо фазои дискро қурбон мекунанд: бояд чизҳоро ба тартиб нигоҳ доранд hashes, нисбат ба hashes барои гиреҳҳои паймоне, ки n қудрати маҷмӯи UTXO аст.
Архитектураи шабака
Пулҳо имкон медиҳанд, ки бе тағир додани нармафзори гиреҳҳои мавҷуда тадриҷан гиреҳҳои паймон ба шабака илова карда шаванд. Гиреҳҳои пурра мисли пештара кор карда, транзаксияҳо ва блокҳоро байни худ тақсим мекунанд. Гиреҳҳои пул гиреҳҳои мукаммал мебошанд, ки ба таври илова маълумоти батареяи Utreexo ва маҷмӯи далелҳои дохилкуниро нигоҳ медоранд. всех UTXO ҳоло. Гиреҳи пул худро чунин таблиғ намекунад ва вонамуд мекунад, ки гиреҳи пурра барои ҳама гиреҳҳои пурра ва гиреҳи паймон барои ҳама гиреҳҳои паймон бошад. Гарчанде ки пулҳо ҳарду шабакаро ба ҳам мепайвандад, онҳо воқеан танҳо бояд онҳоро дар як самт пайваст кунанд: аз гиреҳҳои мавҷудаи пурра то гиреҳҳои паймон. Ин имконпазир аст, зеро формати транзаксия тағир додан лозим нест ва далелҳои UTXO барои гиреҳҳои паймонро партофтан мумкин аст, аз ин рӯ ҳама гиреҳи паймон метавонад транзаксияҳоро ба ҳамаи иштирокчиёни шабака бе иштироки гиреҳҳои пулӣ пахш кунад.
хулоса
Мо ба батареяи Utreexo назар кардем ва прототипи онро дар Rust татбиқ кардем. Мо меъмории шабакаро дида баромадем, ки ба ҳамгироии гиреҳҳои ба батарея асосёфта имкон медиҳад. Бартарии сайдҳои паймон андозаи маълумоти захирашуда мебошад, ки аз логарифмикӣ аз қудрати маҷмӯи UTXOҳо вобаста аст, ки талаботро ба фазои диск ва иҷрои нигоҳдорӣ барои чунин гиреҳҳо хеле коҳиш медиҳад. Камбудӣ трафики иловагии гиреҳ барои интиқоли далелҳо мебошад, аммо усулҳои ҷамъбасти далелҳо (вақте ки як далел мавҷудияти якчанд элементро исбот мекунад) ва кэш метавонад ба нигоҳ доштани трафик дар ҳудуди қобили қабул кӯмак кунад.
мурожиат:
- -
Манбаъ: will.com