This is very cool and really impressive! Nice work, both on a conceptual level and on getting everything to actually work :)

If anyone is curious, here are a couple pointers to related work on problems similar to this.

First, the ideas used here are vaguely related to the way that ZCash works under the hood. The ideas in ZCash come from a sequence of three academic papers: ZeroCoin, PinocchioCoin, and Zerocash:

- ZeroCoin: http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

- PinocchioCoin: https://www.microsoft.com/en-us/research/wp-content/uploads/...

- Zerocash: https://eprint.iacr.org/2014/349

More directly related in terms of application, but quite different in mechanism: the Handshake airdrop in early 2020 could be claimed anonymously. This was slightly tricky because the idea was to retrofit to existing RSA keys. We (full disclosure, I worked on this project) called the resulting protocol a "GooSig":

- GooSigs: https://eprint.iacr.org/2020/676

Section 3 of that paper gives a way of anonymously airdropping to existing ECDSA or EdDSA keys without using a SNARK. The setup may not be quite the same as in the case being discussed above, though. Notably, it requires sending a short message to the recipient before they can claim their funds. But the message can be encrypted to an existing key of theirs and posted publicly, so this probably isn't much of a limitation in many practical cases.

Thank you!

Those papers are some of the densest ones, so maybe as a starter I would recommend Vitalik’s blog posts on ZK[1].

If folks are interested in a complexity theoretic introduction to ZK proofs, incidentally, in the interest of being self recommending, I authored one myself I’d be curious to hear thoughts on :)[2]

[1]: https://vitalik.ca/general/2021/01/26/snarks.html

[2]: https://nibnalin.me/dust-nib/a-succinct-story-of-zero-knowle...

Yeah, those papers are very dense. You might want try reading zerocoin[0] first, it was the starting point of all the zero-knowledge proofs for private payments on a blockchain. Then another academic paper, Pinocchio coin, had a proposal for zkSNARKs. And Zeorcash built the zksnark + merkle tree+ serial umber (later called a nullifiers ) approach.

[0] https://www.cs.umd.edu/~imiers/pdf/ZerocoinOakland.pdf

Sorry I left out ZeroCoin, and thanks for pointing it out! Total braino as I was writing the post.

Great writeup of some of the design thinking and challenges around building a ZK system.

Using a community chest to reward front-runners for submitting claims is clever. Would the ETH reward still need to be at least as large as the transaction cost to incentivize front-runners? Or is there still a cut of the token being taken, in the hopes the token value will make up the difference?

It seems like there would still be a basic gas problem any time the receiving account wants to use the (ERC-20) token, eg to send the token somewhere else via a wallet or some other standard UI?

Very useful exercise, thanks for sharing.

> Using a community chest to reward front-runners for submitting claims is clever. Would the ETH reward still need to be at least as large as the transaction cost to incentivize front-runners? Or is there still a cut of the token being taken, in the hopes the token value will make up the difference?

Yeah, it definitely needs to be at least as large as the gas fee (otherwise front runners will just run the transaction locally and notice that it’s not worth rebroadcasting). Our mechanism doesn’t take a cut of the token, mostly because it is hard to put a value to the token as we mention in the post.

> It seems like there would still be a basic gas problem any time the receiving account wants to use the (ERC-20) token, eg to send the token somewhere else via a wallet or some other standard UI?

That’s certainly true, but if, for instance, your primary use case was as a governance token, most governance happens off-chain(on Snapshot Labs[1], for instance), so that wouldn’t require any funds.

[1]: https://snapshot.org/

I'm definitely onboard with the examples, where influential people's votes influence others, or an influential person votes against an expected outcome and draws ires.

The same is seen with asset holdings within known addresses, especially registered ENS domains. Known selling can mess with the future reputation in the community. Of course, it is super easy to build a new reputation from a new identity, a couple weeks in this market, but this is an unnecessary waste of time.

> I'm definitely onboard with the examples, where influential people's votes influence others, or an influential person votes against an expected outcome and draws ires

In fact, I see that as the potential #1 usecase: enabling zero-trust voting, with the "drop" simply being a way to instantiate the set of voters at time t to prevent a takeover by freshly created accounts created just for the vote.

A weighting by history (say give 20% more weight to a vote per year the address has existed) and activity (say on HN to give more weight to people who post regularly comments that do not get too many downvotes) could have interesting feature for online communities

