go-merkle
go-merkle implements a simple merkle tree in Golang. It allows to obtain proofs and prove the validity of issued proofs.
Introduction
Merkle trees are binary trees built from the given data entries. The input entries i.e. leafs are first hashed. Then each subsequent row is built by hashing two element pairs from the current row using the smaller of the two as the first element when hashing. This is repeated until only 1 element remains.
Design
There are many different approaches to handling the remainder i.e. uneven input list. This implementation carries the odd remainder to the next level until consumed as shown in the diagram below:
52ddb7875b4b 666eec13ab35 7e4729b49fce 31fcacdabf8a 8f5564afe39d
\ / \ / |
\ / \ / |
\/ \/ V
40a65894031a fed10b5a5178 8f5564afe39d
\ / |
\ / |
\/ V
21fd9dfe5c21 8f5564afe39d
\ /
\ /
\/
8846d886ed99
