3

I have just started reading about sparse merkle trees and I came across a function(get value) which is used to find value for the specified key. I can't find an explanation on the internet which can explain how the get value function works.

My understanding is that each node is of 256 bits so there can be 2^256 leaf nodes and keys are indexed. So we start from root and keep choosing left or right node based on weather the bit is 0 or 1 but I'm not able to understand v = db.get(v)[32:] statement. How is it leading me to the value for the key provided?

def get(db, root, key):
    v = root
    path = key_to_path(key)
    for i in range(256):
        if (path >> 255) & 1:
            v = db.get(v)[32:]
        else:
            v = db.get(v)[:32]
        path <<= 1
    return v
Ashwani
  • 53
  • 1
  • 5
  • [32:] is a python slice after 32. [:32] is a python slice everything before. If the cryptography matches, you know it's in that side of the tree. – Devin Jun 17 '21 at 18:51
  • I get it that it's python slice but why 32? 32 is the number of bytes. How is it relevant here? That's my doubt. – Ashwani Jun 17 '21 at 19:36
  • What's the datatype of db.get(v)? String? It could be that the hash is structured with references in specific blocks. Instead of a pointer, the values overlap in specific area to help find the next. – Devin Jun 18 '21 at 03:46

1 Answers1

0

"A Merkle tree [21] is a binary tree that incorporates the use of cryptographic hash functions. One or many attributes are inserted into the leaves, and every node derives a digest which is recursively dependent on all attributes in its subtree. That is, leaves compute the hash of their own attributes, and parents derive the hash of their children’s digests concatenated left-to-right."

This is a citation from "https://eprint.iacr.org/2016/683.pdf"

Each hash has a roadmap to all it's dependent hashes.

Devin
  • 134
  • 9