> weighting by history (say give 20% more weight to a vote per year the address has existed)

I think the capability should be developed and easily applied, I don't think every project needs the ponzinomics to incentivize holding

Wow that didn't take long to break: https://twitter.com/0xPARC/status/1493704577002049537?s=20&t...

As long as "crypto" requires absolute perfection, and even experts have difficulty achieving that it isn't reasonable to suggest crypto for everyday use. This always annoys me when people blame victims for not simply "reading the contract" to verify it's correct. People don't have to carefully audit everything a bank does when they open an account, people don't need to be expert auditors to have a reasonable sense of security when depositing their paycheck.

This is pretty cool. But you might want to update the credit for the zksnark +merkle tree + nullifier idea. It's from an academic paper, Zerocash in 2014. The approach is used in Zcash and then in Tornado.cash Though Tornado.cash is actually an odd hybrid between Zerocash's merkle tree+snark approach and an older academic paper, Zerocoin, which proposed a zk mix protocol as an add on to Bitcoin.

That's a really good write-up. We've been investigating somewhat similar approaches for a problem space we are in.

I wasn't aware of the huge space requirements to use a proving key. That's somewhat limiting, although we do have the advantage that we have a (mobile) wallet we could potentially allow running ZKSnark inside. Are you aware of any work on that side?

The only work adjacent to this I’m aware of is MetaMask Snaps[1], a plug-in system that allows for arbitrary code execution in wallets.

I know some teams in the 0xPARC community[1] are interested in it and have been looking into using it, but nothing publicly shareable on that yet.

[1]: https://0xparc.org/

Yes I read that with interest. If you or any of them is interested in working in this area further please reach out (contact details in my profile).

Web2.0 boomer here. Can someone ELI5 what is an, "Airdrop?"

In cryptocurrency, an "airdrop" refers to receiving free tokens in your wallet.

Some times they're designed to incentivize certain activities, like promoting the coin or participating in something.

As a marketing tactic, they work quite well. Crypto fans will do surprisingly large amounts of free PR and free work for "free" tokens.

From an economic perspective, if a token system is giving out free money to large numbers of people it's effectively inflating away the value of the coin. Ironic given the initial anti-inflation ethos that drove the early days of cryptocurrency.

Total supply is not the only important factor. If there are a million units of some token and a thousand people hold it then each token will still be worth more than if there were just a thousand units, all held by one person. Network effects matter far more than total supply!

If you squint even Bitcoin had an airdrop: Bitcoin has been in an inflationary regime for its entire history and for a while was giving out Bitcoin to anybody who ran the right program on their laptop.

Imagine someone sending you $100 to your bank account. Except those $100 can be tokens. And your bank account is your crypto address.

> ECDSA inside ZK-SNARKs is a starting point that unlocks many other ideas!

Is there a good way of reasoning about what type of ideas this unlocks?

One incomplete answer:

At the bottom, this lets you prove that you know a signature without revealing what that signature is. This idea has been used in anonymous credential systems---much like this one! In the cryptographic literature, the underlying idea goes back to David Chaum ("Blind signatures for untraceable payment," Crypto 1982) and as far as I know the first implementation was Camenisch and Lysyanskya ("An efficient system for non-transferable anonymous credentials with optional anonymity revocation", Eurocrypt 2001).

Even without the zero-knowledge property this idea is useful, essentially because the "K" in "SNARK" stands for "knowledge" (as in, argument of knowledge). In other words: a convincing proof tells the verifier that the prover must know a signature, even if the prover doesn't actually publish that signature. You could also prove that you know 10 signatures, or 100, or more (well, up to the somewhat limited reach of existing proof systems).

Meanwhile, the size of the proof and the cost to verify it grows much more slowly than the number of signatures whose knowledge it establishes---so you can think of this as a kind of cryptographic "compression." This is one of the big ideas behind rollups, which are one possible way of improving the scaling behavior of blockchains like Ethereum.

See 0xPARC’s recent blog post[1] on this topic (in particular, see the section “What can we do with zk-ECDSA?”)

[1]: https://0xparc.org/blog/zk-ecdsa-1

WOW!

Thank you!

Yep. The pseudoscience tech is the sales pitch and the token sales is the motivation for all "crypto" digit tokens