Tangles

A "tangle" in scuttlebutt is a way to define a directed acyclic graph (DAG) of
messages. They are a useful way to determine a partial ordering which is
useful for everything from replication to building multi-writer "records".

There are different types of tangle, but they all must specify:

1. candidate messages: the set of messages which could be part of the
   tangle
2. a recipe: how the tangle (DAG) is constructed from these candidates

It is common for the recipe to start with some "root message" and extend out
from that point, checking the validity of messages as they are added. Some
candidate messages may not have connections to the graph, or may be "invalid"
extentions, in which case they are excluded from the tangle.

Classic feed tangle

The most trivial tangle is the classic scuttelbutt feed. In this case, the
tangle for feed A is defined as:

1. candidate messages:
   • have msg.value.author == A
   • have msg.value.signature which is the signature of msg.value.content by A
2. recipe:
   • find the message with msg.value.sequence == 1 as your "root"
     • check it's signed correctly A
   • find the message with msg.value.sequence == 2
     • check it's signed correctly by A
     • check msg.value.previous points to the previous message
     • if all that's fine, add this message to the chain
   • repeat (incrementing the sequence)

The tangle data these messages carry looks like:

a => { sequence: 1, previous: null }
b => { sequence: 2, previous: a }
c => { sequence: 3, previous: b }
d => { sequence: 3, previous: d }

(author, signature, and content have been ommited here to make the backlinking
pattern clearer)

Multi author tangle

In the case of multiple authors, you need to be able to support a DAG which
branches and merges (because different authors may contribute concurrently,
or while offline).

Diagram where messages X, Y were both published concurrently (so were unaware
of one another). M is aware of both X and Y, and extends the tangle from them.
M is now the new "tip" of the tangle.

The tangle data these messages carry looks like:

A => { root: null, previous: null }
B => { root: A,    previous: [A] }
X => { root: A,    previous: [B] }
Y => { root: A,    previous: [B] }
M => { root: A,    previous: [X, Y] }

Where:

• root is the id of the root message of the the tangle
• previous is an Array of message ids of the tip(s) / leading edges of the
  tangle at the time this message was published.

Note: the root message cannot include its own id (not known until published),
so it sets it's root value as null, which means "I am a root"

Members tangle

The purpose of this tangle is to track the group membership (for a particular
epoch of the group).

We define the members tangle for some id A as:

1. candate messages:
   • the root message with id A so long as it has
     ​​​​​content.tangles.members = { root: null, previous: null }
     

   • any messages where
     ​​​​​content.tangles.members = { root: A, previous: [...] }
     

2. recipe:
   • a) the graph starts with the root message
   • b) for the current tip(s) of the tangle
     • find candidate messages which list that tip in the previous field
       of their tangle data
     • check that the graph contains each message in previous
       • if it does, add it to the graph
       • otherwise set it aside till the graph does contain them
     • newly added messages to the tangle graph constitue new tips
   • c) repeat (b) till you cannot grow the tangle further

In the context of private groups, the addition to a particular epoch is always
published to an earlier epoch (or in the case of the first epoch, to the
Additons feed).

Epoch tangle

The purpose of the epoch tangle is to track progression of epochs that
constitutes each group.

For some group id G, where A is the id of the initial group/init message
(in epoch 0), then define the epoch tangle for G as:

1. candate messages:
   • the root message with id A so long as it has
     ​​​​​content.type = 'group/init'
     ​​​​​content.tangles.epoch = { root: null, previous: null }
     

   • any messages where
     ​​​​​content.type = 'group/init'
     ​​​​​content.tangles.epoch = { root: A, previous: [...] }
     

2. recipe:
   • a) the graph starts with the root message
   • b) for the current tip(s) of the tangle
     • find candidate messages which list that tip in the previous field
       of their tangle data
     • check that the graph contains each message in previous
       • if it does, add it to the graph
       • otherwise set it aside till the graph does contain them
     • newly added messages to the tangle graph constitue new tips
   • c) repeat (b) till you cannot grow the tangle further

Group tangle

The purpose of the group tangle is to clearly identify all messages which are
part of a particular group, and provide partial causal ordering.

For some group id G, where A is the id of the initial group/init message
(in epoch 0), then define the group tangle for G as:

1. candate messages:
   • the root message with id A so long as it has
     ​​​​​content.type = 'group/init'
     ​​​​​content.tangles.group = { root: null, previous: null }
     

   • any messages where
     ​​​​​content.tangles.group = { root: A, previous: [...] }
     

2. recipe:
   • a) the graph starts with the root message
   • b) for the current tip(s) of the tangle
     • find candidate messages which list that tip in the previous field
       of their tangle data
     • check that the graph contains each message in previous
       • if it does, add it to the graph
       • otherwise set it aside till the graph does contain them
     • newly added messages to the tangle graph constitue new tips
   • c) repeat (b) till you cannot grow the tangle further

Using all the tangles together

NOTE: this diagram shows all nice linear tangles for visual simplicity,
remember there may be forks and merges because of concurrent publishing.

Crucially, the group/init messages are involved in 3 tangles, e.g.

{
  type: `group/init`,
  // ...
  tangles: {
    group: { root: A, previous: [W, X] },
    epoch: { root: A, previous: [B] },
    members: { root: null, previous: null }
  }
}

This message says

1. I am part of a group which started with message A, and the last messages I saw in the group were W, X
2. The root epoch was A and the epoch(s) before this one was B
3. I am the root of a new members tangle for this epoch