Implementing zk-SNARK Zero Knowledge Proof in Rust

Imagine holding a sealed envelope containing a secret message. You're tasked with proving the message's contents to a friend, but here's the catch: you can't open the envelope or reveal its contents.

That's the idea behind zk-SNARKs. In the world of cryptography, they're a big deal. And if you're looking to dive into this concept using Rust, the bellman toolkit is your go-to.

This article will break down how zk-SNARKs work and show you how bellman makes them more accessible for developers.

Let's dive into it, starting with a quick recap about zk-SNARKs key concepts.

The foundational pillars of zk-SNARKs

1. Zero-Knowledge

At its core, zero-knowledge proofs aim to uphold a paradoxical scenario: how can one party (the prover) convince another party (the verifier) that they possess a particular knowledge without revealing the essence of that knowledge?

• Example: Think of a color-blinded verifier and a prover with a pair of balls - one red and one green. The prover wants to convince the verifier that the balls are of different colors without revealing which one is red or green. The prover can do this by hiding each ball in separate hands, showing them to the verifier, then hiding them again and switching them or not. The verifier can ask the prover to reveal the balls. If they are being switched correctly, the verifier becomes convinced they are of different colors over multiple rounds without knowing which one is which.

This concept is vital in scenarios where information needs to remain confidential, but its authenticity or validity still needs verification.

2. Succinctness

In cryptographic terms, succinctness implies that the proof should be both small in size and quick to verify, irrespective of the original statement's complexity or length. This is particularly crucial in ensuring scalability and practicality. If every proof were lengthy or took a considerable time to validate, systems based on zk-SNARKs would become sluggish and impractical.

• Example: Imagine sending a message that is hundreds of pages long. Instead of reading each page, you get a 'summary' that is just a paragraph but still captures the essence. Even though the 'summary' (proof) is much shorter than the original message (statement), it still gives you confidence in the content.

3. Non-Interactive

The "Non-Interactive" aspect of zk-SNARKs is about the communication between the prover and verifier. In many cryptographic systems, the prover and verifier need multiple rounds of communication to reach consensus. However, with zk-SNARKs, the prover can generate a single proof and send it to the verifier without any need for further back-and-forth interaction.

4. Arguments of Knowledge

This emphasizes that zk-SNARKs aren't just proofs of a statement's validity, but proofs that the prover possesses specific knowledge. The distinction here is subtle but significant. It's not just about proving a statement like "two numbers multiply to give 12" but proving that "I know two numbers that multiply to give 12" without revealing the numbers.

Introduction to the Rust 'bellman' Crate

What is the bellman crate?

The bellman crate is a Rust library for building zk-SNARKs. With a focus on modularity and ease of use, bellman developers can construct and verify zero-knowledge proofs. It offers a generic API that can be adapted to various cryptographic pairing-friendly elliptic curves.

The bellman library facilitates the construction of zk-SNARK systems, which hinge on several fundamental ideas.

Key Concepts in bellman

1. Circuits

In zk-SNARKs, computations are represented as circuits. These aren't your conventional electrical circuits but are abstract representations of computations where inputs pass through gates to produce outputs.

• Gate: A basic unit of computation. For zk-SNARKs, common gates are addition and multiplication gates.
• Witness: The set of all intermediate values in a circuit.
• Public Inputs: Inputs that are public knowledge.
• Private Inputs: Inputs that the prover knows but does not want to reveal.

2. R1CS (Rank-1 Constraint Systems)

R1CS is a way to represent a circuit. The bellman crate employs R1CS for constructing zk-SNARKs.

• Constraint: An equation that must be satisfied for the circuit to be considered valid.
• Linear Combination: A combination of variables multiplied by coefficients.
• R1CS Constraints: Equations represented in the form A * B = C, where A, B, and C are linear combinations.

In bellman, when you're defining your circuit, you're essentially adding these constraints. The cs.enforce() method is how you add constraints.

3. Parameters

zk-SNARKs require specific parameters to be generated for creating and verifying proofs.

• Proving Key: Used to generate proofs.
• Verifying Key: Used to verify proofs.

Usually, there's an initial trusted setup phase where these parameters are generated. The randomness used in this phase must be discarded; otherwise, it could be used to generate fake proofs.

