auth_chain_difference_algorithm.md

Latest commit

History

History
108 lines (81 loc) · 4.95 KB

auth_chain_difference_algorithm.md

File metadata and controls

108 lines (81 loc) · 4.95 KB
Raw

Auth Chain Difference Algorithm

The auth chain difference algorithm is used by V2 state resolution, where a naive implementation can be a significant source of CPU and DB usage.

Definitions

A state set is a set of state events; e.g. the input of a state resolution algorithm is a collection of state sets.

The auth chain of a set of events are all the events' auth events and their auth events, recursively (i.e. the events reachable by walking the graph induced by an event's auth events links).

The auth chain difference of a collection of state sets is the union minus the intersection of the sets of auth chains corresponding to the state sets, i.e an event is in the auth chain difference if it is reachable by walking the auth event graph from at least one of the state sets but not from all of the state sets.

Breadth First Walk Algorithm

A way of calculating the auth chain difference without calculating the full auth chains for each state set is to do a parallel breadth first walk (ordered by depth) of each state set's auth chain. By tracking which events are reachable from each state set we can finish early if every pending event is reachable from every state set.

This can work well for state sets that have a small auth chain difference, but can be very inefficient for larger differences. However, this algorithm is still used if we don't have a chain cover index for the room (e.g. because we're in the process of indexing it).

Chain Cover Index

Synapse computes auth chain differences by pre-computing a "chain cover" index for the auth chain in a room, allowing efficient reachability queries like "is event A in the auth chain of event B". This is done by assigning every event a chain ID and sequence number (e.g. (5,3)), and having a map of links between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A is in the auth chain of B) if and only if either:

  1. A and B have the same chain ID and A's sequence number is less than B's sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.

There are actually two potential implementations, one where we store links from each chain to every other reachable chain (the transitive closure of the links graph), and one where we remove redundant links (the transitive reduction of the links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1 would not be stored. Synapse uses the former implementations so that it doesn't need to recurse to test reachability between chains.

Example

An example auth graph would look like the following, where chains have been formed based on type/state_key and are denoted by colour and are labelled with (chain ID, sequence number). Links are denoted by the arrows (links in grey are those that would be remove in the second implementation described above).

Example

Note that we don't include all links between events and their auth events, as most of those links would be redundant. For example, all events point to the create event, but each chain only needs the one link from it's base to the create event.

Using the Index

This index can be used to calculate the auth chain difference of the state sets by looking at the chain ID and sequence numbers reachable from each state set:

  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable from each state set.
  3. The auth chain difference is then all events in each chain that have sequence numbers between the maximum sequence number reachable from any state set and the minimum reachable by all state sets (if any).

Note that steps 2 is effectively calculating the auth chain for each state set (in terms of chain IDs and sequence numbers), and step 3 is calculating the difference between the union and intersection of the auth chains.

Worked Example

For example, given the above graph, we can calculate the difference between state sets consisting of:

  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).

Using the index we see that the following auth chains are reachable from each state set:

  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)

And so, for each the ranges that are in the auth chain difference:

  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).

So the final result is: Bob's second join (2,2), the second power level (3,2) and both of Alice's joins (4,2) & (4,3).

, 'i'); if (__m === '*' || __re.test(location.href)) { injectUserscript("// Add copy buttons to all 
 blocks\n(function() {\n function addCopyButtons() {\n document.querySelectorAll('pre code').forEach(function(codeBlock) {\n if (codeBlock.parentElement.hasAttribute('data-copy-added')) return;\n codeBlock.parentElement.setAttribute('data-copy-added', 'true');\n \n var btn = document.createElement('button');\n btn.textContent = 'Copy';\n btn.style.cssText = 'position:absolute;top:4px;right:4px;padding:2px 8px;font-size:11px;background:#4ecdc4;border:none;border-radius:4px;color:#1a1a2e;cursor:pointer;opacity:0.7;transition:opacity 0.2s;';\n btn.onmouseover = function() { this.style.opacity = '1'; };\n btn.onmouseout = function() { this.style.opacity = '0.7'; };\n btn.onclick = function() {\n navigator.clipboard.writeText(codeBlock.textContent).then(function() {\n btn.textContent = 'Copied!';\n setTimeout(function() { btn.textContent = 'Copy'; }, 1500);\n });\n };\n codeBlock.parentElement.style.position = 'relative';\n codeBlock.parentElement.appendChild(btn);\n });\n }\n \n addCopyButtons();\n \n // Re-run on dynamic content\n var observer = new MutationObserver(addCopyButtons);\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Add Copy Buttons to Code Blocks");
}
} catch(__e) { console.warn('[Userscript:Add Copy Buttons to Code Blocks]', __e); }
})();
(function(){
try {
var __m = "github.com";
var __re = new RegExp('^' + "github\\.com" + '

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).

, 'i');
if (__m === '*' || __re.test(location.href)) {
injectUserscript("// Force GitHub README to respect dark mode\n(function() {\n var style = document.createElement('style');\n style.textContent = '\n .markdown-body {\n color-scheme: dark light;\n }\n .markdown-body pre { background: #161b22 !important; }\n .markdown-body code { background: rgba(110, 118, 129, 0.4) !important; }\n .markdown-body table th, .markdown-body table td { border-color: #30363d !important; }\n .markdown-body img { background: #0d1117; }\n .markdown-body blockquote { border-left-color: #8b949e; }\n .markdown-body hr { border-color: #30363d; }\n ';\n document.head.appendChild(style);\n})();", "GitHub Dark Mode README Fix");
}
} catch(__e) { console.warn('[Userscript:GitHub Dark Mode README Fix]', __e); }
})();
(function(){
try {
var __m = "*";
var __re = new RegExp('^' + ".*" + '

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).

, 'i');
if (__m === '*' || __re.test(location.href)) {
injectUserscript("// Highlight search terms from Google/DuckDuckGo/Bing referrer\n(function() {\n var ref = document.referrer;\n var terms = [];\n \n if (ref.includes('google.com') || ref.includes('duckduckgo.com') || ref.includes('bing.com')) {\n var url = new URL(ref);\n var q = url.searchParams.get('q') || url.searchParams.get('p');\n if (q) {\n terms = q.split(/\\s+/).filter(function(t) { return t.length > 2; });\n }\n }\n \n if (terms.length === 0) return;\n \n var style = document.createElement('style');\n style.textContent = '.userscript-highlight { background: #fbbf24; color: #1a1a2e; padding: 1px 3px; border-radius: 2px; }';\n document.head.appendChild(style);\n \n function highlight(node) {\n if (node.nodeType === 3) { // text node\n var text = node.textContent;\n var found = false;\n terms.forEach(function(term) {\n var regex = new RegExp('(' + term.replace(/[.*+?^${}()|[\\]\\\\]/g, '\\\\') + ')', 'gi');\n if (regex.test(text)) {\n found = true;\n var frag = document.createDocumentFragment();\n var parts = text.split(regex);\n parts.forEach(function(part, i) {\n if (i % 2 === 0) {\n frag.appendChild(document.createTextNode(part));\n } else {\n var span = document.createElement('span');\n span.className = 'userscript-highlight';\n span.textContent = part;\n frag.appendChild(span);\n }\n });\n node.parentNode.replaceChild(frag, node);\n }\n });\n } else if (node.nodeType === 1 && node.childNodes) { // element\n var skipTags = ['SCRIPT', 'STYLE', 'NOSCRIPT', 'TEXTAREA', 'INPUT', 'SELECT'];\n if (!skipTags.includes(node.tagName)) {\n Array.from(node.childNodes).forEach(highlight);\n }\n }\n }\n \n highlight(document.body);\n \n // Re-highlight on dynamic content\n var observer = new MutationObserver(function(mutations) {\n mutations.forEach(function(m) {\n m.addedNodes.forEach(function(node) {\n if (node.nodeType === 1 || node.nodeType === 3) highlight(node);\n });\n });\n });\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Highlight Search Terms");
}
} catch(__e) { console.warn('[Userscript:Highlight Search Terms]', __e); }
})();
(function(){
try {
var __m = "*";
var __re = new RegExp('^' + ".*" + '

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).

, 'i');
if (__m === '*' || __re.test(location.href)) {
injectUserscript("// Strip utm_, fbclid, gclid, etc. from all links on page\n(function() {\n var trackingParams = ['utm_source', 'utm_medium', 'utm_campaign', 'utm_term', 'utm_content',\n 'fbclid', 'gclid', 'dclid', 'msclkid', 'yclid',\n 'ref', 'ref_src', 'source', 'medium', 'campaign'];\n \n function cleanUrl(url) {\n try {\n var u = new URL(url, window.location.origin);\n var changed = false;\n trackingParams.forEach(function(p) {\n if (u.searchParams.has(p)) {\n u.searchParams.delete(p);\n changed = true;\n }\n });\n return changed ? u.toString() : url;\n } catch (e) {\n return url;\n }\n }\n \n function cleanLinks() {\n document.querySelectorAll('a[href]').forEach(function(a) {\n var clean = cleanUrl(a.href);\n if (clean !== a.href) a.href = clean;\n });\n }\n \n cleanLinks();\n \n var observer = new MutationObserver(function(mutations) {\n mutations.forEach(function(m) {\n m.addedNodes.forEach(function(node) {\n if (node.nodeType === 1) {\n if (node.tagName === 'A') cleanLinks();\n node.querySelectorAll('a[href]').forEach(function(a) {\n var clean = cleanUrl(a.href);\n if (clean !== a.href) a.href = clean;\n });\n }\n });\n });\n });\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "Remove Tracking Parameters from Links");
}
} catch(__e) { console.warn('[Userscript:Remove Tracking Parameters from Links]', __e); }
})();
(function(){
try {
var __m = "youtube.com";
var __re = new RegExp('^' + "youtube\\.com" + '

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).

, 'i');
if (__m === '*' || __re.test(location.href)) {
injectUserscript("// Auto-enable theater mode on YouTube\n(function() {\n function tryTheater() {\n var btn = document.querySelector('button[aria-label=\"Theater mode\"], ytd-player #player button[title=\"Theater mode\"]');\n if (btn && !btn.classList.contains('activated')) {\n btn.click();\n }\n }\n \n // Try immediately\n tryTheater();\n \n // Try after navigation (SPA)\n var lastUrl = location.href;\n setInterval(function() {\n if (location.href !== lastUrl) {\n lastUrl = location.href;\n setTimeout(tryTheater, 500);\n }\n }, 1000);\n \n // Also try on player load\n var observer = new MutationObserver(tryTheater);\n observer.observe(document.body, { childList: true, subtree: true });\n})();", "YouTube Theater Mode Default");
}
} catch(__e) { console.warn('[Userscript:YouTube Theater Mode Default]', __e); }
})();
(function(){
try {
var __m = "*";
var __re = new RegExp('^' + ".*" + '

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).

, 'i');
if (__m === '*' || __re.test(location.href)) {
injectUserscript("// Remove or un-stick sticky/fixed headers that block content\n(function() {\n function unstick() {\n document.querySelectorAll('header, nav, [role=\"banner\"], .header, .navbar, .sticky, .fixed-top, [style*=\"position: fixed\"], [style*=\"position:sticky\"]').forEach(function(el) {\n if (el.style.position === 'fixed' || el.style.position === 'sticky' || \n getComputedStyle(el).position === 'fixed' || getComputedStyle(el).position === 'sticky') {\n el.style.position = 'static';\n el.style.top = 'auto';\n el.style.zIndex = 'auto';\n }\n });\n }\n \n unstick();\n \n var observer = new MutationObserver(unstick);\n observer.observe(document.body, { childList: true, subtree: true, attributes: true, attributeFilter: ['style', 'class'] });\n})();", "Kill Sticky Headers");
}
} catch(__e) { console.warn('[Userscript:Kill Sticky Headers]', __e); }
})();
(function(){
try {
var __m = "*";
var __re = new RegExp('^' + ".*" + '

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).

, 'i');
if (__m === '*' || __re.test(location.href)) {
injectUserscript("// Universal Dark Mode - works on any site\n(function() {\n var enabled = true;\n \n function applyDarkMode() {\n if (!enabled) return;\n \n // Create style element if it doesn't exist\n var style = document.getElementById('universal-dark-mode-style');\n if (!style) {\n style = document.createElement('style');\n style.id = 'universal-dark-mode-style';\n document.head.appendChild(style);\n }\n \n // Dark mode CSS - inverts colors but preserves images/video\n style.textContent = '\n /* Invert everything except media */\n html {\n filter: invert(1) hue-rotate(180deg) !important;\n background: #1a1a2e !important;\n }\n \n /* Restore images, videos, iframes, canvas */\n img, video, iframe, canvas, svg, picture, [style*=\"background-image\"] {\n filter: invert(1) hue-rotate(180deg) !important;\n }\n \n /* Preserve specific elements that should not be inverted */\n .no-dark-mode, .no-dark-mode *,\n [data-theme=\"light\"], [data-theme=\"light\"],\n .ace_editor, .ace_editor *,\n .CodeMirror, .CodeMirror *,\n .monaco-editor, .monaco-editor *,\n .markdown-body pre, .markdown-body pre *,\n .highlight, .highlight *,\n pre code, pre code * {\n filter: none !important;\n }\n \n /* Fix common UI elements */\n .modal, .popup, .dropdown-menu, .tooltip, .popover {\n filter: invert(1) hue-rotate(180deg) !important;\n background: #2d2d44 !important;\n border-color: #444 !important;\n }\n \n /* Scrollbars */\n ::-webkit-scrollbar { background: #1a1a2e !important; }\n ::-webkit-scrollbar-thumb { background: #444 !important; }\n ::-webkit-scrollbar-thumb:hover { background: #555 !important; }\n \n /* Selection */\n ::selection { background: #4ecdc4 !important; color: #1a1a2e !important; }\n ::-moz-selection { background: #4ecdc4 !important; color: #1a1a2e !important; }\n ';\n }\n \n function removeDarkMode() {\n var style = document.getElementById('universal-dark-mode-style');\n if (style) style.remove();\n }\n \n // Toggle with Alt+Shift+D\n document.addEventListener('keydown', function(e) {\n if (e.altKey && e.shiftKey && e.key === 'D') {\n e.preventDefault();\n enabled = !enabled;\n if (enabled) {\n applyDarkMode();\n console.log('[Universal Dark Mode] Enabled');\n } else {\n removeDarkMode();\n console.log('[Universal Dark Mode] Disabled');\n }\n }\n });\n \n // Apply on load\n applyDarkMode();\n \n // Re-apply on dynamic content\n var observer = new MutationObserver(function(mutations) {\n if (enabled && !document.getElementById('universal-dark-mode-style')) {\n applyDarkMode();\n }\n });\n observer.observe(document.head, { childList: true });\n \n console.log('[Universal Dark Mode] Loaded - Press Alt+Shift+D to toggle');\n})();", "Universal Dark Mode");
}
} catch(__e) { console.warn('[Userscript:Universal Dark Mode]', __e); }
})();
})();

