This book provides a comprehensive and rigorous treatment of cryptographic proofs constructed using ideal hash functions (also known as random oracles). This includes discussions and analyses of notable constructions of SNARGs (succinct non-interactive arguments) based on ideal hash functions. For example, STARKs (scalable transparent arguments of knowledge) are a popular example of SNARGs based on ideal hash functions.
We study how different types of probabilistic proofs (SPs, IPs, PCPs, IOPs) can be transformed, using ideal hash functions, into cryptographic proofs. The combination of probabilistic proofs and cryptography is central to the theory and practice of SNARGs.
The security reductions that we provide have explicit error bounds, which enables setting security parameters in practice. In most cases our analyses are essentially tight, and we improve upon the fragmented and incomplete treatment of this material that exists in the research literature. We adopt uniform terminology and notation throughout the book to highlight the relationships between the different constructions that we study.
This book is a self-contained reference aimed at people interested in understanding the foundations and constructions of succinct arguments. The limited required background (undergraduate-level discrete probability and algorithms) should make this book accessible to a wide audience of students, researchers, and practitioners.
Where is the book?
The book is available here. The source code of the book is available on Github. The book and its source code are licensed under the Creative Commons Attribution-ShareAlike 4.0 International License (CC BY-SA 4.0).
Contents
The book's chapters are divided into parts, which we summarize below.• Part I: What are Cryptographic Proofs?
We introduce the random oracle model and the notion of cryptographic proofs, more formally known as arguments. We describe properties such as (adaptive) soundness, knowledge soundness, and zero knowledge.
• Part II: NARGs Based on SPs
We describe how to transform a sigma protocol (SP) into a non-interactive argument (NARG). This relies on the Fiat–Shamir transformation, which uses the random oracle to "remove interaction" from the sigma protocol.
• Part III: NARGs Based on IPs
We describe how to transform a public-coin interactive proof (IP) into a non-interactive argument (NARG), extending the ideas of Part II to multiple rounds. A delicate point for this multi-round Fiat–Shamir transformation is that the IP must, for security, satisfy a strong soundness notion, state-restoration soundness.
• Part IV: Commitment Schemes
We study two commitment schemes in the random oracle model: the basic commitment scheme; and the Merkle commitment scheme. Commitment schemes are used to construct succinct arguments, studied in Parts V and VI.
• Part V: SNARGs Based on PCPs
We describe how to construct succinct arguments from probabilistically checkable proofs (PCPs). This includes an interactive succinct argument (the Kilian transformation) and then, building on this, a non-interactive succinct argument (the Micali transformation). A key ingredient is the Merkle commitment scheme.
• Part VI: SNARGs Based on IOPs
We describe how to construct succinct arguments from interactive oracle proofs (IOPs). First we study an interactive succinct argument and then, building on this, a non-interactive succinct argument (the BCS transformation). Merkle commitment schemes are key ingredient. The BCS transformation underlies SNARGs used in practice.
• Part VII: Practical Considerations
We include a selection of topics relevant to using arguments in practice: a brief overview of known probabilistic proofs; how to to set parameters to ensure concrete security; Merkle tree optimizations; and discussions of strong soundness properties of probabilistic proofs (special soundness and round-by-round soundness).
Acknowledgements
The authors are grateful to the Ethereum Foundation, Forte Labs, Protocol Labs, and Provable for their funding towards the writing of this book. Moreover, work on this book was done in part while working at StarkWare Industries, and the authors are grateful for its support.