Zero-Knowledge Proof of Progress: Secure Multi-Phase Capture-the-Flag Competitions

Abstract

Existing Capture-the-Flag (CTF) platforms trust a single organizer, offer limited auditability, and are vulnerable to infrastructure-level manipulation. We propose zk–MPSFV, a zk-SNARK-based, multi-phase sub-flag verification scheme that replaces centralized scoring with an on-chain, zero-knowledge, publicly verifiable scoreboard. Challenges are decomposed into sub-challenges arranged as a directed acyclic graph (DAG): a team unlocks the next step only after proving completion of all parent nodes. Sub-flags and decryption keys are jointly generated by n organizers and released via an off-chain ($t, n$) Shamir–BLS threshold signature produced through multi-party computation (MPC), preventing any single organizer from leaking or altering keys. Teams submit zk-PLONK proofs that the contract verifies, timestamps, and records immutably. Under standard assumptions (collision-resistant hashing, SNARK soundness/zero-knowledge, IND-CCA2 ECIES, and at least t honest organizers), we prove that zk–MPSFV achieves the stated security goals, including DAG-gated progress, anti-replay, and threshold-robust organizer security, while out-of-band flag sharing remains out of scope. On a three-organizer testbed with 30 simulated teams, setup costs 0.45 ms per sub-flag, proof generation averages 5.34 s on an 8-core system, and on-chain verification costs $\approx$ 170kL2 gas on zkSync Era with a median fee of 1.33 $\times 10^{-6}$ ETH (about ${\$}$0.0046 at ${\$}$3,435/ETH). Stress replays sustain $\approx$ 7 proof transactions/s up to 5000 proofs; extrapolating to 50,000 proofs (1000 teams $\times$ 50 submissions) yields $\approx$ 0.0665 ETH (about ${\$}$200–${\$}$228) and $\approx$ 2 hours of settlement time. Overall, zk-MPSFV is practical for small- to mid-scale, audit-ready progression CTFs.