What kinds of cryptocurrency smart contracts could be used to reward people for solving specific kinds of useful computational problems?
Background
In this question, I asked for proposals for useful computational problems that can be turned into useful proof-of-work problems. One issue with that previous question is that the requirements for useful proof-of-work problems are quite restrictive. Unfortunately, people are still using cryptocurrencies with completely useless mining problems which is a terrible thing since cryptocurrencies have lost about 90 percent of their market cap from January 2018 to January 2019 and the cryptocurrency community is in January 2019 desperate for innovation. I therefore am wondering of how to create units of value by solving important scientific, computational, or mathematical problems using cryptocurrencies in other ways besides using mining problems. Cryptocurrency smart contracts can be used to reward and finance people with tokens and coins for solving useful computational problems. Furthermore, the smart contract could disperse tokens in more flexible ways than is possible with a cryptocurrency mining problem. For example, a smart contract could disperse tokens as a reward for winning chess tournaments while a cryptocurrency mining problem cannot fruitfully reward anyone for winning Chess.
A smart contract is a protocol put on a cryptocurrency blockchain that can create its own type of tradable token and reward entities with tokens or coins (or punish entities by taking their coins or tokens) if the conditions of the contract are satisfied. In this post, we shall distinguish between tokens and coins. Coins are to the unit of value created by the cryptocurrency itself while tokens are the units of value created and distributed by the smart contract which is an application built upon the cryptocurrency. For example, a smart contract may say "Alice pays Bob 1,000,000 coins if Bob submits a proof of the Riemann hypothesis (in ZFC+all large cardinals) within 1 year and otherwise Alice's coins are returned to herself" or "Alice and Bob both set aside 50 coins. Alice and Bob then play a game of infinite 3D quantum chess and the winner gets the other person's 50 coins and wins a tradable digital trophy."
The goal
Our goal is to come up with ideas for cryptocurrency smart contracts that will reward people with tokens or coins for solving useful computational problems or otherwise engaging in useful computational activity. For example, these smart contracts could reward entities for solving NP-complete problems, winning chess tournaments, or creating secure symmetric cryptosystems among other things.
The computational problem should satisfy the following conditions:
Easy to verify but difficult to win: Running the smart contract should take as little computational resources as possible. However, it should be a difficult computational challenge to satisfy the conditions of the smart contract in order to win the token. For example, chess will satisfy this criterion since validating a chess move does not require a significant amount of computation while searching for the optimal chess move does take much computational power. Blockchains are extremely inefficient, so these smart contracts need to be as efficient to validate as possible.
Coarse tuning difficulty: The difficulty of obtaining the cryptocurrency token should be tunable. If more resources are spent on winning the token, then the difficulty of winning the token should also increase so that tokens are given out at a somewhat predictable rate. However, since such a token is not used to establish consensus, the difficulty does not need to be as finely tuned as it is with a proof-of-work problem. For example, if the smart contract makes players play a game like Go against each other, then the difficulty is automatically coarsely tunable since as one player obtains better strategies for winning the game, his opponent will likewise obtain better strategies.
Automatic generation: The computational problems need to be generated automatically without a central entity being able to modify the computational challenge. Furthermore, the smart contract should not rely upon any data outside the blockchain.
Uncheatable: There should not be a way for anyone to take advantage of the smart contract and win tokens or coins without properly doing the required computations.
Useful knowledge made public: The entities who solve the computational problem will likely have some secret knowledge including algorithms and near solutions that were not posted on the blockchain. It will probably be useful for this knowledge to be out in the public. However, the solvers would also likely have an incentive to keep this knowledge a secret. The smart contract should be set up so that as much useful knowledge is posted on the blockchain as possible.
Public good: Ideally, the general public should benefit from the solutions to the problems instead of a few private individuals. Otherwise, one does not need to use a smart contract token to fund the computation.
No unintended solution traps: If someone makes a smart contract cryptocurrency token to reward useful computation, there may be a risk that as the smart contract automatically generates instances of the computational challenge, each of the individual instances is either trivial or not representative of the underlying problem.
The following conditions are needed for useful proof-of-work problems but are not absolutely necessary for smart contract token problems:
A solution on average every 10 minutes-Bitcoin was designed so that a solution to the mining problem is found on average every 10 minutes. However, there is no need for a cryptocurrency token to be distributed every ten minutes. For instance, it is perfectly acceptable for a cryptocurrency token to be distributed every 24 hours; for example, if it is too computationally costly for the blockchain to evaluate the smart contract every 10 minutes, then the token could be dispersed every 24 hours in order to minimize costs.
Usefulness and scientific importance-People spend billions of dollars of resources on solving cryptocurrency mining problems. Since a cryptocurrency market cap may grow to billions of dollars, one needs to choose a mining problem so that the resources spent on mining are still justified regardless of the market cap of the underlying cryptocurrency. Since the value of a scientific cryptocurrency token is intimately related with the value of the scientific problem it is trying to solve, there is little chance that the resources spent on solving the problem for the cryptocurrency token will greatly exceed the scientific merit or perceived merit of the problem itself. I would not consider any mining problem related to chess or go or any other combinatorial game to be scientifically important enough to be used as a cryptocurrency mining problem, but a smart contract rewarding tokens to people who win chess tournaments sounds like a fun idea. If you create a cryptocurrency token financing a problem that only you and a couple other people are interested in solving, then the worst that could happen is that the smart contract shuts down and no more tokens are issued or that the tokens produced by the smart contract have very little value.
Progress freeness-A computational problem is said to be progress free if a person does not gain any advantage simply because she has been working on the problem already. In other words, a problem is progress free if the amount of time it takes to solve the problem follows an exponential distribution. Cryptocurrency mining problems are required to be progress free. However, smart contract token problems are not required to be progress free.
Fungibility-A type of object is said to be fungible if the value of the object can be precisely quantified. For example, fiat currencies are required to be fungible since your newly minted 20 dollar bill is worth no more than my old crumbled 20 dollar bill. Gold is also fungible since the price of an ounce of gold is fixed, but diamonds are not fungible. Some cryptocurrency tokens such as cryptokitties are non-fungible; some cryptokitties are worth more than others. The coins obtained by solving cryptocurrency mining problems must be fungible. We prefer for the smart contract tokens to be fungible, but fungibility is not absolutely necessary to make a token of value.
Endless problems-If there comes a point in time when the difficulty of obtaining new tokens becomes exceedingly high or exceedingly low, then the smart contract could automatically close and issue no new tokens without putting the cryptocurrency at risk. There is nothing wrong with having a limited edition cryptocurrency token.
Solution tied to solver-In a cryptocurrency mining problem, the solution to that mining problem should only be valid for the entity that solves that problem. In other words, in a cryptocurrency mining problem, each entity will have its own version of the mining problem. However, it is perfectly acceptable for everyone to work on the same version of the problem in order to obtain smart contract tokens.
Unbreakability-If someone finds an algorithm that quickly solves a cryptocurrency mining problem, then that cryptocurrency will be in trouble. However, if a computational problem for a smart contract token is broken, then that smart contract can simply stop issuing any new tokens. A broken computational problem for a smart contract token can be taken to be a good thing because the computational problem is typically broken by good research.
These cryptocurrency tokens will be valuable in the following ways:
The tokens can be bought and sold for money since people will consider such tokens valuable since they represent the solutions to useful problems.
The smart contract could be constructed so that the cryptocurrency token will pay dividends in the underlying cryptocurrency. People will therefore assign value to the tokens since they will give coins.
When a new cryptocurrency is launched, one will need to distribute the newly minted coins somehow. Many of the coins in the initial distribution could be given in exchange for burned cryptocurrency tokens.
I still think useful proof-of-work problems are the best way to initially distribute a cryptocurrency. Furthermore, I personally hesitate to support a scientific cryptocurrency token that runs on a blockchain that is secured by a useless mining problem or where a large portion of the coins were distributed through a mechanism that does not require mining. These useful cryptocurrency tokens are therefore not a replacement for useful cryptocurrency mining problems. There are a couple of other tradeoffs to be made by solving a scientific problem using smart contract tokens rather than mining problems including the following.
Smart contract tokens are unable to establish consensus for a blockchain, so smart contract tokens cannot completely replace useful proof-of-work problems. The only purpose of smart contract tokens is to reward people for solving useful problems and to solve the question of how to distribute cryptocurrencies.
Smart contract tokens cannot be so valuable that the value of a smart contract token approaches the value of the underlying cryptocurrency. On the other hand, a useful cryptocurrency mining problem must be valuable enough to justify the resources spent on solving the problem. Therefore, highly valuable problems that require large quantities of work are better to be used as cryptocurrency mining problems while low value problems that require little work are better to be used to make smart contract tokens.
Smart contract tokens are not a part of their own independent blockchains.
Here are some examples of potential useful smart contract tokens.
Answer format
An answer should be formatted the same way that Examples A and B are formatted. In particular, an answer should not only specify the underlying computational problem but it should also give an outline of how the smart contract will operate in order to reward those who solve the computational problem.
An imperfect smart contract proposal may still be useful for experimental purposes even if it does not have as much direct use as one would like it to have, so I would not shy away from proposing potentially flawed cryptocurrency tokens.
Examples
$\textbf{Example A: Satisfiability:}$
Smart contracts could be used to reward people for solving NP-complete problems. Here are the details of how smart contracts could be used to reward people for solving the circuit satisfiablity problem.
Let $\mu$ be a function such that for each circuit $C$, $\mu(C)$ is some measure of the complexity of the circuit $C$. Let $s$ be a self-adjusting number similar to the difficulty in Bitcoin mining.
The smart contract cycles through the following steps repeatedly.
Step 1: Bidding: Parties bid for the right to submit a circuit.
Step 2: Suppose that Alice is the highest bidder and that Alice has bid $r$ coins. Then Alice will submit a circuit $C$ to the blockchain with $\mu(C)<s$ that she knows how to satisfy but which is difficult for other parties to satisfy.
Step 3: Everyeone will be given a period of time in order to find an input $\mathbf{x}$ with $C(\mathbf{x})=1$. If an entity Bob finds an input $\mathbf{x}$ with $C(\mathbf{x})=1$, then Alice will forfeit all of her $r$ coins, Bob will receive $r/2$ coins, and the other $r/2$ of Alice's bidded coins will be given to tokenholders in order to give the tokens value. If nobody finds an input $\mathbf{x}$ with $C(\mathbf{x})=1$ within the allotted time frame, then Alice will get to keep her $r$ bidded coins and Alice will also receive a token.
In the above interaction, Alice is incentivized to construct circuits $C$ with $\mu(C)<s$ but which are difficult but not impossible to satisfy. Bob is incentivized find inputs $\mathbf{x}$ where $C(\mathbf{x})=1$.
The number $s$ will be automatically self-adjusted so that there is about a $50$ percent probability that nobody besides Alice will be able to find an input $\mathbf{x}$ where $C(\mathbf{x})=1$ within the allotted time period.
Since the circuit satisfiability problem is NP-complete and in a sense is a good representative for all NP-complete problems, I hope that this sample problem will help people develop better algorithms for solving NP problems and also finding instances of NP-complete problems that are particularly difficult to solve.
$\textbf{Example B: Boolean circuit games:}$
We propose a cryptocurrency smart contract in order to improve algorithms for solving general PSPACE problems. As with Problem A, the participants will solve a problem that is representative of all PSPACE complete problems.
This smart contract shall cycle through endless bracket tournaments.
Before the tournament, potential players will pay an entrance fee in order to play in the tournament. This fee will be used to reward the winner of the tournament as well as cover the costs of playing the game. A portion of this fee will also go to the owners of the tokens produced by the smart contract in order to give the tokens some value.
Suppose that $C$ is a Boolean circuit mapping $2^{m}$ to $2$. The game $G_{C}$ with first player Alice is the game where for $i\in\{0,...,m-1\}$, if $i$ is even, then Alice will choose some $x_{i}\in\{0,1\}$ and if $i$ is odd, then Bob will choose some $x_{i}\in\{0,1\}$. If $C(x_{0},...,x_{m-1})=1$, then Alice wins. If $C(x_{0},...,x_{m-1})=0$, then Bob wins.
Suppose that Alice and Bob are competing against each other in the tournament. Then Alice and Bob will perform the following steps.
Alice commits a Boolean circuit $C$ mapping $2^{m}$ to $2$.
Bob commits a Boolean circuit $D$ mapping $2^{n}$ to $2$.
Alice and Bob both reveal their circuits $C,D$ after they have committed their circuits.
Alice and Bob will then compete against each other in the following rounds.
Round 0: If $\mu(C)<\mu(D)$, then Alice wins Round 0. If $\mu(D)<\mu(C)$, then Bob wins Round 0. If $\mu(C)=\mu(D)$, then the winner of Round 0 is chosen at random.
Round 1: Alice and Bob play the game $G_{C}$ where Alice goes first.
Round 2: Alice and Bob play the game $G_{C}$ where Bob goes first.
Round 3: Alice and Bob play the game $G_{D}$ where Alice goes first.
Round 4: Alice and Bob play the game $G_{D}$ where Bob goes first.
The winner is the entity who has won the most out of five rounds. The winner of the bracket tournament will receive a token along with a reward funded by the tournament entrance fee.
Alice is incentivized to create a circuit $C$ with $\mu(C)$ minimized where she knows how to win the game $G_{C}$ whenever she goes first but for which her opponent Bob will not be able to win $G_{C}$ when he goes first.
Alice can easily create a circuit where she wins both Round 1 and Round 2. Likewise Bob can easily create a circuit where he wins both Round 3 and Round 4. However, it will be difficult for Alice to create a circuit $C$ where she will win Rounds 0,1,2 since both Alice and Bob are competing to minimize $\mu(C)$ vs $\mu(D)$ while still being able to win Rounds 1-4.
The problem of finding a winning strategy to the games of the form $G_{C}$ is PSPACE-complete and related to the PSPACE-complete quantified Boolean formula problem, so this cryptocurrency token will hopefully reward entities who are good at solving general PSPACE problems.
In Examples A and B, there is risk that the useful knowledge produced in solving these problems will remain a secret along with other potential issues with these examples such as an unintended solution trap.
I could see smart contracts being used to solve computational problems in various areas of mathematics such as cryptography, group theory, and combinatorics.
