🥇Utreexo: memampatkan banyak UTXO Bitcoin

Hai Habr!

Dalam rangkaian Bitcoin, semua nod, melalui konsensus, bersetuju dengan satu set UTXO: berapa banyak syiling yang tersedia untuk perbelanjaan, kepada siapa sebenarnya, dan dalam keadaan apa. Set UTXO ialah set minimum data yang diperlukan untuk nod pengesah, tanpanya nod tidak akan dapat mengesahkan kesahihan transaksi masuk dan blok yang mengandunginya.

Dalam hal ini, percubaan sedang dibuat dalam setiap cara yang mungkin untuk mengurangkan perwakilan yang disimpan bagi set ini, untuk memampatkannya tanpa kehilangan jaminan keselamatan. Semakin kecil jumlah data yang disimpan, semakin rendah keperluan ruang cakera nod pengesah, yang menjadikan pelancaran nod pengesah murah, membolehkan anda mengembangkan rangkaian dan dengan itu meningkatkan kestabilan rangkaian.

Dalam siaran ini kami akan menyiarkan prototaip Rust cadangan terbaru daripada pengarang bersama Kertas Rangkaian Kilat, Thaddeus Dryja - Utreexo: penumpuk berasaskan cincang dinamik yang dioptimumkan untuk set Bitcoin UTXO, yang membolehkan mengurangkan keperluan ruang cakera untuk nod pengesah.

Apa masalahnya?

Salah satu masalah abadi Bitcoin ialah kebolehskalaannya. Idea "bank anda sendiri" memerlukan peserta rangkaian untuk menyimpan rekod semua dana yang tersedia untuk digunakan. Dalam Bitcoin, dana yang tersedia dinyatakan sebagai satu set output yang tidak dibelanjakan - set UTXO. Walaupun ini bukan perwakilan yang intuitif, ia bermanfaat dari segi prestasi pelaksanaan berbanding perwakilan yang setiap "dompet" mempunyai "baki" sebagai entri yang berasingan, dan juga menambah privasi (cth. CoinJoin).

Adalah penting untuk membezakan antara sejarah transaksi (apa yang dipanggil blockchain) dan keadaan semasa sistem. Sejarah transaksi Bitcoin kini menduduki kira-kira 200 GB ruang cakera, dan terus berkembang. Walau bagaimanapun, keadaan sistem adalah lebih kecil, mengikut susunan 4 GB, dan hanya mengambil kira hakikat bahawa seseorang pada masa ini memiliki syiling. Kelantangan data ini juga meningkat dari semasa ke semasa, tetapi pada kadar yang lebih perlahan dan kadangkala cenderung berkurangan (lihat CDPV).

Pelanggan ringan (SPV) berdagang jaminan keselamatan untuk keupayaan untuk menyimpan tiada keadaan minimum (UTXO-set) selain kunci peribadi.

UTXO dan UTXO-set

UTXO (Unspent Transaction Output) ialah output transaksi yang tidak dibelanjakan, titik akhir perjalanan setiap Satoshi yang dipindahkan dalam transaksi. Output yang tidak dibelanjakan menjadi input transaksi baharu dan dengan itu dibelanjakan (belanja) dan dikeluarkan daripada set UTXO.

UTXO baharu sentiasa dibuat melalui urus niaga:

transaksi coinbase tanpa input: cipta UTXO baharu apabila pelombong mengeluarkan syiling
transaksi biasa: cipta UTXO baharu sambil membelanjakan set UTXO sedia ada tertentu

Proses bekerja dengan UTXO:

Dompet mengira bilangan syiling yang tersedia untuk perbelanjaan (baki) berdasarkan jumlah UTXO yang tersedia untuk dompet ini untuk perbelanjaan.

Setiap nod pengesah, untuk mengelakkan percubaan perbelanjaan dua kali, mesti memantau set Semua UTXO apabila menyemak setiap urus niaga masing-masing blok.

Nod mesti mempunyai logik:

Tambahan kepada set UTXO
Pemadaman daripada set UTXO
Menyemak kehadiran satu UTXO dalam satu set

