User:Dbabbitt/Sandbox/Draft List of unsolved problems in crypto-economy design Article

This article is a list of unsolved problems in crypto-economy. A problem in crypto-economy is considered unsolved when an expert in the field considers it unsolved or when several experts in the field disagree about a solution to a problem.

Blockchain Scalability

• Can a blockchain design that provides a fundamental improvement over the current model be created where every node must process every transaction?
• Can a proof-of-work algorithm be created that is resistant to mining centralization?

One of the largest problems facing the cryptocurrency space today is the issue of scalability. It is a well-known fact that, in its current form, the Bitcoin network can only process 7 transactions per second. On a fundamental level, this is not strictly true; simply by changing the block size limit parameter, Bitcoin can easily be made to support 70 or even 7000 transactions per second. However, if Bitcoin does get to that scale, we run into a problem: it becomes impossible for the average user to run a full node, and full nodes become relegated only to that small collection of businesses that can afford the resources. Because mining only requires the block header, even miners can (and in practice most do) mine without downloading the blockchain.

The main problem with this is trust: if there are only a few entities capable of running full nodes, then those entities can conspire and agree to give themselves a large number of additional bitcoins, and there would be no way for other users to see for themselves that a block is invalid without processing an entire block themselves. Although such a fraud may potentially be discovered after the fact, power dynamics may create a situation where the default action is to simply go along with the fraud (and authorities can create a climate of fear to support such an action) and there is a coordination problem in invalidating the fraudulent chain. Thus, in the limit, Bitcoin with 7000 transactions per second has security properties that are essentially similar to a centralized system like Paypal, and what we want is a system that handles 7000 TPS with higher levels of decentralization.

Ideally, a blockchain design should exist that works, and has similar security properties to Bitcoin with regard to 51% attacks, that functions even if no single node processes more than 1/n of all transactions for an arbitrarily high n. This would allow the blockchain architecture to process an arbitrarily high number of TPS without centralization concerns.

Transaction-sublinear supernodes

• Can a blockchain design be created that maintains Bitcoin-like security guarantees, but where the maximum size of the most powerful node that needs to exist for the network to keep functioning is sublinear in the number of transactions?

Assumptions

• There exist a large number of miners in the network
• Miners may be using specialized hardware or unspecialized hardware. Specialized hardware should be assumed to be more powerful than unspecialized hardware by a large (eg. 10000) constant factor at specific tasks.
• Ordinary users will be using unspecialized hardware
• Attackers exist, but they altogether control less than 33% of the network

Requirements: Level 1

• If N is the number of transactions, a transaction made should reach the point where a double spend attempt has probability 1-t of failure in O(log(N)*log(T)) time.
• The largest honest node that needs to exist should have size sublinear in N. That is to say, as N grows the portion of transaction data that each node needs to store should shrink to an arbitrarily small fraction.

Requirements: Level 2

• No node should need to have more than O(sqrt(N)) resources.
• Create a proof-of-work algorithm that is resistant to mining centralization

Fair PoW

One of the key elements in the Bitcoin algorithm is the concept of "proof of work". In any Byzantine-fault-tolerant system, the security level is often defined as the minimum percentage of hostile nodes - for example, in the context of secret sharing, the Berlekamp-Welch algorithm with 2x redundancy is guaranteed to provide the correct output assuming that the total number of hostile nodes does not exceed 25% of the network, and in the context of Bitcoin mining the requirement is that the size of the set of honest nodes exceeds the size of any individual hostile coalition. However, all of these security guarantees have one important qualification: there must be some way to define what an individual node is. Before Bitcoin, most fault-tolerant algorithms had high computational complexity and assumed that the size of the network would be small, and so it would be possible to count each node individually. With Bitcoin, however, nodes are numerous, mostly anonymous, and can enter or leave the system at any time. Unless one puts in careful thought, such a system would quickly run into what is known as a Sybil attack, where a hostile attacks simply creates five times as many nodes as the rest of the network combined, whether by running them all on the same machine or rented virtual private server or on a botnet. In order to prevent this kind of attack, the only known solution is to use a resource-based counting mechanism. For this purpose, Bitcoin uses a scheme known as proof-of-work, which consists of solving problems that are difficult to solve, but easy to verify. The weight of a node in the consensus is based on the number of problem solutions that the node presents, and the Bitcoin system rewards nodes that present such solutions ("miners") with new bitcoins and transaction fees.

