Utreexo៖ បង្រួម UTXO Bitcoin ជាច្រើន។

ហេហេ!

នៅក្នុងបណ្តាញ Bitcoin ថ្នាំងទាំងអស់ តាមរយៈការមូលមតិគ្នា យល់ព្រមលើសំណុំនៃ UTXOs: តើមានកាក់ប៉ុន្មានសម្រាប់ចំណាយ អ្នកណាពិតប្រាកដ និងនៅក្រោមលក្ខខណ្ឌអ្វី។ សំណុំ UTXO គឺជាសំណុំទិន្នន័យអប្បបរមាដែលត្រូវការសម្រាប់ថ្នាំងដែលមានសុពលភាព ដោយគ្មានថ្នាំងនឹងមិនអាចផ្ទៀងផ្ទាត់សុពលភាពនៃប្រតិបត្តិការចូល និងប្លុកដែលមានពួកវាបានទេ។

ក្នុងន័យនេះ ការព្យាយាមកំពុងត្រូវបានធ្វើឡើងតាមគ្រប់មធ្យោបាយដែលអាចធ្វើទៅបាន ដើម្បីកាត់បន្ថយតំណាងដែលបានរក្សាទុកនៃឈុតនេះ ដើម្បីបង្រួមវាដោយមិនបាត់បង់ការធានាសុវត្ថិភាព។ ទំហំទិន្នន័យដែលបានរក្សាទុកកាន់តែតូច តម្រូវការទំហំថាសរបស់ថ្នាំងសុពលភាពកាន់តែទាប ដែលធ្វើឲ្យការបើកដំណើរការថ្នាំងសុពលភាពមានតម្លៃថោក អនុញ្ញាតឱ្យអ្នកពង្រីកបណ្តាញ និងបង្កើនស្ថេរភាពនៃបណ្តាញ។

នៅក្នុងការបង្ហោះនេះ យើងនឹងបង្ហោះគំរូ Rust នៃសំណើថ្មីៗពីសហអ្នកនិពន្ធ ក្រដាសបណ្តាញរន្ទះ, ថាដឌឺស រីយ៉ា - Utreexo៖ ឧបករណ៍ប្រមូលផ្តុំដែលមានមូលដ្ឋានលើសញ្ញាថាមវន្តដែលត្រូវបានធ្វើឱ្យប្រសើរសម្រាប់សំណុំ Bitcoin UTXOដែលអនុញ្ញាតឱ្យកាត់បន្ថយតម្រូវការទំហំថាសសម្រាប់ថ្នាំងសុពលភាព។

មាន​បញ្ហា​អ្វី?

បញ្ហាមួយក្នុងចំណោមបញ្ហាដែលមានអាយុច្រើនឆ្នាំរបស់ Bitcoin គឺលទ្ធភាពធ្វើមាត្រដ្ឋានរបស់វា។ គំនិតនៃ "ធនាគារផ្ទាល់ខ្លួនរបស់អ្នក" តម្រូវឱ្យអ្នកចូលរួមបណ្តាញរក្សាកំណត់ត្រានៃមូលនិធិទាំងអស់ដែលមានសម្រាប់ប្រើប្រាស់។ នៅក្នុង Bitcoin មូលនិធិដែលមានត្រូវបានបង្ហាញជាសំណុំនៃលទ្ធផលដែលមិនបានចំណាយ - សំណុំ UTXO ។ ខណៈពេលដែលនេះមិនមែនជាតំណាងដ៏វិចារណញាណពិសេសនោះទេ វាមានអត្ថប្រយោជន៍នៅក្នុងលក្ខខណ្ឌនៃការអនុវត្តលើតំណាងដែល "កាបូប" នីមួយៗមាន "សមតុល្យ" ជាធាតុដាច់ដោយឡែក ហើយថែមទាំងបន្ថែមភាពឯកជន (ឧ. កាក់ចូលរួម).

