Skip to content

Latest commit

 

History

History
39 lines (24 loc) · 1.13 KB

README.md

File metadata and controls

39 lines (24 loc) · 1.13 KB

Merkle Tree Kata

Kata for implementing a Merkle Tree class:

A Merkle Tree is a data structure used by Bitcoin and other P2P systems.

Requirements

  • A document will be represented as an string.
  • We want to split the document in chunks of N characters and send each chunk separately.
  • We are going to use a Merkle root for document integrity validation.
  • We always use a pair number of chunks (leaf nodes in the tree). If the number is odd, we have to duplicate the last one.

Iteration 1:

  • We need generate the Merkle root of a document.
  • The hash function will be h(x) = xx.

Iteration 2:

  • Allow changing hash function.

Iteration 3:

  • The initial array of chunks is very big and we want to build the tree passing one chuck at a time.

Iteration 4:

  • Given a MerkleTree and a chunk we want to check if that chunk is valid.

Iteration 5:

  • We want to validate a chunk without using the entire MerkleTree. We want to calculate the minimum branch needed to validate a chunk, and use that branch to validate a chunk.