CompuCoin

This is a proposal to modify the BitCoin protocol in such a way so as to put a large proportion of the computing power spent in the creation of the block chain to practical use, at the same time creating something similar to "backing" for BTC with computing power.

The proposal has two free parameters, K1 and K2, which would be fixed by the community during implementation.

1) Create a standardized way for computing power bids to be encoding in the block chain, alongside transactions. I suggest posing problems in some simple NP-complete problem representation such as 3-SAT, along with a bid. There also needs to be a standardized way to post solutions.

2) Allow computing power bids, written in the above standardized form, to be encoded alongside transaction in the block chain, with the restriction that the maximum worst-case time complexity that is allowed to be encoded into any block is proportional to the current hash difficulty (with some proportionality constant K1).

3) At all times, all nodes maintain in memory a list of the current largest valid computing power bid which has successfully been encoded in the block chain (call this the "current task").

4) A solution of the current task is taken as a form of proof-of-work and can be used as a discount on the hashing proof-of-work difficulty required to produce the next block in the block chain. So, nodes can choose to devote some of their computing power to searching for a solution to the current task in addition to hashing. However, a fixed proportion, K2, of each node's (worst-case) effort must always be devoted to hashing. That is to say, a block is considered valid as long as both (a) the sum of (worst case effort of solving the current task) + (worst case effort of hashing proof-of-work) exceeds some number, and (b) (worst case effort of hashing proof-of-work) >= ((worst case effort of solving the current task) + (worst case effort of hashing proof-of-work))*K2

I propose that the block chain be forked to implement this.

Notes:

• the motivation for selling computing power in the form of nondeterministic polynomial time problems is:
  • to make use of the embarrassing parallelism of the BitCoin miner pool
  • to only allow problems for which the space in bytes necessary to encode the answer to the problem is very small even for very difficult problems (since these answers must be encoded into the block chain)
  • to make it simple to measure the worst-case time complexity of the problem posed
• 3-SAT is nice because the transformation of nondeterministic automata into a 3-SAT representation is relatively straightforward, conceptually, compared to e.g. TSP.
• the motivation for limiting the max time complexity of computing power bids is to prevent one miner from posing problems of large time complexity to which they already know the answer in order to be able to lock everyone else out from getting discounted blocks.
• the motivation for forcing the highest bid-to-date to be serviced is that, if each miner were able to choose which bid to service, then again each miner could submit their own bids for problems they already know the answer to, and in this way get to generate discounted blocks each time they generated a hash, without any additional effort. If the bid must be large and the time complexity limited, then miners who attempted to do this would periodically have their problems solved by other competing miners and would have to pay them large amounts of BTC.
• the motivation for requiring some amount of each proof-of-work to remain in the form of hashing is to prevent nodes from gaining control of the block chain by posing problems to which they already know the solution.
• this system means that people who want to buy computing power from the miner pool will first have to acquire BTC, driving up the price of BTC
• this is "backing" only in the same sense that U.S. income tax and petrodollars provide backing to the U.S. dollar -- it's not the case that your BTC can be redeemed for a fixed amount of computing power, but rather, it just guarantees there is at least one type of commodity which a lot of people will want to purchase from a set of suppliers who only accept BTC as payment (this assumes that the NP-complete solving power offered by the miner pool through this mechanism will end up being cheaper than other sellers of NP-complete computing power; which seems likely; and also that many people would want to purchase computing power in this form if it were cheaply available, which is debatable but which seems likely to me).
• Miners are incentivized to switch to a chain that implements this because this provides something like backing to BTC, which provides a floor to the price of 1 BTC.
• this proposal should be studied game-theoretically to make sure it that there is not some Nash equilibrium or similar in which the the current tasks almost always consist of problems posed by some node which already knows the solution. I have an intuition that the choice of K1 and K2 may be important.

-- BayleShanks

---

see also https://en.bitcoin.it/wiki/Intrinsic_worth_brainstorming