Key chain

this is Yar's suggestion on ensuring that the key can not be sold it is not currently incorporated into the rest of the system; significant review might be required also likely applicable for normal MACI

Idea:

Let's organize private keys in chains of unknown length. As a simplest example: let $H$ be some hash function, and use $H(x)$ as a public key corresponding to a private key $x$. Then, let's say that $y$ dominates $x$ if we know such integer $k>0$ that $H^{\circ k}(y) = x$.

If we have provided the coercing party with a private key, it can not be known for sure whether this private key is dominated (whether it actually has a known preimage).

Then, let's give a dominating public key $y$ ability to "cancel" public key $x$ in our voting system (in a simplest version, this can even be used instead of keychanges). This not only gives non-coercibility, but also prevents key selling.

I.e., simplest (not very efficient) MACI-style voting system works like this: there is an initial registry of keys of height $0$; users send their (encrypted) transactions, which include signatures with keys of arbitrary non-negative height $k$ (possibly with zk-proof that the result of $k$ hashes gives the key from the registry to prevent DoS). Server nullifies all dominated votes and sums up all non-dominated.

Algorithm therefore becomes:

1. sort transaction list $T$ by a 2-wide register: ASC by user, DESC by height, DESC by timestamp
2. add padding element with idx 0
3. for transaction with index $i \in 1..N$ add field as follows $T[i].valid = (T[i].user != T[i - 1].user)$
4. aggregate "valid" transactions into voting result

This seems to not require security deposit.