3
$\begingroup$

I need to verify partial downloads (retrieved sequentially), given a (preferably short) hash of the complete download.

Given a message $m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots$, hash function $H$, and hash value $h = H(m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots)$, I want to have a verifier function $f$ that can work on partial messages $f(h, m_0) = \mathit{valid}$, $f(h, m_0 \mathbin\| m_1) = \mathit{valid}$, $f(h, m_0 \mathbin\| \mathit{random} \mathbin\| m_1) = \mathit{invalid}$.

Message order is known in advance, retrieved in order. $h$ is preferably short. It's okay to spend more time (CPU) or space (memory) during verification. High collision probability is okay. I just need to say $f(h, m_0 \mathbin\| m_1)$ = so far so good, you can continue the download.

Is there a construct that can do that, even a probabilistic one?

EDIT: clarify the bits about 'preferably short'. Hash tree adds space burden to transmit O(2*n) hashes. Hash list is O(n). I'm looking for O(1) space requirement.

$\endgroup$
  • $\begingroup$ Have you looked at Merkle Trees? $\endgroup$ – bmm6o Jun 14 at 15:19
  • $\begingroup$ I've considered chunking (splitting into smaller blocks and calculate all hashes, merkle tree). For our discussion, let's just say these aren't possible due to application constraints (mutable blocks, complexity of transmitting/tracking changed hashes on every small changes). Anyway all chunking is just replacing the definition of partial message becomes total message, and then do smart stuff outside the hash function (tree, etc). I'm looking for hash that has those characteristic: verifying partial message. $\endgroup$ – partialhash Jun 15 at 2:28
  • 1
    $\begingroup$ If you don't like chunking, I have bad news for you about how every variable-length hash function in use works inside. $\endgroup$ – Squeamish Ossifrage Jun 15 at 4:01
  • $\begingroup$ I try to make the question general, just verifying partial message given full message hash. I'm afraid discussing so much about my application constraints will limit the usefulness of the question. If it's fundamentally impossible then I'd take that as an answer. $\endgroup$ – partialhash Jun 15 at 4:32
5
$\begingroup$

You've asked for a way to hash a file into a short string $h$ so that given a partial download $c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1}$ of the file that should start with $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{i-1}$ but may have been modified in transit, you can compute some verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| c'_2 \mathbin\| \cdots \mathbin\| c'_{i-1})$ to tell you whether this partial download is good or not.

You haven't specified what security properties you want, but let's say it's random oracle indifferentiability of the hash function given an underlying short-input hash function $H$ like SHAKE128-256, which serves for preimage resistance, second-preimage resistance, and collision resistance (and therefore forgery detection). This also works if you randomize $H$ and use $H_r$ instead, like KMAC128, which obviates the need for collision resistance.

