# 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"
    ]
} */