signature and group signatures

Reference: GroupSignMerkle circom give the whole procedure of Group Signature with Merkle proof.

signature

Normal signature

  1. KeyGen → (sk, pk): selects a random secret key sk and corresponding public key pk
  2. Sign(m, sk) → s: given a message m and secret key, outputs a signature s
  3. Verify(m, s, pk) → 1/0: given a message m, a signature s, and a public key pk, verifies if signature is valid

Normal signature circom

group signature

Group signature for group G

  1. KeyGen → (ski, pki): selects a random set of secret keys ski and corresponding public keys pki for each member of group
  2. GroupSign(m, ski, G) → : given a message m and secret key, outputs a signature s
  3. GroupVerify(m, s, G) → 1/0: given a message m, a signature s, and the group G, verifies if the signature came from the group

GroupSign circom

With reference to Group Signatures with zkSNARKs

Merkle tree

Merkle tree is a way to sort of accumulating a bunch of different elements set into one commitment. Note that the hash result will be different if the two input elements swap the order.

With the following references:

  1. Merkle Tree Inclusion proof semaphore/tree.circom at main · semaphore-protocol/semaphore · GitHub give the code about Merkle Tree Inclusion proof.
  2. circomlib/poseidon.circom at master · iden3/circomlib · GitHub and circomlib/comparators.circom at cff5ab6288b55ef23602221694a6a38a0239dcc0 · iden3/circomlib give the usage of poseidon hash and comparators/IsEqual.
  3. tornado-core/merkleTree.circom at master · tornadocash/tornado-core · GitHub give the circom of the verification of the Merkle Tree proof
  4. Modern ZK Crypto - Session 4 Lecture Notes - HackMD