Haven't heard of Drogulus before, sounds interesting.
Anything that implements a Kademlia-like decentralized key-value datastore (basically, a DHT) gets my curiosity. Kademlia is a system/protocol how to implement a DHT and how to perform searches on it. The idea is that all network nodes are identified by a (traditionally, 160bit I think) hash. If you want to implement a P2P filesharing network based on Kademlia (like Gnutella), you hash each file to a bitstring of the same hash length.
Now, when you want to reach a particular node (and you have its hash but not its IP), you can do an efficient search by traversing the nodes in the direction of the target nodes. For direction, a distance metric is needed in this case. The distance between two given hashes is simply the result of [hash1] xor [hash2]. This is rather simple and ingenious: you get a value representing the amount of bits by which the two hashes differ. Hence you have a way to measure distances in the hashspace.
Therefore, when trying to locate a node, you don't need to do an exhaustive exponential "ping all my neighbours and get all their neighbours" search; one could say that you are able to follow a vector in the hashspace. edit: by which I simply mean, the most simplistic way to achieve this would be - pick a node from pool/neighbourhood with id/hash closest to target; get id/hash from its pool closest to target; continue until reaching a critical distance within which nodes will be responsible for holding the desired key->value pair. (I'm sure the actual algo will need to be somewhat more complex, as it's very easy to run into dead-ends this way, and so on.)
When there are files involved, nodes whose hashes are close enough to a given key (which is a hash of a file, more or less) are responsible for storing those key->value pairs ('value' differs on implementation, but basically it's another hash pointing to the node which actually has the file in question, if I'm not mixing things up; the whole thing is more complex, with a way to search using (hashed) keywords, etc.) Hence one can implement an efficient distributed search algorithm, where you focus on the hash-neighbourhood of a particular file hash, and get key->value responses from the nodes responsible.
This kind of a system has its disadvantages and possible points of attack. See the wiki article on Kademlia. [1] Probably the most well known type of attack is Sybil attack: [2]
In a Sybil attack the attacker subverts the reputation system of a peer-to-peer network by creating a large number of pseudonymous identities, using them to gain a disproportionately large influence. A reputation system's vulnerability to a Sybil attack depends on how cheaply identities can be generated, the degree to which the reputation system accepts inputs from entities that do not have a chain of trust linking them to a trusted entity, and whether the reputation system treats all entities identically.
Now, Drogulus seems to propose at least a partial way around this, though I suppose it'd still be possible to actually flood/populate the hashspace with garbage(?): [3]
The drogulus has three core components:
* A distributed hash table (DHT) that provides the data store and replaces DNS.
* Trust and identity enforced via cryptographic signing of digital assets.
* Logos [...] (say "log-oss"), a simple implementation of a Lisp like programming language for asynchronously working with data stored in the DHT.
The drogulus implements a version of the Kademlia distributed hash table. The innovation the drogulus brings is that keys and values (items) are signed in such a way that their provenance can be proven and content shown to be intact. Furthermore, users cannot interfere with each other's items stored within the distributed hash table unless they have access to the same private key. Items are self contained and any that do not pass the cryptographic checks are ignored and nodes on the network that attempt to propagate such values are punished by being blocked by their peers.
I don't have time to actually delve into this now, but the next paragraph piqued my curiosity even more - if anyone is into this, would be interesting to hear some comment :)
Logos programs are themselves values stored within the DHT, run in asynchronous "ensembles" that arrive at a consensus and process other items of data stored within the DHT. They are sandboxed and intentionally limited in terms of time (how long a computation may last) and space (how much memory may be used). Since Logos programs are also data there is a mind-bending side effect that Logos programs can rewrite other Logos programs in order to extend the Logos programming language itself. This is an important property: users have the autonomy to grow the Logos programming language to suite their own needs.
First things first: it's an unfinished work in progress and an experiment on which I've been hacking during my 40 minute train journey in to work. So, yes, "something something - Kademlia-like crypto-signed homoiconic datastore - something" just about sums it up.
I can't spend a lot of time answering right now, but I gave a short presentation about the drogulus at this year's Opentech in London which resulted in the following blog post (giving a high-level overview of my motivations and intentions): http://ntoll.org/article/ppdd I followed up with some clarifications in this post: http://ntoll.org/article/drogulus-questions-and-clarificatio...
I have several more blog posts in draft form about other aspects of the system.
It's very early days and I'm pretty sure there are lots of problems with what I'm doing. But, as I mentioned in the first post referenced above, I'm having too much fun to stop. ;-)
Happy to answer questions and constructive feedback, comment and critique is most welcome.
I've been working on a similar project for about a year now. Interested in exchanging notes? We are basing ours on a Chord DHT for better robustness.
benshoof@cs.gsu.edu
And that is my fault. I left out a letter. Now that you have displayed interest and I feel less awkward about directly approaching you I just went ahead and emailed you.
Instead of designing your own language Logos, have you considered using Clojure, which is also homoiconic, is a modern variant of lisp, and was/is designed by programmers who have industry experience, so it's not an academic experiment?
I did seriously look at Clojure but it doesn't quite fit my requirements. Also, I didn't say the drogulus was an academic experiment... that makes it sound far too impressive. ;-)
Could you please go into more detail on what were your requirements that Clojure did not fit?
What you have so far IS an impressive, audacious, idea. You can probably tell by the amount of attention you have gotten for it already. False humility is a kind of arrogance too, you know. Honest humility takes more work. Any time anyone starts talking about writing a new language, either they have not thought through all the challenges that would have to be met, like a boy trying to build a rocket to the moon using fireworks, or they are trying to do something impressive. Which are you?
Regarding Clojure: If the drogulus comes to anything then I'm building a working reference specification. I chose to write it in Python and comment ubiquitously to make sure the code is easy to re-implement in other languages or on other platforms. Adding a dependency on Clojure would make this less likely to happen; the drogulus would instantly be linked to the JVM (and other platforms upon which Clojure runs).
I've used Clojure before "for fun" and I like it - it's not a problem with the language per-se. Rather it's more a case of wanting Logos to be small, simple and "fit" the drogulus. Does this make sense?
I agree with you about developing new languages. That's why I chose to re-implement a Lisp: I don't want to invent a new language. However, I do want a language that meets my need for "fit", simplicity, portability and compactness (I'd like my kids to be able to understand and program in Logos). To use a musical analogy, Logos is a re-arrangement an old classic (Lisp) for different ensembles. ;-)
This is a work in progress and I need to push ideas in to code and get feedback as soon as possible. Only then will you be able to tell if I'm playing with fireworks or doing something impressive. Furthermore, while I have a very clear idea of what needs doing, I don't think this is a one-person job. That's why the biggest challenge for me right now is to transition the drogulus from a one person playtime project hacked together during a daily 40 minute commute in to London in to a functioning multi-person project with an active community of users.
Now, that would be impressive!
As always, I'm happy to answer questions and welcome constructive comment, critique and feedback.
Perhaps "Learning how to write a lisp-like language" is a requirement? Or perhaps it's low memory usage and fast start-up time for short-running tasks. Does it matter what he chooses for his own project?
I kinda like Clojure, but I don't think it would occur to me to default to it every time someone mentions the word 'lisp'. Not because it's not an adequate language, but there are downsides to using it for some jobs.
Oh wonderful, thanks for the reply! And thanks for the links (the "Politics, Programming, Data and the Drogulus" post had already been placed in my when-have-time-random-reading-list, cool.) I'll be sure to follow up with comments if I have any later on.
I assume that the crypto identity part of the system is indeed motivated by Sybil-like attack vector towards similar P2P systems, or something of the sorts.
(Warning: convoluted phrasing follows --) Logos programs and anonymity: I assume your system is not primarily designed to provide some level of anonymity (in the sense of message-originator decoupling). Some P2P systems try and implement a characteristic by which it is impossible to say whether a particular message seen in the network is originating from node X, or was simply broadcast by some node(s), one of which is X. Of course, if we have node identities and message signing, this is obvious, but - the idea could be to decouple actual pub-private-key identities from the nodes themselves (or perhaps implement an 'anonymous messaging' identity system atop the other, so there'd be identities for nodes, and for persons/people/virtual-identities, the two sets obviously overlapping but not homomorphic to each other (a node could broadcast/introduce a myriad of secondary identities, etc.)
Thing is, if Logos could be used to organically extend the system to implement such functionality, it would be rather impressive indeed. (By 'could' I do not suggest anyone doing it, merely observing my thought that the very possibility would be a curious fact about drogulus.)
/end of coffee-related rant, gtg, thanks for the reply again!
Yes, the crypto identity aspect goes some way to address Sybil like problems.
Regarding anonymity: you're only as anonymous as your association with your public key[s]. Given that items (k/v pairs) stored in the DHT are self-contained in terms of proving provenance it doesn't matter from what node they originate. Put plainly, there is no need for a node id (a SHA512) to be linked to a specific user (identified by their public key). I explain how signing items works here: http://ntoll.org/article/drogulus-questions-and-clarificatio...
For me, the most curious fact about the drogulus is that it is a ubiquitous ecosystem for asynchronously processing Logos code and data. If you see the implication of this then you'll get where I'm trying to go with the drogulus.
This really is a great project. Thanks for providing the links. It looks like you're thinking about the right things in building something like this. I'm excited to look at the code!
> The distance between two given hashes is simply the result of [hash1] xor [hash2].
This is the main innovation of Kademlia compared to other DHTs like Chord which uses a simple difference-modulo-N distance metric. Kademlia was the first DHT with a symmetric distance metric, which has the advantage that peer-to-peer connections can actually be used bidirectionally. That means that Kademlia networks need only half of the active connections to reach the same level of connectivity compared to earlier DHTs.
As far as I know, this is pretty much the only advantage Kademlia has over other DHTs, but of course it is quite a significant difference in practice.
Ah, you are quite right, I should have emphasized that point! (I guess I simply wanted to get to the drogulus part, but ended up expanding a bit.)
Indeed, the main paper introducing Kademlia is basically called, "P2P network based on the XOR metric." That is its distinguishing feature, but it is indeed enough to make all the difference.
Kademlia is also quite fun to implement! It's a great example of a distributed system, and me and a couple of friends actually made our own in golang (https://github.com/maxsnew/kademlia-go). We also decided to build a fault-tolerant, secure file store on top of it (https://github.com/jontonsoup/tin-foil-hat), as an educational experience.
> Therefore, when trying to locate a node, you don't need to do an exhaustive exponential "ping all my neighbours and get all their neighbours" search; one could say that you are able to follow a vector in the hashspace.
How are you able to do this without pinging all neighbors? How do you know you've found the node with closest distance? Or is there a defined XOR result for closest distance and you can stop searching once you've found it?
You keep track of a few folks at different distances from yourself, and route packets to the folks one knows which are closest to the ultimate destination (or ask them whom they know closest to that destination).
So rather than asking everyone you know, who ask everyone they know, who ask everyone they know, you're asking a subset, who ask a subset, who ask a subset.
The latter, as far as I take it. That is, each given Kademlia-based system defines a 'close-enough' / neighbourhood constant. If a given result from xor is <= that constant, you have reached your destination. Because obviously, you won't have node IDs actually matching your target (e.g. file) hash (assuming no hash collisions.) So you need a 'proximity' value.
Granted, the whole picture is more complex, and my knowledge is very limited. A node that wants to search for something sends its search query to the neighbour closest to target, which then, as I understand, propagates / rebroadcasts that query to its neighbour which itself is closest to destination. There seems to be some redundancy involved / multiple paths taken, perhaps to ensure that all nodes within that proximity distance are found. (So for example there could be multiple nodes storing the same key (say, file hash), but with different values (different node IDs (for nodes that actually have the file in question.))) I'm being vague though, that's very true..
But as I understand it, as long as the whole graph of nodes is connected, with no orphan sub-graphs forming / detaching (something which may not be trivial to accomplish/ensure), you should be able to get all relevant key->value pairs / reach all relevant nodes in your search. The way the search is concluded in Gnutella (I think) is that each target node responds by connecting to the source/query-issuing node directly (every query carries with it source UDP IP:port (I think)).
edit / P.S.: also, it may be that a given node stores node IDs in its proximity range (the 'close enough' value), but I'm not sure of this; I'm adding this because it may actually help ensure that all nodes / key->value pairs of interest are accounted for, i.e. it's a worthwhile idea anyway.
Tonika looks really interesting and relevant to multiple interests of mine - it may be something I'd been looking for some time, actually. Will read up on it (I've seen the particular arXiv paper Tonika design rests on before, but didn't look into it; hmhm.) Thanks for the link!
edit interests / interesting features = message passing, privacy, deniability, etc. Good stuff.
Interesting indeed. I came to the same conclusion for my pet project (as of yet unpublished), a distributed content addressable data store is only useful if there are attack resistant trust metrics included.
Anything that implements a Kademlia-like decentralized key-value datastore (basically, a DHT) gets my curiosity. Kademlia is a system/protocol how to implement a DHT and how to perform searches on it. The idea is that all network nodes are identified by a (traditionally, 160bit I think) hash. If you want to implement a P2P filesharing network based on Kademlia (like Gnutella), you hash each file to a bitstring of the same hash length.
Now, when you want to reach a particular node (and you have its hash but not its IP), you can do an efficient search by traversing the nodes in the direction of the target nodes. For direction, a distance metric is needed in this case. The distance between two given hashes is simply the result of [hash1] xor [hash2]. This is rather simple and ingenious: you get a value representing the amount of bits by which the two hashes differ. Hence you have a way to measure distances in the hashspace.
Therefore, when trying to locate a node, you don't need to do an exhaustive exponential "ping all my neighbours and get all their neighbours" search; one could say that you are able to follow a vector in the hashspace. edit: by which I simply mean, the most simplistic way to achieve this would be - pick a node from pool/neighbourhood with id/hash closest to target; get id/hash from its pool closest to target; continue until reaching a critical distance within which nodes will be responsible for holding the desired key->value pair. (I'm sure the actual algo will need to be somewhat more complex, as it's very easy to run into dead-ends this way, and so on.)
When there are files involved, nodes whose hashes are close enough to a given key (which is a hash of a file, more or less) are responsible for storing those key->value pairs ('value' differs on implementation, but basically it's another hash pointing to the node which actually has the file in question, if I'm not mixing things up; the whole thing is more complex, with a way to search using (hashed) keywords, etc.) Hence one can implement an efficient distributed search algorithm, where you focus on the hash-neighbourhood of a particular file hash, and get key->value responses from the nodes responsible.
This kind of a system has its disadvantages and possible points of attack. See the wiki article on Kademlia. [1] Probably the most well known type of attack is Sybil attack: [2]
Now, Drogulus seems to propose at least a partial way around this, though I suppose it'd still be possible to actually flood/populate the hashspace with garbage(?): [3] I don't have time to actually delve into this now, but the next paragraph piqued my curiosity even more - if anyone is into this, would be interesting to hear some comment :)Logos programs are themselves values stored within the DHT, run in asynchronous "ensembles" that arrive at a consensus and process other items of data stored within the DHT. They are sandboxed and intentionally limited in terms of time (how long a computation may last) and space (how much memory may be used). Since Logos programs are also data there is a mind-bending side effect that Logos programs can rewrite other Logos programs in order to extend the Logos programming language itself. This is an important property: users have the autonomy to grow the Logos programming language to suite their own needs.
So, something something - Kademlia-like crypto-signed homoiconic datastore - something. Hmm.
[1]: http://en.wikipedia.org/wiki/Kademlia
[2]: http://en.wikipedia.org/wiki/Sybil_attack
[3]: http://drogul.us/how.html