An interesting paper on a new data structure [1] was mentioned on HN [2].
If I read this right, it's a cheap challenge-response protocol for verifying a node performed a computation honestly.
I picture this as being able to potentially solve the "every node must compute every instruction of every transaction" scalability issue with Turing-complete Ethereum-like networks.
The core design idea I had was to publicly post the result of some computation, then if any nodes disagree they can challenge. In a challenge, both sides post a bond, then you run the challenge-response protocol in the paper on the blockchain. The loser forfeits their bond.
You could have a standing bond attached to the posted result which will be forfeit on any successful challenge. You could have every standing bond accumulate inflationary shares proportional to its size, thus incentivizing people to certify third-party computations by bonding their funds to those results. You should independently verify the computation before posting such a bond, however, since if you post your bond to an incorrect result then you will lose the bond because someone will be able to successfully challenge you.
I'm not sure how feasible any of this is in practice, I just wanted to post about some of the ways this paper directed my thoughts.
[1]
http://people.csail.mit.edu/nickolai/papers/vandenhooff-versum.pdf[2]
https://news.ycombinator.com/item?id=8598244