A Hierarchical View of Cryptographic Commitment Schemes

<style> .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(20, 230, 230, 0.36); } /* a, .open-files-container li.selected a { color: #5EB7E0; } */ </style> In this series of notes, we explore *cryptographic commitment schemes*, which are primitives that lie at the foundation of various cryptosystems, such as digital signatures and zero-knowledge proofs. Commitment schemes can be categorized based on the *type* of data or information containing mathematical objects (think data structures but possibly extended to infinities) they operate on, such as sets, vectors, functions and so on. Specifically, we are interested in building a hierarchy of commitment schemes that connect to each other through *reductions*, mathematical bridges that allow us to simulate a family of commitments designed for a *simpler* type of object (such as a set), through another family of commitments designed for a more *complex* type (such as a vector, which can be viewed as an ordered multi-set).   ![](https://i.imgur.com/jj48ydK.png) We will begin by discussing the origins of commitment schemes and the *oracle* ideals they embody, *binding* and *hiding*. Then, we describe the common elements within all commitment schemes, *four* well-specified algorithms that make up a commitment, whose computational complexity along with their output sizes determine the *efficiency* of the scheme. In each chapter that follows, we will introduce and give a clear definition for a different family of commitments based on the catagorization above, e.g. set commitments, vector commitments, univariate polynomial commitments and so on. Further, we will introduce some of the most common or well-known commitment schemes used across many applications in the real-world for that particular family. ![](https://i.imgur.com/aESRNCy.jpg) Finally, in each chapter after the first, we will connect the hierarchy of commitment schemes by introducing a simple reduction that connects that family to its child family introduced previously.  --- Chapters --- - [Elements of Commitment Schemes](/@kullervo/commitmentElements) [target=_blank]  - ### Families of Commitment Schemes - [Single-element Commitments](/@kullervo/commitmentSingle) [target=_blank] - [Set Commitments](/@kullervo/commitmentSet) [target=_blank] - [Vector Commitments](/@kullervo/commitmentVector) [target=_blank] - [Univariate Polynomial Commitments](/@kullervo/commitmentUnivariatePoly) [target=_blank] - [Multilinear Polynomial Commitments (private)](/@kullervo/commitmentMultilinearPoly) [target=_blank] - [Multivariate Polynomial Commitments (private)](/@kullervo/commitmentMultivariatePoly) [target=_blank] --- Remarks --- This series reflects our introductory views on commitment schemes formed from an ongoing and more general study of zero-knowledge proofs. Some of these views are possibly over-simplifications. Further, despite our efforts to minimize them, they may contain certain inaccuracies and we would be happy to remedy any such mistakes. Please feel free to contact us if you would like to contribute to this series in any way, with due acknowledgement on our part. Thank you in advance. P.S. As a practical example of using commitment schemes, here is the digest of a hidden message (based on SHA3-512) that reveals our identity and proves our authorship, which we can open to a 3rd-party/public at a later time if we choose to do so:  881a092f2856a4dbe26a4f274035fdddec406dcbb1acd5848eb63a71de310110b4216c1eae8f1b3fa0f19b8ecc79265af668fb90481ab4621d43481b5e4cf932 --- References --- 1. [DHS15] David Derler, Christian Hanser, and Daniel Slamanig. Revisiting cryptographic accumulators, additional properties and relations to other primitives. https://eprint.iacr.org/2015/087.pdf, in IACR, 2015. 2. [CF13] Dario Catalano and Dario Fiore. Vector commitments and their applications. https://eprint.iacr.org/2011/495.pdf, in IACR, 2013. 3. [BGH19] Sean Bowe, Jack Grigg, and Daira Hopwood. Recursive proof composition without a trusted setup. https://eprint.iacr.org/2019/1021.pdf, in IACR, 2019. 4. [KZG10] Aniket Kate, Gregory M Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf, in AsiaCrypt, 2010. 5. [CFKS10] Hien Chu, Dario Fiore, Dimitris Kolonelos, and Dominique Schröder. Inner product functional commitments with constant-size public parameters and openings. https://eprint.iacr.org/2022/524.pdf, in AsiaCrypt, 2010. 6. [Kus18] John Kuszmaul. Verkle trees. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf, 2018. 7. [But21] Vitalik Buterin. Verkle trees. https://vitalik.ca/general/2021/06/18/verkle.html, 2021. 8. [Fei21] Dankrad Feist. Verkle trie for eth1 state. https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html, 2021. 9. [Fio22] Dario Fiore. A journey in vector commitments. https://www.youtube.com/watch?v=Zi3akuyDzMs, 2022. 10. [Dra19] Justin Drakes. Zk study club: Part 1 polynomial commitments with Justin Drakes. https://www.youtube.com/watch?v=bz16BURH_u8, 2019. [A Hierarchical View of Cryptographic Commitment Schemes](/@kullervo/commitmentHierarchy)