🥇Utreexo: mengompresi banyak UTXO Bitcoin

Hei Habr!

Dalam jaringan Bitcoin, semua node, melalui konsensus, menyetujui serangkaian UTXO: berapa banyak koin yang tersedia untuk dibelanjakan, kepada siapa sebenarnya, dan dalam kondisi apa. Kumpulan UTXO adalah kumpulan data minimum yang diperlukan untuk node validator, yang tanpanya node tidak akan dapat memverifikasi validitas transaksi masuk dan blok yang memuatnya.

Dalam hal ini, upaya dilakukan dengan segala cara yang mungkin untuk mengurangi representasi tersimpan dari kumpulan ini, untuk mengompresnya tanpa kehilangan jaminan keamanan. Semakin kecil volume data yang disimpan, semakin rendah kebutuhan ruang disk dari node validator, yang menjadikan peluncuran node validator menjadi murah, memungkinkan Anda memperluas jaringan dan dengan demikian meningkatkan stabilitas jaringan.

Dalam postingan kali ini kami akan memposting prototipe Rust dari proposal terbaru dari rekan penulis Kertas Jaringan Petir, Tadeus Dryja - Utreexo: akumulator berbasis hash dinamis yang dioptimalkan untuk set Bitcoin UTXO, yang memungkinkan pengurangan kebutuhan ruang disk untuk node validator.

Apa masalahnya?

Salah satu masalah abadi Bitcoin adalah skalabilitasnya. Gagasan “bank Anda sendiri” mengharuskan peserta jaringan untuk mencatat semua dana yang tersedia untuk digunakan. Dalam Bitcoin, dana yang tersedia dinyatakan sebagai satu set output yang belum terpakai - satu set UTXO. Meskipun ini bukan representasi intuitif, ini bermanfaat dalam hal kinerja implementasi dibandingkan representasi di mana setiap "dompet" memiliki "saldo" sebagai entri terpisah, dan juga menambahkan privasi (mis. KoinBergabung).

Penting untuk membedakan antara riwayat transaksi (yang disebut blockchain) dan keadaan sistem saat ini. Riwayat transaksi Bitcoin saat ini memakan ruang disk sekitar 200 GB, dan terus bertambah. Namun, status sistemnya jauh lebih kecil, sekitar 4 GB, dan hanya memperhitungkan fakta bahwa seseorang saat ini memiliki koin. Volume data ini juga meningkat seiring berjalannya waktu, namun dengan kecepatan yang jauh lebih lambat dan bahkan terkadang cenderung menurun (lihat CDPV).

Jaminan keamanan perdagangan klien ringan (SPV) atas kemampuan untuk tidak menyimpan status minimum (set UTXO) selain kunci pribadi.

Set UTXO dan UTXO

UTXO (Unspent Transaction Output) adalah output transaksi yang belum terpakai, titik akhir perjalanan setiap Satoshi yang ditransfer dalam transaksi. Output yang tidak terpakai menjadi input transaksi baru dan dengan demikian dibelanjakan (dibelanjakan) dan dikeluarkan dari set UTXO.

UTXO baru selalu dibuat melalui transaksi:

transaksi coinbase tanpa input: buat UTXO baru ketika penambang mengeluarkan koin
transaksi reguler: buat UTXO baru sambil membelanjakan serangkaian UTXO tertentu yang sudah ada

Proses bekerja dengan UTXO:

Dompet menghitung jumlah koin yang tersedia untuk dibelanjakan (saldo) berdasarkan jumlah UTXO yang tersedia di dompet ini untuk dibelanjakan.

Setiap node validator, untuk mencegah upaya pembelanjaan ganda, harus memantau set tersebut Semua UTXO saat memeriksa masing-masing transaksi dari masing-masing memblokir.

Node harus memiliki logika:

Penambahan pada set UTXO
Penghapusan dari set UTXO
Memeriksa keberadaan satu UTXO dalam satu set