Bitcoin's proof of work algorithm is a simple design known as Hashcash, invented by Adam Back in 1995. The hashcash function works as follows:

def hashcash_produce(data,difficulty):

  nonce = 0
  while sha256(data + str(nonce)) > 2**256 / difficulty:
      nonce += 1
  return nonce

def hashcash_verify(data,nonce,difficulty):

  if sha256(data + str(nonce)) <= 2**256 / difficulty:
      return True
  else:
      return False

Originally, the intent behind the Bitcoin design was very egalitarian in nature. Every individual was intended to participate in the mining process from their own desktop computer, and the result was to produce both a network that is highly decentralized and resistant to any attempt at control and a distribution mechanism that is highly egalitarian in nature. And for the first one and a half years of Bitcoin's existence, that is indeed how the system worked. In the summer of 2010, however, developers released a Bitcoin miner that takes advantage of the massive parallelization offered by the graphics processing unit (GPU), mining about 10-50 times more efficiently than CPUs. Over the course of about nine months, CPU mining became completely unprofitable. At that point, an inequality started to emerge - not many people have GPUs with powerful graphics cards, so the revenue that could be earned by an average person from mining dwindled, and dedicated hobbyist mining operations, purchasing a large quantity of graphics cards and plugging them into a powerful computer, began to grow. Thus, Bitcoin mining remained accessible to individuals, but now increasingly primarily to individuals with money and interest in purchasing hardware. In 2013, the Bitcoin mining economy took a further turn. A number of companies, led by Avalon, ASICMiner and Butterfly Labs, started producing devices known as "application-specific integrated circuits" (ASICs) - chips designed in silicon with the sole purpose of Bitcoin mining in mind. These devices were once again 10-50 times more efficient than GPUs, and after less than six months GPU mining also became unprofitable. And that is where we are now: the only way to mine is to either purchase an ASIC from a specialized ASIC manufacturing company and run it at home or simply purchase a "mining contract" as an investment, where the company produces and runs the devices in-house and returns to the contract purchasers a share of the revenue in exchange for providing the cost of manufacturing the device upfront. The first option is arguably less efficient, and thus only exists because of the hobbyist nature of the current Bitcoin community; once large purely profit-oriented players start to dominate, we have no guarantees that mining will not further centralize into a few large corporations with high barriers to entry.

Human-dominated mining

• Can two functions, PoWProduce(data,diff) -> nonce and PoWVerify(data,nonce,diff) -> 0/1, be created to serve as alternatives to Hashcash such that it is economically unattractive to produce an ASIC for PoWProduce?

Requirements, Level 1:

• PoWProduce must have expected runtime linear in diff
• PoWVerify must have expected runtime at most polylogarithmic in diff
• PoWProduce must not be superlinear in computational power or time; that is to say, the expected number of successful PoWProduce computations for a node with N dollars worth of hardware after t seconds should be bounded by kNt for some k. Furthermore, at a difficulty level which assumes $1 billion worth of hardware in the network producing one successful PoWProduce computation per minute, $1000 worth of hardware should be able to provide 5000k successful PoWProduce computations after 10 seconds
• It should be rigorously shown that either (1) ASICs are not expected to be more than 10x more efficient than generic CPU/GPU hardware per dollar spent on electricity and production with initial and fixed costs infinitely amortized at a 5% discount rate and assuming a firm size of $100 billion, or (2) any ASIC for the system can be simultaneously used as an improved general-purpose or semi-general-purpose computational device such that if this technology were to be integrated into the mainstream the ASIC would not be more than 10x more efficient than generic CPU/GPU hardware.

Requirements, Level 2

• Same as level 1, except substituting CPU/GPU with CPU only.
• Create a proof-of-work algorithm where the work is made up of independently useful computation

