Initial cut at signature verification.

5 files changed, 178 insertions, 17 deletions

diff --git a/synapse/api/room_versions.py b/synapse/api/room_versions.py
index 25c105a4c8..21c3efcfde 100644
--- a/synapse/api/room_versions.py
+++ b/synapse/api/room_versions.py
@@ -30,12 +30,14 @@ class EventFormatVersions:
     ROOM_V1_V2 = 1  # $id:server event id format: used for room v1 and v2
     ROOM_V3 = 2  # MSC1659-style $hash event id format: used for room v3
     ROOM_V4_PLUS = 3  # MSC1884-style $hash format: introduced for room v4
+    LINEARIZED = 4  # Delegated Linearized event
 
 
 KNOWN_EVENT_FORMAT_VERSIONS = {
     EventFormatVersions.ROOM_V1_V2,
     EventFormatVersions.ROOM_V3,
     EventFormatVersions.ROOM_V4_PLUS,
+    EventFormatVersions.LINEARIZED,
 }
 
 
@@ -108,6 +110,7 @@ class RoomVersion:
     msc3931_push_features: Tuple[str, ...]  # values from PushRuleRoomFlag
     # MSC3989: Redact the origin field.
     msc3989_redaction_rules: bool
+    linearized_matrix: bool
 
 
 class RoomVersions:
