Utreexo: mengompresi banyak UTXO Bitcoin

Halo, Habr!

Dalam jaringan Bitcoin, semua simpul setuju dengan konsensus tentang banyak UTXO: berapa banyak koin yang tersedia untuk dibelanjakan, kepada siapa, dan dalam kondisi apa. Himpunan UTXO adalah kumpulan data minimum yang diperlukan untuk simpul validator, yang tanpanya node tidak dapat memverifikasi validitas transaksi yang masuk dan blok yang mengandungnya.

Dalam hal ini, upaya dilakukan dengan segala cara untuk mengurangi representasi simpanan dari set ini, untuk mengompresnya tanpa kehilangan jaminan keamanan. Semakin kecil volume data yang disimpan, semakin rendah persyaratan untuk ruang disk dari simpul validator, yang membuat peluncuran simpul validator murah, memungkinkan Anda untuk memperluas jaringan dan dengan demikian meningkatkan stabilitas jaringan.

Dalam catatan ini, kami akan membahas prototipe Rust dari proposal baru-baru ini dari penulis bersama Lightning Network Paper , Thaddeus Dryja - Utreexo: akumulator berbasis hash dinamis yang dioptimalkan untuk set Bitcoin UTXO , yang mengurangi kebutuhan ruang disk untuk node validator.

Apa masalahnya?

Salah satu masalah abadi Bitcoin adalah skalabilitasnya. Gagasan "memiliki bank" mengharuskan peserta jaringan untuk melacak semua dana yang tersedia untuk digunakan. Dalam Bitcoin, dana yang tersedia dinyatakan sebagai satu set keluaran yang tidak digunakan - set UTXO. Meskipun ini bukan presentasi yang sangat intuitif, ini menguntungkan dalam hal kinerja implementasi, dibandingkan dengan presentasi di mana setiap dompet memiliki "keseimbangan" sebagai entri terpisah, dan juga menambah privasi (misalnya, menyediakan CoinJoin ).

Penting untuk membedakan antara riwayat transaksi (apa yang disebut blockchain) dan kondisi sistem saat ini. Sejarah transaksi Bitcoin saat ini menempati sekitar 200 GB ruang disk, dan terus bertambah. Namun, keadaan sistem jauh lebih kecil, sekitar 4 GB, dan hanya memperhitungkan fakta bahwa seseorang saat ini memiliki koin. Volume data ini juga meningkat seiring waktu, tetapi pada tingkat yang jauh lebih rendah dan kadang-kadang bahkan cenderung menurun (lihat KDPV).

Klien keamanan pertukaran cahaya (SPVs) menukar kemampuan untuk tidak menyimpan status minimum (set-UTXO), kecuali untuk kunci pribadi.

UTXO dan UTXO-set

UTXO (Output Transaksi yang Tidak Terpakai) - output transaksi yang tidak terpakai, titik akhir dari perjalanan setiap satoshi yang ditransmisikan dalam transaksi. Output yang tidak digunakan menjadi input dari transaksi baru dan pada saat yang bersamaan menghabiskan dan dihapus dari UTXO-set.

UTXO baru selalu dibuat oleh transaksi:

• transaksi coinbase tanpa input: buat UTXO baru selama penerbitan koin oleh penambang
• transaksi konvensional: buat UTXO baru, sambil menghabiskan sejumlah UTXO yang ada

Proses bekerja dengan UTXO:

Dompet mempertimbangkan jumlah koin yang tersedia untuk pengeluaran (saldo) berdasarkan jumlah UTXO yang tersedia untuk dompet ini untuk dibelanjakan.

Setiap simpul validator, untuk mencegah upaya pengeluaran ganda, harus melacak pengumpulan semua UTXO selama verifikasi setiap transaksi dari setiap blok.

Node harus memiliki logika:

• Tambahan untuk UTXO-set
• Set penghapusan UTXO
• Memeriksa keberadaan UTXO tunggal di set

Ada cara untuk mengurangi persyaratan untuk informasi yang tersimpan tentang perangkat, sementara tetap mempertahankan kemampuan untuk menambah dan menghapus elemen, memeriksa dan membuktikan keberadaan elemen dalam perangkat menggunakan baterai kriptografi .

Baterai untuk UTXO

Gagasan menggunakan baterai untuk menyimpan banyak UTXO telah dibahas sebelumnya .

UTXO-set dibangun dengan cepat, selama pemuatan awal rantai blok (IBD, pengunduhan blok awal), disimpan secara penuh dan terus-menerus, sementara isinya berubah setelah memproses transaksi dari setiap blok jaringan yang baru dan benar. Proses ini memerlukan mengunduh sekitar 200 GB blok data dan memverifikasi ratusan juta tanda tangan digital. Setelah proses IBD selesai, residu kering yang diatur UTXO akan menempati sekitar 4 GB.

