Fraud Proof Mina Block Relay
Let there be a blockchain, B, which can verify a Mina block proof (or wrapped proof such as the implementation currently in development by Nil Foundation [1]) via a smart contract. Such a proof alone is not enough to prove a block is part of the canonical chain, only that it is part of some valid chain going back to genesis. This may be an abandoned fork, or a fork intentionally created by an adversary.
Regular Mina nodes can follow the canonical chain under the assumption that they share their current best chain tips via the p2p network and use the chain selection algorithm to chose the ‘best’ chain tip in a consistent way.
For an on-chain relay there is an associated cost for submitting and and verifying a block/tip (current estimate for an EVM based implementation is 3M gas). This document proposes a fraud proof based scheme to incentivize participants to relay blocks and to ensure the on-chain state finalizes on the canonical chain.
Proposal
Any account can participate in relaying a new Mina block to B by submitting a transaction. The transaction must include:
- Block Snark proof
- Block height
- Ledger root
- Chain selection data [2] (slot number, min_window_density, sub_window_densities)
Verifying the proof must ensure that the the given data indeed belongs to the given block and that the block is part of a chain of valid blocks back to genesis.
Once a block is submitted it enters a challenge period (say a few hours or days). During this period any other account can challenge this block by submitting a valid block at the same height that is more preferable according to the chain selection algorithm (relative minimum window density). This restarts the challenge period for the new candidate block at that height.
Once the challenge period has elapsed the block is said to be finalized and can no longer be challenged. Other contracts on B can then make use of the ledger root to prove statements about the Mina blockchain at that height.
Relayer Incentives
The above scheme only works if there are sufficient incentives for a relayer to challenge a non-canonical block. One idea for an incentive scheme is as follows:
- Users wishing to make use of the Mina state at a given height submit a bounty attached to that height
- The relayer of a block that becomes finalized at or above the given height is eligible to claim all bounties posted since the last finalized block
As more users contribute to the bounty pool the potential reward for a relayer increases until it is economically viable for them to pay the gas to submit a new block. Any relayer seeing a non-canonical block would be incentivised to challenge it in order to claim the reward themselves.
This accumulation of bounties is possible thanks to the receipt_chain_hash field of accounts in the ledger. This can be used to prove any historical transactions made from an account. Given this, blocks with height at or above the height when transaction was included are equally useful.
Submitting a block is near risk free assuming it has reached a sufficiently high level of finality on the Mina blockchain; however, the first relayer to submit a block that is finalized will receive the full reward. This creates an interesting dynamic that should converge to fast and correct relaying of the canonical chain.
Extension - Avoiding verification costs
The same fraud proof scheme could also be used to save gas by only executing the verification of the block proof in the case of a challenge. In this variation a relayer submits the block details without a proof. There are then two possible challenges other participants can make:
- A challenge that includes a better block, also lacking a proof
- A claim that the block is invalid
For the second challenge the claimant must submit a bond that exceeds the cost of executing the block proof.
The original relayer can then make another transaction to submit and execute the block proof in order to prove its validity and claim the challengers bond. If the block is indeed invalid then presumably they will ignore the challenge and after some challenge response period the initial relayers bond is awarded to the challenger.
Careful consideration is needed for the timing and bond amounts to ensure there are no possible grieving attacks (e.g. disputing valid blocks just before they are about to be finalized to delay the finality). It also needs to be long enough that the probability of block producers on B censoring a transaction responding to a challenge is negligible.
Closing thoughts
The proposed block relay scheme is only possible due to the succinct nature of Mina and its ability to perform chain selection based only on tips.
It is trust-less and permission-less. Any account can participate as a relayer. It is also memory-less in the sense that the relay receiver contract does not have to keep track of historical blocks in order to follow the chain. Each cycle of the challenge protocol is independent of those that have occurred prior. This is a unique property not shared by any existing block relay protocol[1].
-
Actually Stateless SPV also has this property but it only works with proof-of-work chains. ↩︎