XIP-68: Automated Fork Recovery

XIPs (XMTP Improvement Proposals) XIP Stage 1: Drafts
1

XIP: Automated Fork Recovery

Discussion of previous iterations at Fork recovery design sketch · Issue #2062 · xmtp/libxmtp · GitHub

Overview

The MLS protocol requires all group members to maintain and advance the same encryption state as incoming commits update the group, with deviations resulting in parallel ‘forks’ of the group where subsets of the group’s members are unable to communicate with each other. Forks may be caused by inconsistencies in commit processing between client versions, bugs in message processing logic, and concurrency issues both locally on the client as well as due to distributed systems issues. More information on forks can be found here.

The best way to address forks is to prevent them, via robust system design and comprehensive testing. However, in the event that the root cause of a fork was not discovered beforehand, fork recovery provides an ‘insurance plan’ that can give blanket coverage over a wide variety of issues.

The following describes an intuition for how this may be done.

  1. All installations maintain a local log containing the success and failure status of each commit they applied, as well as the resulting encryption state.
  2. Superadmin installations will append each local commit result to the group’s remote commit log. The remote commit log may contain duplicates or conflicting updates from multiple installations. Readers follow the rule of ‘first write wins’, reading the log sequentially and discarding conflicting updates.
  3. When any installation discovers that their local commit log conflicts with the remote commit log, they will send a ‘readd request’ to all superadmin installations as well as their own inbox.
  4. Any recipient of a ‘readd request’ will verify that their own state matches the remote commit log, before removing and readding the member to their fork.

Commit Log

As a pre-requisite for fork detection, there must be accurate tracking of the commit state. Here we introduce two concepts, the local commit log and the remote commit log.

Local Commit Log

All installations must maintain a local commit log for each group they are a member of, the following is an example schema:

CREATE TABLE local_commit_log (
    -- A locally assigned ID for the local log entry
    "rowid" INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "group_id" BLOB NOT NULL,
    -- The sequence ID of the commit being applied
    -- For welcomes, this is the sequence ID of the commit that spawned the welcome
    -- For group creation, this is 0
    "commit_sequence_id" BIGINT NOT NULL,
    -- The encryption state of the group before the commit was applied
    "last_epoch_authenticator" BLOB NOT NULL,
    -- Whether the commit was successfully applied or not
    "commit_result" INT NOT NULL,
    -- The state after the commit was applied, or the existing state otherwise
    "applied_epoch_number" BIGINT NOT NULL,
    "applied_epoch_authenticator" BLOB NOT NULL,
);

The epoch_authenticator is derived from the epoch secret and uniquely identifies the group encryption state after the commit was applied, but is not itself sensitive information. It is defined in the MLS protocol spec.

Each time the local group state has been transformed, or the cursor has been advanced past a failed commit, an entry must be added to the local commit log. Note that the commit log is permitted to have duplicate entries, with the same server sequence_id but different values for the log_id field, as well as out-of-order entries. This would indicate bugs in the client’s processing logic.

Group creation, device sync restores, and welcomes without a corresponding cursor may be stored with a commit_sequence_id of 0. These entries may be useful for local debugging purposes even if they cannot be compared remotely.

Remote Commit Log

For each group, all superadmin installations should additionally publish updates to a remote commit log. This can be performed asynchronously via a worker process, using the local commit log as a reference. Note that group creation operations (those with a commit_sequence_id of 0) should be omitted from the remote commit log.

enum CommitResult {
  COMMIT_RESULT_UNSPECIFIED = 0;
  COMMIT_RESULT_SUCCESS = 1;
  COMMIT_RESULT_WRONG_EPOCH = 2;
  COMMIT_RESULT_UNDECRYPTABLE = 3;
  COMMIT_RESULT_INVALID = 4;
}

message PlaintextCommitLogEntry {
  // The group_id of the group that the commit belongs to.
  bytes group_id = 1;
  // The sequence ID of the commit payload being validated.
  bytes commit_sequence_id = 2;
  // The encryption state before the commit was applied.
  bytes last_epoch_authenticator = 3;
  // Indicates whether the commit was successful, or why it failed.
  CommitResult commit_result = 4;
  // The epoch number after the commit was applied, or the existing state otherwise
  uint64 applied_epoch_number = 5;
  // The encryption state after the commit was applied, or the existing state otherwise
  bytes applied_epoch_authenticator = 6;
}

message CommitLogEntry {
  uint64 sequence_id = 1;
  bytes serialized_commit_log_entry = 2;
  xmtp.identity.associations.RecoverableEd25519Signature signature = 3;
}

message PublishCommitLogEntryRequest {
  bytes group_id = 1;
  bytes serialized_commit_log_entry = 2;
  xmtp.identity.associations.RecoverableEd25519Signature signature = 3;
}

service MlsApi {
  rpc PublishCommitLogEntry(PublishCommitLogEntryRequest) returns (google.protobuf.Empty) {
    option (google.api.http) = {
      post: "/mls/v1/publish-commit-log-entry"
      body: "*"
    };
  }
}

