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:
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()) 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:
## 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.