State Resolution: Reloaded

Yes, this document is intended to be run. It is written in emacs with Org mode in a literate programming style, which interleaves executable code with plain language explanation. If you have emacs and Org mode, you can generate the Haskell file by downloading the reloaded.org file from https://gitlab.com/uhoreg/matrix_state_resolution, opening it in emacs, and doing M-x org-babel-tangle. If you don't have emacs (or don't want to generate the Haskell file), the above repository also contains a pre-generated Haskell file.

Once you have the Haskell file, you can compile it and run the demos in this document. In emacs, you can do C-c C-c in a code block to execute it I had to fiddle with some of my config to get the output to work properly. YMMV. . Note that some demos span multiple code blocks, and you will need to execute them in order.

Of course, this document is also intended to be read. As already mention, this document was written in a literate programming style which mixes code and text blocks. Hopefully the text is easily understandable. The code blocks are prefixed by a line that indicates what the code block is for. This is the chunk name and will be included in other code blocks when their names are included, surrounded by double angle brackets (e.g. <<foo>> will insert any chunks named foo). Chunks named types define some sort of data type, or a utility function for using that type. Chunks named functions define a function. Chunks named foo_demo are part a demonstration named foo.

1+1

2

Some of the foo_demo code blocks are immediately followed by a second code block. This second code block is the value of the final expression of the first code block.

Haskell looks different from what most programmers are used to. For those unfamiliar with Haskell, Appendix A presents a brief primer on Haskell to help understand the code in this document.

In order to make the code easier to understand, I have attempted to avoid overly-idiomatic Haskell, at least in the main parts of the algorithm. Some of the utility functions may have Haskell idioms for brevity, but I have tried to limit this to functions whose implementations would be fairly obvious or that are less important. The hope is that most things should be either intuitively understandable (for those familiar with mathematical notation and with other programming languages), or ignorable.

⊕Note that there may be some opportunity for optimization due to the fact that the entire auth chain may not be needed. It may be possible to stop at a certain point, though the hard part is in determining what that point is.The auth chain of an event is its set of auth events, along with their auth events, recursively.

functions:

authChain :: Event -> (Set.HashSet Event)
authChain (Event { authEvents = e })
  -- ((Set.fromList e):(map authChain e)) means to prepend (Set.fromList e) to
  -- the list returned by (map authChain e), yielding a list of sets.
  -- Set.unions calculates the union of all these sets
  = Set.unions ((Set.fromList e):(map authChain e))

Let us look at an example where Alice creates a room and invites Bob and Carol, and then Bob joins. We will look at the auth chain for Bob's join event.

First, we start with the room creation event. Since it is the first event, it has no auth events.

auth_chain_demo:

create = newStateEvent { eventId = "create"
                       , eventType = Create
                       , sender = "@alice:example.com"
                       }

Next, Alice joins the room. Since she is the room creator and the only previous event is the create event, she is allowed to join the room.

auth_chain_demo:

alice_join = (join "@alice:example.com")
              { eventId = "alice joins"
              , prevEvents = [create]
              , authEvents = [create]
              }

The power levels are set for the room, giving Alice admin powers. The auth events for this event are Alice's join event (she can only send the event if she is in the room), and the room creation event (the room creation event is an auth event for every event in the room) The first power level event sent to a room is a special case: a room that does not have any existing power levels will accept any power level event. .

auth_chain_demo:

pl = ("@alice:example.com" `setsPowerLevels` [ ("@alice:example.com", 100)
                                             ])
     { eventId = "power level"
     , prevEvents = [alice_join]
     , authEvents = [alice_join, create]
     }

The join rules are then set, and Alice invites Bob and Carol. The auth events for these events are the same: the power level event (indicating that Alice has sufficient power to send the event), Alice's join event, and the room creation event.

auth_chain_demo:

join_rules = newStateEvent { eventId = "join rules"
                           , eventType = JoinRules
                           , sender = "@alice:example.com"
                           , content = "private"
                           , prevEvents = [pl]
                           , authEvents = [pl, alice_join, create]
                           }

