Nym's Coconut Credentials - An Overview

Nym has two core technologies.

The first is a mixnet that protects transport data and metadata. Mixnets work against even very strong adversaries who may want to deanonymize users by following their TCP/IP packets as they transit the internet.

The Nym mixnet fulfils the promise of end-to-end unlinkability – not only can it protect the content of messages, it also hides who is communicating with who, and the routes taken by individual packets.

The second technology is a selective disclosure credential. We have based the Nym credential on Coconut, a design funded by Decode, a project initiated by the European Union’s Horizon 2020 innovation program to “build a trustworthy and privacy-aware digital society”.

Coconut is a signature scheme. All signature schemes consist of three algorithms:

1. keygen
2. verify
3. sign

A user must be able to generate public/private keypairs with which to do the signing, so that they are able to sign a piece of cleartext using a private key. Later, anyone with the public key of the signer should be able to verify that the signature is valid. All signature schemes work like this – RSA, DSA, and newer ones like ED25519.

Coconut extends these basic three functions with several more. Understanding the extra functions is the key to understanding what you can build with it. Let’s see what additional algorithms get added.

4. Blind Issuance

David Chaum invented blind signatures in the 1980s. They have some additional properties and functions to those above.

There is still a keygen. There is also an algorithm which allows someone who doesn’t have the secret signing key to create a blinded message: someone can take a piece of cleartext, and turn it into gobbledygook which can then be signed by a signer who has the secret key.

The signature is passed back to whoever created the message, still blinded. This signature can then be unblinded by that person. It’s now equivalent to a valid signature on the original cleartext message. Once it’s been unblinded, the signer has no way of linking the unblinded message with the signature on the blinded message.

Let’s use as an example a simple, fictional e-cash scheme. Here are the steps that I might undertake:

• I create a message saying I have one dollar, in cleartext.
• I blind it using a blind-signature algorithm. The cleartext message turns into gobbledygook.
• I send the blinded message to the bank along with a dollar.
• The bank signs it, saying it attests I have a dollar, and returns the signature to me.
• I unblind the signature, which de-links it from the signature I got back from the bank. This is the crucial step that ensures my privacy.
• I now have an anonymous bearer token which attests I own a dollar.

The bearer token cannot be linked back to what the bank gave me, but its validity can be verified by anyone with the bank’s public key.

This process is blind issuance: create cleartext, blind, send to signer, sign, return to creator, unblind, use. There is a problem with blind issuance: the signer has no clue what they’re signing.

So if you’re the bank, you get some gobbledygook. How does the bank know it doesn’t say “I have one million dollars”? It’s opaque. The standard solution is to use a zero-knowledge proof attesting that the message contains a dollar, but revealing nothing else (serial number, my identity, etc).

Coconut has this zero-knowledge proof ability, so it can do blind issuance. The zero-knowledge proof involved needs to be coded for each domain: a zero-knowledge proof for currency would need to differ from one for identity assertions, or one for anonymous voting protocols.

5. Re-randomisable Signatures

There’s another concept relating to signatures: a re-randomization. This type of signature has one additional algorithm: randomize(). It allows the user to take a signature, call randomize() on it, and generate a brand new signature that is valid for the same message. The new bitstring in the re-randomized signature is equivalent to the original signature but unlinkable to it.

What can this be used for?

You can show the signatures to different people and the people you show them to cannot figure out that the signatures are linked to each other, or to you. The underlying message in all cases is the same, so there’s no possibility of forgery. Essentially, we have multiple anonymized bearer tokens.

Coconut does re-randomization.

6. Selective Disclosure

Coconut also allows what’s called “selective disclosure”.

In a traditional signature scheme you sign the message, and later may verify it. The verifier must have the full message to verify it. What is selective disclosure?

Instead of needing to show the whole message to verify, selective disclosure allows us to show and verify only some parts of the message, keeping other parts of it private.

Let’s say you want to go to the pub, and need to prove your age at the door. You might present your passport, which has the following attributes:

• name
• nationality
• birthplace
• birthdate
• handwriting
• sex
• age
• photo

You go to the pub. The bouncer at the door doesn’t care about anything else, just your appearance and age.

Selective disclosure allows you to simulate this process. You sign a tuple of all the fields in the passport and when it comes to verify, the verifier can verify only some attributes. The verifier here is public, and could be anyone who (a) knows the public key of the passport authority, and (b) sees the signature from the passport authority.

So we have three parties:

1. passport authority
2. subject (you)
3. relying party (bouncer)

You can choose to selectively disclose some, or all attributes in the signed message. Selective disclosure can be applied to “normal” signature schemes (no blinding, no re-randomization). That is, you can get a signed message from an authority and disclose attributes selectively. This provides privacy against the relying party (bouncer) by not revealing more information than necessary. However, if you go again to the same pub, or if the passport authority sees the message (which they signed), those parties can link signature and verification and thus break the subject’s privacy.

But if we combine blinded credentials, re-randomizable signatures, and selective disclosure, we can protect the user’s privacy against multiple “shows” (uses of the credential) at the pub. The bouncer will think it’s always the first time you’ve been there, and the passport authority has no way of linking the blinded credentials you’re using to what they issued.

The idea that you can selectively disclose by showing some attributes and not others is a simplification, it’s more powerful than that. Instead of revealing your age directly, you can associate a zero-knowledge proof that asserts “I’m over 18” without revealing your actual age.

7. Threshold Issuance

Blind signatures, re-randomisable credentials and selective disclosure have all existed in the cryptography literature for years, or even decades. As we’ve seen, stringing them together has some interesting properties, but until now, all of these schemes had one thing in common: signing was always centralized.

The major advance in the Coconut paper is threshold issuance. Instead of having one authority doing the signing, Coconut has multiple authorities that sign (either all together, or as a threshold signature). This makes it possible to issue Coconut-based signatures in a decentralized context, and gain all of the privacy goodness that was previously only available in centarlised systems.

In conclusion

To recap, the Nym validators issue signatures based on a scheme called Coconut. All signature schemes have three algorithms:

1. keygen
2. verify
3. sign

Coconut has these, but adds:

4. blind issuance
5. re-randomisable signatures
6. selective disclosure
7. threshold issuance of signatures

These extra functions give very strong privacy guarantees for users of the scheme. Coconut can be used to add on-chain transaction privacy to existing blockchain systems such as Bitcoin, Ethereum, Libra or Cosmos.