Useful PoW

• Can a proof-of-work algorithm be created where the work is made up of independently useful computation?

One major economic issue, often pointed out by detractors of Bitcoin, is that the proof of work done in the Bitcoin network is essentially wasted effort. Miners spend 24 hours a day cranking out SHA256 (or in more advanced implementations Scrypt) computations with the hopes of producing a block that has a very low hash value, and ultimately all of this work has no value to society. Traditional centralized networks, like Paypal and the credit card network, manage to get by without performing any proof of work computations at all, whereas in the Bitcoin ecosystem about a million US dollars of electricity and manufacturing effort is essentially wasted every day to prop up the network.

One way of solving the problem that many have proposed is making the proof of work function something which is simultaneously useful; a common candidate is something like Folding@home, an existing program where users can download software onto their computers to simulate protein folding and provide researchers with a large supply of data to help them cure diseases. The problem is, however, that Folding@home is not "easy to verify"; verifying the someone did a Folding@home computation correctly, and did not cut corners to maximize their rounds-per-second at the cost of making the result useless in actual research, takes as long as doing the computation oneself. If either an efficiently verifiable proof-of-correct-computation for Folding@home can be produced, or if we can find some other useful computation which is easy to verify, then cryptocurrency mining could actually become a huge boon to society, not only removing the objection that Bitcoin wastes "energy", but even being socially beneficial by providing a public good.

Note that there is one major concern with this approach that has been identified: if done wrong, it can potentially reduce the cost of an attack on the network. If the useful PoW is useful in such a way that it is sometimes economically viable for certain very large entities to perform the computation even without the currency incentive, then those entities have an incentive to launch consensus takeover attacks ("51% attacks") against the network at no cost, since they would be performing the computations anyway. One simple, though crude and imperfect, way of addressing this problem is to make the PoW a half-and-half mix between useful and useless, making sure that every entity would need to pay at least 50% of the intended cost to launch an attack, and another approach is to make the computation a "pure" public good such that no individual entity derives a significant benefit from it. Solutions should include a rigorous analysis of this issue.

Requirements

• PoWProduce must have expected runtime linear in diff
• PoWVerify must have expected runtime at most polylogarithmic in diff
• PoWProduce must not be superlinear in computational power or time; that is to say, the expected number of successful PoWProduce computations for a node with N dollars worth of hardware after t seconds should be bounded by kNt for somek. Furthermore, at a difficulty level which assumes $1 billion worth of hardware in the network producing one successful PoWProduce computation per minute, $10000 worth of hardware should be able to provide 50000k successfulPoWProduce computations after 10 seconds
• PoWProduce must produce a public good, such that the total value to everyone of the public good produced is greater than the cost of all resources invested into the mining process.

Discussed in:

• Laurie, B., & Clayton, R. (2004, September). “Proof-of-Work” proves not to work; version 0.2. In Workshop on Economics and Information, Security.
• Wash, R., & MacKie-Mason, J. K. (2007, August). Security when people matter: structuring incentives for user behavior. In Proceedings of the ninth international conference on Electronic commerce (pp. 7-14). ACM.
• Create an incentive-compatible mechanism for constructing a cryptographic asset whose value is expected to be reasonably stable

Price Stabilization

One of the main problems with Bitcoin is the issue of price volatility. The value of a bitcoin often experiences very large fluctuations, rising or falling by as much as 25% in a single day and 3x in a month. The main economic reason behind this is that the supply of bitcoins is fixed, so its price is directly proportional to demand (and therefore, by efficient market hypothesis, the expected discounted future demand), and demand is very unpredictable. It is not known if Bitcoin will be simply a niche payment method for transcations requiring a high degree of privacy, a replacement for Western Union, a mainstream consumer payment system or the reserve currency of the world, and the expected value of a bitcoin differs over a thousandfold between these various levels of adoption. Furthermore, the utility of the Bitcoin protocol is heavily dependent on the movements of the Bitcoin price (ie. people are interested in Bitcoin more if the price is going up), creating a positive feedback loop, which has arguably been responsible for both Bitcoin's great meteoric rises and its many-month-long periods of rapid decline.

