# Keychain - a fresh look

*Lev, Yar*

Roughly a year ago, me and Yar have suggested using a new public key schema to make MPC version of MACI feasible. In this text we revisit this idea, make few additions and describe trust assumptions required for it to function properly.

Here, we restrict ourselves to a non-MPC scenario (while these constructions are, indeed, applicable for MPC, we want to emphasize the advantages of using this system even in *non-MPC* case).

Throughout the text, we will use a hash function, which we will denote $h$.

We will assume that we have some readily available consumer-grade recursive zk-proof system - our original prototype was made for plonky2, but Nova will also likely work.

## A small note on general attacks on MACI and assumptions

In MACI, there is an important starting point that prevents key-selling at the "entrance" to the system - a cryptoeconomic stake, which can be taken by anyone controlling the original private key. As we will see, this is vulnerable (as much as any scheme starting from a private key and attempting to create some sort of non-coercible / undelegatable identity from it).

The attack works as follows:

1. Buyer (briber) and seller (bribed user) get into 2-MPC.
2. They collectively sign and process all data required to getting the persistent identity in MACI system (*without* revealing private key to the buyer).
3. They open this data to buyer.

As you can see, this is very general, and is, likely, uncounterable. Similarly, it is not possible to defend against coercing party monitoring your traffic in totality - it is required that user unconditionally posseses the key.

Therefore, we are required to somehow weaken our assumptions about the attacker. One option would be saying that it appears only after some time delay of a trusted *setup* procedure, second is saying that it is not really interested in purchasing identity wholesale, and only wants to sway a result of a particular voting.

We will adhere to this paradigm also - our scheme will have a sort of a trusted setup, after which coercion is impossible - provided it is done correctly.

The main value that we see in our approach is the fact that it

1. Removes the need for the persistent secret registry.
2. Splits the registration authority and tallying authority.

The 1st thing is very valuable for MPC (in which this secret registry would need to be permanently split between multiple non-cooperative parties). 2nd is important because that means that we can have a relatively secure initial registration phase, and then any party can use this system to run a MACI without a need to share registry / recreate it from scratch.

The primitive of keychain could even be used in other contexts where non-coercibility is desirable - but we don't have any concrete example except of voting.

## Revisit - what is keychain?

**Keychain** is a following structure:

1. A root value $r$.
2. A private key value $p$.
3. A length parameter $k$.

The corresponding public key $P$ is computed as follows: $P = h_{(p)}^k(r)$, where $h_{(p)}(x) = h(x,p)$.
*// we have had a slightly different schema before but this one seems to be much better against various attacks, including being harder to put into 2-MPC*

The owner of keychain can produce the following two kinds of proofs with relation to keychain:

1. Keychain structure proof: "for public $r$, private $k$ and $p$, the corresponding public key is $P$".
2. Digital signature of power $k' \leq k$: "for private $r'$, public $k'$ and private $p$, corresponding public key is $P$".

Note that in the second case we are actually proving that we know a (potentially) truncated keychain of height $k'$.

These two sorts of proof must have constant size, which is only implementable using recursive proof composition. Moreover, marginal computational cost of creating a proof for $k$ increased by $1$ must always be negligible for the user, and $k$ must be always potentially unbounded.

Our prototype on plonky2 shows that it is indeed possible, achieving the time of creation of a proof of a first kind to be ~ 5 minutes + k/170 seconds on author's machine (4 core, 3.5 GHz) for Poseidon hash, with $k$ bounded from above by (unrealistic) $2^{70}$ sequential hashings.

## A random root model.

Assume, for a moment, that user somehow obtained via some magical trusted process a keychain of user-chosen length, starting from a *random*, unknown to everyone but the user, root $r$.

Then, we claim that this keychain is unsellable in a following sense - there is no way for the seller to convince the buyer that they do not know an additional preimage to the keychain.

This allows to create the following simplified MACI scheme:

**(simplified MACI)**

1. There is a tallying authority, and users, with already registered keychains.
2. They send (encrypted, as in normal MACI) votes. Each vote is endowed with a zk-proof (checked in public to remove the strain from the server) that it is a *correctly encrypted message* of the form ```(uid, vote, power)```, where ```vote``` vector is correctly chosen for the corresponding ```uid```, and additionally user knows the keychain of length ```power``` for this user.
3. The server does the following work - decrypts all the votes, sorts by uid, chooses for each uid the message with highest power, and applies the corresponding vote. No additional checks are done, as they are encapsulated in the zk-proof created on user-side. This takes one stable sort (by pair ```(uid, power)```, and then application of a local predicate) - so relatively friendly for both MPC and zk.

