Alat Kriptografi 101 - Penjelasan Fungsi Hash dan Pohon Merkle

Apa yang dibahas dalam artikel ini?

Blockchain memungkinkan manusia menyepakati berbagai hal tanpa memerlukan perantara. Alih-alih mengandalkan kepercayaan, blockchain mengandalkan bukti kriptografis. Primitif kriptografi digunakan untuk menyediakan bukti tersebut. Namun, apa sebenarnya primitif kriptografi itu?

Dalam artikel ini, kita akan membahas dua primitif kriptografi yang sangat penting bagi bukti kriptografis di blockchain: fungsi hash dan pohon Merkle. Kita akan mempelajari mekanisme inti fungsi hash, memahami pentingnya fungsi tersebut bagi blockchain, dan mempelajari pointer hash. Kemudian, kita akan membahas pohon Merkle tradisional dan konkuren serta menjelaskan peran pentingnya bagi Solana.

Apa itu primitif kriptografi?

Primitif kriptografi adalah operasi atau algoritma yang menjadi dasar untuk membangun protokol dan sistem kriptografi. Hubungan primitif kriptografi dengan protokol kriptografi ibarat atom dengan molekul—primitif merupakan komponen penyusun solusi yang lebih kompleks. Generator angka acak, skema komitmen, dan kriptografi kunci publik merupakan contoh primitif kriptografi.

Jika digunakan sendiri, kemampuan primitif kriptografi cukup terbatas. Jika digabungkan, primitif kriptografi dapat menyediakan fungsi keamanan dasar seperti autentikasi, kerahasiaan, dan integritas. Menggabungkan primitif kriptografi merupakan proses yang sangat rumit serta memerlukan perencanaan cermat dan pemahaman mendalam tentang interaksi antarmasing-masing primitif. Dalam proses ini, Anda harus memperhatikan pertimbangan keamanan sesuai dengan tujuan keamanan yang ingin dicapai. Metode untuk menggabungkan primitif kriptografi secara umum dapat dikategorikan sebagai berikut:

• Komposisi sekuensial: Menerapkan satu primitif setelah primitif lainnya (misalnya, perantaian hash)
• Komposisi paralel: Menggunakan primitif secara bersamaan dan independen (misalnya, mengenkripsi dan melakukan hash pada data secara bersamaan)
• Komposisi hierarkis: Menggunakan suatu primitif kriptografi di dalam primitif lain (misalnya, pohon Merkle)

Memahami definisi primitif kriptografi, cara kerjanya, dan berbagai detail dalam proses penggabungannya akan membantu Anda memahami serta merancang sistem yang aman dan efisien. Salah satu primitif kriptografi yang paling sering digunakan dan digabungkan adalah fungsi hash.

Apa itu fungsi hash?

Fungsi hash adalah fungsi kriptografis yang menerima data berukuran berapa pun dan menghasilkan nilai berukuran tetap. Nilai yang dihasilkan fungsi ini disebut digest atau hash. Algoritma hashing yang populer meliputi: SHA-1, SHA-2, SHA-3, MD5, dan Argon2. Fungsi hash digunakan di seluruh bagian blockchain. Karena itu, Anda harus memahami definisi dan cara kerjanya.

Analogi Sederhana

Bayangkan Anda sedang membuat kue cokelat mewah. Kue tersebut memiliki beberapa lapisan yang masing-masing dibuat dengan bahannya sendiri. Saat Anda memanggang, teman Anda mengirim pesan dan menanyakan apa yang sedang Anda lakukan. Menjelaskan secara terperinci cara Anda membuat kue tersebut beserta semua bahan yang digunakan tentu cukup merepotkan. Sebagai gantinya, Anda memutuskan untuk mengirimkan foto kue cokelat tersebut.

