Прывітанне, Хабр!
У сетцы Bitcoin усе вузлы падчас кансенсусу згаджаюцца над мноствам UTXO: колькі манет даступна для марнавання, каму менавіта і пры якіх умовах. Мноства UTXO - гэта мінімальна неабходны для вузла-валідатара набор дадзеных, без якога вузел не зможа пераканацца ў валіднасці прыходзяць транзакцый і блокаў, якія іх змяшчаюць.
У сувязі з гэтым робяцца спробы ўсяляк паменшыць захаванае ўяўленне гэтага мноства, сціснуць яго без страты гарантый бяспекі. Чым менш аб'ём захоўваемых дадзеных, тым ніжэй патрабаванні да дыскавай прасторы вузла-валідатара, што робіць запуск вузла-валідатара танным, дазваляе нарошчваць сетку і павялічваць тым самым устойлівасць сеткі.
У гэтай нататцы мы запілуем Rust-прататып нядаўняй прапановы ад суаўтара , - , які дазваляе паменшыць патрабаванні да дыскавай прасторы для вузлоў-валідатараў.
У чым праблема?
Адной з вечных праблем Біткоіна была яго маштабаванасць. Ідэя "сам сабе банк" патрабуе ад удзельнікаў сеткі весці ўлік усіх даступных для выкарыстання сродкаў. У Bitcoin даступныя сродкі выяўляюцца ў выглядзе мноства нерастрачаных выхадаў – UTXO-set. Хоць гэтае і не асоба інтуітыўнае ўяўленне, яно з'яўляецца выгодным з пункта гледжання прадукцыйнасці рэалізацыі, у параўнанні з уяўленнем, у якім у кожнага «кашалька» ёсць «баланс» у выглядзе асобнага запісу, а таксама дадае прыватнасці (напрыклад, забяспечвае працу ).
Важна адрозніваць гісторыю транзакцый (тое, што называецца блокчейном) і бягучы стан сістэмы. Гісторыя транзакцый Bitcoin у цяперашні час займае каля 200 Гб дыскавай прасторы, і працягвае расці. Аднак стан сістэмы значна менш, каля 4 Гб, і ўлічвае толькі факт валодання манет кім-небудзь у цяперашні час. Аб'ём гэтых дадзеных таксама з-часам павялічваецца, але значна з меншай хуткасцю і часам нават мае тэндэнцыю да памяншэння (гл. КДПВ).
Лёгкія кліенты (SPV) абменьваюць гарантыі бяспекі на магчымасць не захоўваць ніякага мінімальнага стану (UTXO-set), акрамя прыватных ключоў.
UTXO і UTXO-set
UTXO (Unspent Transaction Output) — нерастрачаны выхад транзакцыі, канчатковы пункт падарожжа кожнага сатошы, які перадаецца ў транзакцыях. Нерастрачаныя выхады становяцца ўваходамі новых транзакцый і пры гэтым трацяцца (spend) і выдаляюцца з UTXO-set.
Новыя UTXO заўсёды ствараюцца транзакцыямі:
- coinbase-транзакцыі без уваходаў: ствараюць новыя UTXO падчас эмісіі манет майнерамі
- звычайныя транзакцыі: ствараюць новыя UTXO, марнуючы пры гэтым нейкі набор існуючых UTXO
Працэс працы з UTXO:
Кашалькі лічаць колькасць даступных для марнавання манет (баланс) зыходзячы з сумы UTXO, даступных гэтаму кашальку для марнавання.
Кожны вузел-валідатар, для прадухілення спроб падвойнага марнавання (double spend), павінен адсочваць набор ўсіх UTXO пры праверцы кожнай транзакцыі кожнага блока.
У вузла павінна прысутнічаць логіка:
- Даданні ў UTXO-set
- Выдаленні з UTXO-set
- Праверкі наяўнасці асобна ўзятага UTXO у мностве
Існуюць спосабы паменшыць патрабаванні да захоўваемай інфармацыі аб мностве, захаваўшы пры гэтым магчымасць дадаваць і выдаляць элементы, правяраць і даказваць існаванне элемента ў мностве з дапамогай. .
Акумулятары для UTXO
Ідэя прымянення акумулятараў для захоўвання мноства UTXO .
UTXO-set будуецца на ляту, падчас пачатковай загрузкі ланцужка блокаў (IBD, initial block download), захоўваецца ў поўным аб'ёме і ўвесь час, пры гэтым яго змесціва змяняецца пасля апрацоўкі транзакцый з кожнага новага і карэктнага блока сеткі. Дадзены працэс патрабуе загрузкі прыкладна 200 Гб дадзеных блокаў і праверкі сотняў мільёнаў лічбавых подпісаў. Пасля таго, як працэс IBD скончаны, у сухой рэштцы UTXO-set будзе займаць каля 4 Гб.
Аднак, пры выкарыстанні акумулятараў, правілы кансенсусу адносна сродкаў зводзяцца да праверкі і генерацыі крыптаграфічных доказаў, а цяжар адсочвання даступных сродкаў перакладаецца на плечы ўладальніка гэтых сродкаў, які дае доказы іх наяўнасці і валодання імі.
Акумулятарам можна назваць кампактнае ўяўленне мноства. Памер захоўваемага прадстаўлення, пры гэтым, павінен быць альбо пастаянным. , альбо павялічвацца сублінейна адносна магутнасці мноства і памеру самога элемента, напрыклад , Дзе n - магутнасць захоўваемага мноства.
Пры гэтым акумулятар павінен дазваляць генераваць доказ уключэння элемента ў мноства (inclusion proof) і даваць магчымасць эфектыўна праверыць гэты доказ.
Акумулятар называецца дынамічным калі дазваляе дадаваць элементы і выдаляць элементы са мноства.
Прыкладам такога акумулятара можа паслужыць . Такі акумулятар мае пастаянны памер захоўваемага прадстаўлення, але патрабуе наяўнасці агульнага сакрэту (trusted setup). Гэтае патрабаванне зводзіць на нішто дастасавальнасць такога акумулятара для trustless-сетак тыпу Bitcoin, паколькі ўцечка дадзеных пры генерацыі сакрэту можа дазволіць зламыснікам ствараць фальшывыя доказы існавання UTXO, ашукваючы вузлы з UTXO-set на базе такога акумулятара.
Utreexo
Прапанаваная Thaddeus Dryja канструкцыя Utreexo дазваляе стварыць дынамічны акумулятар без trusted-setup.
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(), якая даведаецца вузел-бацька для двух зададзеных элементаў.
Функцыя parent()
Паколькі мы выкарыстоўваем дрэвы Меркла, то бацькам кожнага з двух вузлоў з'яўляецца адзін вузел, які захоўвае хэш канкатэнацыі хэшаў вузлоў-нашчадкаў:
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[..])
}Аўтар заўважае, што для прадухілення нападаў, апісаных Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, і Sebastien Zimmer у
, акрамя двух хэшаў варта дадаваць да канкатэнацыі яшчэ і вышыню ўнутры дрэва.
У ходзе дадання элементаў у акумулятар, неабходна адсочваць, якія каранёвыя элементы аказваюцца зменены. Прытрымліваючыся па шляху змены каранёвых элементаў для кожнага дадаванага элемента, пазней можна сканструяваць доказ наяўнасці гэтых элементаў.
Адсочванне змен у ходзе дадання
Для адсочвання зробленых змен, аб'явім структуру 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);- Правесці «аб'яднанне» (coalescing) дададзеных у першы кошык элементаў з астатнімі:
- Для ўсіх кошыкаў, у якіх больш за адзін элемент:
- Бярэм два элементы з канца кошыка, вылічаем іх аднаго з бацькоў, выдаляем абодва элементы
- Дадаем вылічанага аднаго з бацькоў у наступны кошык
- Для ўсіх кошыкаў, у якіх больш за адзін элемент:
Код
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) будзе служыць шлях Меркла (Merkle Path), які складаецца з ланцужка 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
}
}Працэс стварэння доказу
Праверка доказы для элемента
Праверка доказу ўключэння элемента (inclusion proof) зводзіцца да следавання па шляху Меркла, пакуль ён не прывядзе да існага каранёвага элемента:
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
}
}Наглядна:
Працэс праверкі доказы для 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;
}
}Працэс выдалення элемента "А":
Інтэграцыя ў існуючую сетку
Выкарыстоўваючы прапанаваны акумулятар, вузлы могуць адмовіцца ад выкарыстання БД для захоўвання ўсіх UTXO, захоўваючы пры гэтым магчымасць змяняць UTXO-set. Аднак узнікае праблема працы з доказамі.
Назавем вузел-валідатар, які выкарыстоўвае акумулятар UTXO кампактным (compact-state node), а валідатар без акумулятара поўным (full node). Існаванне двух класаў вузлоў стварае праблему інтэграцыі іх у адзіную сетку, паколькі кампактныя вузлы патрабуюць доказы існавання UTXO, якія марнуюцца ў транзакцыях, а поўныя вузлы - не. Калі ўсе вузлы сеткі адначасова і скаардынавана не пяройдуць на выкарыстанне Utreexo, тады кампактныя вузлы застануцца ззаду і не змогуць працаваць у сетцы Bitcoin.
Для вырашэння праблемы інтэграцыі кампактных вузлоў у сетку, прапануецца ўвесці дадатковы клас вузлоў. масты. Вузел-мост - гэта поўны вузел, які да ўсяго іншаму захоўвае акумулятар Utreexo і доказы ўключэння для ўсіх UTXO з UTXO-set. Масты вылічаюць новыя хешы і абнаўляюць акумулятар і доказы па меры паступлення новых блокаў з транзакцыямі. Падтрымка і абнаўленне акумулятара і доказаў не накладвае дадатковай вылічальнай нагрузкі на такія вузлы. Масты ахвяруюць дыскавай прасторай: патрабуецца захоўваць парадку хешаў, у параўнанні з хэшаў для кампактных вузлоў, дзе n - магутнасць мноства UTXO.
Архітэктура сеткі
Масты даюць магчымасць паступова дадаваць кампактныя вузлы ў сетку без змены ПА існых вузлоў. Поўныя вузлы працуюць па-ранейшаму, распаўсюджваючы транзакцыі і блокі паміж сабой. Вузлы-масты ўяўляюць сабой поўныя вузлы, якія дадаткова захоўваюць дадзеныя акумулятара Utreexo і набор доказаў уключэння для ўсіх UTXO на дадзены момант. Маставой вузел ніяк не афішуе сябе як такі, мяркуючы поўным вузлом для ўсіх поўных вузлоў і кампактным вузлом - для ўсіх кампактных. Хоць масты і злучаюць абедзве сеткі разам, у рэчаіснасці патрабуецца злучаць іх толькі ў адным кірунку: ад існых поўных вузлоў да кампактных вузлоў. Гэта магчыма з-за таго, што фармат транзакцый не патрабуецца змяняць, а доказы для UTXO для кампактных вузлоў можа быць адкінута, таму любы кампактны вузел сапраўды гэтак жа можа рассылаць транзакцыі ўсім удзельнікам сеткі без удзелу вузлоў-мастоў.
Заключэнне
Мы разгледзелі акумулятар Utreexo і рэалізавалі яго прататып на мове Rust. Разгледзелі архітэктуру сеткі, якая дазволіць інтэграваць вузлы на базе акумулятара. Перавагай кампактных улоў выступае памер захоўваемых дадзеных, які залежыць лагарыфмічнаму ад магутнасці мноства UTXO, што моцна змяншае патрабаванні да дыскавай прасторы і прадукцыйнасці сховішчы для такіх вузлоў. Недахопам выступае дадатковы трафік вузлоў на перадачу доказаў, але тэхнікі агрэгацыі доказаў (калі адзін доказ даказвае існаванне некалькіх элементаў) і кэшавання могуць дапамагчы ўтрымаць трафік у прымальных межах.
Спасылкі:
- -
Крыніца: habr.com