zkSNARKs and Programmable Group Signatures

to cover:

  • motivation
  • why is building a zk app now possible? snarkjs, circom. some considerations around what is involved in building a zk app
  • what are the guarantees that zk provides / contrast when you don't have a ZK system (you have to trust the server)
  • background on "existing work" - group and ring signatures - contrast cryptographers writing specific protocols vs. zk devs who have access to a programmable "cryptographic computer"
  • quick intro to how zk works / what zk is (maybe some light version of https://blog.zkga.me/intro-to-zksnarks)
  • the protocol / the circuits themselves
  • relationship to blockchains: most zk apps we've written have been on-chain apps; this is not on-chain, but benefits from blockchain as a credibly neutral ledger of identity components (asset ownership, dao membership, etc.) that can be integrated into this offchain system
  • protocol extensions: deniability, ability to reveal the individual signer post facto, accumulator vs. hardcoded max # of signatories
  • speculate on possible use cases / "product" visions that build on these primitives - senators signaling consensus ahead of a vote, AskReddit screencaps where someone tells a story and says "i work at X, and [blah blah blah]" being actually credible, briefly touch on considerations around abuse and negative externalities (i post a Bad Thing saying it's one of {me, someone i don't like}) and some possible design decisions that could help mitigate

sections:

  • [brian] introduction: motivation - credibility vs. anonymity and the limitations of existing protocols (trust server to throw away identity, etc.)
  • [brian] background: introduce two concepts. (1) "existing work" - group and ring signatures. (2) introduce zkSNARKs (one- or two-liner) and link out to further reading for people who want to go deeper. contrast cryptographers writing specific protocols vs. zk devs who have access to a programmable "cryptographic computer"
  • [kevin] "protocol"/circuits: lay out the circuits in pseudocode and explain them, link out to repo. identify the guarantees and properties of a simple application architecture that uses these circuits (i.e. not censorship resistent if using a server, but no one can fake signatures, no one can know who posted a thing besides the poster)
  • [uma] protocol augmentations: you can make deniability possible or not. you can make post facto reveal possible or not. you can use accumulators to have arbitrarily large identity sets, which starts looking less like "i am one of N" and more like "i have property X". note the connection to blockchain here - while blockchain isn't necessary for this, its a natural fit for a very useful augmentation (benefits from blockchain as a credibly neutral ledger of identity components (asset ownership, dao membership, etc.) that can be integrated into this offchain system)
  • [raymond] speculate on possible use cases / "product" visions that build on these primitives - senators signaling consensus ahead of a vote, AskReddit screencaps where someone tells a story and says "i work at X, and [blah blah blah]" being actually credible, briefly touch on considerations around abuse and negative externalities (i post a Bad Thing saying it's one of {me, someone i don't like}) and some possible design decisions that could help mitigate

In most cases, credibility and anonymity seem directly at odds. On the one hand, anonymity allows "anons" and "throwaway accounts" on platforms like 4chan and Reddit to speak their minds in ways that they might not otherwise be comfortable with, and enables whistleblowers to publicly disclose corporate or government wrongdoing while mitigating the risk of real-world reprecussions. On the other hand, it is difficult to verify the credibility of statements that are not attached to known or trusted identities, and anonymity can help bad actors who wish to spread misinformation or harrass other community members.

In this post, we present a few techniques for implementing efficient and practical "group signatures." In combination with blockchain identity systems, which

Background

A Simple Protocol

Note that slightly modified versions of this protocol can be used such that revealSigner and/or denySignature operations are not possible without revealing your secret. For example, to disable denySignature, add a salt. To disable revealSignee, don't publish a message attestation.

First, via a known identity provider (ie tweets or Ethereum signatures), participants commit to secrets by publishing hashes of their respective secrets.

Circuits

groupSign

Inputs:
 - hash1 (pub)
 - hash2 (pub)
 - hash3 (pub)
 - msg (pub)
 - secret

Intermediate values:
 - x (supposed to be hash of secret)
 
Output:
 - msgAttestation
 
Prove:
 - mimc(secret) == x
 - (x - hash1)(x - hash2)(x - hash3) == 0
 - msgAttestation == mimc(msg, secret)

revealSigner

Inputs:
 - hash (pub)
 - msgAttestation (pub)
 - msg (pub)
 - secret
 
Outputs:
 - msgAttestation
 
Prove:
 - msgAttestation == mimc(msg, secret)
 - hash = mimc(secret)

denySignature

Inputs:
 - hash (pub)
 - msg (pub)
 - secret

Outputs:
 - msgAttestation 

Prove
 - msgAttestation != mimc(msg, secret)
 - hash = mimc(secret)
Select a repo