We are given a proof of equality protocol and our task to construct distinct messages a1 and a2 which satisfy the verifier checks. The protocol looks sounds on first glance, but puzzle intro advises us to brush up on the Fiat-Shamir transform, and digging in to the implementation of the challenge construction we find the following red flag: https://github.com/kobigurk/zkhack-strong-adaptivity/blob/a6a2b4794b8396e61a92b768a4e59b2512d67eaf/src/msg_equality_arg.rs#L44
The challenge is a function of the commit key, c_rho and c_tau, but it is independent of the choices made in the offline phase of the protocol where the prover is supposed to initially construct a, C_1 and C_2. This suggests that we can construct a2 adaptively based on the challenge we receive.
For simplicity we'll just set all the terms which interact with the hiding generator to zero, i.e. we choose r1=r2=rho=tau=0. Then we can restate the task as follows.
- Choose r. Compute c_rho = PC(r, 0).
- Choose fake_r. Compute c_tau = PC( fake_r, 0).
- Compute challenge.
- Choose a1. Using this compute s=r+challenge*a1.
- Construct a2 as a function of a1 and challenge.
- Send s, u(=0), t(=0), C_1 and C_2.
The challenge lies in step 5 where we must figure out how to set a2 so that the verifier checks hold.
Note that the first verifier check PC(s; u) = C_rho + challenge*C_1 is independent of a2 and holds automatically. To satisfy the second check we need the following equation to hold
r * message_generator + a1 * challenge * message_generator = fake_r * message_generator + a2 * challenge * message_generator
or equivalently
(r + challenge * a1) = (fake_r + challenge * a2)
or equivalently
a2 = ( r + challenge * a1 - fake_r)/challenge
As long as we choose r!=fake_r then a2!=a1 and our task is complete!