Szia Habr!
A Bitcoin-hálózatban minden csomópont konszenzussal megegyezik az UTXO-k készletében: hány érme költhető el, pontosan kinek és milyen feltételekkel. Az UTXO halmaz az érvényesítő csomóponthoz szükséges minimális adatkészlet, amely nélkül a csomópont nem tudja ellenőrizni a bejövő tranzakciók és az azokat tartalmazó blokkok érvényességét.
Ezzel kapcsolatban minden lehetséges módon megpróbálják csökkenteni a készlet tárolt reprezentációját, tömöríteni a biztonsági garanciák elvesztése nélkül. Minél kisebb a tárolt adatok mennyisége, annál kisebb lemezterületigénye van az érvényesítő csomópontnak, ami olcsóbbá teszi a validátor csomópont elindítását, lehetővé teszi a hálózat bővítését és ezáltal a hálózat stabilitásának növelését.
Ebben a bejegyzésben egy társszerző közelmúltbeli javaslatának Rust prototípusát közöljük , - , amely lehetővé teszi az érvényesítő csomópontok lemezterületigényének csökkentését.
Mi a probléma?
A Bitcoin egyik örök problémája a méretezhetősége volt. A „saját bank” elképzelése megköveteli a hálózat résztvevőitől, hogy minden felhasználható forrásról nyilvántartást vezetjenek. A Bitcoinban a rendelkezésre álló forrásokat el nem költött kimenetek halmazaként fejezik ki – egy UTXO-készletként. Noha ez nem egy különösebben intuitív ábrázolás, előnyösebb a megvalósítási teljesítmény szempontjából, mint egy olyan ábrázolással szemben, amelyben minden „pénztárcának” külön bejegyzésként „egyenlege” van, és egyúttal a magánélet védelmét is növeli (pl. ).
Fontos különbséget tenni a tranzakciók története (az úgynevezett blokklánc) és a rendszer jelenlegi állapota között. A Bitcoin tranzakciós története jelenleg körülbelül 200 GB lemezterületet foglal el, és folyamatosan növekszik. A rendszer állapota azonban jóval kisebb, 4 GB nagyságrendű, és csak azt a tényt veszi figyelembe, hogy valaki éppen érméket birtokol. Ezeknek az adatoknak a mennyisége is növekszik az idő múlásával, de sokkal lassabb ütemben, sőt néha csökkenni is hajlamos (lásd CDPV).
A könnyű kliensek (SPV-k) biztonsági garanciákat keresnek arra vonatkozóan, hogy a privát kulcsokon kívül semmilyen minimális állapotot (UTXO-készletet) nem tárolhatnak.
UTXO és UTXO-készlet
Az UTXO (el nem költött tranzakció kimenet) az el nem költött tranzakció kimenete, a tranzakciókban átvitt Satoshi utazásának végpontja. Az el nem költött kimenetek új tranzakciók bemeneteivé válnak, így elköltik (költés), és eltávolítják az UTXO-készletből.
Az új UTXO-kat mindig a tranzakciók hozzák létre:
- coinbase tranzakciók bemenetek nélkül: új UTXO-k létrehozása, amikor a bányászok érméket bocsátanak ki
- rendszeres tranzakciók: új UTXO-k létrehozása, miközben a meglévő UTXO-k egy részét elkölti
Az UTXO-val végzett munka folyamata:
A pénztárcák a költésre rendelkezésre álló érmék számát (egyenlegét) a pénztárcánál költésre rendelkezésre álló UTXO mennyisége alapján számolják.
A kétszeres költési kísérletek elkerülése érdekében minden érvényesítő csomópontnak figyelnie kell a készletet minden UTXO ellenőrzéskor minden tranzakciók mindegyikből Blokk.
A csomópontnak logikájának kell lennie:
- Kiegészítések az UTXO-készlethez
- Törlés az UTXO-készletből
- Egyetlen UTXO jelenlétének ellenőrzése egy készletben
Vannak módok a halmazokról tárolt információkkal szemben támasztott követelmények csökkentésére, miközben megőrizzük az elemek hozzáadásának és eltávolításának lehetőségét, valamint a halmazban lévő elem létezésének ellenőrzését és bizonyítását. .
Elemek UTXO-hoz
Az ötlet, hogy akkumulátorokat használjunk több UTXO tárolására .
Az UTXO-készlet menet közben, a kezdeti blokkletöltés (IBD) során épül fel, teljes egészében és tartósan tárolódik, miközben a hálózat minden új és helyes blokkjából származó tranzakciók feldolgozása után a tartalma megváltozik. Ehhez a folyamathoz körülbelül 200 GB blokkadat letöltése és több százmillió digitális aláírás ellenőrzése szükséges. Az IBD folyamat befejezése után a lényeg az, hogy az UTXO-készlet körülbelül 4 GB-ot fog elfoglalni.
A felhalmozóknál azonban a pénzeszközökre vonatkozó konszenzus szabályai a kriptográfiai bizonyítékok ellenőrzésére és generálására redukálódnak, és a rendelkezésre álló pénzeszközök nyomon követésének terhe a pénztárak tulajdonosára hárul, aki igazolja azok létezését és tulajdonjogát.
Az akkumulátort egy halmaz kompakt ábrázolásának nevezhetjük. A tárolt ábrázolás méretének vagy állandónak kell lennie , vagy szublineárisan növekszik a halmaz számosságához és magának az elemnek a méretéhez képest, pl. , ahol n a tárolt halmaz számossága.
Ebben az esetben az akkumulátornak lehetővé kell tennie egy elem halmazba való felvételének igazolásának előállítását (befoglalási bizonyíték), és lehetővé kell tennie ennek a bizonyítéknak a hatékony ellenőrzését.
Az akkumulátort ún dinamikus ha lehetővé teszi elemek hozzáadását és elemek eltávolítását egy halmazból.
Példa egy ilyen akkumulátorra . Egy ilyen akkumulátor állandó méretű tárolt ábrázolással rendelkezik, de megköveteli a jelenlétet közös titok (megbízható beállítás). Ez a követelmény tagadja az ilyen akkumulátorok alkalmazhatóságát olyan megbízható hálózatok esetében, mint a Bitcoin, mivel a titkos generálás során fellépő adatszivárgás lehetővé teszi a támadók számára, hogy hamis bizonyítékokat hozzanak létre egy UTXO létezésére, megtévesztve a csomópontokat egy ilyen akkumulátoron alapuló UTXO-készlettel.
Utreexo
A Thaddeus Dryja által javasolt Utreexo dizájn lehetővé teszi az alkotást dinamikus аккумулятор nélkül megbízható beállítás.
Az Utreexo a tökéletes bináris erdeje és a bemutatott ötletek továbbfejlesztése , hozzáadva az elemek készletből való eltávolításának lehetőségét.
Akkumulátor logikai felépítése
Az akkumulátorcellák ideális bináris fák erdejében helyezkednek el. A fákat magasság szerint rendezzük. Ezt az ábrázolást választották a legvizuálisabbnak, és lehetővé teszi a fák egyesülésének megjelenítését az akkumulátorral végzett műveletek során.
A szerző megjegyzi, hogy mivel az erdőben az összes fa ideális, magasságukat kettő hatványával fejezzük ki, ahogy bármely természetes szám ábrázolható kettő hatványainak összegeként. Ennek megfelelően tetszőleges levélhalmaz csoportosítható bináris fákba, és minden esetben egy új elem hozzáadásához tudás kell csak a tárolt fák gyökércsomópontjairól.
Így az Utreexo akkumulátor tárolt reprezentációja a gyökércsomópontok listája (Merkle gyökér), és nem az egész fák erdeje.
A gyökérelemek listáját ábrázoljuk a következővel Vec<Option<Hash>>. Választható típus Option<Hash> azt jelzi, hogy a gyökérelem hiányozhat, ami azt jelenti, hogy nincs megfelelő magasságú fa az akkumulátorban.
/// 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],
}
}
}Elemek hozzáadása
Először is írjuk le a függvényt parent(), amely két adott elemnél felismeri a szülőcsomópontot.
szülő() függvény
Mivel Merkle-fákat használunk, a két csomópont szülője egy csomópont, amely az utódcsomópontok hasheinek összefűzésének kivonatát tárolja:
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[..])
}A szerző megjegyzi, hogy a Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir és Sebastien Zimmer által leírt támadások megakadályozása érdekében
, a két hash mellett a fán belüli magasságot is hozzá kell adni az összefűzéshez.
Amikor elemeket ad hozzá az akkumulátorhoz, nyomon kell követnie, hogy mely gyökérelemek módosulnak. Ha követi az egyes hozzáadott elemek gyökérelemeinek módosítási útvonalát, később bizonyítékot készíthet ezen elemek jelenlétéről.
Kövesse nyomon a változásokat, amikor hozzáadja őket
A végrehajtott változtatások követéséhez deklaráljuk a szerkezetet Update, amely adatokat tárol a csomópontok változásairól.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Egy elem hozzáadásához az akkumulátorhoz a következőkre van szüksége:
- Hozzon létre egy tömböt gyökérelemekből álló kosarakból
new_rootsés helyezze oda a meglévő gyökérelemeket, minden vödörhöz egyet:
Kód
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);
}- Adja hozzá a hozzáadandó elemeket (tömb
insertions) az első kocsihoznew_roots[0]:
Kód
new_roots[0].extend_from_slice(insertions);- Kösd össze az első kosárba helyezett elemeket a többivel:
- Minden több terméket tartalmazó kosár esetén:
- Vegyen ki két elemet a kosár végéről, számolja ki a szülőjét, távolítsa el mindkét elemet
- Adja hozzá a kiszámított szülőt a következő kosárhoz
- Minden több terméket tartalmazó kosár esetén:
Kód
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 });
}
}- A gyökérelemek áthelyezése a tálcákból a kapott gyűjtőtömbbe
Kód
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]);
}
}Bizonyíték készítése hozzáadott elemekhez
A cella akkumulátorba helyezésének igazolása (Proof) a Merkle-ösvényként fog szolgálni, amely egy láncból áll ProofStep. Ha az út nem vezet sehova, akkor a bizonyítás hibás.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}A korábban szerzett információk felhasználása elem (struktúra) hozzáadásakor Update), bizonyítékot készíthet arról, hogy egy elemet hozzáadtak az akkumulátorhoz. Ehhez átnézzük a végrehajtott változtatások táblázatát, és minden egyes lépést hozzáadunk Merkle útjának, ami a későbbiekben bizonyítékul szolgál majd:
Kód
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
}
}Bizonyítás létrehozásának folyamata
Egy elem bizonyításának ellenőrzése
Egy elem befogadási igazolásának ellenőrzése a Merkle-útvonal követését jelenti, amíg az egy meglévő gyökérelemhez nem vezet:
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
}
}Tisztán:
Az A bizonyítvány ellenőrzésének folyamata
Elemek eltávolítása
A cella akkumulátorból való eltávolításához érvényes bizonyítékot kell szolgáltatnia arra vonatkozóan, hogy az elem ott van. A bizonyítás adataiból ki lehet számítani az akkumulátor olyan új gyökérelemeit, amelyekre az adott bizonyítás már nem lesz igaz.
Az algoritmus a következő:
- A kiegészítéshez hasonlóan a Merkle-fáknak megfelelő üres kosarakat szervezünk, amelyek magassága egyenlő a kosárindexből kettő hatványával.
- A Merkle-út lépcsőiből elemeket helyezünk a kosarakba; a kosár index megegyezik az aktuális lépés számával
- Eltávolítjuk a gyökérelemet, amelyhez a bizonyítás útja vezet
- Az összeadáshoz hasonlóan az új gyökérelemeket úgy számítjuk ki, hogy a kosarak elemeit párban kombináljuk, és az összevonás eredményét áthelyezzük a következő kosárba.
Kód
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;
}
}Az "A" elem eltávolításának folyamata:
Integráció meglévő hálózatba
A javasolt tároló használatával a csomópontok elkerülhetik, hogy DB-t használjanak az összes UTXO tárolására, miközben továbbra is módosíthatják az UTXO-készletet. Felmerül azonban a bizonyítékokkal való munka problémája.
Hívjuk meg az UTXO-akkumulátort használó érvényesítő csomópontot kompakt (kompakt állapotú csomópont), az akkumulátor nélküli érvényesítő pedig az teljes (teljes csomópont). A csomópontok két osztályának megléte problémát okoz egyetlen hálózatba való integrálásukkal, mivel a kompakt csomópontok megkövetelik az UTXO-k létezésének bizonyítását, amelyeket tranzakciókra költenek, míg a teljes csomópontok nem. Ha az összes hálózati csomópont nem egyidejűleg és összehangoltan vált át az Utreexo használatára, akkor a kompakt csomópontok lemaradnak, és nem fognak tudni működni a Bitcoin hálózaton.
A kompakt csomópontok hálózatba integrálásának problémájának megoldása érdekében javasoljuk egy további csomópont-osztály bevezetését - hidak. A hídcsomópont egy teljes csomópont, amely az Utreexo akkumulátort és a bekapcsolási bizonyítékot is tárolja minden UTXO az UTXO-készletből. A hidak új kivonatokat számítanak ki, és frissítik az akkumulátort és a bizonyítékokat, amint új tranzakcióblokkok érkeznek. Az akkumulátor és a bizonyítékok karbantartása és frissítése nem jelent további számítási terhelést az ilyen csomópontokra. A hidak feláldozzák a lemezterületet: rendszerezni kell a dolgokat hash, ehhez képest kivonatokat a kompakt csomópontokhoz, ahol n az UTXO halmaz hatványa.
Hálózati architektúra
A hidak lehetővé teszik a kompakt csomópontok fokozatos hozzáadását a hálózathoz a meglévő csomópontok szoftverének megváltoztatása nélkül. A teljes csomópontok ugyanúgy működnek, mint korábban, a tranzakciókat és a blokkokat elosztva egymás között. A hídcsomópontok olyan teljes csomópontok, amelyek emellett tárolják az Utreexo akkumulátoradatokat és egy sor felvételi bizonyítékot minden UTXO egyelőre. A hídcsomópont nem hirdeti magát, hanem úgy tesz, mintha teljes csomópont lenne minden teljes csomópontnál, és kompakt csomópont minden kompaktnál. Bár a hidak összekötik a két hálózatot, valójában csak egy irányba kell összekötniük őket: a meglévő teljes csomópontoktól a kompakt csomópontokig. Ez azért lehetséges, mert a tranzakciós formátumot nem kell módosítani, és a kompakt csomópontok UTXO-próbáját el lehet vetni, így bármely kompakt csomópont hasonlóan sugározhatja a tranzakciókat a hálózat összes résztvevője számára a híd csomópontok részvétele nélkül.
Következtetés
Megnéztük az Utreexo akkumulátort, és megvalósítottuk a prototípusát Rustban. Megvizsgáltuk azt a hálózati architektúrát, amely lehetővé teszi az akkumulátor alapú csomópontok integrálását. A kompakt rögzítések előnye a tárolt adatok mérete, amely logaritmikusan függ az UTXO-készlet teljesítményétől, ami nagymértékben csökkenti az ilyen csomópontok lemezterület- és tárolási teljesítményigényét. Hátránya a további csomóponti forgalom a bizonyítékok továbbításához, de a bizonyítékok összesítési technikái (amikor egy bizonyíték több elem létezését bizonyítja) és a gyorsítótárazás segíthet a forgalmat elfogadható határokon belül tartani.
referenciák:
- -
Forrás: will.com