## Non-coercible voting with MPC operator
ln this text, I will propose an efficient non-coercible voting system with MPC process instead of an operator. It is largely motivated by MACI, however, there are also significant differences.
### Design considerations
MACI has the following desirable properties:
- Soundness
- Privacy
- Non-coercibility
*Soundness* means that the outcome of the vote is always correct, i.e. no parties can cheat to meddle with the outcome of the vote.
*Privacy* means that everyone's votes are private by default.
*Non-coercibility* means that it is infeasible to prove how a participant voted.
Non-coercibility can not be enforced without an additional party, operator. With it, it is enforced using the ability to switch keys. My main goal will be having key-switch with minimal involvement from the operator, so it can be easily put into MPC.
I will mostly discuss the key-switch part, because "adding the votes" part is trivial in MPC.
---
We will build up from the following system which satisfies privacy and soundness, but without non-coercibility:
### No key-switching system
Every user has a public key **P~i~**, private key **p~i~**, and a nullifier **null~i~ = Hash(p~i~)**.
Public keys are known and contained in some registry, zk proofs will typically use a Merkle tree of this registry.
To cast a vote, they publish the following data:
**[X, Y, Z] = [enc(vote~i~ + | + salt), null~i~, zk~i~]**
where
**enc** is an encryption with a public key of the operator
**vote~i~** is their vote (here and further we assume that it is some kind of vector that can be added linearly)
**zk~i~** is a zk-snark proving the following predicate: "there exists **P~i~** in a registry such that I have corresponding private key **p~i~** and **Hash(p~i~) = null~i~** and **X = enc(vote~i~ + | + salt)** where **vote~i~** is a correct vote for user **P~i~**"
Operator then must do the following: remove votes with coinciding nullifiers, decrypt and add everything up.
In principle, this system can even be made operator-less by just broadcasting votes in the open.
This system is clearly coercible, because user can reveal their vote, but it is private - if user does not reveal their vote deliberately, it remains anonymous.
---
Let's build this up to the naive key-switching system (which will still be coercible, but will the necessary intuition).
### Naive key-switching
Let's define the chain of private keys as follows: **p~i~^0^ = p~i~, p~i~^k+1^=Hash~2~(p~i~^k^)**. Here, **Hash~2~** is some different independent hash function.
Now, lets modify the previous system in a following way. We will dynamically update the list of all already sent transactions on-chain (assuming here that the smart contract will just not take transactions with duplicate nullifiers).
The data in the transaction will now look as follows:
**[X, X', Y, Z, W] = [enc(vote~i~^k^ + | + salt), enc(vote~i~^k-1^ + | + salt~2~), null~i~^k^, enc~P_i~(vote~i~^k^ + | + k + | p~i~), zk~i~^k^]**
First notable difference is that we also broadcast the encryption of the vote, concatenated with its index **k**, with our own private key **p~i~**. This is necessary to guarantee that the user has an access to their own previous vote, to invalidate it in future.
The proof is also slightly more involved. There are two cases:
- either **k=0**, in which case the statement is the same (with trivial modifications), and an additional requirement that **Z** is the correct encryption of user's vote.
- or **k>0**, in which case it also says that there exists an already submitted transaction, **Z** of which decrypts via **p~i~** into a correct **vote~i~^k-1^ + | + k-1**.
Basically, that means that a user (even anyone who has a private key) can send a new transaction which is linked to the previous one, and subtracts the previous vote before adding a new one.
The system still can function without operator if **X**, **X'** are sent as cleartext, but then the fact which votes were taken back and in what order will be clear to everyone.
This system is kind of pointless, still, because it is coercible: an adversary can require user to reveal their nullifiers **null~i~^k = Hash(p~i~^k^)** (and prove in zk they are correct), and then check that no new votes in the same chain occur.
---
Now, my idea is to ensure that an adversary can not learn nullifiers. This is the only place where MPC is necessary.
### Non-coercible key-switching
We will assume there is a collection of operators, with public keys **O~j~**. I will work in 1-of-n trust assumption and n-of-n liveness assumption, but it can be modified if necessary. Denote as **O = O~1~ + ... + O~n~**
Now, suppose these operators have **enc~O~(x + | + salt)**. Assume that there is an MPC protocol, which calculates some secret function **F(x)** (only requirements are - it is pseudorandom, and it should be easily calculatable in MPC; multiplying a point of an elliptic curve by a secret scalar will work in this context).
*// Kobi calls a similar thing "oblivios pseudorandom function". Main point is that adversary will not be able to replay it, hence "oblivious".*
We will also require another MPC protocol, which checks whether a secret value **x** belongs to a public set **S**.
We also denote as **enc_mall** some malleable encryption (with O being public key). We will use it to keep track of "double spent" votes without revealing the fact that they were double spent to an adversary.
The following modification is done to the previous protocol:
Users publish the following:
**[X^k^, Y^k^, Z^k^, D^k^, Q^k^] = [enc(vote~i~^k^ - vote~i-1~^k + | + salt), enc(null~i~^k^ + | + salt~2~), enc~P_i~(vote~i~^k^ + | + k + | p~i~), D^k^, zk~i~^k^]**
Where D^k^ is either **enc_mall(1)** for k=0, or re-encryption of **W^k-1^** of a vote it refers to (see further).
Modification is done to zero knowledge proof to ensure formation correctness.
Now, MPC calculates **F(null~i~^k^)**, and checks whether it belongs to the set of already revealed salted nullifiers (it should take logarithmic time).
The tuple **[X, Y, Z, W, F]** is then constructed.
In case **F(null~i~^k^)** is new, **F = F(null~i~^k^)** and **W** is a re-encryption of **D**.
In case it is a double spend, **F = random well formed nullifier**, and **W = enc_mall(0)**
This tuple is added to the list of votes.
This is good - an adversary will not be able to learn whether the vote is taken back or not.
During vote tallying, the coefficients from **W** are multiplied by votes, therefore removing any double spent votes and all votes derived from them.
### Racing ?
It might be possible to send an adversary some information which does not include private key, yet allows them to construct a valid vote. Then, user will be forced to race an adversary.
If such attack is feasible, I suggest the cryptoeconomic mitigation, similar to private key selling: *anyone who is able to submit a correct transaction should be able to steal a security deposit*.
This is doable:
1) To prevent frontrun, transactions are submitted in a commit - reveal pattern: i.e., they are first committed, and then revealed in a further block.
2) The transaction can be submitted in a slashing mode, in which case it is still processed normally. In case it is accepted, the nullifier is added to the list of known nullifiers, but tx is not added to the list against which the Merkle proofs are done. Instead, it will be processed separately, just by subtracting **vote~i~^k-1^**, but not adding a new vote.
3) After the end of the voting process, the same mechanism is used to get security deposits back.
Downside if MPC suddenly drops liveness, everyone's security deposits will be locked up. I do not think this kind of attack is counterable (either here or in MACI //it exists in MACI in a similar way) without such restriction.

