ZKHack - Puzzle 4 - Write-up

verify-hidden-in-plain-sight.rs

///
/// ================================== ZKHACK Puzzle 4 - Write-Up ==================================
///
/// Michael ADJEDJ aka ZeroFearSyndrom
///
/// => URL: https://www.zkhack.dev/puzzle4.html
/// => GitHub Repo: https://github.com/kobigurk/zkhack-hidden-in-plain-sight
///
/// 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-hidden-in-plain-sight.rs` file from the original repository by this one.
///
///
///
/// The puzzle description says
/// ------------------------------------------------------------------------------------------------
/// One-thousand accounts participate in a shielded pool which hides the recipients and other data
/// in each transaction between parties in the pool. The *recipient* is a 256-bit account address
/// which is hidden by blinding a KZG-like polynomial commitment to the address. The sender of the
/// transaction chooses two secret *blinding factors* known only to them by which the polynomial
/// commitment is blinded. Included with the commitment are two openings used to verify the
/// commitment. You intercept a transaction by observing the shielded pool. Armed with the blinded
/// commitment and two openings from the intercepted transaction as well as the public data (the
/// trusted setup for the KZG commitment scheme, a list of all one-thousand account addresses
/// participating in the pool, and the two random challenges used to compute the openings) can you
/// deanonymize the recipient address?
///
/// ## Blinding Scheme
/// The 256-bit recipient address is split into a vector of 32 bytes, and each byte (as a BLS12-381
/// scalar) becomes a coefficient of a degree-31 polynomial P. There is an evaluation domain
/// H = {1, ω, ω^2, ..., ω^(n-1)} with $ω^n = 1$ and a vanishing polynomial Z_H(x) = x^n -1 which
/// evaluates to 0 on each element of the evaluation domain. The sender of the transaction chooses
/// two secret blinding factors b_0 and b_1 and computes the blinded polynomial
/// Q(x) = P(x) + (b_0 + b_1x) • Z_H(x).
///
/// ## Polynomial Commitment
/// The KZG-like polynomial commitment scheme uses a public trusted setup
/// S={g, g•s, ..., g•s^(n+1)}$ where g is the generator point of the BLS12-381 elliptic curve and
/// s is a secret scalar. For the polynomial Q(x) = c_0 + c_1x+c_2x^2 + ... + c_(n+1)x^(n+1) the
/// commitment com(Q) = c_0•g + c_1•g•s + c_2•g•s^2 + ... + c_(n+1)•g•s^(n+1).
///
/// ## Openings
/// Openings of the polynomial are required in order to verify the polynomial commitment. These are
/// simple evaluations of the polynomial at random challenges which are public. For instance, for
/// challenges z_1 and z_2, the openings are Q(z_1) and Q(z_2).
/// ------------------------------------------------------------------------------------------------
///
/// The goal of this challenge is then to de-anonymize the recipient's address. Or equivalently,
/// retrieving the blinded polynomial, along with the two blinding factors.

use ark_bls12_381::{Fr, G1Affine};
use ark_ff::*;
use ark_poly::{
    univariate::DensePolynomial, EvaluationDomain, GeneralEvaluationDomain, Polynomial,
    UVPolynomial,
};
use ark_serialize::CanonicalDeserialize;
use hidden_in_plain_sight::{generate::kzg_commit, PUZZLE_DESCRIPTION};
use prompt::{puzzle, welcome};
use std::str::FromStr;
use std::ops::Mul;
use std::ops::Add;

// Implementation of the 2x2-matrix / 2-vector multiplication
fn mul_mat_vec(matrix: &[[Fr; 2]; 2], vector: &[Fr; 2]) -> [Fr; 2] {
    [
        matrix[0][0].mul(vector[0]).add(matrix[0][1].mul(vector[1])),
        matrix[1][0].mul(vector[0]).add(matrix[1][1].mul(vector[1])),
    ]
}