វាមានសារៈសំខាន់ណាស់ក្នុងការបែងចែករវាងប្រវត្តិនៃប្រតិបត្តិការ (អ្វីដែលគេហៅថា blockchain) និងស្ថានភាពបច្ចុប្បន្ននៃប្រព័ន្ធ។ ប្រវត្តិប្រតិបត្តិការ Bitcoin បច្ចុប្បន្នត្រូវការទំហំថាសប្រហែល 200 GB ហើយបន្តកើនឡើង។ ទោះជាយ៉ាងណាក៏ដោយ ស្ថានភាពប្រព័ន្ធគឺតូចជាងនេះ ទៅតាមលំដាប់នៃទំហំ 4 GB ហើយគ្រាន់តែគិតគូរពីការពិតដែលថាបច្ចុប្បន្នមាននរណាម្នាក់ជាម្ចាស់កាក់ប៉ុណ្ណោះ។ បរិមាណនៃទិន្នន័យនេះក៏កើនឡើងតាមពេលវេលាដែរ ប៉ុន្តែក្នុងអត្រាយឺតជាង ហើយជួនកាលថែមទាំងមាននិន្នាការថយចុះ (សូមមើល CDPV)។

ការធានាសុវត្ថិភាពពាណិជ្ជកម្មរបស់អតិថិជនពន្លឺ (SPVs) សម្រាប់លទ្ធភាពរក្សាទុកគ្មានរដ្ឋអប្បបរមា (UTXO-set) ក្រៅពីសោឯកជន។

UTXO និង UTXO-កំណត់

UTXO (Unspent Transaction Output) គឺជាលទ្ធផលប្រតិបត្តិការដែលមិនបានចំណាយ ដែលជាចំណុចបញ្ចប់នៃដំណើររបស់ Satoshi នីមួយៗដែលបានផ្ទេរក្នុងប្រតិបត្តិការ។ លទ្ធផលដែលមិនបានចំណាយក្លាយជាធាតុបញ្ចូលនៃប្រតិបត្តិការថ្មី ហើយដូច្នេះត្រូវបានចំណាយ (ចំណាយ) និងដកចេញពី UTXO-set ។

UTXO ថ្មីតែងតែត្រូវបានបង្កើតឡើងដោយប្រតិបត្តិការ៖

• ប្រតិបត្តិការ coinbase ដោយគ្មានធាតុបញ្ចូល៖ បង្កើត UTXO ថ្មីនៅពេលអ្នករុករករ៉ែចេញកាក់
• ប្រតិបត្តិការទៀងទាត់៖ បង្កើត UTXO ថ្មីខណៈពេលដែលចំណាយលើសំណុំជាក់លាក់នៃ UTXO ដែលមានស្រាប់

ដំណើរការនៃការធ្វើការជាមួយ UTXO៖

កាបូបរាប់ចំនួនកាក់ដែលមានសម្រាប់ចំណាយ (សមតុល្យ) ដោយផ្អែកលើចំនួន UTXO ដែលមាននៅក្នុងកាបូបនេះសម្រាប់ការចំណាយ។

ថ្នាំងដែលមានសុពលភាពនីមួយៗ ដើម្បីការពារការប៉ុនប៉ងចំណាយពីរដង ត្រូវតែត្រួតពិនិត្យសំណុំ всех UTXO ពេលពិនិត្យ គ្នា ប្រតិបត្តិការ នៃគ្នា ប្លុក។

ថ្នាំងត្រូវតែមានតក្កវិជ្ជា៖

• ការបន្ថែមទៅ UTXO-set
• ការលុបចេញពី UTXO-set
• ការពិនិត្យមើលវត្តមានរបស់ UTXO តែមួយនៅក្នុងសំណុំមួយ។

មានវិធីដើម្បីកាត់បន្ថយតម្រូវការសម្រាប់ព័ត៌មានដែលបានរក្សាទុកអំពីសំណុំ ខណៈពេលដែលរក្សាបាននូវសមត្ថភាពក្នុងការបន្ថែម និងលុបធាតុ ពិនិត្យមើល និងបញ្ជាក់អំពីអត្ថិភាពនៃធាតុនៅក្នុងសំណុំដោយប្រើ ឧបករណ៍បំលែងគ្រីប.

