I’m working on authenticated data structures for
ic-stable-memory library and I want to make my Merkle proofs compatible with the IC’s service worker by default.
So, I went through the documentation and it seems like I have to use
ic_types::HashTree as an interface in order to achieve this compatibility feature. But I kinda struggle to understand it:
It seems like values for
HashTreehave to be byte arrays. I understand that this is because right now this data structure is only used for frontend chunks and other hashes, but if I want to generate a Merkle proof for some rich data (for example, for token balances) what encoding should I use? Wouldn’t it be more useful, if values would be
What is exactly the process of forming a
HashTree? My Merkle tree seems to have the same structure than your Red-Black tree where
node_hash = h(value + left_child_hash + right_child_hash)and I was thinking initially that I will make Merkle proofs of this form:
// vh - (pruned) hash of the value stored inside the node // l_ch - hash of the left child // r_ch - hash of the right child // <empty> - empty slot that will be filled with the valid child hash during reconstruction // <value> - the value we're claiming to be in the set [vh, l_ch, <empty>] \ [vh, l_ch, <empty>] \ [vh, <empty>, r_ch] / [vh, l_ch, <empty>] \ [<value>, l_ch, r_ch]
but I don’t understand if I can achieve the same kind of shape with the provided API of
HashTree. Can you please help me to understand the basic usage of this API? Maybe you have an internal “for dummies” documentation of this crate - this would be very helpful.
Also, does this API provide a way to include more hashes into a single node? I have some ideas of improving the overall performance for my authenticated data structure, but it requires storing additional data in some nodes (not necessarily forks) and this data should also be accounted in reconstruction phase. Can I do that with
It seems like
HashTreesupports aggregated proofs (proofs which prove set membership of multiple keys at the same time) in some form. How do you form one?
Thanks in advance and have a nice day!