Dalam contoh ini, foto kue berfungsi sebagai hash—representasi sederhana dan ringkas dari sesuatu yang jauh lebih kompleks. Teman Anda tidak akan mengetahui setiap bahan yang digunakan untuk membuat kue tersebut, tetapi ia akan mendapat gambaran yang jelas tentang apa yang baru saja Anda buat. Misalnya, kue cokelat Anda dihiasi rasberi. Jika rasberi tersebut diambil atau diganti dengan stroberi, foto kue Anda akan terlihat sangat berbeda dari hasil akhirnya. Demikian pula, setiap perubahan pada data yang di-hash akan menghasilkan nilai hash baru.

Karakteristik Fungsi Hash Kriptografis yang Baik

Definisi fungsi hash yang diberikan sebelumnya memang dapat menyesatkan. Fungsi hash bisa saja menghasilkan hash dengan ukuran yang bervariasi. Fungsi tersebut juga bisa menghasilkan hash yang sama untuk dua input berbeda. Selain itu, seseorang mungkin dapat dengan sangat mudah merekayasa balik hash untuk menemukan input aslinya. Definisi sebelumnya sebenarnya menjelaskan fungsi hash kriptografis yang baik. Namun, apa yang membuat suatu fungsi hash kriptografis dapat dianggap baik?

Fungsi hash yang baik bersifat deterministik—input yang sama akan selalu menghasilkan output yang sama. Jika saya melakukan hash pada input “baseball”, fungsi hash tersebut akan selalu menghasilkan hash yang sama di sistem apa pun. Ini juga berarti bahwa ukuran hash akan tetap sama, berapa pun ukuran inputnya. Hal ini penting untuk efisiensi pemrosesan dan penyimpanan data. Kepastian bahwa input unik akan selalu menghasilkan output unik dan bahwa output tersebut selalu berukuran tetap merupakan indikator jelas dari fungsi hash kriptografis yang baik.

Fungsi hash yang baik tahan terhadap preimage. Artinya, merekayasa balik nilai input berdasarkan hash-nya tidak layak dilakukan secara komputasional. Jadi, jika seseorang memberi Anda sebuah hash, Anda seharusnya tidak dapat mengetahui data yang menghasilkan hash tersebut. Hal ini juga mengarah pada gagasan bahwa dua kumpulan data yang berbeda tidak boleh menghasilkan hash yang sama. Fungsi hash yang baik disebut tahan terhadap collision jika dua input tidak pernah menghasilkan hash yang sama.

Fungsi hash yang baik mengikuti Efek Avalanche—perubahan kecil pada input harus menghasilkan hash yang sangat berbeda. Mengubah satu karakter saja harus menghasilkan hash yang sepenuhnya berbeda. Karena itu, output hash tidak boleh mengungkapkan informasi apa pun tentang input atau memiliki pola yang dapat dikenali. Perhatikan perbedaan hash pada gambar di atas. Rubah merah yang “berlari” menghasilkan hash yang sangat berbeda dibandingkan rubah merah yang “berjalan”. Tidak ada pula indikasi bahwa kedua hash tersebut memuat informasi yang hampir identik.

Fungsi hash yang baik harus dapat dihitung dengan cepat. Fungsi hash yang lambat tidak praktis untuk komputasi real-time atau mendekati real-time, seperti verifikasi transaksi. Fungsi hash yang lambat dapat menjadi hambatan serius yang membatasi kapasitas pemrosesan dan performa jaringan. Fungsi hash yang cepat diperlukan agar blockchain dapat beroperasi secara efisien dan aman.

Mengapa hal ini penting bagi blockchain?

Blockchain adalah ledger terdesentralisasi dan terdistribusi yang mencatat transaksi di seluruh jaringannya. Transaksi tersebut dikelompokkan ke dalam blok yang ditautkan secara aman melalui fungsi hash yang baik. Setiap blok memuat data transaksi, stempel waktu, dan hash dari blok sebelumnya. Karena hash setiap blok bergantung pada hash blok sebelumnya, setiap perubahan pada isi suatu blok akan mengubah hash-nya dan membuat semua blok berikutnya tidak valid. Proses penggunaan hash sebelumnya dalam pembuatan hash baru ini dikenal sebagai perantaian hash.

