Sveiki, Habr!
Bitcoin tinkle visi mazgai bendru sutarimu susitaria dėl UTXO rinkinio: kiek monetų galima išleisti, kam tiksliai ir kokiomis sąlygomis. UTXO rinkinys yra minimalus tikrinimo mazgui reikalingas duomenų rinkinys, be kurio mazgas negalės patikrinti gaunamų operacijų ir juos turinčių blokų teisingumo.
Šiuo atžvilgiu visais įmanomais būdais bandoma sumažinti saugomą šio rinkinio atvaizdavimą, suspausti neprarandant saugumo garantijų. Kuo mažesnis saugomų duomenų kiekis, tuo mažesnis vietos diske reikalingas tikrinimo mazgui, todėl tikrinimo mazgo paleidimas yra pigus, leidžia išplėsti tinklą ir taip padidinti tinklo stabilumą.
Šiame įraše paskelbsime naujausio bendraautorio pasiūlymo „Rust“ prototipą , - , kuris leidžia sumažinti vietos diske poreikį tikrinimo mazgams.
Kokia problema?
Viena iš nuolatinių Bitcoin problemų buvo jos mastelio keitimas. „Savo banko“ idėja reikalauja, kad tinklo dalyviai registruotų visas galimas lėšas. Bitcoin turimos lėšos išreiškiamos kaip nepanaudotų išėjimų rinkinys – UTXO rinkinys. Nors tai nėra ypač intuityvus vaizdavimas, jis yra naudingas diegimo našumui, palyginti su vaizdu, kuriame kiekviena „piniginė“ turi „balansą“ kaip atskirą įrašą, taip pat prideda privatumo (pvz., ).
Svarbu atskirti operacijų istoriją (vadinamą blokų grandine) ir dabartinę sistemos būseną. Bitcoin operacijų istorija šiuo metu užima apie 200 GB vietos diske ir toliau auga. Tačiau sistemos būsena yra daug mažesnė, maždaug 4 GB, ir atsižvelgiama tik į tai, kad kažkam šiuo metu priklauso monetos. Šių duomenų apimtis taip pat didėja laikui bėgant, tačiau daug lėčiau ir kartais net linkusi mažėti (žr. CDPV).
Lengvieji klientai (SPV) prekiauja saugumo garantijomis dėl galimybės saugoti jokios minimalios būsenos (UTXO rinkinio), išskyrus privačius raktus.
UTXO ir UTXO rinkinys
UTXO (nepanaudotų operacijų išvestis) yra nepanaudotų operacijų išvestis, kiekvienos operacijose perkelto Satoshi kelionės galutinis taškas. Nepanaudoti rezultatai tampa naujų operacijų įvestimis, todėl išleidžiami (išleidžiami) ir pašalinami iš UTXO rinkinio.
Nauji UTXO visada sukuriami atliekant operacijas:
- monetų bazės operacijos be įvesties: kurkite naujus UTXO, kai kalnakasiai išleidžia monetas
- reguliarios operacijos: sukurkite naujus UTXO išleisdami tam tikrą esamų UTXO rinkinį
Darbo su UTXO procesas:
Piniginės skaičiuoja išleistų monetų skaičių (likutį) pagal UTXO kiekį, kurį ši piniginė gali išleisti.
Kiekvienas tikrinimo mazgas turi stebėti rinkinį, kad būtų išvengta dvigubų išlaidų visi UTXO tikrinant kiekviena sandorius kiekvienas blokas.
Mazgas turi turėti logiką:
- UTXO rinkinio papildymai
- Ištrynimai iš UTXO rinkinio
- Tikrinama, ar rinkinyje yra vieno UTXO
Yra būdų, kaip sumažinti saugomos informacijos apie rinkinį reikalavimus, išlaikant galimybę pridėti ir pašalinti elementus, patikrinti ir įrodyti elemento egzistavimą rinkinyje naudojant .
Baterijos UTXO
Idėja naudoti baterijas keliems UTXO saugoti .
UTXO rinkinys yra sukurtas skrydžio metu, pradinio bloko atsisiuntimo (IBD) metu, išsaugomas visas ir visam laikui, o jo turinys keičiasi apdorojant operacijas iš kiekvieno naujo ir teisingo tinklo bloko. Šiam procesui reikia atsisiųsti maždaug 200 GB bloko duomenų ir patikrinti šimtus milijonų skaitmeninių parašų. Kai IBD procesas bus baigtas, UTXO rinkinys užims apie 4 GB.
Tačiau naudojant kaupiklius konsensuso taisyklės dėl fondų apsiriboja kriptografinių įrodymų tikrinimu ir generavimu, o turimų lėšų sekimo našta perkeliama tų lėšų savininkui, kuris pateikia jų egzistavimo ir nuosavybės įrodymus.
Akumuliatorius gali būti vadinamas kompaktišku rinkinio vaizdu. Išsaugoto atvaizdo dydis turi būti pastovus , arba padidės potiesiškai, atsižvelgiant į aibės kardinalumą ir paties elemento dydį, pvz. , kur n yra saugomos aibės kardinalumas.
Tokiu atveju akumuliatorius turėtų leisti generuoti elemento įtraukimo į rinkinį įrodymą (įtraukimo įrodymas) ir leisti efektyviai patikrinti šį įrodymą.
Baterija vadinama dinamiškas jei leidžia pridėti elementų ir pašalinti elementus iš rinkinio.
Tokios baterijos pavyzdys būtų . Toks akumuliatorius turi pastovų saugomo atvaizdavimo dydį, tačiau jam reikia bendra paslaptis (patikima sąranka). Šis reikalavimas paneigia tokio kaupiklio pritaikymą nepatikimiems tinklams, pvz., Bitcoin, nes duomenų nutekėjimas slapto generavimo metu gali leisti užpuolikams sukurti klaidingą UTXO egzistavimo įrodymą, apgaudinėjant mazgus su UTXO rinkiniu, pagrįstu tokiu akumuliatoriumi.
Utreexo
Thaddeus Dryja pasiūlytas Utreexo dizainas leidžia kurti dinaminis akumuliatorius be patikimas nustatymas.
Utreexo yra tobulo dvejetainio miškas ir yra pateiktų idėjų plėtojimas , pridedant galimybę pašalinti elementus iš rinkinio.
Baterijos loginė struktūra
Akumuliatoriaus elementai yra išdėstyti idealių dvinarių medžių miške. Medžiai suskirstyti pagal aukštį. Šis vaizdas buvo pasirinktas kaip vizualiausias ir leidžia vizualizuoti medžių susiliejimą atliekant operacijas su baterija.
Autorius pažymi, kad kadangi visi miško medžiai yra idealūs, jų aukštis išreiškiamas dviejų laipsniu, kaip ir bet kuris natūralusis skaičius gali būti pavaizduotas kaip dviejų galių suma. Atitinkamai bet koks lapų rinkinys gali būti sugrupuotas į dvejetainius medžius, ir visais atvejais norint pridėti naują elementą reikia žinių tik apie sandėliuojamų medžių šaknų mazgus.
Taigi, saugomas Utreexo akumuliatoriaus vaizdas yra šakninių mazgų sąrašas (Merkle šaknis), o ne visas medžių miškas.
Pavaizduokime šakninių elementų sąrašą kaip Vec<Option<Hash>>. Neprivalomas tipas Option<Hash> rodo, kad gali trūkti šaknies elemento, o tai reiškia, kad akumuliatoriuje nėra tinkamo aukščio medžio.
/// 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],
}
}
}Elementų pridėjimas
Pirmiausia apibūdinkime funkciją parent(), kuris atpažįsta dviejų nurodytų elementų pirminį mazgą.
tėvų() funkcija
Kadangi naudojame Merkle medžius, kiekvieno iš dviejų mazgų pirminis elementas yra vienas mazgas, kuriame saugoma antrinių mazgų maišos maišos vertė:
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[..])
}Autorius pažymi, kad siekiant užkirsti kelią Charleso Bouillaguet, Pierre'o-Alaino Fouque, Adi Shamiro ir Sebastieno Zimmerio aprašytiems išpuoliams.
, be dviejų maišų, aukštis medžio viduje taip pat turėtų būti pridėtas prie sujungimo.
Kai pridedate elementus į akumuliatorių, turite sekti, kurie šakniniai elementai yra pakeisti. Vykdydami kiekvieno pridėto elemento šakninių elementų keitimo kelią, vėliau galėsite sukurti šių elementų buvimo įrodymą.
Stebėkite pakeitimus, kai juos pridedate
Norėdami stebėti atliktus pakeitimus, deklaruokime struktūrą Update, kuriame bus saugomi duomenys apie mazgų pakeitimus.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Norėdami pridėti elementą prie akumuliatoriaus, jums reikia:
- Sukurkite šakninių elementų krepšelių masyvą
new_rootsir įdėkite esamus šakninius elementus, po vieną kiekvienam segmentui:
Kodas
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);
}- Pridėkite elementus, kuriuos norite pridėti (masyvas
insertions) į pirmąjį krepšelįnew_roots[0]:
Kodas
new_roots[0].extend_from_slice(insertions);- Sujunkite į pirmąjį krepšelį įdėtus elementus su likusiais:
- Visiems krepšeliams, kuriuose yra daugiau nei viena prekė:
- Paimkite du elementus iš krepšelio galo, apskaičiuokite jų pagrindinį elementą, pašalinkite abu elementus
- Įdėkite apskaičiuotą tėvą į kitą krepšelį
- Visiems krepšeliams, kuriuose yra daugiau nei viena prekė:
Kodas
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 });
}
}- Perkelkite šakninius elementus iš dėžučių į gautą kaupimo masyvą
Kodas
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]);
}
}Pridėtų elementų įrodymo kūrimas
elemento įtraukimo į bateriją įrodymas (Proof) tarnaus kaip Merkle kelias, sudarytas iš grandinės ProofStep. Jeigu kelias niekur neveda, vadinasi, įrodymas yra neteisingas.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Anksčiau gautos informacijos naudojimas pridedant elementą (struktūrą Update), galite sukurti įrodymą, kad elementas buvo pridėtas prie akumuliatoriaus. Norėdami tai padaryti, peržiūrime atliktų pakeitimų lentelę ir pridedame kiekvieną Merkle kelio žingsnį, kuris vėliau bus įrodymas:
Kodas
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
}
}Įrodinėjimo kūrimo procesas
Elemento įrodymo tikrinimas
Patikrinant elemento įtraukimo įrodymą, reikia sekti Merkle keliu, kol atveda prie esamo šakninio elemento:
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
}
}Vizualiai:
A įrodymų tikrinimo procesas
Elementų pašalinimas
Norėdami išimti elementą iš akumuliatoriaus, turite pateikti galiojančius įrodymus, kad elementas yra. Naudojant įrodymo duomenis, galima apskaičiuoti naujus kaupiklio šakninius elementus, kuriems pateiktas įrodymas nebebus teisingas.
Algoritmas yra toks:
- Kaip ir papildomai, mes organizuojame tuščių krepšelių rinkinį, atitinkantį Merkle medžius, kurių aukštis lygus dviejų galiai iš krepšelio indekso
- Į krepšelius dedame elementus iš Merklės tako laiptelių; krepšelio indeksas yra lygus dabartinio žingsnio skaičiui
- Pašaliname šakninį elementą, į kurį veda kelias iš įrodymo
- Kaip ir pridedant, apskaičiuojame naujus šaknies elementus, sujungdami elementus iš krepšelių poromis ir perkeldami jungimo rezultatą į kitą krepšelį
Kodas
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;
}
}Elemento "A" pašalinimo procesas:
Integracija į esamą tinklą
Naudodami siūlomą akumuliatorių, mazgai gali vengti naudoti DB, kad saugotų visus UTXO, tačiau vis tiek galės pakeisti UTXO rinkinį. Tačiau iškyla darbo su įrodymais problema.
Iškvieskime patvirtinimo mazgą, kuris naudoja UTXO akumuliatorių kompaktiška (kompaktiškos būsenos mazgas), o tikrintuvas be akumuliatoriaus yra baigta (visas mazgas). Dviejų klasių mazgų egzistavimas sukelia problemų juos integruoti į vieną tinklą, nes kompaktiškiems mazgams reikia įrodyti, kad yra UTXO, kurie išleidžiami atliekant operacijas, o pilni mazgai to nedaro. Jei visi tinklo mazgai vienu metu ir suderintai nepersijungs prie Utreexo, kompaktiški mazgai bus palikti ir negalės veikti Bitcoin tinkle.
Norint išspręsti kompaktiškų mazgų integravimo į tinklą problemą, siūloma įvesti papildomą mazgų klasę - tiltų. Tilto mazgas yra visas mazgas, kuriame taip pat saugoma „Utreexo“ baterija ir įjungimo įrodymas visi UTXO iš UTXO rinkinio. Tiltai apskaičiuoja naujas maišas ir atnaujina kaupiklį bei įrodymus, kai gaunami nauji operacijų blokai. Akumuliatoriaus ir patikrinimų priežiūra ir atnaujinimas nesukelia papildomos skaičiavimo apkrovos tokiems mazgams. Tiltai aukoja vietos diske: reikia viską tvarkyti maišos, palyginti su kompaktiškų mazgų maišos, kur n yra UTXO rinkinio galia.
Tinklo architektūra
Tiltai leidžia palaipsniui pridėti kompaktiškus mazgus į tinklą, nekeičiant esamų mazgų programinės įrangos. Visi mazgai veikia kaip anksčiau, paskirstydami operacijas ir blokus tarpusavyje. Tilto mazgai yra pilni mazgai, kuriuose papildomai saugomi „Utreexo“ akumuliatoriaus duomenys ir įtraukimo įrodymų rinkinys visi UTXO kol kas. Tilto mazgas nesiskelbia kaip toks, apsimesdamas visu pilnu mazgu ir kompaktišku mazgu visiems kompaktiškiems. Nors tiltai jungia abu tinklus, iš tikrųjų juos reikia sujungti tik viena kryptimi: nuo esamų pilnų mazgų iki kompaktiškų mazgų. Tai įmanoma, nes operacijos formato keisti nereikia, o kompaktiškų mazgų UTXO įrodymus galima atmesti, todėl bet kuris kompaktiškas mazgas gali panašiai transliuoti operacijas visiems tinklo dalyviams, nedalyvaujant tiltiniams mazgams.
išvada
Pažiūrėjome į „Utreexo“ bateriją ir įdiegėme jos prototipą „Rust“. Mes pažvelgėme į tinklo architektūrą, kuri leis integruoti akumuliatoriaus mazgus. Kompaktiškų gaudyklių pranašumas yra saugomų duomenų dydis, logaritmiškai priklausantis nuo UTXO rinkinio galios, o tai labai sumažina tokių mazgų vietos diske ir saugojimo našumo reikalavimus. Trūkumas yra papildomas mazgo srautas perduodant įrodymus, tačiau įrodymų sujungimo būdai (kai vienas įrodymas įrodo kelių elementų egzistavimą) ir talpyklos kaupimas gali padėti išlaikyti srautą priimtinose ribose.
Nuorodos:
- -
Šaltinis: www.habr.com