ថ្មសម្រាប់ UTXO

គំនិតនៃការប្រើប្រាស់ថ្មដើម្បីរក្សាទុក UTXOs ច្រើន។ ត្រូវបានពិភាក្សា មុននេះ.

UTXO-set ត្រូវបានបង្កើតឡើងភ្លាមៗ កំឡុងពេលទាញយកប្លុកដំបូង (IBD) ដែលត្រូវបានរក្សាទុកពេញ និងជាអចិន្ត្រៃយ៍ ខណៈពេលដែលមាតិការបស់វាផ្លាស់ប្តូរបន្ទាប់ពីដំណើរការប្រតិបត្តិការពីប្លុកថ្មី និងត្រឹមត្រូវនៃបណ្តាញនីមួយៗ។ ដំណើរការនេះតម្រូវឱ្យទាញយកទិន្នន័យប្លុកប្រហែល 200 GB និងផ្ទៀងផ្ទាត់ហត្ថលេខាឌីជីថលរាប់រយលាន។ បន្ទាប់ពីដំណើរការ IBD ត្រូវបានបញ្ចប់ ចំនុចសំខាន់គឺថា UTXO-set នឹងកាន់កាប់ប្រហែល 4 GB ។

ទោះបីជាយ៉ាងណាក៏ដោយ ជាមួយនឹងអ្នកប្រមូលប្រាក់ ច្បាប់នៃការមូលមតិគ្នាសម្រាប់មូលនិធិត្រូវបានកាត់បន្ថយទៅជាការផ្ទៀងផ្ទាត់ និងការបង្កើតភស្តុតាងគ្រីបគ្រីប ហើយបន្ទុកនៃការតាមដានមូលនិធិដែលមានគឺត្រូវប្តូរទៅម្ចាស់មូលនិធិទាំងនោះ ដែលផ្តល់ភស្តុតាងនៃអត្ថិភាព និងភាពជាម្ចាស់របស់ពួកគេ។

accumulator អាចត្រូវបានគេហៅថាតំណាងបង្រួមនៃសំណុំមួយ។ ទំហំនៃតំណាងដែលបានរក្សាទុកត្រូវតែជាចំនួនថេរ ឬបង្កើន sublinearly ទាក់ទងទៅនឹង cardinality នៃសំណុំ និងទំហំនៃធាតុខ្លួនវា ឧទាហរណ៍ ដែលជាកន្លែងដែល n គឺជា cardinality នៃសំណុំដែលបានរក្សាទុក។

ក្នុងករណីនេះ អ្នកប្រមូលផ្តុំគួរតែអនុញ្ញាតឱ្យបង្កើតភស្តុតាងនៃការរួមបញ្ចូលធាតុនៅក្នុងសំណុំ (ភស្តុតាងរួមបញ្ចូល) និងធ្វើឱ្យវាអាចធ្វើទៅបានដើម្បីផ្ទៀងផ្ទាត់ភស្តុតាងនេះប្រកបដោយប្រសិទ្ធភាព។

ថ្មត្រូវបានគេហៅថា ថាមវន្ត ប្រសិនបើអនុញ្ញាតឱ្យអ្នកបន្ថែមធាតុ និងយកធាតុចេញពីសំណុំ។

