Possible optimsation in the definition of auth difference #1118
Description
Link to problem area:
https://spec.matrix.org/unstable/rooms/v10/#definitions
Auth difference. The auth difference is calculated by first calculating the full auth chain for each state
$S_i$ , that is the union of the auth chains for each event in$S_i$ , and then taking every event that doesn’t appear in every auth chain. If$C_i$ is the full auth chain of$S_i$ , then the auth difference is $\bigcup_i C_i − \bigcap_i C_i$.
Issue
As written, this requires fetching and inspecting the auth chains for all events in each state map
That is, we must process the set of events
I claim that we only need to fetch and inspect the auth chains of events in the conflicted state set
Proof.
$$\begin{align*}
\DeclareMathOperator\fullauthchain{FullAuthChain}
\DeclareMathOperator\authchain{AuthChain}
\text{auth difference as written} &= \bigcup_i C_i − \bigcap_i C_i \
&= \bigcup_i \fullauthchain(S_i) − \bigcap_i \fullauthchain(S_i) \
&= \bigcup_i \left(\bigcup_{e \in S_i} \authchain(e) \right) − \bigcap_i \left(\bigcup_{e \in S_i} \authchain(e) \right) \
&= \bigcup_{e \in \bigcup_i S_i} \authchain(e) − \bigcap_i \left(\bigcup_{e \in S_i} \authchain(e) \right)
\end{align*}$$
Suppose that
Then:
-
$\authchain(f)$ is contained in the first term$\bigcup_{e \in \bigcup_i S_i} \authchain(e)$ . -
$\authchain(f)f$ is contained in the second term$\bigcap_i \left(\bigcup_{e \in S_i} \authchain(e) \right)$ .
Therefore Therefore we so we can omit events INCORRECT, SEE BELOW.
$$\begin{align*}
\DeclareMathOperator\fullauthchain{FullAuthChain}
\DeclareMathOperator\authchain{AuthChain}
\text{auth difference as written} &= \bigcup_{e \in \bigcup_i S_i} \authchain(e) − \bigcap_i \left(\bigcup_{e \in S_i} \authchain(e) \right) \
&= \bigcup_{e \in \bigcup_i S_i - \bigcap_i S_i} \authchain(e) − \bigcap_i \left(\bigcup_{e \in S_i - \bigcap_i S_i} \authchain(e) \right) \
&= \bigcup_{e \in S_\text{conflicted}} \authchain(e) − \bigcap_i \left(\bigcup_{e \in S_i - S_\text{unconflicted}} \authchain(e) \right) \
&= \fullauthchain (S_\text{conflicted}) − \bigcap_i \fullauthchain (S_i - S_\text{unconflicted})
\end{align*}$$
If this reasoning is sound, one could argue that this is an implementation detail rather than a spec concern. But I think the idea is interesting enough to consider a change to the spec anyway.
It was not sound.