Ada cara untuk mengurangi persyaratan informasi yang disimpan tentang suatu himpunan, dengan tetap mempertahankan kemampuan untuk menambah dan menghapus elemen, memeriksa dan membuktikan keberadaan suatu elemen dalam suatu himpunan menggunakan akumulator kriptografi.

Baterai untuk UTXO

Ide menggunakan baterai untuk menyimpan banyak UTXO dibahas sebelumnya.

Set UTXO dibuat dengan cepat, selama pengunduhan blok awal (IBD), disimpan secara penuh dan permanen, sementara isinya berubah setelah memproses transaksi dari setiap blok jaringan yang baru dan benar. Proses ini memerlukan pengunduhan sekitar 200 GB data blok dan memverifikasi ratusan juta tanda tangan digital. Setelah proses IBD selesai, intinya adalah set UTXO akan menempati sekitar 4 GB.

Namun, dengan akumulator, aturan konsensus dana direduksi menjadi verifikasi dan pembuatan bukti kriptografi, dan beban pelacakan dana yang tersedia dialihkan ke pemilik dana tersebut, yang memberikan bukti keberadaan dan kepemilikannya.

Akumulator dapat disebut sebagai representasi kompak dari suatu himpunan. Ukuran representasi yang disimpan harus konstan , atau meningkat secara sublinear terhadap kardinalitas himpunan dan ukuran elemen itu sendiri, misalnya , di mana n adalah kardinalitas himpunan yang disimpan.

Dalam hal ini, akumulator harus memungkinkan pembuatan bukti penyertaan suatu elemen dalam himpunan (bukti penyertaan) dan memungkinkan verifikasi bukti ini secara efektif.

Baterai disebut dinamis if memungkinkan Anda menambahkan elemen dan menghapus elemen dari suatu kumpulan.

Contoh baterai seperti itu adalah Akumulator RSA diusulkan oleh Boneh, Bunz, Fisch pada bulan Desember 2018. Akumulator semacam itu memiliki ukuran representasi tersimpan yang konstan, tetapi memerlukan kehadiran rahasia bersama (pengaturan tepercaya). Persyaratan ini meniadakan penerapan akumulator tersebut untuk jaringan yang tidak dapat dipercaya seperti Bitcoin, karena kebocoran data selama pembuatan rahasia dapat memungkinkan penyerang membuat bukti palsu tentang keberadaan UTXO, menipu node dengan kumpulan UTXO berdasarkan akumulator tersebut.

Utreexo

Desain Utreexo yang diusulkan oleh Thaddeus Dryja memungkinkan untuk berkreasi dinamis akumulator tanpa pengaturan tepercaya.

Utreexo adalah hutan biner sempurna Pohon Merkle dan merupakan pengembangan dari ide-ide yang disajikan dalam Akumulator asinkron yang efisien untuk pki terdistribusi, menambahkan kemampuan untuk menghapus elemen dari suatu kumpulan.

Struktur Logis Baterai

Sel baterai disusun dalam hutan pohon biner yang ideal. Pohon diurutkan berdasarkan ketinggian. Representasi ini dipilih sebagai yang paling visual dan memungkinkan Anda memvisualisasikan penggabungan pepohonan selama pengoperasian baterai.

Penulis mencatat bahwa karena semua pohon di hutan itu ideal, tingginya dinyatakan sebagai pangkat dua, sama seperti bilangan asli apa pun dapat direpresentasikan sebagai jumlah pangkat dua. Oleh karena itu, kumpulan daun apa pun dapat dikelompokkan menjadi pohon biner, dan dalam semua kasus, menambahkan elemen baru memerlukan pengetahuan hanya tentang simpul akar dari pohon yang disimpan.

Jadi, representasi tersimpan dari akumulator Utreexo adalah daftar node akar (Merkle root), dan bukan seluruh hutan pepohonan.

Mari kita nyatakan daftar elemen root sebagai Vec<Option<Hash>>. Tipe opsional Option<Hash> menunjukkan bahwa elemen akar mungkin hilang, yang berarti tidak ada pohon dengan ketinggian yang sesuai di akumulator.

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