Here is a slight variation:

  • The client will download, alongside each chunk $c_i$, a small set of additional hashes $a_i$ that can be used together with $h$ to verify that $c_i$ is correct.
    • The adversary may tamper with the chunk $c_i$ and the additional hashes $a_i$, replacing them by $c'_i$ and $a'_i$; we assume only that the client is given a hash of the complete download, $h$, that is known to be good.
  • We will define a verification function $F(h, c'_i, a'_i)$ which returns 1 if $c'_i = c_i$ and $a'_i = a_i$, that is if the data were unmodified in transit, and 0 with high probability under any forgery attempt. ($F$ is defined on chunks, not on prefixes of the file, so it doesn't actually matter which order you download them in.)

In this slight variation, the original verification function $f(h, c'_0 \mathbin\| c'_1 \mathbin\| \cdots \mathbin\| c'_{i-1})$ will be replaced by

\begin{multline} f\bigl(h, (c'_0, a'_0) \mathbin\| (c'_1, a'_1) \mathbin\| \cdots \mathbin\| (c'_{i-1}, a'_{i-1})\bigr) \\ = F(h, c'_0, a'_0) \mathbin\& F(h, c'_1, a'_1) \mathbin\& \cdots \mathbin\& F(h, c'_{i-1}, a'_{i-1}). \end{multline}

Transmitting the additional hashes is not likely to be an onerous burden: The number of additional hashes for each chunk is logarithmic in the length of the file, the size of the hash can be a tiny fraction of the size of a chunk (say, 32 bytes vs. a megabyte), and most likely, the client will be downloading, e.g., an HTTP header alongside the chunk $c'_i$ anyway, not to mention TCP and IP headers and ethernet frames and any other encapsulation, like tunnels and VPNs, that may happen on the network anyway.

Similarly, storing the additional hashes on the server is not likely to be an onerous burden either: Your file system almost certainly stores various metadata alongside each file anyway, including its modification times, the locations on disk where its data are stored, directory entries pointing to it, etc.


How does this work?

Hash computation. Before anyone can download the file:

  1. On the server, split the full file up into chunks $c_0, c_1, c_2, \dots, c_{2^\ell - 1}$.
  2. On the server, compute the hashes \begin{align} h_{0,0} &:= H(0, 0, c_0), \\ h_{0,1} &:= H(0, 1, c_1), \\ h_{0,2} &:= H(0, 2, c_2), \\ \vdots \\ h_{0,2^\ell - 1} &:= H(0, 2^\ell - 1, c_{2^\ell - 1}). \end{align} These are the leaves of a Merkle tree.
  3. On the server, compute the hashes \begin{align} h_{1,0} &:= H(1, 0, h_{0,0}, h_{0,1}), \\ h_{1,1} &:= H(1, 1, h_{0,2}, h_{0,3}), \\ h_{1,2} &:= H(1, 2, h_{0,4}, h_{0,5}), \\ \vdots \\ h_{1, 2^{\ell-1} - 1} &:= H(1, 2^{\ell-1} - 1, h_{0, 2^\ell - 2}, h_{0, 2^\ell - 1}). \end{align} These are the first level of the Merkle tree above the leaves.
  4. On the server, compute the hashes \begin{align} h_{2,0} &:= H(2, 0, h_{1,0}, h_{1,1}), \\ h_{2,1} &:= H(2, 1, h_{1,2}, h_{1,3}), \\ h_{2,2} &:= H(2, 2, h_{1,4}, h_{1,5}), \\ \vdots \\ h_{2,2^{\ell-2} - 1} &:= H(2, 2^{\ell-2} - 1, h_{1,2^{\ell-1} - 2}, h_{2,2^{\ell-1} - 1}). \end{align}
  5. Repeat, combining two hashes at a time.
  6. At the end of this process, the server will have a hash $h := h_{\ell,0}$. This is the root of a Merkle tree, which is also a hash of the original data $c_0 \mathbin\| c_1 \mathbin\| c_2 \mathbin\| \cdots \mathbin\| c_{2^\ell - 1}$. Share the root hash $h = h_{\ell,0}$ of the Merkle tree first. For example, you might transmit it on another channel (like how a .torrent file is shared separately from the pieces), or the server might digitally sign it with a long-term key pair whose public key the client knows a priori.

Download process. When the client wants to download the $i^{\mathit{th}}$ chunk $c_i$, after getting the known-good hash $h$ of the file:

  1. The server sends a set $a_i$ of additional hashes alongside $c_i$, $$a_i := (h_{0,i \oplus 1}, h_{1,\lfloor i/2\rfloor \oplus 1}, h_{2,\lfloor i/2^2\rfloor \oplus 1}, \ldots, h_{\ell - 1, \lfloor i/2^{\ell - 1}\rfloor \oplus 1}).$$ These are the sibling hashes of a path down the Merkle tree—for the subtrees that do not have $c_i$ in them. Here $\oplus$ means xor; that is, we are toggling between the even- and odd-numbered hash indices.
  2. The client receives a putative chunk $c'_i$ and the putative hashes $a'_i := (h'_{0,i \oplus 1}, \ldots)$, which may be the correct chunk $c_i$ and the correct hashes $a_i = (h_{0,i\oplus 1},\ldots)$ or may have been modified in transit by an adversary. The client can now compute \begin{align} h'_{0,i} &:= H(0, i, c'_i), \\ h'_{1,\lfloor i/2\rfloor} &:= H(1, \lfloor i/2\rfloor, h'_{0,2\lfloor i/2\rfloor}, h'_{0,2\lfloor i/2\rfloor + 1}), \\ h'_{2,\lfloor i/2^2\rfloor} &:= H(2, \lfloor i/2^2\rfloor, h'_{1,2\lfloor i/2^2\rfloor}, h'_{1,2\lfloor i/2^2\rfloor + 1}), \\ \vdots \\ h'_{\ell,0} &:= H(\ell, 0, h'_{\ell - 1, 0}, h'_{\ell - 1, 1}). \end{align} To ensure the data were not modified in transit, the client then checks $h'_{\ell,0} \stackrel?= h_{\ell,0}$ and drops the data on the floor if it fails. In other words, we have the chunk verification function $$F(h, c'_i, a'_i) := \begin{cases} 1, & \text{if $h'_{\ell,0} = h$;} \\ 0, & \text{otherwise,} \end{cases}$$ with $h'_{\ell,0}$ computed from $c'_i$ and $a'_i = (h'_{0,i \oplus 1}, \ldots)$ as above. Note that the computation of $F$, the verification function, involves only the root hash $h$, the chunk $c'_i$ itself, and the $\ell$ hashes included in $a'_i$; verifying a chunk does not require knowing anything else about any other chunk in the file.

For example, in an eight-chunk file, when you transmit chunk $c_6$, send it alongside $h_{0,7}$, $h_{1,2}$, and $h_{2,0}$; the client, given the possibly modified $(c'_6, h'_{0,7}, h'_{1,2}, h'_{2,0})$, computes $h'_{0,6} = H(0, 6, c'_6)$, $h'_{1,3} = H(1, 3, h'_{0,6}, h'_{0,7})$, $h'_{2,1} = H(2, 1, h'_{1,2}, h'_{1,3})$, and $h'_{3,0} = H(3, 0, h'_{2,0}, h'_{2,1})$, and then verifies $h'_{3,0} \stackrel?= h_{3,0}$ before accepting the chunk $c'_6$ as genuine. The information needed to download and verify $c_6$ is illustrated in the diagram below:

  • The red solid boxes are data transmitted. Note that there is no need to download any other chunk to verify $c_6$—only three hashes are needed.
  • The blue dashed boxes are recomputed by the receiver.
  • The red solid circle is the root of the Merkle tree, i.e. the hash $h$ of the whole file, which is sent first on some channel assumed not to be corrupted, and which the receiver uses to verify each chunk.

Merkle tree with fanout 2, height 3, and total length 8

What does this cost? Let $|c|$ be the maximum chunk size, say 64 KB or 1 MB, $|H|$ be the hash size, typically 256 bits, and $n = 2^\ell$ be the total number of chunks.

  • The overhead you must store is a total of $2n$ hashes (one for each chunk, and an additional one for each node in the tree) costing $2 |H| n$ bits of storage.
  • The overhead you must transmit alongside each chunk is $\ell = \log_2 n$ hashes, if the server does nothing to avoid resending hashes the client already has, so the total number of additional bits transmitted for hashes alongside the $n$ chunks is at most $|H| n \log_2 n$.

Thus, the total number of bits stored is $|c| n + 2 |H| n$ and the total number of bits transmitted is $|c| n + |H| n \log_2 n$.

Here are some example data volumes to get some perspective for how much this costs:

\begin{equation} \begin{array}{rrrrrr} \text{file size} & \text{$|c|$} & \text{$|H|$} & \text{hash storage} & \text{hash tx} & \text{tx overhead} \\ 1\,\text{MB} & 1\,\text{KB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 31.25\% \\ 1\,\text{MB} & 64\,\text{KB} & 32\,\text{B} & 1\,\text{KB} & 2\,\text{KB} & 0.20\% \\ 1\,\text{GB} & 64\,\text{KB} & 32\,\text{B} & 1024\,\text{KB} & 7168\,\text{KB} & 0.68\% \\ 1\,\text{GB} & 256\,\text{KB} & 32\,\text{B} & 256\,\text{KB} & 1536\,\text{KB} & 0.15\% \\ 1\,\text{GB} & 1\,\text{MB} & 32\,\text{B} & 64\,\text{KB} & 320\,\text{KB} & 0.031\% \end{array} \end{equation}

Exercises for the reader.

  • Handle all the fenceposts in non-power-of-two lengths.
  • Extend to radix $r > 2$ with total transmission cost of $|c| n + |H| (r - 1) n \log_r n$ bits.
  • Generalize to unbalanced Merkle trees, e.g. backwards SHA-256 if you want to download only in start-to-end order. What costs does this restriction on order save?
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Ella Rose Jun 15 at 14:59
1
$\begingroup$

Suppose you found an error-detecting code $f(H(m), m')$ (forget random oracles, second-preimage resistance, etc.) with the following properties:

  1. $|H(m)| = O(1)$, i.e. the checksum overhead is independent of the message length.
  2. $f(H(m_0 \mathbin\| m_1), m_0) = f(H(m_0 \mathbin\| m_1), m_0 \mathbin\| m_1) = 1$
  3. $f(H(m_0 \mathbin\| m_1), m_0 + \delta) = 0$ with high probability when $\delta \ne 0$
  4. $f(H(m_0 \mathbin\| m_1), m_0 \mathbin\| (m_1 + \delta)) = 0$ with high probability when $\delta \ne 0$

This would be an astonishing development in coding theory, because it would mean that we could detect fine-grained errors in any message on the planet just by hashing them all into a short $|H(m)|$-bit string as follows:

  1. Check every book $m_0, m_1, m_2, \dots$ out of the Library of Alexandria.
  2. Concatenate them all into one giant message $m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots$, encoded appropriately so that the colophon of the previous book doesn't get confused with the title page of the next book.
  3. Compute $h = H(m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots)$ and store it somewhere safe—replicate it at libraries around the world, put it in the blockchain, tattoo it on your forehead, etc.
  4. Whenever you're concerned that a cosmic ray might have dislodged a piece of type and thereby caused a typo into one of the books in the library, check $f(h, m'_0)$, which, if there was an error in $m'_0$ from $m_0$, will fail with high probability, in which case get book 0 reprinted; otherwise, check $f(h, m_0 \mathbin\| m'_1)$, which, if there was an error in $m'_1$ from $m_1$, will fail with high probability, in which case get book 1 reprinted; and so on.

Even better, you could use this bit by bit to determine exactly which bit was flipped, so this would become the world's most efficient error-correcting code too!

Archivists still put checksums on individual pieces of data, instead of merging into one collaborative cabal of archiveborg with a single checksum for all the world's data, so I don't think that breakthrough in coding theory has been found yet.

$\endgroup$

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.