Hei Habr!
Bitcoin-verkossa kaikki solmut sopivat yksimielisesti UTXO-joukosta: kuinka monta kolikkoa on käytettävissä kulutukseen, kenelle tarkalleen ja millä ehdoilla. UTXO-joukko on validaattorisolmun vaatima vähimmäistietojoukko, jota ilman solmu ei pysty varmistamaan saapuvien tapahtumien ja niitä sisältävien lohkojen oikeellisuutta.
Tältä osin yritetään kaikin mahdollisin tavoin vähentää tämän joukon tallennettua esitystä, pakata se menettämättä turvallisuustakuita. Mitä pienempi tallennetun datan määrä on, sitä pienemmät validointisolmun levytilantarve on, mikä tekee validointisolmun käynnistämisestä halpaa, mahdollistaa verkon laajentamisen ja siten verkon vakauden lisäämisen.
Tässä viestissä julkaisemme Rust-prototyypin äskettäin tekemästä ehdotuksesta , - , joka mahdollistaa tarkistussolmujen levytilan tarpeen vähentämisen.
Mikä on ongelma?
Yksi Bitcoinin monivuotisista ongelmista on ollut sen skaalautuvuus. "Oman pankin" ajatus edellyttää, että verkoston osallistujat pitävät kirjaa kaikista käytettävissä olevista varoista. Bitcoinissa käytettävissä olevat varat ilmaistaan käyttämättömien tulosten joukkona - UTXO-sarjana. Vaikka tämä ei ole erityisen intuitiivinen esitys, se on hyödyllinen toteutustehokkuuden kannalta verrattuna esitykseen, jossa jokaisessa "lompakossa" on "saldo" erillisenä merkintänä, ja se lisää myös yksityisyyttä (esim. ).
On tärkeää erottaa tapahtumahistoria (niin sanottu lohkoketju) ja järjestelmän nykyinen tila. Bitcoin-tapahtumahistoria vie tällä hetkellä noin 200 Gt levytilaa ja jatkaa kasvuaan. Järjestelmän tila on kuitenkin paljon pienempi, luokkaa 4 Gt, ja se ottaa huomioon vain sen tosiasian, että joku omistaa tällä hetkellä kolikoita. Myös näiden tietojen määrä kasvaa ajan myötä, mutta paljon hitaammin ja joskus jopa vähenee (katso CDPV).
Kevyet asiakkaat (SPV:t) takaavat, että ne eivät pysty tallentamaan muita vähimmäistilaa (UTXO-set) kuin yksityisiä avaimia.
UTXO ja UTXO-setti
UTXO (Unspent Transaction Output) on käyttämättä jäänyt tapahtumatulos, jokaisen transaktioissa siirretyn Satoshin matkan päätepiste. Käyttämättömät lähdöt tulevat uusien tapahtumien syötteiksi ja ne kulutetaan (kulutetaan) ja poistetaan UTXO-joukosta.
Uudet UTXO:t luodaan aina tapahtumilla:
- coinbase-tapahtumat ilman syötteitä: luo uusia UTXO:ita, kun kaivostyöläiset laskevat kolikoita
- säännölliset tapahtumat: luo uusia UTXO:ita samalla kun käytät tiettyä joukkoa olemassa olevia UTXO:ita
UTXO:n kanssa työskentelyprosessi:
Lompakot laskevat kulutettavien kolikoiden määrän (saldo) tämän lompakon kulutukseen käytettävissä olevan UTXO-määrän perusteella.
Jokaisen validointisolmun on valvottava joukkoa, jotta vältetään kaksinkertaiset kulutusyritykset Kaikki UTXO tarkistettaessa kukin liiketoimia kukin lohko.
Solmussa on oltava logiikka:
- Lisäyksiä UTXO-sarjaan
- Poistoja UTXO-sarjasta
- Yhden UTXO:n läsnäolon tarkistaminen sarjassa
On olemassa tapoja vähentää vaatimuksia joukosta tallennetuille tiedoille säilyttäen samalla mahdollisuus lisätä ja poistaa elementtejä, tarkistaa ja todistaa elementin olemassaolo joukossa käyttämällä .
Akut UTXO:lle
Ajatus akkujen käyttämisestä useiden UTXO:iden tallentamiseen .
UTXO-sarja rakennetaan lennossa, alkulohkolatauksen (IBD) aikana, tallennetaan kokonaisuudessaan ja pysyvästi, kun taas sen sisältö muuttuu jokaisen uuden ja oikean verkon lohkon tapahtumien käsittelyn jälkeen. Tämä prosessi vaatii noin 200 Gt:n lohkodatan lataamisen ja satojen miljoonien digitaalisten allekirjoitusten tarkistamisen. Kun IBD-prosessi on valmis, UTXO-sarja vie noin 4 Gt.
Varastojen osalta konsensussäännöt rajoittuvat kuitenkin salaustodisteiden varmentamiseen ja luomiseen, ja käytettävissä olevien varojen jäljittämisen taakka siirtyy varojen omistajalle, joka todistaa niiden olemassaolon ja omistajuuden.
Akkua voidaan kutsua joukon kompaktiksi esitykseksi. Tallennetun esityksen koon on oltava joko vakio tai kasvaa sublineaarisesti suhteessa joukon kardinaalisuuteen ja itse elementin kokoon, esim. , jossa n on tallennetun joukon kardinaalisuus.
Tässä tapauksessa akun pitäisi mahdollistaa todistuksen luominen elementin sisällyttämisestä joukkoon (sisällytystodistus) ja mahdollistaa tämän todisteen tehokas todentaminen.
Akku on ns dynaaminen jos voit lisätä elementtejä ja poistaa elementtejä joukosta.
Esimerkki tällaisesta akusta olisi . Tällaisella akulla on vakiokoko tallennetun esityksen, mutta se vaatii läsnäolon yhteinen salaisuus (luotettu asennus). Tämä vaatimus kumoaa tällaisen akun sovellettavuuden luotettaviin verkkoihin, kuten Bitcoiniin, koska tietovuoto salaisen generoinnin aikana voi antaa hyökkääjille mahdollisuuden luoda vääriä todisteita UTXO:n olemassaolosta, pettääkseen solmuja UTXO-joukolla, joka perustuu tällaiseen akkuun.
Utreexo
Thaddeus Dryjan ehdottama Utreexo-design mahdollistaa luomisen dynaaminen akku без luotettu asetus.
Utreexo on täydellisen binäärien metsä ja se on jatkoa esitellyistä ideoista , lisäämällä mahdollisuuden poistaa elementtejä joukosta.
Akun looginen rakenne
Akkukennot on järjestetty ihanteellisten binääripuiden metsään. Puut on järjestetty korkeuden mukaan. Tämä esitys valittiin visuaalisimmaksi, ja sen avulla voit visualisoida puiden yhdistämisen akkutoimintojen aikana.
Kirjoittaja huomauttaa, että koska kaikki metsän puut ovat ihanteellisia, niiden korkeus ilmaistaan kahden potenssina, aivan kuten mikä tahansa luonnollinen luku voidaan esittää kahden potenssien summana. Näin ollen mikä tahansa lehtijoukko voidaan ryhmitellä binääripuiksi, ja kaikissa tapauksissa uuden elementin lisääminen vaatii tietoa vain varastoitujen puiden juurisolmuista.
Siten Utreexo-akun tallennettu esitys on luettelo juurisolmuista (Merkle-juuri), eikä koko puumetsää.
Esitetään juurielementtien luettelo muodossa Vec<Option<Hash>>. Valinnainen tyyppi Option<Hash> osoittaa, että juurielementti saattaa puuttua, mikä tarkoittaa, että akussa ei ole sopivan korkeutta puuta.
/// 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],
}
}
}Elementtien lisääminen
Ensin kuvataan toiminto parent(), joka tunnistaa kahden tietyn elementin pääsolmun.
parent()-funktio
Koska käytämme Merkle-puita, kummankin solmun emo on yksi solmu, joka tallentaa alisolmujen tiivisteiden ketjun tiivisteen:
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[..])
}Kirjoittaja panee merkille, että Charles Bouillaguet'n, Pierre-Alain Fouquen, Adi Shamirin ja Sebastien Zimmerin kuvaamien hyökkäysten estämiseksi
, kahden tiivisteen lisäksi ketjutukseen tulee lisätä myös puun sisäinen korkeus.
Kun lisäät elementtejä akkuun, sinun on seurattava, mitä juurielementtejä muutetaan. Seuraamalla kunkin lisäämäsi elementin juurielementtien muutospolkua voit myöhemmin rakentaa todisteen näiden elementtien olemassaolosta.
Seuraa muutoksia, kun lisäät niitä
Tehtyjen muutosten seuraamiseksi määritellään rakenne Update, joka tallentaa tiedot solmun muutoksista.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Elementin lisäämiseksi akkuun tarvitset:
- Luo joukko juurielementtien koreja
new_rootsja sijoita olemassa olevat juurielementit sinne, yksi kutakin säilöä kohti:
Koodi
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);
}- Liitä lisättävät elementit (taulukko
insertions) ensimmäiseen kärryynnew_roots[0]:
Koodi
new_roots[0].extend_from_slice(insertions);- Yhdistä ensimmäiseen koriin lisätyt tuotteet muiden kanssa:
- Kaikille kärryille, joissa on useampi kuin yksi tuote:
- Ota kaksi elementtiä korin päästä, laske niiden yläosa, poista molemmat elementit
- Lisää laskettu vanhempi seuraavaan koriin
- Kaikille kärryille, joissa on useampi kuin yksi tuote:
Koodi
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 });
}
}- Siirrä juurielementit laatikoista tuloksena olevaan akkutaulukkoon
Koodi
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]);
}
}Todisteen luominen lisätyille elementeille
Todiste kennon sisällyttämisestä akkuun (Proof) toimii Merkle-polkuna, joka koostuu ketjusta ProofStep. Jos polku ei johda mihinkään, todiste on väärä.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Aiemmin saatujen tietojen käyttäminen elementtiä (rakennetta) lisättäessä Update), voit luoda todisteen siitä, että akkuun on lisätty elementti. Tätä varten käymme läpi taulukon tehdyistä muutoksista ja lisäämme jokaisen askeleen Merklen polulle, joka toimii myöhemmin todisteena:
Koodi
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
}
}Todistuksen luomisprosessi
Elementin todisteen tarkistaminen
Elementin sisällyttämistodistuksen tarkistaminen tiivistyy Merklen polun seuraamiseen, kunnes se johtaa olemassa olevaan juurielementtiin:
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
}
}Selvästi:
Todistuksen tarkistusprosessi A:lle
Kohteiden poistaminen
Jos haluat poistaa kennon akusta, sinun on toimitettava pätevä todiste kennon olemassaolosta. Todistuksen tietojen avulla voidaan laskea akun uusia juurielementtejä, joille annettu todistus ei enää pidä paikkaansa.
Algoritmi on seuraava:
- Kuten lisäksi, järjestämme joukon tyhjiä koreja, jotka vastaavat Merkle-puita, joiden korkeus vastaa kahden potenssia koriindeksistä
- Lisäämme elementtejä Merkle-polun portaista koreihin; koriindeksi on yhtä suuri kuin nykyisen askeleen numero
- Poistamme juurielementin, johon todistuksen polku johtaa
- Kuten lisäämisen yhteydessä, laskemme uudet juurielementit yhdistämällä elementit koreista pareittain ja siirtämällä yhdistämisen tuloksen seuraavaan koriin
Koodi
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;
}
}Elementin "A" poistoprosessi:
Integrointi olemassa olevaan verkkoon
Ehdotettua akkua käyttämällä solmut voivat välttää tietokannan käyttämisen kaikkien UTXO:iden tallentamiseen samalla, kun he voivat silti muuttaa UTXO-joukkoa. Ongelmana on kuitenkin todisteiden kanssa työskentely.
Kutsutaan validaattorisolmu, joka käyttää UTXO-akkua kompakti (kompaktitilasolmu), ja validaattori ilman akkua on täysi (täysi solmu). Kahden solmuluokan olemassaolo aiheuttaa ongelmia niiden integroinnissa yhdeksi verkkoksi, koska kompaktit solmut vaativat todisteita UTXO:iden olemassaolosta, jotka kulutetaan tapahtumiin, kun taas täydet solmut eivät. Jos kaikki verkon solmut eivät samanaikaisesti ja koordinoidusti siirry käyttämään Utreexoa, kompaktit solmut jäävät jälkeen eivätkä pysty toimimaan Bitcoin-verkossa.
Kompaktien solmujen verkkoon integroimisen ongelman ratkaisemiseksi ehdotetaan ottamaan käyttöön ylimääräinen solmuluokka - sillat. Siltasolmu on täydellinen solmu, joka tallentaa myös Utreexo-akun ja käynnistysvarmuuden Kaikki UTXO UTXO-sarjasta. Sillat laskevat uudet tiivisteet ja päivittävät akkua ja todisteita, kun uusia tapahtumalohkoja saapuu. Akun ja todisteiden ylläpito ja päivittäminen ei aiheuta lisälaskentakuormitusta tällaisille solmuille. Sillat uhraavat levytilaa: asiat on pidettävä järjestyksessä tiivisteet verrattuna tiivisteet kompakteille solmuille, missä n on UTXO-joukon potenssi.
Verkkoarkkitehtuuri
Sillat mahdollistavat pienten solmujen asteittaisen lisäämisen verkkoon muuttamatta olemassa olevien solmujen ohjelmistoja. Täydelliset solmut toimivat kuten ennenkin jakaen tapahtumat ja lohkot keskenään. Siltasolmut ovat täydellisiä solmuja, jotka lisäksi tallentavat Utreexon akkudataa ja joukon sisällytystodistuksia Kaikki UTXO toistaiseksi. Siltasolmu ei mainosta itseään sellaisenaan, teeskentelee olevansa täysi solmu kaikille täydellisille solmuille ja kompakti solmu kaikille kompakteille. Vaikka sillat yhdistävät molemmat verkot toisiinsa, niiden tarvitsee yhdistää ne vain yhteen suuntaan: olemassa olevista täydellisistä solmuista kompakteihin solmuihin. Tämä on mahdollista, koska tapahtumamuotoa ei tarvitse muuttaa ja kompaktien solmujen UTXO-todisteet voidaan hylätä, joten mikä tahansa kompakti solmu voi samalla tavalla lähettää tapahtumia kaikille verkon osallistujille ilman siltasolmujen osallistumista.
Johtopäätös
Tarkastelimme Utreexo-akkua ja toteutimme sen prototyypin Rustissa. Tarkastelimme verkkoarkkitehtuuria, joka mahdollistaa akkupohjaisten solmujen integroinnin. Kompaktien saaliiden etuna on tallennetun tiedon koko, joka riippuu logaritmisesti UTXO-joukon tehosta, mikä vähentää huomattavasti tällaisten solmujen levytilan ja tallennussuorituskyvyn vaatimuksia. Haittapuolena on ylimääräinen solmuliikenne todisteiden lähettämiseen, mutta todisteiden yhdistämistekniikat (kun yksi todiste todistaa useiden elementtien olemassaolon) ja välimuisti voivat auttaa pitämään liikenteen hyväksyttävissä rajoissa.
viittaukset:
- -
Lähde: will.com