Sifat dan Fungsi Hash

Seperti yang sudah disinggung sebelumnya, bahwa fungsi hash kriptografi ini sudah lama ada dan dianggap sebagai kriptografi primitif. Untuk itu, yang perlu pertama kali kita ketahui adalah tentang Fungsi Hash Kriptografi. Fungsi Hash adalah fungsi matematika dengan tiga sifat berikut ini: ⦁ Input bisa dari berbagai macam ukuran string.

⦁ Menghasilkan output dengan ukuran yang tetap

⦁ Efisien dalam komputansi. Hal ini berarti, setiap ada masukan input string, bisa mengkonfigurasi output fungsi hash dalam jumlah waktu yang wajar. Teknisnya, komputasi hash pada sebuah string n-bit harus mempunyai timing waktu, yakni O (n) (Notasi big 0 ).

Sifat-sifat tersebut menggambarkan fungsi hash secara umum. Dan bisa digunakan untuk membangun struktur data seperti halnya tabel hash. Agar Fungsi hash bisa menjadi kriptografi yang aman, maka perlu ditambahkan beberapa sifat tambahan, yakni:

Sifat 1: collision‐resistance

Sifat 2: hiding

Sifat 3: puzzle‐friendliness.

Lebih jauh, kita akan melihat detail masing-masing sifat tambahan tersebut untuk mengetahui mengapa itu diperlukan. Bagi yang sudah mempelajari kriptografi, perlu memperhatikan dan menyadari bahwa penerapan fungsi hash ini sedikit berbeda dari teks kriptografi yang ada pada umumnya. Misalkan pada sifat puzzle-friendliness, tidak menjadi persyaratan umum dalam fungsi hash kriptografi. Namun itu diperlukan untuk cryptocurrency tertentu.

Sifat 1: Collision‐resistance.​

Sifat pertama yang dibutuhkan adalah Collision-Resistance. Secara harfiah, collision-resistance ini berarti resistansi saat terjadi benturan atau bertabrakan. Collision atau benturan ini terjadi jika dua input yang berbeda dan terpisah menghasilkan output yang sama. Fungsi hash H (.) menjadi collision-resistance, jika tidak ada yang menemukan collision (baca lebih lanjut untuk penjelasan tentang ini).

Collision-resistance: Sebuah fungsi hash H dikatakan collision resistant, jika tidak bisa untuk menemukan dua nilai, x dan y, sehingga x ≠ y, namun H (x) = H (y).

kolusi hash

Pada gambar tersebut kita lihat, x dan y adalah nilai yang berbeda dan terpisah, namun ketika dimasukkan kedalam fungsi hash H, mereka menghasilkan output yang sama.

Pada dasarnya, collision ini terjadi dan memang ada. Hal ini bisa dibuktikan dengan melakukan perhitungan argumen secara sederhana. Karena ruang input lebih besar daripada ruang output. Dan kenyataannya, memang ruang input ini tidak terbatas, sedangkan ruang output terbatas. Sehingga harus ada input string yang memetakan kedalam output dengan string yang sama.

output

Jumlah input melebihi jumlah output, oleh karena itu bisa dilogikakan setidaknya ada satu output fungsi hash yang memetakan lebih dari satu input.

Ada sebuah metode yang bisa menjamin untuk bisa menemukan collision. Metode sederhana yang bisa digunakan untuk menemukan collision fungsi hash dengan ukuran 256-bit, ukuran output 2256 + 1 nilai yang berbeda. Lalu komputasi masing-masing, kemudian cek apakah ada output yang sama. Ketika kita memilih input yang lebih besar daripada output, maka beberapa pasangan pasti bertabrakan ketika menerapkan fungsi hash.

Selanjutnya, jika kita memilih input secara acak dan kemudaian mengkomputasi nilai hash. Maka kita akan menemukan sebuah collision dengan probabilitas yang tinggi sebelum menguji input 2256 + 1. Bahkan. Jika kita secara acak memilih hanya input 2130 + 1, ada 99,8% kemungkinan bahwa dua dari itu akan bertabrakan.