@@ -131,6 +134,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V2 = RoomVersion(
         "2",
@@ -152,6 +156,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V3 = RoomVersion(
         "3",
@@ -173,6 +178,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V4 = RoomVersion(
         "4",
@@ -194,6 +200,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V5 = RoomVersion(
         "5",
@@ -215,6 +222,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V6 = RoomVersion(
         "6",
@@ -236,6 +244,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     MSC2176 = RoomVersion(
         "org.matrix.msc2176",
@@ -257,6 +266,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V7 = RoomVersion(
         "7",
@@ -278,6 +288,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V8 = RoomVersion(
         "8",
@@ -299,6 +310,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V9 = RoomVersion(
         "9",
@@ -320,6 +332,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     MSC3787 = RoomVersion(
         "org.matrix.msc3787",
@@ -341,6 +354,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     MSC3821 = RoomVersion(
         "org.matrix.msc3821.opt1",
@@ -362,6 +376,7 @@ class RoomVersions:
         msc3821_redaction_rules=True,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     V10 = RoomVersion(
         "10",
@@ -383,6 +398,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     MSC1767v10 = RoomVersion(
         # MSC1767 (Extensible Events) based on room version "10"
@@ -405,6 +421,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(PushRuleRoomFlag.EXTENSIBLE_EVENTS,),
         msc3989_redaction_rules=False,
+        linearized_matrix=False,
     )
     MSC3989 = RoomVersion(
         "org.matrix.msc3989",
@@ -426,6 +443,7 @@ class RoomVersions:
         msc3821_redaction_rules=False,
         msc3931_push_features=(),
         msc3989_redaction_rules=True,
+        linearized_matrix=False,
     )
     MSC3820opt2 = RoomVersion(
         # Based upon v10
@@ -448,6 +466,29 @@ class RoomVersions:
         msc3821_redaction_rules=True,  # Used by MSC3820
         msc3931_push_features=(),
         msc3989_redaction_rules=True,  # Used by MSC3820
+        linearized_matrix=False,
+    )
+    LINEARIZED = RoomVersion(
+        "org.matrix.i-d.ralston-mimi-linearized-matrix.00",
+        RoomDisposition.UNSTABLE,
+        EventFormatVersions.LINEARIZED,
+        StateResolutionVersions.V2,
+        enforce_key_validity=True,
+        special_case_aliases_auth=False,
+        strict_canonicaljson=True,
+        limit_notifications_power_levels=True,
+        msc2175_implicit_room_creator=True,
+        msc2176_redaction_rules=True,
+        msc3083_join_rules=True,
+        msc3375_redaction_rules=True,
+        msc2403_knocking=True,
+        msc3389_relation_redactions=False,
+        msc3787_knock_restricted_join_rule=True,
+        msc3667_int_only_power_levels=True,
+        msc3821_redaction_rules=False,
+        msc3931_push_features=(),
+        msc3989_redaction_rules=True,
+        linearized_matrix=True,
     )
 
 
@@ -468,6 +509,7 @@ KNOWN_ROOM_VERSIONS: Dict[str, RoomVersion] = {
         RoomVersions.V10,
         RoomVersions.MSC3989,
         RoomVersions.MSC3820opt2,
+        RoomVersions.LINEARIZED,
     )
 }
 
diff --git a/synapse/event_auth.py b/synapse/event_auth.py
index 3aaf53dfbd..84fe9d3c3e 100644
--- a/synapse/event_auth.py
+++ b/synapse/event_auth.py
@@ -55,7 +55,7 @@ from synapse.types import (
 
 if typing.TYPE_CHECKING:
     # conditional imports to avoid import cycle
-    from synapse.events import EventBase
+    from synapse.events import EventBase, FrozenLinearizedEvent
     from synapse.events.builder import EventBuilder
 
 logger = logging.getLogger(__name__)
@@ -117,7 +117,7 @@ def validate_event_for_room_version(event: "EventBase") -> None:
         if not is_invite_via_3pid:
             raise AuthError(403, "Event not signed by sender's server")
 
-    if event.format_version in (EventFormatVersions.ROOM_V1_V2,):
+    if event.format_version == EventFormatVersions.ROOM_V1_V2:
         # Only older room versions have event IDs to check.
         event_id_domain = get_domain_from_id(event.event_id)
 
@@ -125,6 +125,22 @@ def validate_event_for_room_version(event: "EventBase") -> None:
         if not event.signatures.get(event_id_domain):
             raise AuthError(403, "Event not signed by sending server")
 
+    if event.format_version == EventFormatVersions.LINEARIZED:
+        assert isinstance(event, FrozenLinearizedEvent)
+
+        # TODO Are these handling DAG-native events properly? Is the null-checks
+        # a bypass?
+
+        # CHeck that the authorizing domain signed it.
+        owner_server = event.owner_server
+        if owner_server and not event.signatures.get(owner_server):
+            raise AuthError(403, "Event not signed by owner server")
+
+        # If this is a delegated PDU, check the original domain signed it.
+        delegated_server = event.delegated_server
+        if delegated_server and not event.signatures.get(delegated_server):
+            raise AuthError(403, "Event not signed by delegated server")
+
     is_invite_via_allow_rule = (
         event.room_version.msc3083_join_rules
         and event.type == EventTypes.Member
diff --git a/synapse/events/__init__.py b/synapse/events/__init__.py
index 75b62adb33..063abb9c93 100644
--- a/synapse/events/__init__.py
+++ b/synapse/events/__init__.py
@@ -39,7 +39,7 @@ from unpaddedbase64 import encode_base64
 
 from synapse.api.constants import RelationTypes
 from synapse.api.room_versions import EventFormatVersions, RoomVersion, RoomVersions
-from synapse.types import JsonDict, RoomStreamToken, StrCollection
+from synapse.types import JsonDict, RoomStreamToken, StrCollection, get_domain_from_id
 from synapse.util.caches import intern_dict
 from synapse.util.frozenutils import freeze
 from synapse.util.stringutils import strtobool
@@ -334,12 +334,24 @@ class EventBase(metaclass=abc.ABCMeta):
     state_key: DictProperty[str] = DictProperty("state_key")
     type: DictProperty[str] = DictProperty("type")
     user_id: DictProperty[str] = DictProperty("sender")
+    # Should only matter for Linearized Matrix.
+    owner_server: DictProperty[Optional[str]] = DefaultDictProperty(
+        "owner_server", None
+    )
+    delegated_server: DictProperty[Optional[str]] = DefaultDictProperty(
+        "delegated_server", None
+    )
 
     @property
     def event_id(self) -> str:
         raise NotImplementedError()
 
     @property
+    def pdu_domain(self) -> str:
+        """The domain which added this event to the DAG."""
+        return get_domain_from_id(self.sender)
+
+    @property
     def membership(self) -> str:
         return self.content["membership"]
 
@@ -591,6 +603,45 @@ class FrozenEventV3(FrozenEventV2):
         return self._event_id
 
 
+class FrozenLinearizedEvent(FrozenEventV3):
+    """
+    Represents a Delegated Linearized PDU.
+    """
+
+    format_version = EventFormatVersions.LINEARIZED
+
+    @property
+    def pdu_domain(self) -> str:
+        """The domain which added this event to the DAG.
+
+        It could be the authorized server or the sender."""
+        if self.delegated_server is not None:
+            return self.delegated_server
+        return super().pdu_domain
+
+    def get_linearized_pdu_json(self, /, delegated: bool) -> JsonDict:
+        # if delegated and self.delegated_server is None:
+        #     # TODO Better error.
+        #     raise ValueError("Invalid")
+        # TODO Is this form correct? Are there other fields?
+        result = {
+            "room_id": self.room_id,
+            "type": self.type,
+            # Should state key be left out if it isn't a state event?
+            "state_key": self.state_key,
+            "sender": self.sender,
+            "origin_server_ts": self.origin_server_ts,
+            # If we want the delegated version use the owner_server
+            # if it exists.
+            "owner_server": self.delegated_server,
+            "content": self.content,
+            "hashes": self.hashes,
+        }
+        if delegated and self.delegated_server:
+            result["delegated_server"] = self.delegated_server
+        return result
+
+
 def _event_type_from_format_version(
     format_version: int,
 ) -> Type[Union[FrozenEvent, FrozenEventV2, FrozenEventV3]]:
@@ -610,6 +661,8 @@ def _event_type_from_format_version(
         return FrozenEventV2
     elif format_version == EventFormatVersions.ROOM_V4_PLUS:
         return FrozenEventV3
+    elif format_version == EventFormatVersions.LINEARIZED:
+        return FrozenLinearizedEvent
     else:
         raise Exception("No event format %r" % (format_version,))
 
diff --git a/synapse/events/utils.py b/synapse/events/utils.py
index a55efcca56..592e109e22 100644
--- a/synapse/events/utils.py
+++ b/synapse/events/utils.py
@@ -64,6 +64,10 @@ def prune_event(event: EventBase) -> EventBase:
     the user has specified, but we do want to keep necessary information like
     type, state_key etc.
     """
+
+    # TODO Check users of prune_event and prune_event_dict to ensure they shouldn't
+    # be doing something with linearized matrix.
+
     pruned_event_dict = prune_event_dict(event.room_version, event.get_dict())
 
     from . import make_event_from_dict
diff --git a/synapse/federation/federation_base.py b/synapse/federation/federation_base.py
index b77022b406..eff887433c 100644
--- a/synapse/federation/federation_base.py
+++ b/synapse/federation/federation_base.py
@@ -20,7 +20,7 @@ from synapse.api.errors import Codes, SynapseError
 from synapse.api.room_versions import EventFormatVersions, RoomVersion
 from synapse.crypto.event_signing import check_event_content_hash
 from synapse.crypto.keyring import Keyring
-from synapse.events import EventBase, make_event_from_dict
+from synapse.events import EventBase, FrozenLinearizedEvent, make_event_from_dict
 from synapse.events.utils import prune_event, validate_canonicaljson
 from synapse.http.servlet import assert_params_in_dict
 from synapse.logging.opentracing import log_kv, trace
@@ -174,7 +174,7 @@ async def _check_sigs_on_pdu(
 
     # we want to check that the event is signed by:
     #
-    # (a) the sender's server
+    # (a) the sender's (or the delagated sender's) server
     #
     #     - except in the case of invites created from a 3pid invite, which are exempt
     #     from this check, because the sender has to match that of the original 3pid
@@ -193,19 +193,22 @@ async def _check_sigs_on_pdu(
     # let's start by getting the domain for each pdu, and flattening the event back
     # to JSON.
 
-    # First we check that the sender event is signed by the sender's domain
+    # First we check that the sender event is signed by the domain of the server
+    # which added it to the DAG.
     # (except if its a 3pid invite, in which case it may be sent by any server)
+    pdu_domain = pdu.pdu_domain
     sender_domain = get_domain_from_id(pdu.sender)
+    origin_server_ts_for_signing = (
+        pdu.origin_server_ts if room_version.enforce_key_validity else 0
+    )
     if not _is_invite_via_3pid(pdu):
         try:
             await keyring.verify_event_for_server(
-                sender_domain,
-                pdu,
-                pdu.origin_server_ts if room_version.enforce_key_validity else 0,
+                pdu_domain, pdu, origin_server_ts_for_signing
             )
         except Exception as e:
             raise InvalidEventSignatureError(
-                f"unable to verify signature for sender domain {sender_domain}: {e}",
+                f"unable to verify signature for PDU domain {pdu_domain}: {e}",
                 pdu.event_id,
             ) from None
 
@@ -218,9 +221,7 @@ async def _check_sigs_on_pdu(
         if event_domain != sender_domain:
             try:
                 await keyring.verify_event_for_server(
-                    event_domain,
-                    pdu,
-                    pdu.origin_server_ts if room_version.enforce_key_validity else 0,
+                    event_domain, pdu, origin_server_ts_for_signing
                 )
             except Exception as e:
                 raise InvalidEventSignatureError(
@@ -241,16 +242,61 @@ async def _check_sigs_on_pdu(
         )
         try:
             await keyring.verify_event_for_server(
-                authorising_server,
-                pdu,
-                pdu.origin_server_ts if room_version.enforce_key_validity else 0,
+                authorising_server, pdu, origin_server_ts_for_signing
             )
         except Exception as e:
             raise InvalidEventSignatureError(
-                f"unable to verify signature for authorising serve {authorising_server}: {e}",
+                f"unable to verify signature for authorising server {authorising_server}: {e}",
                 pdu.event_id,
             ) from None
 
+    # If this is a linearized PDU we may need to check signatures of the owner
+    # and sender.
+    if room_version.event_format == EventFormatVersions.LINEARIZED:
+        assert isinstance(pdu, FrozenLinearizedEvent)
+
+        # Check that the fields are not invalid.
+        if pdu.delegated_server and not pdu.owner_server:
+            raise InvalidEventSignatureError(
+                "PDU missing owner_server", pdu.event_id
+            ) from None
+
+        # If the event was sent from a linear server, check the authorized server.
+        #
+        # Note that the signature of the delegated server, if one exists, is
+        # checked against the full PDU above.
+        if pdu.owner_server:
+            # Construct the Linear PDU and check the signature against the sender.
+            #
+            # If the owner & sender are the same, then only a Delegated Linear PDU
+            # is created (the Linear PDU is not signed by itself).
+            if pdu.owner_server != sender_domain:
+                try:
+                    await keyring.verify_json_for_server(
+                        sender_domain,
+                        pdu.get_linearized_pdu_json(delegated=False),
+                        origin_server_ts_for_signing,
+                    )
+                except Exception as e:
+                    raise InvalidEventSignatureError(
+                        f"unable to verify signature for sender {sender_domain}: {e}",
+                        pdu.event_id,
+                    ) from None
+
+            # Construct the Delegated Linear PDU and check the signature
+            # against owner_server.
+            try:
+                await keyring.verify_json_for_server(
+                    pdu.owner_server,
+                    pdu.get_linearized_pdu_json(delegated=True),
+                    origin_server_ts_for_signing,
+                )
+            except Exception as e:
+                raise InvalidEventSignatureError(
+                    f"unable to verify signature for owner_server {pdu.owner_server}: {e}",
+                    pdu.event_id,
+                ) from None
+
 
 def _is_invite_via_3pid(event: EventBase) -> bool:
     return (