[Cryptography] Software proposal for verifiable stateless computing

[Daniel Hong]

On Sunday, 4 August 2019 1:06 AM, John Kelsey <crypto.jmk at gmail.com> wrote:
...
> if nobody verifies the state chains, how does anyone rely on the computation results? Why cant a mining node just make up incorrect results?

We rely on the fundamental fact that for a generalized parameter a, b and function f(x), g(x), if a=b and f(x)=g(x), statements f(a)=g(b) and f(b)=g(a) will be both true when honestly computed.

Because all functions are cryptographically tied together and signed, and they do not change (unless the developer explicitly updates it), it is relatively easy to maintain verify the integrity of a bare codex (which holds all the function bytecode).

To verify the parameters and return values (state chain blocks), the same computation task is simply ran on a small, randomized portion of the computation pool. Because an AST and an empty callstack graph is given with the bare codex, when the resulting callstack graph's hashed state root does not match for a particular execution session, we can say that at least one of the devices are faulty.

In such a case, we can either: (i) trust the majority, or (ii) run a recursive tree search on the resulting callstack graph itself. In the case of (ii), because the call-and-return relationships between functions are already given, it would be easy to detect the faulty device and remove its key from the keychain - as all state chain blocks should be signed by a unique device key.

This approach does not guarantee the level of state integrity and liveness as those of a blockchain, but enough for performance-demanding commercial level applications. Also, there are lots of blockchains out there that are already good at those - so periodically submitting state proofs in a batch to a blockchain with a Smart Contract should also guarantee additional state integrity.

Daniel Hong
shhong at unifiedh.com