Building ZK passport-based voting

Oleksandr Kurbatov, Lasha Antadze

For a while, the dream of decentralized, anonymous voting felt illusory. Solutions like Semaphore are excellent for low-risk scenarios such as private DAO voting, but state elections and other high-risk scenarios require the anonymity, eligibility and uniqueness of voters to be totally guaranteed.

Historically, decentralized voting systems have only ever been able to guarantee two of these three properties at once. Rarimo’s Freedom Tool was the first solution to use passport-based voting to guarantee all three simultaneously.

In this article, we start with an exploration of the standard decentralized voting protocol and show the additional layers that can be added to create a fully robust system that overcomes the trade-offs between anonymity, eligibility and uniqueness.

We include the infrastructure used in Freedom Tool, and end with a proposal for a new kind of incognito passport-based protocol. This does away with single use-cases for country-specific passports and instead allows for an incognito network of varied characteristics that different applications can interact with.

Sections:

• Passport challenges
• Passport-based voting trilemma
• Centralized identity provider
• Centralized identity provider + usage of salt for blinding passport nullifier
• Centralized identity provider + random salt for each request + duplication proofs
• Several identity providers with duplicates and intersection proofs
• Incognito passport-based protocol
• Organising a voting scheme based on the passport infrastructure
• Security Considerations

Decentralized Voting Protocols

The typical flow of decentralized anonymous voting solutions is as follows:

1. There is an allowlist of voters. How this list is formed is always a concern, but both centralized and decentralized versions share the same voting process. Classic eligibility criteria includes wallet addresses, NFT ownership, etc.
2. Each user generates a pair of secret values: a Nullifier and a Secret, and sends a transaction with the Commitment to the registration tree. The eligibility is verified using the allowlist. If you're familiar with Tornado Cash or Semaphore, you’ll notice that the basic setup here is the same.Commitment = hash(Nullifier || Secret)
3. When the registration finishes, the user sends the transaction with the Nullifier, a proof of the valid Secret knowledge, and a proof of inclusion of the Commitment into the registration tree. The Nullifier and vote are recorded in the appropriate smart contract if the proofs are valid. The user can’t vote twice using the same Nullifier, so double-voting protection is achieved.

Such models run into problems in hostile or less deterministic environments such as when the eligibility criteria data is unavailable on-chain, or when the government tries to interfere in the voting process.

Rarimo’s FreedomTool solves this, firstly, by using government-issued documents a.k.a. passports, to generate Zero-Knowledge Proofs of eligibility.

Passport Types

Here and after, we use the term“passport” to describe biometric passports that uphold the Doc 9303 Machine Readable Travel Documents standard.

A passport simultaneously proves age, citizenship, and uniqueness. It is considered valid if it’s signed by a government authority and has not expired.

We can divide passports into 3 categories:

1. Passports that only support Basic Authentication (BA) methodsThese are no more than government-signed data packets. They aren’t protected from copying which means attackers can easily clone and use them. (no additional protection methods satisfy direct passport control).
2. Passports that support Active Authentication (AA)
3. These contain a cryptographic keypair for digital signatures. Verifiers can generate a request and ask the passport RFID chip to sign it, guaranteeing that the document being used is the original.
4. Passports that support Extended Authentication (EA) methodsThese passports can be read and verified only by certain eligible authorities. Authentication of the passport’s reader is performed by verifying the certificate branch.

The central challenge AA passports pose is that the signature is not deterministic. We can’t use this signature or its hash as a nullifier. This restricts the capacity to prove uniqueness.

The Great Trilemma

There are three key properties that a robust passport-based voting solution needs to guarantee. Guaranteeing one or two of them is easy, but guaranteeing all three simultaneously is incredibly difficult:

1. Eligibility. This property guarantees that the passport is legitimate and that the user’s age and citizenship meet the voting criteria. It can be achieved fairly easily by providing proof of the government’s signature and the relevant passport information.

a.Such proofs, however, cannot also support both anonymity and uniqueness at the same time:

I. To prove both Eligibility and Uniqueness, users can register with a commitment to the passport (its hash value or the public key (AA)) and then vote. While this allows the votes themselves to be anonymous, it does, however, allow governments to see who is registered in a pool (assuming that the government stores all passport data and can execute a dictionary attack). This can be risky for users, particularly if they are living in a regime.

II. To prove Eligibility and remain Anonymous, users can vote using only a ZK proof of passport eligibility No passport data is revealed, but Uniqueness is compromised: the user can vote an unlimited number of times.

