### 零知识证明 - 从Puzzle理解线性相关

zkHack发布了新的Puzzle。虽然Puzzle用的比较老的Groth16算法，Puzzle的内容非常有趣，对理解零知识证明，多项式，线性相关等等知识非常有帮助。

zkHack发布了新的Puzzle。虽然Puzzle用的比较老的Groth16算法，Puzzle的内容非常有趣，对理解零知识证明，多项式，线性相关等等知识非常有帮助。

https://github.com/geometryresearch/zkhack-groth-puzzle

## Puzzle基本信息

Puzzle对应的电路采用circom搭建，实现在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] &lt;== c;
p.out === 17744324452969507964952966931655538206777558023197549666337974697819074895989;
}``````

``````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 &lt;= nPublic ; s++) {
+//         for (let s = 0; s &lt;= nPublic ; s++) {
+       for (let s = 0; s &lt; 1 ; s++) {
const l1t = TAU_G1;
const l1 = sG1*(r1cs.nConstraints + s);
const l2t = BETATAU_G1;``````

zkhack-groth-puzzle/src/solution.js 给出了Puzzle的要求：

``````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");

publicSignals[0] = new_a;

/*

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");``````

## 如何解题？

``````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"
);``````

## 如何防止线性关系？

https://leastauthority.com/blog/a-bug-in-libsnark/

zkHack新的Puzzle非常有趣，和数据的线性关系有关。在构造的场景下，输入变量的多项式和隐私变量的多项式线性相关。在这样的情况下，可以通过修改已有的证明直接构造其他证明。

• 发表于 2022-08-16 15:19
• 阅读 ( 480 )
• 学分 ( 1 )
• 分类：零知识证明

Star Li

82 篇文章, 6593 学分