Zero Knowledge Proof — one possible malleability of Groth16
zkHack published a new Puzzle. Even though the Puzzle used an older zkp algorithm — Groth16 , it’s very interesting and very helpful to understand the concepts such as Zero-Knowledge Proof, polynomials, linear correlation, etc.
What’s the Puzzle?
The corresponding circuit of Puzzle is constructed in circom, and implemented in zkhack-groth-puzzle/circuits/circuit.circom.
pragma circom 2.0.6;
include "../node_modules/circomlib/circuits/poseidon.circom";
template Circuit() {
signal input a;
signal input b;
signal input c;
a === b;
component p = Poseidon(1);
p.inputs[0] <== c;
p.out === 17744324452969507964952966931655538206777558023197549666337974697819074895989;
}The circuit is fairly simple, its input has three inputs: a/b/c, in which a is a public input. There are two constraints: 1/ a is equal to b 2/ The poseidon hash result of c is a specific value. The circom circuit is compiled into R1CS constraints, and then snarkjs is used to construct the proofs. There’s a specific comment that the snarkjs source code used in Puzzle has some modification:
diff --git a/build/main.cjs b/build/main.cjs
index 00e6965..ef1bd6f 100644
--- a/build/main.cjs
+++ b/build/main.cjs
@@ -4328,7 +4328,8 @@ async function newZKey(r1csName, ptauName, zkeyName, logger) {
}
}
- for (let s = 0; s <= nPublic ; s++) {
+// for (let s = 0; s <= nPublic ; s++) {
+ for (let s = 0; s < 1 ; s++) {
const l1t = TAU_G1;
const l1 = sG1*(r1cs.nConstraints + s);
const l2t = BETATAU_G1;The seemingly minor edit to the proving system leads to the malleability of the final proof.
The question of Puzzle is given in zkhack-groth-puzzle/src/solution.js:
const { proof, publicSignals } = JSON.parse(`{"proof":{"pi_a":["7076778705842675636541778654824835671264842003792815899892788518756808417824","4871300562969249383482829591051792322271432570205055011710223197671646924652","1"],"pi_b": [["4702507968743578934061693422759564470881256571473408115314331474240229998811","16198326042603795115438219508756675682917780977814561672804657276368883889354"],["12916734195569167956837700546311420400354235424337271822709448553494046311159", "20167467333119574021428597666293210644874141810710695584907560968298314755986"],["1","0"]],"pi_c":["20014664648588403789442308373435642542109961553284949305762265534102084844319", "10562544426189233680286850591386198483452124187323754995599976212942563914034","1"],"protocol":"groth16","curve":"bn128"},"publicSignals":["1"]}`);
const isValid = await verifyProof(vKey, { proof, publicSignals });
console.assert(isValid === true, "Proof is not valid");
const new_a = BigInt("PUT_YOUR_ADDRESS_HERE");
publicSignals[0] = new_a;
/*
PUT YOUR SOLUTION HERE
Change the proof such that isValidMalleable = true and passes assertion
*/
const isValidMalleable = await verifyProof(vKey, { proof, publicSignals });
console.assert(isValidMalleable === true, "Malleable is not valid");Given a proof, how to make sure that the proof is verified even after the public input is changed? The Puzzles that accept changed public input are typically interesting, let’s see how to solve this Puzzle.
R1CS Circuit Constraints
Take a look at the circuit structure of Puzzle:
To check whether the value of variable a and b are equal, the circuit utilizes this structure: 0*1 = b-a. And, the other parts of the circuit are Poseidon Hash, which are not related to variable a/b, indicating that:
When the prove and verify process of Groth16 algorithm is combined with the information above:
In this Puzzle, l is 1 (one of them is constant ONE, the other one is variable a). Let’s reorganize the verify formula:
C is decomposed to the formula below:
Take a close look at these two items:
Because u1(x)/v1(x) and u2(x)/v2(x) are both 0, they can be further simplified to:
Combine with the information above:
We can get that w1(x) and w2(x) have linear correlation. Therefore, there’s linear correlation between the following two expressions:
After understanding the challenge, the information of the points of these two expressions are provided publicly. The information of the corresponding point can be found in zkhack-groth-puzzle/build/snark/circuit/circuit_final.zkey of Puzzle, assuming the information of the point is C_2.
How to solve the Puzzle?
After figuring out the logic and the linear correlation, then it’s easy to solve the question. If the public input variable a increases, c also adapts accordingly.
You can check the code of the smart contract to ensure the value of variable _a that is required by the verification(zkhack-groth-puzzle/contracts/Puzzle.sol):
uint256 _a = uint256(uint160(address(msg.sender)));
require(
verifyProof(
[_proof[0], _proof[1]],
[[_proof[2], _proof[3]], [_proof[4], _proof[5]]],
[_proof[6], _proof[7]],
[_a]
),
"Puzzle: Invalid proof"
);Public variable a becomes the last 160 bits data of transaction sending address.
How to prevent linear correlation?
After we have finished solving the question, it’s necessary to consider how to prevent the linear correlation among the data of constraints in the proving system. Recall that Puzzle itself is the minimal edits to the snarkjs. By taking a close look at these edits, you can then tell how to prevent linear correlation:
Except the constraints of “user” defined logic, expand the constraint system for the public inputs: 1*0 = 0. This edit not only ensures that the constraint polynomials of the public input variables have no linear correlation, but also ensures that the constraint polynomials of the public input variable and private input variable have no linear correlation. Some people might notice that for the constraint polynomials of private input variables, they are not required to have non-linear correlation.
In fact, similar questions were found in the libsnark source code back in 2015. If you are interested, feel free to check it out.
Summary:
The new Puzzle of zkHack is very interesting, it is related to the linear correlation of the constraints. In this specific case, it is also related to the polynomial of input variables and private variables. Under this situation, a new proof can be changed directly modifying the accepted one.
