https://www.zkhack.dev/solution3.html Also at: https://hackmd.io/@-yB0zvcCSGu5i7kvgWEeRw/zkhack-3-double-trouble
Use cargo run --release to see it in action
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 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`?.
The inner-product proof is obtained by applying the Fiat--Shamir transform to the following sigma protocol:
Before proof:
During proof of inner product with public vector b:
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; ρ)
C_1 := PedersenCOMM(<a, b>; τ) // <x, y> denotes inner product of x and y.
C_2 := PedersenCOMM(<r, b>; υ)
---- 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
==================================================================================================