Skip to main content
added 886 characters in body
Source Link
sshine
  • 272
  • 6
  • 12

Assuming your stream of hash digests are appended toEdit: Clarifying answer by using a Merkle tree as example.

For a list of values Merkle Mountain Range$x_1,\ldots,x_n$, you only needcan compute a Merkle tree with the root peaks$h_n$. For a given $h_n'$ claimed to computebe $h_n$, and you needcan shorten the verification by revealing the authentication path of length $log_2(n)-1$ calls to your hash function, since after appending a newbetween any known leaf hash digest$f(x_i)$ and the claimed $h_n'$.

By defining the wormhole $w_{i,n}$ as a leaf node in a mountain rangethe authentication path between $f(x_i)$ and $h_n$, you need to recompute the new peakcan verify that encompasses the leaf$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 

In your wormhole metaphorYou can then call verify(f(x_i), w_i_n, h_n'). Specifically, to verify $w_n$ would be$h_n'$ does not require all previous hashing, only a listsubset of peak hash digestslogarithmic size called the authentication path.


The drawback of length at mostusing a Merkle tree here is that we have to assume that it's perfectly balanced, i.e. that $log_2(n)$$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.

Assuming your stream of hash digests are appended to a Merkle Mountain Range, you only need the peaks to compute $h_n$, and you need $log_2(n)-1$ calls to your hash function, since after appending a new hash digest as a leaf node in a mountain range, you need to recompute the new peak that encompasses the leaf.

In your wormhole metaphor, $w_n$ would be a list of peak hash digests of length at most $log_2(n)$.

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.

Source Link
sshine
  • 272
  • 6
  • 12

Assuming your stream of hash digests are appended to a Merkle Mountain Range, you only need the peaks to compute $h_n$, and you need $log_2(n)-1$ calls to your hash function, since after appending a new hash digest as a leaf node in a mountain range, you need to recompute the new peak that encompasses the leaf.

In your wormhole metaphor, $w_n$ would be a list of peak hash digests of length at most $log_2(n)$.