Эй Хабр!
Bitcoin желісінде барлық түйіндер консенсус арқылы UTXO жиынтығына келіседі: қанша монета жұмсауға болады, нақты кімге және қандай жағдайларда. UTXO жиыны – валидатор түйіні үшін қажетті деректердің ең аз жинағы, онсыз түйін кіріс транзакцияларының және оларды қамтитын блоктардың жарамдылығын тексере алмайды.
Осыған байланысты, осы жинақтың сақталған көрінісін азайтуға, қауіпсіздік кепілдіктерін жоғалтпай оны қысуға барлық мүмкін әрекеттер жасалуда. Сақталған деректердің көлемі неғұрлым аз болса, валидатор түйінінің дискілік кеңістік талаптары соғұрлым төмен болады, бұл валидатор түйінін іске қосуды арзан етеді, желіні кеңейтуге және сол арқылы желінің тұрақтылығын арттыруға мүмкіндік береді.
Бұл постта біз бірлескен автордың жақында жасалған ұсынысының Rust прототипін орналастырамыз , - , бұл валидатор түйіндері үшін дискілік кеңістік талаптарын азайтуға мүмкіндік береді.
Мәселе неде?
Биткоиннің көпжылдық мәселелерінің бірі оның ауқымдылығы болды. «Өз банкіңіз» идеясы желі қатысушыларынан пайдалануға болатын барлық қаражаттың есебін жүргізуді талап етеді. Биткоинде қол жетімді қаражат жұмсалмаған шығыстардың жиынтығы ретінде көрсетіледі - UTXO жиынтығы. Бұл әсіресе интуитивті көрініс болмаса да, әрбір «әмиянның» жеке жазба ретінде «баланс» бар және сонымен бірге құпиялылықты қосатын көрініске қарағанда орындау өнімділігі тұрғысынан тиімді (мысалы, ).
Транзакциялар тарихын (блокчейн деп аталатын) және жүйенің ағымдағы күйін ажырата білу маңызды. Биткоин транзакцияларының тарихы қазіргі уақытта шамамен 200 ГБ дискілік кеңістікті алып жатыр және өсуде. Дегенмен, жүйе күйі әлдеқайда аз, 4 ГБ тәртібі бойынша және тек біреудің қазіргі уақытта монеталарға ие екендігін ескереді. Бұл деректердің көлемі де уақыт өте келе артады, бірақ әлдеқайда баяу қарқынмен және кейде тіпті азаюға бейім (CDPV қараңыз).
Жеңіл клиенттер (SPV) жеке кілттерден басқа минималды күйді (UTXO жиынын) сақтау мүмкіндігінің қауіпсіздік кепілдіктерін сатады.
UTXO және UTXO жиынтығы
UTXO (Isspent Transaction Output) – транзакцияда аударылған әрбір Сатоши сапарының соңғы нүктесі, жұмсалмаған транзакция нәтижесі. Игерілмеген шығыстар жаңа транзакциялардың кірістеріне айналады және осылайша жұмсалады (жұмсалады) және UTXO жиынынан жойылады.
Жаңа UTXO әрқашан транзакциялар арқылы жасалады:
- кірістерсіз coinbase транзакциялары: кеншілер монеталарды шығарған кезде жаңа UTXO жасаңыз
- тұрақты транзакциялар: бар UTXO-лардың белгілі бір жинағын жұмсай отырып, жаңа UTXO жасаңыз
UTXO-мен жұмыс істеу процесі:
Әмияндар жұмсауға болатын тиындар санын (баланс) осы әмиянға жұмсауға болатын UTXO сомасына қарай санайды.
Әрбір валидатор түйіні екі рет жұмсау әрекеттерін болдырмау үшін жиынды бақылауы керек всех Тексеру кезінде UTXO әрқайсысы транзакциялар әрқайсысының блок.
Түйіннің логикасы болуы керек:
- UTXO жиынына толықтырулар
- UTXO жиынынан жоюлар
- Жинақта жалғыз UTXO бар-жоғын тексеру
Элементтерді қосу және жою, жиынтықта элементтің бар екенін тексеру және дәлелдеу мүмкіндігін сақтай отырып, жиын туралы сақталған ақпаратқа қойылатын талаптарды азайту жолдары бар. .
UTXO үшін батареялар
Бірнеше UTXO сақтау үшін батареяларды пайдалану идеясы .
UTXO-жиынтығы бастапқы блокты жүктеу (IBD) кезінде толық және тұрақты сақталады, ал оның мазмұны желінің әрбір жаңа және дұрыс блогынан транзакцияларды өңдеуден кейін өзгереді. Бұл процесс шамамен 200 ГБ блоктық деректерді жүктеп алуды және жүздеген миллион цифрлық қолтаңбаларды тексеруді қажет етеді. IBD процесі аяқталғаннан кейін, UTXO жинағы шамамен 4 ГБ алады.
Дегенмен, аккумуляторлармен қорларға қатысты консенсус ережелері криптографиялық дәлелдемелерді тексеруге және генерациялауға дейін азаяды, ал қолда бар қаражатты қадағалау ауыртпалығы олардың бар екендігі мен иелігін дәлелдейтін сол қорлардың иесіне жүктеледі.
Аккумуляторды жиынның ықшам көрінісі деп атауға болады. Сақталған көріністің өлшемі не тұрақты болуы керек , немесе жиынның түбегейлілігіне және элементтің өлшеміне қатысты ішкі сызықтық өсу, мысалы , мұндағы n – сақталған жиынның негізгілігі.
Бұл жағдайда жинақтаушы элементтің жиынтыққа қосылуының дәлелдемесін (қосу дәлелі) генерациялауға және осы дәлелдемені тиімді тексеруге мүмкіндік беруі керек.
Батарея деп аталады динамикалық егер элементтерді қосуға және жиыннан элементтерді жоюға мүмкіндік береді.
Мұндай батареяның мысалы болуы мүмкін . Мұндай аккумулятор сақталған өкілдіктің тұрақты өлшеміне ие, бірақ болуын талап етеді ортақ құпия (сенімді орнату). Бұл талап мұндай аккумулятордың биткоин сияқты сенімсіз желілер үшін қолданылуын жоққа шығарады, өйткені құпия генерация кезінде деректердің ағып кетуі шабуылдаушыларға осындай аккумулятор негізінде UTXO жиынтығы бар түйіндерді алдап, UTXO бар екендігінің жалған дәлелдерін жасауға мүмкіндік береді.
Utreexo
Thaddeus Dryja ұсынған Utreexo дизайны жасауға мүмкіндік береді динамикалық аккумулятор жоқ сенімді орнату.
Utreexo - тамаша бинарлы орман және ұсынылған идеялардың дамуы болып табылады , жиыннан элементтерді жою мүмкіндігін қосу.
Батареяның логикалық құрылымы
Батарея ұяшықтары тамаша екілік ағаштар орманында орналасқан. Ағаштар биіктікке қарай реттелген. Бұл көрініс ең көрнекі болып таңдалды және батареядағы операциялар кезінде ағаштардың біріктірілуін визуализациялауға мүмкіндік береді.
Автор ормандағы барлық ағаштар идеалды болғандықтан, олардың биіктігі де екінің дәрежесімен өрнектелетінін, кез келген натурал санды екінің дәрежелерінің қосындысы ретінде беруге болатынын атап көрсетеді. Тиісінше, жапырақтардың кез келген жиынтығын екілік ағаштарға топтастыруға болады және барлық жағдайларда жаңа элементті қосу білімді талап етеді. тек сақталған ағаштардың түбірлік түйіндері туралы.
Осылайша, Utreexo аккумуляторының сақталған көрінісі түбірлік түйіндердің тізімі (Merkle түбірі), және бүкіл ағаш орманы емес.
Түбір элементтердің тізімін ретінде көрсетейік Vec<Option<Hash>>. Қосымша түрі Option<Hash> түбір элементінің жоқ болуы мүмкін екенін көрсетеді, яғни аккумуляторда сәйкес биіктіктегі ағаш жоқ.
/// 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],
}
}
}Элементтерді қосу
Алдымен функцияны сипаттайық parent(), ол берілген екі элемент үшін негізгі түйінді таниды.
parent() функциясы
Біз Merkle ағаштарын пайдаланатындықтан, екі түйіннің әрқайсысының ата-анасы еншілес түйіндердің хэштерін біріктіру хэшін сақтайтын бір түйін болып табылады:
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[..])
}Автор Шарль Бульяге, Пьер-Ален Фуке, Ади Шамир және Себастьян Циммер сипаттаған шабуылдардың алдын алу үшін
, екі хэштен басқа, ағаштың ішіндегі биіктікті де біріктіруге қосу керек.
Аккумуляторға элементтерді қосқанда, қандай түбір элементтері өзгертілгенін қадағалау керек. Әрбір қосылған элемент үшін түбір элементтерін өзгерту жолын орындау арқылы кейінірек осы элементтердің бар екендігін дәлелдеуге болады.
Өзгерістерді қосқан кезде оларды қадағалаңыз
Жасалған өзгерістерді қадағалау үшін құрылымды жариялайық Update, ол түйін өзгерістері туралы деректерді сақтайды.
#[derive(Debug)]
pub struct Update<'a> {
pub utreexo: &'a mut Utreexo,
// ProofStep хранит "соседа" элемента и его положение
pub updated: HashMap<Hash, ProofStep>,
}Батареяға элемент қосу үшін сізге қажет:
- Түбір элементтерінің себеттерінің массивін жасаңыз
new_rootsжәне бар түбір элементтерін әр шелек үшін бір-бірден орналастырыңыз:
код
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);
}- Қосылатын элементтерді қосыңыз (массив
insertions) бірінші арбағаnew_roots[0]:
код
new_roots[0].extend_from_slice(insertions);- Бірінші себетке қосылған заттарды қалғандарымен біріктіріңіз:
- Бірден көп элементі бар барлық арбалар үшін:
- Себеттің соңынан екі элементті алыңыз, олардың ата-анасын есептеңіз, екі элементті де алып тастаңыз
- Есептелген ата-ананы келесі себетке қосыңыз
- Бірден көп элементі бар барлық арбалар үшін:
код
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 });
}
}- Түбір элементтерін қалталардан алынған жинақтаушы массивіне жылжытыңыз
код
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]);
}
}Қосылған элементтерге дәлел жасау
Батареядағы ұяшықты қосудың дәлелі (Proof) тізбектен тұратын Меркле жолы ретінде қызмет етеді ProofStep. Егер жол ешқайда апармаса, онда дәлел дұрыс емес.
/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}Элементті қосу кезінде бұрын алынған ақпаратты пайдалану (құрылым Update), элементтің батареяға қосылғанын дәлелдей аласыз. Мұны істеу үшін біз енгізілген өзгерістер кестесінен өтіп, әрбір қадамды Меркле жолына қосамыз, ол кейінірек дәлел болады:
код
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
}
}Дәлелдеуді құру процесі
Элемент үшін дәлелді тексеру
Элементтің қосылу дәлелін тексеру бар түбір элементіне әкелгенше Merkle жолын орындауға дейін төмендейді:
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
}
}Көрнекі түрде:
А үшін дәлелдемелерді тексеру процесі
Элементтерді жою
Батареядан ұяшықты алып тастау үшін ұяшықтың бар екенін растайтын дәлелді көрсету керек. Дәлелдеу деректерін пайдалана отырып, берілген дәлел енді ақиқат болмайтын аккумулятордың жаңа түбір элементтерін есептеуге болады.
Алгоритм келесідей:
- Қосымша сияқты, біз себет индексінен биіктігі екінің қуатына тең Merkle ағаштарына сәйкес бос себеттер жинағын ұйымдастырамыз.
- Біз Merkle жолының қадамдарынан элементтерді себеттерге саламыз; себет индексі ағымдағы қадамның санына тең
- Біз дәлелдеу жолы апаратын түбір элементін алып тастаймыз
- Қосу сияқты, біз жаңа түбір элементтерін себеттердегі элементтерді жұппен біріктіру және біріктіру нәтижесін келесі себетке жылжыту арқылы есептейміз.
код
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;
}
}«А» элементін жою процесі:
Қолданыстағы желіге интеграция
Ұсынылған аккумуляторды пайдалану арқылы түйіндер UTXO жиынын өзгерте отырып, барлық UTXO файлдарын сақтау үшін ДБ пайдаланудан аулақ болады. Дегенмен, дәлелдермен жұмыс істеу мәселесі туындайды.
UTXO аккумуляторын пайдаланатын валидатор түйінін шақырайық ықшам (ықшам күй түйіні) және аккумуляторсыз валидатор болып табылады аяқталды (толық түйін). Түйіндердің екі класының болуы оларды бір желіге біріктіру мәселесін тудырады, өйткені ықшам түйіндер транзакцияларға жұмсалатын UTXO бар екендігін дәлелдеуді талап етеді, ал толық түйіндер бұл қажет емес. Егер барлық желі түйіндері бір уақытта және үйлестірілген түрде Utreexo-ны пайдалануға ауыспаса, онда ықшам түйіндер артта қалады және Bitcoin желісінде жұмыс істей алмайды.
Шағын түйіндерді желіге біріктіру мәселесін шешу үшін түйіндердің қосымша класын енгізу ұсынылады - көпірлер. Көпір түйіні - бұл Utreexo батареясын және қосулылығын растайтын толық түйін всех UTXO жиынтығынан UTXO. Көпірлер жаңа хэштерді есептейді және транзакциялардың жаңа блоктары келгенде аккумулятор мен дәлелдемелерді жаңартады. Аккумуляторды және дәлелдемелерді күтіп ұстау және жаңарту мұндай түйіндерге қосымша есептеу жүктемесін түсірмейді. Көпірлер дискілік кеңістікті құрбан етеді: заттарды ретке келтіру қажет салыстырғанда хэштер ықшам түйіндерге арналған хэштер, мұндағы n - UTXO жиынының қуаты.
Желінің архитектурасы
Көпірлер бар түйіндердің бағдарламалық жасақтамасын өзгертпестен желіге ықшам түйіндерді біртіндеп қосуға мүмкіндік береді. Толық түйіндер бұрынғыдай жұмыс істейді, транзакциялар мен блоктарды бір-біріне таратады. Көпір түйіндері - бұл Utreexo батареясының деректерін және қосу дәлелдерінің жиынтығын қосымша сақтайтын толық түйіндер. всех Әзірге UTXO. Көпір түйіні өзін барлық толық түйіндер үшін толық түйін және барлық ықшам түйіндер үшін ықшам түйін ретінде көрсетіп, өзін жарнамаламайды. Көпірлер екі желіні де біріктірсе де, оларды тек бір бағытта қосу керек: бар толық түйіндерден ықшам түйіндерге дейін. Бұл мүмкін, себебі транзакция пішімін өзгерту қажет емес және ықшам түйіндерге арналған UTXO дәлелдемелерін алып тастауға болады, сондықтан кез келген ықшам түйін көпір түйіндерінің қатысуынсыз транзакцияларды барлық желі қатысушыларына бірдей тарата алады.
қорытынды
Біз Utreexo аккумуляторын қарап, оның прототипін Rust-те іске асырдық. Біз батареяға негізделген түйіндерді біріктіруге мүмкіндік беретін желі архитектурасын қарастырдық. Ықшам ұстаудың артықшылығы сақталған деректердің өлшемі болып табылады, ол логарифмдік түрде UTXO жиынтығының қуатына тәуелді, бұл дискілік кеңістікке және мұндай түйіндер үшін сақтау өнімділігіне қойылатын талаптарды айтарлықтай төмендетеді. Кемшілігі дәлелдемелерді жіберуге арналған қосымша түйін трафигі болып табылады, бірақ дәлелдемелерді біріктіру әдістері (бір дәлел бірнеше элементтердің бар екенін дәлелдегенде) және кэштеу трафикті қолайлы шектерде ұстауға көмектеседі.
сілтемелер:
- -
Ақпарат көзі: www.habr.com