ZK interaction with frames with FID replay protection

[Hmac512]

ZK frame interaction with FID replay protection

Motivation

[EulerLagrange on Warpcast](https://warpcast.com/eulerlagrange.eth/0xea60f72d)

ZK interaction with frames with become increasingly important as the protocol scales. Anonymous frame use is also a potential way the like/comment/recast to use frame phenomenon can be broken. Some existing frames may be broken if the user is anonymous, but this can be easily corrected for.

Dan hinted on the Bankless podcast that Merkle with add payments into Warpcast frames at some point. Payments through frames can enable malicious pricing since the frame can lookup a user’s wallet activity on-chain. They can also use an LLM to look for statements like “I have lots of warps” or “I just sold my OG Legacy NFT”.

Overview of problem

ZKPs for Farcaster signers is a lot more difficult than writing a circuit for Eddsa. Altogether, you may need:

1. ZKP of Valid signature,
2. ZKP that signature was generated by a key that is valid for a FID,
3. ZKP that the FID hasn’t interacted with the frame before (replay protection),
4. Minimizing trust assumptions (ie don’t have a trusted entity sign attestations of FID/Signer),
5. ZKP must be very fast to generate client side.

The totality of all these things is actually quite difficult to implement. Without the constraint of fast proving times, there are many ways to approach this problem. EVM state/storage proofs can be considered, as well as hubs indexing signers into a more zk-friendly structure.

We may also want to minimize the changes to the hubs that is required, as it will require a lot more thinking/debate to make sure the tradeoffs are worth it.

Here are the goals that this FIP is optimizing around:

1. Fast client-side proofs,
2. Minimal changes to hub,
3. Optimize for off-hub use (frames and not casts/likes)
4. No compromise on frame use cases that are supported,
5. Sufficiently decentralized (to match the trust assumption of the farcaster protocol).

Changes to the Farcaster contract

In order to get FID replay protection, we propose adding a new key type and key type validator to the KeyRegistry contract. The validator’s job is to enforce that there is only one key for that type for each FID. This rule allows us to get fid replay protection in a fairly simple way.

    function validate(
        uint256 fid, /* userFid */
        bytes memory key,
        bytes calldata keyRequestBytes
    ) external view returns (bool) {
        KeyRequestMetadata memory metadata = abi.decode(keyRequestBytes, (KeyRequestMetadata));

        if (idRegistry.idOf(metadata.requestSigner) != metadata.requestFid) {
            return false;
        }
        if (block.timestamp > metadata.deadline) return false;

        if (getCountOfKeyType(metadata.requestFid) != 0) return false;

        // Rest of the logic
    }

Note that this new key type is purely for off-hub use. The hubs will NOT need to verify and store messages of this type.

As for details of the actual key type, we propose to use the Semaphore system designed and developed by the PSE team of the Ethereum Foundation ([What Is Semaphore? | Semaphore](https://docs.semaphore.pse.dev/)).

The semaphore system has done a lot of good work around anonymous voting that can be repurposed for this use case. It’s also a simple enough system where client-side proofs are very fast relative to things like a ZK eddsa verification.

Remaining problem

There is still an issue here that derives from the KeyRegistry contract not calling the validator when a key is revoked. As such, as the proposal is now there is no way to know if a semaphore identity has been revoked in the KeyRegistry contract.

How to solve the key revocation issue

We can have an off-chain system index revoked keys of this new type into a sparse merkle tree. Sparse Merkle trees are the best choice because:

1. Support non-inclusion proofs
2. Fast to update (compared to binary balanced)

To connect everything together, when you want to use a zkFid identity (semaphore) into interact with a frame, you provide two things:

1. Valid semaphore proof
2. Non-inclusion proof of key revocation state

A non-inclusion proof for a Merkle tree is better explained with a 1D analogy. Imagine you had a sorted array of integers, and you wanted to check if 5 is in the array. If I prove to you 4 and 6 are right next to each other, then it is a proof of the same. So a non-inclusion proof is simply two inclusion proofs. You need some kind of ordering in your Merkle-tree to support non-inclusion proofs. A sparse merkle tree is just a clever construction that makes it fast to update.

This gets us all the properties we set out to achieve in the earlier sections.

If this FIP is adopted, then the sparse merkle tree can be added to hubs to index. Although this is not a requirement to getting started. Potentially a frame can index the revocation tree instead of trusting someone else.

[Hmac512]

A few variations that can be debated:

• Instead of indexing revoked keys, you index active ones to reduce the proof to a single inclusion proof.
• Each zk-identity can have a short expiration so a new one has to be made frequently

[pavlovdog]

Copied here the comments from the discussion on Farcaster.

Sergey Potekhin - Can you provide more details about how the Semaphore is used here? Also, there is only one key for each FID which may become a problem considering that we have a decentralized protocol with a variety of clients. What if we associate a new key with a signer instead of an FID?

EulerLagrange - I’ll write an answer to first question in the morning.

As for the second, each fid can have multiple signers. So associating a semaphore identity to the signer would allow for a fid to have multiple semaphore identities.

In an anonymous poll, a fid could vote multiple times undetected.

The idea is you want your zkFid to inherit the same Sybil resistance as the fid system.

One semaphore identity per fid is the only way I can think of it.

To recover multiple client support, you can make a new contract that lets a semaphore identity add multiple signers.

I feel like we should start simple though.

The semaphore identity is pretty straightforward.

The identity consists of a trapdoor and nullifier (private key), and the key on-chain is just the hash of the two instead of a eddsa public key.

To use the identity you do a PoK ZKP.

Continuing on. Semaphore identity is basically hashing a secret, and “signatures” of the identity is a PoK that you know the secret.

The idea is the validator will insert the identity into a sparse merkle tree, so using the semaphore identity is a PoK, inclusion proof, and non-inclusion of revocation

Sergey Potekhin - Awesome, thank you for the explanation! I was thinking is there a way to use existing keys instead of adding a new one? By somehow deriving all the properties from the signer Ed key. As I see in the current scheme each user needs to add a new key (=send a transaction), which seems like a lot of friction to me.

EulerLagrange - Using existing keys is possible. Simplest approach is to index them into a sparse merkle tree offchain similar to the revocation tree in my proposal.

Might still need a new key type for fid replay protection.

My concern here is interacting with a frame w/ zk eddsa will be a lot slower and use a lot of power.
Also, maybe write these comments in the GitHub? Haha so we have it in one place.

Open to exploring alternatives.

This particular proposal was optimizing for client side proof speed.
I know from convos with D+V this can’t be prioritized internally.

So we can explore a few approaches and compare the implementations.

That way it’s ready for merkle when they need it :)

avi- although replay protection is important but this restriction (one key per fid) would mean user cannot use multiple privacy clients at the same time?

also app developers would have to compete for users in a zero sum way which kinda sucks

EulerLagrange - There are a few ways around this but they introduce complexity.

1. Extend semaphore identity commitment for multiple identities (multiple clients)

2. Instead of trapdoor/nullifier, you add a public key. Then each client gets a trapdoor/nullifier signed by the private key