Kenyataan bahwa kita bisa menemukan collision hanya dengan memeriksa kurang lebih akar pangkat dua jumlah kemungkinan hasil output pada fenomena probabilitas ini, disebut dengan istilah birthday paradox.

Algoritma pendeteksi collision ini bekerja pada setiap fungsi hash. Namun, membutuhkan waktu yang cukup lama. Untuk fungsi hash dengan output 256-bit, harus dikomputasi fungsi hash input 2256 +1 kali dalam kondisi yang buruk, dan sekitar 2128 kali pada kondisi rata-rata. Jumlah tersebut adalah jumlah yang besar. Jika sebuah komputer mengkalkulasi 10.000 hash per detik, akan membutuhkan waktu kurang lebih satu octillion (1027) tahun untuk mengkalkulasi 2128 hash.

Sebuah analogi untuk hal ini, misalkan jika setiap komputer yang pernah dibuat manusia digunakan untuk mengkomputasi seluruh alam semesta hingga sampai saat ini, maka kemungkinan untuk menemukan collision cukup kecil. Saking kecilnya kemungkinan tersebut, ibarat kemungkinan bahwa bumi akan hancur oleh meteor besar selang dua detik berikutnya.

Jadi, kita telah melihat algoritma pendeteksi collision tersebut, meskipun secara teknis cukup sulit untuk dipraktekkan karena waktu yang dibutuhkan cukup lama. Ada sebuah pertannyaan lanjutan, masih adakah algoritma lain yang lebih efisien untuk menemukan collision fungsi hash tertentu?

Coba kita melihat sebuah fungsi hash berikut:

h(x) = x mod 2256

Fungsi tersebut memenuhi persyaratan fungsi hash karena bisa menerima input berbagai ukuran, kemudian menghasilkan sebuah output dengan ukuran yang tetap, yakni 256 bit, dan lebih efisien. Fungsi tersebut hanya menghasilkan output 256 bit. Satu collision maka akan menjadi nilai 3, dan 3+2256. Meskipun tidak bisa dipraktekkan, setidaknya ada beberapa fungsi hash yang bisa mendeteksi collision. Dalam beberapa kasus, seperti pada fungsi hash MD5 yang lama, collision akhirnya ditemukan setelah beberapa tahun kemudian.

Setelah mengetahui apa yang dimaksud dengan collision-resistance, pertanyaan selanjutnya adalah, apa fungsi dan kegunaan collision-resistance itu? Ada sebuah aplikasi yang jika kita mengetahui ada dua input, yakni input x, dan input y untuk fungsi hash H adalah berbeda. Maka, cukup aman untuk mengambil asumsi, bahwa hash H(x) dan H(y) berbeda. Sementara jika seseorang mengetahui bahwa x dan y tersebut berbeda namun memiliki hash yang sama, maka akan melanggar asumsi bahwa H adalah collision resistant.

Sehingga dalam argumen ini, kita bisa menggunakan output hash tersebut sebagai message digest. Message digest ini merupakan angka yang dikalkulasi dari sistem informasi lewat fungsi kriptografi. Selanjutnya, angka ini digunakan untuk memverifikasi integritas data informasi. Segala perubahan pada informasi meskipun kecil akan menghasilkan message digest yang jauh berbeda.

Coba kita perhatikan dalam sebuah securebox, sebuah penyimpanan file online yang memungkinkan penggunanya untuk bisa mengupload file dan memastikan integritas filenya saat file tersebut di download. Misalnya Nita mengupload sebuah file dengan ukuran yang cukup besar, kemudian hendak memferifikasi file tersebut. Sehingga ketika Nita ingin mendownload file tersebut, sama persis ketika file tersebut dia upload. Untuk bisa melakukannya, dengan menyimpan file berukuran bersar tersebut, kemudian membandingkannya pada saat Nita mendownload. Jika Nita ingin untuk mempunyai akses ke local untuk memastikan integritas filenya, Nita bisa secara langsung mengcopy file itu.