Menambahkan elemen

Pertama, mari kita jelaskan fungsinya parent(), yang mengenali simpul induk untuk dua elemen tertentu.

fungsi orang tua()

Karena kita menggunakan pohon Merkle, induk dari masing-masing dua node adalah satu node yang menyimpan hash dari rangkaian hash dari node 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 bahwa untuk mencegah serangan yang dijelaskan oleh Charles Bouillaguet, Pierre-Alain Fouque, Adi Shamir, dan Sebastien Zimmer di
Serangan preimage kedua pada fungsi hash yang ragu-ragu, selain dua hash, ketinggian di dalam pohon juga harus ditambahkan ke rangkaian.

Saat Anda menambahkan elemen ke akumulator, Anda perlu melacak elemen akar mana yang diubah. Dengan mengikuti jalur perubahan elemen akar untuk setiap elemen yang Anda tambahkan, nantinya Anda dapat membuat bukti keberadaan elemen tersebut.

Lacak perubahan saat Anda menambahkannya

Untuk melacak perubahan yang dilakukan, mari kita deklarasikan strukturnya Update, yang akan menyimpan data tentang perubahan node.

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

Untuk menambahkan elemen ke baterai, Anda memerlukan:

Buat array keranjang elemen root new_roots dan tempatkan elemen root yang ada di sana, satu untuk setiap keranjang:

kode

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 ditambahkan (array insertions) ke kereta pertama new_roots[0]:

kode

new_roots[0].extend_from_slice(insertions);

Gabungkan item yang ditambahkan ke keranjang pertama dengan item lainnya:
- Untuk semua keranjang dengan lebih dari satu item:
  1. Ambil dua elemen dari ujung keranjang, hitung induknya, hapus kedua elemen tersebut
  2. Tambahkan induk yang dihitung ke keranjang berikutnya

kode

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

Pindahkan elemen root dari bin ke array akumulator yang dihasilkan

kode

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

Membuat bukti untuk elemen tambahan

Bukti dimasukkannya sel ke dalam baterai (Proof) akan berfungsi sebagai Jalur Merkle, yang terdiri dari sebuah rantai ProofStep. Jika jalannya tidak mengarah ke mana pun, maka buktinya salah.

/// Единичный шаг на пути к элементу в дереве Меркла.
#[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 informasi yang diperoleh sebelumnya saat menambahkan elemen (struktur Update), Anda dapat membuat bukti bahwa suatu elemen telah ditambahkan ke baterai. Untuk melakukan ini, kita melihat tabel perubahan yang dilakukan dan menambahkan setiap langkah ke jalur Merkle, yang selanjutnya akan menjadi bukti:

kode

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 menciptakan bukti

Memeriksa bukti suatu elemen

Memeriksa bukti penyertaan suatu elemen bermuara pada mengikuti jalur Merkle hingga mengarah ke elemen root yang sudah 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
    }
}

Jelas:

Proses pengecekan bukti A

Menghapus item

Untuk mengeluarkan sel dari baterai, Anda harus memberikan bukti sah bahwa sel tersebut ada. Dengan menggunakan data dari pembuktian, dimungkinkan untuk menghitung elemen akar baru dari akumulator yang pembuktiannya tidak lagi benar.

Algoritmanya adalah sebagai berikut:

Sebagai tambahan, kami mengatur satu set keranjang kosong yang sesuai dengan pohon Merkle dengan tinggi yang sama dengan pangkat dua dari indeks keranjang
Kami memasukkan elemen dari tangga jalur Merkle ke dalam keranjang; indeks keranjang sama dengan jumlah langkah saat ini
Kami menghapus elemen root yang menjadi tujuan jalur dari bukti
Seperti halnya penjumlahan, kita menghitung elemen akar baru dengan menggabungkan elemen dari keranjang secara berpasangan dan memindahkan hasil penggabungan ke keranjang berikutnya

