The auth difference is used:
#+BEGIN_QUOTE
... to solve the problem where you have e.g. chains of power level events, like
Alice gives Bob power (A), then Bob gives Charlie power (B) and then Charlie,
say, changes the ban level (C). If you try and resolve two state sets one of
which has A and the other has C, C will never pass auth since Charlie doesn't
have power in A. If you pull in the auth difference (B) then you get A -> B ->
C, which does pass
auth. (https://github.com/matrix-org/matrix-doc/pull/1441#issuecomment-408159689)
#+END_QUOTE
#+HTML:

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~:
#+NAME: functions
#+BEGIN_SRC haskell
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
#+END_SRC
** Full conflicted set
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~:
#+NAME: functions
#+BEGIN_SRC haskell
fullConflictedSet :: [StateSet] -> (Set.HashSet Event)
fullConflictedSet stateSets = conflictedSet `Set.union` (authDifference stateSets)
where
(_, conflictedSet) = calculateConflict stateSets
#+END_SRC
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.
* Ordering
** Reverse topological power ordering
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 of $<$: $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.
We will calculate this topological ordering by using Kahn's algorithm[fn:kahn],
with the modification that when we take a node from the set of nodes under
consideration, we will take the node with smallest priority.
[fn:kahn] 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 [[https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm][Wikipedia]].
~functions~:
#+NAME: functions
#+BEGIN_SRC haskell
-- 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
-- order by # of items in auth chain
data EventPriority
= EventPriority { vertexAuthChain :: Set.HashSet Event
, revAuthChain :: Set.HashSet Event
, remainingOutdegree :: Int
, senderPowerLevel :: Int
}
revTopPowSort :: [Event] -> [Event]
revTopPowSort events = kahn [] pqueue
where
inDegreeZeroVertices = []
pqueue = []
kahn sorted [] = reverse sorted
-- FIXME:
#+END_SRC
FIXME: add example
** Mainline ordering
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 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~:[[mn:1][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.]]
#+NAME: functions
#+BEGIN_SRC haskell
-- 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
-- define a new operator that allows us to chain comparisons and return the
-- first comparison that is not equality
LT ||| _ = LT
GT ||| _ = GT
EQ ||| val = val
-- 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
#+END_SRC
#+HTML:
#+RESULTS: mainline_graph
[[file:mainline.svg]]
#+HTML:

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~:
#+BEGIN_SRC haskell :results value verbatim code :prologue ":load StateResReloaded\n:set +m\nimport qualified Data.HashSet as Set\nimport qualified Data.HashMap.Strict as Map\n:{" :epilogue ":}" :exports code :session mainline
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 }
#+END_SRC
#+NAME: mainline_dot
#+BEGIN_SRC haskell :results value verbatim :exports none :session mainline
eventsToDot [pl1, pl2, pl3, pl4, pl5, pl6, pl7, pl8] (Set.empty)
#+END_SRC
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~:
#+BEGIN_SRC haskell :results value verbatim code :prologue ":{" :epilogue ":}" :exports code :session mainline
myMainlineOrder = mainlineOrder pl7
#+END_SRC
#+NAME: mainline_graph
#+BEGIN_SRC dot :file mainline.svg :var input=mainline_dot
digraph {
graph [bgcolor=transparent,rankdir=BT]
pl7 [shape=rectangle]
pl2 [shape=rectangle]
pl1 [shape=rectangle]
$input
}
#+END_SRC
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~:
#+BEGIN_SRC haskell :results value verbatim code :prologue ":{" :epilogue ":}" :exports both :session mainline
myMainlineOrder pl3 pl5
#+END_SRC
#+RESULTS:
#+BEGIN_SRC haskell
LT
#+END_SRC
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~:
#+BEGIN_SRC haskell :results value verbatim code :prologue ":{" :epilogue ":}" :exports both :session mainline
myMainlineOrder pl4 pl6
#+END_SRC
#+RESULTS:
#+BEGIN_SRC haskell
GT
#+END_SRC
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~:
#+BEGIN_SRC haskell :results value verbatim code :prologue ":{" :epilogue ":}" :exports both :session mainline
myMainlineOrder pl4 pl5
#+END_SRC
#+RESULTS:
#+BEGIN_SRC haskell
LT
#+END_SRC
If we sort all of the events using the mainline ordering, we get the following:
~mainline_demo~:
#+BEGIN_SRC haskell :results value verbatim code :prologue ":{" :epilogue ":}" :exports both :session mainline
sortBy myMainlineOrder [pl1, pl2, pl3, pl4, pl5, pl6, pl7, pl8]
#+END_SRC
#+RESULTS:
#+BEGIN_SRC haskell
["pl1","pl3","pl2","pl6","pl4","pl5","pl7","pl8"]
#+END_SRC
We note that this is not a topological ordering, as any topological ordering
would have ~pl4~ before ~pl6~.
* State resolution algorithm
First, we start by calculating the unconflicted state map and the full
conflicted set (the expression for calculating the full conflicted set was
discussed above).
~resolve~:
#+BEGIN_SRC haskell :noweb-ref resolve
(unconflictedStateMap, conflictedSet) = calculateConflict stateSets
fullConflictedSet = conflictedSet `Set.union` (authDifference stateSets)
#+END_SRC
The state resolution algorithm will try to resolve the state from the full
conflicted set.
First, we focus on trying to resolve the power levels of the room. We do this
by considering the power events from the full conflicted set. We will also add
in the events that are in the full auth chain of the power events that are also
in the full conflicted set.
~resolve~:
#+BEGIN_SRC haskell :noweb-ref resolve
conflictedPowerEvents = Set.filter isPowerEvent fullConflictedSet
conflictedPowerEventsWithAuth
= conflictedPowerEvents
`Set.union`
((fullAuthChain $ Set.toList conflictedPowerEvents)
`Set.intersection`
fullConflictedSet)
#+END_SRC
We sort these events using the reverse topological power ordering and, starting
from the unconflicted state map, build up a new partially resolved state set by
performing the iterative auth checks on these events.
~resolve~:
#+BEGIN_SRC haskell :noweb-ref resolve
sortedPowerEvents = revTopPowSort $ Set.toList conflictedPowerEventsWithAuth
partialResolvedState = iterativeAuthChecks sortedPowerEvents unconflictedStateMap
#+END_SRC
Next, we consider the remaining events from the full conflicted set.
~resolve~:
#+BEGIN_SRC haskell :noweb-ref resolve
otherConflictedEvents = fullConflictedSet `Set.difference` conflictedPowerEventsWithAuth
#+END_SRC
We sort them in ascending order using the mainline ordering with respect to the
previously resolved power levels event, and then, using the iterative auth
checks, we again build up a new resolved state set.
~resolve~:
#+BEGIN_SRC haskell :noweb-ref resolve
resolvedPowerLevels = fromJust $ Map.lookup (PowerLevels, "") partialResolvedState
sortedOtherEvents = sortBy (mainlineOrder resolvedPowerLevels) $ Set.toList otherConflictedEvents
nearlyFinalState = iterativeAuthChecks sortedOtherEvents partialResolvedState
#+END_SRC
Finally, we make sure that the final state has all the events from the original
unconflicted state map.
~functions~:
#+NAME: functions
#+BEGIN_SRC haskell :noweb no-export
resolve :: [StateSet] -> StateSet
resolve stateSets
= let
<