Distributed Selective Deanonymization — An Approach To Compliant Privacy Protocols

Introduction

The privacy protocols on public blockchains have been a topic of interest for quite some time - due to good reasons as well as bad. One one hand, privacy is a fundamental right and a key component of financial freedom. On the other hand, privacy on public blockchains have attracted as venue for crypto money laundering - owing to absence of any anti-money laundering measures in place.

A few measures for compliance for privacy protocols have been attempted in the past - limits, sanctioned addresses, view-access etc. However, these measures have been largely ineffective due to the fact that all of it can either be circumvented easily or are voluntary.

I assume you have basic knowledge of how privacy protocols work on public blockchains.

Privacy Pools Design

Almost all of the privacy pools on public blockchains are designed with a similar architecture. You have a shielded account that has two keys - a spend key and view key. The funds are in the form of notes (like digital coins) with some value attached.

where is owner's public key and is a random element.

A shielded account (with spend public key ) can have multiple such notes, sum of which is the total balance of the account. The commitment of all notes ever created in the system is stored in a Merkle tree with root stored on-chain.

A nullifier of a note is a unique identifier of the note that is used to prevent double spending.

where is the index of the note commitment in the tree. The nullifier is recorded on-chain when the note is spent. If a note is spent again, the same nullifier is bound to be produced and the transaction will be rejected.

To spend a note, the owner proves is the owner by producing a valid signature and proving that:

• The commitment of note is in the tree (i.e. the note exists and is valid)
• The nullifier of note has not been recorded on-chain.
• The sum of the values of all notes being spent is equal to the sum of the values of all notes being created (i.e. no new money is created).

The receiver of the note scans the chain for new incoming notes and attempts to decrypt then using its view key. If the decryption is successful, the note is added to the receiver's shielded account balance. The receiver can then spend the note.

Setup

The goal of this compliance mechanism is to allow de-anonymization of the transactions by decrypting their notes without cooperation of the user and without giving decryption key to any single party.

Actors:

• Revoker Revoker is the actor that is responsible for requesting the decryption of notes involved in a transaction. The revoker is also the actor that will perform the actual decryption of notes as a final step and hence only it sees the decrypted notes.

• Guardians Guardians are the actors that make this mechanism distributed. The guardians hold the shares of a decryption key. This decryption key that whose shares are split among the guardians, decrypts a per-transaction key that actually decrypts the notes.

Setup

Before the system can be used, the guardian key shares need to generated and distributed among the anointed guardians. Although a centralize dealer can split and share secrets using the Shamir Secret Sharing scheme, something like Distributed Key Generation (DKG) might be a better approach for our setting.

Suppose we have guardians each with a key share . At least a of guardians need to cooperate to reconstruct the decryption key .

Revoker also has its own key .

El Gamal

We will use El Gamal encryption scheme to encrypt a key that is used to encrypt the notes. Here's how El Gamal works.

Encryption

Suppose is the encryption keypair. To encrypt a message with public key choose a random field element and calculate:

Our ciphertext is then:

Decryption

To decrypt using the private key to recover message , calculate:

It works because:

El Gamal With Aggregate Key

Now suppose we want an El Gamal based encryption scheme where a public key represents a group or multiparty and all parties need to contribute to decryption without revealing their private keys. It turns out to be pretty simple!

Let's take an example of two parties with keypairs and each. We represent the group's public key as:

As apparent from above the private key of the group is similarly the sum of private keys of all parties i.e. . Of course, we never require to be revealed.

Like before encryption remain same - group public key encrypts to yield ciphertext .

Now, to decrypt each party contributes the partial decryption share as:

After all is collected anyone can decrypt as:

It works because:

so the term eventually becomes similar to the decryption before.

Mechanism

Our mechanism works even for an involuntary subject i.e. de-anonymization or decryption of encrypted transaction data does not require user's coordination.

It works by requiring the user to encrypt the output notes with certain public key whose corresponding private is unknown to everyone. Lets start by defining the two actors or entities involved at compliance side:

Revoker

Revoker is the actor that is responsible for requesting the decryption of notes to a committee of "guardians" involved in a transaction. This transaction maybe involved in an illicit transaction or required by regulation to be decrypted. A revoker could be a regulatory body or some other law enforcement. Only a revoker sees the final decrypted notes.

We assume revoker has its own keypair used for encryption.

Guardians