Signing

Remote commit log entries are signed but not encrypted. This avoids race conditions and complexity around ordering, stemming from the fact that the commit log can always be read, regardless of if a secret has been received or not.

The ‘consensus public key’ to verify all remote commit log entries for a given group is determined by the signing key of the first commit log entry. The first entry and signing key are typically generated by the group creator, but in the event that the creator does not do so (e.g. in groups created before the XIP), it is generated by the first superadmin to publish an entry. In the event that a race occurs and two entries are published with different keys, the first entry as determined by the server ordering determines the consensus public key, and the subsequent entry is invalid.

When a consensus public key is confirmed by reading the first entry of the log from the server, the installation that created the key may optionally update the mutable metadata of the group to share the private key with the group, so that other group members may publish entries. Note the group creator may choose to pre-seed this key on the mutable metadata during group creation to save an additional commit.

Current implementation details in libxmtp can be found in this pull request, but do not need to be followed in other implementations.

Fork Detection

Parsing the remote commit log

All installations should run a worker process which periodically pulls updates from the remote commit log, and stores them in a local cache, for example in a table named remote_commit_log.

Installations should store entries sequentially starting from the beginning of the remote commit log, skipping over entries for which any of the following apply:

  1. The public key of the signature does not match the consensus public key for the commit log, if one exists.
  2. The signature does not correctly verify the serialized entry with the specified public key.
  3. The entry fails to deserialize, or any field of the deserialized entry is NULL.
  4. The group_id of the entry does not match the requested group_id.
  5. The commit_sequence_id of the entry is <= 0.
  6. The commit_sequence_id of the entry is not greater than the most recently stored entry, if one exists.
  7. The last_epoch_authenticator does not match the applied_epoch_authenticatorof the most recently stored entry, if one exists.
  8. The entry has a CommitResult of COMMIT_RESULT_APPLIED, but the applied_epoch_number is not exactly 1 greater than the applied_epoch_number of the most recently stored entry, if one exists.
  9. The entry does not have a CommitResult of COMMIT_RESULT_APPLIED, but the applied_epoch_number and applied_epoch_authenticator do not match the most recently stored entry, if one exists.

The following is an example schema for the cache:

CREATE TABLE remote_commit_log (
    -- The sequence ID of the log entry on the server
    "log_sequence_id" BIGINT NOT NULL,
    "group_id" BLOB NOT NULL,
    -- The sequence ID of the commit being referenced
    "commit_sequence_id" BIGINT NOT NULL,
    -- Whether the commit was successfully applied or not
    -- 1 = Applied, all other values are failures matching the protobuf
    "commit_result" INT NOT NULL,
    -- The state after the commit was applied, or the existing state otherwise
    "applied_epoch_number" BIGINT NOT NULL,
    "applied_epoch_authenticator" BLOB NOT NULL
);

Comparing the local state with the remote state

Installations should also periodically determine if their current state matches the remote state:

  1. Iterate through the local_commit_log by rowid in descending order (from most recent to least recent). For each row:
    1. If the commit_sequence_id of the row is present in the cached remote commit log, compare the applied_epoch_authenticator of both entries, and return.
    2. If the row is a Welcome, stop iterating after the check has been applied - the installation has been readded, so earlier state should not be checked.
  2. If no matching commit_sequence_id has been found, then the result is indeterminate.

If a mismatching applied_epoch_authenticator is found, then the installation may be forked, and should perform the steps described in ‘Fork Recovery’.

Repeated checks can be cached, for example by the latest seen rowID from both logs.

Note that malicious group members may publish incorrect entries that cause the status of the group to incorrectly be reported as forked, so this cannot be treated as an absolute detection mechanism. In ‘Security’, we describe how this case is mitigated. In ‘Future Work’, we describe how this could be prevented in the future.

Fork Recovery

At a high level, installations that have detected they are in a forked state may send ‘readd requests’ to the superadmins of the group, who can reinitialize their state and readd them to the group.

Readd status

Each installation should maintain a local log of readds in progress, similar to the following:

CREATE TABLE readd_status (
    "group_id" BLOB NOT NULL,
    "inbox_id" TEXT NOT NULL,
    "installation_id" BLOB NOT NULL,
    "requested_at_sequence_id" BIGINT,
    "responded_at_sequence_id" BIGINT,
    PRIMARY KEY ("group_id", "inbox_id", "installation_id")
);

The requested_at_sequence_id refers to the latest sequence ID observed in the remote commit log when an installation requests a readd. The responded_at_sequence_id refers to the sequence ID of the commit which readded that installation.

In the following sections, when a readd_status is described as ‘awaiting response’, this means:

  • The requested_at_sequence_id is not NULL, and it is greater than or equal to the responded_at_sequence_id

In the following sections, whenever requested_at_sequence_id or responded_at_sequence_id is updated, this means:

  • The corresponding row should first be created if it does not exist, with default sequence ID values of NULL.
  • The value should only be updated if it is greater than the existing value.

Sending a readd request

