With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information logarithmic in 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 about a big list using some clever trick similar to Merkle Trees?
Specifically, I want to store a huge dataset (>20 GB) on several computers, and then I want any of those nodes to make arbitrary claims about that dataset (like: the max element is 198500461354!
), in such a way that other nodes can verify that claim is true without having to run max
over the whole dataset themselves.