Penambahan blok baru ke blockchain disebut konfirmasi. Konfirmasi memverifikasi dan mengamankan semua transaksi dalam blok baru serta seluruh blok sebelumnya. Alasannya, setiap konfirmasi baru membuat blok sebelumnya semakin sulit diubah. Untuk mengubah blok sebelumnya, penyerang harus menghitung ulang semua hash sebelumnya. Dengan demikian, perantaian hash memastikan bahwa blockchain tidak mungkin diubah setelah suatu blok memiliki cukup banyak konfirmasi.

Sederhananya, blockchain adalah rantai blok yang diamankan melalui fungsi hash. Namun, bagaimana tepatnya kita menunjuk dari satu blok ke blok lainnya? Fungsi hash kriptografis memang digunakan untuk merangkai blok, tetapi bagaimana kita dapat melihat data dari blok sebelumnya? Bukankah fungsi hash kriptografis yang baik seharusnya tahan terhadap preimage?

Apa itu pointer hash?

Pointer adalah variabel yang menyimpan lokasi tempat data tertentu disimpan dalam memori. Data di alamat memori ini dapat diakses dengan mudah karena pointer “menunjuk ke” lokasi data tersebut. Pointer hash adalah struktur data yang mirip dengan pointer, tetapi juga memuat hash kriptografis dari data yang dirujuk. Dengan demikian, pointer hash memberi tahu Anda lokasi untuk mengakses data tertentu sekaligus memungkinkan Anda memeriksa integritas data yang diakses.

Struktur blockchain dapat dijelaskan secara lebih akurat sebagai linked list yang menggunakan pointer hash. Hash dari blok sebelumnya merupakan pointer hash yang menunjuk ke sekumpulan transaksi dan hash dari semua transaksi tersebut. Pointer hash memfasilitasi penautan blok, menjaga integritas setiap blok, dan memverifikasi bahwa blok yang baru ditambahkan mengikuti blok sebelumnya dengan benar.

Pointer hash digunakan untuk merangkai blok secara efisien. Namun, bagaimana dengan transaksi di dalam blok? Jika sebuah blok memuat seribu transaksi, bukankah memverifikasi setiap transaksi satu per satu akan memerlukan banyak sumber daya?

Apa itu pohon Merkle?

Pohon Merkle adalah struktur data yang digunakan untuk mengatur dan memverifikasi kumpulan data berukuran besar. Data disusun dalam struktur menyerupai pohon, dengan setiap daun atau simpul diberi label berupa hash dari sekumpulan data. Setiap simpul non-daun merupakan hash dari simpul turunannya. Pohon Merkle digunakan untuk memverifikasi transaksi yang disertakan dalam blok tertentu dan disebarkan ke blockchain. Jadi, bagaimana cara kerjanya?

Transaksi dikelompokkan dalam sebuah daftar untuk membentuk blok. Setiap transaksi dalam daftar di-hash menggunakan fungsi hashing yang baik. Hash tersebut berfungsi sebagai simpul daun. Simpul daun ini di-hash secara berpasangan untuk membuat lapisan hash baru. Proses ini terus dilakukan secara iteratif hingga hanya tersisa satu hash yang disebut root Merkle. Root Merkle disimpan dalam header blok dan berfungsi sebagai sidik jari digital dari semua transaksi dalam blok tersebut. Kita juga dapat menyebut root Merkle sebagai hash blok. Jadi, ketika kita mengatakan bahwa blok baru ditautkan ke blok sebelumnya menggunakan blockhash blok sebelumnya, artinya blok tersebut menggunakan root Merkle blok sebelumnya sebagai bagian dari hash blok baru.

