🐥 【解题】ZKHACK V Puzzle#1: Zeitgeist

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

    /* This is how the serialized proofs, nullifiers and commitments were created. */
    // serialize();

    /* Implement your attack here, to find the index of the encrypted message */

    let secret = Fr::from(0u64);
    let secret_commitment = poseidon_base::primitives::Hash::<
        _,
        P128Pow5T3Compact<Fr>,
        ConstantLength<2>,
        WIDTH,
        RATE,
    >::init()
    .hash([secret, Fr::from(0u64)]);
    for i in 0..64 {
        let (_, _, commitment) = from_serialized(i);
        assert_eq!(secret_commitment, commitment);
    }
    /* End of attack */
}

pub fn serialize() {
   for i in 0..64 {
       let (proof, nullifier, commitment) = shplonk();

       let filename = format!("./proofs/proof_{}.bin", i);
       let mut file = File::create(&filename).unwrap();
       file.write_all(&proof).unwrap();

       let filename = format!("./nullifiers/nullifier_{}.bin", i);
       let mut file = File::create(&filename).unwrap();
       file.write_all(&nullifier.to_repr()).unwrap();

       let filename = format!("./commitments/commitment_{}.bin", i);
       let mut file = File::create(&filename).unwrap();
       file.write_all(&commitment.to_repr()).unwrap();
   }
}

pub fn shplonk() -> (Vec<u8>, Fr, Fr) {
   use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
   use halo2_proofs::poly::kzg::multiopen::{ProverSHPLONK, VerifierSHPLONK};
   use halo2_proofs::poly::kzg::strategy::AccumulatorStrategy;
   use halo2curves::bn256::Bn256;
   use rand_chacha::ChaCha20Rng;
   use rand_core::SeedableRng;

   let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
   let params = ParamsKZG::<Bn256>::setup(K, setup_rng);
   let rng = OsRng;

   let pk = keygen::<KZGCommitmentScheme<_>>(&params);

   let (proof, nullifier, commitment) =
       create_proof::<_, ProverSHPLONK<_>, _, _, Blake2bWrite<_, _, Challenge255<_>>>(
           rng, &params, &pk,
       );

   let verifier_params = params.verifier_params();

   verify_proof::<
       _,
       VerifierSHPLONK<_>,
       _,
       Blake2bRead<_, _, Challenge255<_>>,
       AccumulatorStrategy<_>,
   >(
       verifier_params,
       pk.get_vk(),
       &proof[..],
       nullifier,
       commitment,
   );

   (proof, nullifier, commitment)
}

#[derive(Default, Clone)]

struct MyCircuit {
	witness: Value<Fr>,
	nonce: Value<Fr>,
}

const WIDTH: usize = 3;
const RATE: usize = 2;

#[derive(Clone, Debug)]

struct MyCircuitConfig {
	input_config: InputConfig,
	hash_config: Pow5Config<Fr, WIDTH, RATE>,
	commitment_hash_config: Pow5Config<Fr, WIDTH, RATE>,
}

impl Circuit<Fr> for MyCircuit {

	type Config = MyCircuitConfig;
	type FloorPlanner = SimpleFloorPlanner;

	fn without_witnesses(&self) -> Self {

		Self::default()
	}

	fn configure(meta: &mut ConstraintSystem<Fr>) -> Self::Config {

		// LOAD CONFIG
		let witness = meta.advice_column();
		let instance = meta.instance_column();
		let constant = meta.fixed_column();
		
		let input_config = InputChip::configure(meta, witness, instance, constant);
		let witness_state = (0..WIDTH).map(|_| meta.advice_column()).collect::<Vec<_>>();
		let witness_partial_sbox = meta.advice_column();
		let witness_rc_a = (0..WIDTH).map(|_| meta.fixed_column()).collect::<Vec<_>>();
		let witness_rc_b = (0..WIDTH).map(|_| meta.fixed_column()).collect::<Vec<_>>();
		
		meta.enable_constant(witness_rc_b[0]);
	
		let witness_hash_config = Pow5Chip::configure::<P128Pow5T3<Fr>>(
			meta,
			witness_state.try_into().unwrap(),
			witness_partial_sbox,
			witness_rc_a.try_into().unwrap(),
			witness_rc_b.try_into().unwrap(),
		);

		// POSEIDON CONFIG
		let state = (0..WIDTH).map(|_| meta.advice_column()).collect::<Vec<_>>();
		let partial_sbox = meta.advice_column();
		let rc_a = (0..WIDTH).map(|_| meta.fixed_column()).collect::<Vec<_>>();
		let rc_b = (0..WIDTH).map(|_| meta.fixed_column()).collect::<Vec<_>>();
		meta.enable_constant(rc_b[0]);
		
		let hash_config = Pow5Chip::configure::<P128Pow5T3<Fr>>(
			meta,
			state.try_into().unwrap(),
			partial_sbox,
			rc_a.try_into().unwrap(),
			rc_b.try_into().unwrap(),
		);
		
		return Self::Config {
			input_config,
			hash_config,
			commitment_hash_config: witness_hash_config,
		};
	}

