scuttlesort


Namescuttlesort JSON
Version 0.0.7 PyPI version JSON
download
home_pagehttps://github.com/tschudin/scuttlesort
SummaryScuttleSort - incremental convergent topological sort for Secure Scuttlebutt
upload_time2022-05-16 15:45:26
maintainer
docs_urlNone
authorChristian Tschudin
requires_python>=3.7
license
keywords
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            # ScuttleSort -- Incremental Convergent Topological Sort for Secure Scuttlebutt (SSB)

## Synopsis

ScuttleSort transforms SSB's tangled append-only logs into a single
linear sequence. Because this sequence changes as new log entries are
incrementally added, an append-only stream of instructions ('insert'
and 'move' commands) is derived as a side effect that permits to
replicate and update copies of the sequence. ScuttleSort is convergent
which means that the resulting sequence is the same for all receivers
having seen the same set of log entries, regardless of the order in
which they process a new log entry as long as it is added in log order.


## ScuttleSort Demo

SSB's append-only logs are implemented by hash chains where each
entry in a log has a unique ID. Basically, a log entry is four-tuple
and its ID is some hash value computed over the entry's binary
representation:

```
log_entry = (author, prev, payload, signature);
id_of_log_entry = hash(log_entry);
```

where
- ```author``` is some public key, used to validate the signature
- ```prev``` is the ID of the predecessor log entry
- ```payload``` is the content of the log entry
- ```signature``` bytes to verify the authenticty and integrity of (the encoding of) all above fields

The first entry in the chain has an empty ```prev``` field. Because of
the randomness of the author key, this entry is unique, and so is its
ID, and so are the subsequent entries in the chain and their IDs. Each
author only appends to their own chain, and receives unchanged copies
of the others' logs.

```
 1st entry      2nd entry    3rd entry                 In Secure Scuttlebutt,
 .------.       .----.       .----.                    each append-only log
 |AUTH  |       |AUTH|       |AUTH|                    is implemented as an
 |PREV=0|    .--|PREV|    .--|PREV    ...              independend hash chain.
 |PAYL  |    |  |PAYL|    |  |                         Only the author can
 |SIGN  |    |  |SIGN|    |  |                         write to their chain.
 `------'    |  '----'    |  `---
   hash|     |  hash|     |
       v     |      v     |
    ID_0 ----'   ID_1 ----'    ID_2


    e0    <----   e1    <----   e2   <----   e3   ... chained log entries
```

In the demo we assume that four append-only logs (see figure below)
are involved in some joint activity where their owners need clarity
about which log entry was appended before another one. The logs only
define a partial order, namely within the log itself and in form of
cross-referenced IDs of other entries (that are carried in the
payloads). The desired "total order" cannot be determined in general,
as some event can be logically independent i.e.,
concurrent. ScuttleSort nevertheless provides such a total order
thanks to a convention how to derive the global order, and based on the
causality relationship of events.

Other total orders will exist, but ScuttleSort's aim is to construct
one that has strong eventual consistency, meaning that all observers
seeing all logs will all compute the same total order that is not
dependend on the sequence in which log entries are ingested (as long
as they are ingested as chained).

As an example, consider the following scenario with four append-only
logs (in form of hash chains) and eight highlighted entries

```
  chain 1   ...............     .-- F <-- E  ....
                               /         /
  chain 2   ...   X <-- A <-- B <-- D <-'   .....
                  ^     ^          /
  chain 3   ...    \     `--- C <-'   ...........
                    \ 
  chain 4   .....    `- Y  ......................

                                               ---> time
```

Causality is shown as arrows from effect to cause i.e., dependency. In
the example above, A depends on X as A was appended later to the chain
than X (and needed to know entry X's ID). We also say that "A points
to X" via its ```prev``` field, for example, and "D points to B" via
its ```prev``` field and contains another hash value (in its payload)
that points to C.

ScuttleSort has bascially one method:
```
add(name, after_list)
```

which adds edges to the dependency graph between a node with ID
```name``` and the names in the ```after_list``` which are hash values
of past events in other chains.

The total order is called a ```Timeline```. On creation of a Timeline
object, one can parametrize it with a callback. In these callbacks,
```insert``` and ```move``` commands are conveyed which permit to
(re-) construct the sorted array with all events added so far.

If the entries are added in the following sequence

```
g = {
    'X': [],
    'A': ['X'],
    'F': ['B'],
    'E': ['D', 'F'],
    'B': ['A'],
    'Y': ['X'],
    'D': ['B', 'C'],
    'C': ['A']
};
```

then the stream of instructions as generated by ScuttleSort looks like this:

```
  adding X
     ins 'X' at 0
  adding A
     ins 'A' at 1
  adding F
     ins 'F' at 0
  adding E
     ins 'E' at 3
  adding B
     ins 'B' at 4
     mov  0  to 4
     mov  2  to 4
  adding Y
     ins 'Y' at 2
  adding D
     ins 'D' at 4
  adding C
     ins 'C' at 4
