房间版本 2

本房间版本在 版本 1 的基础上进行了改进，采用了更优的状态解析算法。

客户端注意事项

本房间版本未引入与客户端相关的新注意事项。本地实现消息删除算法的客户端应参考下方的 消息删除 部分，全面了解该算法。

服务器实现要素

房间版本 2 采用了 房间版本 1 的基础组件，仅更改了状态解析算法。

状态解析

[New in this version]

事件 E 之后的房间状态 S′(E) 由事件 E 之前的房间状态 S(E) 定义，并且依赖于 E 是状态事件还是消息事件：

• 如果 E 是一条消息事件，则 S′(E) = S(E)。
• 如果 E 是一条状态事件，则 S′(E) 与 S(E) 相同，除了其与 E 的 event_type 和 state_key 对应的项被 E 的 event_id 替换。

事件 E 之前的房间状态 S(E) 是 prev_event 集合 {E₁, E₂, …} 之后的状态集合 {S′(E₁), S′(E₂), …} 的 合并与决议结果。如何对一组状态进行合并与决议，见下述算法。

定义

版本 2 房间的状态合并算法使用如下定义，并以房间状态集 {S₁, S₂, …} 为输入：

权限事件（Power events）。
权限事件 指具有类型 m.room.power_levels 或 m.room.join_rules 的状态事件，或者类型为 m.room.member 且 membership 字段为 leave 或 ban，且 sender 与 state_key 不一致的状态事件。其核心思想为：权限事件是那些可能移除某人在房间内某项操作权限的事件。

无冲突状态映射与冲突状态集。
状态映射 S_i 的 key 为形如 (event_type, state_key) 的字符串二元组 K，对应的 value V 为一个状态事件。所有 S_i 的 (K, V) 键值对可划分为两个集合：如果给定 key K 在所有 S_i 出现，且值 V 在每个状态映射都一致，则此 (K, V) 属于 无冲突状态映射；否则，V 属于 冲突状态集。

注意，无冲突状态映射每个 key K 只会有一个事件，而冲突状态集可能因同 key 包含多个事件。

鉴权链（Auth chain）。
事件 E 的 鉴权链，是包含 E 的所有鉴权事件（auth events）、所有这些事件的鉴权事件，递归回溯直到房间创建为止的集合。换句话说，就是通过事件的 auth_events 链接遍历可达的所有事件。

鉴权差集（Auth difference）。
鉴权差集 的计算方式如下：首先对每个状态 S_i，计算其完全鉴权链，即该状态中每个事件的鉴权链的并集。然后找出那些未在所有鉴权链中都出现的事件。若 C_i 表示 S_i 的完全鉴权链，则鉴权差集为 ∪ C_i − ∩ C_i。

完整冲突集（Full conflicted set）。
完整冲突集 是冲突状态集与鉴权差集的并集。

逆拓扑权限排序（Reverse topological power ordering）。
一组事件的 逆拓扑权限排序，是按鉴权事件形成的有向无环图（DAG）进行拓扑排序，得到字典序最小的排序，并从最早事件到最晚事件排列。比较两个拓扑排序确定哪一个字典序更小时，事件的比较关系如下：对事件 x 和 y，若

1. x 的发送者的权限级别 高于 y 的发送者（以各自的 auth_event 查得）；或
2. 发送者权限级别相同，但 x 的 origin_server_ts 小于 y；或
3. 权限级别与 origin_server_ts 都相同，但 x 的 event_id 小于 y 的 event_id，

则 x < y。

逆拓扑权限排序可用 Kahn 算法进行拓扑排序，每步从候选顶点中按上述比较关系选择最小顶点。

主链排序（Mainline ordering）。
令 P = P₀ 为某个 m.room.power_levels 事件。从 i = 0 开始，反复获取 P_i+1，即 P_i 的 auth_events 中类型为 m.room.power_levels 的事件。每次自增 i，直到 P_i 的 auth_events 中没有 m.room.power_levels 事件为止。P₀ 的 主链 为 [P₀ , P₁, … , P_n]。