2. Anonymity. This property guarantees that the voter’s identity remains completely hidden and untraceable. It can be achieved through ring signatures, the Semaphore protocol, and a range of other solutions. Such solutions, however, cannot also support both eligibility and uniqueness simultaneously. If users want to be Anonymous and Unique, they can vote without linking their passport data (for example, by using their wallet address), but such solutions undermine the vote’s legitimacy and legal weight, and don’t necessarily guarantee uniqueness either.

3. Uniqueness. This property guarantees that the user can vote only once. Again, it’s easy to implement using passport-bound nullifiers (open form) or traceable ring signatures (private form). a. It works only when eligibility and anonymity are not required (see all examples above).

The challenge then, is achieving all three properties at once. The solution depends on two things: firstly, how the voter allowlist is created and secondly, what data is required to vote and satisfy the aforementioned properties.

Let’s discuss potential approaches and evaluate their pros and cons.

Centralized Identity Provider

This approach requires having a designated identity provider. The identity provider collects the passport data (or proof of passport eligibility) and issues a Verifiable Credential to each user’s identity key (DID).

This approach is still limited: there is a high degree of centralized trust, but it does achieve provable uniqueness by using passport data as an identity nullifier.

Let’s start building a comparison table for the approaches we’re discussing:

Centralized identity provider + usage of salt for blinding passport nullifier

Now that uniqueness has been achieved, the next step should be ensuring true anonymity and eliminating any possibility of deducing which users have registered. Not even a government should be able to perform a dictionary attack.

This approach includes using the salt generated by the identity provider to blind the passport hash value.

The salt value can be committed before the registration, allowing proof that all nullifiers were derived using the same salt value.

So the passport nullifier transforms from hash(hash(passport) || event_id)) to hash(hash(passport) || salt || event_id)).

Without knowledge of the salt, external parties cannot identify which people were registered, but there is still another vulnerability. Suppose the government, knowing the user’s passport data, tries to re-register the data with the identity provider. In this case, they would receive the same nullifier and can then confirm if the original user has already registered.

We will resolve this issue in the next section, but for now, our comparison table looks like this:

Note there is a slightly improved model that can be used:

• The identity provider can (must) use TEE (trusted execution environment) which generates nullifiers based on the passport hash and salt. If the identity provider has no access to the environment and secrets it manages, it increases the security of the blinding process. When we mention some processes on the identity provider side below, you can assume that TEE is used.

Centralized identity provider + random salt for each request + duplication proofs

We can improve the previous scheme and prevent the government from tracking whether a user has registered in the pool. To do this, the identity provider must first, generate a new salt for each request (even if there are two requests with the same passport hash). Secondly, they must build out a relation table for passport hashes and the nullifiers that belong to them. This allows them to collect all the duplicates generated by a particular user.

This way, if the government tries registering with already registered passport data, it will receive a different nullifier and won’t be able to recognize it.

The more naive approach requires the identity provider to reveal how many duplicates exist after the registration is finished. The more advanced approach allows the identity to provider to prove that the number is correct. To do this, they can recursively generate the proof for each passport hash with all duplicates (nullifiers are the private inputs as well).

A new problem emerges; after recognizing duplicates in the registration tree, we can’t trace how many duplicates voted, only if all registered users voted. This makes this solution more suitable for protests and petitions where it matters how many users voted/signed without votes for different options. This is why the first version of FreedomTool is based on the above approach.

Most of the significant issues have been resolved, but there is still a lot of trust in identity providers.

Several identity providers with duplicates and intersection proofs

This model seeks to decentralize the identity provider role and provide an ability for users to decide which providers will be responsible for maintaining their anonymity, eligibility, and uniqueness.

The approach is similar to the previous one, but the key difference is that we have several trusted identity providers. Each receives requests from users and generates nullifiers based on their random salt. The key challenge this introduces is that duplicates can now exist not only within one identity provider state but also between different providers.

The solution requires an additional round-based protocol based on FHE that allows identity providers to exchange their encrypted database states with each other and calculate the number of intersections without revealing nullifiers of other users.

It’s a pretty complex approach that requires significant resources from the identity provider, but it reduces trust in a centralized party.

This approach is better but it’s still not perfect: too many trust assumptions remain. To solve this issue, we need a fundamentally new and different voting infrastructure.

Incognito Passport-based protocol