Pohon Merkle membuat verifikasi transaksi individual dalam sebuah blok menjadi efisien. Secara tradisional, Anda harus memverifikasi setiap transaksi untuk memverifikasi satu transaksi tertentu. Proses ini mahal dan memakan waktu. Pohon Merkle menyediakan “jalan pintas” kriptografis untuk membantu proses verifikasi ini, yang dikenal sebagai bukti Merkle. Bukti Merkle adalah jalur dari simpul daun transaksi hingga ke root Merkle. Dengan menggunakan gambar di atas, bayangkan jalur dari Data A menuju root Merkle. Jalur ini juga mencakup sibling node, yaitu daun yang bersebelahan dengan setiap simpul pada jalur, tetapi bukan merupakan bagian dari jalur itu sendiri. Pemverifikasi dapat menghitung hash menggunakan jalur bukti untuk memeriksa apakah hash yang dihitung cocok dengan root Merkle. Jika hash yang dihasilkan cocok, pemverifikasi dapat meyakini bahwa transaksi tersebut sah dan belum dimanipulasi.

Daun dapat diubah dengan melakukan hash pada data daun baru dan menghitung ulang root Merkle. Root Merkle baru ini digunakan untuk memverifikasi perubahan baru dan membuat bukti sebelumnya tidak valid. Dalam jaringan berkapasitas pemrosesan tinggi seperti Solana, validator dapat menerima permintaan perubahan pada pohon Merkle on-chain secara berurutan dengan sangat cepat (misalnya, dalam slot yang sama). Setiap perubahan data harus dihitung ulang secara sekuensial. Jika tidak, setiap permintaan perubahan berikutnya akan dibuat tidak valid oleh permintaan perubahan sebelumnya dalam slot tersebut. Mengubah data daun dan menghitung root Merkle baru sangat umum dilakukan dalam blockchain. Jadi, bagaimana kita menangani perubahan yang terjadi dengan cepat?

Apa itu pohon Merkle konkuren?

Pohon Merkle konkuren adalah pohon Merkle yang dioptimalkan untuk operasi baca dan tulis secara bersamaan. Pohon ini menyimpan changelog aman yang mencatat perubahan terbaru, hash root-nya, dan bukti untuk mendapatkannya. Changelog ini disimpan secara on-chain dalam account khusus untuk pohon tersebut, dengan jumlah maksimum perubahan yang dapat dilakukan selama root Merkle masih valid. Jumlah maksimum perubahan ini disebut maxBufferSize. Dengan demikian, ketika validator menerima permintaan perubahan pada pohon Merkle on-chain secara berurutan dengan sangat cepat, validator dapat menggunakan changelog ini sebagai sumber kebenaran yang memungkinkan hingga maxBufferSize perubahan pada pohon dalam slot yang sama.

Pohon Merkle konkuren menyempurnakan pohon Merkle tradisional sehingga cocok untuk lingkungan berkapasitas pemrosesan tinggi seperti Solana. Untuk membuat pohon Merkle konkuren secara on-chain di Solana, terdapat tiga properti yang memengaruhi ukuran pohon, biaya pembuatannya, dan jumlah perubahan konkuren pada pohon tersebut:

• Kedalaman maksimum
• Ukuran buffer maksimum
• Kedalaman canopy

Kedalaman maksimum merujuk pada jumlah lompatan maksimum yang diperlukan untuk mencapai root Merkle dari daun mana pun. maxDepth digunakan untuk menentukan jumlah maksimum simpul yang disimpan dalam pohon. Nilai ini dapat dihitung menggunakan rumus: numberOfNodes = 2 ^ maxDepth. Kedalaman pohon harus ditetapkan saat dibuat. Karena itu, penting untuk menggunakan rumus ini guna menentukan jumlah data yang ingin Anda simpan di dalam pohon.

Seperti yang telah dijelaskan, ukuran buffer maksimum merujuk pada jumlah maksimum perubahan yang dapat dilakukan pada pohon selama root Merkle-nya masih valid.