若另有事件 e = e₀（可以是另一个 m.room.power_levels 事件），可以构造类似事件链 [e₁, …, e_m]，其中 e_j+1 为 e_j 的 auth_events 中的 m.room.power_levels 事件，e_m 没有再指向任何 m.room.power_levels 事件。（注意 e₀ 本身不包含在该列表中，也有可能该列表为空，因为 e 可能没有引用过 m.room.power_levels 事件。）

对这两条列表进行如下比较：

• 查找最小的 j ≥ 1，使得 e_j 属于 P 的主链；
• 若存在这样的 j，则 e_j = P_i，且 i 唯一、i ≥ 0；否则令 i = ∞，其中 ∞ 为一个大于任何整数的特殊标记值；
• 无论哪种情况，e 的 主链位置 就是 i。

以 P 计算得主链位置后，基于 P 的主链排序，就是将一组事件按以下比较关系（从小到大）排序：对事件 x 和 y，若

1. x 的主链位置 大于 y（即 x 的鉴权链基于主链上的较早事件）；或
2. 主链位置相同，但 x 的 origin_server_ts 小于 y；或
3. 主链位置、origin_server_ts 都相同，但 x 的 event_id 小于 y，

则 x < y。

迭代鉴权检查（Iterative auth checks）。
迭代鉴权检查算法 的输入是初始房间状态和已排序的状态事件列表。它通过遍历事件列表，将符合授权规则的状态事件依次应用到房间状态上。若某状态事件未通过授权规则，则忽略该事件。如果验证授权规则时缺少某个必须的 (event_type, state_key) key，则用事件 auth_events 中相应的状态事件（若未被拒绝）替代。

算法

一组状态的 合并与决议 按如下步骤执行：

1. 选取出现在 完整冲突集 内的所有权限事件组成集合 X。对于每一个权限事件 P，将 P 的鉴权链中同时属于完整冲突集的事件也加入 X。对 X 按 逆拓扑权限排序 排序为列表。
2. 从 无冲突状态映射 作为起点，对上一步得到的事件列表应用迭代鉴权检查算法，得出部分已决议状态。
3. 将第 1 步未涉及的所有剩余事件按第 2 步已决议状态中的权限等级，用主链排序确定顺序。
4. 对上述部分已决议状态及新排序的事件列表，再次应用迭代鉴权检查算法。
5. 用无冲突状态映射中的相同 key 事件（若存在）替换当前结果中对应事件，得出最终合并决议状态。

被拒绝的事件

由于基于事件当前状态（而非鉴权链）验证授权而被拒绝的事件，除非另有特别说明，在算法中仍按常规方式处理。

注意，那些由于无法通过其鉴权链授权而被拒绝的事件不应出现在此流程中，因为他们不会出现在状态集合之内（本算法只使用状态集中的事件，或状态集中事件的鉴权链中的事件）。

被拒绝的鉴权事件（auth events）故意不参与迭代鉴权检查，因为检查过程中不会对鉴权事件重新授权（但非鉴权事件则会被检查）。

与 v1 保持一致的内容

以下部分自 v1 起未作修改，仅为内容完整性保留在此。

消息删除

在接收到删除事件后，服务器必须移除除以下列表外的所有键：

• event_id
• type
• room_id
• sender
• state_key
• content
• hashes
• signatures
• depth
• prev_events
• prev_state
• auth_events
• origin
• origin_server_ts
• membership

对于 content 对象，也必须移除除下列类型允许外的所有键：

• m.room.member 允许键 membership。
• m.room.create 允许键 creator。
• m.room.join_rules 允许键 join_rule。
• m.room.power_levels 允许的键有 ban、events、events_default、kick、redact、state_default、users、 users_default。
• m.room.aliases 允许键 aliases。
• m.room.history_visibility 允许 键 history_visibility。

事件 ID

一个事件只能有一个事件ID。在此房间版本中，事件ID的格式为：

$opaque_id:domain

其中，domain 是创建该房间的主服务器的服务器名称，而 opaque_id 是在本地唯一的字符串。

