FIP: multi-signatures

[pfletcherhill]

Problem and background

Right now, a Message is made up of three components:

• MessageData (the content of the message, including body, type, fid, network, timestamp)
• Hash (a hash of the data)
• Signature (a signature of the hash)

We use hashes to identify unique messages, so when a message is submitted to a hub, the hub checks whether it already has the hash and rejects the new message if it does. This approach is problematic when a message ends up being signed by multiple signers, because hubs may end up with different versions of the same message. Specifically, hubs store the first version of a message that they see and discard all subsequent versions.

This non-determinism causes problems when signers are removed. When a signer is removed, hubs revoke messages signed by that signer, because they are no longer valid. Since we don't know which version of a message hubs stored, we don't know which messages will be revoked due to a signer removal. And users can't change the signer associated with an existing message, so users have to wait for the signer’s messages to be revoked before they can be replaced with versions signed by another signer.

Ideally, we’d be able to prepare a user’s account for a signer change to avoid thrash (i.e. lots of messages being deleted and re-added in a short time period).

Proposal: Multi-signatures

Hubs should accommodate multiple signers for the same message and only revoke messages when all of their signatures have been invalidated. This change involves storing the components of a Message separately:

The benefits of this approach are:

1. Hubs will end up with the same state, if they’ve seen the same messages, regardless of the order in which multiple versions of the same message were submitted
2. Users can prepare for signer changes to minimize thrash by submitting re-signed versions of the messages they want to preserve before removing a signer

The downsides are:

1. Hubs end up storing more data per message (each signature/signer blob is 97 bytes—32 for the signer, 64 for the signature, 1 for the scheme). With 10 million users, each with 5,000 messages, signatures would take up between 4.85 and 485 TB of space on the network, because a user can have up to 100 signers.

Examples and other notes

Example 1: SignerRemove

Steps:

• Custody signer submits a SignerAdd adding Eddsa signer X
• Signer X signs and submits a bunch of casts and reactions
• User wants to remove signer X but preserve their casts (but not reactions), so the custody signer submits a new SignerAdd adding Eddsa signer Y
• Signer Y re-signs and submits the casts signed by signer X
• Custody signer submits a SignerRemove removing signer X
• Signer X is removed, all reactions are removed because the only signatures they have are from signer X, and all the casts remain because they still have another valid signature from signer Y

Example 2: Custody address transfer

Steps:

• Custody signer A owns an fid
• Custody signer A submits two SignerAdd messages for signers X and Y
• Signers X and Y both submit casts and reactions
• The user transfers their fid to custody signer B
• Custody signer B submits a SignerAdd adding signer X but does not add one for signer Y
• After a one hour grace period, the hub revokes the SignerAdd adding signer Y because the only signature was from custody signer A. Signer X is unaffected because it still has a signature from custody signer B.

Custody signer grace period

We should institute a grace period (likely one hour) after an fid transfer occurs before revoking messages related to that transfer. We need a grace period for custody signers but not delegate signers. The reason for the difference is that when you plan on removing a delegate signer, you can add a new delegate signer and re-sign messages with the new signer before removing the old one. But since an fid can only have one custody signer at a time, you can’t re-sign messages until you’ve done the transfer. So we need a grace period after the transfer occurs for the re-signing to happen.

gRPC return values

When users query the hub for messages, the return value should include all signatures with a data structure like this:

message Signature {
  bytes signature = 1; // Signature of the hash digest
  SignatureScheme signature_scheme = 2; // Signature scheme that produced the signature
  bytes signer = 3; // Public key or address of the key pair that produced the signature
}

message Message {
  MessageData data = 1;
  bytes hash = 2;
  HashScheme hash_scheme = 3;
  repeated Signature signatures = 4;
}

[deodad]

Could hubs maintain a look up table of signers for an fid and only store the pointer on each message?

[pfletcherhill]

If I understand what you're suggesting, that's similar to how I expect to implement this. We store MessageData in one place and then store signatures independently to avoid duplicating data. We only revoke messages when there are no signatures left for that message, and we return all signatures when the message is queried.

[varunsrin]

I'm supportive of this and think its worth fleshing out into a draft, per FIP-0. The part I want to make sure we get consensus on with hub runners is the migration plan and what actions that people running hubs and people reading from hubs need to take.

With 10 million users, each with 5,000 messages, signatures would take up between 4.85 and 485 TB of space on the network, because a user can have up to 100 signers.

Does this estimate assume that each message has 100 signatures?

[peterferguson]

I don't think this proposal really covers the following use-case but when reading the title it is what I thought of. Multi-sig Farcaster accounts. I don't know if (in the permission-less future of) Farcaster is considering SCA owners of fids as separate entities to EOAs (or even if it should)

The main use-case I see is DAO/company Farcaster accounts. In this example you want multiple people to have the permission to sign for casts & reactions etc, but these are probably low enough stakes to not need a full voting mechanism to decide on them.

Company accounts are already becoming a thing on Farcaster but having to share private keys of accounts is pretty sub-par UX. At Forum, we are building group chats where the members can have fids as identities and so also having an account to represent the chat, where each member can control it is a compelling use-case imo.

[varunsrin]

multi-signatures are no longer needed if the on-chain signers fip passes