Hash collision-free memberikan efisiensi pemecahan masalah ini secara elegan. Nita hanya perlu untuk mengingat hash dari file aslinya itu. Saat ia mendownload, Nita mengkomputasi hash file lantas membandingkannya pada saat ia menaruh file itu. Jika hash sama, maka Nita bisa menyimpulkan bahwa file itu adalah file yang sama. Namun jika hasilnya berbeda, maka Nita menyiimpulkan bahwa file miliknya telah dirusak.

Yang perlu diingat bahwa hash tersebut memungkinkan Nita untuk mendeteksi file corrupt yang terjadi secara sengaja selama proses transmisi atau pada server securebox. Tapi bisa juga karena dimodifikasi secara sengaja oleh server untuk melindungi dari adanya malicious.

Dalam hal ini, server hash berfungsi sebagai panjang digest, atau ringkasan pesan yang tidak ambigu. Memberikan cara yang efisien atas beberapa hal yang kita lihat sebelumnya. Keseluruhan ukuran file bisa mencapai gigabyte, sedangkan panjang hash tetap 256-bit. Sehingga bisa mengurangi kebutuhan penyimpanan file.


Hiding-Sifat Tambahan Kedua

Sifat 2: HIDING

Sifat kedua dari fungsi hash yang kita bahas adalah Hiding. Sifat hiding ini menjelaskan bahwa jika kita diberi output dari fungsi hash y = H (x), tidak ada cara yang bisa dipakai untuk mencari tahu input x itu. Karena sifat ini tidak mungkin “true” dalam bentuk lain. Perhatikan contoh sederhana berikut: Misalkan kita melempar sebuah koin. Jika hasil dari lemparan koin itu menunjukkan kepala, kita akan mengumumkan hash dari string “kepala”. Jika hasilnya adalah ekor, kita akan mengumumkan hash dari string “ekor”.

Selanjutnya kita meminta kepada seseorang yang tidak melihat saat koin dilempar. Hanya melihat hasil lemparan koin saja. Kemudian memintanya untuk mencari hash stringnya. Hasilnya, orang tersebut akan menghitung dan mengkalkulasi kedua string hash “kepala, dan juga “ekor”. Setelah itu baru orang itu bisa melihat inputnya.

Seorang yang berniat buruk bisa menebak string karena hanya terdapat dua kemungkinan nilai x. Dan dengan mudah bagi orang itu untuk mencoba menguji dua kemungkinan itu. Maka, agar bisa mencapai sifat hiding ini, dibutuhkan dalam kasus seperti ini untuk menyembunyikan nilai kemungkinan x. Artinya, nilai x harus dipilih dari satu set kemungkinan yang paling banyak keluar. Jika nilai x sudah dipilih dari set tersebut, maka dengan metode ini mencoba agar beberapa nilai baru x yang cenderung tidak bisa berjalan.

Pertanyaannya kemudian, bisakah sifat hiding ini dicapai saat ketika nilai yang kita inginkan tidak keluar dari set yang kita pilih, seperti contoh pada kemungkinan “kepala”, dan “ekor” tersebut? Ya, sifat hiding ini bisa dicapai. Kita memungkinkan untuk bisa menyembunyikan sebuah input yang tidak menyebar itu, dengan menggabungkan input lain yang sudah menyebar. Jadi kita sekarang sudah mengetahui makna dari sifat hiding ini. (vertikal bar ganda ‖ yang menunjukkan Rangkaian).

Hiding – Sebuah fungsi hash H bersifat hiding, jika nilai tersembunyi dari r dipilih dari pendistribusian kemungkinan yang memiliki nilai min-entropy tinggi, kemudian diberi H (r ‖ x). Sehingga tidak bisa untuk menemukan x.

Secara teori, min-entropi adalah ukuran dari beberapa hasil prediksi. Min-entropi tinggi menangkap distribusi variavel acak yang cukup menyebar. Secara khusus, hal itu berarti ketika kita mengambil contoh sebuah distribusi, tidak ada nilai tertentu yang terjadi. Lebih konkritnya, misal jika r dipilih seragam dari semua string yang memiliki panjang 256 bit, maka setiap string tersebut dipilih dengan probabillitas 1/2256. Nilai itu merupakan nilai yang kecil.

