Is it possible to build short proofs of arbitrary folds over a huge list?

With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information close to just logarithm of the size of the whole tree. Merkle proofs, thus, probabilistically confirm the result of this specific fold:

isMember :: ∀ t . List t -> Bool
isMember e = foldr (\ h t -> h == e || t) False


My question is if the same result can be extended to arbitrary folds; or, in other words, is it possible to prove arbitrary computations over a big list using some clever trick similar to Merkle Trees?

Formally

Given those 5 values:

1. H :: String -> Uint256, a fingerprint function
2. H(X) :: Uint256, the fingerprint of a dataset
3. F :: String -> String, an arbitrary computation
4. Y :: String, the claimed result of F(X)
5. A short proof

I need a verify function that returns true iff F(X) == Y, without having to run F(X); perhaps not even having the whole original dataset X.

Specific example

Suppose that you have a huge dataset (20 GB) distributed through a network of 100 computers that don't trust each-other. Is there any way for a computer to generate a claim such as the sum of this dataset is 1650874919052809!, so that other nodes are able to probabilistically verify that claim is correct, without actually running sum dataset?

Yes, there is a generalization of the construction you mentioned. However, it's utility depends on the function F. The guarantees you get are meaningful only if F is robust, in the sense that you have to change a large fraction of the dataset to make any (meaningful) change to the output of the computation.

Suppose we have an untrusted agent Agatha who is going to do the computation for us and try to prove that she did it correctly. She'll build a Merkle tree in the same way, with one leaf per prefix of the list, and the leaf holding (the hash of) the intermediate state of the fold after processing that prefix. Thus, a list with $n$ items will involve construction of a Merkle tree with $n$ leaves. Agatha will send the hash at the root of the Merkle tree. She will also send the value at the rightmost leaf and a witness to its value. $\newcommand{\pl}{\operatorname{polylog}}$

Agatha will do $O(n)$ work to compute the fold and build the Merkle tree. We want the verifier to be able to verify the correctness of the result, using only $o(n)$ time and $o(n)$ communication with Agatha.

How will the verifier check Agatha's claimed result? The verifier can pick two adjacent leafs at random, ask Agatha to send a witness to the values at those two leaves, and re-apply F to check that the second was correctly obtained from the first. The verifier can repeat this many times. In each round, Agatha sends $O(\lg n)$ bits, and the verifier does $O(\lg n)$ work.

Now suppose Agatha cheats on at least a $p$ fraction of the F applications. Will this be detected? Well, each round has at least a $p$ chance of detecting Agatha's malfeasance. Thus, after $100/p$ rounds, there is a $(1-p)^{100/p} \approx e^{-100} < 2^{-128}$ chance that Agatha's malfeasance goes undetected. In other words, $O(1/p)$ rounds suffice to detect Agatha if she cheats on at least a $p$ fraction of the applications of F.

On the other hand, if Agatha cheats on only a single application of F (say), she has a good chance of getting away with it; the verifier has no good way to detect this.

So, this construction is only useful if F is such that cheating on a small number of applications of F is harmless. This is closely related to the notion of a robust function, from robust statistics, which is about functions where changing a small number of inputs makes only a negligible change to the final output. For instance, since the sum, max, and min are not robust, this construction is not useful for computing the sum, max, and min. However, the median is robust, and the median can be computed securely via such a tree. As a simpler example, consider counting the number of entries in the database that match some pattern; this can be done securely via such a tree. In particular, Agatha can cheat on at most a $p$ fraction of nodes, and we can arrange that this changes the final count by at most $pn$. If that bound on the (additive, absolute) error is good enough, then we can achieve acceptable security.

In practice you probably typically don't want to use this kind of general construction. You can often do better by building a protocol that is specialized or customized for the particular function F you are dealing with. You can find many papers on this topic in the research literature, under names like "secure aggregation" or "outsourced computation" or "resilient aggregation". I've seen papers in the database literature, the cryptography literature, and the sensor network literature.

For example, if F is associative and commutative, and if the fold is robust, then we can obtain a secure Merkle tree scheme, where each internal node in the tree holds the result of the fold on a sublist corresponding to the subtree rooted at that internal node. (This is a bit different than the prefix construction mentioned earlier, and offers better security when F satisfies this property. The verifier needs to pick a random node and check that it was constructed correctly, rather than picking a random leaf.)

The preceding paragraph immediately lets you compute the "count" operator securely, up to an additive error of $\pm pn$. If we want to compute the median, Agatha can first compute the median offline, say $m$, then report $m$, and use a count query to count the number of data items that are $\le m$. The verifier can verify this count query up to an additive error of $\pm pn$, which proves that $m$ isn't "too far" from the true median (its rank differs from the rank of the true median by at most $\pm pn$, which in practice means it'll be quite close to the true median).

There's lots more one can say, and I've probably made oversimplifications at multiple points in this exposition, but hopefully this gives you some ideas and an entry point to the research literature on this subject.

• I love your answers, I honestly wish I could print a book of the contents of your mind. – MaiaVictor Jan 19 '17 at 1:23