Games in the head (and fraud proofs for the plebs)

Original Postby salvatoshi

The discussion revolves around optimizing fraud proofs in MATT contracts by employing a novel method that significantly reduces data overhead and transaction costs.

The suggested strategy applies to two-party games, converting them into protocols with minimal data requirements for each move—approximately two hashes. Consequently, this approach estimates the cost of implementing fully general fraud proofs at about 7000 vbytes and 17 total transactions. For CoinPools consisting of up to 256 users, these costs can be further reduced to 2000 vbytes and merely 5 transactions.

When considering two-party protocols, each step traditionally involves a sequence of transactions updating the contract's state, which can lead to substantial overhead. However, by adopting a 'games in the head' framework, the need to verify each player's move is eliminated. Players assert their moves by declaring the input and committing to the hash of the subsequent state. If a move is incorrect, the opposing player can prove this on their following move by revealing the commitment, thereby winning the game. This simplification means that each transaction consists of revealing only a hash, the input, and the hash of the next state.

This more efficient method, referred to as the game-in-the-head approach, allows for transaction sizes to become independent of the complexity of the state transitions and focuses solely on the size of the input plus a constant overhead. Moreover, the code complexity increase is moderate, offering significant savings in the overall transaction size. This optimization has potential applications in multi-party games.

For fraud proofs, the application of this method is particularly compelling as it could make such proofs more feasible on-chain due to reduced costs. An initial implementation of the bisection protocol was developed using the Python framework pymatt, demonstrating significant savings compared to direct implementations. Further optimization is possible by reducing the number of transactions through a k-section protocol, which uses a k-ary Merkle tree instead of a binary one, thus reducing the number of rounds required for the proof.

In the context of pools, this round-efficient method could be highly valuable, especially when integrated with the Lightning Network. For instance, in a pool of 256 users, applying a k-section protocol could limit the requirement to just 5 transactions for a complete fraud proof—a notable improvement from the 17 transactions needed in the unoptimized version. This reduction in the number of rounds is not only cost-effective but also practically beneficial for the performance of such pooled structures.