Written by
Neiman
on
The latest version of Safecat, my semi-serious project (I haven’t decided myself yet), has commands to issue signed certificates. It also contains an example of what you can do with them.
This article explores this simple idea. Let’s start with a standard problem I like to call the…
The “Are You a Millionaire?” Problem?
The “Are You a Millionaire?” problem goes like this.
You want to prove to Bob that you’re a millionaire, good for you by the way, without exposing how much money you got or in which banks.
One (partial) solution is if all your funds are held in one bank. In this case you show Bob a digitally signed document from the bank stating you’re a millionaire - good for you, again! - without specifying the exact sum you hold. This is only a partial solution since we didn’t want to expose your bank.
However, even this partial solution won’t work in the next case.
Assume you’re holding half a million in each of three different banks. Yes yes, you’re still a millionaire, for the last time - Good. For. You. - but since none of these banks know that, they can’t produce a millionaire certificate like before.
The way to solve this problem is by using zero-knowledge (ZK) protocols like SNARKs or STARKs. It goes like this.
First, assume there’s a list of banks both you and Bob recognize, and each bank is represented by a public key.
Now write a ZK program as follows:
The public input of the problem is the list of trusted banks. The private input, which no one will ever see besides you, is the list of your signed bank statements, saying how much money you have in each.
The program then checks that the sum of the money in all signed statements is bigger than a million and that they are signed by banks from the list. The program outputs a proof for the claim.
You send Bob the program, proof, and public input (but not the certificates themselves!). Then you go to sleep with a smile on your face. This time not only because you’re a millionaire (stop it! stop it! Not good for you!), but also because you proved it to Bob who’s right now as jealous as a green tomato.
Generalizing to certificates
This example works not only for signed bank statements but also for any signed certificate.
Say you hold a collection of certificates signed by reputable entities. There are plenty of claims you can construct using these certificates.
For example, a claim that you’re not a citizen of a sanctioned country, so you’re allowed to get financial services or a claim you’re an adult, over 18, so you can be served alcohol. The options are limitless, depending on who’s asking or which information the certificates contain.
Nowadays to prove such claims you have to expose your certificates. Something that completely violates your privacy. But with ZK programs you can do the same trick as before.
Write a program that gets two inputs:
- (public) a list of public keys of reputable entities that we trust to sign certificates
- (private) signed certificates
The program then checks the claim, and that the certificates are signed by entities from the list. It generates a proof that you can send to whoever is asking the question.
Creating new signed certificates from old ones
Personally, for me, what this process does is generating new signed certificates from old existing ones.
It kind of makes sense. You got your “old” collection of signed certificates. You create a ZK program for a new claim and generate proof of it. Your program is the new certificate, where the proof is a new signature.
Voilà! You just created a new signed certificate from the old ones.
Generalizing even further to databases
Yes, you can go bigger than certificates.
For example, take a database signed by some reputative entity and make a claim based on the information it contains. The ZK program does the same query, verifies the information, and then verifies your claim.
Here you go, you got a proof of a claim based on a signed database, without exposing the database itself.
The idea can be further expanded, for querying data from several databases. Actually, it would work for any signed data.
The only problem is that the current ZK technology doesn’t function well with big data or complicated computations, and you may end up in a state where the proof takes a very long time to make.
Application to proof of humanity
“On the Internet, nobody knows you’re a dog,” says the famous cartoon. Nowadays it’s even worse, on the Internet, nobody knows if you’re a bot or an AI or just one person pretending to be a million people.
This problem can create quite a damage. Let’s look at the example of Gitcoin.
Gitcoin is a project that gives funds to open-source projects based on voting. People vote by donating money to their favorite projects, and in the end, an additional pool of donations from big organizations is spread among the projects based on how much the users donated to each project.
Gitcoin uses something called “quadratic voting”, which basically means that it’s more important how many people donated to you than how much each of them donated.
This worked well for a while, till projects started to cheat and launched Sybill attacks. In a Sybil attack, one person creates thousands of bots, each donates 1$ to their project, making it seem like the project has many supporters though in practice it had very little.
The situation got so bad that in Round 12 of Gitcoin 27.9% of the users were flagged as bots, and who knows how many they missed?
To mitigate things Gitcoin Passport was launched. With Gitcoin Passport you collect signed certificates (they call it stamps) from all kinds of sources and then get a “humanity score” based on all the certificates you collected.
This is a good approach for proof of humanity, where you don’t trust one method or one entity but rather distribute your trust. The main issue with this approach is that every time you want to prove you are human you have to show all your certificates, and that’s just terrible for privacy.
This can be solved easily with ZK proofs. We even made a proof-of-concept below that does that!
How it work in practice? Safecat + Noir example
Noir is a well-known ZK programming language by Aztec, while Safecat is a simple CLI tool meant for experimentation.
In this example, I generated with Safecat a data set of entities and signed certificates of humanity. Two of the entities, Einstein and Euclid (I went funny with the names), signed a certificate claiming another entity, Satoshi (funnnny!), is a human, including its date of birth.
The set of trusted entities is put into a Merkle tree and is represented by the Merkle root.
Then we build a Noir program that does the following. It gets the two signed certificates (as private input), and the hash path proving the signers are in the Merkle tree (also as a private input). It verifies that these certificates were indeed signed for Satoshi and that they are still not expired.
See the full details here.
The program is quite unelegant, but don’t let it influence your opinion about Noir or zk programming! This is really my fault more than anything.
The program is based on the certificates having EdDSA signatures using Baby Jubjub, which is what Noir likes. It makes everything a bit simple to implement and faster to prove and verify.
Can you already do a similar thing now to something like Gitcoin Passport? Emphatically yes! It would help though if the signatures in the pass would be in a format Noir likes, but is not crucial.