Terdapat cara untuk mengurangkan keperluan untuk maklumat yang disimpan tentang set, sambil mengekalkan keupayaan untuk menambah dan mengalih keluar elemen, menyemak dan membuktikan kewujudan elemen dalam set menggunakan akumulator kriptografi.

Bateri untuk UTXO

Idea menggunakan bateri untuk menyimpan berbilang UTXO telah dibincangkan sebelum ini.

Set UTXO dibina dengan cepat, semasa muat turun blok awal (IBD), disimpan sepenuhnya dan kekal, manakala kandungannya berubah selepas memproses transaksi daripada setiap blok rangkaian baharu dan betul. Proses ini memerlukan memuat turun kira-kira 200 GB data blok dan mengesahkan ratusan juta tandatangan digital. Selepas proses IBD selesai, intinya ialah set UTXO akan menduduki kira-kira 4 GB.

Walau bagaimanapun, dengan penumpuk, peraturan konsensus untuk dana dikurangkan kepada pengesahan dan penjanaan bukti kriptografi, dan beban menjejaki dana yang tersedia dialihkan kepada pemilik dana tersebut, yang memberikan bukti kewujudan dan pemilikan mereka.

Penumpuk boleh dipanggil perwakilan padat bagi satu set. Saiz perwakilan yang disimpan mestilah sama ada tetap , atau meningkat secara sublinear berkenaan dengan kardinaliti set dan saiz elemen itu sendiri, contohnya , di mana n ialah kardinaliti set yang disimpan.

Dalam kes ini, penumpuk harus membenarkan penjanaan bukti kemasukan elemen dalam set (bukti kemasukan) dan memungkinkan untuk mengesahkan bukti ini dengan berkesan.

Bateri dipanggil dinamik jika membenarkan anda menambah elemen dan mengalih keluar elemen daripada set.

Contoh bateri sedemikian ialah Penumpuk RSA yang dicadangkan oleh Boneh, Bunz, Fisch pada Disember 2018. Penumpuk sedemikian mempunyai saiz perwakilan tersimpan yang tetap, tetapi memerlukan kehadiran rahsia kongsi (persediaan dipercayai). Keperluan ini menafikan kebolehgunaan penumpuk sedemikian untuk rangkaian tanpa amanah seperti Bitcoin, kerana kebocoran data semasa penjanaan rahsia boleh membenarkan penyerang mencipta bukti palsu kewujudan UTXO, memperdayakan nod dengan set UTXO berdasarkan penumpuk sedemikian.

Utreexo

Reka bentuk Utreexo yang dicadangkan oleh Thaddeus Dryja memungkinkan untuk dibuat dinamik аккумулятор tanpa persediaan-dipercayai.

Utreexo ialah hutan binari yang sempurna Pokok Merkle dan merupakan perkembangan idea yang dikemukakan dalam Penumpuk tak segerak yang cekap untuk pki teragih, menambah keupayaan untuk mengalih keluar elemen daripada set.

Struktur Logik Bateri

Sel bateri disusun dalam hutan pokok binari yang ideal. Pokok disusun mengikut ketinggian. Perwakilan ini dipilih sebagai yang paling visual dan membolehkan anda memvisualisasikan penggabungan pokok semasa operasi pada bateri.

Penulis menyatakan bahawa oleh kerana semua pokok di dalam hutan adalah ideal, ketinggiannya dinyatakan sebagai kuasa dua, sama seperti mana-mana nombor asli boleh diwakili sebagai jumlah kuasa dua. Sehubungan itu, mana-mana set daun boleh dikumpulkan ke dalam pokok binari, dan dalam semua kes, menambah elemen baharu memerlukan pengetahuan hanya mengenai nod akar pokok yang disimpan.

Oleh itu, perwakilan tersimpan penumpuk Utreexo ialah senarai nod akar (akar Merkle), dan bukan seluruh hutan pokok.

Mari kita wakili senarai elemen akar sebagai Vec<Option<Hash>>. Jenis pilihan Option<Hash> menunjukkan bahawa unsur akar mungkin hilang, yang bermaksud bahawa tiada pokok dengan ketinggian yang sesuai dalam penumpuk.