	fn synthesize(
		&self,
		config: Self::Config,
		mut layouter: impl Layouter<Fr>,
	) -> Result<(), Error> {
	
		let input_chip = InputChip::<_>::construct(config.input_config);
		let x = input_chip.load_witness(layouter.namespace(|| "load secret"), self.witness)?;
		let nonce = input_chip.load_nonce(layouter.namespace(|| "load nonce"), self.nonce)?;
		let c = input_chip.load_constant(layouter.namespace(|| "load const"), Fr::from(0u64))?;
		let commitment_hash_chip = Pow5Chip::construct(config.commitment_hash_config.clone());
		let commitment_hasher = Hash::<_, _, P128Pow5T3<Fr>, ConstantLength<2>, WIDTH, RATE>::init(
			commitment_hash_chip,
			layouter.namespace(|| "init witness"),
		)?;
		
		let commitment_digest =
		commitment_hasher.hash(layouter.namespace(|| "commitment"), [x.0.clone(), c.0])?;
		input_chip.expose_public(
			layouter.namespace(|| "expose commitment"),
			Number(commitment_digest),
			1,
		)?;


		// START HASHING
		let poseidon_chip = Pow5Chip::construct(config.hash_config.clone());
		let hasher = Hash::<_, _, P128Pow5T3<Fr>, ConstantLength<2>, WIDTH, RATE>::init(
		poseidon_chip,
		layouter.namespace(|| "init"),
		)?;
		let nullifier = hasher.hash(layouter.namespace(|| "hash"), [x.0, nonce.0])?;
		input_chip.expose_public(
			layouter.namespace(|| "expose nullifier"),
			Number(nullifier),
			0,
		)?;
		Ok(())
	}
}

pub fn main() {

	welcome();
	puzzle(PUZZLE_DESCRIPTION);

	/* This is how the serialized proofs, nullifiers and commitments were created. */
	// serialize();
	
	/* Implement your attack here, to find the index of the encrypted message */
	use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
	use halo2curves::bn256::Bn256;
	use halo2_proofs::transcript::{Transcript, TranscriptRead};
	use halo2_proofs::arithmetic::lagrange_interpolate;
	use halo2curves::bn256::G1Affine;
	use halo2_proofs::arithmetic::eval_polynomial;
	
	// Generate pk/vk
	let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
	let params = ParamsKZG::<Bn256>::setup(K, setup_rng);
	let pk = keygen::<KZGCommitmentScheme<_>>(&params);
	let vk = pk.get_vk();
	
	let mut points = Vec::new();
	let mut evals = Vec::new();
	
	// Read the l(x) from proof for the second column for advice
	for i in 0..64 {

		let (proof, nullifier, commitment) = from_serialized(i);
		let mut transcript: Blake2bRead<&[u8], G1Affine, Challenge255<G1Affine>> = Blake2bRead::<&[u8], G1Affine, Challenge255<G1Affine>>::init(&proof);
		vk.hash_into(&mut transcript).unwrap();
		transcript.common_scalar(nullifier).unwrap();
		transcript.common_scalar(commitment).unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.squeeze_challenge_scalar::<()>();
		transcript.squeeze_challenge_scalar::<()>();
		transcript.squeeze_challenge_scalar::<()>();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.squeeze_challenge_scalar::<()>();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();
		transcript.read_point().unwrap();

		// Read the challenge x from transcript
		let x = transcript.squeeze_challenge().get_scalar();
		transcript.read_scalar().unwrap();
		
		// Read second column's eval l(x) from proof
		let eval = transcript.read_scalar().unwrap();
		points.push(x);
		evals.push(eval);
	}

	// Add one more point/eval pair
	// The order is 64, so we need 65 pairs
	// In this colum, l(\omega^0) = 0
	points.push(Fr::one());
	evals.push(Fr::zero());
	  
	// Evaluate the polynomial by lagrange interpolation
	let poly = lagrange_interpolate(&points, &evals);
	let omega = vk.get_domain().get_omega();
	
	// In this colum, l(\omega^2) = l(\omega^3) = l(\omega^4) = secret
	let secret = eval_polynomial(&poly, omega.pow([2]));
	let secret_commitment = poseidon_base::primitives::Hash::<
		_,
		P128Pow5T3Compact<Fr>,
		ConstantLength<2>,
		WIDTH,
		RATE,
>		::init()
	.hash([secret, Fr::from(0u64)]);
	
	for i in 0..64 {
		let (_, _, commitment) = from_serialized(i);
		assert_eq!(secret_commitment, commitment);
	}

/* End of attack */

}