kode

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 menghilangkan elemen "A":

Integrasi ke dalam jaringan yang ada

Dengan menggunakan akumulator yang diusulkan, node dapat menghindari penggunaan DB untuk menyimpan semua UTXO sambil tetap dapat mengubah set UTXO. Namun, masalah dalam menangani bukti muncul.

Mari kita panggil node validator yang menggunakan akumulator UTXO kompak (node status kompak), dan validator tanpa akumulator adalah lengkap (simpul penuh). Keberadaan dua kelas node menimbulkan masalah untuk mengintegrasikannya ke dalam satu jaringan, karena node kompak memerlukan bukti keberadaan UTXO, yang dihabiskan dalam transaksi, sedangkan node penuh tidak. Jika semua node jaringan tidak secara bersamaan dan terkoordinasi beralih menggunakan Utreexo, maka node kompak akan tertinggal dan tidak dapat beroperasi di jaringan Bitcoin.

Untuk mengatasi masalah pengintegrasian node kompak ke dalam jaringan, diusulkan untuk memperkenalkan kelas node tambahan - jembatan. Node jembatan adalah node lengkap yang juga menyimpan baterai Utreexo dan bukti penyalaan Semua UTXO dari set UTXO. Bridge menghitung hash baru dan memperbarui akumulator serta buktinya saat blok transaksi baru tiba. Memelihara dan memperbarui akumulator dan bukti tidak membebankan beban komputasi tambahan pada node tersebut. Bridge mengorbankan ruang disk: perlu menjaga segala sesuatunya tetap teratur hash, dibandingkan dengan hash untuk node kompak, di mana n adalah kekuatan set UTXO.

Arsitektur jaringan

Bridge memungkinkan penambahan node kompak ke jaringan secara bertahap tanpa mengubah perangkat lunak node yang ada. Node penuh beroperasi seperti sebelumnya, mendistribusikan transaksi dan blok di antara mereka sendiri. Node jembatan adalah node penuh yang juga menyimpan data baterai Utreexo dan serangkaian bukti penyertaan Semua UTXO untuk saat ini. Node jembatan tidak mengiklankan dirinya seperti itu, berpura-pura menjadi node penuh untuk semua node penuh dan node kompak untuk semua node kompak. Meskipun jembatan menghubungkan kedua jaringan bersama-sama, sebenarnya mereka hanya perlu menghubungkannya dalam satu arah: dari node penuh yang ada ke node kompak. Hal ini dimungkinkan karena format transaksi tidak perlu diubah, dan bukti UTXO untuk node kompak dapat dibuang, sehingga setiap node kompak dapat menyiarkan transaksi dengan cara yang sama ke semua peserta jaringan tanpa partisipasi node jembatan.

Kesimpulan

Kami melihat baterai Utreexo dan mengimplementasikan prototipenya di Rust. Kami melihat arsitektur jaringan yang memungkinkan integrasi node berbasis baterai. Keuntungan dari tangkapan kompak adalah ukuran data yang disimpan, yang secara logaritmik bergantung pada kekuatan kumpulan UTXO, yang sangat mengurangi kebutuhan ruang disk dan kinerja penyimpanan untuk node tersebut. Kerugiannya adalah lalu lintas node tambahan untuk mengirimkan bukti, namun teknik agregasi bukti (ketika satu bukti membuktikan keberadaan beberapa elemen) dan caching dapat membantu menjaga lalu lintas dalam batas yang dapat diterima.

referensi:

Sumber: www.habr.com

Utreexo: mengompresi banyak UTXO Bitcoin

Apa masalahnya?

Set UTXO dan UTXO

Baterai untuk UTXO

Utreexo

Struktur Logis Baterai

Menambahkan elemen

Membuat bukti untuk elemen tambahan

Memeriksa bukti suatu elemen

Menghapus item

Integrasi ke dalam jaringan yang ada

Arsitektur jaringan

Kesimpulan

Tambah komentar Membatalkan balasan