4

Distributed Hash Tables are a great way to store immutable data in a resilient way.

However, I am wondering about how it would be possible to store new versions of old data in this system.

Because it is impossible in a distributed network to unconditionally trust the other party, a way is needed to ensure that another party does not manipulate stored data. The easiest way to do this is to store data values under keys that are generated from these values using a one-way hash function. This means that when someone wants to change data, they invalidate the key->value relation of that data, which is easy to check against.

Say, someone stores a document in the DHT, but later made some changes and wants to store that new version. How can other people connected to the DHT find out that there is a new version of this document? The only information that I found about this said that an idea would be to store versioned data like this:

v1: hash(random_number) -> document1
v2: hash(key(v1)) -> document2
v3: hash(key(v2)) -> document3
...etc.

Then, to check if there is a new version, all a client would need to do is to apply the hashing algorithm one more time to the hash of the current value.

Drawback: This approach does not have the relation between key and value, meaning that a value might be changed (by a malicious server or a man-in-the-middle) without invalidating the key.

How can these two approaches be combined? Or is there a different, better way to manage this?

  • You might be interested in Ethereum. – User Oct 7 '15 at 10:48
6
+50

Once you decide that clients cannot be trusted, then it is a given fact that each value is immutable, and each key is immutable. And immutability is forever.

This in turn means that this is not a problem of storing and finding values, it is a problem of identifying the key of the most updated version of a value, so it is a versioning problem.

When trying to solve the versioning problem, you first of all have to ask again if you can trust your sources.

  • If you can trust your sources, then all you need is a straightforward, almost trivial solution. This could involve:

    • Mapping keys to pairs of actual keys and version numbers, so that you can list them all to find the one with the highest version number.

    • Mapping keys to successor keys so that given a "current" key you can traverse the chain and find the key which corresponds to the latest version.

  • If you cannot trust your sources, then you have to employ some voting mechanism. This is a subject which has received plenty of research, under the broad title of "Consensus". So, a good place to start would be the relevant wikipedia article: Wikipedia: Consensus (Computer science)

  • 1
    Consensus is an interesting concept and one that is employed by Bitcoin with the validation of transactions on a block chain. Anybody could try to forge a payment but if the consensus of nearly all clients is that this payment is bogus then it is rejected. – maple_shaft Oct 7 '15 at 1:15
  • @maple_shaft Are you sure that a consensus of nearly all clients is required? I thought a simple majority suffices. Because I have heard it being said that if you can control half the nodes you can own bitcoin. – Mike Nakis Oct 7 '15 at 1:27
  • 1
    @MikeNakis Thank you for this answer. You receive the Bounty because you really have changed my way of thinking about this problem! – Qqwy Oct 12 '15 at 16:47
  • Glad to be of help! – Mike Nakis Oct 12 '15 at 17:20
2

There are ways in which this can be solved, and you can make this as complex as you like. The simplest way is to authenticate the other servers, and allow the servers to trust each other if they are authenticated. Client and Server authenticated SSL for the network connection would achieve this.

You could also do a federated authentication system, where you are asking trusted third parties to vouch for other servers. This can also be achieved using SSL certificates on both the client and server, and authenticated that the certificates are signed by a trusted certificate.

If you are truly after an internet scale cache, the final option is to have the cache vote, based on the majority answer, and trust that there are more honest servers than there are dishonest servers in the network. However, when you have a situation where you don't trust the servers, you still need to solve the problem from the client's perspective... how does the client trust the servers to send their data? How does the client know that their data is distributed to enough trusted servers that their data is accepted. Now having read all this, have a read up on the CAP hypothesis and realise that if you go down this route, you must have partition tolerance as you don't know the servers who are part of the system. You Must have Availability, which means the thing you must sacrifice is consistency.

2

You want

  1. A client connected to any number of (malicious) servers.
  2. An authorized person to create new values, connected to (malicious) servers.

Your assumptions are (correct me if I a wrong):

  1. The values are so big that they need identifiers (hashes).
  2. The client and the person can not communicate directly.

Without any further assumptions the client can not be sure of any value of the person. Possible new assumptions are:

  1. The person signs the values
  2. New values can be created by anyone
  3. The person is not malicious
  4. The person can reach the client
  5. The person and the client have synchronous clocks
  6. The client can identify the person's messages
  7. A message from the person to the client can reach the client within some known time
  8. The client does not need to reach the person
  9. The client can not reach the person
  10. Values have relation to the time of the client
  11. A new value makes previous values invalid
  12. A client must know all values of a person
  13. The client can know that a value is invalid without having a new value
  14. Values are only valid over a time span

Please tell me which assumptions you exclude. Please tell me which assumptions you make. Please tell me which assumptions you do not care about. There might be even more.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.