Aragon-Aztec Private Voting - Documentation - Main page

tags: Aragon Aztec Nouns DAO Private Voting Research Sprint

For detailed progress of Noir primitives, feel free to refer to the Noir Roadmap.

Progress Reports

Progress Report 4

This is the fourth report on the progress made by AZKR and Aztec in implementing our joint proposal submitted to the Nouns DAO Private Voting Research Sprint.

Summary

In the past weeks we have been busy completing the work on the main components. We are now fully focused in the integration phase. A complete version of the ZK circuits for vote submission is now available, thanks to the successful completion of storage proof implementation. A first version of the zkRegistry has been deployed and is now ready to be used. Finally, the TLCS technical report has been published, work on the TLCS-chain prototype is almost complete and we made progress on the Rust version of the TLCS cryptography code.

Implementation Overview

• Voting system

  • Circuits
    • Mostly complete; further testing with storage proofs required (storage proof implementation was recently unblocked by this PR)
  • Rust
    • Implementaiton is available
    • CLI has been implemented and now is in the process of being polished.
    • Smart Contracts have been implemented, waiting for integration with Noir Verifiers Contracts. This will be deployed in the coming days ⚙️
    • The Tally Prover works, work on optimisation is still in progress ⚙️
    • Code for getting storage proofs is going to be implemented next week ⚙️

• Noir Ethereum storage proofs

  • Proving in CLI
    Image Not Showing Possible Reasons

    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported

    Learn More →
    
    A depth-8 Ethereum storage proof of 713k constraints was successfully proved in CLI.
    Proving time was 1.5 - 3 minutes on an average machine.
    The implementation is available.
  • Proving in browser ⚙️
    • Fundamental:
      • bb.js MVP in browser
        Image Not Showing Possible Reasons

        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported

        Learn More →
        
        The JavaScript package of the UltraPlonk proving backend barretenberg now works in browser environments. Find a Next.js example here.
      • bb.js Recursion & Multi-threading in browser ⚙️
        Incompatibilities between Next.js and how bb.js handles worker generation were uncovered and are currently being addressed.
      • Noir Packages MVP
        Image Not Showing Possible Reasons

        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported

        Learn More →
        
        noir_wasm and ACVM.js for compiling and executing Noir programs in JavaScript / browser environments are now available:
        • noir_wasm
        • acvm-simulator-wasm
    • Optimization:
      • Plookup Dynamic Arrays
        Image Not Showing Possible Reasons

        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported

        Learn More →
        
        Merged in on PR #1282.

• zkRegistry

  • The first version is now available
    • Currently, it supports babyjubjub curve, BLS12 and keys computed as Poseidon hashes.

• Timelock

  • Documentation: A draft overview of the service is now available
  • Rust implementation is now available
    • The basic fuctions such as protocol initialization have been implemented, hashing, serilizations have been implemented.
    • Implemented TLCS for two curves: ark_bls12_381 and ark_mnt6_753. The structure is designed so that new curves can be added easily.
    • Remaining tasks ⚙️
      * Add babyjubjub
      * Interaction with drand
      * Proper readme file
  • Tlcs-chain has 3 of 4 stages implemented.
    • 1/4 Added CLI commands and REST endpoint for users to submit proofs and query submitted data
    • 2/4 Tx processing added on the blockchain side to verify then store the submissions
    • 3/4 "Begin blocker" code added which runs automatically when necessary to generate public keys
    • 4/4 Work has started on code for retrieving LoE data to generate secret key when necessary ⚙️

Next steps (by mid July)

• Finish remaining tasks ⚙️
• Finish demo script
• Final report

Progress Report 3

This is the third report on the progress made by AZKR and Aztec in implementing our joint proposal submitted to the Nouns DAO Private Voting Research Sprint.

Summary

We continue to progress nicely on several fronts. We have clarified some uncertaintes but some others still remain and new ones have appeared.

Implementation

• TLCS
  • A skeleton version of the TLCS blockchain software has been implemented. Some of the core blockchain functionality is now in place, work continues to implement the remaining functionality.
  • The current version has been deployed in a network of three nodes.
  • Code now available:
    • C implementation
    • Rust implementation
    • Warning: this code is still experimental code: Some basic fuctions such as protocol initialization have been implemented. The main challenge currently is serialization (in order to compute the hash function) and hashing to the curve point.