invite_bob = ("@alice:example.com" `invites` "@bob:example.com")
             { eventId = "invite bob"
             , prevEvents = [join_rules]
             , authEvents = [pl, alice_join, create]
             }

invite_carol = ("@alice:example.com" `invites` "@carol:example.com")
               { eventId = "invite carol"
               , prevEvents = [invite_bob]
               , authEvents = [pl, alice_join, create]
               }

Finally, Bob joins the room. The auth events for this event are Bob's invitation, the join rules (indicating that Bob can join if he was invited), and the room creation event.

auth_chain_demo:

bob_join = (join "@bob:example.com")
           { eventId = "bob joins"
           , prevEvents = [invite_carol]
           , authEvents = [invite_bob, join_rules, create]
           }

Now we calculate the auth chain for Bob's join event. This will be the auth events for Bob's join event (Bob's invitation, the join rules, and the room creation), the auth events for Bob's invitation (the power levels, Alice's join, and the room creation), the auth events for the power levels (Alice's join and the room creation), the auth events for Alices join (the room creation), and the auth events for the room creation (nothing).

auth_chain_demo:⊕ The fromList in the output just means that the result is either a set or a map created from the list that follows. In this case, it is a set. Since this is a set, the list is not in any particular order.

authChain bob_join

fromList ["join rules","invite bob","power level","create","alice joins"]

When an event is sent to a room, it will only be accepted if the sender is authorized to send them according to the room's state set The exact rules are documented in the Authorization of PDUs section of the Matrix spec. . Users who are not in a room cannot send events other than join events; users can only join if the room is public, or if they have been invited. Events can only be sent by users who are in the room, and who have sufficient power level (in this document, we assume PL 50 is required for state events, and PL 0 for messages).

functions:

-- is the sender in the room?
isInRoom :: String -> StateSet -> Bool
isInRoom sender stateSet
  = maybe False (\x -> (content x) == "join") $ Map.lookup (Membership,sender) stateSet

-- get the power levels (if any) from the state set
stateSetPowerLevels :: StateSet -> Maybe (Map.HashMap String Int)
stateSetPowerLevels stateSet
  = Map.lookup (PowerLevels,"") stateSet
  >>= powerLevels

-- determine if the user has sufficient power level
hasPowerLevel :: String -> Maybe (Map.HashMap String Int) -> Int -> Bool
hasPowerLevel _ Nothing _ = True -- if the room has no power levels, then it's a free-for-all
hasPowerLevel sender (Just powerLevels) pl = (Map.lookupDefault 0 sender powerLevels) >= pl

isAuthorized :: Event -> StateSet -> Bool
-- create events are only allowed if they are the first event
isAuthorized
  (Event { eventType = Create
         , stateKey = Just _
         , prevEvents = prevEvents})
  stateSet
  = null prevEvents -- null tests whether it is empty
-- FIXME: join events
-- FIXME: power level events
-- everything else: PL 50 for state events, PL 0 for messages
isAuthorized
  (Event { stateKey = stateKey
         , sender = sender })
  stateSet
  = isInRoom sender stateSet
    && hasPowerLevel sender (stateSetPowerLevels stateSet) (if (stateKey == Nothing) then 0 else 50)

When checking whether an event is authorized in the state resolution algorithm (in particular, in the iterative auth checks algorithm below), the current state set might not be complete, since the (event type, state key) pair may be one that needs to be resolved by the state resolution algorithm. In this case, the missing state events are taken from the auth events of the event under consideration. We can do this by augmenting the state set with the event's auth events when there is a key missing.

functions:

isAuthorized' :: Event -> StateSet -> Bool
isAuthorized' e stateSet = isAuthorized e augmentedStateSet
  where
    -- fold takes a function, initial accumulator value, and a list, and then
    -- iterates over the values in the list, calling the function to update the
    -- accumulator, and returns the final value
    augmentedStateSet = foldl' insertMissingState stateSet $ authEvents e
    insertMissingState stateSet e@(Event { eventType = eventType
                                         , stateKey = Just stateKey })
      = if (eventType, stateKey) `Map.member` stateSet
        then stateSet
        else Map.insert (eventType, stateKey) e stateSet

The iterative auth checks algorithm takes a list of events and and initial state set, and iterates through the events, updating the state set if the event is authorized.

functions:

iterativeAuthChecks :: [Event] -> StateSet -> StateSet
iterativeAuthChecks events stateSet = foldl' addStateIfAuthorized stateSet events
  where
    addStateIfAuthorized stateSet e
      = if isAuthorized' e stateSet
        then insertEvent e stateSet
        else stateSet

Control events (called power events in previous versions, not to be confused with power levels events) are events that have the potential to remove the ability of another user to do something. Power levels, join rules, bans and kicks are control events Technically, normal leave events are also control events, but they are omitted in order to avoid breaking delta state resolution, and it is less likely that someone would attempt to reverse their own leave event through a malicious state reset. (https://matrix.to/#/!WoCKDnRBaGUpRPqTbx:jki.re/$1532339909206jhdSP:jki.re) .

functions:

isControlEvent :: Event -> Bool
isControlEvent (Event { eventType = PowerLevels
                      , stateKey = Just _ }) = True
isControlEvent (Event { eventType = JoinRules
                      , stateKey = Just _ }) = True
isControlEvent (Event { eventType = Membership
                      , sender = sender
                      , content = "ban"
                      , stateKey = Just stateKey }) = sender /= stateKey
-- a kick is a leave event where the sender of the event is not the same as the
-- person leaving (the state key)
isControlEvent (Event { eventType = Membership
                      , sender = sender
                      , content = "leave"
                      , stateKey = Just stateKey }) = sender /= stateKey
-- everything else is not a control event
isControlEvent _ = False

Given some state sets, the auth difference is calculated by first calculating the full auth chain for each state set (that is, the union of the auth chains for the events in the state set) and taking every event that doesn't appear in every auth chain. In other words, if we take the full auth chains for the state sets, then the auth difference is their union minus their intersection.

functions:

fullAuthChain :: [Event] -> (Set.HashSet Event)
fullAuthChain stateSet = Set.unions $ map authChain stateSet

authDifference :: [StateSet] -> (Set.HashSet Event)
authDifference stateSets = authChainsUnion `Set.difference` authChainsIntersection
  where
    authChainsUnion = Set.unions fullAuthChains
    authChainsIntersection = foldl1' Set.intersection fullAuthChains
    fullAuthChains = map (fullAuthChain . Map.elems) stateSets

The full conflicted set is the union of the the conflicted state map and the auth difference. If we were to write this as a function, using the previously defined functions, it would look like:

functions:

fullConflictedSet :: [StateSet] -> (Set.HashSet Event)
fullConflictedSet stateSets = conflictedSet `Set.union` (authDifference stateSets)
  where
    (_, conflictedSet) = calculateConflict stateSets

However, as this is a very simple function, and uses part of the result of calculateConflict, which will be called elsewhere in the state resolution algorithm, we will not use this function, and will instead just inline the definition where it is needed.

When resolving state, we apply two different orderings to events. The first ordering that we apply is called reverse topological power ordering, which is a topological ordering of the events based on the auth events DAG. However, topological orderings are not necessarily unique, and all servers must use the same ordering in order to get the same result from the state resolution algorithm. Thus we will choose a specific topological ordering to use: we define an order on the events by comparing events based on their sender's power levels, then by time stamp, and finally by event ID. The topological ordering that we use will be the lexicographically smallest topological ordering out of all the topological orderings for the set of events based on the event order.

More specifically, given two topological orders \(A = a_1, a_2, \ldots, a_n\) and \(B = b_1, b_2, \ldots, b_n\) from earliest event to latest event, if \(i\) is the first index where \(A\) and \(B\) differ, then \(A\) is lexicographically smaller than \(B\) if \(a_i < b_i\) using the following definition: \(a_i < b_i\) if:

• \(a_i\)'s sender has greater power level than \(b_i\)'s sender when looking at their respective auth events; or (if the power levels are the same)
• \(a_i\)'s timestamp is less than \(b_i\)'s timestamp; or (if the power levels and timestamps are the same)
• \(a_i\)'s event ID is lexicographically less than \(b_i\)'s event ID.

functions:

-- find the power level event (if any) in an e's auth events
_findPL :: Event -> Maybe Event
_findPL e = find (\x -> eventType x == PowerLevels) $ authEvents e

orderForRevTopPowOrd :: Event -> Event -> Ordering
orderForRevTopPowOrd e1 e2
  -- the <> operator, when applied to an ordering, returns the first comparison
  -- that is not equality
  = comparing power e1 e2
    <> comparing timeStamp e1 e2
    <> comparing eventId e1 e2
  where
    -- get the power level of the event's sender
    power e = _findPL e >>= powerLevels >>= (Just . (Map.lookupDefault 0 (sender e)))

We will calculate this topological ordering by using Kahn's algorithm Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM, 5 (11): 558–562, or if you can't locate a copy of that paper, see Wikipedia. functions: ] revTopPowSort events = fromJust $ kahn orderForRevTopPowOrd graph where graph = makeGraph eventId childrenOf events childrenOf event = map eventId $ prevEvents event FIXME: add example , with the modification that when we take a node from the set of nodes under consideration, we will take the node with smallest priority.

The second ordering that we apply is called mainline ordering with respect to a given power level event \(p\). The power level event that the mainline ordering will be based on is either the power level event that is chosen by an earlier step in the state resolution algorithm, or the power level in the unconflicted state map, depending on whether or not there is a conflict in the power level events. The idea for this ordering is that events that are sent using power levels that are "closer" in the DAG to \(p\) are given priority over events sent using power levels that are "farther".

The mainline of an event \(p\) is the list created by starting with \(p\) and recursively taking the power level events from its auth events. In the proposal, the list is ordered such that \(p\) is the last event. In our implementation, \(p\) will be the first event. So when we compare positions in this list, we will use the negation of the position.

Given another event \(e\), the closest mainline event of \(e\) is the first power level event encountered in the mainline of \(p\) when recursively looking at \(e\)'s power level events. In other words, it is the first event in the mainline of \(p\) that is also in the mainline of \(e\), or equivalently, the first event in the mainline of \(e\) that is also in the mainline of \(p\).

Note that in most cases the mainlines from any two events from the same room will converge at some point (at the first power level event, at the latest) with the exception of events that are sent before the first power level event. (In a most rooms, only two events are sent before the first power level event: the create event and the room creator's initial join event. The create event will never be involved in any state conflict, so this will only be relevant for the room creator's initial join event.) In some other abnormal cases, the mainlines may not converge, such as maliciously crafted events or server bugs. In the case of events that are sent before the first power level event, the mainline ordering implementation should order these events before any others. In the case of abnormal events, we want these events to be ordered earlier so that they will be superceded by other events. So in both cases, events whose mainline does not meet the mainline of \(p\) should be considered to be earlier than other events.

The mainline order first orders events based on their closest mainline events: if \(e_1\)'s closest mainline event is closer to \(p\) than \(e_2\)'s closest mainline event, then \(e_1\) is greater than \(e_2\). If \(e_1\) and \(e_2\) have the same closest mainline event, then they are ordered by timestamp, and then by event ID.

functions:⊕The mainlineOrder function here takes advantage of a Haskell feature called "currying": calling a function in Haskell with fewer arguments than what it expects will result in a function that takes the remaining arguments (this is a bit of a lie: technically, Haskell functions only take a single argument, but we usually pretend that they take multiple arguments). Thus calling mainlineOrder p will result in a function that will compare two events by the mainline order with respect to \(p\), and which can be passed to sortBy to sort a list of events using the mainline order.

-- The mainline list of an event e.  unfoldr generates a list by iteratively
-- applying a function until it returns Nothing.  The function returns a tuple
-- where the first element is the element to add to the list and the second
-- element is the input to the next iteration.
mainline e = unfoldr (maybe Nothing (\event -> Just (event, _findPL event))) (Just e)

mainlineOrder :: Event -> Event -> Event -> Ordering
mainlineOrder p e1 e2
  = comparing mainlineDepth e1 e2
    <> comparing timeStamp e1 e2
    <> comparing eventId e1 e2
  where
    -- creates a map from event to the negation of its position in the mainline
    -- list
    mainlineMap = Map.fromList $ zip (mainline p) [0,-1..]
    -- the "closest mainline event" of e is the first event in (mainline e)
    -- that is also in (mainline p).  So iterate through the mainline e list,
    -- look up each event in mainlineMap, and return the first non-Nothing
    -- result that we find.  If there is no non-Nothing result, then return
    -- Nothing (which will sort below everything else).
    mainlineDepth e = listToMaybe $ mapMaybe (\e -> Map.lookup e mainlineMap) $ mainline e

Let us look at an example. For simplicity, we will only include power levels events in the auth events, and we will not indicate any prev events.

mainline_demo:

pl1 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl1"
      , timeStamp = 1 }