4. Proofs

Once you have a circuit (R1CS representation) and parameters:

• Proof Generation: A prover, who knows the private inputs, uses the proving key to produce a proof that they know such inputs that satisfy the circuit's constraints without revealing the inputs.
• Proof Verification: A verifier, using the verifying key, can check the validity of the proof. If it's valid, it means the prover knows the private inputs, even though the verifier doesn't learn what they are.

5. Pairing-friendly Elliptic Curves

bellman works with pairing-friendly elliptic curves, a type of elliptic curve that supports a bilinear pairing operation. This operation is foundational for the cryptographic processes in zk-SNARKs. The library often uses the BLS12-381 curve, widely recognized for its security and efficiency.

Basic Usage of bellman

Let's dive into a simple example using the bellman crate.

Setting up the Environment

Firstly, you'll want to include the bellman crate in your Cargo.toml:

[dependencies]
bellman = "0.8"  # Check the latest version on crates.io
        

Then, add the necessary imports:

extern crate bellman;
use bellman::{Circuit, ConstraintSystem, SynthesisError};
        

Deep Dive Example

Let's explore the circuit concept further. Imagine you want to prove you know the square root of a number x without revealing the square root.

struct SquareRootCircuit<F> {
    x: Option<F>,
    root: Option<F>,
}

impl<F: Field> Circuit<F> for SquareRootCircuit<F> {
    fn synthesize<CS: ConstraintSystem<F>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
        let x = cs.alloc(|| "x", || self.x.ok_or(SynthesisError::AssignmentMissing))?;
        let root = cs.alloc(|| "root", || self.root.ok_or(SynthesisError::AssignmentMissing))?;
        
        // root * root = x
        cs.enforce(
            || "square",
            |lc| lc + root,
            |lc| lc + root,
            |lc| lc + x,
        );

        Ok(())
    }
}
        

In the above example, the prover wants to prove knowledge of the root of x. The constraint ensures that root it is indeed the square root of x.

When leveraging bellman, you would proceed to create parameters, and generate a proof with a known root, and then anyone can verify this proof without ever knowing the root.

A slightly more advanced example

Let's build on the foundational knowledge of zk-SNARKs to create a slightly more advanced example using bellman.

Consider a scenario where a student wants to prove to a potential employer that they have a diploma from a certain university, without revealing the university's name or the grade they achieved.

Problem Statement

Prove that you possess a diploma from one of three universities (A, B, or C) and that your grade is above a certain threshold, without revealing the exact university or the grade.

Implementation with bellman

Firstly, set up the environment:

extern crate bellman;
use bellman::{Circuit, ConstraintSystem, SynthesisError};
use pairing::bls12_381::{Bls12, Fr};
        

Define the circuit:

struct DiplomaCircuit<F: Field> {
    // Encoded representation of universities: A = 1, B = 2, C = 3
    university: Option<F>, 
    // Encoded representation of grades: Fail = 0, Pass = 1
    grade: Option<F>,
    threshold: F
}

impl<F: Field> Circuit<F> for DiplomaCircuit<F> {
    fn synthesize<CS: ConstraintSystem<F>>(self, cs: &mut CS) -> Result<(), SynthesisError> {
        let university = cs.alloc(|| "university", || self.university.ok_or(SynthesisError::AssignmentMissing))?;
        let grade = cs.alloc(|| "grade", || self.grade.ok_or(SynthesisError::AssignmentMissing))?;

        // Constraint 1: University should be one of A, B, or C.
        cs.enforce(
            || "valid university",
            |lc| lc + (F::one(), university) - F::one(),
            |lc| lc + (F::from(2u32), university) - F::one(),
            |lc| lc + (F::from(3u32), university) - F::one(),
        );

        // Constraint 2: Grade should be above the threshold.
        cs.enforce(
            || "grade above threshold",
            |lc| lc + grade,
            |lc| lc + CS::one(),
            |lc| lc + self.threshold,
        );

        Ok(())
    }
}
        

In this example, we've made some simplifications. Universities are encoded as integers, and the grade is a binary encoding. The actual implementation might be more complex, especially when considering multiple courses, real grade values, and a more extensive set of universities.

