Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
ZKHack - Puzzle 5 - Write-up
#![allow(unused, unreachable_code)]
///
/// ================================== ZKHACK Puzzle 5 - Write-Up ==================================
///
/// Michael ADJEDJ aka ZeroFearSyndrom
/// aka Michael-Qedit
///
/// => URL: https://www.zkhack.dev/puzzle5.html
/// => GitHub Repo: https://github.com/kobigurk/zkhack-strong-adaptivity
///
/// This write-up is written as a Rust file. The comment explains how to solve it, while the code
/// actually solves it. If you want to launch this solution by yourself, just replace the
/// `verify-strong-adaptivity.rs` file from the original repository by this one.
///
/// The puzzle description says
/// ------------------------------------------------------------------------------------------------
/// Shallan recently found a proof system (see below) that enables proving that two
/// Pedersen commitments commit to the same message (but with potentially different
/// randomness). She employes this in her private cryptocurrency to show that two
/// committed coins have the same value. However, soon after deployment, she
/// receives a message from a self-proclaimed hacker. The message contains two
/// Pedersen commitments and their openings, and a proof of message equality for
/// these commitments. The proof is valid, but there's a twist: the openings contain
/// different messages! How can this be? Reproduce the attack and help Shallan
/// diagnose the problem in her system.
///
///
/// The Proof of message equality is obtained by applying the Fiat--Shamir transform to the
/// following sigma protocol:
///
/// Prover Verifier
/// ================================================================================================
/// Offline phase:
/// 1. Prover computes
/// C_1 := PedersenCOMM(a; r1) = a * G + r1 * H
/// C_2 := PedersenCOMM(a; r2) = a * G + r2 * H
///
/// where G and H are generators of the group, and r1 and r2 are random field elements.
/// ------- C_1, C_2 ------->
///
/// Online phase:
///
/// 1. Prover samples random elements r, ρ, τ.
/// 2. Prover computes
/// C_ρ := PedersenCOMM(r; ρ)
/// C_τ := PedersenCOMM(r; τ)
/// ------- C_ρ, C_τ ------->
/// <- random challenge e ---
/// 3. Prover computes
/// s := r + e * a,
/// u := ρ + e * r1
/// t := τ + e * r2
/// -------- s, u, t ------->
/// Check PedersenCOMM(s; u) = C_ρ + eC_1
/// Check PedersenCOMM(s; t) = C_τ + eC_2
/// ------------------------------------------------------------------------------------------------
///
/// The goal of this challenge is 2-fold:
/// - Reproduce the attack, i.e. craft a valid proof, but for two different messages
/// - Help Shallan to diagnose, and potentially fix the problem in her system.
///
/// ------------------------------------------------------------------------------------------------
use ark_ed_on_bls12_381::Fr;
use ark_ff::{Field, UniformRand};
use strong_adaptivity::{Instance, Proof, data::puzzle_data, ProofResponse, ProofCommitment};
use strong_adaptivity::verify;
use strong_adaptivity::PUZZLE_DESCRIPTION;
use prompt::{puzzle, welcome};
use rand::rngs::ThreadRng;
use strong_adaptivity::utils::b2s_hash_to_field;
/// # SOLVING THIS PUZZLE
///
/// ## PRELIMINARIES
/// In the rest of this write-up, we will use the following (maybe abusive) notations/terminology:
/// - The points (`G`, `H`) will be called a base, in the geometric algebra sense
/// - Let π be the function such that: if `A = [α]G + [β]H`, then
/// `π(A) = α`
/// (One could have called it "the norm of the projection on `G`", but nvm)
///
///
/// From the above protocol, one could say that the following equivalences hold:
/// Provided that the proof is verified,
/// π(C_1) == π(C_2) <=> π(C_ρ) == π(C_τ) (I have a proof, but it's too large to fit in the margin)
///
/// We can use this equivalence to state that:
/// π(C_1) != π(C_2) => π(C_ρ) != π(C_τ)
///
/// From this statement, let's rewrite some of the equations as:
/// C_1 := PedersenCOMM(a1; r1)
/// C_2 := PedersenCOMM(a2; r1)
/// C_ρ := PedersenCOMM(r_ρ; ρ)
/// C_τ := PedersenCOMM(r_τ; τ)
///
/// From the proof verification equations: we can write:
/// PedersenCOMM(s; u) = C_ρ + eC_1
/// PedersenCOMM(s; t) = C_τ + eC_2
/// which means
/// [s]G + u[H] = [r_ρ]G + [ρ]H + [e*a1]G + [e*r1]H
/// [s]G + t[H] = [r_τ]G + [τ]H + [e*a2]G + [e*r2]H
///
/// Applying the projection π on both sides of the equations, we get:
/// s = r_ρ + e*a1
/// s = r_τ + e*a2
/// which leads to:
/// r_ρ + e*a1 = r_τ + e*a2
/// or, equivalently
/// a2 = (r_ρ - r_τ)/e + a1 (*)
///
/// ## IMPORTANT NOTE:
/// - In the previous equation, 'e' is the random challenge sent by the verifier.
/// In the Fiat-Shamir heuristic, it can be replaced by the output of a hash function
/// acting as a random oracle, the input being the instance + commitment previously sent.
/// - In this implementation, the computation of the challenge is done as
/// ```
/// let challenge = b2s_hash_to_field(&(*ck, commitment));
/// ```
/// 'ck' being the commitKey (i.e. the points `G` and `H`), and `commitment` being `C_ρ` and `C_τ`
/// In other words, *it does not depend on the instances `C_1` and `C_2`*.
///
/// Going back to (*) using the previous note leads to:
/// a2 = (r_ρ - r_τ) / h(C_ρ,C_τ) + a1
///
/// In other words, fixing C_ρ, C_τ and a1 will impose the value of a2
/// (r1 and r2 can be chosen arbitrarily)
///
/// ## PUTTING EVERYTHING TOGETHER TO SOLVE IT
///
/// To craft a valid proof, one need to
/// 1) first fix the values of (a1, r1), r2, (r_ρ, ρ), (r_τ, τ)
/// They could either be 0, and a random value. In the implementation below, we picked them
/// randomly.
/// 2) compute the points C_1, C_ρ, C_τ along with the challenge e = h(G, H, C_ρ, C_τ)
/// 3) compute a2 using the equation (*), along with the commitment C_2
/// 4) compute the values
/// s := r_ρ + e * a1 (= r_τ + e * a2)
/// u := ρ + e * r1
/// t := τ + e * r2
/// 5) Craft the `Instance` structure using C_1, C_2 and the Proof structure using
/// C_ρ, C_τ, s, u, t
///
/// You can follow each of the previous steps in the implementation below.
///
/// Run it, and admire how it goes smoothly...
/// Cheers!
///
/// # HELPING SHALLAN TO FIX HER PROTOCOL
///
/// One possible way of fixing this would be:
/// - Modify the computation of the challenge to depend on the both instances as well
/// e = h(G, H, C_1, C_2, C_ρ, C_τ)
/// This way, the self-proclaimed hacker will not be able to craft C_2 after having chosen
/// C_ρ, C_τ anymore.
/// ------------------------------------------------------------------------------------------------
fn main() {
welcome();
puzzle(PUZZLE_DESCRIPTION);
let ck = puzzle_data();
let mut rng = ThreadRng::default();
// 1) first fix the values of (a1, r1), r2, (r_ρ, ρ), (r_τ, τ)
let a_1 = Fr::rand(&mut rng);
let r_1 = Fr::rand(&mut rng);
let r_2 = Fr::rand(&mut rng);
let r_rho = Fr::rand(&mut rng);
let rho = Fr::rand(&mut rng);
let r_tau = Fr::rand(&mut rng);
let tau = Fr::rand(&mut rng);
// 2) compute the points C_1, C_ρ, C_τ along with the challenge e = h(G, H, C_ρ, C_τ)
let comm_1 = ck.commit_with_explicit_randomness(a_1, r_1);
let comm_rho = ck.commit_with_explicit_randomness(r_rho, rho);
let comm_tau = ck.commit_with_explicit_randomness(r_tau, tau);
let commitment = ProofCommitment {
comm_rho,
comm_tau,
};
let challenge = b2s_hash_to_field(&(ck, commitment));
// 3) compute a2 using the equation (*), along with the commitment C_2
let a_2 = (r_rho - r_tau) / challenge + a_1;
let comm_2 = ck.commit_with_explicit_randomness(a_2, r_2);
// 4) compute the values
// s := r_ρ + e * a1 (= r_τ + e * a2)
// u := ρ + e * r1
// t := τ + e * r2
let s = r_rho + challenge * a_1;
let u = rho + challenge * r_1;
let t = tau + challenge * r_2;
// 5) Craft the `Instance` structure using C_1, C_2 and the Proof structure using
// C_ρ, C_τ, s, u, t
let (instance, witness, proof): (Instance, (Fr, Fr, Fr, Fr), Proof) = {
(
Instance {
comm_1,
comm_2
},
(a_1, r_1, a_2, r_2),
Proof {
commitment,
response: ProofResponse {
s,
u,
t
}
}
)
};
let (a_1, r_1, a_2, r_2) = witness;
// Run it, and admire how it goes smoothly...
// Cheers!
assert!(verify(&ck, &instance, &proof));
// Check that commitments are correct
assert_eq!(ck.commit_with_explicit_randomness(a_1, r_1), instance.comm_1);
assert_eq!(ck.commit_with_explicit_randomness(a_2, r_2), instance.comm_2);
// Check that messages are unequal
assert_ne!(a_1, a_2);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment