Merkle tree calculation in VM

[ronnno]

Is it worthwhile to let the VM output a Merkle tree diff (including the merkle root) as well as state diff in the process of preparing a new block?

pros:

• VM may have better CPU resources
• VM may often get state before changing it (can we estimate how often?). so if this state is returned with the Merkle proof there are no additional API calls.
• This allows us to embed the most recent Merkle Root in any proposed block rather than only the previous block.

cons:

• For new values, and for state changes that are not preceded by a get (override or increment) we will still have to make a "get" call against state storage to obtain the Merkle proof for these new items. This however may be condensed to a single round trip in a batch "get" operation for any state entry that changes and was not read during execution.
• VM will be responsible for Merkle proof construction and this will not be provided by the state storage.

Optimization:

• to address concern of slowing down transaction processing due to the need to fetch merkle proofs (multiple IOs), we can use this strategy: when the VM needs a value to process, it can receive it without the proof, at which point, the state storage is signalled load the proof in the background. The same would happen when we add a new state entry or write without a prior read. All these background operations may be processed under one context, and a combined proof for the entire state diff will be collected during execution and retrieved from memory once the processing is done. The only added cost for block creation time is the CPU work needed to update the subset Merkle tree once processing is complete.
• (TBD?) Moreover, when a block is propagated in the network is is also possible to transmit the (signed) merkle tree diff along with the block to reduce overall CPU load in the network.

[OdedWx]

Proposal:

1. Rename the interface to: {contract_name, hashkeys} a. hashkeys instead of keys
2. hashkey = hash(contract_name.key), for example hash(token.transfer) a. calculated by the VM, used directly by the state storage (without additional hashing)
3. Even though the address is unique across contracts, the state is managed per contract (allowing to delete / copy on upgrade)
4. Hash (address length): SHA256 (32B) Discussion: TODO a. Length extension attack - 2 hash functions. RIPEMD160 is often used after SHA256 to prevent length extension attack: derive H(m||x) from H(m) without knowing x. This should not a problem for the state storage where the data is public. b. Consider LSB20B(SHA256) to reduce the size to 20B
5. Future feature - add a merkle hash table variable type, allowing to store smart contract data under a separate merkle tree.

[ronnno]

Agree. To recap, you propose:

1. state will retain ability to iterate all contract values, drop, extract and import contract state in isolation from other contracts.
2. contract name will be included in the pre-image of the key hash to prevent collisions. this will be done by the VM and transparent to the state-storage module
3. No double hashing needed

Am I correct? Also, about dropping contract state, however, i think if we want to drop a contract as part of a transaction we would have to iterate all contract keys and clear the merkle tree one by one. there is no way to quickly drop a set of contract keys from the merkle tree unless we build contract merkle trees in hierarchy. Can I assume we don't need to isolate contract merkle trees for now?