This solution is compeletely different from all the approaches above. It proposes a generalized ID infrastructure that publicly associates the user’s passport with an identity key and then reuses this association for all required cases (voting and others). This means that instead of single use cases for country-specific passports there is a huge active network of users with different characteristics that different applications can interact with.

There is no identity provider, only smart contract infrastructure that allows passport ownership to be proved and linked to keys for identity management.

To create the association between the passport and identity key:

1. The user generates the keypair sk_i, PK_i for identity management, and a blinder for personal data as blinder = Hash(sk_i).
2. If the user has a passport with AA, it signs the PK_i with it.a. If a passport doesn’t support this option, the user must include PK_i in the proof with knowledge of the passport data (for MITM protection).
3. The user generates proof that:a. For the AA case: the passport’s public key belongs to the passport signed by the government.b. For the BA case: the passport’s hash value is derived from the passport’s data groups and signed by the government:I. Under the hood, there is a check to ensure that the passport is signed by a key from the ICAO list. In a separate blog post, we will cover the principles of building PKI and keeping the ICAO list up to date on the blockchain.
4. For both cases, the user must calculate the commitment for their passport data DG_commit = Hash(DG1 || blinder) (to prove that some data is included in that in the future).
5. The user sends the transaction with the following data:a. PK_ib. PK_pass / hash(passport)c. sign(PK_i, PK_pass) verification on contract / PK_i as a circuits inputd. binding_proof => (hash(passport) → passport, DG1 → passport, DG_commit = Hash(DG1 || blinder), iss_signature is valid)
6. This way, a specific passport is connected with identity keys PK_i :: PK_pass or PK_i :: hash(passport) at the level of identity infrastructure (we propose to put it as a tree leaf in a Sparse Merkle Tree).

Additionally, the user can define how this association will be managed: such as processes like revocation, reassigning the private identity key, etc. By default, it’s controlled by sk_i, but additional options like multi-sig or account abstraction are available.

Organising a voting scheme based on an Incognito Passport-based Protocol

When the aforementioned passport protocol is created — it allows for organizing different events and defining allowance criteria for participation. In the case of voting, we have an application with the identifier ID_e (can be a smart contract address) and define criteria as:

• The valid passport (signed and not expired)
• Nationality
• Age

In this case, the user generates the following proof:

1. pub_signalsa. nullifier = hash(sk_i || ID_e) or nullifier = hash(sig(ID_e, sk_i))
b. ID Merkle Root
c. ID_e
2. priv_signals:a. sk_ib. DG1c. DG_commitd. SODe. PK_pass
3. circuit logic:a. PK_i → PK_i ID Merkle Treeb. DG_commit = Hash(DG1 || blinder)c. sig_ver(sig, ID_e, PK_i) == truee. hash(sk_i || ID_e) == nullifierf. AGE, Nationality → DG1g. Expiration < Requiredh. PK_pass → SOD (if AA is available)

This proof comes together with Commitment to registration in the voting pool. If the proof is correct, the user commitment is added to the tree, and then the standard semaphore-based protocol works.

Security Considerations

• If the government registers the passport data before the user, the user loses control over their passport.
• We believe that in the future, a ZKML solution will allow us to verify that the real passport owner is attempting to register or perform other actions with the passport
• This ZKML will compare a passport photo sample with a real-time vector of features generated by the person
• Proof generation must be performed on the user’s device, or it won’t be real “zero-knowledge”. This is a CPU-heavy task that has to be optimized so that it can run reasonably fast, even on budget smartphones.
• The government can see all passports associated with identity keys but can’t check how they interacted (registered, voted, etc.)
• If a small quorum of other participants with the same criteria was registered, it’s risky to participate in any actions. The bigger the quorum — the better.
• Governments can issue fake passports to skew the voting results.
• A social graph of historic actions could resolve this problem. Registered users can interact with and attest to each other (confirm ownership and liveness). Creating these events over time allows for the introduction of a new model where the final results depend not only on the voters but also on their social weight.

Conclusion

As well as helping to revolutionize the way that citizens vote, poll and protest, an incognito passport-based protocol would crack open new possibilities for attestations, airdrops and social DAOs.

Despite the list of challenges listed in the Security Considerations Section that the approach currently faces, the development vector looks promising and provides properties we couldn’t reach before.

Privacy is freedom and as this technology continues to evolve, we can look forward to an internet that embeds privacy across a greater range of critical online interactions.

Follow Rarimo on X