Communications in Cryptology IACR CiC

How to Make Rational Arguments Practical and Extractable


Matteo Campanelli, Chaya Ganesh, Rosario Gennaro
Matteo Campanelli ORCID
Protocol Labs, United States
matteo dot campanelli at gmail dot com
Chaya Ganesh ORCID
Indian Institute of Science, India
chaya at iisc dot ac dot in
Rosario Gennaro ORCID
The City University of New York, United States
rosario at ccny dot cuny dot edu


We investigate proof systems where security holds against rational parties instead of malicious ones. Our starting point is the notion of rational arguments, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also computationally bounded.

Rational arguments are an interesting primitive because they generally allow for very efficient protocols, and in particular sublinear verification (i.e. where the Verifier does not have to read the entire input). In this paper we aim at narrowing the gap between literature on rational schemes and real world applications. Our contribution is two-fold.

We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest.

As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our aforementioned compiler can also be applied to obtain efficient extractable rational arguments for $\mathsf{NP}$.


Diego F. Aranha, Emil Madsen Bennedsen, Matteo Campanelli, Chaya Ganesh, Claudio Orlandi, and Akira Takahashi. ECLIPSE: enhanced compiling method for pedersen-committed zkSNARK engines. In Goichiro Hanaoka, Junji Shikata, and Yohei Watanabe, editors, PKC 2022, Part I, volume 13177 of LNCS, 584–614. March 2022. Springer, Heidelberg.
Pablo Daniel Azar and Silvio Micali. Rational proofs. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, 1017–1028. ACM, 2012.
Pablo Daniel Azar and Silvio Micali. Super-efficient rational proofs. In Michael J. Kearns, R. Preston McAfee, and Éva Tardos, editors, Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013, 29–30. ACM, 2013.
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. SNARKs for C: verifying program executions succinctly and in zero knowledge. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, 90–108. August 2013. Springer, Heidelberg.
Adam L. Beberg, Daniel L. Ensign, Guha Jayachandran, Siraj Khaliq, and Vijay S. Pande. Folding@home: lessons from eight years of volunteer distributed computing. In 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, May 23-29, 2009, 1–8. IEEE, 2009.
Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, 677–706. May 2020. Springer, Heidelberg.
Matteo Campanelli, Antonio Faonio, Dario Fiore, Anaïs Querol, and Hadrián Rodríguez. Lunar: A toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, 3–33. December 2021. Springer, Heidelberg.
Matteo Campanelli, Dario Fiore, and Hamidreza Khoshakhlagh. Witness encryption for succinct functional commitments and applications. 2022.
Matteo Campanelli, Dario Fiore, and Anaïs Querol. LegoSNARK: modular design and composition of succinct zero-knowledge proofs. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, 2075–2092. November 2019. ACM Press.
Matteo Campanelli and Rosario Gennaro. Sequentially composable rational proofs. In M. H. R. Khouzani, Emmanouil A. Panaousis, and George Theodorakopoulos, editors, Decision and Game Theory for Security - 6th International Conference, GameSec 2015, London, UK, November 4-5, 2015, Proceedings, volume 9406 of Lecture Notes in Computer Science, 270–288. Springer, 2015.
Matteo Campanelli and Rosario Gennaro. Efficient rational proofs for space bounded computations. In Stefan Rass, Bo An, Christopher Kiekintveld, Fei Fang, and Stefan Schauer, editors, Decision and Game Theory for Security - 8th International Conference, GameSec 2017, Vienna, Austria, October 23-25, 2017, Proceedings, volume 10575 of Lecture Notes in Computer Science, 53–73. Springer, 2017.
Matteo Campanelli and Rosario Gennaro. Fine-grained secure computation. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, 66–97. November 2018. Springer, Heidelberg.
Matteo Campanelli, Nicolas Gailly, Rosario Gennaro, Philipp Jovanovic, Mara Mihali, and Justin Thaler. Sftestudo: linear time prover snarks with constant size proofs and square root size universal setup. In Abdelrahaman Aly and Mehdi Tibouchi, editors, Progress in Cryptology - LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3-6, 2023, Proceedings, volume 14168 of Lecture Notes in Computer Science, 331–351. Springer, 2023.
Matteo Campanelli, Chaya Ganesh, and Rosario Gennaro. How to make rational arguments practical and extractable. 2023.
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, and Nicholas P. Ward. Marlin: preprocessing zkSNARKs with universal and updatable SRS. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, 738–768. May 2020. Springer, Heidelberg.
Jens Ernstberger, Stefanos Chaliasos, George Kadianakis, Sebastian Steinhorst, Philipp Jovanovic, Arthur Gervais, Benjamin Livshits, and Michele Orrù. Zk-bench: a toolset for comparative evaluation and performance benchmarking of snarks. 2023.
Dario Fiore, Cédric Fournet, Esha Ghosh, Markulf Kohlweiss, Olga Ohrimenko, and Bryan Parno. Hash first, argue later: adaptive verifiable computations on outsourced data. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, 1304–1316. October 2016. ACM Press.
Georg Fuchsbauer, Eike Kiltz, and Julian Loss. The algebraic group model and its applications. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, 33–62. August 2018. Springer, Heidelberg.
Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, 626–645. May 2013. Springer, Heidelberg.
Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, 467–476. June 2013. ACM Press.
Siyao Guo, Pavel Hubácek, Alon Rosen, and Margarita Vald. Rational arguments: single round delegation with sublinear verification. In Moni Naor, editor, ITCS 2014, 523–540. January 2014. ACM.
Siyao Guo, Pavel Hubácek, Alon Rosen, and Margarita Vald. Rational sumchecks. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part II, volume 9563 of LNCS, 319–351. January 2016. Springer, Heidelberg.
Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, 305–326. May 2016. Springer, Heidelberg.
Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. 2019.
Assimakis A. Kattis, Konstantin Panarin, and Alexander Vlasov. RedShift: transparent SNARKs from list polynomial commitments. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022, 1725–1737. November 2022. ACM Press.
Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: the power of no-signaling proofs. In David B. Shmoys, editor, 46th ACM STOC, 485–494. May / June 2014. ACM Press.
Eric Korpela, Dan Werthimer, David P. Anderson, Jeff Cobb, and Matt Lebofsky. Seti@home-massively distributed computing for SETI. Comput. Sci. Eng., 3(1):78–83, 2001.
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. In Masayuki Abe, editor, ASIACRYPT 2010, volume 6477 of LNCS, 177–194. December 2010. Springer, Heidelberg.
Jonathan Lee. Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, 1–34. November 2021. Springer, Heidelberg.
Jonathan Lee, Srinath Setty, Justin Thaler, and Riad Wahby. Linear-time and post-quantum zero-knowledge SNARKs for R1CS. 2021.
Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, 2111–2128. November 2019. ACM Press.
Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, 793–802. June 2013. ACM Press.
Carla Ràfols and Arantxa Zapico. An algebraic framework for universal and updatable SNARKs. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, 774–804. Virtual Event, August 2021. Springer, Heidelberg.
Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. In 2018 IEEE Symposium on Security and Privacy, 926–943. May 2018. IEEE Computer Society Press.
Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. Mystique: efficient conversions for zero-knowledge proofs with applications to machine learning. In Michael D. Bailey and Rachel Greenstadt, editors, 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, 501–518. USENIX Association, 2021.

PDFPDF Open access

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Matteo Campanelli, Chaya Ganesh, and Rosario Gennaro, "How to Make Rational Arguments Practical and Extractable," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a63zl86bm.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.