Is it possible to build short proofs of arbitrary folds over a huge list?
-
04-11-2019 - |
Frage
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:
H :: String -> Uint256
, a fingerprint functionH(X) :: Uint256
, the fingerprint of a datasetF :: String -> String
, an arbitrary computationY :: String
, the claimed result of F(X)- 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
?
Keine korrekte Lösung