pl2 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl2"
      , authEvents = [pl1]
      , timeStamp = 2 }
pl3 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl3"
      , authEvents = [pl1]
      , timeStamp = 4 }
pl4 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl4"
      , authEvents = [pl2]
      , timeStamp = 6 }
pl5 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl5"
      , authEvents = [pl4]
      , timeStamp = 6 }
pl6 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl6"
      , authEvents = [pl4]
      , timeStamp = 5 }
pl7 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl7"
      , authEvents = [pl2]
      , timeStamp = 5 }
pl8 = ("@alice:example.com" `setsPowerLevels` [])
      { eventId = "pl8"
      , authEvents = [pl7]
      , timeStamp = 6 }

We will look at the mainline ordering with respect to pl7, and so the mainline events are pl7, pl2, and pl1 (marked as rectangle nodes).

mainline_demo:

myMainlineOrder = mainlineOrder pl7

Looking at pl3 and pl5, the closest mainline event for pl3 is pl1, and the closest mainline event for pl5 is pl2. Since pl2 is closer to pl7 than pl1 is, pl3 < pl5.

mainline_demo:

myMainlineOrder pl3 pl5

*StateResReloaded Set Map Data.List| *StateResReloaded Set Map Data.List| LT

Looking at pl4 and pl6, they both share the same closest mainline event (pl2). So we look at the timestamps. pl4 has timestamp 6, and pl6 has timestamp 5, so pl4 > pl6.