Application: Commitments

Secara khusus, yang ingin kita lakukan adalah sesuatu yang biasa disebut dengan commitments (komitmen). Sebuah komitmen adalah analog digital yang mengambil nilai, kemudian menyegel seperti menyegel sebuah amplop. Lalu, menempatkan amplop itu diatas meja sehingga orang lain dapat melihatnya. Jika seseorang melakukan hal tersebut, berarti orang tersebut telah berkomitmen dengan isi yang ada di dalam amplop tersebut. Sedangkan anda belum membuka amplop itu. Sehingga nilai itu tetap bersifat rahasia. Selanjutnya, dapat membuka ampop itu dan mengungkapkan nilai yang sudah disegel sebelumnya.

Skema komitmen terdiri dari dua algoritma:

⦁ com: = komit (msg, Nonce) fungsi komit mengambil pesan dan nilai acak dan rahasia, atau disebut dengan “Nonce“, sebagai input dan menghasilkan komitmen.

⦁ verify (com, msg, Nonce) Fungsi verifikasi mengambil komitmen, Nonce, dan pesan input. Lalu akan menghasilkan statement true jika com == komit (msg, Nonce) dan false jika yang terjadi sebaliknya.

Membutuhkan dua sifat pengamanan:

⦁ Hiding: pemberian com, tidak mungkin untuk menemukan msg

⦁ Binding: tidak bisa menemukan dua pasang (msg, Nonce) dan (msg ‘, Nonce’). Seperti halnya msg ≠ msg ‘, dan komit (msg, Nonce) == komit ( msg ‘, Nonce’).

Penggunaan skema komitmen perlu untuk generate nonce secara acak terlebih dahulu. Setelah itu menerapkan fungsi komitmen untuk Nonce ini bersama-sama dengan msg. Lantas mempublikasikan com komitmen. Pada tahapan ini, analog berfungsi untuk menempatkan amplop tertutup yang sudah tersegel itu di atas meja.

Jika kita ingin mengungkapkan nilai yang tertetup dan tersegel amplop tersebut, maka dilakukan dengan menerbitkan nonce acak dan pesan yang telah digunakan saat membuat komitment tersebut. Sekarang, siapapun dapat memverifikasi msg itu. Tahap berikutnya, analog membuka amplop itu. Setiap seseorang memberikan komitmen terhadap sebuah nilai, cukup penting untuk memilih nilai nonce secara acak. Dalam kriptografi, istilah Nonce digunakan untuk sebuah nilai yang hanya dapat digunakan sekali saja.

Dua sifat pengaman tersebut memerintahkan algoritma untuk menyegel dan membuka amplop. Pertama, memberikan com, dan komitmen. Jika seseorang yang ingin melihat amplop tidak bisa melihat isi pesannya, maka sifat kedua dari pengaman tersebut yang berfungsi sebagai pengikat. Hal ini berfungsi untuk memastikan bahwa seseorang yang sudah memberikan komitmen pada sebuah nilai, hal itu tidak dapat dirubah lagi. Karena tidak bisa menemukan dua isi pesan yang berbeda. Sehingga pemberian komitmen hanya bisa dilakukan untuk satu pesan saja. Kemudian mengklaim untuk pesan yang lain.

Sedangkan untuk bisa mengetahui bahwa dua sifat ini ada, kita bisa melakukannya dengan menggunakan fungsi hash. Contoh dengan skema komitmen berikut:

commit (msg, Nonce): = H (Nonce ‖ msg) nonce tersebut adalah nilai acak 256-bit.

Dalam memberikan commit pada sebuah pesan, generate dulu nonce acak 256-bit tersebut. Kemudian menggabungkan nonce dan pesan untuk menghasilkan hash dari nilai yang sudah digabung itu menjadi sebuah komitmen. Untuk bisa memverifikasi, seseorang akan menghitung hash yang sama dari nonce itu. Kemudian memeriksa apakah hasilnya sama dengan yang dilihatnya.

