Hej Habr!
I Bitcoin-nätverket kommer alla noder, genom konsensus, överens om en uppsättning UTXO:er: hur många mynt är tillgängliga för utgifter, till vem exakt och under vilka villkor. UTXO-uppsättningen är den minsta uppsättning data som krävs för en valideringsnod, utan vilken noden inte kommer att kunna verifiera giltigheten av inkommande transaktioner och blocken som innehåller dem.
I detta avseende görs försök på alla möjliga sätt att minska den lagrade representationen av denna uppsättning, för att komprimera den utan att förlora säkerhetsgarantier. Ju mindre volym lagrad data är, desto lägre krav på diskutrymme för valideringsnoden, vilket gör lanseringen av en valideringsnod billig, gör att du kan utöka nätverket och därigenom öka stabiliteten i nätverket.
I det här inlägget kommer vi att lägga upp en Rust-prototyp av ett färskt förslag från en medförfattare , - , vilket gör det möjligt att minska kraven på diskutrymme för valideringsnoder.
Vad är problemet?
Ett av Bitcoins ständiga problem har varit dess skalbarhet. Idén med "din egen bank" kräver att nätverksdeltagare håller register över alla medel som är tillgängliga för användning. I Bitcoin uttrycks tillgängliga medel som en uppsättning outnyttjade utgångar - en UTXO-uppsättning. Även om detta inte är en särskilt intuitiv representation, är det fördelaktigt när det gäller implementeringsprestanda framför en representation där varje "plånbok" har ett "saldo" som en separat post, och även lägger till integritet (t.ex. ).
Det är viktigt att skilja mellan transaktionshistorik (det som kallas blockchain) och systemets nuvarande tillstånd. Bitcoin transaktionshistorik upptar för närvarande cirka 200 GB diskutrymme och fortsätter att växa. Systemtillståndet är dock mycket mindre, i storleksordningen 4 GB, och tar bara hänsyn till att någon för närvarande äger mynt. Volymen av dessa data ökar också med tiden, men i mycket långsammare takt och tenderar ibland till och med att minska (se CDPV).
Lätta klienter (SPV) byter ut säkerhetsgarantier för möjligheten att inte lagra något minimitillstånd (UTXO-set) annat än privata nycklar.
UTXO och UTXO-set
UTXO (Ospent Transaction Output) är den outnyttjade transaktionsutgången, slutpunkten på resan för varje Satoshi som överförs i transaktioner. Outnyttjade utdata blir indata för nya transaktioner och förbrukas (spenderas) och tas bort från UTXO-uppsättningen.
Nya UTXO skapas alltid av transaktioner:
- myntbastransaktioner utan indata: skapa nya UTXO när gruvarbetare ger ut mynt
- regelbundna transaktioner: skapa nya UTXO samtidigt som du spenderar en viss uppsättning befintliga UTXO
Processen att arbeta med UTXO:
Plånböcker räknar antalet mynt tillgängliga för utgifter (saldo) baserat på mängden UTXO som är tillgänglig för denna plånbok för utgifter.
Varje valideringsnod måste övervaka uppsättningen för att förhindra dubbla utgiftsförsök Alla UTXO vid kontroll varje transaktioner av varje blockera.
Noden måste ha logik:
- Tillägg till UTXO-set
- Borttagningar från UTXO-set
- Kontrollera förekomsten av en enda UTXO i en uppsättning
Det finns sätt att minska kraven på lagrad information om en uppsättning, samtidigt som man bibehåller möjligheten att lägga till och ta bort element, kontrollera och bevisa existensen av ett element i en uppsättning med hjälp av .
Batterier för UTXO
Idén med att använda batterier för att lagra flera UTXO:er .
UTXO-setet byggs direkt, under den första blocknedladdningen (IBD), lagras i sin helhet och permanent, medan dess innehåll ändras efter att transaktioner bearbetats från varje nytt och korrekt block i nätverket. Denna process kräver nedladdning av cirka 200 GB blockdata och verifiering av hundratals miljoner digitala signaturer. Efter att IBD-processen är klar är slutsatsen att UTXO-setet kommer att uppta cirka 4 GB.
Men med ackumulatorer reduceras reglerna för samförstånd för medel till verifiering och generering av kryptografiska bevis, och bördan av att spåra tillgängliga medel flyttas över till ägaren av dessa medel, som ger bevis på deras existens och ägande.
En ackumulator kan kallas en kompakt representation av en mängd. Storleken på den lagrade representationen måste antingen vara konstant , eller öka sublinjärt med avseende på uppsättningens kardinalitet och storleken på själva elementet, till exempel där n är kardinaliteten för den lagrade uppsättningen.
I det här fallet bör ackumulatorn tillåta generering av ett bevis på inkluderingen av ett element i uppsättningen (inklusionsbevis) och göra det möjligt att effektivt verifiera detta bevis.
Batteriet kallas dynamisk if låter dig lägga till element och ta bort element från en uppsättning.
Ett exempel på ett sådant batteri skulle vara . En sådan ackumulator har en konstant storlek på lagrad representation, men kräver närvaro delad hemlighet (pålitlig installation). Detta krav förnekar tillämpligheten av en sådan ackumulator för tillförlitliga nätverk som Bitcoin, eftersom dataläckage under hemlig generering kan tillåta angripare att skapa falska bevis på existensen av en UTXO, lura noder med en UTXO-uppsättning baserad på en sådan ackumulator.
Utreexo
Utreexo-designen som föreslås av Thaddeus Dryja gör det möjligt att skapa dynamisk batteri без betrodd-setup.
Utreexo är en skog av perfekt binär och är en utveckling av de idéer som presenteras i , lägga till möjligheten att ta bort element från en uppsättning.
Batteriets logiska struktur
Battericellerna är ordnade i en skog av idealiska binära träd. Träden är sorterade efter höjd. Denna representation valdes som den mest visuella och låter dig visualisera sammanslagning av träd under operationer på batteriet.
Författaren noterar att eftersom alla träd i skogen är idealiska uttrycks deras höjd som en potens av två, precis som vilket naturligt tal som helst kan representeras som summan av två potenser. Följaktligen kan vilken uppsättning löv som helst grupperas i binära träd, och i alla fall kräver kunskap om att lägga till ett nytt element endast om rotnoder hos lagrade träd.
Således är den lagrade representationen av Utreexo-ackumulatorn en lista över rotnoder (Merkle root), och inte hela skogen av träd.
Låt oss representera listan med rotelement som Vec<Option<Hash>>. Valfri typ Option<Hash> indikerar att rotelementet kan saknas, vilket betyder att det inte finns något träd med lämplig höjd i ackumulatorn.
/// 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],
}
}
}Lägga till element
Låt oss först beskriva funktionen parent(), som känner igen föräldernoden för två givna element.
parent() funktion
Eftersom vi använder Merkle-träd är föräldern till var och en av de två noderna en nod som lagrar hashen för sammanlänkningen av hasharna för de underordnade noderna:
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[..])
}Författaren noterar att för att förhindra attackerna som beskrivs av Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir och Sebastien Zimmer i
, förutom de två hasharna, bör höjden inuti trädet också läggas till sammanlänkningen.
När du lägger till element i ackumulatorn måste du hålla reda på vilka rotelement som ändras. Genom att följa vägen för att ändra rotelementen för varje element du lägger till, kan du senare konstruera ett bevis på närvaron av dessa element.
Spåra ändringar när du lägger till dem
För att spåra ändringarna som gjorts, låt oss deklarera strukturen Update, som lagrar data om nodändringar.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}För att lägga till ett element till batteriet behöver du:
- Skapa en rad korgar med rotelement
new_rootsoch placera de befintliga rotelementen där, en för varje hink:
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);
}- Lägg till elementen som ska läggas till (array
insertions) till den första vagnennew_roots[0]:
Kod
new_roots[0].extend_from_slice(insertions);- Sammanfoga varorna som lagts till i den första korgen med resten:
- För alla vagnar med mer än en vara:
- Ta två element från slutet av korgen, beräkna deras förälder, ta bort båda elementen
- Lägg till den beräknade föräldern i nästa kundvagn
- För alla vagnar med mer än en vara:
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 });
}
}- Flytta rotelement från fack till den resulterande ackumulatormatrisen
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]);
}
}Skapa ett bevis för tillagda element
Bevis på inkludering av cellen i batteriet (Proof) kommer att fungera som Merkle Path, bestående av en kedja ProofStep. Om vägen inte leder någonstans, är beviset felaktigt.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Använda den information som erhållits tidigare när du lägger till ett element (struktur Update), kan du skapa bevis på att ett element har lagts till batteriet. För att göra detta går vi igenom tabellen över gjorda ändringar och lägger till varje steg till Merkles väg, som sedan kommer att fungera som bevis:
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
}
}Processen att skapa ett bevis
Kontrollera beviset för ett element
Att kontrollera ett elements inkluderingsbevis handlar om att följa Merkle-vägen tills det leder till ett befintligt rotelement:
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
}
}Klart:
Processen för att kontrollera beviset för A
Ta bort föremål
För att ta bort en cell från ett batteri måste du tillhandahålla giltiga bevis på att cellen finns där. Med hjälp av data från beviset är det möjligt att beräkna nya rotelement i ackumulatorn för vilka det givna beviset inte längre kommer att vara sant.
Algoritmen är följande:
- Som med tillägg organiserar vi en uppsättning tomma korgar som motsvarar Merkle-träd med en höjd lika med tvåpotensen från korgindex
- Vi lägger in element från stegen på Merkle-stigen i korgarna; korgindex är lika med numret på det aktuella steget
- Vi tar bort rotelementet som vägen från beviset leder till
- Som med att lägga till, beräknar vi nya rotelement genom att kombinera element från korgar i par och flytta resultatet av föreningen till nästa korg
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;
}
}Processen att ta bort element "A":
Integrering i ett befintligt nätverk
Med den föreslagna ackumulatorn kan noder undvika att använda en DB för att lagra alla UTXO:er samtidigt som de kan ändra UTXO-uppsättningen. Problemet med att arbeta med bevis uppstår dock.
Låt oss anropa valideringsnoden som använder UTXO-ackumulatorn kompakt (compact-state nod), och validatorn utan en ackumulator är full (full nod). Förekomsten av två klasser av noder skapar ett problem för att integrera dem i ett enda nätverk, eftersom kompakta noder kräver bevis på förekomsten av UTXO, som spenderas i transaktioner, medan fullständiga noder inte gör det. Om inte alla nätverksnoder samtidigt och på ett koordinerat sätt övergår till att använda Utreexo, kommer kompakta noder att lämnas kvar och kommer inte att kunna fungera på Bitcoin-nätverket.
För att lösa problemet med att integrera kompakta noder i nätverket föreslås det att införa en extra klass av noder - broar. En bryggnod är en komplett nod som även lagrar Utreexo-batteriet och påslagssäkrat för Alla UTXO från UTXO-set. Broar beräknar nya hash och uppdaterar ackumulatorn och bevisen när nya block av transaktioner anländer. Att underhålla och uppdatera ackumulatorn och bevisen medför inte ytterligare beräkningsbelastning på sådana noder. Broar offrar diskutrymme: måste hålla saker organiserade hash, jämfört med hash för kompakta noder, där n är kraften för UTXO-uppsättningen.
Nätverksarkitektur
Broar gör det möjligt att gradvis lägga till kompakta noder till nätverket utan att ändra mjukvaran för befintliga noder. Fulla noder fungerar som tidigare och distribuerar transaktioner och block mellan sig. Bryggnoder är fulla noder som dessutom lagrar Utreexo-batteridata och en uppsättning inklusionsbevis för Alla UTXO för nu. Bryggnoden annonserar inte sig själv som sådan och låtsas vara en full nod för alla fulla noder och en kompakt nod för alla kompakta. Även om bryggor kopplar samman båda nätverken behöver de faktiskt bara ansluta dem i en riktning: från befintliga fulla noder till kompakta noder. Detta är möjligt eftersom transaktionsformatet inte behöver ändras och UTXO-bevis för kompakta noder kan kasseras, så vilken kompakt nod som helst kan på liknande sätt sända transaktioner till alla nätverksdeltagare utan deltagande av bryggnoder.
Slutsats
Vi tittade på Utreexo-batteriet och implementerade dess prototyp i Rust. Vi tittade på nätverksarkitekturen som möjliggör integration av batteribaserade noder. Fördelen med kompakta fångar är storleken på den lagrade datan, som logaritmiskt beror på kraften hos uppsättningen UTXO, vilket kraftigt minskar kraven på diskutrymme och lagringsprestanda för sådana noder. Nackdelen är den extra nodtrafiken för att överföra bevis, men bevisaggregeringstekniker (när ett bevis bevisar att det finns flera element) och cachning kan hjälpa till att hålla trafiken inom acceptabla gränser.
referenser:
- -
Källa: will.com