Ehi Habr!
Nella rete Bitcoin, tutti i nodi, attraverso il consenso, concordano su una serie di UTXO: quante monete sono disponibili per la spesa, a chi esattamente e a quali condizioni. Il set UTXO è l'insieme minimo di dati richiesti per un nodo validatore, senza il quale il nodo non sarà in grado di verificare la validità delle transazioni in entrata e dei blocchi che le contengono.
A questo proposito si sta tentando in tutti i modi di ridurre la rappresentazione memorizzata di questo insieme, per comprimerla senza perdere le garanzie di sicurezza. Minore è il volume dei dati archiviati, minori sono i requisiti di spazio su disco del nodo validatore, il che rende economico l'avvio di un nodo validatore, consente di espandere la rete e quindi aumentare la stabilità della rete.
In questo post pubblicheremo un prototipo Rust di una recente proposta di un coautore , - , che consente di ridurre i requisiti di spazio su disco per i nodi di convalida.
Qual è il problema?
Uno dei problemi perenni di Bitcoin è stata la sua scalabilità. L’idea della “tua banca” richiede che i partecipanti alla rete tengano traccia di tutti i fondi disponibili per l’uso. In Bitcoin, i fondi disponibili sono espressi come un insieme di output non spesi: un insieme UTXO. Sebbene questa non sia una rappresentazione particolarmente intuitiva, è vantaggiosa in termini di prestazioni di implementazione rispetto a una rappresentazione in cui ogni "portafoglio" ha un "saldo" come voce separata e aggiunge anche privacy (ad es. ).
È importante distinguere tra la storia delle transazioni (quella che viene chiamata blockchain) e lo stato attuale del sistema. La cronologia delle transazioni Bitcoin attualmente occupa circa 200 GB di spazio su disco e continua a crescere. Tuttavia, lo stato del sistema è molto più piccolo, nell’ordine di 4 GB, e tiene conto solo del fatto che qualcuno attualmente possiede monete. Anche il volume di questi dati aumenta nel tempo, ma a un ritmo molto più lento e talvolta tende addirittura a diminuire (vedi CDPV).
I Light Client (SPV) scambiano garanzie di sicurezza con la capacità di non memorizzare alcuno stato minimo (set UTXO) diverso dalle chiavi private.
Set UTXO e UTXO
UTXO (Unspent Transaction Output) è l'output della transazione non spesa, il punto finale del viaggio di ogni Satoshi trasferito nelle transazioni. Gli output non spesi diventano input di nuove transazioni e vengono quindi spesi (spend) e rimossi dal set UTXO.
I nuovi UTXO vengono sempre creati dalle transazioni:
- transazioni coinbase senza input: crea nuovi UTXO quando i minatori emettono monete
- transazioni regolari: crea nuove UTXO spendendo un certo insieme di UTXO esistenti
Processo di lavoro con UTXO:
I portafogli contano il numero di monete disponibili per la spesa (saldo) in base alla quantità di UTXO disponibile per la spesa su questo portafoglio.
Ciascun nodo validatore, per evitare tentativi di doppia spesa, deve monitorare l'insieme tutti UTXO durante il controllo a testa transazioni ogni bloccare.
Il nodo deve avere una logica:
- Aggiunte al set UTXO
- Eliminazioni dal set UTXO
- Verifica della presenza di un singolo UTXO in un set
Esistono modi per ridurre i requisiti per le informazioni memorizzate su un set, pur mantenendo la possibilità di aggiungere e rimuovere elementi, verificare e dimostrare l'esistenza di un elemento in un set utilizzando .
Batterie per UTXO
L'idea di utilizzare le batterie per immagazzinare più UTXO .
Il set UTXO viene creato al volo, durante il download del blocco iniziale (IBD), archiviato per intero e in modo permanente, mentre il suo contenuto cambia dopo l'elaborazione delle transazioni da ogni blocco nuovo e corretto della rete. Questo processo richiede il download di circa 200 GB di dati in blocco e la verifica di centinaia di milioni di firme digitali. Una volta completato il processo IBD, la conclusione è che il set UTXO occuperà circa 4 GB.
Tuttavia, con gli accumulatori, le regole di consenso per i fondi si riducono alla verifica e alla generazione di prove crittografiche, e l’onere di tracciare i fondi disponibili viene trasferito al proprietario di tali fondi, che fornisce la prova della loro esistenza e proprietà.
Un accumulatore può essere definito una rappresentazione compatta di un insieme. La dimensione della rappresentazione memorizzata deve essere costante , oppure aumentare in modo sublineare rispetto alla cardinalità dell'insieme e alla dimensione dell'elemento stesso, ad esempio , dove n è la cardinalità dell'insieme memorizzato.
In questo caso, l'accumulatore dovrebbe consentire di generare una prova dell'inclusione di un elemento nell'insieme (prova di inclusione) e consentire di verificare efficacemente tale prova.
Si chiama la batteria dinamico if ti consente di aggiungere elementi e rimuovere elementi da un set.
Un esempio di tale batteria sarebbe . Un tale accumulatore ha una dimensione costante della rappresentazione memorizzata, ma richiede la presenza segreto condiviso (configurazione attendibile). Questo requisito nega l’applicabilità di un tale accumulatore per reti trustless come Bitcoin, poiché la perdita di dati durante la generazione segreta può consentire agli aggressori di creare false prove dell’esistenza di un UTXO, ingannando i nodi con un set UTXO basato su tale accumulatore.
Utreexo
Il design Utreexo proposto da Thaddeus Dryja permette di creare dinamico аккумулятор без configurazione attendibile.
Utreexo è una foresta di binari perfetti ed è uno sviluppo delle idee presentate in , aggiungendo la possibilità di rimuovere elementi da un set.
Struttura logica della batteria
Le celle della batteria sono disposte in una foresta di alberi binari ideali. Gli alberi sono ordinati per altezza. Questa rappresentazione è stata scelta come la più visiva e consente di visualizzare l'unione degli alberi durante le operazioni sulla batteria.
L'autore nota che poiché tutti gli alberi della foresta sono ideali, la loro altezza è espressa come una potenza di due, così come qualsiasi numero naturale può essere rappresentato come una somma di potenze di due. Di conseguenza, qualsiasi insieme di foglie può essere raggruppato in alberi binari e, in tutti i casi, l'aggiunta di un nuovo elemento richiede conoscenza solo sui nodi radice degli alberi memorizzati.
Pertanto, la rappresentazione memorizzata dell'accumulatore Utreexo è un elenco di nodi radice (radice Merkle), e non l'intera foresta di alberi.
Rappresentiamo l'elenco degli elementi radice come Vec<Option<Hash>>. Tipo facoltativo Option<Hash> indica che potrebbe mancare l'elemento radice, il che significa che nell'accumulatore non è presente un albero con l'altezza adeguata.
/// 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],
}
}
}Aggiunta di elementi
Per prima cosa descriviamo la funzione parent(), che riconosce il nodo genitore per due dati elementi.
funzione genitore()
Poiché stiamo utilizzando gli alberi Merkle, il genitore di ciascuno dei due nodi è un nodo che memorizza l'hash della concatenazione degli hash dei nodi figli:
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[..])
}L'autore osserva che per prevenire gli attentati descritti da Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir e Sebastien Zimmer in
, oltre ai due hash, alla concatenazione va aggiunta anche l'altezza all'interno dell'albero.
Quando aggiungi elementi all'accumulatore, devi tenere traccia di quali elementi radice vengono modificati. Seguendo il percorso di modifica degli elementi radice per ogni elemento aggiunto, puoi successivamente costruire una prova della presenza di questi elementi.
Tieni traccia delle modifiche man mano che le aggiungi
Per tenere traccia delle modifiche apportate, dichiariamo la struttura Update, che memorizzerà i dati sulle modifiche del nodo.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Per aggiungere un elemento alla batteria, è necessario:
- Crea una serie di cestini di elementi radice
new_rootse posiziona lì gli elementi root esistenti, uno per ogni bucket:
codice
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);
}- Aggiungi gli elementi da aggiungere (array
insertions) al primo carrellonew_roots[0]:
codice
new_roots[0].extend_from_slice(insertions);- Unisci gli articoli aggiunti al primo carrello con il resto:
- Per tutti i carrelli con più di un articolo:
- Prendi due elementi dall'estremità del cestino, calcola il loro genitore, rimuovi entrambi gli elementi
- Aggiungi il genitore calcolato al carrello successivo
- Per tutti i carrelli con più di un articolo:
codice
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 });
}
}- Sposta gli elementi radice dai contenitori all'array di accumulatori risultante
codice
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]);
}
}Creazione di una prova per gli elementi aggiunti
Prova dell'inclusione della cella nella batteria (Proof) servirà come il Sentiero Merkle, costituito da una catena ProofStep. Se il percorso non porta da nessuna parte, la dimostrazione è errata.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Utilizzando le informazioni ottenute in precedenza durante l'aggiunta di un elemento (struttura Update), puoi creare la prova che un elemento è stato aggiunto alla batteria. Per fare ciò, esaminiamo la tabella delle modifiche apportate e aggiungiamo ogni passaggio al percorso di Merkle, che successivamente servirà come prova:
codice
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
}
}Processo di creazione di una prova
Controllare la dimostrazione di un elemento
Controllare la prova di inclusione di un elemento si riduce a seguire il percorso Merkle finché non porta a un elemento radice esistente:
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
}
}visivamente:
Processo di verifica della dimostrazione per A
Rimozione di elementi
Per rimuovere una cella da una batteria, è necessario fornire una prova valida della presenza della cella. Utilizzando i dati della dimostrazione è possibile calcolare nuovi elementi radice dell'accumulatore per i quali la dimostrazione data non sarà più vera.
L'algoritmo è il seguente:
- Come per l'addizione, organizziamo un insieme di cesti vuoti corrispondenti agli alberi Merkle con altezza pari alla potenza di due dell'indice del cesto
- Inseriamo nei cestini gli elementi provenienti dai gradini del percorso Merkle; l'indice del paniere è pari al numero del passo corrente
- Rimuoviamo l'elemento radice a cui conduce il percorso dalla dimostrazione
- Come per l'aggiunta, calcoliamo i nuovi elementi radice combinando gli elementi dei panieri in coppie e spostando il risultato dell'unione nel paniere successivo
codice
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;
}
}Il processo di rimozione dell'elemento "A":
Integrazione in una rete esistente
Utilizzando l'accumulatore proposto, i nodi possono evitare di utilizzare un DB per memorizzare tutti gli UTXO pur essendo in grado di modificare il set di UTXO. Tuttavia, sorge il problema di lavorare con le prove.
Chiamiamo il nodo validatore che utilizza l'accumulatore UTXO compatto (nodo a stato compatto) e il validatore senza accumulatore lo è pieno (nodo completo). L’esistenza di due classi di nodi crea un problema per la loro integrazione in un’unica rete, poiché i nodi compatti richiedono la prova dell’esistenza di UTXO, che vengono spesi nelle transazioni, mentre i nodi completi no. Se tutti i nodi della rete non passano simultaneamente e in modo coordinato all’utilizzo di Utreexo, i nodi compatti rimarranno indietro e non saranno in grado di operare sulla rete Bitcoin.
Per risolvere il problema dell'integrazione dei nodi compatti nella rete, si propone di introdurre un'ulteriore classe di nodi: ponti. Un nodo bridge è un nodo completo che memorizza anche la batteria Utreexo e la prova di accensione tutti UTXO dal set UTXO. I bridge calcolano nuovi hash e aggiornano l'accumulatore e le prove man mano che arrivano nuovi blocchi di transazioni. Il mantenimento e l'aggiornamento dell'accumulatore e delle prove non impone un carico computazionale aggiuntivo su tali nodi. I bridge sacrificano lo spazio su disco: è necessario mantenere le cose organizzate hash, rispetto a hash per nodi compatti, dove n è la potenza del set UTXO.
Architettura di rete
I bridge consentono di aggiungere gradualmente nodi compatti alla rete senza modificare il software dei nodi esistenti. I nodi completi funzionano come prima, distribuendo transazioni e blocchi tra di loro. I nodi bridge sono nodi completi che memorizzano inoltre i dati della batteria Utreexo e una serie di prove di inclusione per tutti UTXO per ora. Il nodo bridge non si pubblicizza come tale, fingendo di essere un nodo completo per tutti i nodi completi e un nodo compatto per tutti quelli compatti. Sebbene i bridge colleghino insieme entrambe le reti, in realtà devono collegarle solo in una direzione: dai nodi completi esistenti ai nodi compatti. Ciò è possibile perché non è necessario modificare il formato della transazione e le prove UTXO per i nodi compatti possono essere scartate, quindi qualsiasi nodo compatto può trasmettere in modo simile transazioni a tutti i partecipanti alla rete senza la partecipazione dei nodi bridge.
conclusione
Abbiamo esaminato la batteria Utreexo e implementato il suo prototipo in Rust. Abbiamo esaminato l'architettura di rete che consentirà l'integrazione di nodi basati su batteria. Il vantaggio delle catture compatte è la dimensione dei dati archiviati, che dipende logaritmicamente dalla potenza dell'insieme di UTXO, il che riduce notevolmente i requisiti di spazio su disco e prestazioni di archiviazione per tali nodi. Lo svantaggio è il traffico aggiuntivo sui nodi per la trasmissione delle prove, ma le tecniche di aggregazione delle prove (quando una prova dimostra l'esistenza di diversi elementi) e il caching possono aiutare a mantenere il traffico entro limiti accettabili.
riferimenti:
- -
Fonte: habr.com