Mari kita melihat dua sifat yang membutuhkan komitmen berikut. Jika kita mengganti instalasi commit dan memverifikasi seperti halnya H (Nonce ‖ msg) untuk com. Maka sifat ini akan menjadi:

⦁ Hiding: Pemberian H (Nonce ‖ msg), tidak mungkin untuk menemukan msg

⦁ Binding: Tidak bisa menemukan dua pasang (msg, Nonce) dan (msg ‘, Nonce’). Sehingga msg ≠ msg’ dan H (Nonce ‖ msg) == H ( Nonce ‘‖ msg’)

Sifat hiding dari komitmen ini sebetulnya adalah sifat hiding yang membutuhkan fungsi hash. Jika key yang dipilih menggunakan nilai acak 256-bit, kemudian mengatakan bahwa, jika kita menggabungkan key dan pesan tersebut, maka tidak bisa untuk memulihkan pesan hasil ouput hashnya. Ternyata, sifat binding tersebut terimplikasi oleh collision-resistant dari fungsi hash yang mendasarinya. Jika fungsi hash adalah collision-resistant, maka akan bisa untuk menemukan perbedaan nilai msg dan msg‘. Sehingga H (Nonce ‖ msg) = H (Nonce’ ‖ msg ‘) karena nilai tersebut memang akan menjadi collision.



Puzzle‐Friendliness Sifat Tambahan Ketiga


Sifat 3: Puzzle‐Friendliness

Sifat tambahan selanjutnya adalah Puzzle‐Friendliness. Teknisnya kita akan mencari tahu persyaratan apa yang dibutuhkan agar bisa dipergunakan. Selanjutnya memberikan ilustrasi mengapa sifat puzzle-friendliness ini cukup berguna.
Puzzle‐friendliness

Sebuah fungsi hash H dikatakan memiliki sifat puzzle-friendliness jika setiap kemungkinan output n-bit bernilai y, dan jika k dipilih dari distribusi dengan min-entropi tinggi, maka tidak bisa untuk menemukan x sehingga H (k ‖ x) = y pada waktu yang secara signifikan kurang dari 2n.

Artinya adalah, jika seseorang ingin menargetkan fungsi hash agar bisa keluar di beberapa nilai output tertentu y, maka ada bagian dari input yang dipilih dengan acak itu menjadi sangat sulit untuk bisa menemukan nilai lain yang bisa sama persis seperti target.

Aplikasi: Search puzzle.

Sekarang kita coba untuk mempertimbangkan sebuah aplikasi yang menggambarkan kegunaan sifat ini. Dalam aplikasi ini, kita akan coba membangun sebuah pencari puzzle. Sebuah masalah matematika yang membutuhkan ruang besar untuk bisa menemukan solusinya. Secara khusus, pencari puzzle ini tidak memiliki shortcut (jalan pintas). Artinya, tidak ada cara untuk menemukan solusi valid selain mencari ruang besar itu.

Pencari puzzle. terdiri dari:

⦁ fungsi hash, H,

⦁ nilai, id (yang kita sebut puzzle-ID), dipilih dari distribusi min-entropi tinggi

⦁ dan target yang ditetapkan Y

Solusi untuk teka-teki ini adalah nilai x, sehingga H (id ‖ x) ∈ Y

Jika H memiliki output n-bit, maka dapat mengambil dari nilai-nilai 2n. Dalam memecahkan teka-teki butuh untuk bisa menemukan sebuah input. Sehingga output bisa termasuk dalam set Y, yang biasanya berukuran lebih kecil dari semua himpunan output lainnya. Ukuran Y ditentukan dari seberapa rumit puzzle tersebut. Sementara, jika Y adalah semua himpunan string n-bit yang tidak terlalu rumit, sedangkan Y hanya memiliki 1 elemen puzzle, maka menjadi cukup sulit. Fakta bahwa id puzzle dengan min-entropy tinggi memasikan agar tidak ada shortcut. Sebaliknya, jika nilai tertentu dari ID memungkinkan, maka seseorang berpeluang untuk melakukan kecurangan. Misalnya melakukan pra komputansi memecahkan puzzle dengan menggunakan ID tersebut.