mainline_demo:

myMainlineOrder pl4 pl6

*StateResReloaded Set Map Data.List| *StateResReloaded Set Map Data.List| GT

Looking at pl4 and pl5, they both share the same same closest mainline event (pl2). Next we look at the timestamps, but they both have timestamp 6. So we finally look at their event IDs, which results in pl4 < pl5.

mainline_demo:

myMainlineOrder pl4 pl5

*StateResReloaded Set Map Data.List| *StateResReloaded Set Map Data.List| LT

If we sort all of the events using the mainline ordering, we get the following:

mainline_demo:

sortBy myMainlineOrder [pl1, pl2, pl3, pl4, pl5, pl6, pl7, pl8]

*StateResReloaded Set Map Data.List| *StateResReloaded Set Map Data.List| ["pl1","pl3","pl2","pl6","pl4","pl5","pl7","pl8"]

We note that this is not a topological ordering, as any topological ordering would have pl4 before pl6.

Haskell heavily uses pattern matching when defining functions. For example, consider the following:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

This defines a function called fib.

The first line defines the input and output types. This is mostly optional, as Haskell will deduce the types, but in this document, I have included them in most top-level functions for clarity. This function takes an integer and returns an integer.

The remaining lines are the actual function definitions, and say that when fib is called with arguments that match the provided patterns (on the left hand side of the =), then the return value of the function is given on the right hand side of the =. Patterns that consist of literals match those literals, so the second line means "when the argument to fib is 0, then return 0". Patterns that consist of variable names match anything, and capture the value of the argument into a variable of that name for use in the right-hand side. So the fourth line means "when the argument to fib is anything, return the value of fib (n-1) + fib (n-2) where n is the value of the argument to fib". The three definitions are evaluated in order, so when fib is called, it will first check if the argument is 0, and if not, it will check if the argument is 1, and if not, then it will use the third definition.