/// 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],
        }
    }
}

Menambah elemen

Pertama, mari kita terangkan fungsi parent(), yang mengiktiraf nod induk untuk dua elemen tertentu.

fungsi induk().

Memandangkan kami menggunakan pepohon Merkle, induk bagi setiap dua nod ialah satu nod yang menyimpan cincang gabungan cincangan nod anak:

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

Penulis mencatat bahawa untuk mencegah serangan yang diterangkan oleh Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, dan Sebastien Zimmer dalam
Serangan praimej kedua pada fungsi cincang yang diterbangkan, sebagai tambahan kepada dua cincang, ketinggian di dalam pokok itu juga harus ditambah pada penggabungan.

Semasa anda menambah elemen pada penumpuk, anda perlu menjejaki elemen akar yang diubah. Dengan mengikut laluan menukar elemen akar untuk setiap elemen yang anda tambahkan, anda kemudian boleh membina bukti kehadiran elemen ini.

Jejaki perubahan semasa anda menambahkannya

Untuk menjejaki perubahan yang dibuat, mari kita isytiharkan struktur Update, yang akan menyimpan data tentang perubahan nod.

#[derive(Debug)]
pub struct Update<'a> {
    pub utreexo: &'a mut Utreexo,
    // ProofStep хранит "соседа" элемента и его положение
    pub updated: HashMap<Hash, ProofStep>,
}

Untuk menambah elemen pada bateri, anda memerlukan:

Buat susunan bakul elemen akar new_roots dan letakkan elemen akar sedia ada di sana, satu untuk setiap baldi:

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

Tambahkan elemen yang akan ditambah (array insertions) ke troli pertama new_roots[0]:

Kod

new_roots[0].extend_from_slice(insertions);

Satukan item yang ditambahkan pada bakul pertama dengan yang lain:
- Untuk semua troli dengan lebih daripada satu item:
  1. Ambil dua elemen dari hujung bakul, kira induknya, keluarkan kedua-dua elemen
  2. Tambahkan induk yang dikira pada troli seterusnya

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

Alihkan elemen akar daripada tong ke tatasusunan penumpuk yang terhasil

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

Mencipta bukti untuk elemen tambahan

Bukti kemasukan sel dalam bateri (Proof) akan berfungsi sebagai Laluan Merkle, yang terdiri daripada rantai ProofStep. Jika jalan tidak menuju ke mana, maka buktinya tidak betul.

/// Единичный шаг на пути к элементу в дереве Меркла.
#[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,
}

Menggunakan maklumat yang diperoleh sebelum ini apabila menambah elemen (struktur Update), anda boleh membuat bukti bahawa elemen telah ditambahkan pada bateri. Untuk melakukan ini, kami menyemak jadual perubahan yang dibuat dan menambah setiap langkah ke laluan Merkle, yang kemudiannya akan menjadi bukti:

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

Proses mencipta bukti

Menyemak bukti untuk unsur

Menyemak bukti kemasukan elemen bermula dengan mengikuti laluan Merkle sehingga ia membawa kepada elemen akar sedia ada:

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

Secara visual:

Proses menyemak bukti untuk A

Mengalih keluar item

Untuk mengeluarkan sel daripada bateri, anda mesti memberikan bukti yang sah bahawa sel itu ada di sana. Menggunakan data daripada bukti, adalah mungkin untuk mengira unsur akar baru penumpuk yang mana bukti yang diberikan tidak lagi benar.

Algoritma adalah seperti berikut:

Sebagai tambahan, kami mengatur satu set bakul kosong sepadan dengan pokok Merkle dengan ketinggian sama dengan kuasa dua dari indeks bakul
Kami memasukkan elemen dari tangga laluan Merkle ke dalam bakul; indeks bakul adalah sama dengan bilangan langkah semasa
Kami mengalih keluar elemen akar yang menuju ke laluan dari bukti
Seperti menambah, kami mengira elemen akar baharu dengan menggabungkan elemen daripada bakul secara berpasangan dan mengalihkan hasil gabungan ke bakul seterusnya

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

