Hé Habr!
In het Bitcoin-netwerk zijn alle knooppunten het via consensus eens over een reeks UTXO’s: hoeveel munten kunnen worden uitgegeven, aan wie precies en onder welke voorwaarden. De UTXO-set is de minimale set gegevens die vereist is voor een validatorknooppunt. Zonder deze gegevens kan het knooppunt de geldigheid van inkomende transacties en de blokken die deze bevatten niet verifiëren.
In dit opzicht worden er op alle mogelijke manieren pogingen ondernomen om de opgeslagen representatie van deze set te verkleinen en te comprimeren zonder de veiligheidsgaranties te verliezen. Hoe kleiner het volume aan opgeslagen gegevens, hoe lager de schijfruimtevereisten van het validatorknooppunt, wat het lanceren van een validatorknooppunt goedkoop maakt, u in staat stelt het netwerk uit te breiden en daardoor de stabiliteit van het netwerk te vergroten.
In dit bericht plaatsen we een Rust-prototype van een recent voorstel van een co-auteur , - , waarmee de schijfruimtevereisten voor validatorknooppunten kunnen worden verminderd.
Wat is het probleem?
Een van de eeuwige problemen van Bitcoin is de schaalbaarheid ervan. Het idee van ‘uw eigen bank’ vereist dat netwerkdeelnemers een register bijhouden van alle beschikbare middelen voor gebruik. In Bitcoin worden de beschikbare middelen uitgedrukt als een reeks niet-uitgegeven outputs – een UTXO-set. Hoewel dit geen bijzonder intuïtieve weergave is, is het gunstig in termen van implementatieprestaties ten opzichte van een weergave waarin elke "portemonnee" een "saldo" heeft als afzonderlijke ingang, en ook privacy toevoegt (bijv. ).
Het is belangrijk om onderscheid te maken tussen de geschiedenis van transacties (wat de blockchain wordt genoemd) en de huidige staat van het systeem. De transactiegeschiedenis van Bitcoin neemt momenteel ongeveer 200 GB schijfruimte in beslag en blijft groeien. De systeemstatus is echter veel kleiner, in de orde van 4 GB, en houdt alleen rekening met het feit dat iemand momenteel munten bezit. Het volume van deze gegevens neemt in de loop van de tijd ook toe, maar in een veel langzamer tempo en heeft soms zelfs de neiging af te nemen (zie CDPV).
Light clients (SPV's) bieden veiligheidsgaranties voor de mogelijkheid om geen andere minimumstatus (UTXO-set) op te slaan dan privésleutels.
UTXO en UTXO-set
UTXO (Unspent Transaction Output) is de ongebruikte transactie-output, het eindpunt van de reis van elke Satoshi die in transacties wordt overgedragen. Niet-bestede output wordt input voor nieuwe transacties en wordt dus uitgegeven (uitgegeven) en verwijderd uit de UTXO-set.
Nieuwe UTXO's worden altijd gecreëerd door transacties:
- Coinbase-transacties zonder invoer: creëer nieuwe UTXO's wanneer mijnwerkers munten uitgeven
- reguliere transacties: creëer nieuwe UTXO's terwijl u een bepaalde reeks bestaande UTXO's uitgeeft
Proces van werken met UTXO:
Portefeuilles tellen het aantal munten dat beschikbaar is voor besteding (saldo) op basis van de hoeveelheid UTXO die beschikbaar is voor deze portemonnee voor besteding.
Om dubbele bestedingspogingen te voorkomen, moet elk validatorknooppunt de set monitoren Alle UTXO bij controle elk transacties elke blok.
Het knooppunt moet logica bevatten:
- Toevoegingen aan UTXO-set
- Verwijderingen uit de UTXO-set
- Controleren van de aanwezigheid van een enkele UTXO in een set
Er zijn manieren om de vereisten voor opgeslagen informatie over een set te verminderen, terwijl de mogelijkheid behouden blijft om elementen toe te voegen en te verwijderen, het bestaan van een element in een set te controleren en te bewijzen met behulp van .
Batterijen voor UTXO
Het idee om batterijen te gebruiken om meerdere UTXO's op te slaan .
De UTXO-set wordt on-the-fly gebouwd, tijdens de initiële blokdownload (IBD), volledig en permanent opgeslagen, terwijl de inhoud ervan verandert na het verwerken van transacties van elk nieuw en correct blok van het netwerk. Voor dit proces moet ongeveer 200 GB aan blokgegevens worden gedownload en honderden miljoenen digitale handtekeningen worden geverifieerd. Nadat het IBD-proces is voltooid, komt het erop neer dat de UTXO-set ongeveer 4 GB in beslag zal nemen.
Bij accumulatoren worden de consensusregels voor fondsen echter gereduceerd tot de verificatie en het genereren van cryptografische bewijzen, en wordt de last van het traceren van beschikbare fondsen verlegd naar de eigenaar van die fondsen, die bewijs levert van hun bestaan en eigendom.
Een accumulator kan een compacte weergave van een verzameling worden genoemd. De grootte van de opgeslagen representatie moet constant zijn , of sublineair vergroten met betrekking tot de kardinaliteit van de set en de grootte van het element zelf, bijvoorbeeld , waarbij n de kardinaliteit van de opgeslagen set is.
In dit geval moet de accumulator het mogelijk maken een bewijs te genereren van de opname van een element in de set (insluitingsbewijs) en het mogelijk maken om dit bewijs effectief te verifiëren.
De batterij wordt genoemd dynamisch Hiermee kunt u elementen toevoegen en elementen uit een set verwijderen.
Een voorbeeld van zo'n batterij zou zijn . Zo'n accumulator heeft een constante grootte van opgeslagen representatie, maar vereist de aanwezigheid ervan gedeeld geheim (vertrouwde installatie). Deze vereiste ontkent de toepasbaarheid van een dergelijke accumulator voor betrouwbare netwerken zoals Bitcoin, omdat datalekken tijdens het genereren van geheimen aanvallers in staat kunnen stellen vals bewijs te creëren voor het bestaan van een UTXO, waarbij knooppunten worden misleid met een UTXO-set gebaseerd op een dergelijke accumulator.
Utreexo
Het door Thaddeus Dryja voorgestelde Utreexo-ontwerp maakt het mogelijk om te creëren dynamisch аккумулятор без vertrouwde installatie.
Utreexo is een woud van perfect binair getal en is een ontwikkeling van de ideeën gepresenteerd in , waardoor de mogelijkheid wordt toegevoegd om elementen uit een set te verwijderen.
Logische structuur van de batterij
De batterijcellen zijn gerangschikt in een bos van ideale binaire bomen. Bomen zijn gerangschikt op hoogte. Deze weergave werd gekozen als de meest visuele en stelt u in staat het samenvoegen van bomen tijdens werkzaamheden aan de batterij te visualiseren.
De auteur merkt op dat, aangezien alle bomen in het bos ideaal zijn, hun hoogte wordt uitgedrukt als een macht van twee, net zoals elk natuurlijk getal kan worden weergegeven als een som van machten van twee. Dienovereenkomstig kan elke set bladeren worden gegroepeerd in binaire bomen, en in alle gevallen vereist het toevoegen van een nieuw element kennis alleen over de hoofdknooppunten van opgeslagen bomen.
De opgeslagen weergave van de Utreexo-accumulator is dus een lijst met hoofdknooppunten (Merkle-wortel), en niet het hele bos van bomen.
Laten we de lijst met hoofdelementen weergeven als Vec<Option<Hash>>. Optioneel type Option<Hash> geeft aan dat het wortelelement mogelijk ontbreekt, wat betekent dat er geen boom met de juiste hoogte in de accumulator staat.
/// 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],
}
}
}Elementen toevoegen
Laten we eerst de functie beschrijven parent(), dat het bovenliggende knooppunt voor twee gegeven elementen herkent.
ouder() functie
Omdat we Merkle-bomen gebruiken, is de ouder van elk van de twee knooppunten één knooppunt dat de hash opslaat van de aaneenschakeling van de hashes van de onderliggende knooppunten:
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[..])
}De auteur merkt op dat om de aanvallen te voorkomen die zijn beschreven door Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir en Sebastien Zimmer in
Naast de twee hashes moet ook de hoogte binnen de boom aan de aaneenschakeling worden toegevoegd.
Terwijl u elementen aan de accumulator toevoegt, moet u bijhouden welke hoofdelementen zijn gewijzigd. Door het pad te volgen van het wijzigen van de hoofdelementen voor elk element dat u toevoegt, kunt u later een bewijs maken van de aanwezigheid van deze elementen.
Houd wijzigingen bij terwijl u ze toevoegt
Laten we de structuur declareren om de aangebrachte wijzigingen bij te houden Update, waarin gegevens over knooppuntwijzigingen worden opgeslagen.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Om een element aan de batterij toe te voegen, heb je het volgende nodig:
- Maak een reeks manden met wortelelementen
new_rootsen plaats daar de bestaande wortelelementen, één voor elke emmer:
code
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);
}- Voeg de toe te voegen elementen toe (array
insertions) naar de eerste karnew_roots[0]:
code
new_roots[0].extend_from_slice(insertions);- Voeg de items die aan het eerste mandje zijn toegevoegd samen met de rest:
- Voor alle winkelwagens met meer dan één artikel:
- Neem twee elementen uit het einde van de mand, bereken hun ouder, verwijder beide elementen
- Voeg de berekende ouder toe aan de volgende winkelwagen
- Voor alle winkelwagens met meer dan één artikel:
code
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 });
}
}- Verplaats rootelementen van bins naar de resulterende accumulatorarray
code
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]);
}
}Een proef maken voor toegevoegde elementen
Bewijs van opname van de cel in de batterij (Proof) zal dienen als het Merkle-pad, bestaande uit een ketting ProofStep. Als het pad nergens heen leidt, is het bewijs onjuist.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Gebruikmakend van de eerder verkregen informatie bij het toevoegen van een element (structure Update), kunt u het bewijs leveren dat een element aan de batterij is toegevoegd. Om dit te doen, doorlopen we de tabel met aangebrachte wijzigingen en voegen we elke stap toe aan Merkle’s pad, dat vervolgens als bewijs zal dienen:
code
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 voor het maken van een bewijs
Het bewijs voor een element controleren
Het controleren van het insluitingsbewijs van een element komt neer op het volgen van het Merkle-pad totdat het naar een bestaand hoofdelement leidt:
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
}
}Duidelijk:
Proces voor het controleren van het bewijs voor A
Artikelen verwijderen
Om een cel uit een batterij te verwijderen, moet u geldig bewijs overleggen dat de cel aanwezig is. Met behulp van de gegevens uit het bewijs is het mogelijk nieuwe wortelelementen van de accumulator te berekenen waarvoor het gegeven bewijs niet langer waar zal zijn.
Het algoritme is als volgt:
- Net als bij de toevoeging organiseren we een set lege manden die overeenkomen met Merkle-bomen met een hoogte gelijk aan de macht van twee uit de mandindex
- We plaatsen elementen van de trappen van het Merkle-pad in de manden; de korfindex is gelijk aan het nummer van de huidige stap
- We verwijderen het hoofdelement waarnaar het pad uit het bewijs leidt
- Net als bij het optellen berekenen we nieuwe wortelelementen door elementen uit manden in paren te combineren en het resultaat van de vereniging naar de volgende mand te verplaatsen
code
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;
}
}Het proces van het verwijderen van element "A":
Integratie in een bestaand netwerk
Met behulp van de voorgestelde accumulator kunnen knooppunten voorkomen dat een database wordt gebruikt om alle UTXO's op te slaan, terwijl ze toch de UTXO-set kunnen wijzigen. Het probleem van het werken met bewijs doet zich echter voor.
Laten we het validatorknooppunt aanroepen dat de UTXO-accumulator gebruikt compact (compact-state node), en de validator zonder accumulator is dat wel vol (volledig knooppunt). Het bestaan van twee klassen knooppunten schept een probleem bij de integratie ervan in één enkel netwerk, aangezien compacte knooppunten bewijs vereisen van het bestaan van UTXO's, die worden besteed aan transacties, terwijl dat bij volledige knooppunten niet het geval is. Als niet alle netwerkknooppunten tegelijkertijd en gecoördineerd overstappen op het gebruik van Utreexo, blijven compacte knooppunten achter en kunnen ze niet op het Bitcoin-netwerk opereren.
Om het probleem van het integreren van compacte knooppunten in het netwerk op te lossen, wordt voorgesteld een extra klasse knooppunten te introduceren: bruggen. Een bridgenode is een compleet knooppunt waar ook de Utreexo-batterij en power-on proof voor wordt opgeslagen Alle UTXO uit UTXO-set. Bridges berekenen nieuwe hashes en werken de accumulator en bewijzen bij zodra er nieuwe transactieblokken arriveren. Het onderhouden en bijwerken van de accumulator en de proefdrukken legt geen extra rekenlast op dergelijke knooppunten. Bruggen offeren schijfruimte op: ze moeten dingen georganiseerd houden hashes, vergeleken met hashes voor compacte knooppunten, waarbij n de kracht van de UTXO-set is.
Netwerk architectuur
Bridges maken het mogelijk om geleidelijk compacte knooppunten aan het netwerk toe te voegen zonder de software van bestaande knooppunten te wijzigen. Volledige knooppunten werken zoals voorheen en verdelen transacties en blokken onderling. Bridge-nodes zijn volledige knooppunten die bovendien Utreexo-batterijgegevens en een reeks opnamebewijzen opslaan Alle UTXO voor nu. Het brugknooppunt adverteert zichzelf niet als zodanig en doet alsof het een volledig knooppunt is voor alle volledige knooppunten en een compact knooppunt voor alle compacte knooppunten. Hoewel bruggen beide netwerken met elkaar verbinden, hoeven ze ze eigenlijk maar in één richting te verbinden: van bestaande volledige knooppunten naar compacte knooppunten. Dit is mogelijk omdat het transactieformaat niet hoeft te worden gewijzigd en UTXO-bewijzen voor compacte knooppunten kunnen worden weggegooid, zodat elk compact knooppunt op dezelfde manier transacties naar alle netwerkdeelnemers kan uitzenden zonder de deelname van brugknooppunten.
Conclusie
We hebben naar de Utreexo-batterij gekeken en het prototype ervan in Rust geïmplementeerd. We hebben gekeken naar de netwerkarchitectuur die de integratie van op batterijen gebaseerde knooppunten mogelijk zal maken. Het voordeel van compacte vangsten is de grootte van de opgeslagen gegevens, die logaritmisch afhangt van de kracht van de set UTXO's, waardoor de vereisten voor schijfruimte en opslagprestaties voor dergelijke knooppunten aanzienlijk worden verminderd. Het nadeel is het extra knooppuntverkeer voor het verzenden van bewijzen, maar aggregatietechnieken voor bewijsmateriaal (wanneer één bewijs het bestaan van meerdere elementen bewijst) en caching kunnen helpen het verkeer binnen aanvaardbare grenzen te houden.
referenties:
- -
Bron: www.habr.com