fn read_cha_from_file() -> (Vec<G1Affine>, Vec<Vec<Fr>>, Fr, Fr, G1Affine, Fr, Fr) {
    use std::fs::File;
    use std::io::prelude::*;

    let mut file = File::open("challenge_data").unwrap();
    let mut bytes: Vec<u8> = vec![];
    file.read_to_end(&mut bytes).unwrap();

    let setup_bytes: Vec<u8> = bytes[0..98312].to_vec();
    let accts_bytes: Vec<u8> = bytes[98312..1130320].to_vec();
    let cha_1_bytes: Vec<u8> = bytes[1130320..1130352].to_vec();
    let cha_2_bytes: Vec<u8> = bytes[1130352..1130384].to_vec();
    let commt_bytes: Vec<u8> = bytes[1130384..1130480].to_vec();
    let opn_1_bytes: Vec<u8> = bytes[1130480..1130512].to_vec();
    let opn_2_bytes: Vec<u8> = bytes[1130512..1130544].to_vec();

    let setup = Vec::<G1Affine>::deserialize_unchecked(&setup_bytes[..]).unwrap();
    let accts = Vec::<Vec<Fr>>::deserialize_unchecked(&accts_bytes[..]).unwrap();
    let cha_1 = Fr::deserialize_unchecked(&cha_1_bytes[..]).unwrap();
    let cha_2 = Fr::deserialize_unchecked(&cha_2_bytes[..]).unwrap();
    let commt = G1Affine::deserialize_unchecked(&commt_bytes[..]).unwrap();
    let opn_1 = Fr::deserialize_unchecked(&opn_1_bytes[..]).unwrap();
    let opn_2 = Fr::deserialize_unchecked(&opn_2_bytes[..]).unwrap();

    (setup, accts, cha_1, cha_2, commt, opn_1, opn_2)
}

