Matrix Homeserver Implementation Part 2: State Resolution v1

July 1, 2023

In my previous blog post ¹, I gave an overview of the Matrix protocol and provided some helpful tips for actually implementing the core functionality that homeservers adhering to the spec are expected to provide. I left off on State Resolution, which I felt deserved its own series of posts because covering it will take at least as many words as that post ended up being.

This post is going to have a lot of pseudocode. As I mentioned in my previous post, Matrix state resolution is well-documented from a conceptual standpoint, so I don't feel the need to explain the concepts yet again. Instead, I'll focus on the far more difficult task of translating those concepts into code. My pseudocode is not Python-esque like most—rather, it resembles C, which I find easier to read and write. C is much less ambiguous. But maybe I think that just because I'm a C programmer and not a Python programmer. Regardless of your preferred language, I hope you can see past the syntax and understand what I'm writing. The data structures used can be easily inferred, although I may be biased because they very closely resemble Telodendria's actual code.

To recap briefly the important takeaways from Part 1, State is a collection of key-value pairs where the key is an event type and a state key provided by an event, and the value is an event ID. This collection of key-value pairs describes a room in its entirety; from name, topic, and aliases to user membership and permissions, everything anyone needs to know about a room is derived from the room's State.

You can think of room state as a collection of pointers to the state events that determine what the room looks like, who's in it, and what kind of events they're allowed to send. We know why state is so important, and we know where state resolution fits into the overall implementation of a homeserver, but we have yet to figure out how it actually works. As I mentioned in my last post, there are two algorithms, with room version 1 using the original algorithm, and versions 2 and beyond using the new and improved algorithm. In this post, I'll set up the framework primarily for the original algorithm, but some of these details will apply also to the improved algorithm.

First, we need to figure out what the state resolution algorithm's inputs and outputs are. At a high level, we can say that the state resolution algorithm's input is a single event, and its output is the complete state of the Matrix room before that event was added to the room's directed acyclic graph (DAG). So, your state resolution function is going to look roughly like this:

HashMap *
StateResolve(Event *);

Note that both state resolution algorithms are recursive; that is, you must have resolved the state for each previous event specified by the input event before you can resolve the state for the current event. This might look like this:

HashMap *
StateResolve(Event *e)
{
    Array *states;
    size_t i;
    for (i = 0; i < ArraySize(e->prev_events); i++)
    {
        Event *p = ArrayGet(e->prev_events, i);
        HashMap *state = StateResolve(p);
        /*
         * state is now the room state before p. Remember to
         * apply p to state if p is a state event so that
         * state becomes the room state after p.
         */
        ArrayAdd(states, state);
    }
    /*
     * states is now the set of the previous states of the
     * of the room to be resolved. We can continue with the
     * resolution algorithm.
     */
}

An efficient homeserver will not resolve the room state at an event more than once; room state should be cached for each event that it is calculated for so that the algorithm does not need to compute redundant results. The implication of this is that a Matrix homeserver stores snapshot of the room state before each and every event in the room.

The next step in state resolution now depends on the algorithm we are using. If the room version is 1, then we have to use the original state resolution algorithm. Otherwise, we use the new, improved state resolution algorithm. We should modify the signature of our StateResolve() function to accomodate this:

HashMap *
StateResolve(int roomVersion, Event *e);

To make things easier, after we perform the logic shown above and we have our set of states, lets break out each version of the algorithm into its own function:

HashMap *
StateResolve(int roomVersion, Event *e)
{
    Array *states; /* Array of HashMaps */

    /* ... Logic shown above ... */

    switch (roomVersion)
    {
        case 1:
            return StateResolveV1(states);
            break;
        default:
            return StateResolveV2(states);
    }
}

Let us now implement the original state resolution algorithm. The first step is as follows:

"Start by setting R to the union of the states to be resolved, excluding any conflicting events." ²

What this means is that we have to build up a new partial state map by looking at each state in the incoming array of states and adding all the keys that don't already exist in the partial state. If a key does have a conflict, then we remove it from the partial state and collect the conflicting events events to resolve them. This process looks something like this:

HashMap *
StateResolveV1(Array *states)
{
    HashMap *r;
    HashMap *conflicted;
    size_t i;

    for (i = 0; i < ArraySize(states); i++)
    {
        HashMap *state = ArrayGet(states, i);
        char *eventType;
        HashMap *stateKeys;

        while (HashMapIterate(state, &eventType,  &stateKeys))
        {
            char *stateKey;
            char *eventId;

            while (HashMapIterate(stateKeys, &stateKey, &eventId))
            {
                /* (eventType, stateKey) -> eventId */
                if (HashMapGet(HashMapGet(r, eventType), stateKey))
                {
                    /*
                        * Conflicted state, add to conflicted and
                        * remove from r.
                        */
                }
                else
                {
                    /* Add this state pair to r */
                }
            }
        }
    }
}

We now have R, which perfectly maps a state tuple to a single event ID. However, we also have a conflicted set, which maps a state tuple to more than one event ID. This is what we have to resolve onto R. The original state resolution algorithm states that we must deal specially with the following types of events:

m.room.power_levels
m.room.join_rules
m.room.member

