Deep Study of Bitcoin Code Series - Let's learn Merkle Trees! - Why they are intelligent and useful for Bitcoin

This is part of a series of deep study over the bitcoin blockchain

For interested parties, here is the first article of this series: https://steemit.com/bitcoin/@bitworkers/deep-study-of-bitcoin-code-series-the-times-03-jan-2009-chancellor-on-brink-of-second-bailout-for-banks

So, today we are going to learn and create a Merkle Tree using Perl6

What is a Merkle Tree?

A Merkle Tree is a hash tree in which every non-leaf node is labelled with the hash of the labels or values of its child nodes. The Merkle Tree is used for verification of contents of large data structures. The top hash is called the Merkle Root.

Fonte: https://en.wikipedia.org/wiki/Merkle_tree

In Bitcoin, Merkle Trees are used to make verification of sets of transactions in blocks easy and fast. By chaining hashes in transactions, any change in any leaf affects the root. This way it is easier to verify all transactions in a block simply by checking the merkle root hash.

It provides rapid and trustworthy proof of valid transactions in a block and it is present in the header of the block. The Merkle root can then be hashed and chained to the next block header.

It is important to notice that, in Bitcoin, Merkle Trees use double SHA-256 for hashing each entry. Also, if the entry row of double SHA-256 is odd, the final double-hash is duplicated.

Merkle Tree Perl6 Module

We mocked a dataset containing blocks and hashed them out recursively to obtain a Merkle Tree root. Here's the code we wrote:

unit class BW::Merkle;
use Digest::SHA;

class Tree {
  has $.root;
  has $!height;
  has @!dataset;

  submethod BUILD ( :@dataset ) {
    # check if elems is odd and duplicate last if so
    @!dataset = @dataset;
    if ( @!dataset.elems % 2 == 1 ) {
      @!dataset.push( @dataset.pop );
    }
    my @new-dataset;
    for @!dataset -> $data {
      my $sha256 = sha256 $data.encode: 'ascii';
      sub buf_to_hex { [~] $^buf.list».fmt: "%02x" }
      @new-dataset.push( buf_to_hex $sha256 );
    }
    @!dataset = @new-dataset;
    $!height = log( @!dataset.elems, 2 ) + 1;
    print "On constructor I got " ~ @!dataset ~ " with height $!height\n";
  }

  method get-root() {
    my @line = @!dataset;
    loop ( my $h=$!height-1; $h >= 0; $h-- ) {
      print "h: $h\n";
      loop ( my $i=0; $i < @!dataset.elems/($!height-$h); $i+=2 ) {
        print "i: $i\n";
        my $sha256 = sha256 (@line[$i]~@line[$i+1]).encode: 'ascii';
        sub buf_to_hex { [~] $^buf.list».fmt: "%02x" }
        say my $data = buf_to_hex $sha256;
        @line[$i/2] = $data;
      }
    }
    return @line[0];
  }

}

This module or class returns the Merkle Root for any block of transactions. We plan to use the module in our project of building HON blockchain.

Cheers, tell me what you think. Upvote and follow if you enjoy our content!

EDUARDO CAPANEMA
@bitworkers