ឧទាហរណ៍នៃថ្មបែបនេះនឹងមាន RSA accumulator ស្នើឡើងដោយ Boneh, Bunz, Fisch ក្នុងខែធ្នូ ឆ្នាំ 2018. ឧបករណ៍ផ្ទុកបែបនេះមានទំហំថេរនៃការតំណាងដែលត្រូវបានរក្សាទុកប៉ុន្តែតម្រូវឱ្យមានវត្តមាន សម្ងាត់ចែករំលែក (ការដំឡើងដែលអាចទុកចិត្តបាន) ។ តម្រូវការនេះបដិសេធការអនុវត្តរបស់ឧបករណ៍ប្រមូលផ្តុំសម្រាប់បណ្តាញដែលមិនគួរឱ្យទុកចិត្តដូចជា Bitcoin ចាប់តាំងពីការលេចធ្លាយទិន្នន័យកំឡុងពេលបង្កើតសម្ងាត់អាចឱ្យអ្នកវាយប្រហារបង្កើតភស្តុតាងមិនពិតនៃអត្ថិភាពនៃ UTXO ដែលបញ្ឆោតថ្នាំងដោយប្រើ UTXO-set ដោយផ្អែកលើឧបករណ៍ប្រមូលផ្តុំបែបនេះ។

Utreexo

ការរចនា Utreexo ដែលស្នើឡើងដោយ Thaddeus Dryja ធ្វើឱ្យវាអាចបង្កើតបាន។ ថាមវន្ត аккумулятор ដោយគ្មាន ការដំឡើងដែលអាចទុកចិត្តបាន។

Utreexo គឺជាព្រៃនៃគោលពីរដ៏ល្អឥតខ្ចោះ ដើមឈើ Merkle និងជាការអភិវឌ្ឍន៍នៃគំនិតដែលបានបង្ហាញនៅក្នុង ឧបករណ៍ផ្ទុកអសមកាលប្រកបដោយប្រសិទ្ធភាពសម្រាប់ pki ចែកចាយបន្ថែមសមត្ថភាពក្នុងការយកធាតុចេញពីសំណុំ។

រចនាសម្ព័ន្ធឡូជីខលនៃថ្ម

កោសិកាថ្មត្រូវបានរៀបចំនៅក្នុងព្រៃនៃដើមឈើគោលពីរដ៏ល្អ។ ដើមឈើត្រូវបានតម្រៀបតាមកម្ពស់។ ការតំណាងនេះត្រូវបានជ្រើសរើសជារូបភាពដែលមើលឃើញបំផុត និងអនុញ្ញាតឱ្យអ្នកមើលឃើញការបញ្ចូលគ្នានៃដើមឈើអំឡុងពេលប្រតិបត្តិការលើថ្ម។

អ្នកនិពន្ធបានកត់សម្គាល់ថា ដោយសារដើមឈើទាំងអស់នៅក្នុងព្រៃមានលក្ខណៈល្អ កម្ពស់របស់វាត្រូវបានបង្ហាញថាជាអំណាចនៃពីរ ដូចគ្នានឹងចំនួនធម្មជាតិណាមួយអាចត្រូវបានតំណាងថាជាផលបូកនៃអំណាចពីរ។ ដូច្នោះហើយ ស្លឹកឈើណាមួយអាចត្រូវបានដាក់ជាក្រុមទៅជាដើមឈើគោលពីរ ហើយក្នុងគ្រប់ករណីទាំងអស់ ការបន្ថែមធាតុថ្មីទាមទារចំណេះដឹង តែអំពីថ្នាំងឫសនៃដើមឈើដែលរក្សាទុក.

ដូច្នេះតំណាងដែលបានរក្សាទុកនៃ Utreexo accumulator គឺជាបញ្ជីនៃថ្នាំងឫស (Merkle root) ។ ហើយមិនមែនព្រៃឈើទាំងមូលទេ។.

ចូរតំណាងឱ្យបញ្ជីនៃធាតុដើមជា Vec<Option<Hash>>. ប្រភេទស្រេចចិត្ត Option<Hash> បង្ហាញថាធាតុឫសអាចបាត់ ដែលមានន័យថាមិនមានមែកធាងដែលមានកម្ពស់សមរម្យនៅក្នុង accumulator ទេ។

/// 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[..])
}

