That’s a good idea, I’ll look look into it. Collaborative research ftw.
Scope: Yes, initially limited but that is the intention. E.g. grow both in dimensions (column) and what is being compared (rows).
That’s a good idea, I’ll look look into it. Collaborative research ftw.
Scope: Yes, initially limited but that is the intention. E.g. grow both in dimensions (column) and what is being compared (rows).
Abbreviated day due to meetings.
This isn’t controversial, and I read it a few years ago when working on event sourced architectures with distributed message queues, but it’s useful to re-read.
Summary: LinkedIn many problems reduced to writing a log. Aka write-ahead log, commit log, transaction log. This article outlines what it is, why it’s a fundamental data structure, where it is used and how you can extend it and scale it. It also links to various related distributed systems literature.
What: Append-only, totally ordered sequence of records ordered by time. Discrete log time. Record what happened and when. Immediate authoritative source; then use projections on top of it. Machine-readable, often internal in DBs etc.
PostgresqSQL etc log shipping protocol to transmit part of log to replica database which acts as a slave (NB indicates master-slave).
Problems it solves: (a) Ordering changes (b) Distributing data.
State Machine Replication Principle: If two identical deterministic proccesses begin in the same state and get he same inputs in the same order, they will product the same output and end in the same state.
A replica can then simply be described by maximum log entry they processed.
Two models: State machine replication model primary backup model.
What’s the difference? In state machine replication model we write write transformations/events to the log and then to each peer. Vs primary-backup: go via primary node, then log results.
Example: Arithmetic service starts at 0, then +1 *3. Logging transformations (+1 *3) or results (1, 3).
A log can be seen as a series of decision of the next value to append. Relevant for distributed, consistent, shared log. E.g. see RAFT, Paxos, Viewstamped Replication (?), [and blockchains].
Theory before practice in distributed system research, which might explain why there’s a bunch of talk about single-value registers as opposed logs for abstractions.
Duality: log of changes and a table. Log - list of credits and debits; table account balances. Log more fundamental because you can re-derive stuff.
Changelog to to get near-real-time replicas. Similar to version control: pull down patches and apply to snapshot.
It then talks about why it is useful for things like data integration, real-time data processing, and distributed system design. Skimming this part.
With logs we have a logical clock, so subscribers can measure to this (e.g. block height). Allows for reasoning about each subscribers state.
Data production is asynchronous from data consumption. Subscribers can subscribe at different rates.
Hints at atomic broadcast aka total order broadcast, as a log for messaging system, where multiple processes receveives event in same order.
Isolate consumer from soure of data for many different services. Lead to Kafka (and later, AWS Kinesis).
[ETL stuff, not interesting.]
Scalability hard. Tricks: partion the log; better throughput with batched r/w; avoiding too many data copies.
[-- aka implied async optimistic; partial replication]
Each partition totally ordered log, but no global ordering between partitions. Without coordination between shards.
Log easy to optimize for read and write patterns.
Kafka binary format: same in-memory, on disk and over network. Can do zero-copy data transfers.
Together means can r/w data at rate supported by data/network.
Also some Real time streaming process, skipping.
Data Flow graphs: feeds that result from many feeds. E.g. DAG of logs and jobs impacting other logs.
Briefly on log compaction.
Summary in paper - architecture: handle data consistency (eventual and immediate) for concurrent updates to nodes. Data replication. Handling rebalancing.
Example for system with two logical parts: log and serving layer. Client writes to log (or proxied), then log writes to serving node, which is what client reads from.
Has some links to related stuff like replication algortihmics, Paxos/Raft, Replication book.
Event sourcing as being same as state machine replication.
Evaluation: Tool for distributed system design. Useful overview and has some good pointers. A lot of it seems to be implicitly consensus-based though (e.g. distributed cluster vs p2p and local).
How kafka achieves fault tolerance: partioned data; brokers and followers; at any time have a leader then N leaders. Election process.
Similar to Ethereum in that you have state and STF, STF(s0, e0) => s1. Events array [e0, e1,…]
(NB: Receive events in same order - probably false! This should be more DAG, where it might look different.)
A lot of this implicitly has one single distributed log and then replicas.
https://hackernoon.com/thorough-introduction-to-apache-kafka-6fbf2989bbc1 just to see how a distributed kafka cluster works (N participants, one broker at a time that can persist and die, election-based).
Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial http://www.cs.cornell.edu/fbs/publications/smsurvey.pdf - linked from “The Log” article.
Primary Backup approach http://www.cs.cornell.edu/fbs/publications/DSbook.c8.pdf - linked from “The Log” article.
Vive La Diff ́erence:Paxos vs. Viewstamped Replication vs. Zab https://arxiv.org/pdf/1309.5671.pdf - If you are “shopping for replication algorthm” read this, according to “The Log” article. Not clear to me how relevant this is wrt consensus, but perhaps worth a skim.
https://en.wikipedia.org/wiki/Atomic_broadcast I don’t understand how this works, but total order broadcasting seems useful to understand somewhat.
http://www.pmg.csail.mit.edu/papers/vr-to-bft.pdf From Viewstamped Replication to ByzantineFault Tolerance, by Liksov. From Replication book. Seems like there are two branches of replication algorithms, where BFT is a continuation that deals with arbitrary failure. Both came from MIT apparently, and both deal with ‘state machine replication’. Still unclear to me to what extent we need something like BFT/consensus for replication, but worth digging into basics more and understanding trade-offs. Also see: basis of blockchains.
Summary: Need immutability to coordinate at a distance, we can afford it with storage requirements. Change in tech and how we do computing. How updates are layered on top of LSF (Log Structured File Systems), COW (Copy on Write), LSM (Log Structured Merge trees). Also implications for e.g. replication [what interested in]. Then talking about hardware and finally trade-offs.
Append-only computing. Accountants don’t use erasers or they go to jail.
Single-master computing - order changes, either through centralized master or some consensus like protocol.
Append-only: record facts then derive
Immutable files - Replication of files w/o update anomalies.
Versions and history:
Versions as immutable objects, a book is published.
GFS and HDFS provide immutable files, chunks replicated across data nodes and identified by GUID. [Similar to Swarm?].
“master-less” file store.
Consistent hash ring: Rebalancing under failure and additional capacity. “Cannot get stale versions of data”
Trade-offs: Denormalization, flexible but fat. Write amplication vs read perspiration.
Clean replication: data immutable and unique id means fewer challenges. No stale version, so less picky about where replications are, also fewer bugs.
Evaluation: General overview of immutability across the stack. Either nothing really new or not super relevant. Useful to think about linear history as strongly consistent vs DAG for eventual consistent though.
Question: Is it possible to have a linear version of history in p2p? Probably yes (well, consensus and using a chain of blocks…), but is it desirable? Why / why not.
Look more into consistent hashing, it is useful for data partioninging things (need to remap fewer keys). DHT is one example of this.
Question: When is it desirable to have a single log that we have consensus about? Vs multiple individual logs.
Think more about exactly how a DAG generalizes a log, and what the trade-offs are (e.g. wrt ordering properties and and lack of coordination/consensus), as well to what extent they are the same thing.
Too wordy, better to read through then jot down summary/notes.
Feeling a bit under the weather today, but I spent some time with the excellent Jepsen’s Consistency Model overview https://jepsen.io/consistency, as well as trying to understand the subtleties of various consistency models and session guarantees.
Starts with a good overview of the fundamental concepts that consistency models and distributed systems builds on. Operations, processes, invocation/completion times, imaginary real-time, concurrency, history, consistency models.
Diagram of various consistency models and how they relate. Several mini articles the various concepts. Zooming in on the most relevant for an exposition.
Linearizability: Operations occur in (imaginary) real-time clock order. Can’t be totally or sticky available; Useful if real-time ordering is a requirement.
Sequential consistency: Operations appear in some total order that reflects order of events. Individual nodes may lag behind reality. Doesn’t provide availability.
Casual consistency: Captures notions that casually-related events should appear in the same order. Casually-independent events don’t. E.g. A: lunch? B: yes C: no, here no one will see yes or not before lunch?, but yes and no might be in different order.
For convergent casual consistency, eventually yes and no would be ordered (e.g. based on hash order).
There are also other forms of casual consistency, such as Real-Time Casual consistency. The strongest consistency model in available system. If you want total availablity you need to give up read-your-writes property.
Casual models come from happen-before semantics by Lamport (potential causality).
Session properties for casual consistency: writes follow reads; monotonic reads and writes.
Mentions formal treatment that decomposes casual consistency into: CasualVisibility, CasualArbitrarion and RVal (see below).
Session properties - Write follows reads: (Wikipedia): Wihin process p, r(x) then w(x), write on x then takes place on same or more recent x. You can’t change the past.
Session properties - Monotonic writes: If a process does w1 then w2, then all processes observe w1 before w2.
Session properties - Monotonic reads: If a process p reads r1 then r2, r2 can’t reflect a state written before r1. You can’t read backwards.
Session properties - Read Your Writes: This one is interesting, because it is not totally available, only sticky available. If you write to a process, you should be able to read that value after. This is also why Casual Consistency isn’t totally available.
Sticky availability: If there’s a network partition, all nodes can progress, as long as client is connected to the same ‘server’.
There’s also PRAM (pipeline random access memory) which is weaker. As well as a bunch of Serializability models, that deals with read committed/uncommitted and monotonic atomic view, snapshot isolation, cursory stability, and repeatable reads.
Really useful to understand design space of consistency models, what guarantees they provide and why you might want one or the other.
Didn’t look into Serializability/Transaction side of tree too much (read committed/uncommited, montonic atomic view).
Claim: Conversations are generally casual, i.e. you either start conversation or respond
Claim: Network availability is vital in permission-less p2p and to be censorship-resistant
If we value availability over total order, then casual consistency is the strongest consistency model we can provide
This implies UI needs to accommodate the rendering of casually-independent events
Question: Are there use cases when a total ordering is a requirement, and we can sacrifice availability (or network partitioning)?
– E.g.: authentication; canonical chat history; canonical name resolution
Question - why is casual consistency not totally available but only sticky available? I think I understand if your model is client-server, and you write and then try to read. But not 100% intuitive, especially how it differs vs other session models.
Question: What consistency model does Bitcoin/Ethereum provide for? See below for skimmed resources.
Documenting session properties seems useful, and impacts how to consume protocol.
Comment on Monotic Writes: In Bramble model, you don’t deliver writes until you have message dependencies. This ensures this session property is provided for.
Question: But how does that work if you do have w2 message but for some reason can’t find w1 due to that data not being available? That seems like the same as not having gotten w1 or w2 in first place, so perhaps it reduces to what we mean by availablity and eventual consistency in the first place.
I’m a bit worried people won’t fundamentally grok casual consistency, so how do we render this in a reasonable way? What would two parents in UI look like?
Does convergent casual consistency makes sense for us? How would it be rendered?
Does a notion of finalization makes sense? (a la Eth2)
Is there something similar to Bitcoin’s Omega factor w.r.t probability of message persisting? Swarm and data availability problem.
It turns out casual consistency is family of algorithms. What do other versions of casual consistency provide and why might you want to use them / not?
(I wonder if using Jepsen would be interesting at some point https://github.com/jepsen-io/jepsen)
Also see below on some skimmed.
[Principles of Distributed Computing (lecture collection), Roger Wattenhofer] (https://disco.ethz.ch/courses/podc_allstars/) link2. Explores pearls of distributed computing. Including byantine/authenticated agreement, quroum systems, eventual consistency and bitcoin, distrbitued storage, game theory, and routing. Is also a course.
Eventual consistency - Amazon CTO on eventually consistent variations, including read-your-writes and stickiness.
Consistency in Non-Transactional Distributed Storage Systems Formal treatment. This is what Jepsen refers to. Interesting casual family and fork based (new family of consistency models?). many different types of casual consistency, also fork based. Worth having a look over. Has this graph.
Consistency, Availability, and Convergence - on Real Time Casual Consistency.
Time, Clocks, and the Ordering of Events in a Distributed System, Lamport. Classic. Read before but was a while ago.
Bitcoin Guarantees Strong, not Eventual, Consistency -
Emin Gün Sirer, 2016 provides a nice way of thinking about it. Brief summary: Bitcoin (and Ethereum) provides strong consistency through serializability. You need to look at Bitcoin as a read protocol and write protocol, considerings its outputs, not the internal state. It guarantees serializability, with a probability that is exponentially decreasing with latency. Can’t say it is inconsistent just because you can have re-orgs, that’s like saying it is works like MongoDB as a DB. Instead: for the read protocol you can discard Omega blocks, and you can analyze what this is to get the desired probability of anomaly. Using a low Omega (0 confirmations) just means you are not leveraging the consistency that Bitcoin provides. This parameterization property is indeed very nice, since it depends on use case (0-conf for coffee vs 6-conf for bigger transactions, etc). [It should be noted that there appears to be disagreement about how to classify this in academia; most important is being able to rigorously argue for what properties it has, incl probability of failure etc].
Additionally: Eventual Consistency & Bitcoin
Probably more, found some formal one but lost it
The way to make sense of it seems to be that it’s about client-view consistency, not data per se. E.g. client+server as node slightly different (since they fail together).
Via a classic partitioning argument, we can see that RYW is not achievable under the stringent CAP availability model. We can partition a client C away from all but one server S and require C to perform a write. If our implementation is available, S should eventually acknowledge the write as successful. If C reads from S, it’ll achieve RYW. But, what if we partition C away from S and allow it to only communicate with server T? If we require C to perform a read, T will have to respond, and C will not read its prior write. This demonstrates that it’s not possible to guarantee RYW for arbitrary read/write operations in an available manner.
Session Guarantees for Weakly Consistent Replicated Data. More on session guarantees, how apps can get view of db that is consistent, when it is reading from inconsistent servers. Developed together with Bayou Project at Xerox. Relates to mobile intermittent connection and replication strategies. Worth skimming for mobile angle.
Eventually Consistent by Werner Vogels, CTO of Amazon (2008. Popularization of eventual consistency model. Based on client-server. Include mentions of RYW, etc.
Unrelated to reading:
People: Added minor.
Setup basic open group here and added some papers https://www.zotero.org/groups/2306124/secure_messaging
Still playing around with it:
– Need to figure out local save copy
– How to auto add citations
– If anyone has examples of good open groups I’d be interested
– And also add existing lit
– How does this interact with awesome-secure-messenger repo?
– Notes seem a bit iffy, might be best for keeping track for lit alone
Call for Messaging for Web3 on next Tuesday https://github.com/status-im/messaging-pm/issues/1
Fever, but the research continues, albeit abbreviated. Let’s look briefly at casual consistency and fork join consistency models.
Consistency used to be a more vague notion, e.g. what does “strong consistency” really mean? This survey paper looks at more than 50 different notions of consistency in distributed systems, especially with a focus on storage systems. It then decomposes them into specific formal properties that hold, and creates a graph that shows hows different consistency models are related. It relates both to database literature and distributed systems literature.
Uses graph theory and first-order logic to describe and classify consistency semantics.
Mostly interested in getting a rough idea of fork-join based models and casual consistency family. See picture posted yesterday.
Classify consistency semantics into ten families.
Describe an operation by process on shared object formally as a tuple of:
A history is then a set of operations. They then define more formal notions using various logic and equivalance classes etc. Skipping details of a a lot of this for now. With this you get relations on elements in history such as:
Abstract execution: multi graph A=(H,vis, ab). Vis and ab captures message delivery order and e.g. conflict resolution. Looking at relations between operations in a histoy and justification, e.g. vis (visibility) that accounts for propagation of writes, ar (arbitration) total order that deals with conflict resolution.
A lot of this went over my head and would require more time to get into in detail. (Update: went back to clarify some things, actually seems largely like straightforward set logic with some additional unfamiliar notation for things like transitive closure +some unknowns)
Update: visibility is an acyclic relation that acconuts for write propagation. If a is visibile to b (a vis-> b), then effects of a are visible to a.
Also defines things like:
Meat, chapter 3: non-transactional consistency semantics:
[Not clear why non-transactionl, seems like it is because of single-operation?]
happens-before semantics (Lamport 1978) was originally for messaging passing systems but then seems to have turned out to be equivalent to consistency model for shared-memory.
Fork based models:
Trust limitations for storage and computations led to dealing with byzantine faults. What consistency guarantees can you get in an untrusted environment?
Fork-linearizable models guarantee that if the visible histories of two processes differ for a single operation, they may never observe each other’s writes.
Other forms of fork models, fork-sequential, fork-join casual consistency, - this seems eerily similar to things like things like CBC Casper. That’s largely part of (separate?) consensus literature, which I don’t want to go into right now.
Fork model came from: [http://cs.brown.edu/courses/cs296-2/papers/sundr.pdf](Mazieres, David, and Dennis Shasha. “Building secure file systems out of Byzantine storage.” Proceedings of the twenty-first annual symposium on Principles of distributed computing. ACM, 2002.)
Probably a lot more in consensus and Ethereum etc lit.
Byzantine general problem: [https://www-inst.eecs.berkeley.edu/~cs162/sp16/static/readings/Original_Byzantine.pdf](Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982): 382-401.) - classic, worth re-reading.
Another related Lamport classic worth re-reading:
[http://pages.cs.wisc.edu/~remzi/Classes/739/Fall2015/Papers/clocks.pdf](Lamport, Leslie. “Time, clocks, and the ordering of events in a distributed system.” Communications of the ACM 21.7 (1978): 558-565.)
Other casual consistency models:
Could look into this but seems like too much of a rabbit hole, probably better use of time to go to p2p direction.
“Casual consistency as an optimal trade-off between user-perceived correctness and coordination overhead, especially in mobile or geo-replicated applications”:
Real time consistency:
Linked to other papers to understand subtle implications for eventual consistency:
Bermbach, David, and Stefan Tai. “Eventual consistency: How soon is eventual? An evaluation of Amazon S3’s consistency behavior.” Proceedings of the 6th Workshop on Middleware for Service Oriented Computing. ACM, 2011.
Bernstein, Philip A., and Sudipto Das. “Rethinking eventual consistency.” Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 2013.
Bailis, Peter, and Ali Ghodsi. “Eventual consistency today: Limitations, extensions, and beyond.” Queue 11.3 (2013): 20.
Bailis, Peter, et al. “Quantifying eventual consistency with PBS.” The VLDB Journal 23.2 (2014): 279-302.
Unclear if worthwhile, but especially p2p would be interesting.
Something on hashes in p2p and how it relates to byzantine cases?
[https://hal.inria.fr/hal-01350652/document](Balegas, Valter, et al. “Geo-replication: Fast if possible, consistent if necessary.” IEEE Data Engineering Bulletin 39.1 (2016): 12.) - hybrid RedBlue convergence that attempts that both strong and casual consistency.
Rodrigo Rodrigues (author) seems to look into p2p, routing, and consistency: https://scholar.google.com.tw/citations?user=mxdX7FYAAAAJ&hl=en&oi=sra
data layer availability problem; L2 protocol using eth2 as a data layer; zk roll ups - complete noob in these so need to wrap my head around it, and whether it’d be useful at all
IPFS (draft) https://arxiv.org/pdf/1407.3561.pdf vs Swarm as well
Look at Zotero file save with closed group
Formulate more precise research questions
Might take tomorrow off depending on how I feel.
Most consistency models literature has been in the context of traditional distributed database systems. Now it’s time to explore more of the literature for p2p, with the goal of finding out how nodes join, link up, etc. In the context of data replication.
P2p scaling examples:
P2P overlay networks types:
Unstructured: ad hoc, data locality unrelated to topology. Each peer knows its neighbors but not what resources they have.
Search method: The most basic and expensive is flooding. You can do perf optimizations though (see further reading):
They then talk about things like query expressiveness (key lookup/sql-like query).
Examples: Gnutella, Kazaa, FreeHaven.
Strucured networks: Emerged to solve scalability problem. Done by controlling overlay topology and data placement (data or pointers to data). DHT (Distributed Hash Table) main example.
Each peer has some neighbors with a routing table. Usually: lookup to find peer with desired data, then communicate with peer directly. Can find key in O(log N).
Downside: autonomy limited, since node is responsible for some piece of data. Also: usually for exact key searches, but possible to generalize somewhat.
Examples: Chord, CAn, Tapestry, Pastry, Freenet (semi-structured), etc.
Super-peer: Unlike unstructured and structured, super-peer servers aren’t pure. Each peer provides equal functionalities. Super-peer are hybrid client-server, and if just using one it is same as client-serve. These super-peers provides services such as: indexing, querying, access control, meta data etc.
Advantages: efficiency and quality of service. Takes advantage of different resource consumption. Also access control [NB Bad boy!]. Restricts autonomy (can’t login to any node) and worse fault tolernace. Possibly dynamic replacement [mailserver round rubbin hurr-hurr].
Comparison: They compare on a few dimensions:
They then compare the three approaches. Essentially super-peer has moderate autonomy and low fault-tolerance, but high everything else. Unstructured has low efficency, QoS and security, but high in other aspects. Structured low autonomy, query expressiveness and security, high in everything else.
It then goes into details of various replication solutions in p2p systems. Won’t go into too much detail right now but:
Napster: Relies on central service to mediate, super-peer. Replication occurs passively. Super peers as single points of failure. Only stores static data.
Gnutella: To obtain shared file node/requestor must perform three tasks: join network, search for desired file and download it. Join with bootstrap nodes, then search with flooding. Passive replication. Active replication strategies proposed (see further reading Q. Lv). Only deals with static files.
Chord routing system on top of DHT. Uses consistent hashing.
CAN, Tapestry Freenet etc but didn’t look into here.
Activate replication seems similar to semi-trusted nodes
What about hybrid approaches between these p2p overlays to get best of both worlds? Also which aspects put more of a premium on?
[Mental model check: Assuming message size 1KB, we have 100 users who send average of 100 messages a day. Probably all on the high end, perhaps by factor of 2 or so, but that’d be 10 MB/day in messages. Then we’ve been on for say a year, so messages should take up something like 3GB. Now let’s ask and wait for #status-core. No answer yet]
QUESTION: Are super-peers desirable for some contexts? What are the main invariants we want to avoid? Something like: each round is a fresh, i.e. arbitrary which we use and can select K. No privileged read. Compare with e.g. Matrix federation and our mailservers.
We do want to take advantage of different resource consumptions, but it’s about it not being a special relationship. Also see miners etc. Has to be a lot more research on this.
Also leads to me to all these validator designs people have in Ethereum, a lot of them seems way overkill and like a bad alternative to basic operations. It needs to be integrated or very simple, probably.
[Question: Super-peer hybrid, but if everyone has OPTION to be that player, is this a problem? Vs centralized decision]
Unstructured optimization: Is this roughly what was initially intended for Whisper?
Also routing indicies seems similar to PSS
Why is Gnutella so well studied?
How does PSS deal with nodes storing whatever vs IPFS and DHT (autonomy but also censorship resistance)
Whisper as (ephemeral) a DHT: key is topic and then expiring values that are replicated everywhere
They seem more interested in collaborative semantically rich data like SQL.
Due to dynamic behavior, join and leave whenever, rely on massive data duplication
Back of the envelope calculation for message size:
Question: How can we do efficient search and replication in p2p networks?
Lv, Qin, et al. “Search and replication in unstructured peer-to-peer networks.” Proceedings of the 16th international conference on Supercomputing. ACM, 2002.. Attempts to improve on e.g. flooding based query algorithms in unstructured networks, such as Gnutella. For example: multiple random walks, which can reduce network traffic by two orders of magnitude. Many citations, worth reading.
Yang, Beverly, and Hector Garcia-Molina. “Improving search in peer-to-peer networks.” Proceedings 22nd International Conference on Distributed Computing Systems. IEEE, 2002.. More efficent search as well.
Kalogeraki, Vana, Dimitrios Gunopulos, and Demetrios Zeinalipour-Yazti. “A local search mechanism for peer-to-peer networks.” Proceedings of the eleventh international conference on Information and knowledge management. ACM, 2002. - improve BFS with key for search, and use past behavior to steer.
Chawathe, Yatin, et al. “Making gnutella-like p2p systems scalable.” Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications. ACM, 2003.
Checking Lv, Qin et al. above “cited by” and ordering by citations gives https://scholar.google.com.tw/scholar?cites=17818466769784722704&as_sdt=2005&sciodt=0,5&hl=en which leads to more reference works, such as Modern Information Retrieval (too broad) and Principles of distributed database systems (probably too broad, but there is a chapter on data replication with some further resources) and A survey of peer-to-peer content distribution technologies (comparative approach across dimensions such as scalability, access control, anonymity, etc - seems useful).
Possibly re-read Chord paper
SSB DHT problems page somewhere
P2P Buford book
F2F networks and tradeoffs:
Chothia and Chatzikokolakis, “A Survey of Anonymous Peer-to-Peer File-Sharing”; Li and Dabek, “F2F: Reliable Storage in Open Networks”; Rogers and Bhatti, “How to Disappear Completely: A Survey of Private Peer-to-Peer Networks”; Popescu, Crispo, and Tanenbaum, “Safe and Private Data Sharing with Turtle.”
Collecting for evaluation. Challenge: right table (problem-fit, relevance) and minimal set of consistent dimensions and comparables.
Outside of replication attributes above, consistency model, we also have P2P overlay topology type, and probably ~join|find|pull method.
Other tables from Martins, et al. 2006:
And final table in Martins:
Replication Systems in P2P Systems:
Link to library: https://www.zotero.org/groups/2306124/secure_messaging/items
Plan of action: go through specific applications and describe them along relevant dimensions. Timeboxed. At the end, do brief comparison. E.g. something like: Briar, Matrix, Scuttlebutt, Tox, Swarm.
Briar synchronizes data in a group context among a subset of devices called peers.
Since you only connect to devices you did key exchange with, it is a friend-to-friend network
Each message is immutable, and (depending on the client) include message dependencies. This means we build up a DAG of history, and it thus provides casual consistency
It’s not an unstructured network nor a super-peer network. Since you have direct connections with each other you might classify it as a direct p2p network, or possibly a structured p2p network, since A talking to B means A knows B has its own log of data. It is not anything like a DHT though, so perhaps this notion makes less sense for f2f networks.
BSP requires a transport security protocol to communicate between devices.
Peer discovery: to sync up initially requires meeting up in person. To know how to reach a device Briar keeps track of transport properties. For short-distance it uses BT/LAN discovery beacons, and for long distance it uses Tor hidden services.
Look into Tor hidden services interface more, both in general and in Briar. E.g. see onion addresses.
Assumptions: A Briar node runs on a mobile device, but it runs in background. This means currently mainly Android is supported, and there are some battery considerations. Though it is less than in an unstructured network.
Briar and problems with battery consumption. Additionally, there’s some resources on Tor specific battery work that I can’t find right now.
Briar and problems with running on iOS due to background restrictions
In Briar asynchronous, optimistic replication is practiced. This means you append to your own log, and then try to sync up with other nodes in some group context. Since each message is immutable and hashed, conflicts are likely to be rare.
Conflict-resolution: Unlikely to be a problem due to hashes, but in the case it is it is presumed validation will take care of this in a straightforward manner.
Briar’s have weak network assumptions, and it can sync over pretty much any medium. Including USB sticks, BT, and Tor. It only requires the ability to securely transport something from device A to B.
Replication data: For individual objects, it is single-master and ‘static data’ since only a device writing a message can write it, and it doesn’t change after that. No other node can change a message. This is the minimum object being replicated and is essentially a simple file. However, if we look at the whole thing being replicated in a group context, it is really a DAG. This DAG can be updated by all the members, and since it is a DAG it is a form of CRDT. This means it might be more apt to classify it as a dynamic data; multi-master setup.
Exactly how resolution works in case of group membership conflicts needs to be studied more carefully. The semantics are fairly coarse, but well specified through a finite state machine. E.g. see [private group sharing client[(https://code.briarproject.org/briar/briar/wikis/Private-Group-Sharing-Client).
Since all devices participating in a group sync context are interested in messages of that group, it is a form of passive replication. No other helper nodes are active by default in Briar, e.g. there’s no active replication involved. If there were, these nodes would have to choose between seeing the encrypted messages or see the shape of the DAG, since the DAG is encoded inside a message through message dependencies. This is different from, say, a linear log where the contents could be encrypted but the sequence number would be transparent.
There are some plans to have a “relayer” node that actively replicates for you, to get better latency guarantees for offline inboxing.
Full vs partial replication: within a group, a set of peer for a single node is a subset of the devices within that group. Messages are thus partially replicated by default, but it is likely it’ll settle on full replication as an individual node is interested in all the messages of a group context. But the contract is a partial copy of the graph, so it is a form of partial replication.
Pull/push call: there are different synchronization modes, i.e. interactive and batch mode. These are coordination-less and up to the client. I.e. either you can request specific messages or offer messages to someone else. This can either be in on go (send all messages) or more efficient by offering message ids, then waiting for a specific request. There doesn’t appear to be any specific “request all most recent messages” API call.
To ensure casual consistency, a message is only delivered once all its message dependencies have been delivered. This ensures Monotonic Writes (MW).
Additionally: it is possible to delete/unshare messages (while retaining some information to fill in the partial graph).
TBD: How exactly it ensures WFR, MR, RYW, MW (above) session properties.
Matrix can be looked at in a few different ways. They provide a suite of protocols, and by default an end user uses their client server API and then each server uses the server to server API for data syncronization.
This is a form of federated or super peer architecture, since a Homeserver has special capabilities. This means individual endpoints don’t need high availability.
It is also possible to do pure P2P by hosting your own homeserver. We won’t look into this here, as it isn’t currently widely practiced and has its own challenges.
Federation: Homeservers can send multiple types of messages, not all which needs to be sync. This is a form of framing. They distinguish between Persisted Data units (PDU), ephemeral (EDU) and queries. PDUs record history of message and state of room. EDUs don’t need to be replied to, necessarily. Queries are simple req/resp to get snapshot of state.
Like Briar, Matrix uses DAGs in PDUs. Their equivalent of a group context is a room.
Additionally, Matrix separates prev_event from auth_events. Auth events are special events that contain previous room state etc. In Briar, this separation is a bit more general and the semantics are encoded in a state machine for each specific data sync client.
PDU validation: checks if events are valid, signatures, hash and various auth rules match.
Soft failure / ban evasion prevention: in order to prevent user from evading bans by attaching to an older part of DAG. These events may be valid, but a federation homeserver checks if such an event passes the current state auth checks. If it does, homeserver doesn’t propagate it. A similar construct does not appear in Briar, since there’s no such federation contruct and there’s no global notion of the current state.
EDUs are used for things such as presence notifications.
There’s a room state that contains e.g. room name, and they have techniques for room state resolution, e.g. a form of conflict resolution. This may look different depending on which room version is used (client id for data sync client in Briar).
Once a homeserver joins a room it gets new events by other homeservers in that room. Users might request previous history before homeserver was part of this room. Homeservers can get previous history from each other with the /backfill API or /get_missing_events.
The above implies homeservers practice partial replication, i.e. a node doesn’t need to have all state to be functioning.
Since Matrix is a form of federated/super-peer architecture, we can also look at it as a client server architecture. A client authenticates with a server in some fashion.
Client discovery of homeservers happens out-of-band, for example by a known URL.
TBD: How does failure work if a user’s homeserver fails? Can you seamlessly be connected to several homeservers?
TBD: Homeserver discovery? It appears that you need to know a hostname for homeservers to connect. It is not clear to me if this can happen in-band, e.g. through some form of propagation.
Conversation history is ‘linearized’ eventually (casual) consistent event graph into an event stream for the end user.
There are two types of room events: state events and message events. State events describe metadata and overwrite each other. Message events are transient one-off events. Applications can also add their own type of events.
To me it seems like this is mostly putting data sync client of Briar into the data sync layer itself. E.g. message/state events are different event types with different semantics. The main difference is the soft ban / intermediation that servers can do to check current auth state. It isn’t clear what this would look like if each server is a homesever, since this enforcement is up to each node. This makes moderation and group membership an interesting topic, and the state can possibly look different for different people. But assuming there’s a well-encoded rule set and clients are well-behaving, this should be fine.
To sync, a client simple calls GET /sync. This returns most recent message events and state for each room, it is thus a pull API. This also gives you a pointer to know how to only get most recent states, as well as how to go further back in the event stream. I.e. a prev_batch and next_batch field.
To get new events, Matrix uses HTTP long polling. There’s thus a persistant connection with a homeserver, that is assumed to have high uptime.
TBD: How is the partial graph compacted into an event stream?
For clients to send events, it sends a PUT request to its homeserver. This means event is acknowledged once homeserver, and homeserver assumes responsibility to deliver it. This is true both for state events and message events.
TBD: If a homeserver goes down, is it possible to do message resends to a different homeserver?
TBD: Why exactly do they make sure a big difference between? Is it simply because of the soft failure / ban evasion case?
They also support redaction of events, which strips off a lot of common keys.
For room creation in client-server API they use POST requests.
TBD: In case of redactions/deletes, how does the hashing change not change? Doesn’t it break the immutability invariant? Same question for Briar.
Homeservers can query each other’s public rooms through a public room directory, which is a form of discovery mechanism.
Client server API end to end encryption is optional. Key exchange happens out of band, and its public key is uploaded to a homeserver.
Multi device: A user has a user id which can be queried through homeserver, and this contains list of all device identity keys.
For E2EE it is only the content of the message that is encrypted from what I can tell, not event types or who it is sent to. This means the DAG is transparent to the homeserver, even though the home server isn’t an end-user endpoint.
TBD / out of scope: They use the Olm crypto ratched for E2EE. It isn’t clear to me how it differs from Double Ratchet.
TBD / out of scope: For group chat they use Megolm variant, which is more scalable for group chat. It isn’t clear to me exactly how it is more scalable in terms of e.g. algorithmic complexity.
It is multi-master since many people can write to a room. Depending on if it is a message event or room state change different conflict resolution might be required.
From a client’s point of view to a homeserver it is synchronous (PUT request acts as a confirmation). Between home servers it is optimistic asynchronous.
Like Briar, it provides casual consistency through a DAG.
TBD: Conflict resolution algorthim for room state exact semantics.
TBD: Treating each user as running their own homeserver, how it change things. Probably requires looking into more detailed Github issues / planning docs / code, as right now the details are a bit hazy.
Note: Clients can send messages to a room without knowing who is participating in it, this is a form of pubsub.
Partial replication, since a homeserver doesn’t need all events to start being used.
Server discovery: Ad hoc, e.g. see https://matrix.to/#/#matrix-spec:matrix.org
TBD look into relevnat existing WIP proposals here: https://matrix.org/docs/spec/proposals
Example: Websockets as alternative transport: https://github.com/matrix-org/matrix-doc/blob/master/drafts/websockets.rst
Transactions: homeservers sync PDUs/EDUcs in transaction of some limited size (~50/100). These are synced in a HTTP PUT, which gives ACK semantics (200 OK). Additionally, errors can be returned with the 200 such as not allowed to send messages to room, wrong version, etc.
Room Version 3 is the latest spec for rooms. In Briar this would be a specific data sync client. It specifies things like room state resolution (actually in room v2 spec). It uses things like revers topological power ordering.
List of super peers aka home servers: https://www.hello-matrix.net/public_servers.php
Decentralized secure gossip platform.
Discovery: Locally it broadcasts UDP beacons for discovery.
Have a concept of pubs, ssb peer available publicly and you can be invited to it. This acts as a form of super-peer (?).
Each user has a feed which is a list of all messages posted by an identity. This is an append-only log. Each message has a pointer to previous one. This points to them using a form of casual consistency.
Each message has a link to previous message with a hash, author which is a public key of where it should appear, and sequence number for position in feed. Also timestamp, hash, content. Field are in a specific order.
Message ID is a hash of messages with their signature.
A SSB client maintains a set of feeds they are interested in.
When peers connect, they ask each other if the feeds they care about have any new messages.
There’s of blobs for attachments etc. They can be linked from meesages. Peers signal with ‘want’ and ‘have’ (request and offer in Briar).
A feed can follow another feed, this means they are interested in messages from that feed. To follow, you post a special message on your own feed. This message is signed with author, and content includes identity of contact want to follow.
Each feed announces which feed they are following publicly. This means clients can arrange feeds into a graph of who follows who.
By doing this, we have several layers of a social graph: a user’s own feed, the feeds it explicitly follows (visible in UI), 2 hops away client fetches and stores messages (but doesn’t display), and 3 hops clients see these feeds mentions but doesn’t store. Layer 0: write, layer 1: read, layer 2: store/fetch; layer 3: aware.
Clients can choose how they want to display these messages.
Pub is a publicly accessible SSB node, it serves social and technical purpose: socially as a gathering point for new users. Technically it has a stable IP and allows incoming TCP connections. Joining a pub means you follow it and it follows you back.
A lot of emphasis is on content discovery, which happens automatically when you join a pub since you are two hops away from other users of that pub. After following a pub a user discovered new feeds and don’t need to follow pub for feed visibility. Though pub helps with replication and accepting incoming TCP.
Any user can follow a pub. But to get pub to follow you back, you need invite code. Invite codes can work in different way (e.g. single use, etc).
It is a form of private p2p, but group based, as you can see more than one hop.
TBD: What happens if a pub doesn’t follow you back?
TBD: Can this be a setting? I.e. access control up to each node how visible they want to be.
Private messages are encrypted and posted to own feed like normal messages but e2ee.
Note: I like their protocol guide that link to specific parts of various implementations.
TBD: Privacy preservation seems unclear. Threat model? Options?
TBD: How does replicaiton and gossiping work in more detail?
Peer connections: once SSB peer discovered IP/port/pubkey of a peer that can connect via TCP it asks for updates and exchanges messages.
Handshake and connection based to create encrypted channel. JSON RPC protocol. E.g. createHistoryStream which asks a peer for list of messages for specific feed.
Scuttlebot behaves just like a Kappa Architecture DB. In the background, it syncs with known peers. Peers do not have to be trusted, and can share logs and files on behalf of other peers, as each log is an unforgeable append-only message feed. This means Scuttlebots comprise a global gossip-protocol mesh without any host dependencies.
A key difference with other p2p architectures is that it doesn’t use singletons such as a DHT. Instead it operates on a human user network which is a form of group-based private p2p. Also see [https://ssbc.github.io/docs/articles/design-challenge-sybil-attack.html](SSB on sybil attack).
A pub is just a normal helper client, and anyone can run it. Thus it doesn’t act so much as a super peer, but it helps with active replication for other peers, if you have a static IP.
All data is eventually consistent, or casually consistant within one log (total order), globally there’s a partial order, similar to Briar and Matrix.
TBD. “There’s a proposal to used signed pings to measure the “freshness” of a feed, but this could only be used in small groups of interested peers.” Not clear where this proposal lives.
TBD. Documentation for SSB replication API - https://ssbc.github.io/docs/ dead link. https://scuttlebot.io/apis/scuttlebot/replicate.html not a lot. Can ask in their chat. Also see https://github.com/ssbc/ssb-db/issues/148
Privacy-preservation: https://ssbc.github.io/docs/ssb/end-to-end-encryption.html “Private-box” proposal (?). For hidden recipents.
It appears to be partially replicated since you can choose how much of the partial graph you want to sync.
Unlike Briar and Matrix, there’s no strict notion of a room with specific semantics. Instead everything is your log and other logs you sync, with fluid discovery/gossiping of interests.
It is optimistic async, since you sync your own log locally.
It is single-master since you only write to your own growing log, and sync other people’s logs separately.
It is either a form of direct or structured network since data locality is in a specific peer, or possibly two hops away.
TBD: Exactly how policy for sharing is decided. I.e. why do my messsages end up at pub, and how does this get to another pub and then to B recipient? Gossip based but more details would be useful on this type of active replication.
The log/feed structure is not encrypted, instead only content is. The main idea here is that it’s a private network and you trust your friends (and your friend’s friends?).
Continue with other real-world applications, such as Tox, Swarm, IPFS, (Whisper, Status), (Bittorrent, Git, Tribler).
Create table of comparison of these.
Collecting descriptions per stack first instead, since (a) there’s no usually very little agreement on what terms to use (b) these tools are generally too new to have been studied in any academic surveys.
Also look into more:
Local peer discovery how generalize and work for us, what’s needed (RFP). This relate to transport properties component, and would be amazing for conferences.
Bittorrent hidden services.
Spend more dedicated time looking into protocol upgradability
/specs repo outline and rough TODOs to get this work started
This looks super interesting I forwarded this to Twitter.com/etzrodtmartin , who is pursuing collaborative research efforts at Akasha.
Combines work from 27 and 28th too.
Plan of action: resume work and look into Tox, Swarm, Tribler etc. Sketch comparison.
Should timebox this and focus on data sync more specificially.
Tox is a p2p instant messenger and protocol with a focus on security and privacy. They have many clients and they support audio and video capabilities.
There is a Tok Tok project as well that seems to be essentially the same (?). Current focus is on things like a formal spec and executable model.
Goals: authentication, e2ee, forward secrecy, privacy, resiliance
Privacy: attempts to avoid leaking public key to 3rd parties, and avoid determining IP address of a given user
– no central servers; bootstrap nodes permission-less and no specific privilege
– connecting to peers behind NAT/FW - UDP hole-punching, UPnP, NAT-PMP, untrusted nodes as relays, DNS tunnels
– to basic DoS attacks with short timeouts ~
Non goal: Anonymity. Instead be compatible with solutions that provide it
By default they provide direct connections between peers, since this is needed for real-time multimedia comms
Crypto Numbers used: based in NaCl/libsodium: public key / secret key / combined key / nonce
(- Crypto box Differentiates between Plain Text and Cipher text)
Transport Protocol below Tox protocol. Supports UDP and TCP. Binary representation a single bit, 0/1.
Socket address: Host address+port number + transport protocol
Node info: transport protocol, socket address and a public key
Protocol packet different message types, ping req/resp, nodes, crypto handshake, dht req, onion req, annonuce, bootstrap info, etc.
DHT based so it is an structured, public p2p network, self organizing swarm of all Tox nodes in network.
DHT keypair acts as node address - renewed every time Tox closes/restarts (!)
DHT Public key of friend is found through onion model
XOR distance metric; client list max size k nodes closest to base key. List can be full, viable nodes can replace if distance is lower
I.e. doesn’t use Kademlia least-recently-seen eviction policy
DHT node state: keypair; close list (node info of neighbor nodes); search list (public keys looking for ~)
DHT search list [don’t quite follow, but more interested in data replication right now - skipping a lot from here]
Check for responsiveness every 60s with Node Requests
Sections on various forms of NAT traversal, hole punching; LAN discovery
contact is public key+nospam bytes+checksum [how does nospam work? => friend_request doc]
Messenger on top, different forms of packets: online/offline/nickname, message, file_sendreq etc
TCP server and client (so get acks that way); if packets dropped TCP client should save them and prioritize re-sending them; out-of-band (OOB) TCP relay
Connect to TCP relay to send onion packets
… if TCP connections is a limited number, how does routing work? TCP server acts as relay for non-direct; can be run on any tox node but more commonly on actual server
TCP server handshake to get secure comm channel, client has to send some encrypted data to confirm the connection to avoid handshake+timeout attack
When TCP client connects it tells TCP server who it wants to connect to; TCP server only allows if both have indicated they allow; does not give any feedback by default if packets arrived or not
…I find it difficult to read the Tok Tok spec. Partly because it has a different architecture and partly because it isn’t very well structured, it mixes interface and implementation details a bunch. It is also 100 pages long… lets ctrl-f some keywords
ctrl-f: no mention of replication, retransmission, log, consistency [hmm]. Some of “sync” and “offline”.
Sync: state and group syncing, if receiving higher version number then search DHT ~.
Friend connection takes care of establishing the connection to the friend and gives the upper messenger layer a simple interface to receive and send messages, add and remove friends and know if a friend is connected (online) or not connected (offline).
Does this mean only online messaging works?
“Mesenger” (with all various message types) is on top of friend_connection, which sits above DHT/onion/net_crypto.
Create connection over relayer, use onion to search.
Can establish direct TCP or UDP connection but it isn’t clear how req/res works, or message history, etc.
There’s a separate Tox Multi device proposal doc In it it seems like data sync is tentative. Oh well. Let’s move on for now.
Interesting to note how Tox and Briar both punt on anonymity to Tor. This seems like it’d be useful to allow other projects to integrate this mixnet, e.g. allowing Tox and Briar to hook into it.
DHT keypair is renewing each restart
Does the DHT Client List eviction policy mean you can force inclusion by generating public key closer? Seems cheap, what does that enable? Indeed, someone mentions this concern down the line:
TODO: this is different from kademlia’s least-recently-seen eviction policy; why the existing solution was chosen, how does it affect security, performance and resistance to poisoning? original paper claims that preference of old live nodes results in better persistence and resistance to basic DDoS attacks;
If the DHT keypair is rotating, how does identity work?
Find it difficult to read and it seems rather ad hoc, perhaps I just need to spend more time with it to decipher
Distributed storage platform and content distribution network. Base layer for web3 stack.
Provide infrastructure for: messaging, data streaming, peer to peer accounting, mutable resourceupdates, storage insurance, proof of custody scan and repair, payment channels and database service
Swarm is a collection of nodes on devp2p network
Swarm allows for upload and disappear; It is a persistent data structure
“Uploading” and “downloading”, uploading is adding to local node and syncing. Downloading querying peers for relevant data then reassemble locally
Optimistic asynchronous replication, thus
swarm up foo.md => hash of swarm manifest; manifest is a json file; manifest ensures you download file with right mime type, multiple entries, etc.
Can also upload to a swarm gateway without running a node
Can modify swarm manifest [how does manifest hash change?]
Dealing with mutability of resources through ENS (blockchain) and Feeds in Swarm.
With ENS can get something like bzz://foobar.eth/quux.txt resolution
Swarm hashes are content addressed so changes to data changes hash; feeds provide single, persistent identifier for sequential data
Why use feeds instead of ENS? Update costs gas; can’t change data fast enough; resolution requires synced blockcchain
feed = user + topic; can give illusion of subtopics by e.g. taking hash of photo and adding “-comment” string.
What is the consistency model of Feeds? It updates, but I assume there can be stale reads. How does it work in case of concurrent updates?
Access control for content: password, by pk for one participant or with act (multi grantee).
ACT strategy - where can I find more info on this?
PSS: Destination can be specific node or neighborhood; specify destination in overlay address space independent of payload
Relay using devp2p and forwarding kademlia, semi-permanent TCP connections between relaying nodes; within neighborhood it uses message gossip
PSS is best-effort and does not guarantee ordering or delivery
Due to forwarding kademlia, pss offers sender anonymity (same packet though? ~)
Optional DH exchange supporting
Chunks (basic unit of storage, <4K), references (cryptographic hash, and possibly decryption key), and manifests (data structure for collections, can be basic kv-store)
A Swarm Hash aka bzzhash is a Merkle tree, ~drop in replacement for e.g. SHA3. Can verify integrity of partial content without having to transmit all of it, thus allow random access.
Since ENS is a smart contract its consistency models follows that of the underlying chain; Feeds is off-chain, so what consistency model does it have?
Swarm node address = sha3(eth acc pubkey)
Swarm implements a “distributed preimage archive” where nodes closest to address of chunk stores the data
Reachability from node (uploader/requester) to storer node is guaranteed by structured network topology that Kademlia provides, with guarantees of max number of forwarding hops
Auto scaling: nodes cache content that is passed on at retrieval, this leads to maximum resource utilisation and a garbage collection process removes least-accessed.
Storage insurance for unpopular content will be provided in future versions to ensure important content isn’t deleted
It thus offers partial replication, and caching+GC
Proximity metric: XOR of two adddresses, binary, log and diff of max distance to get integer where higher represents closer
Uses devp2p as transport layer allows for semi-stable peer connections ove TCP, authenticated/encrypted/sync data streams
Define kademlia connectivity more formally: ~ connected to nodes with all different proximity orders (intuitively: can call someone in family, in neighborhood, city, country, continent)
If points to connected subgraphs has kademlia connectiviy then there’s kademlia topology, and thus a path between two nodes exists, max hops, only need local information
Bootstrap nodes, then each node tries to reach saturation to fill bin with different proximity; once saturated can increase depth (more peers at each proximity level?)
DHT for k-v store, for content address storage usually means nodes are seeders and can serve that content (IPFS?); not just information/fingerprint but the content itself. This is what Swarm calls “Distributed Preimage Archive” (DPA). [This is useful for coercion resistance]
DPA splits into chunks and synced no nodes whose bin they fall into
Once request reaches storer node then it relays back to requestor, assumes forwarding nodes remembers requestors [what if relay nodes go offline?]
Success of retrievals dependings on routes and availability of nodes syncing chunks nearby
Redundantly retrievable to degree n if it can deal with n-1 failures; set of nearest neighbors hold replicas, this is called area of responsibility
Later on in POC4 things like erasure codes for improved reliability might be implemented
Briefly on caching and puring storage, synchronization by caching (along retrieval path)
This means it is a form of active replication
When two nodes connect they offer locally available chunk ~ per dbin [some subtlelty wrt proximity bin and heuristics]
Downstream node completed history syncing if: acknowleged chunks from upstream peer from beginning up until time session started; completed session syncing if synced all since session started
I.e. essentially heuristic for why a downstream node should have certain chunks based on their proximity and bins etc (though need to look into details more)
To reduce BW and redunant syncs from multiple sources, source sends offeredHashes and wantedHashes handshake (similar to Briar)
Data units: message, chunk, file(mime type, integrity), collection
Storage consists of two layers: local store (memory and persistant) and netstore (DPA)
Upload and disappear very powerful, as is coercion resistance (vs IPFS pinning IIRC)
…don’t follow manifest updates changing or hashed? Assume it is hashed but didn’t see explicitly
Feeds update consistency live where who can update?
What does upload mean exactly when transaction finished? Sync locally then with most immediate peers but more in detials
How does replication factor work? [briefly mentioned above]
Who can update a feed?
Look into PSS requirements more
…Forwarding kademlia and anonymity, not clear about how rigorous this is, no mix format, timing attacks etc
More details on ACT?
Best interface for using DPA as extension of data sync?
P2P Mobile https://www.zerotier.com/manual.shtml
Look more into
https://keybase.io/blog/chat-apps-softer-than-tofu (HN thread: https://news.ycombinator.com/item?id=19502657 nice quote:
So to call most E2E chat systems TOFU is far too generous. It’s more like TADA — Trust After Device Additions.
MLS concurrency ongoing issue:
Probably more in Zotero I forgot to add
WARNING: This is an early draft, and likely contains errors.
This document compares various forms of data sync protocols and applications, along various dimensions, with the goal of making it easier for you to choose which one is for you.
Let’s start with some definitions.
Node: Some process that is able to store data, do processing and communicate with other nodes.
Peer: The other nodes that a peer is connected to.
Peer-to-peer (P2P): Protocols where resources are divided among multiple peers, without the need of central coordination.
Device: A node capable of storing some data locally.
User: A (human) end-user that may have multiple devices.
Data replication: Storing the same piece of data in multiple locations, in order to improve availability and performance.
Data sync: Achieving consistency among a set of nodes storing data
Mobile-friendly: Multiple factors that together make a solution suitable for mobile. These are things such as dealing with mostly-offline scenarios, network churn, limited resources (such as bandwidth, battery, storage or compute).
Replication object: Also known as the minimal unit of replication, the thing that we are replicating.
Friend-to-friend network (F2F): A private P2P network where there are only connections between mutually trusted peers.
Content addressable storage (CAS): Storing information such that it can be retrieved by its content, not its location. Commonly performed by the use of cryptographic hash functions.
Consistency model: …
Network churn: …
Light node: …
Private P2P: …
Structured P2P network: …
Unstructed P2P network: …
Super-peer P2P network: …
Group-based P2P network: …
Cryptographic hash function: …
We look at generally established dimensions in the literature [TODO] [TODO], and evaluate protocols and applications based on these. Specifically the focus is on p2p applications that perform some form of data synchronization, with a bias towards secure messaging applications.
All notes are tentative and are based on the provided documentation and specification. Code is generally not looked into, nor has any empirical simulations been performed. These results have yet to be reviewed so take them with a grain of salt.
These dimensions are largely taken from the survey paper [TODO].
For single-master, there’s only a single node that writes to a specific piece of data. The other peers purely replicate it and don’t change it.
For many of the studied systems, content addressable storage is used. This means the replication object is usually immutable, and it is only written to once. As a side effect, many systems are naturally single-master from this point of view.
This is in comparison with the survey paper, where they are more interested in update-in-place programming through replicating SQL DBs and other “rich” data structures.
However, if we look at what is semantically interesting for the user, this is usually not an individual message or chunk of a file. Instead it is usually a conversation or a file. Seen from that point of view, we often employ some form of linear or DAG-based version history. In this case, many participants might update the relevant sync scope. Thus, the system is better seen as a multi-master one. To capture this notion I’ve modified single-master dimension to be w.r.t. replication object or user scope point of view. I suspect the latter is more informative for most cases.
TODO: Tighten up above paragraph with better definitions.
TODO: Add definitions of below
TODO: Add more relevant dimension
TODO: Possibly decompose into further subproblems
TODO: Possibly re-structure as who-what-when-where-how-withwhat
This includes both applications and specification. The level of rigor and nomenclature varies between projects.
Briar and its associated Bramble protocol stack [TODO]
Matrix and its specification [TODO]
Secure Scuttlebutt [TODO]
(- Tox and its Tok Tok specification [TODO])
Apples to apples: Does it really make sense to compare Matrix with something like Swarm directly? This also depends on how decomplected protocols are and to what extent they can be studied in isolation.
More technologies: Bittorrent, Git, Tribler, IPFS. Whisper, Status.
Similarities and differences: Since a lot of protocols make the same choices, it might make sense to break similarities apart and focus on differences. Similar to what is done in Whisper vs PSS [TODO].
|Replication object||Message (DAG)||Message* (DAG/*)||Messages (?) (Log)||Chunks (File/Manifest)|
|Full vs partial replication?||Partial||Partial||Partial?||Partial|
|Consistency model||Casual consistency||Casual||Eventual / Casual|
|P2P Topology||F2F Network||Super-peer||Group-based||Structured|
This dimension is a bit hairy:
| Read-only? | Read&Write | Read&Write | Read&Write | Read&Write | - it depends on what we see as the minimal object of replication, and I’m not satifised with the current separation
Maybe it makes more sense to have two replication objects, e.g. chunks and DAG or log, as opposed to changing notion of single-master etc
Matrix depends: should capture auth state semantics
How deal with other things that are kind of replicated but differently? E.g. metadata, etc. Auth state, ephemeral, manifests, feeds, etc.
Continued with data sync comparison: https://github.com/status-im/bigbrother-specs/blob/master/data_sync/p2p-data-sync-comparison.md
Protocol weekly notes https://notes.status.im/EVxnIQeqTpquNETtdXcqNw#
Continued with data sync p2p comparison: https://github.com/status-im/bigbrother-specs/blob/master/data_sync/p2p-data-sync-comparison.md
Not happy with the dimensions break down. Tweaking a bit:
*Request for comments: What’s a better way to decompose these properties? Ideally something like 2-5 dimensions that matter most. Right now it reads a bit like a laundry list, or like an ad hoc classification.
These dimensions are largely taken from the survey paper by Martins as well, with some small tweaks. To make it easier to survey, we divide up the dimensions into rough sections.
Replication control mechanisms.
As well as filling in properties and comparisons of various properties.
More technical details on SSB: https://github.com/dominictarr/scalable-secure-scuttlebutt/blob/master/paper.md
Been a while since last post. Let’s post a brief update, starting with the two goals that were posted in OP a month ago.
- Research and hacking.
a) Continue studying relevant literature and existing solutions
b) Document findings and create juxtaposition of different approaches
c) Informed by above, resume PoC hacking and precise specification
Once there’s confidence in PoC and spec, make a plan for getting it into the app
- Finding great people.
a) Keep track of researchers and people with relevant expertise
b) Triage based on their relevance and likely availability
c) As budget and time frame allows, reach out for collaboration
1 (a) and (b) have been done enough for (c ) to be resumed. It allowed us to get a deeper understanding of things such as consistency models, how people look at replication in the literature, and survey various approaches to this problem.
While a and b could continue for longer (much longer), we have enough to get a minimal viable version going (more on this later). As long as it supports upgradability we can improve things as we go along. This is important as it allows us to stay on the critical path.
We’ve also started having more regular calls (https://github.com/status-im/messaging-pm/) with other people under the Web3 Messaging banner. This includes closer collaboration with mixnet researchers such as Nym/Panoramix, and also recently the Swarm team.
For the continued research and juxtaposition, while slightly deprioritized last few weeks, it is also something important that we should keep working on. There are about ~10 bigger ish issues that need more thinking, as well as some feedback and misc TODOs that should be addressed. All of thee are in-line in here https://github.com/status-im/bigbrother-specs/blob/master/data_sync/p2p-data-sync-comparison.md
The proposed next milestone of the p2p data sync survey paper is to create a solid draft survey/research paper. This should be something of sufficient quality that we can put it out to the larger community, including academia. The idea being that this allows us to be evaluated seriously by security/ethereum/dist-sys community, and this can have other positive side effects such as:
The latter is already partly happening through e.g. Web3 Messaging calls, and by being public with research we have multiple groups reach out to us, being featured in Week in Ethereum, etc. We can reach wider than the Ethereum community though.
More on this in another update.
Some PoCs that have been written recently that relate to data sync:
Hello Staples - Swarm/PSS/Feeds PoC: Hello Staples - Swarm PSS/Feeds PoC for #buidlweek
Some half-baked ideas and PoC around using Merkle trees https://notes.status.im/MLGgpdgqRzeyTqVWkl7gjg?both
Slightly out of scope of data sync per se, but there are some dependencies and interface points. We’ve made a bunch of progress on documenting on our current protocol stack, largely thanks to Adam.
This also includes discussions around bandwidth saving changes (while keeping compatibility), and the dependencies this has on things like moving to device-based comms, multidevices, and so on.
You can see the umbrella issue of things that have to be done here: https://github.com/status-im/specs/issues/10
The goal with this work is to get a minimal viable data sync spec and PoC out as soon as possible so the app can use it. This can later be enhanced and upgraded. You can read Dean’s log here Minimal Viable Data Sync Research Log
The current description is here: https://notes.status.im/O7Xgij1GS3uREKNtzs7Dyw#
As part of this we have a set of requirements that we have been going back and forth on, in an attempt to lock down the things we know now. More on these specific requirements in the next section. This is still an open discussion, and to read more about this please consult above hackmd or ping me or Dean.
Here are the proposed requirements as of today.
MUST sync data reliably between devices.
By reliably we mean having the ability to deal with messages being out of order, dropped, duplicated, or delayed.
MUST NOT rely on any centralized services for reliability.
By centralized services we mean any single point of failure that isn’t one of the endpoint devices.
MUST allow for mobile-friendly usage.
By mobile-friendly we mean devices that are resource restricted, mostly-offline and often changing network.
MAY use helper services in order to be more mobile-friendly.
Examples of helper services are decentralized file storage solutions such as IPFS and Swarm. These help with availability and latency of data for mostly-offline devices.
MUST have the ability to provide casual consistency.
By casual consistency we mean the commonly accepted definition in distributed systems literature. This means messages that are casually related can achieve a partial ordering.
MUST support ephemeral messages that don’t need replication.
That is, allow for messages that don’t need to be reliabily transmitted but still needs to be transmitted between devices.
MUST allow for privacy-preserving messages and extreme data loss.
By privacy-preserving we mean things such as exploding messages. By extreme data loss we mean the ability for two trusted devices to recover from a, deliberate or accidental, removal of data.
MUST be agnostic to whatever transport it is running on.
It should not rely on specific semantics of the transport it is running on, nor be tightly coupled with it. This means a transport can be swapped out without loss of reliability between devices.
This brings down the total list of requirements from 11 conditions to 8, and 5 SHOULDS to 0. This is still a work in progress and feedback or questions on these requirements are welcome.
Just some points that might be worth mentioning.
It was brought to our attention that Teller Network would be interested in using data sync for state channels. This is one of several alternatives being evaluated, and its requirements would roughly be reliability (why mailservers don’t cut it for now) and scalability (why Ethereum PoW chain might not be the best choice). Other alternatives being evaluated are POA/POS chain, etc. One idea here is to choose a short-term solution, black box it, and work on something more desirable over long term, such as generalized plasma solution, etc.
From a data sync point of view, this is interesting as a specific use case that fits the requirements. A concern here is in terms of timeline.
Another point worth emphasizing is making sure we see data sync as generalized messaging, including machine to machine communication, and don’t get blindsighted by our focus on supporting the app. There are probably more areas where we aren’t taking this general view sufficiently seriously (e.g. assuming human users everywhere).
Main strands of work.
Refine minimal requirements above, associated spec with wire protocol and protobuf, and get a working PoC that we can (later) use through console-client, and possibly other means. Aggressive deadline for inital version of this has been set at end of April, but this might be revised.
Work on getting a a solid draft for all the associated specs in spec repo. This is ongoing work and with Adam going on vacation this might take a tad longer than expected. Old ETA for this was mid May but may be revised.
Associated with spec effort is also critical path for getting Whisper partition topic bandwidth consumption with compatiblity into app. This is a must for a public launch, and interfaces with existing spec, the app, multi device pairing, and data sync.
As well as continue with general collaboration with Messaging for Web3 teams. Potentially something more with Swarm team as there appears to be some opportunities there in the medium term.
I probably forgot some things, but that’s the (long) gist of it in terms of updates.
Until next time!
Compilation of notes from previous week. Today most focus was on Bloom filters. Specifically as they pertain to dealing with data loss and privacy preservation (see minimal requirements above), as well as to what extent they are a necessary optimization for bw/latency, and how they relate to sync with untrusted nodes. See research questions at end for more details.
Realized one thing that was bugging me with the existing survey work, is that it largely compares these different sync protocols in a vacuum. This means things that shouldn’t be captured there are, and there’s not explicit focus on constraints of the problem, nor proposing a solution.
While the desired output here is code into the app (this remains the critical path), we also want to keep doing this paper in parallel, being more problem and solution oriented as opposed to detached survey. To be continued.
Some notes and misc resources I didn’t get around to post before. More of a dump/reference.
Also revisited SoK and conversational security a while ago:
SoK Small note: they say self-destructuring messages is impossible, which is true, but they are possibly missing local threat model as seen from real world issues.
Three small pieces: (Notes captures elsewhere)
Dealing with large grup chats, a sketch: <notes in physical notebook, essentially random selection sync>
Git for CS
bloom filter and consistency and date integrity
because pictures are pretty
<Notes from Git internals and object model, tags,references, remotes etc missing>
In this paper they go over basics of Bloom filters, and surveys multiple variations of Bloom filters with different characteristics.
They also go through various applications, from general search, caching, network routing to p2p data sync.
Achieving Blockchain Scalability with Sparse Merkle Trees and Bloom Filters. The main idea in this blog post is to combine Sparse Merkle Trees (SMT) and Bloom filters to increase Bitcoin scalability. SMTs are a more sparse version of Binary Merkle Trees, and leverage default hash values for empty leafs. The SMT is used to prove membership of a transaction, whereas the bloom filter is used to prove non membership of a transaction. That is, to prove that an unspent transaction hasn’t been spent in a previous block. This is useful as you can have a compact representation, instead of going over all block headers and prove a transaction hasn’t been spent.
Similar ideas have been proposed for e.g. Plasma in Ethereum. See https://ethresear.ch/t/plasma-cash-with-sparse-merkle-trees-bloom-filters-and-probabilistic-transfers/2006 I believe there’s a difference here if you use something UXTO like vs account based. There are some concerns on the performance of SMTs, but this is largely irrelevant at the interface level. See post by Vitalik for some ideas to optimize this. https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751
See papers above, things to read more.
Only skim. Most sync uses “slow sync”, which is band for BW and latency. Their idea: synchronize hosts using one message in each direction with length |A-B| + |B-A|. Their approache CPISync supposedly more efficient than even standard Bloom filter approaches, using some kind of characteristic polynomial (didn’t dive into math details).
InformedContentDelivery AcrossAdaptiveOverlayNetworks. Optimizing throughput through better set reconciliation and collobrative downloads (p2p?). Also erasure coding.
Efficient Peer-to-Peer Keyword Searching. Quick search with low bandwidth using Bloom filters and DHTs. Inverted index over DHT. Some mathy calculations and experimental results, including for cpu,latency and with forms of caching.
TRIBLER: a social-basedpeer-to-peer system. Exploiting similar interest and friendship/community to increase usabiliy/perf in p2p. Set of extensions to BT. Talks about 5 challenges: of achieving decentralization, availability, system integrity/trust, providing proper incentives and finally network transparency (NAT traversal, etc). Taste-buddy-based content discovery. Buddycast. Bloom filters are used for their Megacaches. Using empirical data and carwler to see Friendster average friend (~243) and f2f connections (9147), within order of magnitude same for others. This means ~260 bytes to discover friend-of-friend, and enable thousands of peers to exchange a lot of data quicky. Buddycast: taste buddy exploration (random peer) vs exploitation (taste buddies). Ratio thereof.
How they solve the availability issue and how this relates to replication between untrusted nodes, Swarm etc.
Need to look into this in more detail
If you randomly sync with nodes, wouldn’t this impact sync scope? For a topic, say.
https://pdfs.semanticscholar.org/94e6/26b7ff25b07d23fd345aad254abbdd0a574b.pdf. Data bundle synchronization. Bloom filters, NAT traversal, data bundle selection algorithms. Good for high churn. Node from candidate list (probabilistic to get good behavior, 1%/45%/50% iirc, tracker/friend/f2f/random? ish). You select a range of bundles to sync, but which are these nodes? Only a range. They mention 100k bundles, so that’s all their content?
Flow Model: Node selection -> Bundle Selection -> Bloomfilter creation -> NAT traversal -> Waiting for reply. Need to read and think about this more - my mental model of replication space is different now from last time.
Churn resiliance - 1000 nodes 30m to 30s experiment.
Also, this paper is better than their wiki. (Dispersy Read the doc system overview).
No PDF found. Cai, Hailong, Ping Ge, and Jun Wang. “Applications of bloom filters in peer-to-peer systems: Issues and questions.” 2008 International Conference on Networking, Architecture, and Storage. IEEE, 2008.
http://netgroup.uniroma2.it/wp-content/uploads/2015/04/BBL-PSD-cameraready.pdf - Bloom filters and provable privacy, to read.
(Delft, Niels Zeilemaker etc? Where are these people now? Reach out?)
Can Bloom Filters be used to do more efficient data sync?
Are Bloom Filters necessary for a minimal version of data sync, or can they can be added after the fact?
Leaning towards adding after the fact as enhancement being a desirable possibility.
TODO: Still here - the main unknown is in terms of how to deal with sync scope and sync with untrusted nodes.
Can we generalize the node selection and bundle selection step? This might make it more elegant (make it work->right->fast).
Can Bloom filters be used/relied on for privacy?
See paper (http://netgroup.uniroma2.it/wp-content/uploads/2015/04/BBL-PSD-cameraready.pdf) for analysis. Also how does Tribler deal with this? Vs private overlay.
Can Bloom filters ability to prove non-memberhip be used to deal with exploding messages and data loss?
To be explored.
How big is the perf difference for reasonable parameters and Bloom filter?
I.e. bandwidth saving, to calculate.
TODO: Still here - need to set some assumptions and do some math, or compile existing empirical data. Can probably KISS to get order of magnitude intuition.
Look into above questions more in detail, especially as blocking critical path. Study Tribler in more detail.
iirc it doesn’t, by sharing a bloom filter you allow a node to discern information about you, it’s similar to the sync with untrusted nodes issue
Looked into Dispersy bundle synchronization and Tribler into more detail. Efficient sync using subset bloom filter selection, as well as some good ideas on dealing with challenging networks of various types.
Just to capture briefly ideas from physical notebook. Terse version.
Leverage multicast when underlying protocol allows it, i.e. use | topic | message | for sending offers/acks. This assumes you send to many IDs and these are all listening to that topic.
Random selection for large group chats. I.e. pick K out of N to offer/ack to, this allows not having quadratic scaling for naive syncs.
Log collator idea. f(topic, logs) => topic, one log. Problem: Censorship resistance (proof of data availability~)? No denial of service.
The main idea is to exploit the social connections between people who share similar interests, and use this to increase usability and performance in p2p networks.
Content discovery and recommendations is based on taste buddies, i.e. users with similar interests.
Talks about decentralization/availability/integrity/incentives/network transparency as being fundamental challenges in p2p networks.
Architecturally, it is a set of extensions to Bittorrent. It has a module for social networking, and ‘megacaches’ to locally query metadata. This meetadata are things like friends list (information on social network); peer cache (info on super peers); preference cache (preference list of other peers). All of these are under 10MB in size.
The problem domain is Bitorrent so static files. In UI there’s downloads/friends/files liked and taste buddies.
They have a buddycast algorithm (epidemic based on social graph) and a ‘peer simularity evaluator’.
Bootstraping use random super peer to get more nodes, then use those other ones.
Session boundary problem - using stable peer ids, i.e. keypairs.
Bloom filters for storing and testing set membership for these megacaches. Filtering peers from messages that are known to destinations.
Size of these filters functions of expected connections. Empirical data: Friendster 240 average friends and FB 9100. [FB ~200 median, 340 average]. (This makes sense, since 100 and then 100*100 with some overlap).
To get a bloom filter with 1% false positive rate you need <10 bits per element, so that’s 260 bytes to test and figure out common friends of friends.
Buddycast: Each peer has a number of taste buddies in their megacache with preference list (what content they want) and random peers (i.e. no known preference list). Then every 15s, each peer can either exploit or explore. Exploit = connect to taste buddy, explore = conect random peer. This ratio can be titrated.
A buddycast message also has taste buddies, top 10 preference list and random peers. Buddycast can be disabled for privacy. Peers are listed either by freshness (random peers) or similarity (~overlapping preference lists?).
Briefly talking about BT and rarest-first, tit for tat, and BTSlave using repeaters to increase content replication.
Curious, does the megacache concept scale for messages? Assume a message is 1KB, and average user sends 100 messages a day (70 for slack average sent). If you are talking to 100 other people (~200 friends in some constellation of N chats), that’s 10k messages per day or 10 mb per day already. The key thing here is that it’s metadata Tribler is storing, not messages themselves, which (a) allows it to be a cache, cause data integrity not hard requirement (b) constant space, ish (prune preference list at top N).
What would happen if we used this on top for most popular/recent content? Still allowing for other means.
This is their academic paper equivalent to https://dispersy.readthedocs.io/en/devel/introduction.html - not clear exactly what overlap looks like. I find it interesting that in their docs they call it Distributed Permissions System, but in the paper they emhpasis data dissemination in challenged networks. EDIT: Oh, cause this is about the Bundle Synchronization in particular, not Dispersy or how they use it.
Requires minimal assumptions about reliability of communication/network copmonents. Decentralized and pure p2p. Specifically for challenged networks.
What are examples of challenged networks?
Mainly: Vechuilar ad hoc networks (VANET), Delay Tolerant Networks (DTNs).
Additionally: P2P Networks and smartphones.
What’s challenging about VANETs?
Connection windows are small.
What’s challenging about DTNs?
Connections are only possible when network isn’t very well-utilized.
According to Dispersy, what’s challenging about pure p2p networks?
In past, these were treated in isolated. For Dispersy, these concerns are combined.
What’s the main idea in Dispersy?
Nodes advertise locally available data in one message, and repeat random interactions lead to quick spreading of data.
NOTE: It appears that the goal is to spread all bundles to all nodes, i.e. a form of full replication. It is also active, since all nodes are spreading all data.
Individual bundles can appear out of order, so it’s different from Delivery in Bramble. They suggest not having dependencies on bundles.
Key things in paper:
What are the three forms of distributing updates Demers proposed?
direct mail, anti-entropy and rumor mongering.
According to Demers, how does direct mail data distribution work?
Update is sent from one node to all other nodes.
According to Demers, how does anti-entropy data distribution work?
Node chooses random node and resolve difference in state.
According to Demers, how does rumor mongering data distribution work?
Node receive new update (hot rumor), then forward update until it goes cold (received from many nodes).
Demers initially thought anti-entropy too expensive; optimiztion to use check-sums etc. (NOTE: Before Bloom filters popular?)
VANET can be seen as P2P due to churn and many nodes w/o central component.
What is the network churn in VANETs due to?
Movement of the vechile.
Lee had urban vechiles with event summary such as license plate and then bloom filter to detect missing summaries. Bloom filters as being very efficient for membership testing, in Lee’s case using 1024 Bytes. (NOTE: for 1% false positive rate that’d be ~1000 cars). They also coupled this with a push to one-hop neighbor. The bloom filter here is thus only used to detect missing summaries. They call this a form of harvesting.
‘Bundle synchronization middleware’ for challenged networks. Extends the ant-entropy method using compact hash representation (Bloom filters). Allows two nodes to compare data sets w/o sending complete copy.
TODO: Insert overview of sync and receive
In Dispersy, What does the synchronization five steps look like?
Synchronization extends harvesting by Lee. They only have a range of bundles, which keeps false positive rate low w/o big bloom filter.
NOTE/QUESTION: How does that follow? Bloom filter size is dteremined by bits-per-element (m/n), but if the element is the set of possible bundles what does it matter what the specific range is? Does this imply the recipient knows which range it is supposed to receive, in order to limit the universe of possible elements?
They say “in contrast Lee used fixed size w/o selecting bundles”. This seems to imply the recipent knows what the range is.
Allow for different types of challenged networks, so Dispersy is modular. They have a few different components:
All nodes communicate in one or more overlays.
What’s an overlay in p2p?
An additional network build on top of e.g. Internet.
A public key is used as identifier of an overlay, which has to be known to nodes joining.
NOTE: Is this sloppily written or am I misunderstanding? Is this just NodeID or do they mean some kind of bootstrap node / Network ID? EDIT: I guess if we look at each node as having their own overlay.
Why did Dispersy choose to run on UDP over TCP?
Because it allows for better NAT firewall puncturing.
Each overlap has a candidate list,
What is the candidate list that each Dispersy node has in each overlay?
List of active connections within that overlay.
When we connect to an overlay, the candidate list is empty, thus requiring node discovery.
What’s the most basic form of node discovery if you have an Internet connection?
What characteristics does a tracker have for node discovery?
(1) Known to all nodes (2) Must be connectable (not behind NAT-firewall).
What does a tracker do in terms of node discovery?
(1) Maintains list of nodes for several overlays (2) Returns these upon request.
After populating candidate list with initial nodes, for example by asking a tracker, these can be used for new connections.
A node A asks node B for introduction to new node, B sends reply with node C. Then A can puncture NAT.
Description of NAT puncture mechanism, more in later section.
We have to select a node from candidate list to send intro request to, but there might be attacker nodes in the list.
Why is node selection in p2p non-trivial?
You might connect to a malicious node, leading to e.g. eclipse attack.
What’s manipulating the candidate list of nodes in p2p called so that it includes attack nodes?
What can a malicious node do after eclipsing a node?
Control all data received by victim.
How does Dispersy create a more robust node selection algorithm?
By dividing candidate list into three categories, one with two subcategories.
What are the 3-4 selection list categories in Dispersy?
When selecting a node from candidate list, category 1 is 1% of the time, 99% divided by category 2 and 3. Each subcategory gets 24.75% of the time.
NOTE/TODO: This probably generalizes to how Bitcoin and Ethereum deals with Eclipse attacks, in terms of buckets etc. Might be worth comparing these.
For each step in Dispersy node selection, what’s the probability of choosing each category?
1% trusted, ~50% nodes we connected to before, and ~25% for each of other nodes having contacted us before.
How does Dispersy’s node selection algorithm guard against eclipse attacks?
Attacker nodes will (usually!) end up in the third bucket, which has a cap on the selection probability.
In terms of which node is selected in each category, this is elaborated on later. But roughly oldest for NAT timeouts, as well as most similar friend (IIRC).
If an attacker has a lot of resources they can still eclipse node, hence the use of trusted nodes.
NOTE/TODO: Eclipse video worth rewatching with better notes on mitigations. Also: How does 1% impact eclipse possibility to do harm? If you have limited amount of connections you might still not reach 1% case, so seems to depend on what harm individual/set of nodes can do.
Trusted nodes (i.e. trackers): Contacting a trusted node will completely reset candidate list (!). They did experiments with manipulating category 2 nodes.
Why are trusted nodes (trackers) less suspectible to eclipse attacks?
They are contacted a lot and constantly by honest nodes, which makes it harder to pollute the candidate list. (N.B. Sybil attacks).
NOTE/TODO: Read up more on Sybil attack and Sybil resistance.
NOTE: They seem to claim 4 million concurrenct nodes in P2P empirically (cite 18, Gnutella), and implicitly that the risk of Sybil attack for that is low.
NOTE/TODO: How does recency impact the sybil attack resistance? IIRC in Eclipse presentation there’s an argument that old nodes are safer, I guess this depends on bucket design? I.e. if % allocation changes.
How many nodes connected to the Internet are behind a NAT, according to Halkes et al 2011?
Two thirds, up to 64%.
NOTE/TODO: this number might be even higher nowadays with smartphones? Read up on current state of NAT traversal, and how this changes with different protocols, i.e. QUIC etc.
As a consequence of this, each introduction step is used with distributed UDP NAT puncturing mechanism.
How does Dispersy get around the fact that 64% of nodes are behind a NAT?
By integrating each node discovrey step with a distributed UDP NAT puncturing mechanism.
How does the UDP NAT puncturing mechanism work in Dispersy? Three steps.
NOTE/TODO: A bit fuzzy on the details of how the ports are matched up, worth revisiting basics. Same re NAT timeouts.
Due to NAT timeouts, nodes are invalidated after some time (~30s-1m). See Halkes (cite 9) for more.
Bundle synchronization through bloom filters, allow nodes to check for missing bundles. Additionally, piggybacking on introduction mechanism to allow just one message to be sent.
Why is it extra important to limit size of bloom filter in Dispersy?
Due to UDP + piggybacking on introduction message, so that the MTU of link isn’t exceeded.
What happens if the MTU of the link is exceeded for UDP?
If UDP consists of multiple fragments, there’s a higher probability it will be lost.
What’s a typical MTU size used on the Internet, according to RFC 3580?
1500 Bytes (2304B for 802.11).
NOTE: Might be more up to date resources for this / gotchas for various links.
NOTE/TODO: How big would e.g. Sphinx packet format be? Same for various types of standard cryptographic payloads, e…g Handshake. If they are written with TCP in mind, perhaps this is a gotcha.
<1000 bundleds can be synchronized with 1% false positive rate for 1024 Bytes; <2000 for 10% false positive rate.
Assuming bloom filter of 1024B, how many messages can we synchronize with 10% false positive rate?
What’s a flaw in Lee’s MobEyes bloom filter design that uses 1024 Bytes filter?
There’s no limit on bundles being synced, which means the false positive rate shoots up if we add e.g. 2000 vechiles (10% for x2).
How does Dispersy get around the flaw in Lee’s MobEyes bloom filter parameter choices AND MTU limitations?
By fixing false positive rate to 1% as a constant, and limiting number of bits available (MTU) (m), this means Bloomfilter has a fixed capacity, so we select subset of bundles to synchronize (n).
Based on global time property of each bundle, which is an implementeation of Lamport’s logical clock.
What property is subset selection in Dispersy based on?
Global-time property of each bundle, which is using Lamport’s logical clock.
Global time is highest global time received by node + 1 when creating a bundle. NOT unique, but provides partial ordering in overlay. Assume distribution is uniform ish.
Two heuristics for defining which subset to sync.
How does global time property help selecting what to sync in Dispersy?
By specifying a subset range of this (non-unique) global time to sync.
What heuristics are used in Dispersy to select subset to sync in Dispersy and when are they used?
Modulo heuristic when a node is lagging behind, and pivot heuristic when it’s almost up to date.
Modulo heuristic: count number of bundles, divide by Bloom filter capacity. E.g. 10k bundles, bloom filter 1000 capacity, use modulo 10. Then use random offset, e.g. select every 10+n, e.g. 1, 11, 21 etc.
What does modulo heuristic in Dispersy resemble and what does it not require?
Linear download (1, 11, 21 etc) and doesn’t require state.
What’s the downside of modulo heuristic in Dispersy?
If almost caught up, it’d take a modulo number of steps to sync up, e.g. 10th bundle +1/+2 etc offset.
For pivot sync, using exponential distribution between 0 and (locally known global time). Then select bloom filters to left and right, and pick the one~. (NOTE: A bit hazy on exact details here, would need to revisit; exponential means bias towards new).
**NOTE/TODO: How would we allow for these types of sync modes? It’d require global-time partial ordering visible for all nodes, AFAIUI
What does a node do when receiving Bloom filter in Dispersy?
Checks if it has missing bundles to send, based on local subset of bundles and testing against Bloom Filter.
What does receiving node in Dispersy need to find out if it has missing bundles to send?
Nice math based on false positive rate, MTU, bundles etc. Depending on synchronization level.
NOTE: Interesting to note re false positive rate, AFAIUI this is inversely related to BW perf.
Actual simulation and empirical study of things described above. Including NAT experiments, random node selection etc. Skimming for now.
Churn resiliance based on session time. Propagation speed. Bandwidth consumption. High workloads. Internet deployment (integrate into Tribler).
NOTE: Cell phone perfmrance is much worse than WiFI connections. I.e. carrier grade APDM routers, hard to puncture. Also UDP concerns.
NOTE/TODO: Look into smartphone NAT traversal state of the art.
To sync 100k bundles Dispersy connected to ~1000 nodes and consumed 30 Mbytes of BW per run. (NOTE: Assuming bundle is ~1KB that’s 30*1000=30k for 100k or 1/3? Eh, unit is off somewhere).
Sucess rate of 77% for 15 different NAT traversal (N.B. smartphone worse). Can handle excessive churn (session times 30s).
Awesome paper, much better and clearer than Tribler Dispersy docs. Wish I read it in detail earlier. Lots of beautiful ideas and backed up by real world experience and math. Still need to think about the untrusted stuff, but at least the dependencies and mechanics are more clear.
Some citations from paper:
Bloom, Burton H. “Space/time trade-offs in hash coding with allowable errors.” Communications of the ACM 13.7 (1970): 422-426.
Demers, Alan, et al. “Epidemic algorithms for replicated database maintenance.” ACM SIGOPS Operating Systems Review 22.1 (1988): 8-32.
Halkes, Gertjan, and Johan Pouwelse. “UDP NAT and Firewall Puncturing in the Wild.” International Conference on Research in Networking. Springer, Berlin, Heidelberg, 2011.
Huang, Hong-Yu, et al. “Performance evaluation of SUVnet with real-time traffic data.” IEEE Transactions on Vehicular Technology 56.6 (2007): 3381-3396.
Laoutaris, Nikolaos, et al. “Delay tolerant bulk data transfers on the internet.” ACM SIGMETRICS Performance Evaluation Review. Vol. 37. No. 1. ACM, 2009.
Lee, Uichin, et al. “Dissemination and harvesting of urban data using vehicular sensing platforms.” IEEE transactions on vehicular technology 58.2 (2009): 882-901.
Singh, Atul, et al. “Defending against eclipse attacks on overlay networks.” Proceedings of the 11th workshop on ACM SIGOPS European workshop. ACM, 2004.
Ran out of time for timebox, and still have some synthesizing to do, but thought I’d post it here for e.g. Dean et al. TODO: understand in more detail the following points:
Existing spec for MVDS: https://notes.status.im/O7Xgij1GS3uREKNtzs7Dyw?view#
Data Sync log research including Dispersy Bundle Sync: (Mostly) Data Sync Research Log
Bundles and messages are used interchangeably.
While the currently suggested implementation takes care of the requirements, it has a few things that can probably be improved:
Churny nodes means mostly-offline, smartphones, etc.
One way of doing this is to extend the current protocol proposal with some ideas from Dispersy Bundle Sync algorithm (DBS hereafter).
DBS uses stateless sync with bloom filters on subset of bundle rages. Essentially it goes something like this:
They assume you want to sync all data with all nodes. Essentially you have a candidate list and then you pick a (possibly untrusted) node from it, using a specific selection algorithm.
For us, we can do this per sync scope, and let nodes be the participants by default. As an extension, other nodes (i.e. any node) can be included, but there are some privacy considerations to work out to make this workable.
Even if we leave node selection alone it would already be an improvement, as you can leverage existing nodes in a group chat, with no difference from current MVDS setup.
The tricky part, and the one that requires some modification, is how to do bundle selection. To make the Bloom filter efficient, we need to be able to select a subset range of bundles/messages to sync. This has some requirements, things that should be doable by any node. That is, it shouldn’t be like a DAG inside the message.
For Bloom filter creation, what it gives you is a way to check that someone is missing messages. I.e. A sends B some Bloom filter of a range of bundles, and B can test against this range. If they have other messages A doesn’t have, it can send them, just like we do in MVDS right now. And B would do vice versa.
To do bundle selection we need a few things. The main property that helps us cut bundles up is the global time property. This is a Lamport logical timestamp which provides a partial ordering of bundles. When a bundle is created, it takes the highest global time it has seen and +1. It is assumed the range of these timestamps are roughly uniform, and they are not assumed to be unique.
We probably want this to property to be outside the payload, as this allows any node to participate in this sync. I imagine this would be in the header. I imagine this will be per sync scope, but it might also be global. We need to figure out trade-offs and how much this needs to be specified.
In addition to this global time property, we need a few more things. These are more like mechanisms and things for the Bloom Filter Offer payload.
Essentially we want a way to take a specific subset of all bundles available. Then depending on what sync mode we have (old, lots of missing bundles) (new, just give me latest) we use different heuristics. These are the modulo heuristic and pivot heuristic. Without going into too much detail, the main thing we need to communicate here is:
In the modulo heuristic case, if we want 10k bundles, we might pick modulo 10, then offset 1…n and in each sync send a bloom filter with metadata: [lamport low, high], 10, 1. Then receiver would use bloom filter and check if sender is missing something in bundles: 1, 11, 21, etc. Then repeat process for each offset until we have synced across the whole bundle range.
NOTE: Need to confirm this is how they structure global time range
For pivotal sync, as far as I can tell, it’s a global time range and then we probabilistically choose it based on exponential curve. This has a bias towards most recent messages.
As far as I can tell the only thing we really need here to enable this is to:
As well as later on:
4) Writing modulo and pivotal heuristics
5) Adding Bloom Filter creation, offer and handling logic
- Additional payload with global time, modulo, offset
Sanity checks and comments welcome.
To allow for more efficient transports, it’s useful to be mindful of the MTU. From my current reading, 1500 Bytes seems like a safe standard. This is 1.5KB, or essentially 1KB with some wrapper on it. Some questions we should answer:
How much should we care about this at this stage? I lack intuition to know how big of a PITA this can be, other than knowing it can lead to huge packet loss for UDP with NAT puncturing.
Is this MTU budget correct? Are there other limits in UDP / smart phone routing / mesh networks etc we should care about?
Are there any aspects of our design where this MTU might be hit? Example are: Big cryptographic handshakes; Header overhead; Excessive wrapping; Sphinx packet format; Bloom Filter size; Message payload.
Is there some general heuristic for budgeting these things? I.e. how big of a payload budget do we have, given that we want to encrypt it, put some header, then routing info, etc.
How much should we care about this at this stage?
Not sure you need to care about MTU at all for a protocol at this layer, I think it makes sense if you are designing one that you know will run directly on UDP (for example a discovery protocol over udp, but it’s unlikely to be the case here, as it will have probably a few layers underneath), and in our specific case will run most likely over tcp (devp2p).
That’s not to say that we shouldn’t keep the payload small and lean, but we might try to keep it under 1.5K, and then is just being padded by the encryption layer and uses tcp as a transport, where mtu is less of an issue.
While this is true for current setup, I think assuming we’ll run on TCP forever is too strong. UDP was specifically chosen in e.g. Dispersy due to NAT traversal, and similar considerations are probably true for Internet less usage and running in the browser. The libp2p folks might have some discussion about this in their forum, but I haven’t looked into it.
No assumption on running on TCP forever was made
my point is that as I understand, this layer will not be directly connected to peers (i.e you won’t have to do any NAT traversal at this layer), and will piggy back on the transport below for these kind of things (which will have to provide a list of peers and a way to communicate with them).
So unless you are planning to have this running directly on top of UDP/TCP, I don’t think we should be taking MTU much into account, although as mentioned, we should keep the payload as small as possible of course, but that goes without saying.
First, started over paper with a more problem-solution oriented and less huge comparison. First section draft done, related works: https://github.com/status-im/bigbrother-specs/commit/219918e0be53d2f035eb579effedfc9c3c21cb34. Tomorrow, continue incorporate existing MVDS etc requirements into problem and solution sections. Aim is to get a solid draft this week (~4-5000 words).
Also looked into Swarm feeds a bunch:
Parallel feed lookups: https://github.com/ethersphere/go-ethereum/pull/1332
What’s the purpose of the adaptive-frequency lookup algorithm FluzCapacitor in Swarm for Feeds?
To find the latest update in a feed, i.e. the latest chunk.
What problem does the adaptive frequency MRU(Feed) in Swarm solve?
Previous implementation required users to agree upon frequency and start time beforehand to publish updates.
What does the adaptive frequency MRU algorithm in Swarm allow users to easily guess?
Where the next update ought to be.
What is an Epoch in Swarm Feeds?
A section of time.
What pieces of data does an epoch consist of in Swarm?
A start time and a level.
What does a level correspond to in Swarm feed epochs?
A duration of time, 2^n.
What is epoch id in Swarm Feeds?
Number corresponding to binary operation of start time and level.
What’s the harvesting algorithm for Swarm Feeds?
Describes how to find latest update of a resource by walking back in time.
How does the harvesting algorithm for Swarm Feeds roughly work?
By dividing the grid of time (start time x duration) into smaller and smaller sections for each lookup step.
For Swarm feeds update, if you have a period covered at level n with some duration (start_time to start_time + n), what is always true for epochs at n-1 levels?
That they are covered by higher levels, each epoch provides ‘shade’ for layers below.
What does the parallel feed lookup function do in Swarm?
Explores keyspace more efficiently by launching queries in parallel.
The parallel feedback lookup algorithm (LongEarth) solved timeout issue, since before each lookup to remote node might wait 100ms, but this could result in timeout, which results in false lookup failures. Using a longer timeout, say 1s, would solve this. But then each lookup might consist of 5 lookups, which would lead to ~5s lookup (and even 20s for first lookup).
What does the parallel feed lookup function (LongEarth) in Swarm basically do?
Binary search, divides epoch grid into lookback area and lookahead area.
Once this is merged upstream: https://github.com/ethersphere/go-ethereum/pull/1332 then false timeouts should be less of an issue for remote node testing.
Louis proposal, some questions: Some thoughts on chats using with shuffling feed and pss locations reply
Want to revisit video Viktor made on Swarm vision, and also (new?) Swarm paper. See if there’s time to expand on Staples PoC a bit.
Draft now up to 4000 words: https://github.com/status-im/bigbrother-specs/blob/master/data_sync/p2p-data-sync-mobile.md
Almost all of system model and enhancements. A bit left on DSP. Next is adding wire protocol and protobuf as well. Also add SSB. And isolate Feeds list and getting historical actual data. Then example clients, desired simulations ~, then some references and have a solid first draft. Is latency/UX a first class design requirement perhaps? Also multidevice sync at some point.
Question on message id compatibility: How is chunk ids in Swarm calculated? How do they differ from our message ids, and can they be consistently mapped? What about IPFS ids? Would be useful if the same piece of content had the same address, even with ~multicodec. If it isn’t possible, how would we do the mapping?