• Noir Ethereum storage proofs
  • Primitives for storage proofs are now complete with Variable-length Keccak256 merged in since our last progress update
    Image Not Showing Possible Reasons

    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported

    Learn More →
  • Primitives for proving in browser
    • Fundamental
      • Low Constraint Recursion in UltraPlonk was merged in on PR #414
        Image Not Showing Possible Reasons

        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported

        Learn More →
      • bb.js is an NPM package of the UltraPlonk proving backend barretenberg. An alpha version is now released with recursive, low memory and multi-threaded proving
        Image Not Showing Possible Reasons

        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported

        Learn More →
        
        The source code is available here. Feel free to give it a try by installing it with npm install -g @aztec/bb.js@alpha.
      • Noir Packages covering interactions with Noir programs + UltraPlonk in browser environments are met with slight release delays. We are currently in the process of fixing instabilities.
        The release date is re-targeted to be no later than the end of this week. The Noir frontend demo will be updated with the new set of packages once they are ready.
      • Recursion in Noir is met with slight release delays. We are currently resolving merge rebases and conflicts.
        The release date is re-targeted to be the end of this week. You can follow the latest progress here.
    • Optimizations Since our last progress update, we have discovered the need and have kickstarted the following intiatives to provide a better voting UX from web browsers.
      • Dynamic Arrays was merged in on PR #1271
        Image Not Showing Possible Reasons

        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported

        Learn More →
      • Plookup Dynamic Arrays is a behind-the-scenes upgrade that further optimizes dynamic arrays in Noir through the use of efficient RAM/ROM opcodes if the proving backend used is capable of supporting them.
        It is currently under pre-merge review. You can follow the latest progress here.
• Voting system
  • Ethereum storage proofs: Noir circuit sizes becoming more manageable (~250k for a depth 8 proof without Keccak checks)
  • zkRegistry: first implementation for the prototype done. We’re started a process of drafting a standard (may turn into an EIP) with other projects that also have similar needs. Everyone is invited to participate (send us a DM to do so)
  • Tally server: Basic functionality implemented. Currently optimising circuits. Researching if it is more convenient to use Poseidon or Keccak hash.
• Integration
  • Most of the work is to be done during June, but we’ve already tested that everything works compiled to WASM in the browser.

Uncertainties

• UltraPlonk look-up optimisations is crucial for the storage proofs but hasn't yet been merged.
• The current implementation of the tally server relies on generating proofs for up to ~2000 voters and requires a SNARK-friendly hash function. We are currently using Poseidon but are investigating unusually large circuit sizes that make this less feasible.
• Keccak would be the better choice for the tally as far as gas costs are concerned (one hash is computed per vote), but this would be expensive to do in a circuit. Poseidon would be a compromise if we manage to get the circuit size down.
• Next steps: Tally server: decide on which hash functions to use based on further testing.
• For TLCS, we may initially use the C implementation as the Rust version is not yet ready.

Progress Report 2

This is the second report on the progress made by AZKR and Aztec in implementing our joint proposal submitted to the Nouns DAO Private Voting Research Sprint.

Summary

Significant progress has been made in both the Noir Ethereum storage proof and Time Lock Cryptographic Service areas. However, upon further examination of our original proposed project scope, we have identified additional requirements and are currently working on an expanded scope. This concerns the generation of storage proofs (and thus trustless voting) directly within web browsers.

While our primary objective remains the implementation of trustless in-browser voting during the research sprint, we are also broadening the project's scope to encompass the generation of storage proofs from users' local machines and/or a delegated external server. This backup solution will prove useful in ensuring a smooth voting user experience, even if optimizations for voting through web browsers fall short by the end of the research sprint.

Design

• Time Lock Cryptographic Service (TLCS) A draft of the specifications is completed, including the main algorithms. A cleaned up version will be published together with the next update.
• Proof geneartion from CLI / server Considering the possibility of Noir optimizations listed in the following sections do not fully make their way in time to ensure a decent voting UX in web browsers by the end of the research sprint, we are providing a transient solution in parallel where a voting proof can be generated on the user's computer or in an external server.
  AZKR will lead the R&D of the fallback solution, while Aztec Labs will continue leading the R&D of the Noir optimizations to improve trustless in-browser voting.

Implementation