អ្នកនិពន្ធកត់សម្គាល់ថាដើម្បីការពារការវាយប្រហារដែលបានពិពណ៌នាដោយ Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir និង Sebastien Zimmer នៅក្នុង
ការ​វាយ​ប្រហារ​ជា​លើក​ទី​ពីរ​នៅ​លើ​មុខងារ hash ដែល​ខូចបន្ថែមពីលើសញ្ញាទាំងពីរ កម្ពស់ខាងក្នុងដើមឈើក៏គួរតែត្រូវបានបន្ថែមទៅការភ្ជាប់គ្នា។

នៅពេលអ្នកបន្ថែមធាតុទៅ accumulator អ្នកត្រូវតាមដានថាតើធាតុឫសណាមួយត្រូវបានផ្លាស់ប្តូរ។ ដោយធ្វើតាមផ្លូវនៃការផ្លាស់ប្តូរធាតុ root សម្រាប់ធាតុនីមួយៗដែលអ្នកបន្ថែម អ្នកអាចបង្កើតភស្តុតាងនៃវត្តមានរបស់ធាតុទាំងនេះនៅពេលក្រោយ។

តាមដានការផ្លាស់ប្តូរនៅពេលអ្នកបន្ថែមវា។

ដើម្បីតាមដានការផ្លាស់ប្តូរដែលបានធ្វើ ចូរយើងប្រកាសអំពីរចនាសម្ព័ន្ធ 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);

• បង្រួបបង្រួមធាតុដែលបានបន្ថែមទៅកន្ត្រកដំបូងជាមួយនៅសល់៖
  • សម្រាប់រទេះទាំងអស់ដែលមានធាតុច្រើនជាងមួយ៖
    1. យកធាតុពីរពីចុងកន្ត្រក គណនាមេរបស់វា យកធាតុទាំងពីរចេញ
    2. បន្ថែមមេដែលបានគណនាទៅរទេះបន្ទាប់

លេខកូដ

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 });
    }
}

• ផ្លាស់ទីធាតុ root ពីធុងសំរាមទៅអារេ accumulator លទ្ធផល

លេខកូដ

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) នឹងបម្រើជាផ្លូវ Merkle ដែលមានខ្សែសង្វាក់ 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) អ្នកអាចបង្កើតភស្តុតាងដែលថាធាតុមួយត្រូវបានបន្ថែមទៅក្នុងថ្ម។ ដើម្បីធ្វើដូច្នេះ យើងឆ្លងកាត់តារាងនៃការផ្លាស់ប្តូរដែលបានធ្វើ ហើយបន្ថែមជំហាននីមួយៗទៅកាន់ផ្លូវរបស់ Merkle ដែលនឹងបម្រើជាភស្តុតាងជាបន្តបន្ទាប់៖

លេខកូដ

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, &current_parent)
            } else {
                parent(&current_parent, &s.hash)
            };
        }

        current_parent == expected
    } else {
        false
    }
}

ដោយមើលឃើញ៖

ដំណើរ​ការ​នៃ​ការ​ត្រួត​ពិនិត្យ​ភស្តុតាង​សម្រាប់ ក

ការដកធាតុចេញ

ដើម្បីដកក្រឡាចេញពីថ្ម អ្នកត្រូវតែផ្តល់ភស្តុតាងត្រឹមត្រូវដែលថាកោសិកានៅទីនោះ។ ដោយប្រើទិន្នន័យពីភស្តុតាង វាគឺអាចធ្វើទៅបានដើម្បីគណនាធាតុឫសគល់ថ្មីនៃ accumulator ដែលភស្តុតាងដែលបានផ្តល់ឱ្យនឹងមិនពិតទៀតទេ។

ក្បួនដោះស្រាយមានដូចខាងក្រោម៖

1. បន្ថែមពីលើនេះ យើងរៀបចំកន្ត្រកទទេមួយដែលត្រូវនឹងដើមឈើ Merkle ដែលមានកម្ពស់ស្មើនឹងថាមពលពីរពីសន្ទស្សន៍កន្ត្រក។
2. យើងបញ្ចូលធាតុពីជំហាននៃផ្លូវ Merkle ទៅក្នុងកន្ត្រក។ សន្ទស្សន៍កញ្ចប់គឺស្មើនឹងចំនួនជំហានបច្ចុប្បន្ន
3. យើងដកធាតុឫសដែលផ្លូវចេញពីភស្តុតាងដឹកនាំ
4. ដូចនឹងការបន្ថែម យើងគណនាធាតុឫសថ្មីដោយផ្សំធាតុពីកន្ត្រកជាគូ និងផ្លាស់ទីលទ្ធផលនៃសហជីពទៅកន្ត្រកបន្ទាប់។

