Are such verification wormholes known, or even possible?

Question

1. Scenario

Suppose that we have a source that is generating one random value per, say, minute. So we have random value $x_1$ in $1$st minute, $x_2$ in $2$nd minute, $\ldots$, $x_n$ in the $n$th minute, and so forth.

The distribution of values $x_1, x_2, \ldots$ is not entirely uniform random, but follows the following rule: for any $i \ge 1$, $x_i = (y_i, y_{i+1})$, where, $y_i$ is the unique identifier of $x_i$, and $y_{i+1}$ is the unique identifier of upcoming $x_{i+1}$ that going to arrive at the next minute.

In other words, at any given $i$th minute, the current $x_i$, and the next $x_{i+}$ are known, but the one after $x_{i+2}$ is absolutely unknown, or random. Below is an example:

Minute 1:  x_1 = (334234   , 234829129   )
Minute 2:  x_2 = (234829129, 983220      )
Minute 3:  x_3 = (983220   , 831231236347)
...
Minute n:  x_n = (643532754, 3534611     )

One way to hash those $n$ values, in order, is to hash each value as it arrives, e.g. $h_1 = f(x_1)$, then chain it with the next newly arriving one, e.g. $h_2 = f(x_2 \parallel h_1)$.

In other words, the hash of the ordered list of input, in the $n$th minute is defined recursively as $h_n = f(x_n \parallel h_{n-1})$, with the base case being $h_1 = f(x_1)$.

The advantage of this approach is that, for somehow who is running this process from the beginning, at every minute, both the run-time and space-time are in $O(1)$, as he can cache the hash from the previous minute.

The disadvantage of this approach is that, for someone that was not following the process, and wishes to verify if $h_n$ is indeed the hash of the entire sequence, he will have to start over from the beginning with $h_1$, and repeat the entire chain all the way until $h_n$. Effectively, this verification process will take $O(n)$ space and $O(n)$ time.

2. Wormhole

It would be nice if it is possible that, at every $n$ many hashed chains, we can discover a wormhole $w_n$ that has the following properties:

• Once the $n$th hash, $h_n$, is legitimately calculated off $h_1$ by following the full recursion earlier, only then the wormhole $w_n$ becomes discovered. Otherwise, finding $w_n$ is practically impossible.
• For a given $h'_n$ hash that is claimed to be $h_n$, the wormhole can shortcut the verification as follows:

$$ w_n(h_1, h'_n) = \begin{cases} 1 & \text{if $h'_n = h_n$}\\ 0 & \text{else}\\ \end{cases} $$

• The asymptotic worst run-time as well as the asymptotic worst space for computing $w_n(h_1, h'_n)$ is not worse than $O(\log n)$. If it's possible to make it in $O(1)$, that's be even better of course.

Note. This is different than the pre-image attack of hashing functions. The difference being as follows:

• Pre-image attacks allow the attacker to forge an arbitrary input that gives some desired target hash.

• This wormhole $w_n$ does not allow forging any arbitrary input, but rather reveals a hidden shortcut path that works only for linking a specific input that allows to link $h_n$ back to $h_1$, and that the only way to discover such wormhole is by legitimately calculating $h_n$ first.

• Maybe we can call such a wormhole to be a conditional pre-image attack that does not benefit the adversary.

3. Question

Are such verification wormholes known, or even possible?

Answer 1

Edit: Clarifying answer by using a Merkle tree as example.

For a list of values $x_1,\ldots,x_n$, you can compute a Merkle tree with the root $h_n$. For a given $h_n'$ claimed to be $h_n$, you can shorten the verification by revealing the authentication path of length $log_2(n)-1$ between any known leaf hash $f(x_i)$ and the claimed $h_n'$.

By defining the wormhole $w_{i,n}$ as the authentication path between $f(x_i)$ and $h_n$, you can verify that $h_n' = h_n$ in $log_2(n)$ calls to $f$. As pseudo-code:

def verify(f_x_i, w, h_n):
    h_i = f_x_i
    for h_j in w:
        h_i = f(h_i + h_j)
    return h_i == h_n

You can then call verify(f(x_i), w_i_n, h_n'). Specifically, to verify $h_n'$ does not require all previous hashing, only a subset of logarithmic size called the authentication path.

---

The drawback of using a Merkle tree here is that we have to assume that it's perfectly balanced, i.e. that $n = 2^k$ for some $k$, and appending requires rebuilding the tree, so no gain. Appending your $h_i$ to a Merkle Mountain Range instead, there is something similar to an authentication path to show that it lives under a set of peaks rather than under one root.