Proses mengalih keluar elemen "A":

Integrasi ke dalam rangkaian sedia ada

Menggunakan penumpuk yang dicadangkan, nod boleh mengelak daripada menggunakan DB untuk menyimpan semua UTXO sementara masih boleh menukar set UTXO. Walau bagaimanapun, masalah bekerja dengan bukti timbul.

Mari kita panggil nod pengesah yang menggunakan penumpuk UTXO padat (nod keadaan padat), dan pengesah tanpa penumpuk ialah lengkap (nod penuh). Kewujudan dua kelas nod menimbulkan masalah untuk mengintegrasikannya ke dalam satu rangkaian, kerana nod padat memerlukan bukti kewujudan UTXO, yang dibelanjakan dalam transaksi, manakala nod penuh tidak. Jika semua nod rangkaian tidak secara serentak dan dalam cara yang diselaraskan beralih kepada menggunakan Utreexo, maka nod padat akan ketinggalan dan tidak akan dapat beroperasi pada rangkaian Bitcoin.

Untuk menyelesaikan masalah mengintegrasikan nod padat ke dalam rangkaian, adalah dicadangkan untuk memperkenalkan kelas nod tambahan - jambatan. Nod jambatan ialah nod lengkap yang turut menyimpan bateri Utreexo dan bukti kuasa hidup untuk Semua UTXO daripada UTXO-set. Bridges mengira cincang baharu dan mengemas kini penumpuk serta bukti apabila blok urus niaga baharu tiba. Mengekalkan dan mengemas kini penumpuk dan bukti tidak mengenakan beban pengiraan tambahan pada nod tersebut. Jambatan mengorbankan ruang cakera: perlu memastikan perkara teratur hash, berbanding dengan cincang untuk nod padat, dengan n ialah kuasa set UTXO.

Seni bina rangkaian

Jambatan memungkinkan untuk menambah nod padat secara beransur-ansur pada rangkaian tanpa mengubah perisian nod sedia ada. Nod penuh beroperasi seperti sebelumnya, mengedarkan urus niaga dan blok sesama mereka. Nod jambatan ialah nod penuh yang juga menyimpan data bateri Utreexo dan satu set bukti kemasukan untuk Semua UTXO buat masa ini. Nod jambatan tidak mengiklankan dirinya seperti itu, berpura-pura menjadi nod penuh untuk semua nod penuh dan nod padat untuk semua nod padat. Walaupun jambatan menghubungkan kedua-dua rangkaian bersama-sama, mereka sebenarnya hanya perlu menyambungkannya dalam satu arah: daripada nod penuh sedia ada kepada nod padat. Ini mungkin kerana format transaksi tidak perlu diubah, dan bukti UTXO untuk nod padat boleh dibuang, jadi mana-mana nod padat boleh menyiarkan transaksi yang serupa kepada semua peserta rangkaian tanpa penyertaan nod jambatan.

Kesimpulan

Kami melihat bateri Utreexo dan melaksanakan prototaipnya dalam Rust. Kami melihat seni bina rangkaian yang akan membenarkan penyepaduan nod berasaskan bateri. Kelebihan tangkapan padat ialah saiz data yang disimpan, yang bergantung secara logaritma pada kuasa set UTXO, yang sangat mengurangkan keperluan untuk ruang cakera dan prestasi storan untuk nod tersebut. Kelemahannya ialah trafik nod tambahan untuk menghantar bukti, tetapi teknik pengagregatan bukti (apabila satu bukti membuktikan kewujudan beberapa elemen) dan caching boleh membantu mengekalkan trafik dalam had yang boleh diterima.

rujukan:

Sumber: www.habr.com

Utreexo: memampatkan banyak UTXO Bitcoin

Apa masalahnya?

UTXO dan UTXO-set

Bateri untuk UTXO

Utreexo

Struktur Logik Bateri

Menambah elemen

Mencipta bukti untuk elemen tambahan

Menyemak bukti untuk unsur

Mengalih keluar item

Integrasi ke dalam rangkaian sedia ada

Seni bina rangkaian

Kesimpulan

Tambah komen Batal reply