លេខកូដ

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;
    }
}

ដំណើរការនៃការដកធាតុ "A"៖

ការរួមបញ្ចូលទៅក្នុងបណ្តាញដែលមានស្រាប់

ដោយប្រើ accumulator ដែលបានស្នើឡើង ថ្នាំងអាចជៀសវាងការប្រើ DB ដើម្បីរក្សាទុក UTXO ទាំងអស់ ខណៈពេលដែលនៅតែអាចផ្លាស់ប្តូរ UTXO-set។ ទោះជាយ៉ាងណាក៏ដោយបញ្ហានៃការធ្វើការជាមួយភស្តុតាងកើតឡើង។

តោះហៅថ្នាំងសុពលភាពដែលប្រើ UTXO accumulator បង្រួម (compact-state node) ហើយ validator ដោយគ្មាន accumulator គឺ បញ្ចប់ (ថ្នាំងពេញ) ។ អត្ថិភាពនៃថ្នាក់ថ្នាំងពីរបង្កើតបញ្ហាសម្រាប់ការរួមបញ្ចូលពួកវាទៅក្នុងបណ្តាញតែមួយ ចាប់តាំងពីថ្នាំងបង្រួមត្រូវការភស្តុតាងនៃអត្ថិភាពនៃ UTXO ដែលត្រូវបានចំណាយក្នុងប្រតិបត្តិការ ខណៈដែលថ្នាំងពេញលេញមិនមាន។ ប្រសិនបើថ្នាំងបណ្តាញទាំងអស់មិនក្នុងពេលដំណាលគ្នា ហើយក្នុងលក្ខណៈសំរបសំរួលប្តូរទៅប្រើ Utreexo នោះថ្នាំងបង្រួមនឹងត្រូវទុកចោល ហើយនឹងមិនអាចដំណើរការលើបណ្តាញ Bitcoin បានទេ។

ដើម្បីដោះស្រាយបញ្ហានៃការរួមបញ្ចូលថ្នាំងបង្រួមទៅក្នុងបណ្តាញ វាត្រូវបានស្នើឡើងដើម្បីណែនាំថ្នាក់បន្ថែមនៃថ្នាំង - ស្ពាន. ថ្នាំងស្ពានគឺជាថ្នាំងពេញលេញដែលរក្សាទុកថ្ម Utreexo និងភស្តុតាងនៃការបើកថាមពលផងដែរ។ всех UTXO ពី UTXO-set ។ Bridges គណនាលេខហាសថ្មី និងធ្វើបច្ចុប្បន្នភាពឧបករណ៍ប្រមូល និងភស្តុតាង នៅពេលដែលប្លុកថ្មីនៃប្រតិបត្តិការមកដល់។ ការថែរក្សា និងធ្វើបច្ចុប្បន្នភាពឧបករណ៍ផ្ទុក និងភស្តុតាងមិនដាក់បន្ទុកបន្ថែមលើថ្នាំងបែបនេះទេ។ ស្ពានលះបង់ទំហំថាស៖ ចាំបាច់ត្រូវរក្សាអ្វីៗឱ្យមានរបៀបរៀបរយ hashes ធៀបនឹង សញ្ញាសម្រាប់ថ្នាំងបង្រួម ដែល n គឺជាថាមពលនៃសំណុំ UTXO ។

ស្ថាបត្យកម្មបណ្តាញ