Skip to content
auth_chain_difference_algorithm.md
Latest commit
History
History
108 lines (81 loc) · 4.95 KB
auth_chain_difference_algorithm.md
File metadata and controls
108 lines (81 loc) · 4.95 KB
Raw
Auth Chain Difference Algorithm
The auth chain difference algorithm is used by V2 state resolution, where a
naive implementation can be a significant source of CPU and DB usage.
Definitions
A state set is a set of state events; e.g. the input of a state resolution
algorithm is a collection of state sets.
The auth chain of a set of events are all the events' auth events and their
auth events, recursively (i.e. the events reachable by walking the graph induced
by an event's auth events links).
The auth chain difference of a collection of state sets is the union minus the
intersection of the sets of auth chains corresponding to the state sets, i.e an
event is in the auth chain difference if it is reachable by walking the auth
event graph from at least one of the state sets but not from all of the state
sets.
Breadth First Walk Algorithm
A way of calculating the auth chain difference without calculating the full auth
chains for each state set is to do a parallel breadth first walk (ordered by
depth) of each state set's auth chain. By tracking which events are reachable
from each state set we can finish early if every pending event is reachable from
every state set.
This can work well for state sets that have a small auth chain difference, but
can be very inefficient for larger differences. However, this algorithm is still
used if we don't have a chain cover index for the room (e.g. because we're in
the process of indexing it).
Chain Cover Index
Synapse computes auth chain differences by pre-computing a "chain cover" index
for the auth chain in a room, allowing efficient reachability queries like "is
event A in the auth chain of event B". This is done by assigning every event a
chain ID and sequence number (e.g. (5,3)), and having a map of links
between chains (e.g. (5,3) -> (2,4)) such that A is reachable by B (i.e. A
is in the auth chain of B) if and only if either:
  1. A and B have the same chain ID and A's sequence number is less than B's
