Conflicting Proofs Policy

In Kaspa based rollups design, entities called provers will regularly submit proofs of an ordered aggregation of txs that occurred since the last proof was submitted – a point in time which I will refer to as the latest settlement point. More precisely, txs are proven in batches according to the chain blocks that accepted them. These proofs are treated as regular txs from the point of view of L1. Currently there is no set bound planned on how late or how early can these proofs arrive. Provers may cooperate completely on the proving effort – there is no clear danger in them cooperating as the results of their computation are deterministically decided by the contents of the L1.

Nevertheless for reasons of lack of coordination, or for plain avarice, two provers may end up submitting two distinct proofs, starting from the same L2 latest settlement point. The two proofs will naturally agree on a prefix of the proven txs, but one will usually contain a suffix missing from the second. I refer to such events as conflicting proofs. If the longer of the two is the first included in the L1 ledger, then it is clear that the second proof is to be ignored. But if the shorter is included first, it is less obvious what to do. Naively, the longer proof is treated as a double spend attempt/ invalid tx and ignored. However there are several issues with it, first, in terms of quality of service, the longer proof contains txs that the L1 has yet to see the proof of. Ideally, these proofs can be included immediately, but the naive design foregoes that. Second, the prover has worked tirelessly to create their longer proof, but now will have to start from anew, leading to losses, potentially making proving financially unsustainable if this occurs routinely. Third, this paves the way for a liveness attack on the L2: a malicious party can regularly submit proofs proving 1 block of txs to scoop all other provers (as supplying long proofs takes more time for the benevolent provers), resulting in the settlement to L1 progressing very slowly.

Two possible solutions come to mind: the first, perform major logical changes to allow miners to include a more inclusive proof even if its settlement point has already been deprecated. I believe this is possible to engineer in some manner, but will likely demand a further level of utxos abstraction, more opcodes, and might end up introducing other complications.

The second solution is the empty solution where we will accept this phenomenon as a fact of life, yet explain away why the problems are not as fatal as they superficially seem: a property of Snark/Stark proofs as I understand them is that they are componentized. i.e., proofs are not necessarily created as one massive indivisible black box block, rather the different stages of the computation could be broken apart and proven separately, then combined together. If this supposition is true, then even if scooped, a prover only loses the work put to prove the subset of txs proven by its competitor, and some constant metadata. Thus they can relatively quickly rebuild a new proof from the surplus txs they previously proved but their competitor did not. It is self apparent that if this supposition is true it will mitigate the effects of all 3 of the issues discussed above, without the need to take drastic measure. However the β€œif” here is crucial: I address the zk audience (@reshmem and @proof are explicitly called, but please others join in) with a question: is this supposition about the way snark/stark proofs behave true?

As a sidenote, it is worth mentioning that β€œscooping” is not all bad: if the fear of being scooped rules the ring, one might expect provers to compete within themselves on proving as fast as possible, vastly improving quality of service. However the exact mechanics required to ensure such competition without collapsing to cannibalism and monopoly require more thought, and seem out of scope for this post.

3 Likes