Getting started with libsnark

In this two-part series we’ll talk about how to get started with the library
libsnark. We’ll review two very
useful tutorials and give some supplementary commentary along the way.

Howard Wu’s tutorial

For the beginner, your first port of call should be the excellent
tutorial by one of libsnark's
main contributors - Howard Wu. Its README provides step-by-step instructions to
create a simple application that generates an example zk-SNARK proof (based on
the Groth-16 protocol) and verifies it. While you can just clone the
repo and go straight to building and running the application, it’s very
instructive to go through the steps to see how a libsnark based project is
structured. The rest of this post assumes you have managed to build and run the tutorial.

The essence of the tutorial

To give a high level description of what’s going on in the application, let’s
cut down the function run_r1cs_gg_ppzksnark to just the most essential elements:

template<typename ppT>
bool run_r1cs_gg_ppzksnark(const r1cs_example<libff::Fr<ppT> > &example)
{
    r1cs_gg_ppzksnark_keypair<ppT> keypair =
    r1cs_gg_ppzksnark_generator<ppT>(example.constraint_system);
    r1cs_gg_ppzksnark_proof<ppT> proof =
    r1cs_gg_ppzksnark_prover<ppT>(keypair.pk,
                                    example.primary_input,
                                    example.auxiliary_input);
    const bool ans =
      r1cs_gg_ppzksnark_verifier_strong_IC<ppT>(keypair.vk,
                                                example.primary_input,
                                                proof);
    // ... etc.
}

These three function calls describe the basic workflow common to most zk-SNARK protocols:

1. Given a R1CS (Rank-1 constraint system) — here called example -
   the function
   r1cs_gg_ppzksnark_generator generates a keypair - one for the prover and
   the other for the verifier.
2. The prover takes her key and together with the inputs of the example R1CS,
   builds a proof with r1cs_gg_ppzksnark_prover. Note that the inputs
   include both public values (primary_input - known also to the verifier) and
   private “witness” values (auxiliary_input - not revealed to the verifier).
3. Together with the public inputs and the verification key, the verifier checks
   the proof with r1cs_gg_ppzksnark_verifier_strong_IC, which should return
   true if the proof was indeed provided a satisfying witness by the prover.

The libsnark functions to use will differ from one program to next, but the
basic pattern will remain similar to the above.

libsnark functions

A point to note here is that the particular functions and types used will
depend on a number of factors. In this case, we’re working with a Groth-16
zk-SNARK which determines that the functions prefixed with r1cs_gg_ppzksnark_
should be used.

In fact, the particular verification function to call depends on no less than three factors:

• As mentioned already, the SNARK to use.
• The verification key — processed keys contains a small constant amount of
  additional pre-computed information that enables a faster verification time.
  In this case the verifier is called an online verifier.
• Weak vs strong input consistency (IC) — strong IC means the number of
  primary inputs matches exactly the number of inputs of the constraint system
  where as weak IC relaxes this requirement.

In the example above, a standard non-processed key is used for verification with
strong input consistency:

template<typename ppT>
bool r1cs_gg_ppzksnark_verifier_strong_IC(
  const r1cs_gg_ppzksnark_verification_key<ppT> &vk,
  const r1cs_gg_ppzksnark_primary_input<ppT> &primary_input,
  const r1cs_gg_ppzksnark_proof<ppT> &proof);

As another example, the same SNARK but with a processed verification key and only weak
input consistency would use the following verification function instead:

template<typename ppT>
bool r1cs_gg_ppzksnark_online_verifier_weak_IC(
  const r1cs_gg_ppzksnark_processed_verification_key<ppT> &pvk,
  const r1cs_gg_ppzksnark_primary_input<ppT> &input,
  const r1cs_gg_ppzksnark_proof<ppT> &proof);

Using this online verifier implies some additional processing to the standard
verification key by passing it to a function
r1cs_gg_ppzksnark_verifier_process_vk to produce the
r1cs_gg_ppzksnark_processed_verification_key.

See the libsnark source code for more details.

While Howard Wu’s tutorial shows an example of this very important pattern of
working with a zk-SNARK, it does not say much about how one actually goes about
constructing R1CS objects in practice. This (and more) will be the topic of the next post.