Jika pencari puzzle itu bersifat puzzle-friendliness, implikasinya tidak ada pemecahan puzzle yang jauh lebih baik daripada menggunakan nilai acak x. Dan, kita bisa membuat sebuah puzzle yang sukar untuk dipecahkan dengan cara ini. Selama kita bisa melakukan generate ID puzzle secara acak. Ide tentang hal ini selanjutnya dipergunakan dalam proses penambangan bitcoin, yang juga dilakukan dengan komputansi puzzle.

SHA-256

Ada cukup banyak fungsi hash yang telah ada, namun pada Bitcoin, fungsi hash yang satu ini menjadi yang utama dan cukup baik untuk digunakan, disebut dengan SHA-256. Hash umumnya disajikan dalam bentuk bilangan hexadecimal, yaitu kombinasi antara angka 0-9 dengan huruf a hingga f.

Perlu diingat bahwa kita memerlukan fungsi hash untuk bisa bekerja pada input dengan panjang tertentu, tetap. Ada sebuah metode umum yang bisa mengubahnya menjadi sebuah fungsi hash yang bisa bekerja pada panjang input yang berubah-ubah. Metode itu disebut Merkle-Damgard transform. SHA-256 adalah salah satu dari sekian banyak fungsi hash yang digunakan dalam metode ini. Dalam terminologi secara umum, panjang yang tetap dari sifat fungsi hash collision-resistant disebut dengan compression-function. Dan hal ini telah terbukti. Sehingga jika compression-function tersebut adalah collision-resistant, maka secara keseluruhan fungsi hash adalah collision-resistant juga.

Proses Merkle-Damgard cukup sederhana. Compression-function mengambil panjang input m dan menghasilkan output yang lebih pendek n. Input ke fungsi hash tersebut, dapat dari berbegai ukuran, kemudian dibagi menjadi blok-blok dengan ukuran panjang m-n. Proses kerjanya melalui setiap blok bersama dengan output blok sebelumnya kedalam compression-function. Perhatikan bahwa panjang input akan menjadi (m-n)+n = m, yang merupakan panjang input untuk compression-function. Jika blok tersebut adalah blok pertama, tentu tidak ada output blok sebelumnya. Dan jika menggunakan intialization Vector, jumlah tersebut digunakan kembali untuk memanggil fungsi hash.

SHA-256 menggunakan compression-function dengan mengambil input 768-bit, dan menghasilkan output 256-bit. Ukuran blok adalah 512 bit.

fungsi sha

Pada gambar itu, SHA-256 menggunakan Merkle-Damgard untuk mengubah panjang yang tetap dari collision-resistant compression-functoin menjadi fungsi hash, yang bisa menerima input berbagai ukuran.

Dengan demikian, kita telah membahas tentang fungsi hash, beberapa sifat khusus tambahan fungsi hash kriptografi, aplikasi dari sifat fungsi hash tersebut, dan juga fungsi hash tertentu yang digunakan dalam Bitcoin. Bahasan selanjutnya akan mengarah pada fungsi hash dengan struktur data yang lebih rumit yang digunakan dalam sistem Bitcoin.



Pointer Hash Dan Struktur data

Pointer Hash

Kita telah sampai pada pembahasan tentang pointer hash dan aplikasi yang digunakan. Pointer hash adalah struktur data yang berguna dalam banyak sistem. Sebuah pointer hash berfungsi seperti sebuah pointer pada umumnya, menunjukkan dimana informasi itu disimpan, bersama-sama dengan informasi hashnya. Pointer hash juga menunjukkan cara untuk mengambil informasi tersebut, dan juga cara untuk memverifikasi informasi tersebut agar tidak berubah

