This document was written to remove some of my FUD experienced when reading NIZK specification in papers such as Crypsinous and Zerocash. I wanted to understand the structure of these specifications and perhaps even be able to write them myself.

First up, learning the jargon, I’ve started an NIZK glossary as a cheat sheet and will link to the definitions throughout this document:

Best way to understand is by building so lets build out a toy NIZK specification:

The main steps in defining an NIZK are:

1. define an NP language $\mathcal{L}$ for each NIZK statement you would like to make
2. Ensure your NIZK statements are Universally Composable

A Toy NIZK Specification

To get a feel for things, lets write a toy specification for a system that allows users to prove that they hold a secret value $v$ that exceeds a given threshold $T$ i.e. $v > T$.

Setup

Lets imagine we are in the blockchain context, each block has in it’s header the root of a Merkle tree over all secret value commitments. Users can commit to new secret values by getting these commitments included in a block and the commitments will be added to the merkle tree.

With that, let’s build our specification.

Constructing our Language $\mathcal{L}_{\text{THRESH}}\in\text{NP}$.

To define $\mathcal{L}_{\text{THRESH}}$, we need to specify our statement $\mathbf{x}$, witness $\mathbf{w}$, and witness relation $R(\mathbf{x}, \mathbf{w})$.