Namun, ketika menggunakan baterai, aturan konsensus mengenai dana turun untuk memeriksa dan menghasilkan bukti kriptografi, dan beban melacak dana yang tersedia ditempatkan di pundak pemilik dana ini, yang memberikan bukti keberadaan dan kepemilikannya.

Baterai dapat disebut representasi ringkas dari perangkat. Ukuran tampilan yang disimpan, dalam hal ini, harus konstan $$$O (1)$, atau menambah secara sublinear relatif terhadap kekuatan himpunan dan ukuran elemen itu sendiri, misalnya $$$O (log (n))$di mana n adalah kekuatan set yang disimpan.

Dalam hal ini, akumulator harus memungkinkan menghasilkan bukti dari dimasukkannya elemen dalam set (bukti inklusi) dan memungkinkannya untuk memverifikasi bukti ini secara efektif.

Baterai disebut dinamis jika memungkinkan Anda untuk menambah item dan menghapus item dari set.

Contoh dari baterai tersebut adalah baterai RSA yang diusulkan oleh Boneh, Bunz, Fisch pada bulan Desember 2018 . Baterai seperti itu memiliki ukuran konstan dari tampilan yang disimpan, tetapi membutuhkan 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 untuk membuat bukti palsu tentang keberadaan UTXO dengan menipu node dengan set UTXO yang didasarkan pada akumulator tersebut.

Utreexo

Desain Thaddeus Dryja yang diusulkan oleh Utreexo memungkinkan Anda untuk membuat baterai yang dinamis tanpa pengaturan yang tepercaya.

Utreexo adalah hutan biner Merkle Trees yang ideal dan merupakan pengembangan dari ide-ide yang disajikan dalam akumulator Asinkron efisien untuk pki terdistribusi , menambahkan kemampuan untuk menghapus elemen dari set.

Struktur logis baterai

Sel baterai diatur dalam hutan pohon biner yang sempurna. Pohon dipesan berdasarkan tinggi. Presentasi ini dipilih sebagai yang paling visual dan memungkinkan Anda untuk memvisualisasikan penggabungan pohon selama operasi pada baterai.

Penulis mencatat bahwa karena semua pohon di hutan sempurna, ketinggiannya dinyatakan oleh kekuatan dua, sama seperti nomor alami dapat direpresentasikan sebagai jumlah dari kekuatan dua. Dengan demikian, setiap set sheet dapat dikelompokkan dalam bentuk pohon biner, dan dalam semua kasus, menambahkan elemen baru hanya membutuhkan pengetahuan tentang simpul akar dari pohon yang disimpan .

Dengan demikian, tampilan tersimpan baterai Utreexo adalah daftar simpul akar (akar Merkle), dan bukan seluruh hutan pohon .

Bayangkan daftar elemen root sebagai Vec<Option<Hash>> . Jenis Option<Hash> opsional Option<Hash> menunjukkan bahwa elemen root mungkin hilang, yang berarti bahwa pohon tidak memiliki pohon dengan ketinggian yang sesuai.

 /// 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 Item

Pertama, kami menggambarkan fungsi parent() , yang mengenali node induk untuk dua elemen yang diberikan.

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

Saat menambahkan item ke baterai, Anda harus melacak item root mana yang sedang diubah. Mengikuti jalur untuk mengubah elemen root untuk setiap elemen yang ditambahkan, Anda kemudian dapat membuat bukti keberadaan elemen-elemen ini.

 #[derive(Debug)] pub struct Update<'a> { pub utreexo: &'a mut Utreexo, // ProofStep  ""     pub updated: HashMap<Hash, ProofStep>, } 

Untuk menambahkan elemen ke baterai, Anda perlu:

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

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

 new_roots[0].extend_from_slice(insertions); 

• Lakukan "penggabungan" item yang ditambahkan ke keranjang pertama dengan yang lain:
  
  • Untuk semua keranjang dengan lebih dari satu item:
    
    1. Kami mengambil dua elemen dari akhir keranjang, menghitung induknya, menghapus kedua elemen
    2. Tambahkan induk terhitung ke keranjang berikutnya.

 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 keranjang ke array baterai yang dihasilkan

 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 item yang ditambahkan

Bukti dimasukkannya elemen dalam baterai ( Proof ) akan menjadi Merkle Path, yang terdiri dari rantai ProofStep . Jika jalan itu tidak menuju ke mana-mana, 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 selama penambahan elemen (Struktur Update ), Anda dapat membuat bukti bahwa elemen telah ditambahkan ke baterai. Untuk melakukan ini, kita berkeliling tabel perubahan yang dibuat dan menambahkan setiap langkah ke jalur Merkle, yang selanjutnya akan berfungsi sebagai bukti:

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

Bukti bukti untuk suatu barang

