Halo semuanya! Baru-baru ini menemukan bahasa Rust. Dia berbagi kesan pertamanya di artikel sebelumnya . Sekarang saya memutuskan untuk menggali lebih dalam, untuk ini Anda perlu sesuatu yang lebih serius daripada daftar. Pilihan saya jatuh pada pohon Merkle. Dalam artikel ini saya ingin:
- bicarakan struktur data ini
- lihat apa yang sudah dimiliki Rust
- menawarkan implementasi Anda
- bandingkan kinerja
Merkle Tree
Ini adalah struktur data yang relatif sederhana, dan sudah ada banyak informasi tentang hal itu di Internet, tetapi saya pikir artikel saya tidak akan lengkap tanpa uraian pohon.
Apa masalahnya?
Pohon Merkle ditemukan kembali pada tahun 1979, tetapi mendapatkan popularitasnya berkat blockchain. Rantai blok dalam jaringan sangat besar (untuk bitcoin lebih dari 200 GB), dan tidak semua node dapat memompanya. Misalnya, telepon atau mesin kasir. Namun demikian, mereka perlu tahu tentang fakta termasuk ini atau itu transaksi di blok. Untuk ini, protokol SPV - Verifikasi Pembayaran Sederhana telah ditemukan.
Cara kerja pohon
Ini adalah pohon biner yang daunnya hash dari benda apa pun. Untuk membangun tingkat berikutnya, hash daun tetangga diambil berpasangan, digabungkan dan hash dari hasil penggabungan dihitung, yang diilustrasikan dalam gambar di header. Dengan demikian, akar pohon adalah hash dari semua daun. Jika Anda menghapus atau menambahkan elemen, root akan berubah.
Bagaimana cara kerja pohon?
Memiliki pohon Merkle, Anda dapat membangun bukti dari penyertaan transaksi dalam blok sebagai jalur dari hash transaksi ke root. Sebagai contoh, kami tertarik pada transaksi Tx2, untuk itu buktinya adalah (Hash3, Hash01). Mekanisme ini juga digunakan dalam SPV. Klien hanya mengunduh header blok dengan hash-nya. Memiliki transaksi yang menarik, ia meminta bukti dari simpul yang berisi seluruh rantai. Kemudian ia melakukan pemeriksaan, untuk Tx2 akan menjadi:
hash(Hash01, hash(Hash2, Hash3)) = Root Hash
Hasilnya dibandingkan dengan root header blok. Pendekatan ini membuat tidak mungkin untuk memalsukan bukti, karena dalam hal ini hasil tes tidak menyatu dengan isi tajuk.
Implementasi mana yang sudah ada
Karat adalah bahasa yang muda, tetapi banyak realisasi pohon Merkle sudah ditulis di atasnya. Dilihat oleh Github, saat ini 56, ini lebih dari gabungan C dan C ++. Meskipun Go membuatnya berdiri dengan 80 implementasi.
Sebagai perbandingan, saya memilih implementasi ini dengan jumlah bintang di repositori.
Pohon ini dibangun dengan cara yang paling jelas, yaitu grafik benda. Seperti yang sudah saya catat, pendekatan ini tidak sepenuhnya ramah terhadap karat. Misalnya, komunikasi dua arah dari anak ke orang tua tidak mungkin dilakukan.
Konstruksi bukti terjadi melalui pencarian mendalam. Jika lembar dengan hash yang tepat ditemukan, maka jalan menuju itu akan menjadi hasilnya.
Apa yang bisa diperbaiki
Itu tidak menarik bagi saya untuk membuat implementasi sederhana (n +1), jadi saya berpikir tentang optimasi. Kode untuk vektor-merkle-tree saya ada di Github .
Penyimpanan data
Hal pertama yang terlintas dalam pikiran adalah untuk memindahkan pohon ke array. Solusi ini akan jauh lebih baik dalam hal lokalitas data: lebih banyak hit cache dan preload yang lebih baik. Berjalan di sekitar objek yang tersebar dari memori membutuhkan waktu lebih lama. Fakta yang mudah adalah bahwa semua hash memiliki panjang yang sama, karena dihitung dengan satu algoritma. Pohon Merkle dalam array akan terlihat seperti ini:
Bukti
Saat Anda menginisialisasi pohon, Anda dapat membuat HashMap dengan semua indeks daun. Jadi, ketika tidak ada daun, tidak perlu mengelilingi seluruh pohon, dan jika ada, maka Anda dapat langsung pergi ke sana dan naik ke akar, membangun bukti. Dalam implementasi saya, saya membuat HashMap opsional.
Rangkaian dan Hashing
Tampaknya di sini dapat ditingkatkan? Bagaimanapun, semuanya jelas - ambil dua hash, rekatkan dan hitung hash baru. Tetapi kenyataannya adalah bahwa fungsi ini non-komutatif, yaitu hash (H0, H1) ≠ hash (H1, H0). Karena itu, ketika membuat bukti, Anda perlu mengingat sisi mana simpul tetangga berada. Ini membuat algoritma lebih sulit untuk diimplementasikan, dan menambahkan kebutuhan untuk menyimpan data yang berlebihan. Semuanya sangat mudah diperbaiki, cukup urutkan dua node sebelum hashing. Sebagai contoh, saya mengutip Tx2, dengan mempertimbangkan commutativity, cek akan terlihat seperti ini:
hash(hash(Hash2, Hash3), Hash01) = Root Hash
Saat Anda tidak perlu khawatir tentang pesanan, algoritme verifikasi terlihat seperti konvolusi array yang sederhana:
pub fn validate(&self, proof: &Vec<&[u8]>) -> bool { proof[2..].iter() .fold( get_pair_hash(proof[0], proof[1], self.algo), |a, b| get_pair_hash(a.as_ref(), b, self.algo) ).as_ref() == self.get_root() }
Elemen nol adalah hash dari objek yang diinginkan, yang pertama adalah tetangganya.
Ayo pergi!
Cerita itu tidak akan lengkap tanpa perbandingan kinerja, yang membuat saya beberapa kali lebih lama daripada implementasi pohon itu sendiri. Untuk tujuan ini, saya menggunakan kerangka kriteria . Sumber tes itu sendiri ada di sini . Semua pengujian dilakukan melalui antarmuka TreeWrapper , yang diterapkan untuk kedua subjek:
pub trait TreeWrapper<V> { fn create(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); fn find(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); fn validate(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); }
Kedua pohon bekerja dengan kriptografi cincin yang sama. Di sini saya tidak akan membandingkan perpustakaan yang berbeda. Saya mengambil yang paling umum.
Sebagai objek hash, string yang dihasilkan secara acak digunakan. Pohon dibandingkan pada susunan berbagai panjang: (500, 1000, 1500, 2000, 2500 3000). 2500 - 3000 adalah perkiraan jumlah transaksi di blok bitcoin saat ini.
Pada semua grafik, sumbu X menunjukkan jumlah elemen array (atau jumlah transaksi dalam blok), dan sumbu Y mewakili waktu rata-rata untuk menyelesaikan operasi dalam mikrodetik. Artinya, semakin buruk.
Pembuatan pohon
Penyimpanan semua data pohon dalam satu array sangat melebihi grafik kinerja objek. Untuk array dengan 500 elemen, 1,5 kali, dan untuk 3000 elemen sudah 3,6 kali. Sifat nonlinear dari ketergantungan kompleksitas pada volume input data dalam implementasi standar terlihat jelas.
Juga, sebagai perbandingan, saya menambahkan dua opsi untuk pohon vektor: dengan dan tanpa HashMap . Mengisi struktur data tambahan menambahkan sekitar 20%, tetapi memungkinkan Anda untuk mencari objek lebih cepat ketika membangun bukti.
Membangun bukti
Di sini Anda dapat melihat inefisiensi nyata dari pencarian secara mendalam. Dengan peningkatan input, itu hanya bertambah buruk. Penting untuk dipahami bahwa objek yang Anda cari adalah lembaran, sehingga tidak ada kerumitan log (n) . Jika data pra-hash, maka waktu operasi praktis tidak tergantung pada jumlah elemen. Tanpa hashing, kompleksitas tumbuh secara linear dan terdiri dari pencarian brute force.
Validasi bukti
Ini adalah operasi terakhir. Itu tidak tergantung pada struktur pohon, karena bekerja dengan hasil membangun bukti. Saya percaya bahwa kesulitan utama di sini adalah perhitungan hash.
Ringkasan
- Cara data disimpan sangat memengaruhi kinerja. Ketika semuanya dalam satu array jauh lebih cepat. Dan serialisasi struktur seperti itu akan sangat sederhana. Jumlah total kode juga dikurangi.
- Menyatukan node dengan penyortiran sangat menyederhanakan kode, tetapi tidak membuatnya lebih cepat.
Sedikit tentang Rust
- Menyukai kerangka kriteria . Ini menghasilkan hasil yang jelas dengan nilai rata-rata dan penyimpangan yang dilengkapi dengan grafik. Mampu membandingkan implementasi berbeda dari kode yang sama.
- Kurangnya warisan tidak terlalu mengganggu kehidupan.
- Macro adalah mekanisme yang kuat. Saya menggunakannya dalam tes pohon saya untuk parameterisasi. Saya pikir jika mereka digunakan dengan buruk, Anda dapat melakukan hal seperti itu sehingga Anda sendiri tidak akan bahagia nanti.
- Di beberapa tempat, kompiler bosan dengan pemeriksaan memorinya. Asumsi awal saya bahwa mulai menulis di Rust jadi tidak berhasil ternyata benar.
Referensi