HASH & BINARY TREE

Ketika kita mengikuti seminar atau membaca buku tentang blockchain kita sering kali mendengar atau menyinggung istilah hash dan hashing. Mungkin bagi beberapa orang mengangap istilah tersebut bukanlah hal yang berarti. Namun bagi anda yang penasaran pasti akan bertanya – tanya apasih hash  atau hashing itu? Hashing adalah teknik yang digunakan untuk menyimpan kunci dan mengambil kunci dengan cepat. Hashing merupakan suatu proses yang menghasilkan suatu output yang terenkripsi yang ukurannya sama dan tetap dari inputan variable yang ukurannya berbeda- beda . Atau hash bisa juga di artikan sebagai aktivitas untuk mengubah suatu objek  menjadi serangkaian angka / karakter atau sejenisnya yang terenkripsi. Ada beberapa hash yang melibatkan penggunaan kriptografi yang merupakan inti dari cryptocurrency. Hal tersebut yang membuat sistem seperti blockchain memiliki keamanan yang signifikan.

Cara kerja Hash
Hash dengan fungsi yang berbeda akan menghasilkan output dengan ukuran yang berbeda dari input. Tetapi setiap algoritma hashing kemungkinan akan memiliki output dengan ukuran yang konstan. Nilai yang di return oleh fungsi hash disebut nilai hash, kode hash, jumlah hash, atau hanya hash. Kita ambil contoh algoritma SHA-1 dengan SHA-256. SHA-256 selalu menghasilkan output 256 bits sedangkan SHA-1 selalu menghasilkan 160 bits.
Ketika kita menginput menggunakan algoritma SHA-256 outputnya akan seperti berikut:
Input                     Output
Hello                185F8DB32271FE25F561A6FC938B2E264306EC304EDA518007D1764826381969
hello             2CF24DBA5FB0A30E26E83B2AC5B9E29E1B161E5C1FA7425E73043362938B9824
h                 AAA9402664F1A41F40EBBC52C9993EB66AEB366602958FDFAA283B71E64DB123
H                 44BD7AE60F478FAE1061E11A7739F4B94D1DAF917982D33B6FC8A01A63F89C21

Berapa banyakpun karakter yang kita input mau itu melebihi 64 atau kurang dari 64 akan tetap menghasilkan output 64 karakter seperti contoh yang di atas. Jika dari inputan yang kita berikan terdapat spasi maka spasi akan tertap dihitung. Walaupun yang kita input hanya berbeda huruf besar pada awalan sebuah kata tetap saja menghasilkan output yang berbeda. Namun tetap saja karena menggunakan algoritma SHA-256 maka tetap akan menghasilkan output 64 karakter.
Kita lihat apa yang terjadi ketika kita menggunakan algoritma SHA-1
Input                     Output
Hello                     F7FF9E8B7BB2E09B70935A5D785E0CC5D9D0ABF0
hello                     C4D871AD13AD00FDE9A7BB7FF7ED2543AEC54241
h                            244AA7266B3F5A08321B403B2C59BAEBA5539B19
H                           7CF184F4C67AD58283ECB19349720B0CAE756829           
Berbeda dengan algoritma SHA-256, ketika kita memasukan input ke SHA-1 maka outputnya tidak berupa 64 karakter walaupun tetap ukuranya tetap konstan.

Fungsi kriptografi HASH
Agar fungsi kriptografi berjalan denga baik terdapat 3 syarat yang harus dipenuhi:
•             Collision resistance
•             Fast Computing
•             Preimage resistance

Collision Resistance
Dalam fungsi hash ada yang dikenal dengan tabrakan. Apa itu tabrakan? Tabrakan itu ketika sebuah inputan yang berbeda menghasilkan output yang sama. Sedangkan hal ini tidak boleh terjadi agar menjamin sistem keamanan. Namun karena terdapat kemungkinan input yang tak terbatas tetapi outputnya terbatas maka kemungkinan terjadinya tabrakan selalu ada. Maka ketika sebuah fungsi jarang sekali ditemukan tabrakan maka fungsi tersebut sudah bisa dikatakan collision resistance.

Fast Computing
Fungsi hash harus bisa men-return inputan dengan cepat jika tidak cepat maka sistem tidak efisien.

Preimage resistance
Berbeda dengan tabrakan tadi, Preimage resistance ini merupakan sifat fungsi yang aman ketika seseorang mencoba mencari sebuah nilai alsi dengan mengamati dari outputnya.

Implementasi pada blockchain

Blockchain sebenarnya adalah linked list yang isinya adalah data dan pointer hash yang menunjuk ke blok sebelumnya, jadi terlihat seperti rantai. Sebuah pointer hash mirip dengan sebuah pointer, Pointer hash tidak hanya berisi alamat dari blok sebelumnya tetapi juga berisi hash dari data di dalam blok sebelumnya . Jika seseorang mencoba mengubah sebuah data ke 2 dari rantai tersebut maka karena sifat hash yang ketika ada sebuah perubahan data yang kecil maka akan terjadi perubahan total pada hash sehingga akan terjadi perubahan hash blok ke 1.


