Quantcoin is an idea for a cryptocurrency.
The current plan is for the auction to work as follows. The computing power buyers ("problem posters") will submit problems that they need solved, and bids in terms of how many Quantcoins they will pay to solve them.
In each cycle, the problem with the highest bid (per maximal computation time) will be selected for solution.
A more complicated, but possibly better, system would be to allow the miners to submit 'asks' for each problem just as the problem submitters submit 'bids'; then the problem with the most overlap between bids and asks is chosen (perhaps this overlapping amount of Quantcoin is actually destroyed when that problem is solved!); one issue is how to weight the 'asks' of miners (because we can guarantee that a bidder will only be allowed to bid if they reserve sufficient funds, but we cannot make the same guarantee of miners); perhaps fall-back to a proof-of-work and/or proof-of-stake scheme for that.
Miners will then attempt to solve the given problem. The first miner to solve the problem (and satisfy the other mining requirements) gets all of:
There could be a maximal bid proportional to the maximal difficulty of the problem. This would set a price floor for Quantcoin (but also would deter mining if quantcoin got too valuable? hmm, mb that's not such a great idea).
Note: if we opted to build this on top of Etherium, then since Etherium already does mining, we couldn't use this as mining. If we wanted, though, we could still have an Etherium-based computing power auction.
There will be a mechanism for the specification and publication (in the blockchain) of automated algorithmic trading strategies.
The publisher (owner) of a strategy will gain the right to have that strategy pre-emptively executed once each time a block is added to the blockchain, having priority over any strategies published later, and over user transaction in that block.
The strategy owner must pay fees to the miners to cover the cost of executing their strategy. Each block, the strategy owner must post a "strategy execution fee" proportional to the computational cost of executing their strategy. This will work by associating each strategy with a Quantcoin account/address; the strategy's assets will be placed at that address, and the fees will be taken out of that address. Initially, (and periodically, if the strategy is not sufficiently profitable) the strategy owner must to transfer Quantcoin to that address to cover future fees. The owner is the only one with the private key necessary to withdraw from this address (outside of the strategy's instruction, and the subtraction of the strategy's fees).
If a strategy's address can't pay its fees once, it becomes inactive forever, i.e. it loses its priority and is deleted from the 'strategy roster'. This is because we don't want miners to have to process an ever-growing list of dead strategies upon each block.
To prevent problems arising from requiring miners to query data from external sources (namely, inter-miner verification; cost of I/O; also, too much traffic crashing the external server when there are many miners), algorithms cannot request interaction with external services, however, they can read information that has been previously inserted into the blockchain.
This requires that the protocol includes a mechanism to allow third parties to insert external information into the blockchain. It's important that this external information not be available to strategies until after the next block (e.g. it's not available to strategies executing in the same block as the transaction that posts the information); see External Instruction to Strategies, below.
The party who inserted a piece of external information may charge for its usage (either a per-use fee, or by volume (in units of Quantcoin, of course) of the resulting transaction). The fees for this access are added into the strategy execution fee charged to the strategy owner. Clearly, external humans looking at the public blockchain get to consume this information for free, but the prioritized strategies may not do so.
There are many design issues that remain to be worked out.
If the only requirements on miners are to participate in the computing power auction, and to execute the strategies, then couldn't a miner just post a problem to the auction for which they already know the solution? Assuming they bid high enough to win the auction, this would allow the miner to guarantee that they will be the one creating the next block, allowing a 51% attack.
This is perhaps the biggest open issue in the proposal so far.
One idea is to combine the computing power auction requirement with some other requirement. This could be proof-of-stake, traditional meaningless proof-of-work, or some alternative meaningful proof-of-work as in Primecoin. For example, we could have a traditional Bitcoin-style proof-of-work but scaled so that it is expected that the miners will have to expend 10x as much computing power in the auction (working on somebody else's real problem) as they do in the useless proof of work.
Towards a meaningful proof-of-work, one appropriate task could be a search for new, profitable automated trading strategies. This appears to be NP-complete; once a profitable strategy is found, it is relatively quick to doublecheck the profitability of the strategy, but a search through the space of potential strategies probably requires running that same computation many times. However, in absolute terms, it can be quite expensive to check the profitability of a strategy, as it requires simulating running the strategy through all past time. Also, it is easy to create a profitable strategy in retrospect; just make a strategy which doesn't do anything except buy at one hardcoded time that you know would have been a good time to buy. Still, if these difficulties could be overcome, that would be a cool way to do mining.
Two parties who trust each other and who don't want to wait for their transaction to be encoded into the blockchain can agree to a transaction in another venue and then settle the transaction over the blockchain later. Algorithmic traders could make use of this to execute low-latency trades off the blockchain, circumventing the need to publish their stategy.
My guess is that, depending on their particular strategy and situation, some algorithmic traders will choose to do this, but others won't, so Quantcoin will still be of use in motivating these others to publish. So, I don't see this as an open issue that needs to be solved. But i could be wrong.
What actions can these algorithmic trading strategies take? They need to be able to trade something. These trades will probably be the buying and selling of commodities and currencies priced in Quantcoin. But who is their counterparty? It seems like Quantcoin may have to include a protocol for a distributed exchange. This is a research project in itself. Other cryptocurrencies have been working on this, so perhaps it's a solved problem by now, but I haven't been keeping up with this work so I don't know.
One important question is, if you are creating an exchange to trade Quantcoin for something external, how do you deal with fradulent sellers, eg someone who lists an item for sale on the exchange but then doesn't actually send the item? One solution could be: by default, only exchange for other cryptocurrencies which have escrow/multisignature/multiparty capabilities such that a protocol can be created to guarantee the exchange (would it be possible to trustlessly exchange Quantcoin for Bitcoin in this manner? I'm not sure). Another solution could be: allow the strategy-owner to separately specify a list of sellers that they trust (or to subscribe to someone else's public list).
One interesting idea: the Quantcoin network could observe proof-of-burn (sending money to a provably unspendable address associated with this currency) in another cryptocurrency, and mint Quantcoin in exchange, with a price set by auction; this could allow a virtual (one-way) exchange rate between the other currency and Quantcoin to be set (the downside of this is that everyone else's Quantcoin decreases in value when this happens, so why would anyone take the other side of the auction? But this could be a mechanism for setting a fixed permanent floor on Quantcoin's price; i think such a floor could only be set relative to one other currency, or an arbitrage loop could be formed that would destroy Quantcoin).
The computational cost of both problems posted at auction, and strategy algorithms must be easily measurable so that the strategy execution fees can be set.
If a bad choice is made for the 'programming language' of strategies, some strategies could be charged much more expensive strategy execution fees than they deserve.
Another idea is to state the problems in the form of 3-SAT. 3-SAT is an NP-complete problem representation. This means that it can encode problems which take a long time to solve, but for which, when a solution is presented, it can be quickly determined that the solution is correct. It also has the virtue that the maximal computation time required to solve a problem in 3-SAT form can be easily measured by measuring the length of the 3-SAT problem statement (the maximal time grows geometrically with the 3-SAT length).
3-SAT admits a special form for specification of fixed-time algorithms; the Quantcoin protocol has special treatment for 3-SAT instances of that form, calculating their maximal computation time as linearly, rather than geometrically, related to their 3-SAT length. This is not very useful for the computing power auction, but it is useful for the representation of published strategy algorithms in 3-SAT form.
Polynomial-time programs can easily be represented as 3-SAT problems. However, the computation time required to run a polynomial-time program is much less than the maximal computation time required to solve any member of the family of 3-SAT problems of the same length as that program's 3-SAT encoding, so if we did it that way, there would be unnecessary pressure to find trading algorithms with short 3-SAT encodings.
However, perhaps 3-SAT can be saved in a simple manner. The encoding of a fixed-time algorithm (rather, combinatorial circuits) into 3-SAT is simple to do and easy to recognize. We simply specify a special discount pricing (linear in the number of clauses, rather than exponential) for 3-SAT instances that follow this special form. Miners then detect whether a 3-SAT instance is of that form, and if it is, they execute it in a special manner optimized for this.
This isn't quite good enough; we need a straightforward format for encoding fixed-length loops into 3-SAT and being charged appropriately (that is, a 3-SAT special form for algorithm whose running time is polynomial in the length of the 3-SAT instance). I don't know off the top of my head if this has been done, but bet it has, and if not, I bet it's possible.
Compared to EVM, 3-SAT is simpler but also less practical. Is there any reason to use it rather than EVM? One reason is that you wouldn't really want to use a network of miners to run a conventional algorithm; because every miner must run the algorithm, but only one gets paid, they price the buyer gets charged will probably be more than the price to rent a single machine. But running an NP-complete algorithm is different; there is no known way to solve, in general, such problems besides brute force search; but once a solution is found, it can be easily verified. In this case, the network of miners is doing something similar to what you would do anyways if you had a small cluster of computers available; you'd tell each computer to semi-randomly explore the search space looking for a solution (if you controlled the whole cluster, you might still be able to make further gains by having the computers explore non-overlapping regions of search space; but if the search space is very large compared to the number of computers, this might not matter much, and in some cases any gains might be offset by the overhead of keeping each computer in the assigned space).
However, it's possible to get 'the best of both worlds' by simply specifying that the EVM should be used to define, not a program to be run once, but rather a verifier for NP problems; that is to say, the program given will accept and input and will return a single boolean value saying whether or not that input represents an acceptable solution to the problem. The miners then have the task of trying various inputs, in search of one which the program accepts.
This scheme would have the additional virtue of stimulating development of heuristics for searching in the kinds of NP tasks defined by verifiers of real, practical problems that people are willing to pay for. For example, a miner with clever heuristics for planning problems might have an advantage when a planning problem is posed to it. Such a miner might inspect the problems posed in the auction, detect those to which it can apply its heuristics, and submit an 'ask' (in the computing power auction) lower than other miners for the completion of those particular problems, driving down the price for the buyer (bidder in the computing power auction).
Bitcoin puts a ceiling on the difficulty of proof-of-work problems in terms of the difficulty of problems that have already been solved. We can't do that here, because we have to worry about a bidder submitting a seemingly-difficult-but-actually-easy instance of a problem, for example, a problem that they generated by starting with the solution; so the theoretical difficulty of auction problems that were solved in the past may be much harder than the problems actually were.
But we also have to worry about a bidder posting a problem that is too hard, for example, one that with high probability won't be solved in the lifetime of the universe. So, we need some mechanism to ensure that a problems of extreme difficult won't crowd out others.
One thing we could do is, instead of having the entire network working on one problem at a time, allow any miner to work on any problem at auction that they want. In this case there seems to be no point to having the miners submit 'asks' for the problems, so there are only bids. Here, though, we still have the full problem of someone submitting a problem that they know the answer to, and then submitting the solution.
Another thing we could do is, force the entire network to be working on the problem with the biggest difference between bid and (miner-weighted) ask (proof-of-burn), but allow this choice to change even before the problem has been solved. Of course, we'd need mini-blocks to record changes in bids and asks while the real block is being worked on; perhaps a conventional proof-of-stake or proof-of-work system could be used for these.
A related problem is, if bids and asks are 'sticky', then what if someone way underbids? Then it could become temporarily unprofitable to mine, and miners could drop out, leading to the current block never being completed. So, there must be some way for bids to expire or to be removed.
If we are allowing external parties to place information into the blockchain, then couldn't someone publish a strategy that just says, "When I say X, buy Y", and then control it externally by placing the statement X into the blockchain whenever they want to buy? This would defeat the purpose of publishing strategies.
Yes, and in fact, it would be hard to prevent this even without allowing the posting of external information, because we have to give a strategy must have some sort of information about market conditions, and the strategy owner could steganographically encode their instructions into the market. However, it's not a problem, because strategies only have access to information encoded in the prior block, not in the same block as themselves. So, a person doing this would effectively lose the priority advantage of a published strategy; they may as well just issue normal user transactions themselves.
Quantcoin is currently just an idea by Bayle Shanks. No one is currently working on implementing it, but if you would like to talk about related stuff, or would like to work on it, please email me at