以下資料主要是出自於 State Resolution v2 for the Hopelessly Unmathematical
算法目標
由於所有 Homeserver 都獨自保有一份控制事件樹（有向無環），各自採用一固定算法得到控制狀態，這個算法是為了解決控制狀態不同（通常是因為控制事件亂序）時，協調出一個控制狀態的共識（對控制事件數進行排列）
名詞定義
等下講到的算法會需要對目標做一些定義，由於原文區分的部份有些模糊（尤其是 Auth Event 的定義），所以有加了些我個人的理解
State Event
State Event 泛指那些會更改聊天室設定的事件，小到設定聊天室的圖標，大到用戶間的權限更改/踢人/拉人等等操作
之後提到的 State Event 如果沒有特別表明，通常指的是 Normal State Event，也就是比較無關痛癢的事件，像是更改圖標、用戶登入/離開等等
在這類狀態事件中，有另一類是相對更為重要的，也就是控制事件
Control Event
控制事件，像是權限的給予/收回，這類操作會直接影響後續對應的操作是否合法，因此事件順序影響非常大
這邊的「控制事件」我個人認為更接近「踢人、Ban 人」等等「受權限影響的操作」
Auth Event
而另外一邊「調整權限的操作」則應該分類為認證事件，這些事件的順序會影響控制事件的執行與否
State Resolve Algorithm
所有的（聊天室）狀態又簡單分成兩種： unconflicted 與 conflicted
現在假設狀態出現了分支（fork），以下狀態屬於 conflicted state set （狀態集合）：
- 在所有分支中，同一個事件類別（event_type）有超過一種的對應值 （state_key）
- 在所有分支中，一事件類別存在僅一分支保有 state_key 而其他分支沒有
而 unconflicted state set 基本上就是 vice versa
流程
整個過程就是把 conflicted state 消化掉後加到 unconflicted state
直到所有狀態都變成 unconflicted state
- 從 unconflicted state 開始，作為出發點（base layer）
- 用 Reverse Topological Ordering 算出控制事件的順序，並把結果疊到 unconflicted stated 上
- 用 Mainline Ordering 算出（一般）狀態事件的順序，並把結果疊到 unconflicted stated 上
- 檢查有沒有 unconflicted state_key 在前面步驟被更改
Reverse Topological Ordering
這個排序算法的目的在於「保證被使用到的 Auth Events 總是會排在需要他的事件前」
為此會使用到 Kahn’s Algorithm 的變種，因此來簡介下 Kahn’s algorithm
Kahn’s Algorithm
Kahn’s Algorithm 是一個圖排序算法，用這個算法排出來的順序不唯一，因此需要做一點調整才能符合 Matrix 的需求
這是一個相對直覺的算法，網路上也有蠻多教學，我簡單用圖例說明
如上圖，我們把事件間的依賴關係抽象成 DAG，edge 連線則代表依賴關係
文言一點來說，incoming edge 的數量代表「多少事件依賴你」，outgoing edge 的數量代表「你依賴多少事件」
因此我們可以很直覺的得到「沒有 incoming edge 的人是最晚發生的」的觀察結果 （因為沒有其他事件依賴它）
利用這個觀察結果，我們開始 Kahn’s Algorithm
這個算法主軸就是「遞歸的移除節點，以及其的 outging edge」，而這邊我們需要選擇的就是「沒有 incoming edge 」的節點（也就是每次迭代中，最晚的節點）
根據上圖，我們可以選擇的節點包含 1 與 5，假設這邊選擇了刪掉節點 1
在下次迭代中，我們可以看到節點 2, 3, 5 現在都算是最晚的節點了，於是再在這三個面選一個，假設選節點 5
以此類推，我們最後可以得到一組不唯一的解，像是（1, 5, 2, 3, 4, 6）或是（5, 1, 2, 3, 4, 6）都是合法的，並且需要注意到這邊的順序是反過來的，是「由最晚發生到最早發生」，因此才會稱為 Reverse topology ordering
但是這個方法的得到的順序是不唯一的 non-deterministic result，Matrix 加上了一些限制讓結果變成唯一，像是：
- 高權限的優先
- 有較早時間戳的優先（要拿到 consistent timestamp 可能也要去 Google Spanner Truetime）
- ID 比較小的先（這個是作為預防措施，以防上面都不管用）
因此在真正跑 Kahn’s Algorithm 之前，需要先用上述三個規則排序得到唯一的順序
Mainline ordering
現在我們已經將影響權限的事件排序了，現在只剩下其他的狀態事件了，我們可以把這些 auth event 串起來作為一個 partial graph 稱之為 「Power level mainline」，基本上這個 mainline 的長度會從「創建聊天室」到「最後一個取得共識的 auth event」，其他的狀態事件會座落在這個像是一個座標軸的線上，mainline 上的 auth event 這邊又稱為 「power level event」，可以想像成 x=1, 2, 3 … 那種感覺，而狀態事件就是落在 x 軸上的點，任兩個 power level event 中間間隔又被稱之為 epoch，可以理解成 2 < x < 5 的感覺
上圖中我們可以看到 （我所理解的） mainline 示意圖，由於我們上一部已經將所有的 Power Level Event 排好序了，我們接下來要處理的就剩下 Power Level Event 之間的一般狀態事件（Normal state events）了，由於一些狀態事件操作依然需要權限（像是更改聊天室圖像至少要 Power 50）因此我們需要為每個狀態事件找他們對應的、最接近的 Power Level Event
以上圖為例，Bob 與 Alice 皆嘗試在 Power Level Event 2（之後簡稱 PLE 好了）與 3 之間發送事件，然而對於 Bob 發送的事件來說，其需要追朔到 PLE 1 才能找到他的權限，而對於 Alice 發送的事件，因為 PLE 2 就設定其相關權限，因此只需要追朔到 PLE 2
以上「對應的 PLE」事實上就是主要判斷一般狀態事件先後順序的依據，其排序規則如下：
- 較晚的 PLE 優先
- 較早時間戳的優先（同 Reverse Topo）
- ID 小的優先（同 Reverse Topo）
Re-apply unconflicted state
這塊就是最後的檢查，以防止以上的操作更改到原本的 unconflicted states （由於 unconflicted states 在這個流程中視為 ground truth 不能被更改），所以就是把原始的 unconflicted states 覆寫一次
結論
雖然說為了寫文章所以重複讀了幾次，但是感覺還是有點雲裡霧裡，大概知道他在幹什麼，但是感覺細節上還是接不太上，像是 Auth Event 真正的定義是啥？還有從 Reverse topo 到 Mainline 具體要怎麼轉？我下一步打算直接去看它們 Homeserver 的原始碼（synapse 是目前比較穩定的，但是他是用我很討厭的 python 寫的；他們好像打算用 Go 重新寫，也就是 dendrite，我打算先去 Synapse 看一下到底麼運作的，然後再去 dendrite 看有沒有啥可以貢獻的）
Btw Synapse 那邊提到 Homeserver 的負擔很大，我到是挺好奇為啥的（e.g. 為啥 Matrix 有這個問題別的通訊軟體沒有），感覺可以研究看看，寫一篇分析啥的
後記
最近這幾天終於回到實驗室了，想說正好可以用實驗室的網路看能不能直接連到 matrix.org 上
會這麼說是因為我前一陣子心血來潮想試試看 matrix.org 有沒有上 gfw list XDD → 結果好像一點都不意外的上了
如果嘗試在牆內連到 matrix.org 上呢，你會收到 RST 的回覆，詳情可以自己去 Google 下，簡單來說就是有一個在中間幫忙傳的機掰節點不做它該它該做的事，反而在那邊亂，對你跟接收者說「阿東西掉囉」
（這種攻擊實務面來說其實蠻難擋的，應該說之前修完段老師的資安之後，對網路上的這些有的沒的越來越覺得沒有希望了）
結果跑到實驗室網路，發現也看不到 matrix.org （也被 RST 了），不僅如此我用其他無線網路加上台灣學術網的 VPN 也同樣被 RST …
這代表很有可能在進到 VPN 之前就被看到並且 RST 了，有趣的是像是臉書 / Google 都可以正常看，但是 matrix.org 這種小網站卻被封了，這有可能代表內部網路的審查機制是用白名單
害我現在只能趁還能看得到的時候（某個無線網 ＋ VPN 可以）趕快把網頁印成 PDF 之後看，莫名其妙的克難
這同時也面向證明去中心化的加密通訊是必要的阿 =)