TREES & BINARY TREES
Tree: Salah satu dari bentuk struktur data yang tidak linear. Seperti bentuknya, trees mengambarkan hubungan one to many antar elemen. Tiap-tiap node yang terdapat pada tree tidak perlu disimpan secara bersebelahan atau berdekatan melainkan bisa disimpan dimana saja dan dihubungkan menggunakan pointer seperti linked list..Berikut adalah istilah-istilah yang terdapat pada tree.
https://miro.medium.com/max/677/1*Z89j_NoDx9HkFcPHy3rPZg.png
Predesesor: Node yang berada diatas node tertentu. (contoh: 99 predesesor dari 44 dan 11)
Succesor: Node yang berada dibawah node tertentu.(contoh: 44 dan 11 adalah successor dari 99)
Ancestor: Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. (contoh 2 dan 10 adalah ancestor dari 87).
Descendant: Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama. (ContohL 87 dan 77 merupakan descendant dari 2).
Parent: Predesesor satu level diatas satu node.(contoh 9 merupakan parent dari 2).
Child: Succesor satu level dibawah satu node. (contoh: 2 merupakan child dari 9).
Sibling: Node yang memiliki parent yang sama dengan satu node.(Contoh : 55 merupakan sibling dari 87).
Subtree: Bagian dari tree yang berupa suatu node beserta descendant-nya.(contoh: subtree 99, 44 , 11 dan subtree 10,55,87)
Size: Banyaknya node dalam suatu tree.(contoh size dari tree tersebut adalah 14)
Height: Banyaknya tingkat/level dalam suatu tree.(contoh: height tree tersebut adalah 3)
Root (Akar): Node khusus dalam tree yang tidak memiliki predesesor. (contoh: rootnya adalah 2)
Leaf (Daun): Node-node dalam tree yang tidak memiliki daun. (contoh: 2,1,7,2,8 ,44,11,55, 87).
Degree (Derajat): Banyaknya child yang dimiliki oleh suatu node.

Binary tree: merupakan sebua tree dengan setiap node hanya boleh memiliki masksimal 2 anak yang bisa dibedakan dengan left child dan right child. Berikut merupakan beberapa tipe dalam binary tree:
-        Pohon biner penuh: Semua simpul selain daunmemiliki 2 anak dan tiap cabang memiliki panjang ruas yang sama.
-        Pohon biner lengkap: semua simpul selain daun memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.
-        Pohon biner miring: Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun.
-        Pohon biner seimbang: Pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya.


Dalam binary tree kita mengenal kunjungan preorder, inorder, postorder. Dengan itu kita bisa membuat prefix, infix, dan postfix.

Kunjungan Preorder : Kunjungan ini mencetak dengan urutan (P L R) Parent - > Left -> Right
                                   Dengan kunjungan preorder kita bisa menghasilkan prefix.
Kunjungan InOrder   : Kunjungan ini mencetak dengan urutan (L P R) Left -> Parent - > Right.
                                   Dengan iini kita bisa menghasilkan infix.
Kunjungan PostOrder:  Kunjungan ini mencetak dengan urutan (L R P) Left -> Right -> Parent.
                                      Dengan itu kita bisa menghasilkan postfix. 
Referensi:
https://saragusti22.wordpress.com/2015/05/04/pengantar-struktur-data-tree-dan-binary-tree/
https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/
https://www.binance.vision/id/blockchain/what-makes-a-blockchain-secure
https://www.geeksforgeeks.org/difference-between-general-tree-and-binary-tree/

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
Balanced Binary Search Tree Seperti yang sudah kita pelajari, tree merupakan suatu bagian dari struktur data yang memungkinkan melakukan operasi insert, delete , dan searching. Sayangnya, waktu yang dibutuhkan insertion, deletion, dan searching bergantung pada tingginya tree tersebut dimana makin besar height nya maka akan semakin lama. Hal ini yang menyebabkan mengapa menggunakan Binary Search Tree akan kurang efektif bila sedang mengerjakan sebuah data yang berjumlah besar atau banyak. Oleh karena itu, dengan menyeimbangkan height dari tree tersebut akan membantu mempercepat operasi insert, delete, dan searching pada sebuah tree. Tree dengan tujuan untuk meminimalkan height disebut dengan Balanced Binary Search. Contoh dari Balanced Binary tree adalah AVL tree dan Red Black Tree karena kedua tree tersebut sebisa mungkin akan meminimalkan height dari sebuah tree. AVL Tree AVL tree merupakan salah satu bagian dari self-balancing binary search tree. Bahkan AVL tree merupakan se...
Baca selengkapnya

Linked List

Gambar
Linked List Apa itu Linked list? Linked List adalah suatu struktur data yang terdiri dari urutan record data dimana setiap record data terdiri dari field dimana salah satunya menyimpan alamat dari record data selanjutnya. Seperti definisi di atas, Linked list merupakan bagian dari struktur data. Di dalam linked list terdapat sesuatu yang disebut node. Node merupakan elemen data yang telah terhubung atau dihubungkan dengan link. Terdapat 2 istilah yang sering kita dengar di dalam Linked list yaitu tail dan head . Di dalam linked list terdapat 2 hal yang bisa dilakukan yaitu insertion dan deletion. Dengan ini di dalam linked list dimungkinkan untuk menambah atau menghapus node baik dia tail head atau bukan keduanya. Linked list terdiri dari 2 tipe yaitu single linked list dan double linked list. Linked List VS Array Apasih perbedaan array dengan linked list? Seperti yang kita ketahui array relatif lebih mudah jika dibandingkan dengan linked list. Lalu kenapa kita harus menggunakan l...
Baca selengkapnya