Challenge rounds in Groth16-like system This is a continuation and clarification of my previous post which was a very rough description of a possible scheme of adding lookups (and any other challenge arguments) to Groth16. It generated some traction and comments. Mainly I would like to thank Weikeng Chen who gave me some references on similar approaches (based on LegoSNARK), and confirmed that it should be possible to get rid of all interfacing between different argument systems (which loosely works similar to Pinoccio), instead using a singular Groth16-styled equation. It seems that it is, indeed, possible. I describe the protocol here, and provide a sketch of proof. Let's recall normal Groth16 protocol, first This turned out to be quite long, tbh. Can be skipped, but it makes sense to look on zero-knowledgness / soundness proofs here to make sense of my arguments for the UltraGroth.

4/5/2023yes (sort of) Huge thanks to Lúcás Meier @cronokirby for asking this question. UPDATE: Weikeng Chen has suggested an even simpler version of this approach, which is relative to it in a similar way to how Pinoccio is related to Groth16. This largely deprecates the "Pinoccio" approach. Brief explanation: instead of just separating private and public inputs as in normal Groth16, lets make a more refined separation of witness, by using few elements $\gamma_1, ..., \gamma_n$, and the elements $C_i$ belonging to a subset of a witness will be divided by $\gamma_i$. This will achieve the desired effect of witness commitment separation. So, more precisely, the question asked was "can R1CS support lookups". There is, indeed, a very simple and natural extension of the R1CS language which can support lookups and all sorts of other interesting things. Here, I will describe it, and suggest possible Groth16-style proof system for this language.

3/27/2023
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up