Timestamping using a hashed linked list and public known events

Question

Let's say we have a timestamping scheme of the following characteristics,

• The hashes of the documents we are trying to timestamp are XOR'ed with "events" whose time of occurrence are very publicly known (i.e. the hash of the latest block on the blockchain),

$$M_{i}=(H_{D_{i}} \oplus B_{t_{i}})$$

Where,

$M_{i} =$ the hash of the document "mixed" with a known public event,

$H_{D_{i}} =$ hash of document to timestamp,

$B_{t_{i}} =$ hash of the latest block on the blockchain (a very known public event) at the time of timestamping ,

• The concatenation of $M_{i}$ and the previous timestamp gets hashed together forming a new node on a hashed linked list,

$$H_{i} = Hash(M_{i} ||H_{i-1})$$

Where,

$H_{i} =$ the timestamp of the document.

• Each $H_{i}$ is then published in "real time" into an independent (no relation to the timestamper) public third party platform so that anybody can potentially monitor any modification to the list. An example of this type of platform could be Twitter where each tweet is the concatenation of the current and previous timestamp,

$$T_{i} = H_{i} || H_{i-1}$$

Where,

$T_{i} =$ Public reference of the timestamping (i.e. a tweet).

That being said,

1. What are your thoughts of the following assertions?

   • Future-dating a document (even in collusion with the timestamping service) would be not feasibly because of the unpredictable nature of the public event (i.e. it is not feasibly to know what the hash of the next block in the blockchain is going to be unless someone mines it).

   • Backdating a document, even in collusion with the timestamping service, would not be feasibly because of the nature of the hashed linked list.

2. Does anybody know if a scheme like this is already described and/or implemented somewhere?
3. What are your thoughts about the weaknesses of a scheme like this?

Answer 1

Your diagram is not very clear, but XOR is not a good combiner function to use for timestamping, as it may allow backdating in some circumstances. For instance, see the "time travel" attacks in Section 3.3 of the following paper (e.g., pp.179-180): Cryptanalytic Attacks on Pseudorandom Number Generators. Depending upon how many inputs you have to the XOR function and the specific details of your scheme (which are not sufficiently clear from your question), generalized birthday attacks may also be possible and might allow backdating.

Instead, you should use hashing. There are standard constructions for hash-chaining: I suggest you use them. In particular, if the sequence of documents/data to be hashed is $D_1,D_2,D_3,\dots$, we form a hash chain by the formula

$$H_i = \text{Hash}(H_{i-1} \,||\, \text{Hash}(D_i)).$$

Then we can publish the $H_i$'s as well as each $\text{Hash}(D_i)$. See a standard reference on hash chaining and timestamping for more details.

---

Update (after the question was edited):

No, this is definitely not a good idea, because $x \oplus y$ does not uniquely determine $x$ and $y$.

For instance, someone could register $H_{D_i}$ (which gets mixed with $B_{t_i}$), then later claim that they actually registered $H'_{D_i}$ (and it was mixed with $B'_{t_i}$), as long as $H_{D_i} \oplus B_{t_i} = H'_{D_i} \oplus B'_{t_i}$. How would you detect it? There's not a fantastic way to do it.

It would be much better to compute $M_i$ as

$$M_i = \text{Hash}(\text{Hash}(D_i), t_i, B_{t_i}).$$

Now $D_i$ and $B_{t_i}$ are uniquely determined, given $M_i$; the collision-resistance of the hash function prevents backdating or lying about how $M_i$ was formed. This is such a simple fix, and it is so obviously better, that there's not much point analyzing in great detail the exact degree of vulnerability of xor; it's clear that using a hash is better than using a xor, so there's absolutely no reason to use a xor in this context.

So, bottom line: use a hash function, not xor.