Memeriksa bukti dimasukkannya elemen (bukti inklusi) dikurangi untuk mengikuti jalur Merkle, sampai mengarah ke elemen root yang 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:

Hapus item

Untuk menghapus elemen dari baterai, Anda harus memberikan bukti yang valid bahwa elemen itu ada di sana. Dengan menggunakan data dari buktinya, kita dapat menghitung elemen-elemen root baru dari baterai yang buktinya tidak lagi benar.

Algoritma adalah sebagai berikut:

1. Seperti halnya penambahan, kami mengatur satu set keranjang kosong yang sesuai dengan pohon Merkle dengan ketinggian sama dengan dua indeks keranjang
2. Masukkan item dari langkah-langkah lintasan Merkle ke dalam keranjang indeks keranjang sama dengan nomor langkah saat ini
3. Kami menghapus elemen root yang path dari bukti mengarah.
4. Seperti halnya penambahan, kami menghitung elemen root baru, menggabungkan elemen dari keranjang berpasangan dan memindahkan hasil gabungan ke keranjang berikutnya

 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 menghapus item "A":

Integrasi ke dalam jaringan yang ada

Menggunakan baterai yang diusulkan, node dapat menolak untuk menggunakan database untuk menyimpan semua UTXO, sambil mempertahankan kemampuan untuk mengubah set UTXO. Namun, ada masalah dalam bekerja dengan bukti.

Kami akan memanggil simpul validator yang menggunakan baterai kompak UTXO (compact-state node), dan validator tanpa baterai - penuh (simpul penuh). Keberadaan dua kelas node menciptakan masalah mengintegrasikan mereka ke dalam satu jaringan, karena node kompak memerlukan bukti keberadaan UTXO, yang dihabiskan dalam transaksi, tetapi node penuh tidak. Jika semua node jaringan pada saat yang sama dan secara terkoordinasi tidak beralih ke Utreexo, maka node kompak akan tertinggal dan tidak akan dapat bekerja di jaringan Bitcoin.

Untuk memecahkan masalah mengintegrasikan node kompak ke dalam jaringan, diusulkan untuk memperkenalkan kelas tambahan node - jembatan . Bridge node adalah node lengkap yang, antara lain, menyimpan baterai Utreexo dan bukti inklusi untuk semua UTXO dari set UTXO. Bridges menghitung hash baru dan memperbarui baterai dan bukti ketika blok baru tiba dengan transaksi. Mendukung dan memperbarui baterai dan bukti tidak membebankan beban komputasi tambahan pada node tersebut. Bridges mengorbankan ruang disk: menjaga ketertiban $$$2n$hash dibandingkan dengan $$$log (n)$hash untuk node kompak, di mana n adalah kekuatan dari set UTXO.

Arsitektur jaringan

Jembatan memungkinkan untuk secara bertahap menambahkan node kompak ke jaringan tanpa mengubah perangkat lunak dari node yang ada. Node penuh berfungsi seperti sebelumnya, mendistribusikan transaksi dan blok di antara mereka sendiri. Bridge node adalah node lengkap yang juga menyimpan data baterai Utreexo dan satu set bukti inklusi untuk semua UTXO saat ini. Node jembatan tidak mengiklankan dirinya sendiri seperti itu, berpura-pura menjadi simpul penuh untuk semua simpul lengkap dan simpul kompak untuk semua simpul padat. Meskipun jembatan menghubungkan kedua jaringan bersama-sama, pada kenyataannya, mereka harus terhubung hanya dalam satu arah: dari node lengkap yang ada ke node kompak. Ini dimungkinkan karena format transaksi tidak perlu diubah, dan bukti untuk UTXO untuk simpul padat dapat dibuang, sehingga simpul padat apa pun dapat mengirim transaksi ke semua peserta jaringan dengan cara yang sama tanpa partisipasi simpul jembatan.

Kesimpulan

Kami meninjau baterai Utreexo dan mengimplementasikan prototipe di Rust. Kami memeriksa arsitektur jaringan, yang akan mengintegrasikan node berdasarkan pada baterai. Keuntungan dari compact catch adalah ukuran data yang disimpan, yang tergantung secara logaritmik pada kekuatan banyak UTXO, yang sangat mengurangi kebutuhan ruang disk dan kinerja penyimpanan untuk node tersebut. Kerugiannya adalah trafik node tambahan untuk transfer bukti, tetapi teknik agregasi bukti (ketika satu bukti membuktikan keberadaan beberapa elemen) dan caching dapat membantu menjaga lalu lintas dalam batas yang dapat diterima.

Referensi :

• Utreexo Rust Prototype GitHub
• Thaddeus Dryja - Utreexo: akumulator berbasis hash dinamis yang dioptimalkan untuk set Bitcoin UTXO
• Karya Seni Animasi dari Artikel