```

which corresponds to the array and sequence ```[X, A, Y, B, C, D, F, E]```.


## Python Implementation

The full demo code is given below. It also includes a generator
for all possible ingestion schedules. The demo then exhaustively
invokes ScuttleSort for all schedules and each time produces
the same result, as required for strong eventual consistency:

```
  ingest
   order  resulting (total) ScuttleSort order
--------  ----------------------------------------
FEXABDCY  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']
FEXABDYC  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']
FEXABCDY  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']
FEXABCYD  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']
FEXABYDC  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']
FEXABYCD  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']
...
```

## Appendix: Demo Code

```
#!/usr/bin/env python3

# scuttlesort/demo.py
# 2022-05-12 <christian.tschudin@unibas.ch>

# ----------------------------------------------------------------------

if __name__ == '__main__':

    from scuttlesort import Timeline
    import copy
    import os

    notify = lambda a,b,c: \
             print("    ", a, f"'{b}' at {c}" if a=='ins' else f" {b}  to {c}")

    timeline = Timeline(notify)   # for scuttlesort

    g = { 'X': [],
          'A': ['X'],
          'F': ['B'],
          'E': ['D', 'F'],
          'B': ['A'],
          'Y': ['X'],
          'D': ['B', 'C'],
          'C': ['A']
    }

    for n,a in g.items():
        print("  adding", n)
        timeline.add(n, a)

    print("\nScuttlesort's timeline (other valid linearizations may exist):")
    print(" ", [nm for nm in timeline])
    print("  note the lexicographic order within the same rank")

    print("\nname  rank  successor(s)")
    for h in timeline.linear:
        print("  ", h.name, ("%5d " % h.rank), [x.name for x in h.succ])


    chains = [
        [ ('F',['B']), ('E',['D','F']) ],
        [ ('X',[]), ('A',['X']), ('B',['A']), ('D',['B','C']) ],
        [ ('C',['A']) ],
        [ ('Y',['X']) ]
    ]

    def interleave(pfx, config, lst):
        if len([x for x in config if len(x) > 0]) == 0:
            lst.append(pfx)
            return
        for i in range(len(config)):
            if len(config[i]) > 0:
                config2 = copy.deepcopy(config)
                e = config2[i][0]
                del config2[i][0]
                interleave(pfx + e[0], config2, lst)
    lst = []
    interleave('', chains, lst)

    print("\nRunning ScuttleSort for all", len(lst),
          "possible ingestion schedules:\n")

    print("  ingest")
    print("   order  resulting (total) ScuttleSort order")
    print("--------  ----------------------------------------")
    for pfx in lst:
        tl = Timeline()
        for nm in pfx:
            tl.add(nm, g[nm])
        print(f"{pfx}  {[x.name for x in tl.linear]}")

