interview.md

Merkle Tree

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

A Merkle tree is a binary tree where each node's value is calculated by concatenating and hashing both of it's child leaves: sha256(left_child + right_child). Uninitialized leafs should have the value of a hash of an empty string: sha256('').

Example

From the diagram:

// Leaf hashes are initialized from the data
hash00 = sha256(l1)
hash01 = sha256(l2)
hash10 = sha256(l3)
hash11 = sha256(l4)

// Next level is calcualted based on the previous level
hash0 = sha256(hash00 + hash01)
hash1 = sha256(hash10 + hash11)

// Root is calucalted based on it's two child nodes
root = sha256(hash0 + hash1)

Task

Create a data structure representing a fixed-height Merkle tree in-memory with the following API:

func NewMerkleTree(height uint) *MerkleTree

// Returns the height of the Merkle tree
func (m *MerkleTree) GetHeight() uint

// Returns the value at the root now of the Merkle tree
func (m *MerkleTree) GetRoot() Hash

// Sets the value of a leaf node (bottom-most level).
// Leafs are indexed left-to-right starting from 0.
// All of the hashes in the tree have to be updated according to the new data.
func (m *MerkleTree) SetLeaf(index uint, hash Hash)

Write unit-tests to cover those API methods.

Tips

For hashing you can use the go-ethereum packages:

import (
	"github.com/ethereum/go-ethereum/common"
	"github.com/ethereum/go-ethereum/crypto"
)

func HashTwo(a, b common.Hash) common.Hash {
	buf := make([]byte, 64)
	copy(buf[0:32], a.Bytes())
	copy(buf[32:64], b.Bytes())
	return crypto.Keccak256Hash(buf)
}