Привіт, Хабре!
У мережі 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 на базі такого акумулятора.
Утріксо
Запропонована 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