The special pattern "_" matches anything without capturing it value.⊕It is the same as matching with a variable, but never using that variable in the expression. This can be seen in the following definition, which defines a function that provides the functionality of an if-then-else statement:

if' True value _ = value
if' False _ value = value

This defines a function called if' that takes three arguments: a boolean and two other arguments (whose types must be the same). The pattern if' True value _ will match any call to if' where the first argument is True, and the second and third arguments are anything. The second argument is captured into the variable value, and the third argument is ignored. The function in this case just returns value, that is, the second argument. Similarly, when if' is called with False as the first argument, then it will just return its third argument, ignoring the second argument.

In the above examples, the function definitions just return a single expression. More complicated functions can be created using let and where clauses, which can define functions or variables to use in the expression. For example:

l2 (x1,y1) (x2,y2) = sqrt ((sq dx) + (sq dy))
  where
    dx = x2 - x1
    dy = y2 - y1
    sq x = x * x

l2' (x1,y1) (x2,y2)
  = let  dx = x2 - x1
         dy = y2 - y1
         sq x = x * x
    in sqrt ((sq dx) + (sq dy))

Both function definitions are equivalent, and define a function that gives the Euclidean (\(L^2\)) distance between two points. In most cases, the where and let forms can be used interchangeably. In this document, the form used will mostly depend on whether the final expression or the intermediate variables are of most interest.

