Summary Hashing Table dan Implementasi Hash pada Blockchain

HASHING TABLE

Pada post kali ini saya akan membahas mengenai implementasi Hash Table dalam pembuatan Blockchain. Sebelum itu kita harus tau apa itu Hash Table yang di dalamnya terdapat Hash Function dan Collision. Saya akan membahas secara lengkap mengenai semuanya itu pada blog kali ini.

Hash Table adalah sebuah struktur data sebagai tempat kita menyimpan data. Hash Table terdiri atas tabel dan fungsi yang bertujuan memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Tujuan dari Hash Table sendiri adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Namun pada kenyataannya, sering kali ditemukan angka hash yang bertabrakan (collision) record-recordnya. Maka, untuk mengatasi hal ini diterapkan Kebijakan Resolusi Bentrokan (Collision Resolution Policy). Kebijakan ini berguna untuk menentukan lokasi record dalam tabel.

Operasi pada Hash Table:

·       Insert  =  Penambahan data dalam tabel

int hashtbl_insert(HASHTBL *hashtbl, const char *key, void

*data)

{

struct hashnode_s *node;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) {

node->data=data;

return 0;

}

node=node->next;

}

//Jika tidak menemukan key yang sama

if(!(node=malloc(sizeof(struct hashnode_s)))) return -1;

if(!(node->key=mystrdup(key))) {

free(node);

return -1;

}

node->data=data;

node->next=hashtbl->nodes[hash];

hashtbl->nodes[hash]=node;

return 0;

}

·        Find    =  Pencarian data yang berhubungan dengan key

void *hashtbl_get(HASHTBL *hashtbl, const char *key)

{

struct hashnode_s *node;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) return node->data;

node=node->next;

}

return NULL;

}

·    Delete/remove  =  Penghapusan data setelah diberi key, kemudian menemukan nilai yang berhubungan dengan key dan setelahnya akan dihapus.

int hashtbl_remove(HASHTBL *hashtbl, const char *key)

{

struct hashnode_s *node, *prevnode=NULL;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) {

free(node->key);

if(prevnode) prevnode->next=node->next;

else hashtbl->nodes[hash]=node->next;

free(node);

return 0;

}

prevnode=node;

node=node->next;

}

return -1;

}

Hashing Function

Teknik-teknik pada Hash Function:

·         Division :

String yang kita input akan dimoduluskan dengan sejumlah memori agar nilai (value) yang didapatkan dari hasil modulus kemudian dijadikan indeks tempat nilai itu disimpan.

·         Mid-Square :

Setiap nilai yang kita terima akan dipangkatkan dua. Jika memori hash kita ada 100, memori itu terdiri dari 0-99 maka angka yang menjadi hash kita adalah 2 digit dari nilai tengahnya.

·         Folding      :

Memecahkan nilai dari hash tersebut menjadi beberapa bagian.

Collision (Tabrakan)

Keterbatasan table hash menyebabkan terdapat 2 angka yang jika dimasukkan ke dalam fungsi hash menghasilkan nilai yang sama. Peristiwa ini disebut dengan Collision.

Misalkan kita ingin menginput string floor dan float (hash-key : 5) dengan huruf awal f. Di sini terdapat 2 hash index yang sama. Jika bentrok ini dinamakan collision. Kejadian ini harus bisa ditangani.

Cara penanganan collision:

·        Collision Resolution Open Addressing

Menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori di luar array yang digunakan. Cara ini mencari alamat lain apabila alamat yang akan dituju sudah terisi data. Ada 3 cara untuk mencari alamat lain tersebut:

1.      Linear Probing

Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.

2.      Quadratic Probing

Penanganannya hampir sama dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … ).

3.      Double Hashing

Alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi.

·        Collision Resolution Chaining

Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Kerugian:

-          Overhead pada memory tinggi jika jumlah entry sedikit.

Keunggulan dibandingkan open addressing:

-          Proses insert dan remove lebih sederhana.

-          Ukuran Array bukan batasan (tetapi harus tetap meminimalisir collision.

IMPLEMENTASI HASHING PADA BLOCKCHAIN

Sebelum masuk lebih dalam kita harus tahu apa itu blockchain. Blockchain adalah catatan transaksi digital berdasarkan strukturnya, di mana catatan individu, yang disebut blok, dihubungkan bersama dalam satu daftar, yang disebut chain (rantai). Blockchain digunakan untuk mencatat transaksi yang dilakukan dengan cryptocurrency, seperti Bitcoin dan memiliki banyak aplikasi lain.

Pada era sekarang ini, kriptografi menjadi peran penting dalam jaringan blockchain yang terus berkembang. Salah satunya adalah proses perhitungan sebuah data secara konkret dan unik. Metode ini dikenal dengan Hash. Kode unik yang kita temukan dalam Blockchain itu menggunakan metode Hash.

Nilai berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik untuk mencegahnya ialah dengan pemberian kode unik.

Data tersebut akan aman dan pastinya menjadi orisinalitas data dari orang lain. Hanya orang yang terkait berhak dan bisa masuk ke akses data tersebut. Saat ini beragam proses pengamanan data, mulai dari sidik jari, sidik mata, dan di sistem Blockchain menggunakan kode unik (Hash).

Tak hanya itu saja, Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri. Ini yang tidak didapatkan pada jaringan biasa. Selain itu, setiap data dokumen dengan panjang berapa pun akan menghasilkan nilai hash yang punya nilai panjang berbeda tergantung spesifikasi Hash yang digunakan.

Sejumlah hash yang digunakan saat ini karena fungsi dan keamanannya beragam dan memiliki kemampuan transaksi data yang cepat :

1.     SHA256

SHA256 adalah hash pertama sekali muncul dan digunakan di jaringan blockchain publik. Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai Hash. Pengguna ini sudah mulai dicetus sejak tahun 2001 oleh NIST (National Institute of Standard and Technology).

SHA256 merupakan generasi kedua dari hash jenis Sha, penggunaan angka 256 karena dasar data yang dihasilkan adalah 256 bit. SHA26 sendiri banyak digunakan oleh berbagai sistem blockchain lainnya karena punya kapasitas mengirim yang relatif kecil dan cepat. Terlebih lagi untuk proses transaksi besar.

2.      RIPEMD160 (Race Integrity Primitive Evaluation Message Digest)

Konsep dari algoritma dari RIPEMD160 dikembangkan oleh MD4. Jumlah data transaksi yang dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.

Tentu saja hal ini membuktikan RIPEMD lebih cepat dan bertenaga, sehingga proses pending data berkurang. Peran utama yang diemban oleh RIPEMD160 adalah dengan membuat alamat Bitcoin yang diakumulasi berdasarkan pada kunci publik.

3.     Beragam Hash pada Monero
      Pada Monero, penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Blake, Grostl, JH, dan Skein pada CryptoNote. Konsep dari Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous.

Monero menilai bahwa perlu adanya keamanan khusus dan beragam pada Hash. Inilah yang menjadi dasar lahirnya konsep CryptoNote. Pengguna yang mengirimkan transaksi atau data tidak dapat diidentifikasi oleh publik karena ada beberapa kunci tersebut. 

 

Demikian penjelasan yang dapat saya sampaikan mengenai Hash Table, Hash Function, Collision serta pengimplementasian dan peran Hash pada jaringan Blokchain. Semoga bermanfaat.