Basic Usage¶
This page outlines walks through the basic usage of zksk library, leveraging only built-in primitives.
Notation and Syntax¶
The computations are done within cyclic groups induced by elliptic curves. When we use mathematical expressions, we write points in those groups in uppercase, and scalar numbers in lowercase. We write the group operation additively, i.e., \(+\) denotes the group operation.
In code, however, we follow the Python conventions and write both groups and group elements in lowercase.
We use Camenisch-Stadler notation [CS97] for zero-knowledge proofs. A proof of knowledge of a secret integer \(x\) such that \(Y = x G\) for some group element \(G\) is denoted as follows:
Tip
We use petlib library for working with elliptic curves. We strongly advise you to take a look at petlib’s documentation page.
Overview¶
This library enables zero-knowledge proofs that are composed of the following blocks:
Discrete Logarithm representation. A proof of knowledge of secret integers \(x_i\), such that \(Y\) can be written as \(Y = \sum_i x_i G_i\):
\[PK \{ (x_0, x_1, ..., x_n): Y = x_0 G_0 + x_1 G_1 + ... + x_n G_n \}\]AND, conjunctions of other proofs.
OR, disjunctions of other proofs.
Your own custom proof primitive.
Apart from discrete-logarithm representations, we include other useful primitives in the library distribution.
The library supports three different modes of using zero-knowledge proofs:
Interactive proof. You can get the messages that need to be transmitted between a prover and a verifier, along with functionality to verify those messages.
Non-interactive proof through Fiat-Shamir heuristic.
Simulation.
Defining a Simple Proof Statement¶
In this example, we define a proof for the following statement:
Tip
The next steps use petlib’s big number and elliptic curve syntax (petlib.bn,
petlib.ec). We encourage you to get familiar with them on petlib’s
documentation page.
First, we set up the group elements: elliptic curve points \(G_i\), and the secrets \(x_i\).
g0 = group.hash_to_point(b"g0")
g1 = group.hash_to_point(b"g1")
# Preparing the secrets.
# In practice, they probably should be big integers (petlib.bn.Bn)
x0 = Secret()
x1 = Secret()
Then, we can define a proof statement like this:
# First, compute the value, "left-hand side".
y = 4 * g0 + 42 * g1
# Next, create the proof statement.
stmt = DLRep(y, x0 * g0 + x1 * g1)
See the next section for more details about secrets and expressions that can
be specified in zksk.
Executing the Proofs¶
zksk supports both intractive and non-interactive proof modes. To execute the interactive proof
protocol, we are going to instantiate a zksk.base.Verifier and a
zksk.base.Prover. In a realistic setup, one would not get both from the same proof
object (typically the prover and the verifier sides are not running on the same machine).
prover = stmt.get_prover({x0: 4, x1: 42})
verifier = stmt.get_verifier()
The prover and verifier are going to interact using a sigma protocol, ending with the verifier accepting or rejecting the proof.
challenge = verifier.send_challenge(commitment)
response = prover.compute_response(challenge)
assert verifier.verify(response)
Once you have defined your proof along with the values of the secrets, you can
call the zksk.base.Prover.prove() method to get a non-interactive ZK proof
(NIZK):
nizk = stmt.prove({x0: 4, x1: 42})
The returned zksk.base.NIZK object embeds a challenge, a list of
responses, a hash of the proof statement and a precommitment, if any.
To verify a NIZK, the verifier needs reconstruct the same statement and
call zksk.base.Verifier.verify():
stmt.verify(nizk)
Secrets and Expressions¶
A zksk.expr.Secret objects represent the secret integer in a zero-knowledge proof. A secret has
a name and a value, but both can be empty. It can be constructed without any arguments:
x = Secret()
In this case, a name is assigned automatically.
To provide a value, construct a secret like this:
x = Secret(value=42)
If a secret contains a value, the proof will be able to use it, otherwise a prover will wait for a dictionary that maps secrets to values. The following two equivalent snippets illustrate this:
# If secret come with values, prover will get them.
x = Secret(value=4, name="x")
y = x.value * g
stmt = DLRep(y, x * g)
prover = stmt.get_prover()
# Otherwise, a prover needs to have the values as a dictionary.
x = Secret(name="x")
value = 4
stmt = DLRep(value * g, x * g)
prover = stmt.get_prover({x: value})
The names of secrets do not matter, they are only used for debugging purposes. All secrets can be left unnamed.
Multiplying secrets by elliptic curve points, as in x * G, produces expressions. Expressions can
also be added together. In general, an expression has the following form:
For example:
x = Secret()
y = Secret()
g = group.hash_to_point(b"one")
h = group.hash_to_point(b"two")
expr = x * g + y * h
expr here represents \(x G + y H\).
If secrets have their values set, you can also evaluate an expression using
zksk.expr.Expression.eval() method:
x = Secret(value=5)
expr = x * g
expr.eval()
This can simplify the redundant definition of a proof above:
stmt = DLRep(expr.eval(), expr)
Composing Proofs with AND¶
In this example, we show how to build an “and”-composition of two discrete-logarithm proofs:
As before, we initialize the points \(G_i\) and the secrets \(x_i\).
group = EcGroup()
# Create the base points on the curve.
g0 = group.generator()
g1 = group.hash_to_point(b"one")
g2 = group.hash_to_point(b"two")
g3 = group.hash_to_point(b"three")
# Preparing the secrets.
# In practice, they probably should be big integers (petlib.bn.Bn)
x0 = Secret()
x1 = Secret()
x2 = Secret()
Tip
If you need several group generators, as above, you can use the zksk.utils.groups.make_generators()
function.
Then, we can create the “and”-proof like this:
# First, compute the values, "left-hand side".
y1 = 4 * g0 + 5 * g1
y2 = 4 * g2 + 7 * g3
# Next, create the proof statement.
stmt = DLRep(y1, x0 * g0 + x1 * g1) \
& DLRep(y2, x0 * g2 + x2 * g3)
This syntax enables us to almost copy the mathematical expression of the proof in the Camenisch-Stadler notation.
We can also instantiate subproofs separately and pass them to the
zksk.composition.AndProofStmt. In fact, the above is just a simplified way of writing
the following:
stmt_1 = DLRep(y1, x0 * g0 + x1 * g1)
stmt_2 = DLRep(y2, x0 * g2 + x2 * g3)
equivalent_stmt = AndProofStmt(stmt_1, stmt_2)
The two ways to construct the AndProofStmt are equivalent and work with an arbitrary number of parameters.
Composing proofs takes into consideration the re-occuring secrets. The following are two not equivalent snippets:
x0 = Secret(4)
x1 = Secret(4)
stmt = DLRep(4 * g0, x0 * g0) & DLRep(4 * g1, x1 * g1)
# NOT the same as above. Note that x1_prime is used for both clauses.
x1_prime = Secret(4)
another_stmt = DLRep(4 * g0, x1_prime * g0) & DLRep(4 * g1, x1_prime * g1)
They are not equivalent as the second one will verify that the same
zksk.expr.Secret object is used.
Executing the protocol is the same as in the previous example.
Composing Proofs with OR¶
In this example, we show how to build an “or”-composition of two discrete-logarithm proofs:
Or-proofs are slightly more complicated than and-proofs.
A simple way to define this or-proof is as follows:
# First, compute the values, "left-hand side".
y0 = x0.value * g0
y1 = x1.value * g1
# Next, create the proof statement.
stmt = DLRep(y0, x0 * g0) | DLRep(y1, x1 * g1)
An or-proof works by simulating all subproofs but the one true subproof which will be actually proved. Before executing the protocol, you can explicitly define which subproofs will be simulated.
# Set the first clause as simulated.
stmt.subproofs[0].set_simulated()
This ensures that this subproof is not picked for the legitimate execution.
Note
When constructing an or-proof, orp = p1 | p2, the p1 and p2 are
copied. After the or-proof is constructed, modifying the original objects
does not change the composed proof.
Tip
You don’t need to provide all the secret values for the or-proof. The library will draw a random subproof to execute, but it will choose only among those for which you provided all secrets.
Equivalently, you can use zksk.composition.OrProofStmt:
# This is an equivalent way to define the proof statement above.
stmt_1 = DLRep(y0, x0 * g0)
stmt_2 = DLRep(y1, x1 * g1)
stmt_1.set_simulated()
equivalent_stmt = OrProofStmt(stmt_1, stmt_2)
The built-in primitives such as zksk.primitives.dlrep.DLRep accept a
simulated parameter. You can use it to mark which subproof to simulate at
its construction time:
# Another equivalent way.
stmt_1 = DLRep(y0, x0 * g0, simulated=True)
stmt_2 = DLRep(y1, x1 * g1)
equivalent_stmt = OrProofStmt(stmt_1, stmt_2)
Executing the protocol is the same as in the previous sections.
Composing AND and OR¶
You can have complex composition trees:
Definining this statement amounts to the following:
y0 = x0.value * g0
y1 = x1.value * g1
y2 = x2.value * g2
stmt = (DLRep(y0, x0 * g0) | DLRep(y1, x1 * g1)) & DLRep(y2, x2 * g2)
Some Special Cases are not Allowed¶
The library cannot prevent all cases of flawed proofs, but it will try its best to detect issues. For that, it needs to impose certain limitations on the expressivity of the proofs.
When reusing a secret \(x\) with two different group points \(G_0\), \(G_1\), the groups induced by \(G_0\) and \(G_1\) must have the same size.
No secret should appear at the same time in and out of an or-proof. This proof will fail to instantiate:
\[PK\{ (x_0, x_1): Y_0 = x_0 G_0 \land (Y_1 = x_1 G_1 \lor Y_2 = x_0 G_2 ) \}\]You must use the same order in expressions when proving and verifying. Proving non-interactively \(PK\{(x_0, x_1): Y = x_0 G_0 + x_1 G_1 \}\), but verifying \(PK\{(x_0, x_1): Y = x_1 G_1 + x_0 G_0 \}\) will fail as proofs generate and compare order-sensitive identifiers.
- CS97
J. Camenisch and M. Stadler, “Proof systems for general statements about discrete logarithms,” Tech. rep. 260, Mar. 1997