Check that the witness is a leaf witness in the challenge manager

[kerzhner]

The Challenger Manager must validate that a witness points to a leaf node. There are two approaches to do so:

1. Pad a tree to a full binary tree. With full binary tree, the witness size is function of the number of leaves.
2. Do not expect a full tree. Then, the calculation of whether a witness points to a leaf is more complex. But certainly doable.

In this PR, we are choosing the first approach.

[kerzhner]

Another approach is for leaf values to be hashes of {stateHash: Bytes32, stateStep: number}. Then a merkle proof is:

• A list of siblings on the path to the leaf.
• A cleartext leaf value.

The nice properties of this approach are:

• Full binary trees are no longer needed. It is simple to validate whether a proof points to a leaf or not.
• We can reduce some of the implicit step calculations.

That being said, implicit step calculations have the benefit that callers are forced to evenly split the consensus-to-dispute range. We probably want to keep this property.

[andrewgordstewart]

That being said, implicit step calculations have the benefit that callers are forced to evenly split the consensus-to-dispute range. We probably want to keep this property.

This is a good benefit of the implicit step calculations.

Another benefit is the reduced calldata requirements. It doesn't make sense to pay 80 gas per uint40 stateStep provided (for instance), plus additional gas to validate that the steps are evenly splitting the computation. This adds up quickly when doing a k-section for large k.

The choice here is between:

1. validate "even splitting" on layer 1
2. enforce "even splitting" by implicitly assuming even splitting (and penalizing players who violate this rule)

[andrewgordstewart]

Another approach is for leaf values to be hashes of {stateHash: Bytes32, stateStep: number}.

They can also be hashes of {stateHash: Bytes32, isLeaf: true}.

For someone to claim that a non-leaf whose value x is a leaf, they would need to find a y such that hash((y, true)) == x, and we are assuming hash is cryptographically secure.

[kerzhner]

For someone to claim that a non-leaf whose value x is a leaf, they would need to find a y such that hash((y, true)) == x, and we are assuming hash is cryptographically secure.

That's a neat idea. Just want to follow up with the thought (that you point out above) that any time "cleartext" leaves are revealed, an extra hash operation is introduced per leaf.

[lalexgap]

Another approach is for leaf values to be hashes of {stateHash: Bytes32, stateStep: number}.

They can also be hashes of {stateHash: Bytes32, isLeaf: true}.

For someone to claim that a non-leaf whose value x is a leaf, they would need to find a y such that hash((y, true)) == x, and we are assuming hash is cryptographically secure.

I believe that's roughly the approach found in this RFC