Kedalaman canopy merujuk pada subset pohon Merkle yang disimpan secara on-chain. Bukti yang di-cache ini digunakan untuk memeriksa hash terhadap root Merkle on-chain. Jalur bukti lengkap harus digunakan untuk memverifikasi kepemilikan asli suatu daun saat melakukan operasi tulis pada daun tersebut. Misalnya, Anda perlu menulis ke pohon saat mentransfer NFT. Canopy memungkinkan Anda mengurangi ukuran bukti dan menghindari penggunaan ukuran bukti sebesar maxDepth untuk memverifikasi pohon. Pohon dengan maxDepth sebesar 20 akan memerlukan ukuran bukti sebesar 20. Dengan canopy sebesar 15, hanya ukuran bukti sebesar 5 yang perlu dikirimkan untuk setiap transaksi tulis. Dengan demikian, kedalaman canopy yang lebih tinggi membuat Anda membayar biaya awal yang lebih besar agar dapat mengirimkan bukti yang lebih kecil di kemudian hari.

Kedalaman canopy merupakan faktor utama yang menentukan biaya pembuatan pohon. Alasannya, semakin tinggi kedalaman canopy, semakin besar account yang diperlukan. Developer dapat menggunakan package @solana/spl-account-compression untuk menghitung ruang yang diperlukan bagi ukuran pohon tertentu dan biaya untuk mengalokasikan ruang yang diperlukan bagi pohon secara on-chain. Developer dapat menggunakan fungsi getConcurrentMerkleTreeAccountSize untuk menghitung ruang yang diperlukan bagi account tertentu berdasarkan parameternya, lalu menggunakan getMinimumBalanceForRentExemption pada ruang yang diperlukan untuk mendapatkan biaya akhir dalam Lamport.

Solana menggunakan pohon Merkle konkuren untuk kompresi state. Kompresi state adalah metode untuk membuat hash dari data off-chain dan menyimpannya secara on-chain agar dapat diverifikasi dengan aman. Kasus penggunaan kompresi state yang paling populer adalah NFT terkompresi karena metode ini secara drastis mengurangi biaya minting. Sebagai contoh, minting satu miliar NFT di Solana akan memerlukan biaya 507 $SOL, dibandingkan dengan 12 000 000 $SOL menggunakan NFT “reguler”. Setelah memahami hashing dan pohon Merkle dengan baik, kita akan membahas NFT terkompresi dalam artikel mendatang!

Kesimpulan

Selamat! Dalam artikel ini, kita telah menganalisis fungsi hashing dan pohon Merkle, dua primitif kriptografi yang sangat penting bagi blockchain. Memahami blockchain bukanlah hal mudah—blockchain adalah sistem terdistribusi kompleks yang memerlukan pemahaman teknis luas. Sering kali, developer, pengguna, atau investor pada umumnya dianggap sudah memiliki pengetahuan ini. Artikel ini tidak mengasumsikan adanya pengetahuan sebelumnya tentang primitif kriptografi. Sebaliknya, kita memulai dari dasar sebelum beralih ke pembahasan yang lebih kompleks mengenai pohon Merkle tradisional dan konkuren. Pemahaman mendasar ini sangat penting sebelum kita mendalami topik yang lebih kompleks, seperti NFT terkompresi. Dengan pengetahuan baru ini, Anda akan lebih siap menjelajahi codebase atau mengikuti diskusi mengenai primitif kriptografi dan solusi kriptografis yang lebih kompleks.

Jika Anda sudah membaca sejauh ini, anon, terima kasih!

Referensi Tambahan / Bacaan Lebih Lanjut

• Bab buku terperinci tentang primitif kriptografi
• Artikel yang membandingkan algoritma hashing aman
• Algoritma Hashing dan Keamanan - Video YouTube oleh Computerphile
• Video YouTube ringkas tentang pohon Merkle
• Mempelajari Kompresi NFT di Solana