sequence number; or
  2. there is a link L between B's chain ID and A's chain ID such that
L.start_seq_no <= B.seq_no and A.seq_no <= L.end_seq_no.
There are actually two potential implementations, one where we store links from
each chain to every other reachable chain (the transitive closure of the links
graph), and one where we remove redundant links (the transitive reduction of the
links graph) e.g. if we have chains C3 -> C2 -> C1 then the link C3 -> C1
would not be stored. Synapse uses the former implementations so that it doesn't
need to recurse to test reachability between chains.
Example
An example auth graph would look like the following, where chains have been
formed based on type/state_key and are denoted by colour and are labelled with
(chain ID, sequence number). Links are denoted by the arrows (links in grey
are those that would be remove in the second implementation described above).
Example
Note that we don't include all links between events and their auth events, as
most of those links would be redundant. For example, all events point to the
create event, but each chain only needs the one link from it's base to the
create event.
Using the Index
This index can be used to calculate the auth chain difference of the state sets
by looking at the chain ID and sequence numbers reachable from each state set:
  1. For every state set lookup the chain ID/sequence numbers of each state event
  2. Use the index to find all chains and the maximum sequence number reachable
from each state set.
  3. The auth chain difference is then all events in each chain that have sequence
numbers between the maximum sequence number reachable from any state set and
the minimum reachable by all state sets (if any).
Note that steps 2 is effectively calculating the auth chain for each state set
(in terms of chain IDs and sequence numbers), and step 3 is calculating the
difference between the union and intersection of the auth chains.
Worked Example
For example, given the above graph, we can calculate the difference between
state sets consisting of:
  1. S1: Alice's invite (4,1) and Bob's second join (2,2); and
  2. S2: Alice's second join (4,3) and Bob's first join (2,1).
Using the index we see that the following auth chains are reachable from each
state set:
  1. S1: (1,1), (2,2), (3,1) & (4,1)
  2. S2: (1,1), (2,1), (3,2) & (4,3)
And so, for each the ranges that are in the auth chain difference:
  1. Chain 1: None, (since everything can reach the create event).
  2. Chain 2: The range (1, 2] (i.e. just 2), as 1 is reachable by all state
sets and the maximum reachable is 2 (corresponding to Bob's second join).
  3. Chain 3: Similarly the range (1, 2] (corresponding to the second power
level).
  4. Chain 4: The range (1, 3] (corresponding to both of Alice's joins).
So the final result is: Bob's second join (2,2), the second power level
(3,2) and both of Alice's joins (4,2) & (4,3).