search

snapshot-labs / sx-starknet

Core smart contracts of Snapshot X for Starknet
https://docs.snapshotx.xyz
MIT License
118 stars 71 forks source link

Merkle Accumulator for voter addresses in each proposal #354

Open Orland0x opened 2 years ago

Orland0x commented 2 years ago

We would store a merkle root of the list of addresses who have voted. Then each time someone votes, they would send a merkle proof of exclusion from this list to prevent double voting. If the voter has not already voted, the proof would pass and then the merkle root would be updated to include the new voter.

Currently we write a new storage slot for each voter, whereas this approach would mean we just need a single slot containing the merkle root for all voters.

bonustrack commented 2 years ago

This could be used https://github.com/starkware-libs/cairo-lang/blob/d61255f32a7011e9014e1204471103c719cfd5cb/src/starkware/cairo/common/merkle_update.cairo#L9

Orland0x commented 2 years ago

The Issue with the standard merkle accumulator is that the proofs submitted by voters/relayers would change after every vote is cast. This makes the system susceptible to front running attacks which could lead to censorship.

This paper seeks to address this issue: https://eprint.iacr.org/2015/718.pdf Allowing the proofs to be updated sub-linearly in the number of additions to the accumulator. However they only discuss proofs of membership whereas we require proofs of non-membership.