Zero-knowledge proofs library in petlib

23 January 2016

The petlib library exposes basic elliptic curve (EC), big number and crypto functions. As an example, I also implemented genzkp.py, a simple non-interactive zero-knowledge proof engine. This is a short tutorial on how to use genzkp, in case you need a proof of knowledge and do not wish to write all details by hand.

We will use as a running example proving knowledge of the opening and the secret of a Pedersen commitment over an elliptic curve field. In a nutshell the prover defines a commitment of the form:statement

The variables h and g are publicly known points on an elliptic curve. The commitment Cxo commits to the secret value x, using the secret opening value o. One can show that this commitment scheme provides perfect hiding and computational binding. The creator of this commitment may with to prove it knows values x and o, without revealing them. For this we can use an non-interactive zero-knowledge proof.

First we need to load the petlib Elliptic Curve module petlib.ec and the genzkp functions used to define and verify proofs. We then define an EC group G, and its order. As it happens group 713 is OpenSSL’s “NIST/SECG curve over a 224 bit prime field“.

from petlib.ec import EcGroup
from genzkp import ZKProof, ZKEnv, ConstGen, Sec
# Define an EC group
G = EcGroup(713)
print (EcGroup.list_curves()[713])
order = G.order()

Next we need to define the proof statement using an instance of ZKProof, namely zk. The proof variables and constants are defined using zk.get() (or zk.get_list()). This function takes the type of variables defines, either a constant generator ConstGen, a secret Sec or a generator Gen that is used internally by the proof. It also takes the names of the variables, as they are going to be used later to bind values to them during the construction and verification of the proof. After defining all variables one or more linear statements can be associated with the proof, such as Cxo = x*g+o*h, using the add_proof method.

## Define the Zero-Knowledge proof statement
zk = ZKProof(G)
g, h = zk.get(ConstGen, ["g", "h"])
x, o = zk.get(Sec, ["x", "o"])
Cxo = zk.get(ConstGen, "Cxo")
zk.add_proof(Cxo, x*g + o*h)

For debugging or other visualization purposes the proof statement can be printed out in Latex using the render_proof_statement method. When compiled in a Latex document this renders to:

fullstatement

## Render the proof statement in Latex
print(zk.render_proof_statement())

Using standard petlib math function, we can build a concrete Pedersen commitment using random h, x an o, an define Cxo = x*g+o*h.

# A concrete Pedersen commitment
ec_g = G.generator()
ec_h = order.random() * ec_g
bn_x = order.random()
bn_o = order.random()
ec_Cxo = bn_x * ec_g + bn_o * ec_h

The concrete secrets, EC points and commitment then need to be bound to the variables of the zero-knowledge proof. We can do this by defining an environment, using ZKEnv, and binding the values to the proof variable names. For example, env.x = bn_x binds the value bn_x to the proof variable x. Since we are first to prove the statement, all secrets need to be defined.

## Bind the concrete variables to the Proof
env = ZKEnv(zk)
env.g, env.h = ec_g, ec_h 
env.Cxo = ec_Cxo
env.x = bn_x 
env.o = bn_o

Finally, on the prover size, we construct the signature (or NIZK) using the build_proof function. This can be serialized and deserialized using the petlib.pack functions if necessary.

# Create the Non-Interactive Zero-Knowledge (NIZK) proof
sig = zk.build_proof(env.get())

On the verification side, the exact same statement needs to be defines, as zk. An environment is then created binding values to all public variables (g, h and Cxo), but not to the secrets.

# Execute the verification on the proof 'sig'
env = ZKEnv(zk)
env.g, env.h = ec_g, ec_h 
env.Cxo = ec_Cxo

The verification is then performed to ensure the signature and the environment may be used to verify the statement of the NIZK.

assert zk.verify_proof(env.get(), sig)

The genzkp library has been used to implement all proofs of the examples/amacscreds.py anonymous credential system. The proofs of these scheme are elaborate and illustrate how to define lists of secrets or lists of public generators, parametrically.

The full source code of the running example is also available.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: