I am thinking of a particular datastructure, but don't know the name of it.

A sequence of elements may be modeled by a collection of some X, where each X consists of:

  1. The element, serialized as a bunch of bytes.
  2. [a] The hash of the previous X in the sequence, based on the bytes of both parts of that X in a predictable way or [b] some mechanism to denote no such X exists, i.e. that this is the first element.

Given a database that contains (at least) all relevant Xs, and a lookup mechanism by hash, we can take a single X and reconstruct the sequence of elements from it.

What is the general name (if it exists) of this datastructure in the literature? I.e.

  • What is the general name of X?
  • What is the general name of a sequence of Xs.

Note that although this looks like (and is inspired by) a blockchain or git commit object, it is more general: any list sequence could be so rewritten.

In comparison with the blockchain / git, the above does not make any statement about distributed databases, timestamps or contents of each element. It also notably differs from git at least in the sense that it is single-parent.

  • 1
    $\begingroup$ I don't know the answer to your question, but is the name really relevant? I mean, it just looks like a mere linked list where you recode the way memory & pointers works. I don't think there is specific literature on this. $\endgroup$
    – md5
    Jul 3 '17 at 14:57
  • $\begingroup$ @md5 as Abelson says: "It's important, by the way, to get names for, to get names for, the parts of things, or the parts of expressions. One of the things that every sorcerer will tell you is if you have the name of a spirit, you have power over it. So you have to learn these names so that we can discuss these things." - youtube.com/… $\endgroup$ Jul 3 '17 at 15:26
  • $\begingroup$ Related: en.m.wikipedia.org/wiki/Hash_consing $\endgroup$
    – rici
    Jul 3 '17 at 15:51
  • $\begingroup$ @rici — thanks for the link to Hash Consing. It indeed seems to be close to what I'm talking about, though perhaps even a bit more general/fundamental than the solution above. In the example above a distinction is made between "elements" and the list; as far as I understand HCONS would not make a distinction in the treatment of the 2 operants (car & cdr). $\endgroup$ Jul 3 '17 at 20:00
  • $\begingroup$ @klaas: that is correct. It is often used for trees (even turning them into acyclic graphs by structure-sharing equivalent subtrees). $\endgroup$
    – rici
    Jul 3 '17 at 20:38

This is known as hash chaining. The blockchain uses this technique, as do some kinds of timestamping schemes (see, e.g., Haber & Stornetta) and in some cryptographic schemes for append-only audit logs.

  • $\begingroup$ The Wikipedia article for Hash Chain that you linked, as well as Lamport's article linked therein ("Password Authentication with Insecure Communication") and the link to S/KEY talk only about repeated application of a hash function to a single input, i.e. h(h(h(h(x)))). I'm asking about h(e3|h(e2|h(e1|h(e0|nil)))) ... (where h stands for the hash function, e0 .. e3 for elements and | stands for concatenation) $\endgroup$ Jul 3 '17 at 18:53
  • $\begingroup$ @KlaasvanSchelven, h(e3|h(e2|h(e1|h(e0|nil)))) is called hash chaining, too. Ignore the Lamport and S/Key stuff; that's sometimes also called hash chaining, but as you point out it is different. (Hash chaining as a term covers both kinds of usages.) If you want something more specific, look at Haber & Stornetta. $\endgroup$
    – D.W.
    Jul 4 '17 at 0:18
  • $\begingroup$ Ah, I see — Haber & Stornetta indeed describe a similar scheme; although I cannot find the usage of the term "Hash Chaining" in their 1991 article. $\endgroup$ Jul 4 '17 at 8:28
  • $\begingroup$ @KlaasvanSchelven IIRC Ralph Merkle called it a hash list (with chained list structure, the way you want it, as opposed to what the Wikipedia article describes which is more of a hash array), and soon after generalized it to a hash tree, but I can't find the paper I was thinking of so I may be misremembering. $\endgroup$ Aug 2 '17 at 19:36

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.