ZKHack - Puzzle 5 - Write-up

verify-strong-adaptivity.rs

#![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);
}