StateRoot Manipulation

[Jake-Song]

Problem / Overview

StateRoot Manipulation is problem that operator put other data on database deliberately.

For example, let's assume {key: 1, val: 1, key: 2, val: 2, key: 3, val: 3} in DB. when to execute SSTORE set key = 1, val =2, got stateRoot#1, and operator also set key = 1, val = 2, but also set key = 4, key = 4 and operator got stateRoot#2.

although stateRoot#1 != stateRoot#2, both of them can be passed through merkle verification. so operator can store new value without any disruption, which is verification game.

Solutions

To solve this problem, we should need merkle branch, which include key, val and merkle proof, and submit to contract on chain. and then calculate rootHash with merkle branch.

i'm considering solidity-partial-trie for verifying

here is how it works

we have 4 steps to verify merkle proof; SSTORE, FirstStep, CALLStart, CALLEnd FirstStep is literally first step of transaction. load state at this step. so it needs merkle verification.

i) SSTORE reset : got inclusion merkle proof + key, val -> commitBranch(submit merkle branch to contract) -> update -> got stateRoot for verification

new : got not inclusion merkle proof -> commitBranch -> insert -> got stateRoot for verification

ii) FirstStep we must agree the stateRoot at the first step. because it assumes that operator and challenger must agree stateRoot at the right before the transaction on verification game. so we don't need State Root Manipulation verification at FirstStep.

iii) CALLStart in the case of call.value ≠ 0, have to verify CALLER and CALLEE.

• CALLER : commitBranch → update → stateRoot 1
• CALLEE: initTrie(stateRoot 2) → commitBranch → update → stateRoot 2 verify
• in the case of creating CALLEE(not included in state trie yet) : got not inclusion merkle proof -> commitBranch →insert → stateRoot verify

iv) CALLEnd if not any problem at the prior step, state root that operator and challenger would be same. if any problem, that is, for example, different state root or EVM state at the SSTORE step, it is caught at that step. so we don;t need State Root Manipulation verification.

[Jake-Song]

Here is Solution update

if we introduce Loom's Sparse Merkle Trie (https://github.com/loomnetwork/plasma-cash/blob/master/server/contracts/Core/SparseMerkleTree.sol),

we need to update how it process, so then,

1. SSTORE

• reset

1) offchain - get inclusion merkle proof(key) 2) onchain - checkMemberShip(key, beforeVal, beforeStorageRoot, proof) 3) onchain - checkMemberShip(key, afterVal, afterStorageRoot, proof)

• new

1) offchain - exclusion merkle proof(key) 2) onchain - checkMemberShip(key, val = 0, beforeStorageRoot, proof) 3) onchain - checkMemberShip(key, val, afterStorageRoot, proof)

the reason why to do checkMemberShip twice, to fix valid proof. if we omit second process, one can pass through checkMemberShip with any other proof.

Note : it can bundle checkMemberShip into one function

2. FirstStep

1) offchain - get inclusion merkle proof(key) 2) onchain - checkMemberShip(key, val, stateRoot, proof)

operator and challenger must agree with before state root. so execute checkMemberShip once.

3. CALLStart At CALLStart, it is more complicated than above. it needs to be watched two nodes. CALLER and CALLEE

i) CALLER

1) offchain - get inclusion merkle proof(CALLER key) 2) onchain - checkMemberShip(CALLERKey, beforeVal, beforeStateRoot, CALLERProof) 3) onchain - checkMemberShip(CALLERKey, afterVal, intermediateStateRoot, CALLERProof)

ii) CALLEE

1) offchain - get inclusion merkle proof(CALLEE key) 2) onchain - checkMemberShip(CALLEEKey, beforeVal, intermediateStateRoot, CALLEEProof) 3) onchain - checkMemberShip(CALLEEKey, afterVal, intermediateStateRoot, CALLEEProof)

it needs to be added intermediateStateRoot, that is different from intermediateStateRoot in EVM steps. the reason why to add intermediateStateRoot is we have to get merkle proof whenever we update the leaf value. let's see diagram below.

• CALLER update

• CALLEE update

iii) in case of creating CALLEE account (ie. call not existed account) 1) offchain - exclusion merkle proof(key) 2) onchain - checkMemberShip(key, val = 0, beforeStateRoot, proof) 3) onchain - checkMemberShip(key, afterVal, afterStateRoot, proof) Note: if call.value ≠ 0, do call ≠ 0 process above.

4. CALLEnd operator and challenger must agree with before state root. so it must be same at CALLEnd. if operator and challenger have different state root at this step, it may be caught up at the earlier SSTORE.