# Modern ZK Crypto - Session 4 Lecture Notes Materials covered in today's lecture: * Group signature motivation and circuits from https://0xparc.org/blog/zk-group-sigs * Merkle trees in circom from https://github.com/semaphore-protocol/semaphore/blob/main/packages/circuits/tree.circom * More notes in https://decentralizedthoughts.github.io/2020-12-22-what-is-a-merkle-tree/ * snarkjs circuit compilation process * Steps convered in https://github.com/iden3/snarkjs * Diagram and resources in https://zkiap.com/snarkjs * With additional time * Nullifiers in https://semaphore.appliedzkp.org/docs/guides/identities * Deny/reveal from https://0xparc.org/blog/zk-group-sigs * QuinSelector / IsZero from https://hackmd.io/@gubsheep/S1Hz96Yqo ## Simple zkSNARK signature scheme A digital signature corresponds of the following functions: * $KeyGen → (sk, pk)$: selects a random secret key $sk$ and corresponding public key $pk$ * $Sign(m, sk) → s$: given a message $m$ and secret key $sk$, outputs a signature $s$ * $Verify(m, s, pk) → 1/0$: given a message $m$, a signature $s$, and a public key $pk$, verifies if signature is valid We can build a simple digital signature with just a hash function and zkSNARKs! ### KeyGen ``` include "circomlib/poseidon.circom"; template SecretToPublic() { signal input sk; signal output pk; component poseidon = Poseidon(1); poseidon.inputs[0] <== sk; pk <== poseidon.out; } ``` For sk = 5, pk = 19065150524771031435284970883882288895168425523179566388456001105768498065277. ### Sign ``` template Sign() { signal input m; signal input sk; signal input pk; // verify prover knows correct sk component checker = SecretToPublic(); checker.sk <== sk; pk === checker.pk; } component main { public [ pk, m ] } = Sign(); ``` The proof **itself** becomes your signature! You may notice the message is never constrained; this does not break soundness! You can see more details at https://geometry.xyz/notebook/groth16-malleability ### Verify You need to verify the proof along with the public inputs of pk and m to verify this zkSNARK signature. ## Simple Group Signature Let's say there are $n$ members in a group $G$. Then we define a group signature scheme as: * $KeyGen → (sk_i, pk_i)$: selects a random set of secret keys $sk_i$ and corresponding public keys $pk_i$ for each member of group * $GroupSign(m, sk_i, G)$ → : given a message $m$ and secret key, outputs a group signature $s$ * $GroupVerify(m, s, G) → 1/0$: given a message $m$, a group signature $s$, and the group $G$, verifies if the signature came from the group ### KeyGen We have the same KeyGen as before, except we generate $n$ of these pairs for each of the members of the group. ### GroupSign ``` template GroupSign(n) { signal input sk; signal input pk[n]; // even though m is not involved in the circuit, // it is still constrained and cannot be // changed after it is set. signal input m; // get the public key component computePk = SecretToPublic(); computePk.sk <== sk; // make sure computedPk is in the inputted group signal zeroChecker[n+1]; zeroChecker[0] <== 1; for (var i = 0; i < n; i++) { zeroChecker[i+1] <== zeroChecker[i] * (pk[i] - computePk.pk); } zeroChecker[n] === 0; } ``` ### Verify Just as before, the proof itself is our signature! We can verify it by inputting the message and public keys of the group. An example that will verify with `GroupSig(5)` and secret key 5 is: ``` { "pk": ["19065150524771031435284970883882288895168425523179566388456001105768498065277", "1", "2", "3", "4"], "m": "1" } ``` ## Larger groups with Merkle Trees The previous solution required inputting all of the public keys as inputs, which can get unweildy with larger groups. Instead we use a Merkle Tree, which only requires inputting log(n) elements to prove membership: ``` include "circomlib/poseidon.circom"; // if s == 0 returns [in[0], in[1]] // if s == 1 returns [in[1], in[0]] template DualMux() { signal input in[2]; signal input s; signal output out[2]; s * (1 - s) === 0; out[0] <== (in[1] - in[0])*s + in[0]; out[1] <== (in[0] - in[1])*s + in[1]; } template MerkleTreeInclusionProof(nLevels) { signal input leaf; signal input pathIndices[nLevels]; signal input siblings[nLevels]; signal input root; component mux[nLevels]; component poseidons[nLevels]; signal hashes[nLevels+1]; hashes[0] <== leaf; for (var i = 0; i < nLevels; i++) { mux[i] = DualMux(); mux[i].in[0] <== hashes[i]; mux[i].in[1] <== siblings[i]; mux[i].s <== pathIndices[i]; poseidons[i] = Poseidon(2); poseidons[i].inputs[0] <== mux[i].out[0]; poseidons[i].inputs[1] <== mux[i].out[1]; hashes[i+1] <== poseidons[i].out; } root === hashes[nLevels]; } component main { public [ leaf, root ] } = MerkleTreeInclusionProof(15); ``` To test, here is a valid input: ``` /* INPUT = { "root": "12890874683796057475982638126021753466203617277177808903147539631297044918772", "leaf": "1355224352695827483975080807178260403365748530407", "siblings": [ "1", "217234377348884654691879377518794323857294947151490278790710809376325639809", "18624361856574916496058203820366795950790078780687078257641649903530959943449", "19831903348221211061287449275113949495274937755341117892716020320428427983768", "5101361658164783800162950277964947086522384365207151283079909745362546177817", "11552819453851113656956689238827707323483753486799384854128595967739676085386", "10483540708739576660440356112223782712680507694971046950485797346645134034053", "7389929564247907165221817742923803467566552273918071630442219344496852141897", "6373467404037422198696850591961270197948259393735756505350173302460761391561", "14340012938942512497418634250250812329499499250184704496617019030530171289909", "10566235887680695760439252521824446945750533956882759130656396012316506290852", "14058207238811178801861080665931986752520779251556785412233046706263822020051", "1841804857146338876502603211473795482567574429038948082406470282797710112230", "6068974671277751946941356330314625335924522973707504316217201913831393258319", "10344803844228993379415834281058662700959138333457605334309913075063427817480" ], "pathIndices": [ "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1" ] } */ ```