To solve this problem, there are generally two paths that can be taken. The first is to have the network somehow detect its current level of economic usage, and have a supply function that automatically increases supply when usage increases. This reduces uncertainty; even though the expected future level of adoption of the protocol may have a variance of 10-100x, the circumstance where adoption increases 100x will also have 100x more supply and so the value of the currency will remain the same. There is a problem that if usage decreases there is no way to remove units from circulation, but even still the lack of upward uncertainty should reduce upward volatility, and downward volatility would also naturally reduce because it is no longer bad news for the value of the currency when an opportunity for increased usage is suddenly removed. Furthermore, in the long term the economy can be expected to grow, so the zero-supply floor may not even ever be reached in practice. The problem is that measuring an economy in a secure way is a difficult problem. The most obvious metric that the system has access to is mining difficulty, but mining difficulty also goes up with Moore's law, and there is no known way to estimate the impact of Moore's law alone and so the currency cannot know if its difficulty increased by 10x due to better hardware, a larger user volume or a combination of both. Other metrics, such as transaction count, are potentially gameable by entities that want the supply to change in a particular direction (generally, holders want a lower supply, miners want a higher supply).

Another approach is to attempt to create a currency which tracks a specific asset, using some kind of incentive-compatible Schelling-point scheme to feed price information about the asset into the system in a decentralized way. This could then be combined with a supply function mechanism as above, or it can be incorporated into a zero-total-supply currency system which uses debts collateralized with other cryptographic assets to offset its positive supply and thus gain the ability to grow and shrink with changes to usage in either direction. The problem here is constructing the scheme in such a way that there is no incentive for entities to feed in false price information in order to increase or decrease the supply of the asset in their favor.

Cryptographic assets

• Can an incentive-compatible mechanism for constructing a cryptographic asset be created whose value is expected to be reasonably stable?
• Can an incentive-compatible mechanism for constructing a cryptographic asset be created whose value specifically tracks an arbitrary asset or basket of commodities?

Assumptions

• No coalitions above 25% are possible
• Over 75% of the agents (weighted by resources) are rational and interested in maximizing profits
• At least one honest and altruistic party exists
• Financial markets offering 10x leverage on any asset exist, but no higher

Requirements: Level 1

• The expected root-mean-square daily change in the logarithm of the price of the asset should be less than 50% of that of Bitcoin under similar conditions
• The expectation analysis should take into account black swan risks (ie. systems where the variance is 0% 99% of the time but 10x in a day the other 1% of the time are unacceptable)
• The submitters are expected to come up with a model, including parameters such as short-term-consumption purchases, medium-term purchases, speculative purchases, positive and negative media, adoption and regulatory events, irrational actors and actors with political motives, show that their model well fits the history of Bitcoin and potentially major altcoins without overfitting, and show that under the model the other two requirements hold

Requirements: Level 2

• The asset should be guaranteed to maintain a value within 10% of an arbitrary cryptographic or real-world asset for which price information is easily accessible given the economic assumptions.
• Can an incentive-compatible pure or nearly-pure proof-of-stake currency be created?

Other problems

• Can a proof-of-excellence distribution/mining mechanism be created that is expected to be human-dominated and reasonably egalitarian?
• Can a proof-of-work distribution/mining mechanism be created that is expected to be competitively mine-able via unskilled human labor?
• Can a high-accuracy distributed timestamp consensus system be created?
• Can a Merkle-tree-like data structure be created with a succinct node addition/removal/modification proof?
• Can a method of constructing an arbitrary proof-of-computation be created that is semi-succinctly verifiable?
• Can an efficient indistinguishability obfuscation algorithm {note|What defines efficiency?} be created?

External links

• Major unsolved problems in theoretical crypto-economy on StackExchange.
• Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405.
• Challenges for Theoretical crypto-economy (Broken link)
• The Open Problems Project – open problems in computational geometry and related fields.
• The RTA list of open problems – open problems in rewriting.
• The TLCA List of Open Problems – open problems in area typed lambda calculus.

* crypto-economy