PLUME: Verifiably Deterministic Signatures on ECDSA
This repository provides libraries for the construction of deterministic nullifiers on Ethereum keys, ERC 7524. We call them Privately Linked Unique Message Entities (or PLUMEs). We hope that wallets integrate the javascript, rust, or C repositories for both software and hardware signature generation, and dapps integrate the zk proof in the circuits/ directory.
If you would like to get a grant to create PLUME applications or improve the library, we have grants available from Ethereum Foundation PSE and Gitcoin Grants, and would give grants for any PRs to the repository! There are projects ideas both below in the README, as well as bountied every issue in Github has a $50 bounty on it. Feel free to pick one up, and dm us on Twitter/Telegram (@yush_g) or email Provenant Research to help! This work was generously funded and supported by 0xPARC, Gitcoin donors, and EF PSE, and exists only due to the valuable work by contributors to this Github such as yush_g, Oren Yomtov, Richard Liu, Blake M Scurr, Piotr Roslaniec, Vu Voth, Weijie Koh, and Vivek Bhupatiraju who directly contributed to the code. Thanks to Poseidon Labs for a V2 proposal and Weiking Chen for a V3 proposal, and our auditors (0xbok), as well as all of the folks acknowledged in the research paper and blog post.
Contributions
If you'd like to contribute, we offer $50 bounties in Eth/DAI for resolving any of the bugs in our issues! Each of them is quite small. That includes #28, #24, #22, #19, #15, #14,and #13.
Implementations
rust-k256: Rust, using the k256 libraryrust-arkworks: Rust, using arkworksjavascript: JavaScript, using MIRACL
Testing the circom circuit
First, clone this repository and navigate to the javascript/ directory.
Install dependencies:
npm i
If you encounter an error No prebuilt binaries found, try switching to node v18.17.0 (using n, for example) to work around our dependency's build issue.
Then, navigate to the circuits/ directory and install the dependencies there:
npm i
Run the tests:
npm run flatten-deps && \
npm run test
Be prepared to wait around 20-40 minutes for the tests to complete.
TODO
- [DONE] Incorporate the V2 proposed by poseidon to be a codepath both in the wallet WIP PR and in the circom
- Improve
rust-k256to use a similar interface asrust-arkworks- i.e. generate/accept arbitrary keypairs andrvalues, and not just hardcoded values - Rewrite in halo2 (WIP by blakemscurr and vuvoth)
- [$500 Bounty] Implement hash to curve in halo2
- Reduce number of arguments to c via Wei Dai's + Poseidons suggestions (potentially just g^sk, h[m, pk], g^r is fine) and write a proof in the Algebraic Group Model for the change.
- [$500 Bounty] Fix stealthdrop MVP, the first anonymous airdrop to any Ethereum keys via PLUMEs -- repo and slides.
- Edit: Poseidon hash will be too slow in Ledger and is a newer hash function -- given that we have reasonably efficient sha256 hashing with halo2 zkevm sha256 as well as efficient EVM computation in the V2 proposal, we do not intend to switch the hash function away from SHA256.
Resources
Paper
Thesis [most up to date version]: https://aayushg.com/thesis.pdf
Paper [slightly out of date]: https://eprint.iacr.org/2022/1255
Slides
Blog Post
blog.aayushg.com/posts/nullifier
This describes the construction as well as explains our choices for the various hash/hash-to-curve functions.
ERC 7524
Demo
Talk
https://www.youtube.com/watch?v=6ajBnMdJGoY
Circom Proof Data
For the V1,
See this PR.
6.5 million constraints. Mostly dominated by EC operations, but the hashes are very expensive too.
sha256 ~1.5M. hash_to_curve ~0.5M. a/b^c ~1.5 each (this is the sub circuit for the first 2 verification equations). the remaining 1.5M is probably dominated by calculating g^s and h^s.
For the V2, the sha256 is 0 cost in the circuit, but is added to the verification cost. This takes in-circuit constraints down to 5M and adds the sha to the verification.
Hash to Curve Circom Code
https://github.com/geometryresearch/secp256k1_hash_to_curve/ https://geometry.xyz/notebook/Hashing-to-the-secp256k1-Elliptic-Curve
We are giving a $500 grant for an implementation of this in halo2.
Nullifier Calculation Spec
https://hackmd.io/uZQbMHrVSbOHvoI_HrJJlw