Difference between encoding empty user states and `abi.encode(0)`

[dmaretskyi]

Encoding a StateLeaf struct with all zeros produces a different output then abi.encode(0). We've noticed that abi.encode(0) is used to represent a vacant state leaf.

An example where this differences may be exploited is a TRANSFER transaction where receiver is an empty state leaf.

The disputer would have to provide a witness for the receiver state leaf in: https://github.com/thehubbleproject/hubble-contracts/blob/003235445e3b625211ed19de49bff6575a8bc94e/contracts/libs/Transition.sol#L157

But that's impossible to do since the witness leaf value is passed as a struct and it would be impossible to pass a struct which would have the same leaf hash as abi.encode(0).

[msieczko]

Some examples to better understand this issue:

1. It is impossible to dispute a transfer from a nonexistent state leaf

In order to do so, you would provide the following UserState struct representing the sender state before transfer to the dispute method:

UserState {
    pubkeyID: 0,
    tokenID: 0,
    balance: 0,
    nonce: 0
}

Encoding of such UserState produces a different value than abi.encode(0) which is used to represent an empty state leaf. Therefore the following require statement would fail, reverting the dispute transaction: https://github.com/thehubbleproject/hubble-contracts/blob/003235445e3b625211ed19de49bff6575a8bc94e/contracts/libs/Transition.sol#L127-L135

Possible fix to no. 1

Encode zero UserStates as abi.encode(0). This fixes the problem with the failing state tree inclusion check. A transfer must have a nonzero amount therefore the balance check will fail approving the dispute: https://github.com/thehubbleproject/hubble-contracts/blob/003235445e3b625211ed19de49bff6575a8bc94e/contracts/libs/Transition.sol#L182-L183

2. It is impossible to dispute a transfer to a nonexistent state leaf.

Similarly as in no. 1 the following require would fail, reverting the dispute transaction: https://github.com/thehubbleproject/hubble-contracts/blob/003235445e3b625211ed19de49bff6575a8bc94e/contracts/libs/Transition.sol#L155-L162

The Possible fix to no. 1 would stop the require statement from failing but would not make such transfer disputable.

3. It is impossible to dispute a fraudulent transfer that in the same commitment is preceded by a transfer from/to a nonexistent state leaf

The failing require statements mentioned in no. 1 and 2 would prevent a dispute transaction to finish.

The Possible fix to no. 1 would solve this issue.

[msieczko]

Another possible fix could be changing the representation of a vacant state leaf to a hash of abi.encodePacked(0, 0, 0, 0) (current encoding of a zero UserState). This would however require changes to other pieces of the SCs. For instance, SubtreeVacancyProofs passed to submitDeposits relay on the fact that abi.encode(0) is the vacant state leaf.

[jacque006]

Making a zero'd user state (0, 0, 0, 0) encode to abi.encode(0) appears to solve this issue https://github.com/thehubbleproject/hubble-contracts/pull/655/files#diff-f2cdceb56d3a8c8a457906a15fe58b0cdc283d6202375c7afeb61b2f485d6979 . However, a zero user state leaf is a valid state leaf. It points to the first pubkey, for the first token, with no balance and no txs. This state leaf is commonly created in tests, and is likely to be created as a fee receiver for the first proposer on a hubble network. There also is no reason why someone could not create more of them to have multiple balances for the first token. This might be more common in mainnet deploys where we would provide an option to skip the ExampleToken (now CustomToken with Example/EMP constructor params) and something like WETH or DAI is the first registered token at tokenID 0.

Ideally, we could allow a watcher to call disputeTransitionTransfer where instead of a UserState being part of a proof, they instead can pass in the empty leaf state (abi.encode(0)). But this would break a lot of validation logic as other steps depend on that proof having user state data.

Another option is to have a zero state encode to 0 per workaround at top, and ban/prevent contract callers from creating deposits, bulk deposits, or c2t's that are zero user states. This adds complexity/gas costs to other contract function calls, but would also have the benefit of preventing callers from accidentally passing in likely bad data after initial hubble network setup.

Thoughts? @ChihChengLiang your input would be appreciated as well.

[jacque006]

