This module is supposed to be used together with =nil;Crypto3 zk. The blueprint module is used to generate the input data in form of a constraint system, while crypto3-zk is used to process them as input for what to prove.
In this document, we introduce the very basic concepts of blueprint. For the example of usage please follow the usage markdown or look through the simple example.
Preliminaries
If you are a developer who is completely new to zk-SNARKS we would recommend you to look through this great resource with the list of the most meaningful zk-related papers and posts. You can find there both thorough pure-technical papers and high-level overview of zk technologies.
Quick intro to R1CS
A Rank One Constraint System (R1CS) is a way to express a computation that makes it amenable to zero knowledge proofs. Basically any computation can be reduced (or flattened) to an R1CS. A single rank one constraint on a vector w is defined as
Where A, B, C are vectors of the same length as w, and <> denotes inner product of vectors. A R1CS is then a system of these kinds of equations:
The vector w is called a witness and zk-SNARK proofs can always be reduced to proving that the prover knows a witness w such that the R1CS is satisfied.
Basics:
1. The Blueprint
In the =nil; Crypto3 Blueprint tool, the blueprint is where our "circuits" (i.e. PLONK, R1CS and components) will be collected.
The C++ file defining the blueprint is here. We will first show how to add R1CS to the blueprint.
Let's assume, that we want to prove knowing of a value x that satisfies the equation
We can make this a little more general, and say that given a publicly known output value out, we want to prove that we know x such that
Recall that we can introduce some new variables sym_1, y, sym_2 and flatten the above equation into the following quadratic equations:
We can verify that the above system can be written as an R1CS with
and the vectors A_1, ..., A_4, B_1, ..., B4, C_1, ..., C_4 are given by
The original degree 3 polynomial equation has a solution x=3 and we can verify that the R1CS has a corresponding solution
Now let’s see how we can enter this R1CS into =nil;Crypto3 Blueprint, produce proofs and verify them. We will use the blueprint_variable type to declare our variables. See the file test.cpp for the full code.
First lets define the finite field where all our values live, and initialize the curve parameters:
Next we define the blueprint and the variables we need. Note that the variable one is automatically defined in the blueprint.
Next we need to "allocate" the variables on the blueprint. This will associate the variables to a blueprint and will allow us to use the variables to define R1CS constraints.
Note that we are allocating the out variable first. This is because =nil;Crypto3 Blueprint divides the allocated variables in a blueprint into "primary" (i.e. public) and "auxiliary" (i.e. private) variables. To specify which variables are public and which ones are private we use the blueprint function set_input_sizes(n) to specify that the first n variables are public, and the rest are private. In our case we have one public variable out, so we use
to specify that the variable out should be public, and the rest private.
Next let's add the above R1CS constraints to the blueprint. This is straightforward once we have the variables allocated:
Now that we have our circuit in the form of R1CS constraints on the blueprint we can run the Generator and generate proving keys and verification keys for our circuit:
Note that the above is the so-called "trusted setup". We can access the proving key through keypair.pk and the verification key through keypair.vk.
Next we want to generate a proof. For this we need to set the values of the public variables in the blueprint, and also set witness values for the private variables:
Now that the values are set in the blueprint we can access the public values through bp.primary_input() and the private values through bp.auxiliary_input(). Let's use the proving key, the public inputs and the private inputs to create a proof that we know the witness values:
Now that we have a proof we can also verify it, using the previously created proof, the verifying key keypair.vk and the public input bp.primary_input():
At this stage the boolean verified should have the value true, given that we put in the correct values for the witness variables.
2. Components
The =nil;Crypto3 Blueprint library uses components to package up R1CS into more manageable pieces and to create cleaner interfaces for developers. They do this by being a wrapper around a blueprint and handling generating R1CS constraints and also generating witness values.
We're going to show how to create a component for the example R1CS above in order to make it a bit more manageable.
First we create a new file src/component.hpp which contains the component file. In our case we want the developer using the component to be able to set the public variable out, as well as the private witness variable x, but the component itself would take care of the intermediate variables y, sym_1 and sym_2.
Thus we create a class test_component, derived from the base component class which has the variables y, sym_1 and sym_2 as private members (in the C++ sense). The variables x and out will be public class member variables.
In the following sections we go over the functions of this component and how to use it.
Constructor
As any component, the constructor takes as input a blueprint bp. We also have blueprint_variable inputs x and out. We assume that the user of the component has already allocated x and out to the blueprint.
The constructor then allocates the intermediate variables to the blueprint:
Function <tt>generate_r1cs_constraints()</tt>
This function adds the R1CS constraints corresponding to the circuits. These are the same constraints as we added manually earlier, just bundled up inside this function.
Function <tt>generate_r1cs_witness()</tt>
This function assumes that we've already set the public value out, and the witness value x. It then computes the inferred witness values for the intermediate variables sym_1, y, sym_2. Thus the user of the component never needs to worry about the intermediate variables.
Using the component
In the file src/test-component.cpp we can see how the component it used. This file is very similar to the file in the previous section. We start as before by generating curve parameters. After this we initialize the blueprint, and allocate the variables out, x to the blueprint:
After this we specify which variables are public and which are private (in the zk-SNARK sense). This would be out as the only public variable and the rest as private variables. We also create a new test_component:
Next generate the R1CS constraints by simply calling the corresponding function:
Now we add the witness values. We add the value 35 for the public variable out and the value 3 for the witness variable x. The rest of the values will be computed inside the component:
That's it! Now we can run the Generator to generate proving and verification keys, create the proof and verify it as we did before.
Examples
Below are two examples, how the constraint system can be generated by =nil; Crypto3 blueprint module.
Inner-product component
Let's show how to create a simple circuit for the calculation of the public inner product of two secret vectors. In crypto3-blueprint library, the blueprint is where arithmetic circuits are collected. The statement (or public values) is called primary_input and the witness (or secret values) is called auxiliary_input. Let bp be a blueprint and A and B are vectors which inner product res has to be calculated.
Then we associate the variables to a blueprint by using the function allocate(). The variable n shows the size of the vectors A and B. Note, that each use of allocate() increases the size of auxiliary_input.
Note, that the first allocated variable on the blueprint is a constant 1. So, the variables on the blueprint would be 1 , res, A[0], ..., A[n-1], B[0], ..., B[n-1].
To specify which variables are public and which ones are private we use the function set_input_sizes(1), so only resvalue is a primary input. Thus, usually, the primary input is allocated before the auxiliary input in the program.
Component is a class for constructing a particular constraint system. The component's constructor allocates intermediate variables, so the developer is responsible for allocation only primary and auxiliary variables. Any Component has to implement at least two methods: generate_r1cs_constraints() and generate_r1cs_witness().
Now we initialize the simple component inner_product. The function generate_r1cs_constraints() adds R1CS constraints to the blueprint corresponding to the circuit.
Next, we set the random values to vectors.
The function generate_r1cs_witness() computes intermediate witness value for the public values and the inner product for the res.
SHA2-256 component
Now we want to consider a more complicated construction of a circuit. Assume that the prover wants to prove that they know a preimage for a hash digest chosen by the verifier, without revealing what the preimage is. Let hash function be a 2-to-1 SHA256 compression function for our example.
We will show the process for some pairing-friendly curve curve_type and its scalar field field_type.
Firstly, we need to create a blueprint and allocate the variables left, right and output at the blueprint. The allocation on the blueprint proceeds at the constructor of digest_variable. Then we initialize the component sha256_two_to_one_hash_component and add constraints at the generate_r1cs_constraints() function.
After the generation of r1cs constraints, we need to transform data blocks into bit vectors. We use a custom pack, which allows us to convert data from an arbitrary data type to bit vectors. The following code can be used for this purpose:
After getting bit vectors, we can generate r1cs witnesses.
Now we have the blueprint with SHA2-256 component on it and can prove our knowledge of the source message using Groth-16 (r1cs_gg_ppzksnark).
Keys & Proof Generation
Using the example above we can finally create and verify proof. We assume here, that prover and generator from crypto3-zk are used.
- The generator
grth16::generatorcreates proving keys and verification keys for our constraints system. - The proving key
keypair.first, public inputbp.primary_input, and private inputbp.auxiliary_inputare used for the constructing of the proof (grth16::prover).
Proof Verification
To verify proof you only need to put all the data in the byte vector and give it as parameter to the TON vm instruction __builtin_tvm_vergrth16 .
zk-SNARK verifier argument has to contain of 3 parts packed together:
verification_key_type vkprimary_input_type primary_inputproof_type proof
Type requirements for those are described in the Groth16 zk-SNARK policy
Byte vector assumes to be byte representation of all the underlying data types, recursively unwrapped to Fp field element and integral std::size_t values. All the values should be putted in the same order the recursion calculated.