Outsource Computation on Bitcoin SV
We present a novel paradigm to outsource intensive computation using Bitcoin smart contracts. It is amenable to solving a large set of computationally intensive problems. We apply it to the Travelling Salesman Problem as an example.
Travelling Santa/Salesman Problem
On Christmas Eve, Santa Claus needs to traverse every family to deliver presents to the children. He wants to find the shortest route to make the round-trip of all chimneys before preparing his sledge. Impressed by Bitcoin’s superior smart contracting capability, he decides to leverage it to tackle this challenge, which is computationally intensive since the number of chimneys is large¹.
He deploys the following contract and locks up an entire bitcoin in the UTXO containing it. Anyone that finds a path no longer than a given threshold can unlock and redeem the bounty². It is noteworthy that the contract does not recompute the path, but merely verify if its length meets requirement.
Practical Concerns
In practice, additional measures, such as R-Puzzle, have to be taken to prevent attackers from stealing the solution, which is in plaintext and can be intercepted.
Also, another spending condition (i.e., a public function in sCrypt) can be added such that if no solution is found by a deadline, the bounty can be redeemed by the owner.
Generalization
It is straightforward to generalize the above contract to solve a large class of computation problems. They are difficult to solve but easy to verify once a solution is proposed. For example, all NP-complete problems belong to such a class.
This approach distinguishes Bitcoin from competing smart-contract blockchains. The latter has to rerun each computation to verify it, while the former can verify without recalculating, making it immensely efficient and scalable. Combined with micropayments, this opens up an enormous global computation market, more granular, competitive, and efficient than status quo.
Happy holidays!
[1] Travelling Salesman Problem is NP-Complete.
[2] We solve the decision version of TSP.
