Short Paper: Rewardable Naysayer Proofs

Combining verifiable computation with optimistic approaches is a promising direction to scale blockchain applications. The basic idea consists of saving computations by avoiding the verification of proofs unless there are complaints. A key tool to design systems in the above direction has been recently proposed by Seres, Glaeser and Bonneau [FC’24] who formalized the concept of a Naysayer proof: an efficient to verify proof disproving a more demanding to verify original proof. In this work, we discuss the need of rewarding naysayer provers, the risks deriving from front-running attacks, and the failures of generic approaches trying to defeat them. Next, we introduce the concept of verifiable delayed naysayer proofs and show a construction leveraging proofs of sequential work, without relying on any additional infrastructure.