Compare calldata requirements for designs 2 & 3

[andrewgordstewart]

Ignore the storage cost of each round -- assume we can store an array of arbitrary size for free. (This will be tackled later).

Assume a maximum of 132KB for calldata, and assume that any "cryptographically important" word is 32 bytes.

Answer the following question, by deriving how many "words" need to be supplied to perform a single k-section.

How much k-section can be done in one turn in option 2 vs the symmetric version of option 3?

This forms a part of the justification of option 3 over option 2, relevant to maximizing the feasible branching factor from Milestone 3.

[andrewgordstewart]

@lalexgap I realized a flaw in my thinking. In option 2, it is not necessary to provide (in calldata) the full Merkle tree that you are committing to on-chain. Instead, you only need to provide the bottom layer, since everything above it is a function of the bottom layer.

The contract would then need to:

1. compute the root corresponding to the nodes provided
2. verify that this root is different from the node being contested

[lalexgap]

I've created this document explaining the call data size:

TLDR: Both approaches will have a call data size of log_2(k) + k + c

[andrewgordstewart]

I've created this document explaining the call data size:

TLDR: Both approaches will have a call data size of log_2(k) + k + c

Note: an eager over-optimizer could reduce the calldata size for Option 3 (we call it array dissection?) to k + c, by using eg. an RSA accumulator to "store" an array a of length k, rather than a Merkle tree.

(I haven't thought carefully about whether you could get rid of the log_2(k) cost in Option 2, but you probably can.)