Sebuah pointer hash adalah pointer yang menunjukkan ke mana data itu disimpan bersama-sama dengan hash dari nilai data pada waktu tertentu.

Kita bisa menggunakan pointer hash untuk membangun semua jenis struktur data. Kita juga dapat mengambil struktur data yang menggunakan pointer seperti list link atau pohon pencarian binary dan kemudian menerapkannya dengan pointer hash, tidak seperti pointer yang biasanya digunakan.

pointer 2

Block chain

Gambar itu adalah list link menggunakan sebuah pointer hash. Selanjutnya struktur data ini disebut dengan Block chain. Secara umum, list link ini memiliki serangkaian blok. Setiap blok memiliki data dan pointer yang menuju ke blok sebelumnya pada list. Pada block chain, blok sebelumnya akan diganti dengan pointer hash. Sehingga pada setiap blok, tidak hanya memberikan kita dimana nilai blok sebelumnya saja, tapi juga mempunyai nilai yang memungkinkan kita untuk memverifikasi nilai itu agar tidak bisa berubah, setelah diverifikasi.

Block chain akan berfungsi sebagai tamper-evident log. Sehingga struktur data tersebut menyimpan begitu banyak data. Dan memungkinkan untuk menambahkan data di akhir log. Jika kemudian ada seseorang yang mengubah data sebelumnya, maka akan bisa dideteksi.

Untuk mengetahui mengapa block chain bisa menjadi tamper-evident log, misalnya ada seorang pengganggu yang ingin mengubah data pada bagian tengah block chain. Secara khusus tentu orang tersebut sudah mengetahui bahwa pointer hash dibagian kepala saja yang tidak bisa mendeteksi gangguan itu. Kemudian orang tersebut mengubah beberapa data di blok k. Karena data terebut telah berubah, hash di blok menjadi k+1. Sedangkan hash tersebut merupakan hash dari seluruh blok k, sehingga menjadi tidak akan cocok.

Perlu diingat adalah, bahwa hash baru itu tidak akan cocok dengan konten yang baru saja dirubah sejak fungsi hash menjadi collision-resistant. Perubahan itu akan bisa dideteksi di antara data baru di blok k dan pointer hash yang berada di blok k+1. Untuk menutupi hal ini, maka perusuh tersebut harus mengubah hash blok berikutnya juga, dan akan terus melakukan hal ini. Strategi orang tersebut akan gagal ketika sudah mencapai puncak list. Secara khusus, selama kita menyimpan pointer hash di bagian kepala daftar list, dan orang tersebut tidak bisa mengubahnya tanpa terdeteksi.

Maka, jika seseorang ingin mengutak-atik data di bagian mana saja di seluruh rantai data ini, agar perubahan data yang dilakukan itu menjadi konsisten, maka dia harus mengubah juga semua hash dari awal. Pada akhirnya, orang itu akan banyak mengalami hambatan, karena tidak akan mampu mengutak-atik induk list tersebut. Itulah mengapa hanya dengan menaruh pointer hash tunggal ini, maka akan menjadi tamper-evident log seluruhnya. Sehingga kita bisa membuat rangkaian block chain yang bisa terdiri dari sebanyak blok yang diinginkan.

Selanjutnya mari kita menengok kembali pada awal list blok yang dikenal dengan genesis block. Kita akan mengingat bahwa pembangunan rantai blok ini mirip dengan kontruksi Merkle-Damgard yang sudah dijelaskan sebelumnya. Keduanya memang cukup mirip, dan memiliki argumen keamanan yang berlaku juga di keduanya.

pointer 3

Gambar tersebut, jika seseorang merubah data di blok mana saja dalam rantai tersebut, maka akan mengakibatkan keselahan pointer hash di blok berikutnya. Jika kita menyimpan pointer hash di kepala daftar, dan kemudian seseorang memodifikasi semua pointer agar bisa konsisten dengan data yang dirubah, maka pointer di bagian kepala list blok akan mengalami kesalahan. Sehingga itu data yang tidak konsisten tersebut akan bisa dideteksi.

