dalek-cryptography / zkp

Experimental zero-knowledge proof compiler in Rust macros

zkp: a toolkit for Schnorr proofs

This crate has a toolkit for Schnorr-style zero-knowledge proofs, instantiated using the ristretto255 group.

It provides two levels of API:

• a higher-level, declarative API based around the define_proof macro, which provides an embedded DSL for specifying proof statements in Camenisch-Stadler-like notation:

  define_proof! {
    vrf_proof,   // Name of the module for generated implementation
    "VRF",       // Label for the proof statement
    (x),         // Secret variables
    (A, G, H),   // Public variables unique to each proof
    (B) :        // Public variables common between proofs
    A = (x * B), // Statements to prove
    G = (x * H) 
    }
  

  This expands into a module containing an implementation of proving, verification, and batch verification. Proving uses constant-time implementations, and the proofs have a derived implementation of (memory-safe) serialization and deserialization via Serde.

• a lower-level, imperative API inspired by Bellman, which provides a constraint system for Schnorr-style statements. This allows programmable construction of proof statements at runtime. The higher-level define_proof macro expands into an invocation of the lower-level API. The lower-level API is contained in the toolbox module.

Examples

Examples of how to use the API can be found in the library's tests directory.

Currently, the examples include:

• Specification of an "anonymous credential presentation with 10 hidden attributes" proof from CMZ'13. Depending on the backend selection, the generated implementation is between 20 to 40 times faster than the benchmark numbers reported in that paper.

• A transcript-based signature and VRF construction with an auto-generated implementation. This includes an example of using the online interactive composition described in the Merlin blog post to provide chained signatures with a counterparty.

• An example of using the lower-level constraint system API.

Use and features

To enable the define_proof macro, import the crate like so:

#[macro_use]
extern crate zkp;

Nightly features

The nightly feature enables nightly-specific features. It is required to build the documentation.

Backend selection

zkp provides the following pass-through features to select a curve25519-dalek backend:

• u32_backend
• u64_backend
• simd_backend

Transcript debugging

The debug-transcript feature is for development and testing, and prints a log of the data fed into the proof transcript.

Autogenerated benchmarks

The define_proof macro builds benchmarks for the generated proof statements, but because these are generated in the client crate (where the macro expansion happens), they need an extra step to be enabled.

To enable generated benchmarks in your crate, do the following:

• Add a bench feature to your crate's Cargo.toml;
• Add #[cfg_attr(feature = "bench", feature(test))] to your crate's lib.rs or main.rs, to enable Rust's nightly-only benchmark feature.

WARNING

THIS IMPLEMENTATION IS NOT YET READY FOR PRODUCTION USE

While I expect the 1.0 version to be largely unchanged from the current code, for now there are no stability guarantees on the proofs, so they should not yet be deployed.

zkp's Issues

Save time using batch-double-and-compress

Rewrite documentation

The existing documentation should be moved into a markdown file that explains the two levels of the API (declarative / imperative), and has a description of the design choices.

Rewrite crate to have a constraint system API (like Bellman or Bulletproofs)

The current implementation uses the create_nipk macro to generate standalone modules for each proof statement. But all of the proof statements have to be known at compile time, and it's not possible to define proof statements programmatically.

To fix this, the crate should be rewritten in the following way: there should be a new constraint system API for defining Schnorr constraints (i.e., exactly the language which is currently supported, an AND of a bunch of linear combinations of public variables by witness variables). Then, the existing create_nipk macro should be rewritten to use that API internally, instead of just generating code directly.

What should the constraint system API look like? Drawing on the Bellman and Bulletproofs APIs, it should have the following pieces:

• a SchnorrCS trait with methods for:
  • allocating and assigning instance variables (the variable assignments are RistrettoPoints)
  • allocating and assigning witness variables (the variable assignments are Option<Scalar>s)
  • adding a constraint (an LHS instance variable constrained to equal a linear combination of instance variables by witness variables)
• a ProverCS type implementing the SchnorrCS trait. The ProverCS should have a prove(mut self) method that consumes the constraint system to produce a proof, or maybe multiple proving methods for different kinds of proofs (e.g., compact vs batchable).
• a VerifierCS type implementing the SchnorrCS trait. The VerifierCS should have a verify(mut self, ...) method that consumes the constraint system to verify a proof (again, maybe multiple, in case there are multiple proof formats).

This API can coexist with the current macro, because the two would sit at different levels: the constraint system API has the user declare their proof statements programmatically, while the macro has the user declare them declaratively.

Change assignment structs to avoid redundant compressions / decompressions

Currently the ProveAssignments and VerifyAssignments force redundant compressions / decompressions because they require that all assignments are either compressed or uncompressed. Instead, they should use an enum to allow either or both (i.e., if the caller has both the compressed and uncompressed forms, there should be no additional work).

Ensure generated types derive appropriate traits (e.g., Debug)

For instance, CompactProof does not implement Debug.

Errors trying to compile sample ZKP code sig_and_vrf_example.rs

I'm getting the following errors when trying to compile code sig_and_vrf_example.rs.
Rust version: 1.47.0

ERROR 1
error[E0308]: mismatched types
--> src/main.rs:91:20
|
91 | x: &self.sk.0,
| ^^^^^^^^^^ expected struct zkp::curve25519_dalek_ng::scalar::Scalar, found struct curve25519_dalek::scalar::Scalar
|
= note: expected reference &zkp::curve25519_dalek_ng::scalar::Scalar
found reference &curve25519_dalek::scalar::Scalar

Cargo.tml
...
[dependencies]
zkp = "0.8.0"
rand = "0.7"
curve25519-dalek = { version = "2", default-features = false, features = ["serde", "std"] }

[features]
default = ["u64_backend"]
u32_backend = ["curve25519-dalek/u32_backend"]
u64_backend = ["curve25519-dalek/u64_backend"]
simd_backend = ["curve25519-dalek/simd_backend"]

ERROR 2
Also, if trying using the latest version of rand and curve25519, get a different error:
error[E0277]: the trait bound R: zkp::rand::RngCore is not satisfied
--> src/main.rs:49:34
|
49 | SecretKey(Scalar::random(rng))
| ^^^ the trait zkp::rand::RngCore is not implemented for R
|
::: /home/oracle/.cargo/registry/src/github.com-1ecc6299db9ec823/curve25519-dalek-3.0.2/src/scalar.rs:558:22
|
558 | pub fn random<R: RngCore + CryptoRng>(rng: &mut R) -> Self {
| ------- required by this bound in curve25519_dalek::scalar::Scalar::random
|
help: consider further restricting this bound
|
48 | fn new<R: RngCore + CryptoRng + zkp::rand::RngCore>(rng: &mut R) -> SecretKey {
| ^^^^^^^^^^^^^^^^^^^^

Cargo.toml
...
[dependencies]
zkp = "0.8.0"
rand = "0.8.3"
curve25519-dalek = "3.0.2"

Implement two flavors of proofs: compact and batchable

Add examples as unit tests

Restructure the existing tests so that each test file contains a proof statement and some example code showing how that statement is used.

Figure out a stability story

This might look like "use cargo expand" before deploying the code