For each of these event types, we are to collect all the event IDs that have these types in the conflicted set into a list. We will then sort that list by depth and event ID—well, specifically the SHA-1 hash of the event ID. Then, we will iterate over each list, adding the first event, and then making sure the rest of the events are allowed by the authorization rules in R. If they are, we keep updating R with the events, otherwise, we stop and continue on to the next list. This process is explained a little more clearly in the Matrix specification, but here's some pseudocode that shows how it's done:

HashMap *
StateResolveV1(Array *states)
{
    HashMap *r;
    HashMap *conflicted;

    Array *authTypes;
    size_t i;

    /* ... Logic shown above ... */

    ArrayAdd(authTypes, "m.room.power_levels");
    ArrayAdd(authTypes, "m.room.join_rules");
    ArrayAdd(authTypes, "m.room.member");

    for (i = 0; i < ArraySize(authTypes); i++)
    {
        char *authType = ArrayGet(authTypes, i);
        HashMap *stateKeys = HashMapGet(conflicted, authType);

        Array *events;
        char *stateKey;
        Array *eventIds;

        char *eventId;
        Event *e;

        /* Assemble all the events of the given type */

        while (HashMapIterate(stateKeys, &stateKey, &eventIds))
        {
            size_t j;

            for (j = 0; j < ArraySize(eventIds); j++)
            {
                eventId = ArrayGet(eventIds, i);

                ArrayAdd(events, eventId);
            }
        }

        /* Sort ascending by depth, descending by SHA-1 of ID */

        ArraySort(events, EventCompareFunc);

        /* Add first event to R */

        eventId = ArrayGet(eventIds, 0);
        e = EventGet(eventId);
        HashMapSet(HashMapGet(r, e->type), e->state_key, eventId);
    }
}

The EventCompareFunc() is implemented roughly as follows:

int
EventCompareFunc(Event *e1, Event *e2)
{
    int depth1 = e1->depth;
    int depth2 = e2->depth;

    if (depth1 > depth2)
    {
        return 1;
    }
    else if (depth1 < depth2)
    {
        return -1;
    }
    else
    {
        /* Descending */
        char *sha1 = Sha1(e1->event_id);
        char *sha2 = Sha1(e2->event_id);

        return strcmp(sha1, sha2) * -1;
    }
}

The above code actually covers the next two steps in the algorithm as well; it sorts the event lists and it adds the first event in the list to R. The next step is to process the rest of the events in the list, which is as simple as iterating over it and performing the auth check using the partial state R.

We should then clean up the conflicted set, removing the type keys that we've processed so far, because we will have to iterate over all the remaining type keys.

But first, suppose we have this function:

int
AuthCheck(HashMap *state, Event *e);

This function takes in a room state and an event and determines whether or not that event is allowed to be in the room based on the authorization rules determined by the room state, such as membership, power levels, and the like. This is going to be the same function used when receiving events from the client-server API or the federation API. We also need it for state resolution. AuthCheck() should follow the authorization rules for the room version we are working with. Refer to the relevant section of the specification. It doesn't make sense to lay out an implementation here because the logic is very clearly laid out in the specification.

Assuming we have such a function, we can continue on with our algorithm. After we add the first event from our sorted list to R, we can use the AuthCheck() function on the remainder of the events, like this:

HashMap *
StateResolveV1(Array *states)
{
    HashMap *r;
    HashMap *conflicted;
    size_t i;

    /* ... Logic shown above ... */

    for (i = 0; i < ArraySize(authTypes); i++)
    {
        char *authType = ArrayGet(authTypes, i);
        size_t j;
        Array *events;

        /* ... Logic shown above ... */

        for (j = 1; j < ArraySize(events); j++)
        {
            char *eventId = ArrayGet(events, j);
            Event *e = EventGet(eventId);

            if (AuthCheck(r, e))
            {
                HashMapSet(HashMapGet(r, e->type), e->state_key, eventId);
            }
            else
            {
                break;
            }
        }

        HashMapDelete(conflicted, authType);
    }
}

Finally, one step remains in the algorithm:

"... for all other conflicts, just pick the event with the highest depth and the lowest sha1(event_id) that passes authentication in R and add it to R."

All that the specification is telling us to do here is to iterate over the remaining conflicted events, sorting them like we sorted all the other events, and then work backwards through the list until we find an event that passes authentication against R. That looks like this:

HashMap *
StateResolveV1(Array *states)
{
    HashMap *r;
    HashMap *conflicted;

    size_t i;
    char *eventType;
    HashMap *stateKeys;

    /* ... Logic shown above ... */

    while (HashMapIterate(conflicted, &eventType, &stateKeys))
    {
        char *stateKey;
        Array *events;

        while (HashMapIterate(stateKeys, &stateKey, &events))
        {
            ArraySort(events, EventCompareFunc);

            for (i = ArraySize(events) - 1; i >= 0; i--)
            {
                char *eventId = ArrayGet(events, i);
                Event *e = EventGet(eventId);
                if (AuthCheck(r, e))
                {
                    HashMapSet(HashMapGet(r, eventType), stateKey, eventId);
                    break;
                }
            }
        }
    }
}

And that should be it! This is the basic algorithm for state resolution v1. While some details are omitted—notably the auth check and the details of some of the primitive data structures—this should fundamentally work.