/// ```
/// From the puzzle description, we know that the definition of the blinded polynomial is:
/// Q(x) = P(x) + (b_0 + b_1x) • Z_H(x)
/// where
/// ```
///   - `P(x)` is the polynomial encoding the recipient's address,
///   - `b_0` and `b_1` are random coefficients.
///   - `H(x)` is the vanishing polynomial,
///
/// evaluation of `Q(x)` at these two values.
/// Two challenges `z_1` and `z_2` are picked up at random, and the openings are simply the
/// From this, we have
///  Q(z_1) = P(z_1) + (b_0 + b_1z_1) • Z_H(z_1)
/// ```
///  Q(z_2) = P(z_2) + (b_0 + b_1z_2) • Z_H(z_2)
/// At this stage, we know:
/// ```
///   - the values `Q(z_1)` and `Q(z_2)` since they were intercepted.
///     `P(z_1)` and `P(z_2)` for each possible recipient.
///   - all the polynomials `P` since they are given in the public data. Thus, we can compute
///   - the vanishing polynomial `Z_H` since it comes with the public data as well. Again,
///     computing `Z_H(z_1)` and `Z_H(z_1)` is easy
///
/// The only unknowns in the previous system of equations are `b_0` and `b_1`, and this system
/// is easily rewritten as:
/// ```
///  (Q(z_1) - P(z_1)) / Z_H(z_1) = b_0 + b_1z_1
///  (Q(z_2) - P(z_2)) / Z_H(z_2) = b_0 + b_1z_2
/// ```
/// which is a linear system of 2 equations, with 2 unknowns.
/// To solve it, we have to invert the following 2x2 matrix:
/// ```
///  ( 1   z_1 )
///  ( 1   z_2 )
/// ```
/// I precomputed it as the `invM` matrix.
///
/// Once we get this matrix, we need to compute back for each possible recipient the associated
/// polynomial `Q(X)`, and check whether the commitment of this polynomial equals the intercepted
/// one. In this case, this means we correctly retrieved the target blinded account polynomial.
/// Retrieving (i.e. de-anonymizing) the recipient is then easily done.
fn solve(setup: &Vec<G1Affine>, accts: &Vec<Vec<Fr>>, cha_1: &Fr, cha_2: &Fr, commt: &G1Affine, opn_1: &Fr, opn_2: &Fr) -> DensePolynomial<Fr> {
    let invM =
        [
            [Fr::from_str("22951854599759835910992311772168417415264555850924163441646824277609327787373").unwrap(), Fr::from_str("29484020575366354568455428736017548422425996649603474380956834422329253397141").unwrap()],
            [Fr::from_str("40354641401611018555778208291758157338022977399176114215242170068986924921628").unwrap(), Fr::from_str("12081233773515171923669532216427808499667575101351523607361488630951656262885").unwrap()]
        ];

    let number_of_accts = 1000usize;

    for (idx, acct) in accts.iter().enumerate() {
        // For each possible recipient, we will compute the values `(Q(z_1) - P(z_1)) / Z_H(z_1)`
        // and `(Q(z_2) - P(z_2)) / Z_H(z_2)`, which I called `normalized_diff`.
        //
        let domain: GeneralEvaluationDomain<Fr> =
            GeneralEvaluationDomain::new(number_of_accts + 2).unwrap();

        //  This will give me the polynomial `P` I will then evaluate at the both values `z_1` and
        // `z_2`
        let target_acct_poly = DensePolynomial::from_coefficients_vec(domain.ifft(acct));
        let normalized_diff: [Fr; 2] =
            [
                (opn_1.clone() - target_acct_poly.evaluate(&cha_1)).mul(domain.evaluate_vanishing_polynomial(cha_1.clone()).inverse().unwrap()),
                (opn_2.clone() - target_acct_poly.evaluate(&cha_2)).mul(domain.evaluate_vanishing_polynomial(cha_2.clone()).inverse().unwrap())
            ];

        // To retrieve the values `b_0` and `b_1`, we just need to multiply the `normalized_diff`
        // vector by the inverse of the matrix previously computed.
        // The result is then converted into the equivalent polynomial `b_0 + b_1x`.
        let b0_b1 = mul_mat_vec(&invM, &normalized_diff).to_vec();
        let blinding_poly =
            DensePolynomial::from_coefficients_vec(b0_b1);

        // We then compute the blinded polynomial as `Q(x) = P(x) + (b_0 + b_1x) • Z_H(x)` ...
        let blinded_acct_poly = target_acct_poly + blinding_poly.mul_by_vanishing_poly(domain);

        // ... and compute the commitment for it.
        let commitment: G1Affine = kzg_commit(&blinded_acct_poly, &setup);

        // If the computed commitment is the same as the one in the intercepted transaction,
        // then we win! And we can exit the loop, and return the polynomial...
        if commitment.to_string() == commt.to_string() {
            // In this case, if required, the recipient address can be computed back from `acct`
            // The recipient's address is either:
            // ```
            //    - DA87BE72D77766E5B65AA9F3CE0C5664A49246734EDDC150AA0D0871ADBC05C1
            //    - C105BCAD71080DAA50C1DD4E734692A464560CCEF3A95AB6E56677D772BE87DA
            // ```
            // depending whether it's taken BigEndian or LittleEndian to derive the polynomial.
            println!("The deanonymized recipient is the recipient id {} ", idx);
            print!("  It's associated address is: ");
            acct.iter().for_each(|val| print!("{}", &val.to_string()[70..72]));
            print!(" (BE) / ");
            acct.iter().rev().for_each(|val| print!("{}", &val.to_string()[70..72]));
            println!(" (LE)");
            return blinded_acct_poly;
        }
    }
    unreachable!();
}

fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

    let (setup, accts, cha_1, cha_2, commt, opn_1, opn_2) = read_cha_from_file();

    let solution_blinded_acct = solve(&setup, &accts, &cha_1, &cha_2, &commt, &opn_1, &opn_2);
    let solution_commitment = kzg_commit(&solution_blinded_acct, &setup);
    assert_eq!(solution_commitment, commt);
}