Anonymous functions are written as (\ arguments -> return value). For example, an anonymous function for doubling a number is (\x -> 2*x). The arguments can also use destructuring. For example, an anonymous function for exchanging the elements in a tuple is (\(x,y) -> (y,x)).

Haskell has a special data type called Maybe, which is used to signify an optional value. In a dynamically-typed language such as JavaScript or Python, it would be similar to a variable being allowed to have, for example, either a string value or null (in JavaScript) or None (in Python). However, since variables in Haskell can only have one type, the type Maybe T is used, where T is any other data type. If a variable is of type Maybe String, then it can have a value Just s, where s is any string, or it can have the value Nothing.

Haskell has an >>= operator which is related to a concept called monads, which many people find confusing. However, in this document, the >>= operator is only used with the Maybe data type, which makes things simpler. Suppose that x is a value of type Maybe T1, and f is a function that takes an argument of type T1 and returns a Maybe T2. If x has value Just s, then x >>= f is equal to f s, and if x is Nothing, then x >>= f is equal to Nothing. In other words, >>= will pass through Nothing, but if the left-hand side has a value, then >>= will unwrap it from the Maybe type and apply the right-hand side. It can be seen as something like an exception handler in that returning a Nothing will cause it to skip over the remaining computations.

In Haskell, the $ operator is just a trick to avoid using parentheses. It is equivalent to inserting an open parenthesis where the $ is, and the matching close parenthesis at the end of the expression. For example, the expression

Set.fromList $ concat $ map Map.keys stateSets

is equivalent to

Set.fromList ( concat ( map Map.keys stateSets ))

The . operator represents function composition. For example, if we write

f = g . h

then evaluating f x would be the same as evaluating g (h x).

Haskell allows any binary function to be used as an infix operator by wrapping the function name in backticks ("`"). In this document, this is mostly used for set and map operations and for creating events where doing so makes things read more like the way you would read it in English. For example, x `Set.member` y is equivalent to Set.member x y and can be read as "x is a member of the set y".