Please read the editorial disclaimer.
Participants:
Context. This page was prepared for a breakout session during the ZKProof 4th workshop. The goal of this document is to receive concurrent/collaborative suggestions of content that may be useful for the "ZKProof Community Reference" (ZkpComRef).
Goal. We will create a new subsection in ZkpComRef that describes cryptographic primitives that are optimized for efficient implementation within the constraint systems of ZK proof systems.
Existing WG amd resources. At ZKProof3, we initiate a working group for detailed study and description of SNARK-friendly primitives, aiming to create a dedicated document that specifies them precisely and discussed them at depth. The current effort has a smaller scope: a brief high-level description to be integrated into ZkpComRef. None the less, the deliberations and resources of the existing working group provide valuable resources:
Content. We seek to add an overview discussion of ZK-friendly primitives (why they're needed, what approaches are taken, etc.), followed by a brief enumeration of major known ones. Each specific ZK-friendly primitive should be described in a couple of paragraphs, following the template below.
Expectations. This material is collected for inclusion into ZkpComRef, subject to review and editing by the ZKProof editors. It is licensed under CC-BY 4.0 International License. After inclusion in the ZkpComRef, it may be updated as part of the usual ZkpComRef editorial process.
Contributions. To contribute a new case study, duplicate the template below, fill in the details, and send an email to "editors at zkproof dot com" to confirm your contribution.
Guidelines:
This is an example. Alice
Generic examples belong in Section 42 of ZkpComRef, so move there and reference. Bob
Add an overview discussion of ZK-friendly primitives: why they're needed, what approaches are taken, etc.
Do not edit or delete this template; instead, copy-paste its content inside one of the available suggestion placeholders below, and then edit it there.
Replace all italicized text, total is up to ½ a page + unlimited diagrams.
Contributors: [fill in]
Functionality: Is it a CRH? An accumulator? A coffee-maker?
Applicable context: What ZKP scheme context it applicable/optimized for?
Specification and implementation: Where is it defined? Is it a family and what does it consist of? Where can we find implementations?
Security: Security claims, assumptions/models, and known analysis.
Performance: Indicative cost/performance numbers, e.g., in constraint counts or milliseconds.
A Bowe–Hopwood Pedersen hash is an algebraic hash function. It is based on the work of David Chaum, Ivan Damgård, Jeroen van de Graaf, Jurjen Bos, George Purdy, Eugène van Heijst and Birgit Pfitzmann in [CDvdG1987], [BCP1988] and [CvHP1991], and of Mihir Bellare, Oded Goldreich, and Shafi Goldwasser in [BGG1995], with optimizations for efficient instantiation in zk-SNARK circuits by Sean Bowe and Daira Hopwood.
It is assumed that the field over the circuit is defined is a suitable base field for an Edwards and/or Montgomery curve. (There is a birational equivalence between these two curve types.) It is particularly useful for circuits that already depend on a specific elliptic curve for their security or functionality.
This hash function was originally optimized for R1CS circuits, providing roughly a ?x improvement in constraint count over a straightforward implementation of a Pedersen hash. The optimizations arise mainly from:
The collision resistance (for fixed input length) of this hash is derived from assumed hardness of the Discrete Logarithm Problem on an elliptic curve. It does not have any other security properties typically associated with hash functions; for example it is not suitable to instantiate a random oracle, or for pre-image resistance.
Typically 869 R1CS constraints for a ~512-bit input, i.e. just under 1.7 constraints per bit. This assumes that the input is already decomposed into bits.
Poseidon is a recently designed cryptographic permutation described in GKRRS2019. It operates over a sequence of finite field elements of fixed length, referred to as the "width".
Poseidon can be used in a "sponge" configuration BDPA2011 to instantiate a general hash function or a cipher, for example.
Poseidon is designed for circuit defined over prime fields. The field size is quite flexible, although there are interactions between this size and the available parameters.
As a recently designed symmetric primitive, the cryptanalytic effort that has been applied to Poseidon does not compare to more well-established hash functions such as SHA-256, SHA-3, or BLAKE2, or to ciphers such as AES. Nevertheless, Poseidon is generally believed to have a substantial security margin when used with the recommended number of rounds. GKRRS2019 KR2020 BCD+2020 GRS2020
TODO: table of performance against width. (Performance per hashed field element is generally better for higher widths.)
A Wegmann–Carter polynomial MAC is a message authentication code with statistical security, given that a key is only used once. The restriction on key reuse can be relaxed by combining it with a key derivation function, for example based on another SNARK-friendly primitive such as Poseidon.
An example of such a polynomial MAC is Poly1305, which is frequently used in non-zk-proof applications. The proposed primitive here is essentially Poly1305 generalized to an arbitrary field. The field size should be a prime of at least 128 bits.
No deployments known.
Polynomial MACs are extremely efficient in a circuit: they essentially only require one multiplication per field element of input, plus the cost of the primitive used for key derivation. For example, if keyed Poseidon is used for the latter, then the cost would be 1 R1CS constraint per field element, plus a cost independent of message length of ??? (a few hundred constraints).
https://cr.yp.to/mac/poly1305-20050329.pdf
BLAKE2s is a general-purpose hash function, providing collision resistance and pre-image resistance, and also suitable to instantiate a random oracle.
A conservative choice of hash function, for applications where only a small number of hashes are needed or where confidence in cryptographic security is an overriding factor.
BLAKE2s is a well-established hash function that is generally considered to have a high security margin. TODO: references
In R1CS, BLAKE2s can be implemented in ~21600 constraints. In PLONK, it can be implemented in somewhere between 1000-3000 constraints [I think –Daira]
This is significantly larger than Poseidon or Pedersen hashes, but smaller than for example SHA-256 or SHA-3/Keccak.
The Boneh-Lynn-Shacham signatures [BLS01] are a type of pairing-based signature scheme that allows for the aggregation of the signatures, enabling amortization of the verification of several signatures at the cost of one verification. In this context, we are interested in computing in zero-knowledge the verification algorithm (and not the signature algorithm)
One of the challenges of implementing BLS signatures as part of a ZK system is to perform pairing operations inside of the circuit / constraint system. Furthermore, the base field over which the pairing-friendly curve is defined is best to be efficient in the underlying field of the proving system. This would normally, for practical efficiency, require use of one of:
The complexity of correctly and efficiently implementing a pairing operation in a circuit is substantial and should not be underestimated.
BLS signatures can be used in different contexts where the amount of signatures to be verified at once is large and using BLS + ZK proofs can compress the cost. These include Blockchain consensus protocols.