Let's now demonstrate how parameter generation, proof creation, and verification would work using the bellman crate.

1. Parameter Generation

The parameter generation is usually done once for a given circuit structure. This phase results in a proving key and a verifying key.

use bellman::groth16::{generate_random_parameters, prepare_verifying_key, create_random_proof, verify_proof};
use rand::rngs::OsRng;  // or another suitable RNG

fn main() {
    let rng = &mut OsRng;

    // Generate parameters based on our circuit
    let params = {
        let empty_circuit = DiplomaCircuit::<Fr> {
            university: None,
            grade: None,
            threshold: Fr::from(1u32),  // Assuming a binary encoding for grade
        };
        generate_random_parameters::<Bls12, _, _>(empty_circuit, rng).expect("Parameter generation failed")
    };
}
        

2. Proof Generation

With the proving key and secret inputs, we can generate a zk-SNARK proof.

// Let's create a proof for having a diploma from university `A` (encoded as 1) with a passing grade (encoded as 1).
    let prover_circuit = DiplomaCircuit {
        university: Some(Fr::from(1u32)),
        grade: Some(Fr::from(1u32)),
        threshold: Fr::from(1u32),
    };

    let proof = create_random_proof(prover_circuit, &params, rng).expect("Proof generation failed");
        

3. Proof Verification

Anyone can verify the proof with the verifying key and public inputs (in this case, just the threshold).

    let pvk = prepare_verifying_key(&params.vk);
    let public_inputs = vec![Fr::from(1u32)];  // Our threshold for passing grade

    assert!(verify_proof(&pvk, &proof, &public_inputs).expect("Proof verification failed"));
}
        

The assertion here confirms that the provided proof is valid with respect to the given public inputs and verifying key.

The Lifecycle of a zk-SNARK with bellman

To appreciate the depth of what bellman offers, it's important to understand the general flow of a zk-SNARK:

1. Define the Problem: This is where you decide on the computation you want to prove knowledge of without revealing certain inputs. In the context of bellman, this involves creating a Rust struct that implements the Circuit trait.
2. Setup: This is a one-time phase where the cryptographic parameters (proving key and verifying key) are generated. In bellman, you'll use methods like generate_random_parameters for this. Remember, the randomness used here must be discarded to ensure the system's security.
3. Prove: With the proving key and your private inputs, you generate a proof. This proof asserts: "I know certain values that satisfy the given computation." Yet, it doesn't reveal any of those values. bellman provides the create_random_proof function for this.
4. Verify: This is the magic of zk-SNARKs. Someone else, with just the verifying key and public inputs (but without the private inputs or knowledge of the computation's internals), can verify the validity of the proof. They'll be assured that the prover knows the private values that satisfy the computation, without learning what those values are. In bellman, you'll use the verify_proof function for this.

Advanced Features of bellman

Beyond the basics, bellman offers several advanced features:

• Multi-threaded Proving: zk-SNARK proof generation can be computationally heavy. bellman supports multi-threading, allowing proofs to be generated faster on multi-core machines.
• Custom Curves: While BLS12-381 is a common choice, bellman is designed to be flexible. If you have a specific elliptic curve you'd like to use, you can integrate it with bellman, provided it's pairing-friendly.
• Batch Verification: If you have multiple proofs to verify, doing them individually can be inefficient. bellman supports batch verification, which is faster than verifying each proof individually.
• Recursive zk-SNARKs: This is a more advanced topic, but in essence, it allows for proofs about proofs. This can be especially valuable in scaling solutions for blockchains.

Read more articles about Rust in my Rust Programming Library !

This full flow—from parameter generation through proof creation to verification—gives a glimpse of how zk-SNARKs can be employed in real-world scenarios using the bellman crate.

So, we've had a deep dive into zk-SNARKs and got our hands dirty with bellman.

Happy coding, and keep those gears turning! ??????

Read more articles about Rust in my Rust Programming Library !

Visit my Blog for more articles, news, and software engineering stuff!

Follow me on Medium , LinkedIn , and Twitter .

All the best,

CTO | Tech Lead | Senior Software Engineer | Cloud Solutions Architect | Rust ?? | Golang | Java | ML AI & Statistics | Web3 & Blockchain