No, they don't. You need to read the article. It says such devices cost $20k.
178 karma · joined December 1, 2017
It's ok that it runs faster, but much better if it's easier, safer, or more painless than the alternatives. The amount of code for a hello-world doesn't seem to indicate so, but maybe it pays off on more complex usecases.
No mention of why
I think it's very valuable to bring people into the topic which is very cool (that's why I added a very long intro to try to provide all the background).
The trickiest part was not the CRDT, but the DAG traversal with multiple workers processing parallel updates on multiple branches and switching CRDT-DAG roots as they finish branches.
I think it is good to explain Merkle-DAG CRDTs (MD-CRDTs) as "merklerized "op-based CRDTs", and I would add that Merkle-Search-Tree CRDTs (MST-CRDTs) are akin to "state-based" CRDTs, to complete the analogy. This helps to bridge traditional and Merkle CRDTs and I would probably introduce it the same way, but it is also not quite right when going into some more depth. I will try to explain why.
In MD-CRDTs we have a growing-DAG that works like a chain of operations that are applied in the order that the DAG is traversed. It looks a lot like an operation log, except it can have multiple branches and, if we follow my paper, operations do not need to have any total order (unlike op-based crdts). We know the latest operation in the DAG (the root node) happened AFTER its children, so there is an embedded notion of order. However, if it has multiple children, we don't know how to order the operations in their respective branches, and we don't need to because they should be commutative etc. For that to work, the paper explains that DAG-nodes embed not operations, but "state deltas". So in reality, MD-CRDTs are delta-based crdts where the merkle-dag structure stores the deltas as they are broadcasted from replicas. It's just that deltas look a lot like operations.
In MST-CRDTs, if my understanding is correct, replicas will be broadcasting the roots of the DAG pointing the full state (similar to state-based CRDTs broadcasting the full state). However, thanks to Merklelization etc., changes to the state only update sections of the full DAG, and diffing, retrieving or broadcasting only the changed parts is super easy and very compact. Since the nodes values will be CRDTs themselves, they can be merged on conflict just fine. In practice, it is sort of also dealing with delta-crdts.
The main thing in both is that reconstructing the full state from deltas is easy and efficient because everything is linked, so you just follow links and drop branches that you already have. Deltas without headaches.
Perhaps another way to conceptually understand both is that in MD-CRDTs, you add DAG-nodes to the top of the DAG as root DAG nodes, leaving the bottom of the DAG untouched. In MST-CRDTs, you add dag nodes to the bottom (the leaves) of the DAG, which cascades into having new root DAG nodes. In both cases you broadcast new root DAG nodes and the rest of people traverse and sync.
Now, what are the practical consequences for implementations:
- The main problem in pure MD-CRDTs (with no caveats) is the unbounded growth (ala blockchain) even when the state becomes smaller. This only matters if you plan to delete or overwrite things from the state. In MST-CRDTs it is "easy" to discard orphaned data. However, one of the main advantages in MD-CRDTs is that "syncing" happens from the last operation/delta. This can be important if you care about having certain notion of order, i.e. that "elements added last" are the first ones to be synced into an empty replica. Another advantage may be to be able to reconstruct multiple views of the same state by re-traversing the DAG, which has "everything".
- MST-CRDTs are very good for database tables, syncing is very efficient, things are compact. I haven't implemented them myself but they seem quite adequate for that use-case. When thinking of downsides, I wonder if they suffer from the cost of re-hashing operations as they grow with a very large number of keys and with heavy usage (larger blocks to hash or more levels to update). One very important advantage of MST-CRDTs is that they are more resilient if a leave-DAG-node is unretrivable. In MD-CRDTs an unretrievable DAG node can break DAG-traversal and with it a large portion of the state while in MST-CRDTs, this will affect only a key or a set of keys related to the missing DAG node.
In the end, for both the devil will be in implementation details: how good is your pubsub code? How good and parallelizable is your update-processing code? How good is your GC process? How good is your blockstore? All those things become performance bottlenecks even when the theoretical properties work perfectly.
Imagine engineers designing a car would have to write about the design rationale of their touch interfaces...
And of course what interfaces are announced is and has been configurable for as long as I remember ("NoAnnounce" setting in the config).
In this case, IPFS breaks the monopoly of trust (only obtaining content from a single source because that source is the reputable source for it). Content addressed data makes the source irrelevant. Many possibilities open from there (i.e. breaking the monopoly of storage).
I have run a public gateway on 2GB of RAM. Later 4GB because it was subject to very heavy abuse, but it was perfectly possible. Perhaps it is a matter of knowing how to configure things and how to not inflict self-pain with wrong settings.
Doing it like that has many advantages, like being able to verify hashes as small blocks are downloaded and not after downloading a huge file. Being able to de-duplicate data, being able to represent files, folders and any type of linked content-addressed data structure.
As long as your content is under 4MiB you can opt out of all this and have a content ID that is exactly the hash of the content.
Thus, this priority represents the current depth (or height) of the DAG at each node. It is sort of a timestamp and you could use a timestamp, or whatever helps you sort. In the case of concurrent writes, the write with highest priority wins. If we have concurrent writes of same priority, then things are sorted by CID.
The idea here is that in general, a node that is lagging behind or not syncing would have a dag with less depth, therefore its writes would have less priority when they conflict with writes from others that have built deeper DAGs. But this is after all an implementation choice, and the fact that a DAG is deeper does not mean that the last write on a key happened "later".
Also, please re-implement it properly!
Nodes could however rely on some form of "consensus" to compact/reset the graph at intervals. But then you have invited a consensus into the party which is the opposite of what CRDTs want to have.
I now had time to read more closely. Thank you for citing us!
In our paper and original approach/algo (iirc), CRDT updates are applied from the bottom of the dag to the heads (older to recent). This is also what you propose although we don't discuss how this helps wrt BFT. I think it is a very good point to highlight that hash-graph based CRDTs (or Merkle-CRDTs as well call them) can provide this property when processed "in order".
The caveat is that, in practice we found this quite impractical: when receiving an update with unknown descendants, you'd have to choose whether to hold on it to apply it at a later point when the missing sub-dag is received (which may never happen), or to drop it and rely on re-transmission at a later point. The first opens the door to abuse by a bad actor because you spend memory holding on to un-applied updates. The latter causes additional work as updates could pile up over an missing one, thus incurring re-transmission costs for the missing and all the later elements.
This also means that peers pubsub systems should probably decide whether to re-broadcast an update based on whether is valid or not per the CRDT operation it contains, which can have bad side-effects: a network missing an update due to a network issue may block the broadcasting of later any later updates even if they are correct, thus worsening the delivery for everyone and forcing the network to issue more re-transmissions.
And as a result, a peer should also decide whether to issue/broadcast updates based on whether the previous update has at least been received by a non Byzantine replica, as otherwise updates built on top will not be accepted by the network until re-transmission. That makes another potential bottleneck.
In our implementation, we found more practical to process updates immediately as they are received, and then process descendants until we reach the "known" part of the DAG. This means every update can be broadcast, gossiped around, and will be potentially applied without doing any waiting for parents, and occasional loss of an update does not block the processing of new updates before re-transmission. If an update has descendants that do not exist then it can be considered a DAG with a different "root" and does not have many consequences in terms of convergence . Note that here we are talking about DAGs with depth of 100k+ items, where sometimes there are 200 heads and processing every update may take a few seconds. We need to avoid blocking a replica as much as possible and get as much work done as possible asap.
I think some CRDTs can get away with this (in our case, CRDT-add-only-sets, using the hashes as IDs) and be byzantine-failure resistant (things would converge). In the paper you mention some examples where CRDT-rules can be abused more easily, so I'm guessing it is more difficult other CRDT types. Ensuring that IDs are unique is one of the main advantages of using hash trees.
In general, I think an attacker can usually find ways to screw up with a non-permissioned CRDT system without breaking convergence (i.e by submitting many valid updates). Your approach makes however a very good point wrt to misbehaving nodes which are not necessarily malicious.
https://arxiv.org/abs/2004.00107 (I'm among the authors)
Unfortunately, the verification that the author proposes (not accepting new updates until the dag below is verified) will need a lot of caveats for real world usage.
Currently we use these CRDTs for a key value database of 40M+ keys in a deployment of ipfs-cluster, which uses https://github.com/ipfs/go-ds-crdt .
> he encouraged Schliemann to pick up where he left off
Yeah, like Schliemann arrived, dismissed Calvert suggestions that it was Troy, and when finally convinced, cheated, stole and took all credit for discoveries from Calvert despite Calvert owning half of the land of the mound and sorting out a ton of practical matters for him (Calvert was consul and well established in the area).
If you happen to visit the area, I would actually recommend to skip it. Go to Assos instead: the citadel, the walls, the theater... all more impressive than Troy. Go the Alexandria Troas and see the baths, the aqueduct, the temple they were digging up a few years ago. Go to see the grandiose Temple of Apollo Smintheum in Gülpinar.
The most impressive thing sadly left in Troy is Schliemann's trench.
https://github.com/hsanjuan/go-dcc
Digitalizing locos with DCC decoder chips is mostly possible and a good exercise.
In any case, IPFS is not a "product", it is a number of protocols and layers sometimes used together and sometimes not (libp2p, ipld, kad-dht, gossipsub, bitswap, graphsync...).
And all of them are in production and sucessfully used, but they also have different levels of maturity and evolve as we have the need and capacity.
The fact that the state is not the final "interplanetary distributed rainbow that replaces the web as we know it" doesn't mean it is completely broken either.
One major hurdle is browsers not being made for p2p. We will need http gateways and other centralized compatibility layers for the time being, which are costly and very prone to abuse. I have hopes in better webrtc support to improve interop with browsers.
Other than that, a DHT at the scales we aim for in terms of indexed content is a problem when 95% of nodes are clients which don't contribute to it. NAT hole punching and supernodes will help.
With IPFS becoming the delivery layer for content stored on Filecoin, and being the standard storage layer for NFTs, there are certainly incentives for the protocols to be used and usage to keep growing heavily.
I understand this complain as it is not obvious why things are like they are, but there are somewhat good reasons!
> I expected to be able to compute a hash and see whether the file is in the IPFS network; then upload it if it not in the network.
There is no upload in IPFS. Either you serve the file from your peer or you don't. It should be irrelevant whether that file was already present in the network or not.
It is however true heavier IPFS usage results in more resources used, or slower experience in general. It is also true that the connection manager could be improved to be more expedient in handling spikes.