Outsource Computation on Bitcoin SV

How Santa uses Bitcoin to optimize his Christmas Eve trip

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¹.

TSP through US cities

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.

TSP Contract

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.

sCrypt Inc (https://scrypt.io) is a company with mission to providing integrated on-chain smart contracting solutions on Bitcoin SV. scrypt@moneybutton.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store