Sometimes a blockchain application needs to perform an operation, such as a scrypt verification, that is extremely computationally expensive. Are there any techniques that can help me design around this problem so that my application doesn't have to pay enormous fees?

  • Also see the previous, similar question: ethereum.stackexchange.com/questions/22/… Jan 20 '16 at 17:45
  • Posting an answer to this question now, which will help to show how these two questions are actually slightly different from each other. Jan 20 '16 at 17:53
  • There. As you can see, the objective of this question is to "design around the problem" by taking the computation off chain, whereas I'm taking the other one to be about the performance optimisation techniques used in on-chain code. Jan 20 '16 at 18:35

Yes, there are! Although the Ethereum scripting language is Turing Complete and therefore able to perform any possible computation, there is a simple way to remove many types of difficult computation from having to be performed directly on the blockchain itself, by making use of deposits, challenges and verifications.

Take the example of verifying a scrypt operation. My application might have some data, and it wants to know what the scrypt hash of that data is in order to compare it against a reference or to check a certain property of the hash (for a mining algorithm, perhaps). Instead of computing the hash immediately, the application can instead allow anyone to submit the hash of the data themselves, along with a deposit. The purpose of the deposit is so that submitter can be penalised if they submit an inaccurate hash, and for the sake of our example let's assume the deposit is large enough to cover the cost of computing the operation on the blockchain if necessary, in addition to the penalty.

Next, the application holds a challenge period so that external observers have a chance to check on their own machines if the data in fact hashes to the claimed value. Because this operation is performed by only a few observers instead of the entire blockchain, this is a total savings in terms of resources. During the challenge period, if any of the observers discovers that the submitted hash is inaccurate, they submit a transaction to that effect containing their own counter-deposit. Again we can assume for the sake of our example that the deposit is large enough to cover the costs of verifying the hash on chain.

Now the application merely needs to check the result and return the remainder of the deposits to the party who was proved correct, along with an additional reward of some kind for a correct hash. Or, if no challenge was submitted during the challenge period, the application can merely return the reward along with the deposit to the original user, without performing any verification. With this technique, users who submit correct hashes or challenges receive a reward for their efforts, and if they submit incorrect hashes (or incorrect challenges) they pay a large penalty. The incentives ensure that any misbehaviour is a losing strategy, and the application developer themselves can play the role of both submitter and challenger to ensure the application operates as desired. Because observers will not pursue losing strategies, the application will almost never have to actually verify the hash.

An advanced version of this technique would give the "caught" submitter with an incorrect hash an opportunity to "fess up" in return for a lower penalty, so that even in the event an invalid hash is submitted, verification will not need to be actually performed.

More elaborate techniques are also possible involving zero knowledge proofs, but this basic deposit-challenge-verification approach requires no complicated mathematics, and incurs a lower computational cost than most zero knowledge proof techniques.

  • 3
    Proof-of-Concept for this idea is located here: github.com/pipermerriam/ethereum-computation-market
    – Matt
    Jan 20 '16 at 18:50
  • Doesn't this open up a possibility of an attack, where an attacker controlling multiple addresses gives an invalid hash. If the number of attacker controlled addresses is greater than the number of valid hashes submitted in transactions by legit users the attacker wins in a sense that your application will always pick the majority correct hash (since it does not actually compute the hash on its own). Another issue is with respect to the reward; only one submitter is rewarded (continued)
    – Sebi
    Jun 4 '16 at 21:11
  • (continued) but there may be several valid hashes submitted submitted by users who will not get anything for the invested computation and time.
    – Sebi
    Jun 4 '16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.