Solution to ZKHack puzzle 4

verify-hidden-in-plain-sight.rs

#![allow(unused, unreachable_code, dead_code)]

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;


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)
}

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

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

    let invM =
        [
            [Fr::from_str("22951854599759835910992311772168417415264555850924163441646824277609327787373").unwrap(), Fr::from_str("29484020575366354568455428736017548422425996649603474380956834422329253397141").unwrap()],
            [Fr::from_str("40354641401611018555778208291758157338022977399176114215242170068986924921628").unwrap(), Fr::from_str("12081233773515171923669532216427808499667575101351523607361488630951656262885").unwrap()]
        ];

    // Replace with the solution polynomial, derived from the account!
    let mut solution_blinded_acct = DensePolynomial::from_coefficients_vec(vec![]);

    let number_of_accts = 1000usize;

    for acct in accts.iter() {
        let domain: GeneralEvaluationDomain<Fr> =
            GeneralEvaluationDomain::new(number_of_accts + 2).unwrap();

        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())
            ];

        let blinding_poly =
            DensePolynomial::from_coefficients_vec(mul_mat_vec(&invM, &normalized_diff).to_vec());
        let blinded_acct_poly = target_acct_poly + blinding_poly.mul_by_vanishing_poly(domain);

        let commitment: G1Affine = kzg_commit(&blinded_acct_poly, &setup);

        if commitment.to_string() == commt.to_string() {
            solution_blinded_acct = blinded_acct_poly;
            break;
        }
    }

    let solution_commitment = kzg_commit(&solution_blinded_acct, &setup);
    assert_eq!(solution_commitment, commt);
}