A non-coercibility argument is that user (provided the tallying authority is non-cooperative) could always send a vote of higher power, thus nullifying the vote revealed to the attacker. There is a [simple game theoretic model](https://morgana-proofs.github.io/mpc-maci/master/chapter-5-random-ideas/game.html) developed by us in a previous iteration of this research.

## A structured root attack.

Sadly, the self-created keychains do not necessarily have the crucial property of having a random $r$. A seller might be incentivized to create a keychain with $r$ structured in a specific way (say, have a lot of leading zeroes). Then, proving this property, seller can efficiently convince buyer that they do not know the preimage of $r$.

Therefore, we propose the scheme involving a registry authority.

## Registration phase.

The registration phase works as follows:

1. User chooses a private key $p$.
2. The registry authority sends to user a random root $r$ (say, signing it with designated verifier signature, to ensure not creating a receipt).
3. User chooses $k$, and creates a keychain structure proof (private k, p, public r).
4. Registry authority validates this proof and registers the corresponding public key (say, submitting it into on-chain registry of public keys).

This interaction is assumed to be

1. Done by user, not a sort of a proxy actor registering instead of them (say, 2-MPC of user and attacker, or just attacker engaged into identity fraud from the start).
2. Traffic of the user is not logged by the potential adversary. This is sort of important, because adversary could just ask user to decrypt the logs of communication with the registry, and in particular, message 2 - which exposes the root.

2nd rules out the usage against state level adversaries, as these are clearly capable of monitoring traffic of an average user. Generally, both concerns can be ruled out by doing the registration phase in person while being covered with a thick layer of tinfoil - or some tradeoffs, likely similar to normal MACI with regards to the first transaction, need to be made.

## Trust assumptions.

Here we discuss what happens if various parties are malicious.

Malicious registry authority can register arbitrary keychains, including ones with structured roots. Therefore, it enables key-selling.

Malicious registry authority can not overpower a keychain from an honest user by itself - as it doesn't know the private key $p$.

Tallying authority of a particular voting being malicious still allows the vote selling. This is due to the reason that it can inform the buyer whether the vote was overpowered or not.

Tallying authority of a particular voting being malicious does not allow key-selling - i.e. adversary interested in another voting will not be able to profit from it.

## Distributing the trust - what is MPC-able and how much?

It is possible (and likely desirable) to have multiple registry authorities. The voting, then, would require overpowering in k of n signatures. This can reduce trust in registry authorities significantly (moreover, they can even validate non-intersecting domains of interest, like "having a twitter account" or "having your iris scanned by Sam Altmann").

This does not require MPC and non-interactive. Individual registry can also be replaced by MPC if it is needed, as its only job is to ouput a random string, and then validate a zk-proof against it.

Notable caveat is that a proof must be MPC-friendly to be validated inside of MPC - groth16 or (kzg) plonk will suffice, but anything FRI-based is no-go.

Considering tallying authority, the procedure itself is also notably MPC friendly, with bulk consisting of a decryption of each vote (easy for El Gamal scheme), and then a single oblivious sort.

Moreover, it even produces a witness for a collaborative snark, so the proof for external auditing can still be produced.

In general, it is much easier to have MPC for tallying without a permanent private registry, as there are typically multiple parties (beneficiaries of the voting round) engaged in a zero-sum game - therefore, they are incentivized to run the infra.

## Privacy even if tallying authority is malicious?

There were some discussions whether MACI could preserve the privacy for honest end-users even if the tallying authority is malicious.

Our scheme is trivially combinable with Semaphore, which can just be encapsulated into the user-side proof:

instead of providing the proof that we have sent message ``enc_{P}(uid,vote,power)``, use the nullifier ``null = h(uid, voting_id, private_key of the user)``, and add a Merkle proof to the structure proof of the vote.

## Heavy optimization for server-side.

Particularly interesting topic is minimizing the work of the tallying server - it seems that the current iteration of MACI already bottlenecks on it.

We recall an interesting approach which allows to minimize the work by the tallying authority:

Accompany the message ```enc(P, msg)``` encrypted by a public key of the tallying authority by the following additional data:

1. KZG commitment to ``msg`` (offset by a random value not occuring in any previous transactions - this minimizes the probability that same offset will occur twice in a block, which would force us to re-send a transaction).
2. Encryption with ``P`` of a blinding factor involved in KZG commitment.
3. Proof that the aforementioned data is formed correctly.

This, likely, requires some relatively heavy computation by user, so this needs to be evaluated in light of recent progress in non-native MSMs / recursive computation.

Then, the work by server becomes much smaller - while it still needs to decrypt ``msg``, it does not need to create a proof of this decryption, as it is already handed KZG commitments to naked unencrypted messages that it can add directly and use as a PlonK column.

This makes it scalable, potentially, to millions of users.