4

I'd like to verify the inclusion of a certain data within the state of a smart contract supposing that I've already have the right block header.

What is the depth of the State Root? When I've reached the right node, how depth is again the Storage Root?

Essentially if I am given a value of a variable inside a smart contract, how long is the Merkle Patricia Proof so that it is possible to re-construct the State Root?

Thanks for your time :)

|improve this question
  • Could you provide a practical example, e.g. what the starting situation is, which steps are taken and what output you would like to have? – Nikita Fuchs May 22 '17 at 15:35
  • 1
    Just imagine you have a contract with a byte32 variable. I am a light node with all the block headers for which I am sure they are correct. Someone says to me: "Inside the contract, the bytes32 variable has value X". I do not trust this person and so I want a proof that pairs this value X with my block headers. How big is the proof to go from the State Root in the block header to the value X which I think is saved and summarized by the Storage Root ? :) – gatb27 May 22 '17 at 18:48
  • 1
    You most likely won't get around fetching the block, as I cannot imagine of a way to deduct a proof for what you need simply from the block header. Here is some information about what a block is comprised of: github.com/ethereum/wiki/wiki/Block-Protocol-2.0 You 1. either need to get the transaction list and parse the change of storage from the input data of transactions, or 2. directly read the storage value from the contract with web3. – Nikita Fuchs May 22 '17 at 20:11
  • Yes, I do not want to download the full block. In Bitcoin, considering 2000 tx in a block, I need a proof that is made up by: the tx itself + merkle branch (11 32bytes hashes to reach the root). With these data I can reconstruct the Merkle Root stored in the Bitcoin block header. So, from a theoretical point of view, I'd like to know how many Bytes is the proof to go from the State Root (accessible from the block header) to the value inside the contract. Patricia Trees are not binary and I don't know how many depth levels they have. – gatb27 May 23 '17 at 14:47
5

The trie can be up to 64 levels deep. 1 for each hex character of a bytes32 hash. To find a piece of data, one must traverse 1 level at a time picking out the nth index of a (usually) 17 element array. (source)

However there is an optimization to shortcut this path when there are no other branches at a particular level. In practice I have found there to be an average of 6 levels before reaching an account. To traverse the data of the account you would traverse deeper from there.

So in practice a proof of an account balance will require about ~6 arrays of ~17 elements each (expected to slowly increase).

|improve this answer
  • Finally the answer I needed :) So when I've reached an account, say with 6 arrays of 17 elements, then to verify the presence of a certain value inside a contract I need other arrays of elements depending on the amount of data stored in the contract? – gatb27 May 31 '17 at 7:34
  • 1
    When you get to an account you'll see a 4-element array. I think they are nonce,balance,storageRoot,codeRoot. So the balance is right there but the variables and stuff are in another Patricia trie with the root being that storageRoot – ZMitton May 31 '17 at 7:42
  • Exactly, I'm Interested in the storageRoot. Am I right assuming that the levels of the Patricia Tree whose root is the storageRoot depends on the amount of data saved into the smart contract variables? – gatb27 May 31 '17 at 7:51
  • 1
    Generally true but you'll need understand Patricia tries. There aren't really tools to create this proof yet but I'm in the process of trying to make something for it – ZMitton May 31 '17 at 7:59
  • Ok thank you very much for everything! I hope to see your work – gatb27 May 31 '17 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.