Fork Resolution

If members of a group merge different commits, the group state is called forked. At this point, the group members have different keys and will not be able to decrypt each others' messages. While this should not happen in normal operation, it may still occur due to bugs. When enabling the fork-resolution-helpers feature, OpenMLS comes with helpers to get a working group again. There are two helpers, and they use different mechanisms.

The readd helper removes and then re-adds members that are forked. This requires that the caller knows the set of members that are forked. It is relatively efficient, especially if only a small number of members forked.

The reboot helper creates a new group and helps with migrating the entire group state over. This includes extensions in the group context, as well as re-inviting all the members.

We provide examples for how to use both, and in the end provide some guidance on detecting forks.

readd Example

First, let's create a forked group. In this example, Alice creates a group and adds Bob. Then, they both merge different commits to add Charlie.

    // Alice creates a group
    let mut alice_group = MlsGroup::new(
        alice_provider,
        &alice_signature_keys,
        &mls_group_create_config,
        alice_credential.clone(),
    )
    .unwrap();

    // Alice adds Bob and merges the commit
    let add_bob_messages = alice_group
        .commit_builder()
        .propose_adds(vec![bob_kpb.key_package().clone()])
        .load_psks(alice_provider.storage())
        .unwrap()
        .build(
            alice_provider.rand(),
            alice_provider.crypto(),
            &alice_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(alice_provider)
        .unwrap();

    alice_group.merge_pending_commit(alice_provider).unwrap();

    // Bob joins from the welcome
    let welcome = add_bob_messages.into_welcome().unwrap();
    let mut bob_group =
        StagedWelcome::new_from_welcome(bob_provider, mls_group_config, welcome.clone(), None)
            .unwrap()
            .into_group(bob_provider)
            .unwrap();

    // Now Alice and Bob both add Charlie and merge their own commit.
    // This forks the group.
    let charlie_kpb = generate_key_package(
        ciphersuite,
        charlie_credential,
        Extensions::empty(),
        charlie_provider,
        &charlie_signature_keys,
    );

    let add_charlie_messages = alice_group
        .commit_builder()
        .propose_adds(vec![charlie_kpb.key_package().clone()])
        .load_psks(alice_provider.storage())
        .unwrap()
        .build(
            alice_provider.rand(),
            alice_provider.crypto(),
            &alice_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(alice_provider)
        .unwrap();

    bob_group
        .commit_builder()
        .propose_adds(vec![charlie_kpb.key_package().clone()])
        .load_psks(bob_provider.storage())
        .unwrap()
        .build(
            bob_provider.rand(),
            bob_provider.crypto(),
            &bob_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(bob_provider)
        .unwrap();

    alice_group.merge_pending_commit(alice_provider).unwrap();
    bob_group.merge_pending_commit(bob_provider).unwrap();

    // Charlie joins using Alice's invite
    let welcome = add_charlie_messages.into_welcome().unwrap();
    let mut charlie_group =
        StagedWelcome::new_from_welcome(charlie_provider, mls_group_config, welcome, None)
            .unwrap()
            .into_group(charlie_provider)
            .unwrap();

    // We should be forked now, double-check
    // Alice and Charlie are on the same state
    assert_eq!(
        alice_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );
    // But Bob is different from the other two
    assert_ne!(bob_group.confirmation_tag(), alice_group.confirmation_tag());
    assert_ne!(
        bob_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );

Then, Alice removes and re-adds Bob using the helper. We assume here that Alice knows that only Bob merged the wrong commit. This information needs to be transferred somehow, see Fork Detection. Notice how Alice needs to provide a new key package for Bob.

    // Let Alice re-add the members of the other partition (i.e. Bob)
    let bob_new_kpb = generate_key_package(
        ciphersuite,
        bob_credential,
        Extensions::empty(),
        bob_provider,
        &bob_signature_keys,
    );

    // Alice and Charlie are in the same partition
    let our_partition = &[alice_group.own_leaf_index(), charlie_group.own_leaf_index()];
    let builder = alice_group.recover_fork_by_readding(our_partition).unwrap();

    // Here we iterate over the members of the complement partition to get their key packages.
    // In this example this is trivial, but the pattern extends to more realistic scenarios.
    let readded_key_packages = builder
        .complement_partition()
        .iter()
        .map(|member| {
            let basic_credential = BasicCredential::try_from(member.credential.clone()).unwrap();
            match basic_credential.identity() {
                b"Bob" => bob_new_kpb.key_package().clone(),
                other => panic!(
                    "we only expect bob to be re-added, but found {:?}",
                    String::from_utf8(other.to_vec()).unwrap()
                ),
            }
        })
        .collect();

    // Specify the key packages to be re-added and create the commit
    let readd_messages = builder
        .provide_key_packages(readded_key_packages)
        .load_psks(alice_provider.storage())
        .unwrap()
        .build(
            alice_provider.rand(),
            alice_provider.crypto(),
            &alice_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(alice_provider)
        .unwrap();

    // Make Bob re-join the group and Alice and Charlie merge the commit that adds Bob.
    let (commit, welcome, _) = readd_messages.into_contents();
    let welcome = welcome.unwrap();
    let bob_group = StagedWelcome::new_from_welcome(bob_provider, mls_group_config, welcome, None)
        .unwrap()
        .into_group(bob_provider)
        .unwrap();

    alice_group.merge_pending_commit(alice_provider).unwrap();

    if let ProcessedMessageContent::StagedCommitMessage(staged_commit) = charlie_group
        .process_message(charlie_provider, commit.into_protocol_message().unwrap())
        .unwrap()
        .into_content()
    {
        charlie_group
            .merge_staged_commit(charlie_provider, *staged_commit)
            .unwrap()
    } else {
        panic!("expected a commit")
    }

    // The fork should be fixed now, double-check
    assert_eq!(alice_group.confirmation_tag(), bob_group.confirmation_tag());
    assert_eq!(
        alice_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );
    assert_eq!(
        charlie_group.confirmation_tag(),
        bob_group.confirmation_tag()
    );

In the end, they all can communicate again.

reboot Example

Again, let's create a forked group. In this example, Alice creates a group and adds Bob. Then, they both merge different commits to add Charlie.

    // Alice creates a group
    let mut alice_group = MlsGroup::new(
        alice_provider,
        &alice_signature_keys,
        &mls_group_create_config,
        alice_credential.clone(),
    )
    .unwrap();

    // Alice adds Bob and merges the commit
    let add_bob_messages = alice_group
        .commit_builder()
        .propose_adds(vec![bob_kpb.key_package().clone()])
        .load_psks(alice_provider.storage())
        .unwrap()
        .build(
            alice_provider.rand(),
            alice_provider.crypto(),
            &alice_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(alice_provider)
        .unwrap();

    alice_group.merge_pending_commit(alice_provider).unwrap();

    // Bob joins from the welcome
    let welcome = add_bob_messages.into_welcome().unwrap();
    let mut bob_group =
        StagedWelcome::new_from_welcome(bob_provider, mls_group_config, welcome, None)
            .unwrap()
            .into_group(bob_provider)
            .unwrap();

    // Now Alice and Bob both add Charlie and merge their own commit.
    // This forks the group.
    let charlie_kpb = generate_key_package(
        ciphersuite,
        charlie_credential.clone(),
        Extensions::empty(),
        charlie_provider,
        &charlie_signature_keys,
    );

    let add_charlie_messages = alice_group
        .commit_builder()
        .propose_adds(vec![charlie_kpb.key_package().clone()])
        .load_psks(alice_provider.storage())
        .unwrap()
        .build(
            alice_provider.rand(),
            alice_provider.crypto(),
            &alice_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(alice_provider)
        .unwrap();

    bob_group
        .commit_builder()
        .propose_adds(vec![charlie_kpb.key_package().clone()])
        .load_psks(bob_provider.storage())
        .unwrap()
        .build(
            bob_provider.rand(),
            bob_provider.crypto(),
            &bob_signature_keys,
            |_| true,
        )
        .unwrap()
        .stage_commit(bob_provider)
        .unwrap();

    alice_group.merge_pending_commit(alice_provider).unwrap();
    bob_group.merge_pending_commit(bob_provider).unwrap();

    // Charlie joins using Alice's invite
    let welcome = add_charlie_messages.into_welcome().unwrap();
    let charlie_group =
        StagedWelcome::new_from_welcome(charlie_provider, mls_group_config, welcome, None)
            .unwrap()
            .into_group(charlie_provider)
            .unwrap();

    // We shoulkd be forked now, double-check
    // Alice and Charlie are on the same state
    assert_eq!(
        alice_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );
    // But Bob is different from the other two
    assert_ne!(bob_group.confirmation_tag(), alice_group.confirmation_tag());
    assert_ne!(
        bob_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );

Then, Alice sets up a new group and adds everyone from the old group. In this approach, she not only needs to provide key packages for all members, but also set a new group id and migrate the group context extensions, because these might be contain e.g. the old group id. This is the responsibility of the application, so the API just exposes the old extensions and expects the new ones.

    // Let Alice reboot the group. For that she needs new key packages for Bob and Charlie, a;s
    // well as a new group ID.
    let bob_new_kpb = generate_key_package(
        ciphersuite,
        bob_credential,
        Extensions::empty(),
        bob_provider,
        &bob_signature_keys,
    );

    let charlie_new_kpb = generate_key_package(
        ciphersuite,
        charlie_credential,
        Extensions::empty(),
        charlie_provider,
        &charlie_signature_keys,
    );

    let new_group_id: GroupId = GroupId::from_slice(
        alice_group
            .group_id()
            .as_slice()
            .iter()
            .copied()
            .chain(b"-new".iter().copied())
            .collect::<Vec<_>>()
            .as_slice(),
    );

    let (mut alice_group, reboot_messages) = alice_group
        .reboot(new_group_id)
        .finish(
            Extensions::empty(),
            vec![
                bob_new_kpb.key_package().clone(),
                charlie_new_kpb.key_package().clone(),
            ],
            // We can use this closure to add more proposals to the commit builder that is used to
            // create the commit that readds all the other members, but in this case we will leave
            // it as-is.
            |builder| builder,
            alice_provider,
            &alice_signature_keys,
            alice_credential,
        )
        .unwrap();

    alice_group.merge_pending_commit(alice_provider).unwrap();

    // Bob and Charlie join the new group
    let welcome = reboot_messages.into_welcome().unwrap();
    let bob_group =
        StagedWelcome::new_from_welcome(bob_provider, mls_group_config, welcome.clone(), None)
            .unwrap()
            .into_group(bob_provider)
            .unwrap();
    assert_eq!(bob_group.own_leaf_index(), LeafNodeIndex::new(1));

    let charlie_group =
        StagedWelcome::new_from_welcome(charlie_provider, mls_group_config, welcome, None)
            .unwrap()
            .into_group(charlie_provider)
            .unwrap();
    assert_eq!(charlie_group.own_leaf_index(), LeafNodeIndex::new(2));

    // The fork should be fixed now, double-check
    assert_eq!(alice_group.confirmation_tag(), bob_group.confirmation_tag());
    assert_eq!(
        alice_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );
    assert_eq!(
        bob_group.confirmation_tag(),
        charlie_group.confirmation_tag()
    );

In the end, they all can communicate again.

Fork Detection

Before initiating fork resolution, we first need to detect that a fork happened. In addition, for using the readd mechanism, we also need to know the members that forked.

One simple technique that may work, depending on how the delivery service works, is to consider all incoming non-decryptable messages as a sign that there is a fork. However, this may lead to false positives and is not enough to know the membership.

One way to learn about this that every member send a message when they merges a commit, encrypted for the old epoch, that contains the hash of the commit they are merging. This way, all group members know which commits are merged, and the readd strategy can be used to resolve possible forks.