search

ssbc / ssb-tangle

8 stars 2 forks source link

readme

:warning: This module is being deprecated. Please use modules from gitlab.com/tangle-js

ssb-tangle

This is a collection of tools for processing thread-like tangles in scuttlebutt. This pattern is a way to causally order messages, which is hard in a p2p system, because there is no central source of truth (like a single database which tracks when messages were created)

The simple solution is for each message to reference the messages that happened before it in the thread.

   A     (the root message)
  / \
 B   C   (two concurrent replies)
  \ /
   D     (a message merging those two contexts together)
   |
   E     (the current end-point of the thread)

e.g. the messages before E were : [A, B, C, D]

This would get out of hand pretty quickly as threads get longer, so instead we record just the message(s) immediately prior to the one we're posting. e.g.

We call these links back to previous messages "backlinks", and they allow us to construct a graph like the one above of where messages were relative to on another in time.

e.g. we know the messages before E because we can walk up along the backlinks 

E > D > B > A
      > C > A

This pattern was first used in thread-conversations, but it's much more widely applicable - e.g. changes to a gathering (when is it, who's attending), chess moves, etc.

This library formalises some of the ideas by thinking about each message in a thread-tangle as a "transformation" - a signal to change the state somehow, where that means "what a reply on" or "move Knight to C5"

The formalisation is through defining strategies which specify things like how to combine a series of messages (transformations), and how to determine iif a merging-message is valid.

API

strategy/compose

const Compose = require('ssb-tangle/strategy/compose')
const Overwrite = require('ssb-tangle/strategy/overwrite')
const Set = require('ssb-tangle/strategy/simple-set')

const compostion = {
  preferredName: Overwrite(),
  altNames: Set()
}

const strategy = Compose(compostion)

const T1 = {
  preferredName: { set: 'andromeda' }
  altnames: { ziva: 1, goomba: 0 }
}

strategy.mapToOutput(T1)
// => { 
//   preferredName: 'andromeda',
//   altNames: ['ziva'],
// }
strategy.concat(T1, T2)
strategy.mapToPure(T2)

Compose takes an Object which maps field names to a strategy for that field, and returns a higher-order strategy.

Functions attached to this strategy are:

graph-tools/reduce

reduce(entryNode, otherNodes, strategy, opts)
// => headState

where

const reduce = require('ssb-tangle/graph-tools/reduce')

// say we have 3 messages posted one after another like this:
//    A   (the root message)
//    |
//    B
//    |
//    C

const A = {
  key: '%A...',
  value: {
    content: {
      preferredName: { set: 'ziva' }
      tangles: {
        profile { root: null , previous: null }
      }
    }
  }
}

const B = {
  key: '%B...',
  value: {
    content: {
      preferredName: { set: 'Ziva!' },
      altNames: { goomba: 1 }
      tangles: {
        profile { root: '%A...' , previous: ['%A...'] }
      }
    }
  }
}

const C = {
  key: '%C...',
  value: {
    content: {
      altNames: { goomba: -1, andromeda: 1 }
      tangles: {
        profile { root: '%A...' , previous: ['%B...'] }
      }
    }
  }
}

const strategy = // the strategy we composed in the last method say

reduce(A, [B, C], strategy, {
  getThread: m => m.value.content.tangles.profile,
  getTransformation: m.value.content
})
// =>
// {
//   '%C...: {
//     preferredName: { set: 'ziva' },
//     altNames: { andromeda: 1 }
//   }
// }

reduce gives you the output of walking the tangle so far. It's important to know there might be multiple outputs (because the thread can diverge if people post online concurrently). This is why the return value is an Object which maps keys (representing the different end-points/ tips of the graph histroy) to what the cumulative transform to that point.

You can take any of the cumulative transforms so far and use strategy.mapToOutput on it to see what the transform mapped into a user-facing state would be.

graph-tools/get-heads

Useful for calculating the keys of the current leading heads of your tangle. Mainly used to calculate previous when publishing new tangle messages.

Note this is just a thin wrapper over reduce, and if you already have the output of that (because you've calculated the transformation state) you should probably use that instead.

reduce(entryNode, otherNodes, opts)
// => headState

where

Development

WIP - not all aspects of this are production ready yet

TODO: