Name | scuttlesort JSON |

Version | 0.0.7 JSON |

download | |

home_page | https://github.com/tschudin/scuttlesort |

Summary | ScuttleSort - incremental convergent topological sort for Secure Scuttlebutt |

upload_time | 2022-05-16 15:45:26 |

maintainer | |

docs_url | None |

author | Christian 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 ```

{ "_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