Guardians are the actors that make this mechanism distributed. The guardians hold the shares of a decryption key. This decryption key is never revealed, only split shares are available to the guardians.

Lets say each of the guardians hold the key share . The private keys of each guardian is generate via the Distributed Key Generation (DKG) ceremony such that a minimum number () of key shares are required to reconstruct the guardian threshold decryption key . The corresponding public key is published publicly onchain.

Encryption Keys

For each transaction client generates a random key which is used to encrypt output notes of the transaction.

is itself encrypted with a public key with El Gamal encryption scheme we described above. However is not randomly generated. It instead is the aggregation of public keys of revoker and the guardian group. That is:

is stored publicly onchain for verifying correctness of encryptions via zk proof and for sake of user lookups.

As earlier discussed in our aggregated El Gamal encryption scheme, to decrypt the ciphertext to reveal , holders of private keys and will need to provide provide their decryption shares and .

Since revoker is a single party it can use its private key to simply calculate , after receiving from guardians and simply decrypt to get . With , revoker simply decrypts the notes of that transaction.

The case for guardians to calculate is not straightforward since guardians only hold key shares , not the actual private key . We will see it later.

Constructing The Compliant Transaction

With setup in place a client makes the private transactions compliant in this manner:

1. Encrypt output notes

The client encrypts the output notes of the transaction with randomly generated . Any encryption scheme may be used - however choosing a zk-friendly scheme will be favorable since this encryption will need to be proved for correctness in the zk proof.

2. Encrypt the note encryption key

The key itself is encrypted with public key . Since smart contract stores , it can enforce that chosen was indeed encrypted with by requiring the same in zk proof. Let's say the resulting ciphertext is:

3. Construct compliance proof

Now as we said earlier, enforce via proof that encryptions were performed correctly. Apart from transaction related inputs to circuit, the randomly chosen and must go as private input. The contract stores which goes as public input. Circuit can then constrain that both encryptions were done as intended.

4. Broadcast compliance data included transaction

Broadcast the transaction and make sure that ciphertext remain available should deanonymization be required in future. For example, it can be emitted as event data on EVM chains.

Decrypting The Compliant Transaction

Since notes are encrypted with key , decrypting the ciphertext to get effectively decrypts the transaction for us since output notes can be seen then.

To decrypt a transaction, the revoker fetches the transaction id and posts a signed request (signed with ), to a publicly auditable board. Anyone, including guardians, can verify the legitimacy of the revoker request.

Guardians then try to form a quorum of at least members to decide whether to allow revoker to decrypts by yielding their decryption shares. Should the guardians agree to decrypt, each of them provide their decryption share as:

And then send the shares to the revoker.

The revoker calculates decryption share from a quorum of guardians as:

where are the Lagrange coefficients for the quorum .

The revoker also calculates its own decryption share as:

The final decryption now works the same as we described for aggregated key El Gamal:

With recovered, the revoker simply decrypts the encrypted notes data.

If a decrypted note is revealed to any entity it can verify that a revoker indeed decrypted the correct note by calculating note commitment and checking it against onchain records for that commitment's existence.

Tracing The Transactions

Adopting this compliance mechanism assumes that decryption of a note (or any additional information) is sufficient to also reveal its nullifier . This might not be the case for every privacy protocol design, but also not hard to design to make it so. Since, different protocols may choose different nullifier functions, we proceed with this assumption rather than specifying a fixed nullifier function.

Suppose the note is decrypted in a transaction . Revoker then calculates the nullifier of this note and then scans the chain to find the transaction is revealed. Lets say this transaction is . Revoker then repeats the same process with to decrypt note created in and get the nullifier . And so on. This process repeats till some note in this chain of transactions gets fully withdrawn from the private pool and into the public.

For sake of simplicity only one note is shown per transaction. In reality, revoker decrypts multiple notes per transaction. Notes decrypted in one transaction can be spent and linked to multiple other transactions rather than just one as shown in image above. The trace will then be visually a more complex tree-like structure where multiple branches emerge from a node.

A friction point can be when the trace is too wide and/or long. In that case, revoker needs to constantly send requests to the guardians for decryption. A practical solution to this is to include a depth parameter in the request for deanonymization. Guardians then decide for once how deep in the trace should they be allowing the decryptions. After a positive decision an automated system can be run that automatically loops in revoker and guardians contributions to constantly decrypt notes across transactions until the specified depth is reached.