Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

11
  • 1
    $\begingroup$ I think there must be an extra input beside $n$, $h_1$ and $h'_n$ to the algorithm computing $w_n(h_1, h'_n)$. In particular, what it does should depend on $x_1$ to $x_n$, right? Therefore, why single out $h_1$, and what in the problem statement prevents from making $h_n$ that extra input, which allows a trivial implementation of $w_n(h_1, h'_n)$? Is it assumed $x_1$ to $x_n$ are implicit inputs to said algorithm? $\endgroup$ Commented Feb 14, 2022 at 16:57
  • $\begingroup$ Do the random values have to be genuinely random and outside of the control of the source, or do the values only need to be indistinguishable from random to an observer? $\endgroup$ Commented Feb 15, 2022 at 2:36
  • $\begingroup$ @fgrieu - Right, it depends on $x_1, x_2, \ldots$. However, I wonder, can we pass information about such dependence in the output hashes $h_1, h_2, \ldots$? In other words, can it be that $h_2 = f(x_2, h_1)$ is effectively passing related information in $x_1$ into $h_2$? Subsequently, as the chain goes on, can $h_n$ effectively have related information from $x_n, x_{n-1}, \ldots, x_1$, that's sufficient to create a verification wormhole $w_n(h_1, h'_n)$? $\endgroup$ Commented Feb 15, 2022 at 11:38
  • $\begingroup$ @fgrieu - As for your question about the problem statement preventing trivial solutions, if I understand you correctly, it's the requirement that the space complexity for the "wormhole user" must be constrained in $O(\log n)$. But, the "wormhole discoverer" must do the $O(n)$ process. $\endgroup$ Commented Feb 15, 2022 at 11:44
  • 1
    $\begingroup$ I assume the source can't be trusted to assert anything about the values? Because if the source is trusted, the source can just release a "checkpoint" every $n$th time, where a signed message containing the latest hash is announced. If the source can't be trusted to assert anything, how can the source be trusted to introduce a wormhole that attests to the correct value of the hash? $\endgroup$ Commented Feb 15, 2022 at 12:02