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

Image for post
Image for post
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

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

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.

Written by

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

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