Optimizations for fraud proofs

[bigspider]

The current implementation of fraud proofs requires around 500 vbytes for each bisection round (Alice + Bob transaction). That brings the total cost for a crazy-long computation of 4 billions steps to about 500 * 32 = 16000 vbytes in the uncooperative case.

This post describes a generic approach to optimize this kind of games.

Further gains probably require revisiting the protocol: while all the descriptions focused on binary Merkle trees for the computation trace, a radix-d tree with d > 2 is likely substantially more efficient, due to the fixed per-transaction costs. Moreover, this would reduce the total number of rounds, which probably even more important than in practice than minimizing transaction size. Making a table of number of rounds and total size for different values of d would be an interesting problem.

I expect that a radix-8 Merkle tree would probably still be practical, have smaller total size overall than a binary tree (using the trick in the gist), and require only 1/3 of the rounds of the binary tree.