Another great week has passed in the zkhack event and I'm thrilled to share with you another writeup for another challenge that I (Matan Hamilis) have solved with Elichai Turkel and Shalevos.
We have written also solutions to the first problem and the second problem, go ahead and check them out too someday :)
This puzzle called "Double Trouble" gives us some introductory material about ZK-proofs and Schnorr's Knowledge-of-Descrete-Logarithm Zero-Knowledge-Proof-of-Knowledge protocol. If all this means nothing to you we will get to it right away, if you already know about it, feel free to skip forward.
If you're taking part in the awesome zkhack event you've probably already heard about Zero Knowledge proofs, at least by name.
Just to get things straight the setting is as follows: We have two entities - a Prover (denoted by
Many proofs in life, and especially in mathematics, can be done by supplying an example. For example (did you get the recusrion?), we can prove that a number is composite (not prime) by supplying a divisor of that number. Such "examples" are usually referred to as "witnesses". So let's say you have a number that we want to prove it to be composite. But you don't want to provide to the verifier your witness. Actually you want to verifier to gain zero knowledge about the number besides it is composite.
This is where Zero-Knowledge proofs come to the rescue. If we devise a certain protocol such that we will be able to convince the verifier that a composite number really is composite without disclosing our witness, this will be a Zero-Knowledge-Proof (or ZKP in short). It is also important that the verifier will likely reject false proofs.
Let's assume there is a proof-system in which we, as verifiers, are convinced that a certain number is indeed composite, how can we show that this proof-system is ZKP? Well, if we could "simulate" a similar proof between a prover and a verifier that looks exactly the same as a regular proof and without knowing the actual secret, this would mean that zero information is leaked in the process of proving right? Otherwise, we could gain this information by simply simulating the proof! So, a proof-protocol is ZKP if we can create a simulator that can create identical transcripts of proofs just like a real proof taking place.
You may have heard some "heavy" terms like "statistical indistinguishability" and such, but all they mean is simply to give a proper and precise mathemtical definition to what "identical transcripts" really mean.
The fact that someone has just given us a proof that some number is indeed composite, doesn't mean that he really knows such a divisor for that number, right? While it makes sense to us that this is "the only" way to prove that some number is composite, we still can't really know that the prover knows the divisor. In some cases, we don't only want to be satisfied that some property holds but that the prover actually knows such a witness. These proofs are knows as proofs of knowledge (PoK).
We can't argue anything about what exactly the prover holds in its memory, so what exactly does "knowledge" even mean? In cryptography it is common to think of knowing something as "being able to efficiently extract the value of it".
While we can't claim that a prover really holds a divisor of some number in its memory, we can prove that using the information it provides us it can efficiently extract such a divisor!
Formally speaking, to prove that a proof is a PoK of some value
For example, an extractor for the knowledge of a divisor of a composite number will be able to run and rewind the procedure of the proof to gain enough transcripts of a proof and using those transcripts to extract the value of a divisor. This shows us that the prover itself could have extracted this value (since everything the extractor sees is generated by the prover) and therefore we can tell that the prover knows it (or is able to know it without too much effort).
As said, many proof systems are interactive. Therefore, the prover and the verifier have multiple rounds of communication in which the verifier asks questions / sends challenges and the prover responds accordingly. To make the proof system non-interactive so that the proof can be generated offline and verified later (even publicly for example, on a blockchain) we need to find a way to generate the challenges of the verifier in a reliable way. This can be done using the Fiat-Shamir assumption which basically states that instead of the verifier randomly sending challenges, the prover can generate a challenge by himself.
But how is this fair? If the prover chooses the challenges he can create false proofs! That's correct, that's why we don't want the prover to be able to control the challenges easily. The challenge will be the output of some cryptographically secure hash function given as input the whole transcript of the proof. Since those function are considered to be random (under the assumption known as the "random oracle assumption") we can assume that those challenges the prover gets from the hash function are really "random" and couldn't have been specially crafted to trick the verifier.
One last thing we should mention are Pedersen Commitments which are being used a lot in the challenge. Let's see what those mean.
A commitment scheme in general gives the functionality of committing to a specific value while exposing the committed value later. A commitment scheme has two main "functions":
-
$\text{Commit}(x,s)$ : Creates a commitment to the value$x$ with some (possibly empty) supplementary data$s$ . -
$\text{Verify}(c,v,s)$ : Verify that the commitment$c$ commits correctly to the value$v$ with some supplementary data$s$ .
The most simple commitment scheme which relies on the hardness of discrete-log-assumption uses some group
-
$\text{Commit}(x,s)$ : Return$x\cdot G$ -
$\text{Verify}(c,v,s)$ : Check$c \stackrel{?}{=} v\cdot G$ .
Noticed in this simplistic commitment scheme we haven't used the supplementary data.
This scheme is perfectly binding, meaning that it binds the committer to the value of
The pedersen commitment, however, is perfercly hiding so that it hides the committed value based on information-theoretic arguments without relying on any hardness assumption (such as discrete log), but is only computationally binding so that given enough computation resources someone else could claim that a commitment to value of
The way Pedersen commitments work is by holding two generators
-
$\text{Commit}(x,s)$ : Return$x\cdot G + s\cdot H$ . -
$\text{Verify}(c,v,s)$ : Check if$c \stackrel{?}{=} v \cdot G + s \cdot H$ .
This commitment scheme is perfectly hiding because for each commitment value
However, it is only computationally binding since it is possible, with enough resources to find the discrete log of
In this puzzle we are using a special variant of pedersen commitment used to commit on vectors instead of just scalars. In which we can commit to vectors of some size
Great, now that we have enough introductory material, let's try and solve the puzzle!
The puzzle goes as follows:
Bob has developed a new zero-knowledge inner-product proof allows proving that
the inner product of a hidden, committed vector `a` with a public vector `b`
equals the claimed value `v` that is committed. He's released the protocol
license-free below, but still wants to profit from his invention. So, he
developed a proprietary prover that he claims is 2x faster than the standard one
described below, but without sacrificing zero-knowledge: it still hides all
information about the committed vector `a`. To back up his claim, he has
published a few proofs generated by this proprietary prover for the same `a` but
with respect to possibly different `b` vectors, and has challenged people to recover `a`
from just these proofs.
Can you rise to the challenge and recover the vector `a`?.
In the puzzle we are given an (allegedly) ZKP protocol to prove that the inner product of some unknown vector
The proof system of Bob is made non-interactive by using the Fiat-Shamir assumption we discussed earlier. The original proof system works as follows:
Prover Verifier
=================================================================================================
Offline phase (before `b` is available):
1. Prover computes
C_a := PedersenCOMM(a; α)
= sum_i (a_i * G_i) + α * H
where G_i and H are random group elements,
and s is sampled randomly.
--------- C_a ---------->
Online phase for a given public vector `b` (can be repeated for different `b`s):
1. Prover samples a random vector r
and random elements ρ, τ, υ.
2. Prover computes
C_r := PedersenCOMM(r; ρ)
:= sum(r_i*G_i) + ρ*H
C_1 := PedersenCOMM(<a, b>; τ) // <x, y> denotes inner product of x and y.
:= <a,b>*G_1 + τ*H
C_2 := PedersenCOMM(<r, b>; υ)
:= <r,b>*G_1 + υ*H
---- C_r, C_1, C_2 ----->
<- random challenge γ ---
3. Prover computes
s := a + γr,
u := α + γρ
t := τ + γυ,
-------- s, u, t ------->
// Check that `s` really is a + γr,
Check PedersenCOMM(s; u) = C_a + γC_r
// Check that the inner product is committed in C_1.
Check PedersenCOMM(<s, b>; t) = C_1 + γC_2
==================================================================================================
We are also given two proofs each contains the whole transcript of the proofs (i.e.
We are also given the commit_key which is the set of generators ChaChaRng which is considered secure and thus nothing "fishy" determined the value of the generators so there really is no disrete log known between them.
One can also verify that cargo run command line utility.
The proofs we are given are therefore known to be verified successfully.
Therefore, the only things we can learn about them is that for
Recall that
Notice that since we are using another prover we can't tell that:
-
$s_i = a_i + \gamma_i r_i$ . $u_i = \alpha + \gamma_i \rho_i$ $t_i = \tau_i + \gamma_i \nu_i$
An important observation we make is that both
let (commit_key, [(instance_1, proof_1), (instance_2, proof_2)]) = puzzle_data();
let b_1 = instance_1.b;
let b_2 = instance_2.b;
let a_comm_1 = instance_1.comm_a;
let a_comm_2 = instance_2.comm_a;
assert_eq!(a_comm_1, a_comm_2);
assert_eq!(b_1, b_2);
Therefore we will denote
Eventually we want to find
Now let's get totally rid of all this
$$\begin{align}
\langle s_1, G \rangle + u_1H &= \langle a, G \rangle + \alpha H + \gamma_1 \cdot {C_r}_1 \
\langle s_2, G \rangle + u_2H &= \langle a, G \rangle + \alpha H + \gamma_2 \cdot {C_r}_2 \
\end{align}$$
Remember - because the discrete log of
- Represent each
$C_r$ by breaking a discrete log. - Know some discrete log between the
$Cr$ values.
Since the first option is not reasonable, the prover isn't almighty! We decided to try break the discrete log between
We weren't sure what multiple of
We have run the following code:
let (commit_key, [(instance_1, proof_1), (instance_2, proof_2)]) = puzzle_data();
let gamma_1 = challenge(&commit_key, &instance_1, &proof_1.commitment);
let gamma_2 = challenge(&commit_key, &instance_2, &proof_2.commitment);
let cr_1 = proof_1.commitment.comm_r;
let cr_2 = proof_2.commitment.comm_r;
let elements = vec![
cr_1,
cr_2,
cr_1.mul(gamma_1).into_affine(),
cr_2.mul(gamma_1).into_affine(),
cr_1.mul(gamma_2).into_affine(),
cr_2.mul(gamma_2).into_affine(),
];
let mut elements_copy = Vec::clone(&elements);
let mut i = 2;
loop {
elements_copy
.iter_mut()
.zip(elements.iter())
.for_each(|(copy, orig)| *copy += *orig);
elements_copy
.iter()
.enumerate()
.for_each(|(copy_idx, copy)| {
elements.iter().enumerate().for_each(|(orig_idx, orig)| {
if copy == orig {
println!("elements[{}] * {} = elements[{}]", copy_idx, i, orig_idx);
}
})
});
i += 1;
}
And got the output:
elements[0] * 2 = elements[1]
elements[2] * 2 = elements[3]
elements[4] * 2 = elements[5]
This is awesome! We have:
So if we just modify the equations a little bit we have:
Let's write
Now we multiply the first equation by
Now if we subtract the second equation from the first we can cancel
$2\gamma_2(u_1-\alpha) = \gamma_1 (u_2 - \alpha)$ $2\gamma_1 (s_1 -a) = \gamma_1 (s_2 -a)$
By solving each equation we get:
We have computed their values in:
let u_1 = proof_1.response.u;
let u_2 = proof_2.response.u;
let s_1 = proof_1.response.s;
let s_2 = proof_2.response.s;
let two = Fr::from(2);
let alpha = (two * gamma_2 * u_1 - gamma_1 * u_2) / (two * gamma_2 - gamma_1);
let a: Vec<Fr> = s_1
.iter()
.zip(s_2.iter())
.map(|(s1_e, s2_e)| (two * gamma_2 * s1_e - gamma_1 * s2_e) / (two * gamma_2 - gamma_1))
.collect();
Now we have verified by integrate all of our code into the main function provided and we see that our solution acutally works!
use ark_ed_on_bls12_381::Fr;
use ark_ff::Field;
use double_trouble::data::puzzle_data;
use double_trouble::inner_product_argument::utils::challenge;
use double_trouble::verify;
use double_trouble::PUZZLE_DESCRIPTION;
use prompt::{puzzle, welcome};
use std::ops::{AddAssign, Mul};
use ark_ec::{
twisted_edwards_extended::{GroupAffine, GroupProjective},
AffineCurve, ProjectiveCurve,
};
use ark_ed_on_bls12_381::{EdwardsParameters, FrParameters};
use ark_ff::Zero;
use ark_serialize::CanonicalSerialize;
use double_trouble::{utils::dot_product, CommitKey};
fn main() {
welcome();
puzzle(PUZZLE_DESCRIPTION);
let (ck, [instance_and_proof_1, instance_and_proof_2]) = puzzle_data();
let (instance1, proof1) = instance_and_proof_1;
let (instance2, proof2) = instance_and_proof_2;
assert!(verify(&ck, &instance1, &proof1));
assert!(verify(&ck, &instance2, &proof2));
let (commit_key, [(instance_1, proof_1), (instance_2, proof_2)]) = puzzle_data();
let b_1 = Vec::clone(&instance_1.b);
let b_2 = Vec::clone(&instance_2.b);
let a_comm_1 = instance_1.comm_a;
let a_comm_2 = instance_2.comm_a;
assert_eq!(a_comm_1, a_comm_2);
assert_eq!(b_1, b_2);
let gamma_1 = challenge(&commit_key, &instance_1, &proof_1.commitment);
let gamma_2 = challenge(&commit_key, &instance_2, &proof_2.commitment);
let cr_1 = proof_1.commitment.comm_r;
let cr_2 = proof_2.commitment.comm_r;
let elements = vec![
cr_1,
cr_2,
cr_1.mul(gamma_1).into_affine(),
cr_2.mul(gamma_1).into_affine(),
cr_1.mul(gamma_2).into_affine(),
cr_2.mul(gamma_2).into_affine(),
];
let mut elements_copy = Vec::clone(&elements);
let mut i = 2;
let u_1 = proof_1.response.u;
let u_2 = proof_2.response.u;
let s_1 = proof_1.response.s;
let s_2 = proof_2.response.s;
let two = Fr::from(2);
let alpha = (two * gamma_2 * u_1 - gamma_1 * u_2) / (two * gamma_2 - gamma_1);
let a: Vec<Fr> = s_1
.iter()
.zip(s_2.iter())
.map(|(s1_e, s2_e)| (two * gamma_2 * s1_e - gamma_1 * s2_e) / (two * gamma_2 - gamma_1))
.collect();
let (a, comm_a_rand): (Vec<Fr>, Fr) = { (a, alpha) };
assert_eq!(
ck.commit_with_explicit_randomness(&a, comm_a_rand),
instance1.comm_a
);
assert_eq!(
ck.commit_with_explicit_randomness(&a, comm_a_rand),
instance2.comm_a
);
}