domain 仅用于命名空间，以避免不同主服务器之间标识符发生冲突的风险。并不意味着相关房间或事件一定还在对应的主服务器上可用。

事件格式

本版本房间中的事件具有如下结构：

{
  "auth_events": [
    [
      "$af232176:example.org",
      {
        "sha256": "abase64encodedsha256hashshouldbe43byteslong"
      }
    ]
  ],
  "content": {
    "key": "value"
  },
  "depth": 12,
  "event_id": "$a4ecee13e2accdadf56c1025:example.com",
  "hashes": {
    "sha256": "thishashcoversallfieldsincasethisisredacted"
  },
  "origin_server_ts": 1404838188000,
  "prev_events": [
    [
      "$af232176:example.org",
      {
        "sha256": "abase64encodedsha256hashshouldbe43byteslong"
      }
    ]
  ],
  "room_id": "!UcYsUzyxTGDxLBEvLy:example.org",
  "sender": "@alice:example.com",
  "signatures": {
    "example.com": {
      "ed25519:key_version": "these86bytesofbase64signaturecoveressentialfieldsincludinghashessocancheckredactedpdus"
    }
  },
  "type": "m.room.message",
  "unsigned": {
    "age": 4612
  }
}

已弃用的事件内容模式

发送到此版本房间中的事件，其格式可能与其常规模式不同。此类情况将在此处进行说明。

m.room.power_levels 事件支持以字符串形式传递数值

为了与早期实现保持向后兼容， m.room.power_levels 事件中的每个整数值属性 都可以被编码为字符串而非整数。这包括 events、notifications 和 users 属性中的嵌套值。例如，以下是在此房间版本中有效的 m.room.power_levels 事件：

{
  "content": {
    "ban": "50",
    "events": {
      "m.room.power_levels": "100"
    },
    "events_default": "0",
    "state_default": "50",
    "users": {
      "@example:localhost": "100"
    },
    "users_default": "0"
  },
  "origin_server_ts": 1432735824653,
  "room_id": "!jEsUZKDJdhlrceRyVU:example.org",
  "sender": "@example:example.org",
  "state_key": "",
  "type": "m.room.power_levels"
}

当该值表示整数时，必须符合以下格式：

• 仅包含一个十进制整数，不允许浮点数或小数点，可以带任意数量的前导零（如 "100"、"000100"）；
• 可选地在整数前面加一个 - 或 + 字符（如 "+100"、"-100"）；
• 可选地在前后添加任意数量的空白字符（如 " 100 "、" 00100 "、" +100 "、" -100 "）。

授权规则

影响授权的状态事件类型包括：

• m.room.create
• m.room.member
• m.room.join_rules
• m.room.power_levels
• m.room.third_party_invite

规则如下：

1. 若类型为 m.room.create：
   1. 若有任何 prev_events，则拒绝。
   2. 若 room_id 的域名与 sender 的域名不符，则拒绝。
   3. 若 content.room_version 存在但不是识别的版本，则拒绝。
   4. 若 content 没有 creator 属性，则拒绝。
   5. 否则，允许。
2. 针对事件的 auth_events：
   1. 若某一 type 与 state_key 组合存在重复，则拒绝。
   2. 若存在其 type 与 state_key 不符合 认证事件选择 算法（详见服务器规范）的项，则拒绝。
   3. 若有事件本身因 接收 PDU 时执行的检查 被拒绝，则拒绝。
   4. 若未能在条目中找到 m.room.create 事件，则拒绝。
3. 若房间状态中的 m.room.create 事件的 content 包含 m.federate 属性且值为 false，且此事件的 sender 域名不与创建事件的 sender 域名一致，则拒绝。
4. 若类型为 m.room.aliases：
   1. 若事件无 state_key，则拒绝。
   2. 若发送者域名与 state_key 不符，则拒绝。
   3. 否则，允许。