Bridges ធ្វើឱ្យវាអាចបន្ថែមថ្នាំងបង្រួមបន្តិចម្តងៗទៅក្នុងបណ្តាញដោយមិនផ្លាស់ប្តូរកម្មវិធីរបស់ថ្នាំងដែលមានស្រាប់។ ថ្នាំងពេញលេញដំណើរការដូចពីមុន ចែកចាយប្រតិបត្តិការ និងប្លុកក្នុងចំណោមពួកគេ។ ថ្នាំងស្ពានគឺជាថ្នាំងពេញលេញដែលរក្សាទុកទិន្នន័យថ្ម Utreexo និងសំណុំនៃភស្តុតាងរួមបញ្ចូលសម្រាប់ всех UTXO សម្រាប់ពេលនេះ។ ថ្នាំងស្ពានមិនផ្សព្វផ្សាយដោយខ្លួនវាទេ ដោយធ្វើពុតជាថ្នាំងពេញលេញសម្រាប់ថ្នាំងពេញលេញទាំងអស់ និងថ្នាំងបង្រួមសម្រាប់ថ្នាំងតូចទាំងអស់។ ទោះបីជាស្ពានតភ្ជាប់បណ្តាញទាំងពីរជាមួយគ្នាក៏ដោយ តាមពិតពួកគេគ្រាន់តែត្រូវការភ្ជាប់ពួកវាក្នុងទិសដៅតែមួយប៉ុណ្ណោះ៖ ពីថ្នាំងពេញលេញដែលមានស្រាប់ទៅថ្នាំងបង្រួម។ នេះអាចទៅរួច ដោយសារទម្រង់ប្រតិបត្តិការមិនចាំបាច់ត្រូវបានផ្លាស់ប្តូរ ហើយភស្តុតាង UTXO សម្រាប់ថ្នាំងបង្រួមអាចត្រូវបានលុបចោល ដូច្នេះថ្នាំងបង្រួមណាមួយអាចផ្សាយប្រតិបត្តិការដូចគ្នាទៅកាន់អ្នកចូលរួមបណ្តាញទាំងអស់ដោយមិនមានការចូលរួមពីថ្នាំងស្ពាន។

សេចក្តីសន្និដ្ឋាន

យើងបានមើលថ្ម Utreexo ហើយបានអនុវត្តគំរូរបស់វានៅក្នុង Rust ។ យើងបានក្រឡេកមើលស្ថាបត្យកម្មបណ្តាញដែលនឹងអនុញ្ញាតឱ្យរួមបញ្ចូលថ្នាំងដែលមានមូលដ្ឋានលើថ្ម។ អត្ថប្រយោជន៍នៃការបង្រួមតូចគឺជាទំហំនៃទិន្នន័យដែលបានរក្សាទុកដែលអាស្រ័យលើលោការីតលើថាមពលនៃសំណុំ UTXO ដែលកាត់បន្ថយយ៉ាងខ្លាំងនូវតម្រូវការសម្រាប់ទំហំថាស និងដំណើរការផ្ទុកសម្រាប់ថ្នាំងបែបនេះ។ គុណវិបត្តិគឺចរាចរថ្នាំងបន្ថែមសម្រាប់ការបញ្ជូនភស្តុតាង ប៉ុន្តែបច្ចេកទេសនៃការប្រមូលផ្តុំភស្តុតាង (នៅពេលដែលភស្តុតាងមួយបង្ហាញពីអត្ថិភាពនៃធាតុជាច្រើន) និងឃ្លាំងសម្ងាត់អាចជួយរក្សាចរាចរក្នុងដែនកំណត់ដែលអាចទទួលយកបាន។

សេចក្តីយោង:

• GitHub នៃគំរូ Utreexo នៅក្នុង Rust
• ថាដឌឺស រីយ៉ា - Utreexo៖ ឧបករណ៍ប្រមូលផ្តុំដែលមានមូលដ្ឋានលើសញ្ញាថាមវន្តដែលត្រូវបានធ្វើឱ្យប្រសើរសម្រាប់សំណុំ Bitcoin UTXO
• គំនូរជីវចលពីអត្ថបទ

ប្រភព: www.habr.com