Verifiable Verifications

Bluesky recently introduced a new form of verification . It’s a social version of the familiar notion of a blue check, in a way that is architecturally aligned with Bluesky and its underlying protocol ATProto . This allows notable accounts and accounts that are related to trusted organizations to be verified as authentic.

In order to support that, the Bluesky app has a list of a few trusted verifiers - the Bluesky team itself, NY times, Wired and The Athletic. Each of these organizations can attest that another user is authentic. They do so by adding records on their own Personal Data Server (PDS), which stores all the records related to their activity in Bluesky and potentially a wider ATProto ecosystem, the Atmosphere. Steve Klabnik has a good post that describes how it fits within the protocol design considerations. This form of attestation is simple and decentralized in spirit - while the official Bluesky has this initial list of trusted verifiers, other views of the same social Bluesky records can ignore these or trust other verifiers.

In this short post, I’d liked to explore potential ways this mechanism can be extended to more forms of verification, and especially those that are automated and verifiable - verifications that contain non-interactive cryptographic evidence rather than just attestations.

Recap on current verification

As Steve describes in his post , verification is done by the attester adding a record of the following form to their PDS:

The record of type app.bsky.graph.verification describes the verified identity, including some other details like when they were verified, what’s their handle and their name.

Design goals

A couple of very simple ones:

The new form of verification should be easy to, at least partially, integrate into apps that support the existing form

Apps that would like to perform full verification have all the cryptographic evidence necessary to do so in a way that is compatible with ATProto

Non-interactive verification using ZK Email

As a concrete example, let’s look at ZK Email . It’s an open source project that uses zero knowledge proofs about the content of emails. This is possible since modern email infrastructure uses DKIM (DomainKeys Identified Mail), where sent emails contains signatures on the headers and body.

This allows us to create some fun examples of verified sets of users:

Prove that Kobi sent you an email

Prove that your were a speaker in a conference

Prove that you have a valid Instagram accounts

The above all contain links of examples from the ZK Email Registry of how you can use regex on the email contents to achieve these properties. The nice thing about this method is that you don’t have to expose the entire email. Because the proofs are zero-knowledge, you can just prove that the email satisfies the desired property without revealing the rest of it, containing potentially sensitive data. Note that the examples above require you to associate your email with your Bluesky identity somehow.

First method - new schema

A design that ignores the first requirement is just adding new records. We could think of something of the following form:

The record is of a new type that identifies it as a ZK Email verification, the blueprint of what kind of data is used and extracted from the email in the proof, similar details to the current form of verification and, finally, a proof.

This answers point 2, but requires app views to adopt both a new schema and a new, relatively complex, method to verify the attestations.

It would be cool if we can somehow combine the existing approach with a new one while moving in the trust tradeoff space.

Second method - optimistic verification

Another approach we could take is the following:

Use a new schema as in the first method. Let’s call this a ZK attestation.

Additionally, create another attestation as in the existing verification mechanism. Let’s call it a signature attestation.

This would mean that you have two kinds of attestations for the same identity. The advantage of going in this direction is that apps that want a lightweight version of the attestation can use the existing signature-based attestation for verification, and other apps can do full verification.

The challenge is that there can be disagreements between the two kinds if the attester is compromised. You could just trust the attester that they verified the ZK attestation and only created a signature attestation. Another way to solve it is to take a page from the dispute window playbook - when a signature attestation is added, you don’t accept it immediately. Instead, you wait a few days to deem it valid. If there are disagreements between the methods, on any attestation for any user, the attester will be considered compromised by the community and the app developers will take action to remove it. Otherwise, if the days have passed and it hasn’t happened, you’re good.

This creates a new challenge - you now have to trust the timestamps in the signature attestations, where previously they were arbitrary. This is a non-trivial problem, but it’s at least much more contained. This is what’s done for credit card disputes, for example. It’s also a common mechanism in the blockchain space, where states of some chains (specifically, optimistic rollups) are deemed valid only after some time has passed.

There are a few approaches for time stamping that are possible:

Have a generic timestamping attester that can service many different applications, not just signature attestation. This can be treated like a trusted verifier.

Do the same with a few entities, to increase the trust in the mechanism. When doing this, instead of agreeing on a very precise timestamp, you can agree on a day.

Use an existing blockchain that supports easy verification (also known as light clients) and submit data there. The timestamp the transaction was included in the chain will be the one you will start counting from.

This requires the app to integrate one of this three.

Third method - TEE-powered attestation

Another point in the space to explore is Trusted Execution Environments. A TEE consists of hardware and software that guarantee what code has been run in the machine. Given that, we could create the following TEE program:

When first booted, it generates a signature key pair. It never exposes the private key and doesn’t provide an API to retrieve it. This will be the key pair that is used for signature attestations.

The program has an API method to create a signature attestation given a ZK attestation. It only returns a signature attestation if the ZK attestation has been verified successfully.

The TEE security mechanism provides you with the evidence necessary to know that this is the structure of the program.

Since the private key is never exposed, this enhances our security, removes the latency introduced in the second method and doesn’t require any further interaction with other services, like a timestamping service. It does require you to verify the evidence at least once, so that you know the correct program and key pair are used. Since this is an infrequent operation, it can be done by several members of the community and then the signature key pair can be included in the app for verification.

The TEE method can be used in different places - a timestamping service or API-checking service for other kinds of verification, for example.

This is really nice but not all is roses, since TEEs are hard to build and there has been breaches in the past. That said, this is an area that is continuously being worked on and is deployed in practice. Also, if you trust the attester’s server, you don’t need the extra security guarantees.

Side note - there are also cryptographic methods that theoretically can achieve similar guarantees, but they’re not practical yet. One of those is called indistinguishability obfuscation (trying saying that three time quickly, or even write it tbh).

Epilogue

I’m really not sure what is the right method to use or even if it’s one of the above. I also don’t have a concrete proposal, there’s a lot more work to define the precise details here 🙂 Just wanted to share some ideas here of different areas to explore, and mention some technologies that are less commonly used in these contexts.