• TLCS First PoC already working with an implementation in C/C++ that uses OpenSSL and therefore supports all the curves of OpenSSL and in addition it supports RSA. Now working on the implementation in Rust + Arkworks. The public repository will be available in the next progress report. Meanwhile, work on the blockchain layer in Rust is also progressing.
• Noir Ethereum storage proofs
  • Primitives for storage proofs With both UltraPlonk Keccak256 and UltraPlonk ECDSA verification gadgets now integrated with CLI Noir, all primitives for building Ethereum storage proofs in Noir are in place.
  • Primitives for proving in browser
    • Fundamental
      • NPM Package of UltraPlonk release workflow is one of the works we have kickstarted our work to enable generation of Ethereum storage proofs in web browsers.
        The release pipeline of UP NPM packages is aimed to complete by end May. You can follow our latest progress here.
      • Recursion in Noir is another piece of work that we have kickstarted for generating proofs of large Noir programs (like Ethereum storage proofs) in web browsers. With that we would be able to split the program up into smaller chunks, and aggregatively complete a proof of it via recursion (i.e. proof of proofs of proofs…).
        Noir recursion is aimed to complete by end May. You can follow our latest progress here.
      • Low Constraint Recursion of UltraPlonk set out to optimize UP recursion's costs to costs \(2^{18}\) (~260k) constraints per proving operation.
        The work is currently under review here.
      • Low Memory Prover of UltraPlonk was kickstarted to increase UP WASM's supported Noir program constraint count ceiling from \(2^{17}\) (~130k) constraints as discussed in our last progress report to \(2^{19}\) (~520k) constraints.
        The work, together with UP low constraint recursion, unlocks recursive proving in UP WASM (hence in web browsers).
        Proof of conecept is successfully running in both NodeJS and browser environments. We are in the process of reviewing and merging the work into the main barretenberg repo. You can follow its latest progress here.
    • Optimizations Since our last progress update, we have discovered the need and have kickstarted the following intiatives to provide a better voting UX from web browsers.
      • Multi-threading of UltraPlonk NPM Package is carried out as part of the UP LMP works, which significantly improves proving speed of Noir programs in browser environments.
        With multi-threading, proving time of a 512k Noir program can be improved from 3.2mins in a single-threaded context to 25s on an 8-core machine. Given the millions of constraints users will be proving with on Ethereum storage proofs, this would be a significant UX upgrade when in place.
        The multi-threading works are carried out in conjunction with the UP LMP works. You can follow its latest progress on the same PR.
      • Storage proof related Noir optimizations are also in progress to bring the constraint count (hence proving time) of Ethereum storage proofs down, including but not limited to:
        • Dynamic arrays
        • Low constraint recursion
        • Plookup dynamic arrays
        • Variable-length Keccak256
  • Noir Program Optimisations have been carried out so that proofs involving RLP decoding can now be generated. Further bottlenecks have been identified and are currently being addressed, which should result in a further reduction of circuit sizes, making server proofs realistic and browser proofs a possibility with the help of recursion and WASM multi-threading.
• Proof generation/verification There has been good progress on vote generation and vote verification, so far without storage proofs. An important focus was on making sure that there is compatibility between the programs that generate the proof, and the program verifying it.

What does all this mean for the Nouns community

• What do we aim to deliver by the end of this project (late June)?
  • Clear answers to research questions 1 to 4 (listed below)
  • Proofs of concepts (PoC) of the key components of the proposed system to back our answers
  • Integration PoC
• Research questions This is a research project, thus, the expected outcome is to answer some research question(s) and shed light on the next steps (e.g. the following research questions). To this end, making some progress in the state of the art is usually required. Our research questions are as follows:
  1. Up to which point it is possible to build a user-friendly, trustless (decentralised), fair (no one can count votes before a given time), weighed (voting power depends on the amount of tokens hold/delegated) and ballot-secret (it is impossible to link a voter with a choice) voting system in Ethereum?
  2. If all these properties cannot be met at once, which are incompatible and why?
  3. If all these properties cannot be met at once, which is the recommended combination and why?
  4. What is needed to make the recommended combination available to the Nouns community? (Resources needed, roadmap, etc.)
     Definition of PoC: experimental but working code with command line interface (CLI)