When a fork is detected, the installation should send a readd request as a oneshot message. This is simply a Welcome message for a newly created, single-use MLS group that contains all superadmin installations (according to the group metadata on the local forked state).

The readd request contains the group ID, and the latest commit sequence ID according to the remote commit log.

message ReaddRequest {
  bytes group_id = 1;
  uint64 latest_commit_sequence_id = 2;
}

Once the request has been sent, the requested_at_sequence_id should be set to the latest_commit_sequence_id of the readd request.

Receiving a readd request

The following description assumes a state-driven client implementation, where a background worker processes requests from the readd_status table on a regular interval.

When an installation receives a readd request, the following steps must be taken:

  1. If the readd request is received in a group that the sender inbox has not consented to, the request is ignored.
  2. If the sender is not a member of the group, the request is ignored.
  3. The recipient updates the requested_at_sequence_id of the readd_status to the latest_commit_sequence_id on the readd request.

On a regular interval, the installation’s worker:

  1. Pulls all group_ids for which there exist readd_status rows from other installations that are ‘awaiting response’
  2. For each group_id:
    1. Sync the group
    2. If the current installation is no longer a consenting super admin of the group, readd_status rows from all other installations on the group are deleted.
    3. Fetch all ‘pending’ readd status rows from other installations in the group. For each remaining row:
      1. If the requester installation is no longer in the group’s ratchet tree, the readd_status row is deleted.
    4. Re-compute the group’s fork state:
      1. If the group is forked, readd_status rows from all other installations are deleted.
      2. If the local commit log is ahead of the remote commit log, the group is skipped.
    5. All remaining installations are added to a readd commit that is published to the group, which triggers welcomes to be sent. If the publish fails due to an epoch error, no retry is necessary (it will be handled by the next iteration of the worker).

It is possible that a readd request was handled by another installation in the group before the current installation processes it. Anytime a readd commit is received on a group for which the current installation is a super admin, regardless of if the current installation is the sender or not:

  1. The responded_at_sequence_id is updated to the sequence ID of the commit.

It is recommended that the worker runs on an interval, such as every 5 minutes, which effectively adds a random jitter before each superadmin performs the requested readds, mitigating the ‘thundering herd’ problem while allowing for batch readds. If there is no worker or the interval is short, the client may choose to manually add a random jitter.

Receiving a welcome

When an installation receives a welcome for a group that it is already active in, the installation must validate that a readd was requested, and that the sender of the welcome is either an installation from the same inbox or a superadmin.

When the welcome is applied, the installation must:

  1. Update the responded_at_sequence_id of their readd status to the sequence ID on the welcome cursor.
  2. If their readd status is no longer ‘awaiting response’, they should clear any bookkeeping of their forked state.

Security

  1. The remote commit log is visible to all users, including non-group members.
  2. The remote commit log is signed by an ED25519 key that is typically shared in the group’s mutable metadata. Only superadmins of the group should create and share this key, but there is no enforcement that prevents other group members from doing so.
  3. In normal operation, only superadmins may write to the remote commit log, but there is no enforcement preventing other group members (or ex group members) from writing to the log using the key shared in the mutable metadata.
  4. When receiving a welcome payload that was issued in response to a ‘readd request’, installations will verify that it was issued by a superadmin of the group (according to the metadata on their fork), or another installation under its own inbox, before accepting it.

Metadata leakage

Entries in the remote commit log are verified only by the ‘consensus public key’, which does not leak identifying information other than membership in the group. The remote commit log may leak general information about when group members are online, and whether commits were successful or not. For comparison, reading encrypted payloads on the group itself may leak similar information.

Malicious group members

In this model, malicious group members and ex-members may write malicious updates to the remote log, causing all group members to send readd requests. However, no superadmin will match the state of the remote log, and hence no installation will be able to service the readd request, resulting in a no-op. All group members will perceive that they are ‘forked’, but continue publishing and reading payloads on this ‘fork’, resulting in no user-visible impact. The end result is that automatic fork recovery for future commits becomes disabled due to the chain of ‘authentic’ updates on the remote commit log being broken.

The ability for group members to arbitrarily ‘disable’ fork recovery is a conscious compromise made to avoid metadata leakage on the remote commit log while keeping the design simple, and could be an area of future work.

Future work

Decentralization

The remote commit log is required to be totally ordered, however the trust assumptions for the log are relaxed. In order to achieve this ordering, the creator of the group may nominate an originator that should receive all publishes to the log, with all other installations following this recommendation. In the event that the originator becomes unavailable, or tampers with the ordering of the log, fork recovery simply becomes disabled, as described in ‘Security’.

Malicious group members

As described in ‘Security’.

Increasing coverage

Currently, fork recovery relies on superadmins being regularly online to publish remote commit log updates and perform readds. In future, a ‘rollover’ mechanism for inactive superadmins, or a more permissive permission model could be considered to increase coverage and response time.

11 Likes
2

Cool！

4 Likes
3

too good

3 Likes
4

Thank you, very detailed

3 Likes
5

look fine!

4 Likes