# eof
```

            

Raw data

            {
    "_id": null,
    "home_page": "https://github.com/tschudin/scuttlesort",
    "name": "scuttlesort",
    "maintainer": "",
    "docs_url": null,
    "requires_python": ">=3.7",
    "maintainer_email": "",
    "keywords": "",
    "author": "Christian Tschudin",
    "author_email": "christian.tschudin@unibas.ch",
    "download_url": "https://files.pythonhosted.org/packages/7b/93/6169ab23a4c358d6b0d88a053f127575d150ae516d1323f6004994a7f8ac/scuttlesort-0.0.7.tar.gz",
    "platform": null,
    "description": "# ScuttleSort -- Incremental Convergent Topological Sort for Secure Scuttlebutt (SSB)\n\n## Synopsis\n\nScuttleSort transforms SSB's tangled append-only logs into a single\nlinear sequence. Because this sequence changes as new log entries are\nincrementally added, an append-only stream of instructions ('insert'\nand 'move' commands) is derived as a side effect that permits to\nreplicate and update copies of the sequence. ScuttleSort is convergent\nwhich means that the resulting sequence is the same for all receivers\nhaving seen the same set of log entries, regardless of the order in\nwhich they process a new log entry as long as it is added in log order.\n\n\n## ScuttleSort Demo\n\nSSB's append-only logs are implemented by hash chains where each\nentry in a log has a unique ID. Basically, a log entry is four-tuple\nand its ID is some hash value computed over the entry's binary\nrepresentation:\n\n```\nlog_entry = (author, prev, payload, signature);\nid_of_log_entry = hash(log_entry);\n```\n\nwhere\n- ```author``` is some public key, used to validate the signature\n- ```prev``` is the ID of the predecessor log entry\n- ```payload``` is the content of the log entry\n- ```signature``` bytes to verify the authenticty and integrity of (the encoding of) all above fields\n\nThe first entry in the chain has an empty ```prev``` field. Because of\nthe randomness of the author key, this entry is unique, and so is its\nID, and so are the subsequent entries in the chain and their IDs. Each\nauthor only appends to their own chain, and receives unchanged copies\nof the others' logs.\n\n```\n 1st entry      2nd entry    3rd entry                 In Secure Scuttlebutt,\n .------.       .----.       .----.                    each append-only log\n |AUTH  |       |AUTH|       |AUTH|                    is implemented as an\n |PREV=0|    .--|PREV|    .--|PREV    ...              independend hash chain.\n |PAYL  |    |  |PAYL|    |  |                         Only the author can\n |SIGN  |    |  |SIGN|    |  |                         write to their chain.\n `------'    |  '----'    |  `---\n   hash|     |  hash|     |\n       v     |      v     |\n    ID_0 ----'   ID_1 ----'    ID_2\n\n\n    e0    <----   e1    <----   e2   <----   e3   ... chained log entries\n```\n\nIn the demo we assume that four append-only logs (see figure below)\nare involved in some joint activity where their owners need clarity\nabout which log entry was appended before another one. The logs only\ndefine a partial order, namely within the log itself and in form of\ncross-referenced IDs of other entries (that are carried in the\npayloads). The desired \"total order\" cannot be determined in general,\nas some event can be logically independent i.e.,\nconcurrent. ScuttleSort nevertheless provides such a total order\nthanks to a convention how to derive the global order, and based on the\ncausality relationship of events.\n\nOther total orders will exist, but ScuttleSort's aim is to construct\none that has strong eventual consistency, meaning that all observers\nseeing all logs will all compute the same total order that is not\ndependend on the sequence in which log entries are ingested (as long\nas they are ingested as chained).\n\nAs an example, consider the following scenario with four append-only\nlogs (in form of hash chains) and eight highlighted entries\n\n```\n  chain 1   ...............     .-- F <-- E  ....\n                               /         /\n  chain 2   ...   X <-- A <-- B <-- D <-'   .....\n                  ^     ^          /\n  chain 3   ...    \\     `--- C <-'   ...........\n                    \\ \n  chain 4   .....    `- Y  ......................\n\n                                               ---> time\n```\n\nCausality is shown as arrows from effect to cause i.e., dependency. In\nthe example above, A depends on X as A was appended later to the chain\nthan X (and needed to know entry X's ID). We also say that \"A points\nto X\" via its ```prev``` field, for example, and \"D points to B\" via\nits ```prev``` field and contains another hash value (in its payload)\nthat points to C.\n\nScuttleSort has bascially one method:\n```\nadd(name, after_list)\n```\n\nwhich adds edges to the dependency graph between a node with ID\n```name``` and the names in the ```after_list``` which are hash values\nof past events in other chains.\n\nThe total order is called a ```Timeline```. On creation of a Timeline\nobject, one can parametrize it with a callback. In these callbacks,\n```insert``` and ```move``` commands are conveyed which permit to\n(re-) construct the sorted array with all events added so far.\n\nIf the entries are added in the following sequence\n\n```\ng = {\n    'X': [],\n    'A': ['X'],\n    'F': ['B'],\n    'E': ['D', 'F'],\n    'B': ['A'],\n    'Y': ['X'],\n    'D': ['B', 'C'],\n    'C': ['A']\n};\n```\n\nthen the stream of instructions as generated by ScuttleSort looks like this:\n\n```\n  adding X\n     ins 'X' at 0\n  adding A\n     ins 'A' at 1\n  adding F\n     ins 'F' at 0\n  adding E\n     ins 'E' at 3\n  adding B\n     ins 'B' at 4\n     mov  0  to 4\n     mov  2  to 4\n  adding Y\n     ins 'Y' at 2\n  adding D\n     ins 'D' at 4\n  adding C\n     ins 'C' at 4\n```\n\nwhich corresponds to the array and sequence ```[X, A, Y, B, C, D, F, E]```.\n\n\n## Python Implementation\n\nThe full demo code is given below. It also includes a generator\nfor all possible ingestion schedules. The demo then exhaustively\ninvokes ScuttleSort for all schedules and each time produces\nthe same result, as required for strong eventual consistency:\n\n```\n  ingest\n   order  resulting (total) ScuttleSort order\n--------  ----------------------------------------\nFEXABDCY  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']\nFEXABDYC  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']\nFEXABCDY  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']\nFEXABCYD  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']\nFEXABYDC  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']\nFEXABYCD  ['X', 'A', 'Y', 'B', 'C', 'D', 'F', 'E']\n...\n```\n\n## Appendix: Demo Code\n\n```\n#!/usr/bin/env python3\n\n# scuttlesort/demo.py\n# 2022-05-12 <christian.tschudin@unibas.ch>\n\n# ----------------------------------------------------------------------\n\nif __name__ == '__main__':\n\n    from scuttlesort import Timeline\n    import copy\n    import os\n\n    notify = lambda a,b,c: \\\n             print(\"    \", a, f\"'{b}' at {c}\" if a=='ins' else f\" {b}  to {c}\")\n\n    timeline = Timeline(notify)   # for scuttlesort\n\n    g = { 'X': [],\n          'A': ['X'],\n          'F': ['B'],\n          'E': ['D', 'F'],\n          'B': ['A'],\n          'Y': ['X'],\n          'D': ['B', 'C'],\n          'C': ['A']\n    }\n\n    for n,a in g.items():\n        print(\"  adding\", n)\n        timeline.add(n, a)\n\n    print(\"\\nScuttlesort's timeline (other valid linearizations may exist):\")\n    print(\" \", [nm for nm in timeline])\n    print(\"  note the lexicographic order within the same rank\")\n\n    print(\"\\nname  rank  successor(s)\")\n    for h in timeline.linear:\n        print(\"  \", h.name, (\"%5d \" % h.rank), [x.name for x in h.succ])\n\n\n    chains = [\n        [ ('F',['B']), ('E',['D','F']) ],\n        [ ('X',[]), ('A',['X']), ('B',['A']), ('D',['B','C']) ],\n        [ ('C',['A']) ],\n        [ ('Y',['X']) ]\n    ]\n\n    def interleave(pfx, config, lst):\n        if len([x for x in config if len(x) > 0]) == 0:\n            lst.append(pfx)\n            return\n        for i in range(len(config)):\n            if len(config[i]) > 0:\n                config2 = copy.deepcopy(config)\n                e = config2[i][0]\n                del config2[i][0]\n                interleave(pfx + e[0], config2, lst)\n    lst = []\n    interleave('', chains, lst)\n\n    print(\"\\nRunning ScuttleSort for all\", len(lst),\n          \"possible ingestion schedules:\\n\")\n\n    print(\"  ingest\")\n    print(\"   order  resulting (total) ScuttleSort order\")\n    print(\"--------  ----------------------------------------\")\n    for pfx in lst:\n        tl = Timeline()\n        for nm in pfx:\n            tl.add(nm, g[nm])\n        print(f\"{pfx}  {[x.name for x in tl.linear]}\")\n\n# eof\n```\n",
    "bugtrack_url": null,
    "license": "",
    "summary": "ScuttleSort - incremental convergent topological sort for Secure Scuttlebutt",
    "version": "0.0.7",
    "split_keywords": [],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "ba25c8428191628c3d0694bb7ed5b58d",
                "sha256": "59cfe9c756983a5371b954d7f6bf0c0597b9a00f69afa89f90a4344977d51acd"
            },
            "downloads": -1,
            "filename": "scuttlesort-0.0.7-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "ba25c8428191628c3d0694bb7ed5b58d",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.7",
            "size": 9105,
            "upload_time": "2022-05-16T15:45:24",
            "upload_time_iso_8601": "2022-05-16T15:45:24.907015Z",
            "url": "https://files.pythonhosted.org/packages/9b/b1/3a89d2c3c8a658acd4859692edfffdf0a5e2c56fe3c1e053488d3534b545/scuttlesort-0.0.7-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "4de2394fd6265e1d0d9865dcb95aa22d",
                "sha256": "f7952b2f8335745cccd58b46e8d7d05846d397b6736bb1a9c63419369c95a046"
            },
            "downloads": -1,
            "filename": "scuttlesort-0.0.7.tar.gz",
            "has_sig": false,
            "md5_digest": "4de2394fd6265e1d0d9865dcb95aa22d",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.7",
            "size": 9921,
            "upload_time": "2022-05-16T15:45:26",
            "upload_time_iso_8601": "2022-05-16T15:45:26.473682Z",
            "url": "https://files.pythonhosted.org/packages/7b/93/6169ab23a4c358d6b0d88a053f127575d150ae516d1323f6004994a7f8ac/scuttlesort-0.0.7.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2022-05-16 15:45:26",
    "github": true,
    "gitlab": false,
    "bitbucket": false,
    "github_user": "tschudin",
    "github_project": "scuttlesort",
    "lcname": "scuttlesort"
}
        
Elapsed time: 0.36416s