This article comes fromAragonThis article comes from
secondary title
background
backgroundAs a leading digital governance project, Aragon Labs has invested heavily in research and innovative governance models. We have identified various Layer 2 governance solutions that show potential, but also have some technical issues.
We have been able to implement a gas-free voting process on Vochain, our dedicated voting blockchain, and have designed and implemented a method using Ethereum Storage proof, which will be based on the ERC-20 generation Coin statistics from Ethereum cross-chain to Vochain. So far though, the possibility of transferring cross-chain results to Ethereum has been an open research question.To that end, Aragon Labs has been running a newly designed experiment,
This design will allow the results of an off-chain voting process to be cross-chained to Ethereum without using subjective oracles or any other trusted components.
Our proposal would allow for a voting process that takes place entirely off-chain, with results enforced on Ethereum with the same integrity as on-chain governance, at a fraction of the cost of on-chain governance.
secondary title
Voting Protocol Proof of Concept Requirements
Before designing the technical solution, we defined the parameters of the research protocol:
The requirements of the voting protocol are:
license-free;
resistance to censorship;
Ability to bind results on Ethereum;
Voters who do not generate gas fees;
Free from token cross-chain;
As simple as possible (no sidechains);
Can be used for voting with ERC-20/ERC-777 and NFT.
As a proof-of-concept design, we accept the following constraints:
No user anonymity: votes can be bound to an Ethereum address;
Not without receipts: it is possible to buy ballots;
There is no clear incentive scheme for relayers.
secondary title
ideal proposal
According to the design of the proposal, when creating a new voting process, the organizer submits a transaction to Ethereum specifying the contract address of the ERC-20 token for the census of voters. The Storage Root Hash of this address becomes the census root of this process at the specified block height. Anyone holding a given token can prove their eligibility by providing a Merkle Proof of the token balance (via EIP-1186). They can then vote by sending the proof and signature to a zk-SNARK rollup relayer, which will compute a proof of the final result.
The potential problem that exists is that the participants in the zk-SNARK proof (the coordinator) that theoretically computed the result could review the result by deciding to exclude the vote. We solve this by allowing anyone (not just the coordinator) to submit new votes: any user can generate and submit an aggregate containing their vote if they detect that the coordinator did not include it.
Our proposal will use zk-SNARKS for the following purposes:
Validate an address without voting through the Merkle Tree accumulator;
Verifies that users own tokens through Proof of Storage;
calculate partial results of a batch of votes;
Based on the above pattern, we can find two main problems:
secondary title
ERC-20 storage proofs are very complex to verify in SNARKs. This is partly due to their use of Recursive Length Prefix (RLP) parsing and multiple Kecmack -256 hash verifications, both of which are computationally inefficient in state-of-the-art SNARK summarization techniques. This problem is difficult to solve, so currently we use optimistic validation to solve this problem.
secondary title
Problem 2: ECDSA/Secp256k1 signature verification is not friendly to SNARKs
One current cryptographic standard that we can use to verify user signatures is ECDSA, which uses a BabyJubJub key from the Ethereum signature, using that signature as the original private key, allowing users to recover their addresses. Since this method relies on user signatures, it is vulnerable to malicious proxies that trick users into signing fraudulent transactions in their Web3 wallets. This vulnerability exists anywhere that browser wallets use to sign transactions. A potential solution could be to use the web address as the derivation path to derive the private key.
Another challenge is proving that each token owner's Ethereum address approves the BabyJubJub public key to vote at the block height created by the voting process. We do this through a "singleton" smart contract that maps an Ethereum address to a BabyJubJub public key, and users must add their key to the smart contract via a standard transaction. Address-to-key mapping can be achieved with optimistic storage fraud proofs. Because these authorization keys are expected to be used multiple times in different voting processes, this solution also addresses data availability issues through a reusable design.
In summary, we can handle most verifications in SNARKs, excluding:
Confirm that an address has not been voted through the Merkle tree accumulator → SNARK before;
Verify whether the user has tokens through Storage proof → Optimistic;
secondary title
user
user
Retrieve their account's voting information and proof of storage, generate a signature on the voting packet, and forward it to a relayer or group of relayers.
secondary title
Voting Smart Contract
Register the voting process, including: ERC-20 smart contract address, slot index of ERC-20 address → balance mapping, state root hash of the starting block of the voting process, and process parameters for calculating votes.
By monitoring the registration of new votes through zk-Rollup, SNARK will prove that:
result calculation;
The voting signature is determined by the BabyJubJub key;
Keep the vote accumulator updated;
Keep the list of voters updated.
Allow anyone to challenge evidence of last vote registration fraud. But one of the following conditions must be met:
Proof of storage, proving that the voter's Ethereum address has no tokens;
Proof that the BabyJubJub key has voted (the key is in the "voted" Merkle tree).
secondary title
Relayer
Phase 0: An election process is created on Ethereum and a relayer is selected from the list of available relayers. The election organizer needs to pay the election fee (rewarded to the coordinator). The organizers provide EVM bytecodes that need to be executed after the election of the DAO smart contract, depending on the outcome.
Phase 1: Voting begins. Anyone can send a voting packet (either HTTPs or libp2p transport) to the chosen coordinator. The coordinator rolls up the selected results in batches, builds a zk-SNARK proof, uploads the proof and the result to Ethereum, collects votes cast by users, verifies them, and broadcasts them to other relayers.
Phase 2: The coordinator who detects that he did not join the vote can roll up his own vote and send a zk-SNARK proof of validity to the voting smart contract. Additionally, if they detect that a vote was added incorrectly, they can send a fraud proof that the previously added result was invalid and the coordinator who produced it will be slashed.
Phase 3: When the voting date limit is reached:
Anyone (usually the coordinator) invokes the EVM bytecode execution, using the final result as input.
secondary title
Lines and Contracts
zk-SNARK will aggregate voting lists. zk-SNARK proofs are valid based on a given voting list, census root, election identifier (electionId) and aggregated results.
Input of zk-SNARK:
Hash input is to reduce the gas cost of SNARK verification;
private election identifier;
Calculated voting results;
the current nullifiers root (nullifiers root);
Updated empty rune roots;
the number of votes in the batch;
The voting value and the corresponding BabyJubJub key signature.
The input to the smart contract function call for uploading the reconciliation result is:
election identifier;
A list of the public keys of the voters in the batch;
Updated empty rune roots;
SNARK proof.
secondary title
Proof of concept implementation
We have implemented a minimum viable smart contract and circuit, thus checking the cost and feasibility of the solution. The proof of concept only includes user registration, vote aggregation, and fraud proof verification.
Our tests resulted in the following gas costs:
User Key Registry Deployment: 258536
Registration: 68956
Vote Deployment: 6673,159
New votes: 25989
Cumulative summary: 291801
Fraud proof 2: 908822 (account ERC-20 balance is zero)
secondary title
future research
Based on this research, we would like to explore the following ideas in more depth:
Verification of standard kecak/ECDSA/Sec256k1 signatures via SNARKs. We believe that soon, PLOOKUP will be able to verify these schemes, which will lead to two possibilities:
Proof that the BabyJubJub key is derived from the Secp256k1 key.
Verify the vote signature itself.
Proof of storage is verified inside the SNARK. We think that this kind of complex wiring can be easily integrated by a zkVM, although the cost may be huge. We are concerned that Ethereum clients will drop out of archive nodes, prioritizing higher gas cost limits, so another area of research is to try methods other than EIP1186 for Proof of Storage.
To calculate the count, some opcodes are embedded to execute in zkVM, making general programmable voting circuits available.zk.moneyProof of votes are generated in the browser, mixed via batch processing, and the results are recursively aggregated, similar to
protocol. This will increase the privacy of the voting process.
Allows SNARKs to be computed in a distributed fashion at the browser level, even if they are expensive to compute. This saves reliance on high-visibility servers and is fully P2P, giving all power to voters.
Embed privacy and mixing in the voting protocol at the network level.
Find a reasonable cryptoeconomic model that is fully interoperable with Ethereum 2.0.
