Double Blind project outline

# 0xPARC Sansome Summer Kickoff Project In your first week at 0xPARC, you'll build an end-to-end app with programmable cryptography. Specifically, you will be writing a *group signature* protocol using zkSNARKs, and integrating that into an web application--for example, an anonymous 0xPARC message board or voting app. A group signature scheme allows let you sign a message on behalf of a group. In other words, your signature will prove that you are a member of the group, without revealing which member you are. Specifically, you will use a programming language called [circom](https://github.com/iden3/circom) to write a zero-knowledge circuit to prove the following statement: - I have a (private) signature `sig`, a (private) signature-verification key `key`, and a public message (or message hash) `msg` and list of keys `key1, ..., keyN`, such that: - The "signature verification" algorithm, run on inputs `sig`, `key`, and `msg`, returns `pass` - The hidden key `key` is one of the list of keys `key1, ..., keyN`. Your system should accept signatures using RSA keys, compatible with the protocol used by Github and `ssh-keygen`. You will: - Use circom to build a zero-knowledge proof, as described above, that will function as a group signature. - Build a web frontend on top of your circuit. This involves compiling your circom circuit, and using a Javascript library called snarkjs to generate and verify ZKPs in browser. The frontend should: - Accept `sig`, `key`, `msg` and the list of keys `key1, ..., keyN` -- or even better: have an interface to upload `sig` and `msg`, and find `key` and `key1, ..., keyN` from Github, and - Generate a group signature. ## About SSH keys and signatures (Almost) every Github account has attached one or more public keys that can be used to verify the account owners' digital signatures; the keys can be accessed at `github.com/USERNAME.keys`. If you are a Github user and you have an SSH key attached to your account, you can sign any message on your local computer using the command `ssh-keygen`. A standard invocation is `ssh-keygen -Y sign -n "namespace" -f ~/.ssh/id_ed25519 msg`. Here: `-Y sign` tells `ssh-keygen` to produce a signature using your private key (rather than its default behavior, which is to create a key) `-n "namespace"` creates a "namespace" for your signature -- the namespace is a security feature to prevent a malicious attacker from reusing a signature for a purpose for which it was not intended `-f ~/.ssh/id_ed25519` tells `ssh-keygen` where to find your private key. You can see your private keys by typing `ls ~/.ssh`: by default, your SSH agent will store private and public cryptographic keys here. By default, your private key will be called `~/.ssh/id_ed25519` or `~/.ssh/id_rsa`, depending which algorithm you used; your public key will be called `~/.ssh/id_ed25519.pub` or `~/.ssh/id_rsa.pub`. ### Parsing keys and signatures One of the challenges you'll encounter in this project is figuring out how to handle RSA keys and signatures in a way that is compatible with the behavior of `ssh-keygen`. In other words, you'll need to figure out how `ssh-keygen` *really* works. To do this you'll need to search for specifications or examples of other code in the wild that generates and verifies SSH RSA signatures. **This is one of the hardest parts of the project!** You'll probably need to Google around, read open-source code, or talk to LLMs to figure this out. To give you some guidance, at a high level, an RSA signature verifier: - hashes the provided message - appends it to the namespace + hash algorithm name, and then - hashes again. - Finally, there is an additional round of padding, with bytes `1f ff ff ...` as needed, and a header with details about the hash algorithm. ## Circuit libraries and other code A big part of this project is implement ZK circuits that prove validity of an SSH RSA signature. Some code exists online for this, mostly written by other people who have undertaken this project. We ask that you implement your ZK circuits from scratch, apart from access to basic functions found in: - [circomlib](https://github.com/iden3/circomlib), a library of some basic utility functions. - [circom-bigint](https://github.com/0xPARC/circom-bigint/blob/main/bigint.circom), a libray of some basic "bigint" operations for non-native field arithmetic. For all other parts of the project, you're welcome to use whatever code or libraries you'd like that you can find on the Internet, besides direct copy-paste from the existing double-blind repo. **In fact, we specifically ask that you start off by *not* looking at any other double-blind repos.** ## Recommended approach We suggest that you approach the project in a few steps. The guiding principle is to **get to something simple that works end-to-end as quickly as possible, and add features progressively.** 1. Get a webpage running (with vanilla HTML and Javascript) that allows you to generate a verify a ZKP that you know the pre-image of some Poseidon hash in a list of Poseidon hashes. - We recommend looking at the [snarkjs README tutorial](https://github.com/iden3/snarkjs). 2. Modify your ZKP circuits so that you're proving you have a valid RSA signature of a public message that recovers to some key in a list of public keys, with a very simplified RSA protocol (you can look up the [Wikipedia article on RSA](https://en.wikipedia.org/wiki/RSA_cryptosystem) for example). 3. Modify the ZKP so that it is compatible with ssh keys that are generated and used for signing by `ssh-keygen`. 4. Build a web application of your choice on top of this--for example, a message board, or a voting app, or a game! ## What to do if you get stuck You'll likely run into obstacles while trying to put this all together. Don't fret! That's part of the process. That being said, we don't want you to be spinning your wheels forever. If you've spent 30-60m on a problem and feel like you've made no progress, feel free to ask a 0xPARCer for help. ## Resources and readings See these links: - [Blog post](https://0xparc.org/blog/zk-group-sigs) about zkSNARKs for group signatures - [Video demo](https://drive.google.com/file/d/1CO1bwhRxomV_kAlTqfKvAXAKQTTUogjv/view?usp=drive_link) of double-blind - For general computer-y questions, you may find [Evan Chen's writeup on filesystem concepts](https://web.evanchen.cc/filesys.html) helpful.