How the get value function works in sparse merkle trees?

user_8558033 0
Viewed 81

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
merkle-tree ethereum
1 Answers

"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.

user_81004940
Related