• What must we investigate and at which point are we now?
  The most relevant areas where we are pushing the state of the art forward are the following.
  • Ethereum storage-proofs: stand-alone solution vs in-browser, progress made, progress expected, etc.
    Ethereum storage proofs are the "holy grail" necessary for trustless proofs of token ownership. Ideally we want to generate them locally in users' web browsers, which will achieve trustlessness and one-click voting. The main unknmown at this stage is in-browser proving time. This is why we are exploring the alternative solution of providing an open source program for generating such proofs on the user's computer, or on a trusted server.
  • Proof generation/verification Our design achieve ballot secrecy by proving that a certain ethereum address held or had delegated a certain number of Nouns NFTs at certain ethereum block without reveling to the verifier (a smart contract of the voting system) the specific address. Development is well under way and we do not expect any particular problems, beyond integration issues between Rust and Noir.
  • Time lock cryptographic service (TLCS) Our design achieve fairness encrypting the ballots with the decryption key only available after a time t (e.g. after the voting period is over). This must be done in a trustless manner, but to the best of our knowledge such solution does not exist today, thus, we are developing it under this project. Currently we have a PoC in C/C++ and we have already started the Rust implementation. We believe that this service can be useful to other projects like Vocdoni, thus, we are building it as a stand-alone service. TLCS enables other promissing cryptographic applications like timed signatures/ZK proofs that can be verified until time t but after time t nobody will longer be convinced of the validity of the signature/ZK proof.
  • zkRegistry This is required for nullifiers (i.e. prevent double spending/voting) and does not pose patricular problems.
  • Delay relayer In our design this is another stand-alone service which 1) acts as a mixnet, thus, adds one more layer of anonymisation, 2) allwos thrid parties to pay the voting gas costs, and, 3) may enable votes agreggation. For time reasons we are not focusing on it during the current sprint. But this doesn't mean that we forgot it. We are already in contact with hopr to expore together how their mixent, which is already in production, can be adapted to meet our requirements.
• What will we do after June?
  • Beyond Nouns, both AZKR and Aztec Labs plan to keep working on the developments we are doing under this project because they are core for our activities, thus, are part of our roadmaps. In-browser storage proof is a key unlock for ZK dApps to trustlessly make use of on-chain information. AZKR must provide a similar voting system to the Aragon community by early next year.
  • But we will be more than happy to contribute to implement the workplan we will deliver at the end of June to evolve for the PoCs we are developing under this project to a user-friendly solution for Nouns. According to our perliminar results, a fist version of such solution should be feasible by the end of this year or early next year.

Progress Report 1

This is the first report on the progress made by AZKR and Aztec in implementing our joint proposal submitted to the Nouns DAO Private Voting Research Sprint.

• Design

  • Ready to receive feedback from third parties This is the perfect time to make changes. We encourage the Nouns DAO and the rest of the web3 community to go over our design and give us feedback (as comments in the HackMD). Let's build a rock-solid private voting system all together!
  • One change from our original proposal is the introduction of the zkGlobalRegistry (zkreg.eth). Every Nouns holder or delegate will have to register to this registry once before being able to vote. Although this is a small overhead, we have found no other way to guarantee unique nullifiers, which prevent double voting. On the positive side, we believe that other web3 project may also benefit from this registry.
  • A second potential change we are considering is to develop a parallel solution in case in-browser Ethereum storage proofs will take too long. This would be a proof generator that can be used in two ways: 1) a standalone docker container that can be deployed and used by voters deirectly or 2) as a remote service that would be part of the delay-relayer. We hope however that this development will not be necessary.

• Implementation

  • Noir UltraPlonk Integration
    With months of collaborative efforts across engineering and cryptography teams, UltraPlonk is now integrated with CLI Noir (GitHub PR) 🎉
  • UltraPlonk WASM Constraint Count Benchmark
    A benchmark of UltraPlonk WASM was conducted on a local test build of Noir with UltraPlonk to explore the circuit count ceiling of UP WASM under WASM's memory limit. The current build supports a Noir program with up to \(2^{17}\) (~130k) constraints.
  • Ethereum Storage Proofs (Noir) The unoptimized implementation is complete, and we are currently working on optimizing the code to generate smaller proof sizes. The large proof size poses a potential risk to the project, and one solution is using recursion.
  • Noir Recursion
    In the light of the benchmarking results versus the millions of constraints estimated to be needed for storage proofs under the current design, we are investigating the feasibility to introduce recursion in Noir + UltraPlonk within the reasearch sprint period to unlock proving infinitely-large Noir programs in browser. Track the scope and progress on GitHub here.