5. 若类型为 m.room.member：
   1. 若没有 state_key 属性，或 content 中无 membership 属性，则拒绝。
   2. 若 membership 为 join：
      1. 若唯一的前序事件为 m.room.create 且 state_key 为创建者，则允许。
      2. 若 sender 与 state_key 不符，则拒绝。
      3. 若 sender 被封禁，则拒绝。
      4. 若 join_rule 为 invite，则当 membership 状态是 invite 或 join 时，允许。
      5. 若 join_rule 为 public，则允许。
      6. 否则，拒绝。
   3. 若 membership 为 invite：
      1. 若 content 含有 third_party_invite 属性：
         1. 若 目标用户 被封禁，则拒绝。
         2. 若 content.third_party_invite 无 signed 属性，则拒绝。
         3. 若 signed 无 mxid 和 token 属性，则拒绝。
         4. 若 mxid 与 state_key 不符，则拒绝。
         5. 若当前房间状态中无 state_key 为 token 的 m.room.third_party_invite 事件，则拒绝。
         6. 若 sender 与该 m.room.third_party_invite 的 sender 不符，则拒绝。
         7. 若 signed 中的任意签名与该 m.room.third_party_invite 事件中的任一公钥匹配，则允许。公钥位于 m.room.third_party_invite 的 content 中：
            1. 单个公钥存于 public_key 属性；
            2. 公钥列表存于 public_keys 属性。
         8. 否则，拒绝。
      2. 若 sender 当前成员状态不是 join，则拒绝。
      3. 若 目标用户 当前成员状态是 join 或 ban，则拒绝。
      4. 若 sender 权限等级大于或等于 邀请等级，则允许。
      5. 否则，拒绝。
   4. 若 membership 为 leave：
      1. 若 sender 与 state_key 匹配，则仅当其当前成员状态为 invite 或 join 时允许。
      2. 若 sender 当前成员状态不是 join，则拒绝。
      3. 若 目标用户 当前成员状态为 ban 且 sender 权限等级低于 封禁等级，则拒绝。
      4. 若 sender 权限等级大于等于 踢人等级，且 目标用户 权限等级小于 sender 权限等级，则允许。
      5. 否则，拒绝。
   5. 若 membership 为 ban：
      1. 若 sender 当前成员状态不是 join，则拒绝。
      2. 若 sender 权限等级大于等于 封禁等级，且 目标用户 权限等级低于 sender 权限等级，则允许。
      3. 否则，拒绝。
   6. 其他情况下，未知成员状态。拒绝。
6. 若 sender 当前成员状态不是 join，则拒绝。
7. 若类型为 m.room.third_party_invite：
   1. 仅当 sender 当前权限等级大于等于 邀请等级 时允许。
8. 若事件类型的 所需权限等级 大于 sender 权限等级，则拒绝。
9. 若事件的 state_key 以 @ 开头且与 sender 不符，则拒绝。
10. 若类型为 m.room.power_levels：
    1. 若 content 中 users 属性不是键为有效用户ID且值为整数（或整数字符串）的对象，则拒绝。
    2. 若房间中没有前序的 m.room.power_levels 事件，则允许。
    3. 针对 users_default、events_default、state_default、ban、redact、kick、invite 属性，在添加、更改或移除时，针对每个变动：
       1. 若当前值大于 sender 当前权限等级，则拒绝。
       2. 若新值大于 sender 当前权限等级，则拒绝。
    4. 针对 events 属性中被更改或移除的每一项：
       1. 若当前值大于 sender 当前权限等级，则拒绝。
    5. 针对 events 属性中被添加或更改的每一项：
       1. 若新值大于 sender 当前权限等级，则拒绝。
    6. 针对 users 属性（除 sender 本人）的被更改或移除的每一项：
       1. 若当前值大于等于 sender 当前权限等级，则拒绝。
    7. 针对 users 属性被添加或更改的每一项：
       1. 若新值大于 sender 当前权限等级，则拒绝。
    8. 否则，允许。
11. 若类型为 m.room.redaction：
    1. 若 sender 权限等级大于等于 撤回等级，则允许。
    2. 若被撤回事件的 event_id 域名与 m.room.redaction 的 event_id 域名一致，则允许。
    3. 否则，拒绝。
12. 否则，允许。

规范 JSON

出于附录中所述的原因，服务器不得强制严格遵循所规定的 JSON 格式。