Merkle Root and Inclusion Proof
Light clients check that a transaction is in a block using a Merkle proof. We use a toy hash so the maths is easy to follow: toyHash(s) starts with h = 17, and for each character does h = (h * 31 + charCode) % 1000000007; the result is h written in lowercase hex, left-padded with zeros to 8 characters.
The leaves are toyHash(item) for each of items. Each level above pairs nodes left to right and a parent is toyHash(left + right) (string concatenation of the two hex hashes). If a level has an odd number of nodes, its last node is paired with itself. The single node at the top is the root; with one item, the root is that item's leaf hash.
Return { root, proof } for the item at index. proof lists, from the leaf level upwards, the sibling hash at each level as { hash, side }, where side is "left" or "right": the side the sibling sits on relative to the running hash.
Example 1
Input: items = ["tx1","tx2"], index = 0 Output: {"root":"2df67b5e","proof":[{"hash":"00097c7d","side":"right"}]} Explanation: Two leaves; the proof for index 0 is just the right leaf.
Example 2
Input: items = ["alice->bob:5","bob->carol:2","carol->dan:1"], index = 2 Output: {"root":"15dfa5eb","proof":[{"hash":"042e07e1","side":"right"},{"hash":"0a41d73c","side":"left"}]} Explanation: Three leaves: the third is paired with itself.
Constraints
- 1 <= items.length <= 10^4
- 0 <= index < items.length
- items are strings of printable ASCII, length <= 100
Hint 1
Push a copy of the last node before pairing an odd level.
Hint 2
At each level the sibling of position i is i ^ 1, and the parent is at i >> 1.
Discussion 0
Join free to post in the discussion.
Good practice for: Blockchain Developer, Backend Developer, Embedded Systems Engineer, Data Engineer, Cloud Engineer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.