Paper 2023/1067

How to Compile Polynomial IOP into Simulation-Extractable SNARKs: A Modular Approach

Markulf Kohlweiss, University of Edinburgh, Input Output Global
Mahak Pancholi, Aarhus University
Akira Takahashi, University of Edinburgh

Most succinct arguments (SNARKs) are initially only proven knowledge sound (KS). We show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties: weak unique response (WUR) and trapdoorless zero-knowledge (TLZK); and that together they imply simulation extractability (SIM-EXT). The factoring of SIM-EXT into KS + WUR + TLZK is becoming a cornerstone of the analysis of non-malleable SNARK systems. We show how to prove WUR and TLZK for PIOP compiled SNARKs under mild falsifiable assumptions on the polynomial commitment scheme. This means that the analysis of knowledge soundness from PIOP properties that inherently relies on non-falsifiable or idealized assumption such as the algebraic group model (AGM) or generic group model (GGM) need not be repeated. While the proof of WUR requires only mild assumptions on the PIOP, TLZK is a different matter. As perfectly hiding polynomial commitments sometimes come at a substantial performance premium, SNARK designers prefer to employ deterministic commitments with some leakage. This results in the need for a stronger zero-knowledge property for the PIOP. The modularity of our approach implies that any analysis improvements, e.g. in terms of tightness, credibility of the knowledge assumption and model of the KS analysis, or the precision of capturing real-world optimizations for TLZK also benefits the SIM-EXT guarantees.

Available format(s)
Publication info
non-malleabilittysimulation-extractabilitySNARKinteractive oracle proofs
Contact author(s)
markulf kohlweiss @ ed ac uk
mahakp @ cs au dk
takahashi akira 58s @ gmail com
2023-07-11: revised
2023-07-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Markulf Kohlweiss and Mahak Pancholi and Akira Takahashi},
      title = {How to Compile Polynomial IOP into Simulation-Extractable SNARKs: A Modular Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1067},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.