links:
A log of my thoughts while solving ZK Hack IV puzzle 1.
initial pass notes and unpacking ConstraintSynthesizer are quite messy, but remain here for posterity. Skip to header [[#in review]] for the "knowledge clean-up" phase of the log
Based on Zcash private transaction design and Mina chain compression. Alice is able to double spend.
Guess: something in the recursion system over MNT7653exposes the key used for spending, or allows her otherwise to forge a new spending key.
We will generate a faulty nullifier and secret, that satisfy the same tree proof for the merkle tree leaf at index 2.
They define a Merkle Tree with some properties. Odds are, there isn't a bug in the merkle tree or hash implementation, but ya never know.
vaguely hinted as suspicious secret and nullifier:
type ConstraintF = MNT4BigFr;
struct SpendCircuit {
pub leaf_params: <LeafH as CRHScheme>::Parameters,
pub two_to_one_params: <LeafH as CRHScheme>::Parameters,
pub root: <CompressH as TwoToOneCRHScheme>::Output,
pub proof: Path<MntMerkleTreeParams>,
pub secret: ConstraintF,
pub nullifier: ConstraintF,
}
let tree = MntMerkleTree::new(
&leaf_crh_params,
&leaf_crh_params, // repeat?
leaves.iter().map(|x| x.as_slice()),
)
ConstraintSynthesizer
, i.e. we can pass it to grothcheck that the parameters are correct, though too few rounds, or incorrect params seem unlikely to be the source of the vuln; still, they specified a configuration of Poseidon, so not impossible a vuln lives here
From https://zips.z.cash/protocol/protocol.pdf#poseidonhash, also see daira's pasta-hadeshash
calc_round_numbers.py
a couple differences, minor sus, check more later, look at daira's param gen script and check poseidon docs for more; also see arkworks src
We found that we need to generate a faulty null/secret pair for leaf at index 2 in the merkle tree pair. These are not used to generate the merkle inclusion proof, so it seems unlikely that there is a bug in the hash function implementation. It seems more likely that then, that our bug lies in our Constraint system.
We should try to understand how the nullifer and secret are spent, which should give hints about how to forge new ones.
We also don't much remember how nullifiers are used, so hit a recap if the constraint review fails to turn much up.
everything here looks pretty boilerplate. That leaves to look at MNT and Poseidon, and investigating what precisely is proved.
recall that the nullifier is the hash defined over the private_spending_key
, the shielded address, and the notes (UTXO model) that the user would spend.
If we can construct a fake nullifier, then we must be able to find a hash pre-image. There must be something the issue with using MNT for the curve, i.e. maybe too small field or something.
Or else, maybe there is some convenient structure in MNT / Poseidon that we can exploit (the pairing).
Let's find exactly how the nullifier is created and used.
let ie$ullifier = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![leaked_secret]).unwrap();
// where
type LeafH = poseidon::CRH<ConstraintF>; // implements the hash
type ConstraintF = MNT4BigFr;
// where in ark crypto primitives:
/// Interface to CRH. Note that in this release, while all implementations of `CRH` have fixed length,
/// variable length CRH may also implement this trait in future.
pub trait CRHScheme {
type Input: ?Sized;
type Output: Clone + Eq + Debug + Hash + Default
type Parameters: Clone;
fn setup<R: Rng>(r: &mut R) -> Result<Self::Parameters, Error>;
fn evaluate<T: Borrow<Self::Input>>( parameters: &Self::Parameters, input: T, ) -> Result<Self::Output, Error>;
}
// and:
fn evaluate(
parameters: &Self::ParametersVar,
input: &Self::InputVar,
) -> Result<Self::OutputVar, SynthesisError> {
let cs = input.cs();
if cs.is_none() {
let mut constant_input = Vec::new();
for var in input.iter() {
constant_input.push(var.value()?);
}
Ok(FpVar::Constant(
CRH::<F>::evaluate(¶meters.parameters, constant_input).unwrap(),
))
} else {
let mut sponge = PoseidonSpongeVar::new(cs, ¶meters.parameters);
sponge.absorb(&input)?;
let res = sponge.squeeze_field_elements(1)?;
Ok(res[0].clone())
}
}
// restated from top:
let nullifier_in_circuit =
<LeafHG as CRHSchemeGadget<LeafH, _>>::evaluate(&leaf_crh_params_var, &[secret])?;
if no input cs:
do we have a cs?
base: mnt6 G1var
The nullifier is consumed by the SpendCircuit
. We have:
fn prove<C: ConstraintSynthesizer<E::ScalarField>, R: RngCore>(
pk: &Self::ProvingKey,
circuit: C,
rng: &mut R,
) -> Result<Self::Proof, Self::Error> {
Self::create_random_proof_with_reduction(circuit, pk, rng)
}
/// Create a Groth16 proof that is zero-knowledge using the provided
/// R1CS-to-QAP reduction.
/// This method samples randomness for zero knowledges via `rng`.
#[inline]
pub fn create_random_proof_with_reduction<C>(
circuit: C,
pk: &ProvingKey<E>,
rng: &mut impl Rng,
) -> R1CSResult<Proof<E>>
where
C: ConstraintSynthesizer<E::ScalarField>,
{
// the zk parts, zero if no zk;
let r = E::ScalarField::rand(rng);
let s = E::ScalarField::rand(rng);
Self::create_proof_with_reduction(circuit, pk, r, s)
}
/// Create a Groth16 proof using randomness `r` and `s` and the provided
/// R1CS-to-QAP reduction.
#[inline]
pub fn create_proof_with_reduction<C>(
circuit: C,
pk: &ProvingKey<E>,
r: E::ScalarField,
s: E::ScalarField,
) -> R1CSResult<Proof<E>>
where
E: Pairing,
C: ConstraintSynthesizer<E::ScalarField>,
QAP: R1CSToQAP,
{
let cs = ConstraintSystem::new_ref();
// Set the optimization goal
cs.set_optimization_goal(OptimizationGoal::Constraints);
// Synthesize the circuit.
circuit.generate_constraints(cs.clone())?;
debug_assert!(cs.is_satisfied().unwrap());
cs.finalize();
let h = QAP::witness_map::<E::ScalarField, D<E::ScalarField>>(cs.clone())?;
let prover = cs.borrow().unwrap();
let proof = Self::create_proof_with_assignment(
pk,
r,
s,
&h,
&prover.instance_assignment[1..],
&prover.witness_assignment,
)?;
Ok(proof)
}
We know a few things:
LEAFH::evaluate(&leaf_crh_params, [leaked_secret])
, where leaf params are just the poseidon config, and leaked secret is the secret key.N == LeafHG::evaluate(¶ms, &[my_secret])?;
leaf_g = (g1_generator * my_secret).x
h(params, cheat_secret) == h(params, secret)
root
/ \
h(h0,h1) h(h2,h3)
| | | |
h0 h1 h2 h3 (this row: leaves.bin)
| | | |
l0 l1 l2 l3
^(leaked_secret.bin)
Issue: how are we going to construct a hash collision?
hint 1 updated: see zcash spec lemma 5.4.7 for bob's reasoning on why to only use the x coordinate when storing public keys.
Lemma 5.4.7. Let
Given leaked secret
Is it possible that
It's not immediately obvious how we will peel off
Maybe if solving the discrete log problem in
Still, we've made some progress. The state of the problem is now:
Lemma 5.4.7. Let
Hint 2 released:
Note that the MNT curves are represented in Weierstrass from in the circuit, and use the fact that both (x,y) and (x,-y) are valid points for spending
Which confirms my suspicion that we want
We observe that for the order
However, note that mnt4::Fr
field, but the order mnt4::Fp
, so we'll have to do a type conversion.