Struktur Data

Merkle Trees

Struktur data lainnya yang berguna dan bisa kita buat menggunakan pointer hash adalah binary tree. Struktur data binary tree yang mempunyai pointer hash, disebut dengan Merkle Tree, yang ditemukan oleh Ralph Merkle. Misalnya kita memiliki sejumlah blok yang memiliki sejumlah data. Kemudian, blok ini tersusun menggunakan merkle tree. Kemudian mengklasifikasikan data blok-blok tersebut menjadi dua pasang. Setiap pasangnya dibuat struktur data yang mempunyai hash pointer, satu pada setiap blok. Struktur data ini membuat tingkatan berikutnya pada pohon strukturnya. Lantas pada setiap pasangan, membuat struktur data baru yang mempunyai hash pada masing-masingnya. Hal ini dilakukan terus menerus hingga mencapai satu blok, yang menjadi akar (root).

pointer 4

Pada Merkle Tree, data blok dikelompokkan berpasangan, hash pada masing-masing blok disimpan pada node induk. Selanjutnya, node induk akan dikelompokkan lagi berpasangan, dan hash akan disimpan lagi di level berikutnya. Hal ini dilakukan secara terus-menerus hingga mencapai simpul akar.

Sebelumnya, kita tentu masih mengingat bahwa hanya pointer hash yang ditempatkan di kepala pohon yang tidak bisa dirubah bukan? Sehingga jika ada beberapa bagian di bawah pohon, akan menyebabkan pointer hash di satu titik dengan titik lain diatasnya menjadi tidak cocok. Jika pengubahan data ini terus dilakukan, pada akhirnya juga akan merambah di bagian atas pohon, dimana orang tersebut pun tidak akan bisa mengutak-atik, dan akan terdeteksi hanya dengan menambatkan pointer hash di bagian atas.

Proof of Membership (bukti keanggotaan)

Ada sebuah fitur lain dalam Merkle yang cukup berguna. Namun tidak seperti pada rantai blok yang kita bahas sebelumnya. Dengan fitur ini memungkinkan untuk membuat ringkasan keanggotaan. Sehingga data itu menjadi lebih pendek dan tidak terlalu panjang. Sebagai contoh, katakanlah ada seseorang yang ingin memberikan bukti bahwa data blok tertentu merupakan bagian dari Merkle Tree. Selanjutnya yang perlu diingat hanyalah root saja. Kemudian ornag tersebut perlu untuk menunjukkan data bloknya, dan data blok tersebut akan berjalan sesuai dengan urutan data bloknya hingga menuju ke akar. Kita bisa mengabaikan sisa bagian pohon itu, karena jalur pohon akan memungkinkan dalam memverifikasi hash hingga mencapai akar pohon.

pointer 5

Pada gambar itu, untuk bisa membuktikan bahwa data blok termasuk dalam anggota merkle, maka yang dibutuhkan hanya menunjukkan blok tersebut pada jalur yang bisa mencapai ke akar.

Sorted Merkle Tree

Sorted Merkle Tree adalah sebuah Merkle tree dimana kita mengambil blok pada bagian bawah, kemudian mengurutkannya dengan beberapa fungsi. Bisa berupa abjad, urutan leksikografis, numerik, atau lainnya.

Proof of Non-Membership

Merkle Tree yang sudah diurutkan tadi, maka memungkinkan untuk melakukan verifikasi non-membership. Artinya, bisa dibuktikan bahwa ada blok tertentu yang tidak menjadi bagian dari Merkle Tree. Caranya, adalah dengan menunjukkan jalur pada item tersebut tepat sebelum item itu dipertanyakan, dan juga menunjukkan jalur item itu tepat setelahnya. Jika dua item tersebut ada berturut-turut dalam merkle, maka bisa dijadikan bukti bahwa item itu tidak menjadi bagian merkle. Jika kedua item itu dimasukkan bagian merkle, maka dua item itu harus ditampilkan juga, sedangkan tidak ada ruang karena keduanya ada secara berturut-turut.
sumber