Verification of computation by untrusted source

A method of verifying a computation by an untrusted entity, the method comprising:

• on an untrusted device:
• storing states of the computation at one or more points along a length of the computation;
• generating one or more hashes based on the states of the computation at the one or more points along the length of the computation;
• generating a hash tree including one or more leaf nodes, wherein the one or more leaf nodes of the hash tree correspond to the one or more hashes of the states of the computation and further wherein the one or more leaf of the hash tree nodes are derived as the hash of at least two child nodes;
• creating at least one pair of paths from a root of the hash tree to the leaf nodes corresponding to the one or more of hashes of the states of the computation, the pair of adjoining paths of the hash tree leading from the root of the hash tree to the leaf nodes corresponding to hashes of adjacent point of the computation;
• and
• transmitting a proof of the computation comprising the at least one pair of paths from a root of the hash tree and siblings of each leaf destination of the pair of paths to one or more other entities for verification;
• on a third party device:
• receiving the transmitted proof of the computation including the at least one pair of paths of the hash tree and siblings of each leaf destination of the pair of paths;
• and
• verifying that a hash of each leaf destination is a hash of a pair of children of the leaf.

A method of verifying a computation by an untrusted entity, the method comprising:

• on an untrusted device:
• storing states of the computation at one or more points along a length of the computation;
• generating one or more hashes based on the states of the computation at the one or more points along the length of the computation;
• generating a hash tree including one or more leaf nodes, wherein the one or more leaf nodes of the hash tree correspond to the one or more hashes of the states of the computation and further wherein the one or more leaf of the hash tree nodes are derived as the hash of at least two child nodes;
• creating at least one pair of paths from a root of the hash tree to the leaf nodes corresponding to the one or more of hashes of the states of the computation, the pair of adjoining paths of the hash tree leading from the root of the hash tree to the leaf nodes corresponding to hashes of adjacent point of the computation;
• and
• transmitting a proof of the computation comprising the at least one pair of paths from a root of the hash tree and siblings of each leaf destination of the pair of paths to one or more other entities for verification;
• on a third party device:
• receiving the transmitted proof of the computation including the at least one pair of paths of the hash tree and siblings of each leaf destination of the pair of paths;
• and
• verifying that a hash of each leaf destination is a hash of a pair of children of the leaf
• wherein when the memory of the untrusted entity is full, a partial proof of the computation is published.