owned this note   changed 4 years ago  
Published Linked with GitHub

#4 - Home Edition

ZkpComRef: SNARK-Friendly Primitives

Please read the editorial disclaimer.

Participants:

Collaboration Instructions

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:

  • Size: Each primitive should be desvribed in a couple of paragraphs (up to half a page), excluding diagrams (which are very welcome and do not count for the space limit).
  • Simplicity: While trying to be cryptographically precise, feel free to handwave some explanations or arguments, for readability purposes. Try to modularize high-level explanations and low-level concrete technicalities.
  • Terminology: When possible, rely on concepts/terminology already present in the ZkpComRef.
  • Introducing general concepts: If you need to introduce general concepts that best belong earlier in the ZkpComRef, please mark these as such and point out the desired location. The ZkpComRef editors will help relocating the text to its proper place, and it won't count towards page limit.
  • References: Add URLs or DOIs for further reading (whether inline or in the end).
    Rules. All interaction/contributions must abide to the ZKProof Charter, IP Policy and Code of Conduct.
  • Comments: Please include editorial comments when useful, and these will be considered when integrating into ZkpComRef. For example:

This is an example. Alice

Generic examples belong in Section 42 of ZkpComRef, so move there and reference. Bob

Overview of SNARK-Friendly Primitives

Add an overview discussion of ZK-friendly primitives: why they're needed, what approaches are taken, etc.

Primitive TEMPLATE

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.

Primitive 0: Pedersen Commitments

Primitive 1: Bowe–Hopwood Pedersen hashes

Functionality

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.

Applicable context

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:

  • using incomplete additions on a Montgomery curve;
  • processing more than one bit of the hash input at once (typically three bits).

Deployments

  • Zcash Sapling (and reuses/forks such as Tezos Sapling, Pirate Chain, …)
  • Filecoin?? (not sure if they switched completely to Poseidon)

Security

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.

Performance

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.

Primitive 2: Poseidon

Functionality

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.

Applicable context

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.

Deployments

  • Filecoin (in Merkle trees)
  • Proposed for Zcash Orchard
  • Mina: in recursive verification for Fiat–Shamir challenges; Merkle trees; and transaction signatures

Security

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

Performance

TODO: table of performance against width. (Performance per hashed field element is generally better for higher widths.)

Primitive 3: Polynomial MACs

Functionality

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.

Applicable context

No deployments known.

Security

Performance

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

Primitive 4: BLAKE2s

Functionality

BLAKE2s is a general-purpose hash function, providing collision resistance and pre-image resistance, and also suitable to instantiate a random oracle.

Applicable context

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.

Deployments

  • Zcash, in two places in the Sapling circuit (as a collision-resistant hash and as a PRF).

Security

BLAKE2s is a well-established hash function that is generally considered to have a high security margin. TODO: references

Performance

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.

Primitive 5: RedDSA

Primitive 5: BLS Signatures

Functionality

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:

  • a 2-chain of curves, of which the smaller is pairing-friendly and the larger is suitable for the proof system; or
  • a 2-cycle of pairing-friendly curves (of which the only known construction is an MNT4/MNT6 cycle); or
  • a half-pairing cycle, if the proof system does not require a pairing.

The complexity of correctly and efficiently implementing a pairing operation in a circuit is substantial and should not be underestimated.

Applicable context

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.

Deployments

  • Celo, for signatures used in a roll-up.

Security

Performance

Select a repo