Another thing to add, working on the test case for the non-existent toIndex. I think the initial requires in Transition.sol.processSender and processReceiver should to switch to become new Result enum values, such as BadFromIndex and BadToIndex. This would allow disputes on invalid L2 txs that are submitted on L1 to successfully trigger a rollback rather than fail the dispute L1 txn. This would also impact Create2Transfer and MassMigration which I am less familiar with.

[ChihChengLiang]

a zero user state leaf is a valid state leaf. It points to the first pubkey, for the first token, with no balance and no txs. This state leaf is commonly created in tests, and is likely to be created as a fee receiver for the first proposer on a hubble network.

There are other options we can use for empty states.

# pubkeyID ranges from [0, 2^32-1], 2^32 is a pubkeyID no one can get
(2^32, 2^32, 0, 0) 
# This is -1 in uint256
(2^256 - 1, 2^256 - 1, 0, 0) 

• For pubkeyID, we can choose a number that's larger than the biggest possible pubkey tree index.
• For tokenID, we can set the largest tokenID possible and bound that number in the TokenRegistry.
• For balance, choose 0 to rule out any chance of printing out money.
• For nonce, probably doesn't matter.

Another possible fix without defining the preimage empty state is letting the disputer submit the stateHash.

// disputer first justify the inclusion of stateHash
require(
    MerkleTree.verify(
        stateRoot,
        stateHash,
        senderStateIndex,
        proof.witness
    ),
    "Transition: Sender does not exist"
);
// check if sender is empty
if (stateHash == ZERO_BYTES32) return Types.Result.TransferFromNonexistentSender;
// sender is non-empty, the disputer now have to justify the preimage of the state
require(stateHash == keccak256(proof.state.encode(), "stateHash mismatch");
... other checks

This alternative comes with additional costs of witnessing a stateHash and a separate require check for stateHash.

[jacque006]

From offline discussion of tradeoffs with @ChihChengLiang :

If we use a special value for empty states (preimage), we will need to update all zero hashes and default state roots to match the new value. This keeps the interface to disputeTransitionTransfer and other dispute calls intact, but will also require clients to update those zero values and initial states as well if they are not pulling them from contracts at startup.

If we let the disputer submit the stateHash as part of the dispute, we do not need a special value and can add the additional check pseudocode above. This will break the Rollup contract interface as it is an require updates in clients/components to match the new function signature and args. It will also increase dispute gas cost.

Going to let this bake for a bit before deciding on a path forward. Additional input/feedback appreciated.

[ChihChengLiang]

... can add the additional check pseudocode above.

Just want to add that we still need to check stateHash == ZERO_BYTES32 if we do the preimage approach.

The code would look similar but the benefit is no change in function signatures.

stateHash = keccak256(proof.state.encode());
// disputer first justify the inclusion of stateHash
require(
    MerkleTree.verify(
        stateRoot,
        stateHash,
        senderStateIndex,
        proof.witness
    ),
    "Transition: Sender does not exist"
);
// check if sender is empty
if (stateHash == ZERO_BYTES32) return Types.Result.TransferFromNonexistentSender;

[msieczko]

So to summarise, I think we considered 3 solutions so far:

0. Encode empty user state as abi.encode(0) (initial proposal)

Pros:

• no change in zero hash used for state tree leaves

Cons:

• transfers to nonexistent state leaves are still possible
• quite hacky approach with an if statement in encoder method

1. "Preimage" solution

Use a hash of (2^32, 2^32, 0, 0) or (2^256 - 1, 2^256 - 1, 0, 0) for empty states

Pros:

• it will be possible to dispute transfers to nonexistent state leaves

Cons:

• needs some work to update zero hash used for state leaves everywhere

2. Let disputer submit the stateHash

Pros:

• no change in zero hash used for state tree leaves
• it will be possible to dispute transfers to nonexistent state leaves

Cons:

• increased gas usage of dispute transactions
• needs some work to update the clients to pass stateHash as a param to dispute methods

Feel free to suggest other pros and cons that I may have missed. We talked this through internally as well and for now we'd suggest going forward with the approach no. 2. The increase in gas usage should not be very large and passing this additional parameter is not a problem as well. We can measure the gas used by dispute txs after this change and see if it becomes a problem.