Hej Habra!
W sieci Bitcoin wszystkie węzły w drodze konsensusu uzgadniają zestaw UTXO: ile monet jest dostępnych do wydania, komu dokładnie i na jakich warunkach. Zbiór UTXO to minimalny zestaw danych wymagany dla węzła walidatora, bez którego węzeł nie będzie w stanie zweryfikować ważności transakcji przychodzących i zawierających je bloków.
W związku z tym na wszelkie możliwe sposoby podejmuje się próby zmniejszenia przechowywanej reprezentacji tego zbioru, skompresowania go bez utraty gwarancji bezpieczeństwa. Im mniejsza ilość przechowywanych danych, tym mniejsze zapotrzebowanie na miejsce na dysku węzła walidatora, co sprawia, że uruchomienie węzła walidatora jest tanie, pozwala na rozbudowę sieci i tym samym zwiększenie stabilności sieci.
W tym poście zamieścimy prototyp Rusta najnowszej propozycji współautora , - , co pozwala zmniejszyć wymagania dotyczące miejsca na dysku dla węzłów walidatora.
Jaki jest problem?
Jednym z odwiecznych problemów Bitcoina jest jego skalowalność. Idea „własnego banku” wymaga od uczestników sieci prowadzenia ewidencji wszystkich środków dostępnych do wykorzystania. W Bitcoinie dostępne środki wyrażane są jako zbiór niewydanych wyników – zbiór UTXO. Chociaż nie jest to szczególnie intuicyjna reprezentacja, jest ona korzystna pod względem wydajności w porównaniu z reprezentacją, w której każdy „portfel” ma „saldo” jako osobny wpis, a także zapewnia prywatność (np. ).
Ważne jest, aby rozróżnić historię transakcji (tzw. blockchain) od aktualnego stanu systemu. Historia transakcji Bitcoin zajmuje obecnie około 200 GB miejsca na dysku i stale rośnie. Stan systemu jest jednak znacznie mniejszy, rzędu 4 GB i uwzględnia jedynie fakt, że ktoś aktualnie posiada monety. Ilość tych danych również rośnie z biegiem czasu, ale w znacznie wolniejszym tempie, a czasami nawet ma tendencję do zmniejszania się (patrz CDPV).
Klienci Light (SPV) handlują gwarancjami bezpieczeństwa w zakresie możliwości przechowywania stanu minimalnego (zestawu UTXO) innego niż klucze prywatne.
Zestaw UTXO i UTXO
UTXO (niewydane dane wyjściowe transakcji) to niewydane dane wyjściowe transakcji, punkt końcowy podróży każdego Satoshi przekazanego w transakcjach. Niewydane dane wyjściowe stają się danymi wejściowymi nowych transakcji, a zatem są wydawane (wydawane) i usuwane ze zbioru UTXO.
Nowe UTXO są zawsze tworzone przez transakcje:
- transakcje w bazie monet bez danych wejściowych: twórz nowe UTXO, gdy górnicy emitują monety
- regularne transakcje: twórz nowe UTXO, wydając określony zestaw istniejących UTXO
Proces pracy z UTXO:
Portfele zliczają liczbę monet dostępnych do wydania (saldo) w oparciu o ilość UTXO dostępną dla tego portfela do wydatków.
Każdy węzeł walidatora, aby zapobiec próbom podwójnego wydania, musi monitorować zestaw wszystko UTXO podczas sprawdzania każdy transakcje każdy blok.
Węzeł musi mieć logikę:
- Dodatki do zestawu UTXO
- Usunięcia ze zbioru UTXO
- Sprawdzenie obecności pojedynczego UTXO w zestawie
Istnieją sposoby na zmniejszenie wymagań dotyczących przechowywanych informacji o zbiorze, przy jednoczesnym zachowaniu możliwości dodawania i usuwania elementów, sprawdzania i udowadniania istnienia elementu w zbiorze za pomocą .
Baterie do UTXO
Pomysł wykorzystania baterii do przechowywania wielu UTXO .
Zestaw UTXO jest budowany na bieżąco, podczas początkowego pobierania bloku (IBD), przechowywany w całości i trwale, a jego zawartość zmienia się po przetworzeniu transakcji z każdego nowego i prawidłowego bloku sieci. Proces ten wymaga pobrania około 200 GB danych blokowych i weryfikacji setek milionów podpisów cyfrowych. Po zakończeniu procesu IBD najważniejsze jest to, że zestaw UTXO zajmie około 4 GB.
Jednak w przypadku akumulatorów zasady konsensusu dotyczącego środków sprowadzają się do weryfikacji i generowania dowodów kryptograficznych, a ciężar śledzenia dostępnych środków zostaje przerzucony na właściciela tych środków, który przedstawia dowód ich istnienia i własności.
Akumulator można nazwać zwartą reprezentacją zbioru. Rozmiar przechowywanej reprezentacji musi być stały lub zwiększ subliniowo w odniesieniu do liczności zbioru i rozmiaru samego elementu, na przykład , gdzie n jest licznością przechowywanego zbioru.
W takim przypadku akumulator powinien umożliwiać wygenerowanie dowodu włączenia elementu do zbioru (dowód włączenia) i umożliwiać skuteczną weryfikację tego dowodu.
Bateria nazywa się dynamiczny if pozwala na dodawanie i usuwanie elementów ze zbioru.
Przykładem takiej baterii może być . Taki akumulator ma stały rozmiar przechowywanej reprezentacji, ale wymaga obecności wspólny sekret (zaufana konfiguracja). Wymóg ten neguje możliwość zastosowania takiego akumulatora w sieciach bez zaufania, takich jak Bitcoin, ponieważ wyciek danych podczas generowania sekretu może pozwolić atakującym na stworzenie fałszywego dowodu na istnienie UTXO, oszukując węzły za pomocą zestawu UTXO opartego na takim akumulatorze.
Utreexo
Projekt Utreexo zaproponowany przez Thaddeusa Dryję daje możliwość tworzenia dynamiczny akumulator без zaufana konfiguracja.
Utreexo to las idealnego układu binarnego i jest rozwinięciem idei przedstawionych w , dodając możliwość usuwania elementów ze zbioru.
Struktura logiczna baterii
Ogniwa akumulatorów ułożone są w lesie idealnych drzew binarnych. Drzewa są uporządkowane według wysokości. To przedstawienie zostało wybrane jako najbardziej wizualne i pozwala zwizualizować łączenie się drzew podczas operacji na akumulatorze.
Autor zauważa, że skoro wszystkie drzewa w lesie są idealne, ich wysokość wyraża się jako potęgę dwójki, tak jak każdą liczbę naturalną można przedstawić jako sumę potęg dwójki. W związku z tym dowolny zestaw liści można pogrupować w drzewa binarne i we wszystkich przypadkach dodanie nowego elementu wymaga wiedzy tylko o węzłach korzeniowych przechowywanych drzew.
Zatem przechowywana reprezentacja akumulatora Utreexo jest listą węzłów głównych (korzeń Merkle), a nie cały las drzew.
Przedstawmy listę elementów głównych jako Vec<Option<Hash>>. Typ opcjonalny Option<Hash> wskazuje, że może brakować elementu korzeniowego, co oznacza, że w akumulatorze nie ma drzewa o odpowiedniej wysokości.
/// 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],
}
}
}Dodawanie elementów
Najpierw opiszemy tę funkcję parent(), który rozpoznaje węzeł nadrzędny dla dwóch danych elementów.
funkcja rodzic().
Ponieważ używamy drzew Merkle, rodzicem każdego z dwóch węzłów jest jeden węzeł, który przechowuje skrót konkatenacji skrótów węzłów podrzędnych:
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[..])
}Autor zauważa, że aby zapobiec atakom opisanym przez Charlesa Bouillagueta, Pierre-Alaina Fouque, Adi Shamira i Sebastiena Zimmera w
, oprócz dwóch skrótów, do konkatenacji należy również dodać wysokość wewnątrz drzewa.
Kiedy dodajesz elementy do akumulatora, musisz śledzić, które elementy główne zostały zmienione. Podążając ścieżką zmiany elementów głównych dla każdego dodawanego elementu, możesz później skonstruować dowód na obecność tych elementów.
Śledź zmiany w miarę ich dodawania
Aby śledzić wprowadzone zmiany, zadeklarujmy strukturę Update, który będzie przechowywać dane o zmianach węzłów.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Aby dodać element do baterii, potrzebujesz:
- Utwórz tablicę koszyków elementów głównych
new_rootsi umieść tam istniejące elementy główne, po jednym dla każdego segmentu:
kod
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);
}- Dołącz elementy, które mają zostać dodane (array
insertions) do pierwszego wózkanew_roots[0]:
kod
new_roots[0].extend_from_slice(insertions);- Połącz elementy dodane do pierwszego koszyka z resztą:
- Dla wszystkich koszyków zawierających więcej niż jeden przedmiot:
- Weź dwa elementy z końca koszyka, oblicz ich rodzica, usuń oba elementy
- Dodaj obliczonego rodzica do następnego koszyka
- Dla wszystkich koszyków zawierających więcej niż jeden przedmiot:
kod
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 });
}
}- Przenieś elementy główne z pojemników do wynikowej tablicy akumulatorów
kod
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]);
}
}Tworzenie proofa dla dodanych elementów
Dowód włączenia ogniwa do akumulatora (Proof) będzie służyć jako Ścieżka Merkle'a, składająca się z łańcucha ProofStep. Jeśli ścieżka prowadzi donikąd, dowód jest błędny.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Korzystając z informacji uzyskanych wcześniej podczas dodawania elementu (structure Update), możesz stworzyć dowód, że do baterii został dodany element. Aby to zrobić, przeglądamy tabelę wprowadzonych zmian i dodajemy każdy krok do ścieżki Merkle, co później posłuży jako dowód:
kod
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
}
}Proces tworzenia dowodu
Sprawdzanie dowodu elementu
Sprawdzenie dowodu włączenia elementu sprowadza się do podążania ścieżką Merkle, aż doprowadzi ona do istniejącego elementu głównego:
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
}
}Wyraźnie:
Proces sprawdzania dowodu dla A
Usuwanie przedmiotów
Aby wyjąć ogniwo z akumulatora, należy przedstawić ważny dowód na to, że ogniwo tam się znajduje. Na podstawie danych z dowodu można obliczyć nowe elementy pierwiastkowe akumulatora, dla których dany dowód nie będzie już prawdziwy.
Algorytm wygląda następująco:
- Podobnie jak w przypadku dodatku, organizujemy zestaw pustych koszy odpowiadający drzewkom Merkle o wysokości równej potędze dwójki z indeksu koszyka
- Do koszyków wkładamy elementy ze stopni ścieżki Merkle; indeks koszyka jest równy numerowi bieżącego kroku
- Usuwamy element główny, do którego prowadzi ścieżka z dowodu
- Podobnie jak przy dodawaniu, nowe elementy pierwiastkowe obliczamy łącząc elementy z koszyków w pary i przenosząc wynik sumowania do następnego koszyka
kod
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;
}
}Proces usuwania elementu „A”:
Integracja z istniejącą siecią
Korzystając z proponowanego akumulatora, węzły mogą uniknąć używania bazy danych do przechowywania wszystkich UTXO, jednocześnie mając możliwość zmiany zestawu UTXO. Pojawia się jednak problem pracy z dowodami.
Nazwijmy węzeł walidatora korzystający z akumulatora UTXO kompaktowy (węzeł stanu zwartego), a walidator bez akumulatora to zakończone (pełny węzeł). Istnienie dwóch klas węzłów stwarza problem w integracji ich w jedną sieć, ponieważ węzły zwarte wymagają dowodu na istnienie UTXO, które są wydawane w transakcjach, podczas gdy węzły pełne nie. Jeśli wszystkie węzły sieci nie przejdą jednocześnie i w skoordynowany sposób na korzystanie z Utreexo, wówczas kompaktowe węzły zostaną pozostawione w tyle i nie będą mogły działać w sieci Bitcoin.
Aby rozwiązać problem integracji węzłów zwartych z siecią, proponuje się wprowadzenie dodatkowej klasy węzłów - mosty. Węzeł mostkowy to kompletny węzeł, który przechowuje również baterię Utreexo i dowód włączenia zasilania wszystko UTXO z zestawu UTXO. Mosty obliczają nowe skróty i aktualizują akumulator oraz dowody w miarę nadejścia nowych bloków transakcji. Utrzymanie i aktualizacja akumulatora oraz dowodów nie powoduje dodatkowego obciążenia obliczeniowego tych węzłów. Mosty poświęcają miejsce na dysku: trzeba zachować porządek skróty w porównaniu do skróty dla węzłów zwartych, gdzie n jest potęgą zbioru UTXO.
Architektura sieci
Mosty umożliwiają stopniowe dodawanie do sieci węzłów kompaktowych bez zmiany oprogramowania istniejących węzłów. Pełne węzły działają jak poprzednio, rozdzielając między sobą transakcje i bloki. Węzły mostkowe to pełne węzły, które dodatkowo przechowują dane o baterii Utreexo i zestaw dowodów włączenia wszystko Na razie UTXO. Węzeł mostkowy nie reklamuje się jako taki, udając, że jest pełnym węzłem dla wszystkich pełnych węzłów i zwartym węzłem dla wszystkich zwartych. Chociaż mosty łączą obie sieci, w rzeczywistości wystarczy je połączyć tylko w jednym kierunku: od istniejących pełnych węzłów do węzłów kompaktowych. Jest to możliwe, ponieważ nie trzeba zmieniać formatu transakcji, a dowody UTXO dla węzłów kompaktowych można odrzucić, dzięki czemu każdy węzeł kompaktowy może w podobny sposób rozgłaszać transakcje do wszystkich uczestników sieci bez udziału węzłów mostowych.
wniosek
Przyjrzeliśmy się akumulatorowi Utreexo i zaimplementowaliśmy jego prototyp w języku Rust. Przyjrzeliśmy się architekturze sieci, która umożliwi integrację węzłów akumulatorowych. Zaletą kompaktowych połowów jest rozmiar przechowywanych danych, który zależy logarytmicznie od mocy zestawu UTXO, co znacznie zmniejsza wymagania dotyczące miejsca na dysku i wydajności przechowywania dla takich węzłów. Wadą jest dodatkowy ruch węzłowy do przesyłania dowodów, ale techniki agregacji dowodów (kiedy jeden dowód potwierdza istnienie kilku elementów) i buforowanie mogą pomóc w utrzymaniu ruchu w akceptowalnych granicach.
referencje:
- -
Źródło: www.habr.com