<

Ethereum’s Vitalik Buterin: 16 difficult problems in cryptocurrency from 2014 and status quo

Ethereum News
By Congecko News

Back to 2014, Vitalik Buterin, a Russian-Canadian programmer, especially known as co-founder of Ethereum, presented a list of hard problems in math, computer science, and economics that he thought was important for the development of cryptocurrency industry.

In a recent tweet, he introduced an article that talked about 16 problems from 2014 and sees where they are standing on each one, additionally, including new hard problems of 2019.

The matters are divided into three types: (i) cryptographic, expected to be solvable with purely mathematical techniques (ii) consensus theory, mostly improvements to proof-of-work and proof-of-stake and (iii) economic, create structures involving incentives given to different participants, and the application layer more than the protocol layer. We can see a substantial advancement in all kinds though some more than others.

Cryptographic problems

Cryptography or cryptology is the practice and study of techniques for secure communication in the presence of third parties called adversaries. The main objective is to develop and analyze protocols that prevent third parties or the public from reading private messages; various aspects of information security such as data confidentiality, data integrity, authentication, and non-repudiation are central to modern cryptography, as described by Wikipedia. The following are some of the difficult issues and the status quo of cryptography in crypto:

1. Blockchain Scalability

It is one of the largest issues in crypto space. If only having some entities that can run full nodes, then they could conspire and consent to add themselves a large number of bitcoin, and there no way other users know about an invalid block without processing an entire block themselves.

Problem: make a blockchain design that maintains security guarantees like Bitcoin, while existing the maximum size of the most powerful node for the network to keep functioning that is basically the number of transactions.

Status: Great progress in theory, but waiting for more real-world evaluation

So far, the company has had huge progress theoretical in Scalability. Five years ago, mostly no one knew about Sharding – now sharding designs are common. Besides Ethereum 2.0, many other research papers such as OmniLedger, LazyLedger, Zilliqa are come out every month.

According to Vitalik Buterin, “it will further progress”. He also added they have had lots of techniques that allow groups of validators to securely come to a consensus on much more data than an individual validator can process, as well as allow clients to indirectly verify the full validity and availability of blocks even under 51% attack conditions.

However, sharded blockchains have still not been had in real operation. About theory, it is easy to say that there are mainly disputes about details remaining, challenges of the stability of sharded networking, and mitigating risks of centralization,… But we can not solve the remaining challenges just by thinking.

Here is one of the most important technologies:

Vitalik Buterin: 16 Difficult Problems in Cryptocurrency From 2014 and Status

Vitalik Buterin, co-founder of Ethereum

2. Timestamping

Problem: make a compatible system that incentive distribution, though it is a coating on top of a blockchain or its own blockchain, which helps to maintain current time with high accuracy.

In a normal distribution, all legal users have clocks with some “real” time and a standard deviation of 20 seconds, the solution is permitted to base on the existing concept “N nodes”.

Status: Complete some progress

Ethereum has really survived well with a 13-second block time without having particularly advanced timestamping technology. It only uses a simple technique whereby a client does not accept a block whose stated timestamp is earlier than the client’s local time. However, this not be tested under serious attacks.

The recent proposal about network-adjusted timestamps is trying to improve the status quo by allowing the customer to define the consensus on the time in the case where the client does not locally know the current time to high accuracy; this not yet tested. In general, timestamping is not currently remarkable with perceived research challenges; this maybe will change once more proof-of-stake chains appear online like real live systems.

3. Arbitrary Proof of Computation

Problem: make programs POC_PROVE(P,I) -> (O,Q) and POC_VERIFY(P,O,Q) -> { 0, 1 } such that POC_PROVE runs program P on input I and returns the program output O and the proof-of-computation Q and POC_VERIFY takes P, O and Q and outputs whether or not Q and O were legitimately produced by the POC_PROVE algorithm using P.

Status: Good both theoretical and practical progress

Basically, this is to build a SNARK (or STARK, or SHARK, or…). And Ethereum has completed it. NARK is increasingly well understood and has even been used in many blockchains today (e.g Tornado.cash on Ethereum). Moreover, SNARKs are extremely useful, both as a privacy technology (see Zcash and tornado.cash) and as a scalability technology (see ZK Rollup, STARKDEX and STARKing erasure-coded data roots).

On the other hand, it is still to have challenges. For instance, making Arithmetization-friendly hash functions is a big one and another is efficiently proving random memory accesses. Special, the question about, whether the O(n * log(n)) blow up in prover time is a fundamental limitation, is still unsolved. Further, it also having ever-present risks that the existing schemes have bugs. All in all, the problems are in the details, not the fundamentals.

4. Code Obfuscation

Problem: come up with a way to “encrypt” a program for that the encrypted program would still provide the same outputs for the same inputs, but “internals” of the program be hidden. For example, a program containing a private key where the program only allows the private key to sign certain messages.

Status: Slow progress

A remedy to code obfuscation would be very useful for blockchain protocols. The use cases are subtle because one must against the possibility that an on-chain obfuscated program will be copied and run in an environment different from the chain itself.

One thing that interests Buterin is the ability to remove the centralized operator from collusion-resistance gadgets by replacing the operator with an obfuscated program that contains some proof of work, which makes it very expensive to run more than once with different inputs in trying to determine individual participants’ actions.

Unfortunately, it is still a hard problem. The working is continuing to attack the problem, one side trying to reduce the number of assumptions on mathematical objects that we do not know practically exist and another side trying to make practical implementations of the desired mathematical objects. But all of those paths are quite far from creating something viable and secure.

5. Hash-Based Cryptography

Problem: make a signature algorithm without security assumption, but the random oracle property of hashes that maintains 160 bits of security against classical computers (ie. 80 vs. quantum due to Grover’s algorithm) with optimal size and other attributes.

Status: Complete Some progress

Having been 2 strands of progress on this since 2014, including SPHINCS and STARKs.

Whereby, SPHINCS, a “stateless” (using it many times not require remembering information like a nonce)signature scheme, was issued soon after this list was published and provides a purely hash-based signature scheme of size around 41 kB.

Besides, with STARKs also can create signatures of similar size based on them. In fact that not only signatures but also general-purpose zero-knowledge proofs.

The main problem with hash-based cryptography that not yet solved is aggregate signatures, like what BLS aggregation makes possible. It’s known that they just make a STARK over many Lamport signatures, but not efficient; a more efficient plan would be welcome.

Consensus theory problems

Consensus theory is a social theory that holds a particular political or economic system is a fair system, and that social change should take place within the social institutions provided by it. Consensus theory contrasts sharply with conflict theory, which holds that social change is only achieved through conflict, as described by Wikipedia. The following are some of the difficult issues and the status quo of consensus theory in crypto:

6. ASIC-Resistant Proof of Work

Problem: create a proof-of-work algorithm relies on a type of computation that is very difficult to specialize, is one approach to solve the problem.

Status: Solved as far as they can

Roundly six months after the “hard problems” of the co-founder was published, Ethereum dealt with its ASIC-resistant proof of work algorithm: Ethash.

Ethash is mentioned as a memory-hard algorithm. In theory, that random-access memory in regular computers is well-optimized already, therefore, it is difficult to improve on for specialized applications. To achieve ASIC resistance, Ethash allows memory access to the dominant part of running the PoW computation.

Although it was not the first memory-hard algorithm, it did add one innovation: it uses pseudorandom lookups over a two-level DAG, allowing for two ways of evaluating the function.

Ethash has proven significantly successful at ASIC resistance. After three years and billions of dollars of block rewards, ASICs do exist at best 2-5 times more power and cost-efficient than GPUs. Additionally, ProgPoW has been proposed as an alternative, as most of the people said that ASIC-resistant algorithms will absolutely have a limited lifespan and that ASIC resistance has downsides because it makes 51% attacks cheaper (eg. see the 51% attack on Ethereum Classic).

It is believed that PoW algorithms can supply a medium level of ASIC resistance, however, such resistance is limited-term and both ASIC and non-ASIC PoW have weaknesses; in the long term, proof-of-stake is the better choice for blockchain consensus.

7. Useful Proof of Work

Problem: make the proof-of-work function something that is concurrently useful. For example, Folding@home, a 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.

Status: Probably not realizable, with one exception

The proof-of-work algorithm requires many properties:

  • Hard to compute
  • Easy to verify
  • Not depend on large amounts of external data
  • Can be efficiently computed in small “bite-sized” chunks

Unfortunately, there are not many useful computations that preserve all of these properties, and most computations that do have all of those properties are only “useful” for a far too short time to build a cryptocurrency around them.

On the other hand, having a possible exception: zero-knowledge-proof generation. Aspects of blockchain validity in Zero-knowledge proofs are difficulty compute and easy verify.

Zero-knowledge proofs of blockchain validity bring great value to users of the blockchain, significantly assist in improving the blockchain’s safety and scalability, additionally, users can substitute the need to verify the chain directly. Coda is doing this, despite a simplified blockchain design that is heavily optimized for provability.

8. Proof of Stake

Problem: Another way to solving the mining centralization problem is to annul mining totally and move to other mechanisms for counting the weight of each node in the consensus. To date, the most popular solution under discussion is “proof of stake” – meaning that instead of seeing the consensus model as “one unit of CPU power, one vote” it becomes “one currency unit, one vote”.

Status: Good progress about theory, waiting for more real-world evaluation

To maintain economic security, nodes have to a checkpoint extra-protocol when they sync for the first time, and again if they go offline for more than a few months. While lots of PoW supporters still cling to PoW because the “head” of the chain can be discovered with the only data coming from the blockchain client software itself – a trusted source; on the other hand, PoS advocate willing to see the added trust requirements as not being large. Therefore, the way to proof of stake through long-duration security deposits became clear.

Currently, the majority of interesting consensus algorithms are basically similar to PBFT, but supersede the fixed set of validators with a dynamic list that anyone can join – by sending tokens into a system-level smart contract and time-locked withdrawals. These algorithms get “economic finality” in many cases by penalizing validators that are caught performing actions when violating the protocol in certain ways.

Remaining arguments about proof of stake, also in Vitalik Buterin’s view, is optimizing the economic incentives and further formalizing the strategy for responding to 51% attacks, additionally, the Casper CBC spec still use for concreting efficiency improvements.

Some special algorithms of the company so far:

9. Proof of Storage

Problem: The third way for this problem is to use a scarce computational resource, besides computational power or currency. There are 2 main alternatives that have been proposed are storage and bandwidth.

Proof of storage, something that definitely can be done computationally. One of the advantages of its is absolutely ASIC-resistant – the kind of storage that has in hard drives is already close to optimal.

Status: many progress in theoretical, needing more real-world evaluation.

Chia and File coin are 2 blockchains that have planning to use proof of storage protocols. Meaning that these algorithms have not been tested in the wild. Their own main concern is centralization: will these algorithms actually be affected by smaller users using spare storage capacity, or will they be dominated by large mining farms?

Economics

Cryptoeconomics refers to the study of economic interaction in adversarial environments. The underlying challenge is that in decentralized P2P systems, that do not give control to any centralized party, one must assume that there will be bad actors looking to disrupt the system. Cryptoeconomics approaches combine cryptography and economics to create robust decentralized P2P networks that thrive over time despite adversaries attempting to disrupt them. The cryptography underlying these systems is what makes the P2P communication within the networks secure, and the economics is what incentivizes all actors to contribute to the network so that it continues to develop over time, cited from the book Token Economy by Shermin Voshmgir. The following are some of the difficult issues and the status quo of economics:

10. Stable-value crypto assets

Problem: to Bitcoin, price volatility is one of the largest problems. So, the aim here is to construct a cryptographic asset with a stable price.

Status: Complete Some progress

After a 93% drop in the value of its underlying collateral asset (ETH), MarketDAO is surviving and has held stable for nearly two years with more than $100 million in DAI issued. It has become a pillar for the Ethereum ecosystem, further, many Ethereum projects have or are integrating with it.

Although the MakerDAO system has survived tough economic conditions in 2019, that is not the toughest that could happen. In the past, Bitcoin has downed to 75% over the course of two days; the same may happen to Ether or any other collateral asset someday.

Another larger challenge is the stability of MakerDAO-like systems that depend on some underlying oracle scheme. It has had different attempted at oracle systems (see #16), but the jury is still out on how well they can hold up under large amounts of economic stress.

In present, the collateral controlled by MakerDAO has been lower than the value of the MKR token; if this relationship reverses MKR holders may have a collective incentive to try to “loot” the MakerDAO system. There are ways to try to protect against such attacks, but not been yet tested in real life.

11. Decentralized Public Goods Incentivization

Problem: “Public goods” is one of the challenges of economic systems generally. Most problems to this challenge so far have involved centralization Additional Assumptions and Requirements.

Status: Complete Some progress

The matter of funding public goods is often to be split into 2 problems: the funding problem (where to get funding for public goods from) and the preference aggregation problem (how to specify what is a genuine public good). This problem focuses specifically on the former, assuming the latter is solved (see the#14).

Generally, having not big new breakthroughs here. There are 2 principal kinds of solutions: First, trying to elicit individual contributions – give people social rewards for doing so, such as charity through marginal price discrimination and the anti-malaria donation badges on Peepeth; Second, collecting funds from applications that have network effects.

In blockchain land there are several options can to do this:

  • Launching coins
  • Getting a portion of transaction fees at the protocol level (eg. through EIP 1559).
  • Getting a portion of transaction fees from some layer-2 application (eg. Uniswap)
  • Getting a portion of other kinds of fees (eg. ENS registration)

12. Reputation systems

Problem: design a formalized fame system that includes a score rep(A,B) -> V where V is the fame of B from viewpoint of A. It is mechanism for determining the probability that one party can be trusted by another, and a mechanism for updating the reputation given a record of a particular open or finalized interaction.

Status: Slow progress

From 2014, it has not had much work on reputation systems, maybe the best is the use of token curated registries to create curated lists of trustable entities/objects, such as the Kleros ERC20 TCR – a token-curated registry of legitimate ERC20 tokens.

Reputation systems of the subjective variety have not actually been tried perhaps due to not enough information about the “social graph” of people’s connections to each other that has already been published to a chain in some form. If such information starts to exist for other reasons, then subjective reputation systems may become more popular.

13. Proof of excellence

Problem: This is an interesting solution but largely unexplored, specific to the problem of [token] distribution (there are reasons why it cannot be so easily used for mining) is that uses tasks that are socially useful but require original human-driven creative effort and talent. For instance, coming up with a “proof of proof” currency that rewards players for coming up with mathematical proofs of certain theorems.

Status: Don’t have any progress, the problem is largely forgotten

Instead, the main alternative approach to token distribution popularly is Airdrops, normally, tokens are distributed at launch either proportionately to existing holdings of some other token or based on some other metric (eg. as in the Handshake airdrop).

Verifying human creativity directly has not really been tried, and with recent progress on AI the problem of creating a task that only humans can do but computers can verify may well be too difficult.

14 [sic]. Decentralized contribution metrics

Problem: Unfortunately, incentivizing the production of public goods is not the only problem that centralization solves. The other problem is defining which public goods are worth producing in the first place and what extent a particular effort actually accomplished the production of the public good. This challenge deals with issue #16.

Status: Complete Some progress, having some change in focus

Recently, determining the value of public-good contributions does not try to separate determining tasks and determining the quality of completion because of in practice the two are difficult to separate.

Fortunately, having some great progress on this, particularly in the discovery of quadratic funding. It is a mechanism where individuals can make donations to projects, and then based on the number of people who donated and how much they donated and to use a formula calculate how much they would have donated if they were perfectly coordinated with each other (ie. took each other’s interests into account and did not get prey to the tragedy of the commons). Moreover, see #11 for where the central pool funding could come from.

Pay attention to that this mechanism focuses on satisfying the values of some community, not on satisfying some given goal regardless of whether or not anyone cares about it. Because the problem of the value is complexity, this approach is likely to be much more robust to the unknown.

On the other hand, Quadratic funding has even been tried in real life with considerable success in the recent Gitcoin quadratic funding round. It also has some significant progress on improving quadratic funding and similar mechanisms; especially pairwise-bounded quadratic funding to mitigate collusion. Besides, also having worked on the specification and implementation of bribe-resistant voting technology, preventing users from proving to third parties who they voted for to help prevent prevents many kinds of collusion and bribe attacks.

Sybil Ethereum

15 [sic]. Anti-Sybil systems

Problem: create a “unique identity system” – the system for generating tokens that prove that identity is not part of a Sybil attack… but Ethereum would like to have a system that nicer and more egalitarian features than “one-dollar-one-vote”; arguably, one-person-one-vote would be ideal.

Status: Complete Some progress

It has had quite a few attempts at solving the unique-human problem. Additionally, with the growing interest in techniques like quadratic voting and quadratic funding, the need for some kind of human-based anti-Sybil system continues to grow. It is hoped that the ongoing development of these techniques and new ones can come to meet it.

Some attempts that come to mind include:

16. Decentralized success metrics

Problem: bring out and perform a decentralized method for measuring numerical real-world variables that should be able to measure anything that humans can currently reach a rough consensus on (price of an asset, temperature, global CO2 concentration). This is recently called “the oracle problem”.

Another challenge is to people want to base on these systems to guide transfers of quantities of assets larger than the economic value of the system’s native token.

Status: Complete Some progress

Augur, the largest known instance of a decentralized oracle running, has processed outcomes for millions of dollars of bets. Another example is Kleros TCR, token curated registries. However, these systems still have not tried in a real-world test of the forking mechanism (search for “Subjectivocracy” here) either due to a highly controversial question or due to an attempted 51% attack; also having research on the oracle problem happening outside of the blockchain space in the form of the “peer prediction” literature; see here.

About the second challenge, in theory, with these conditions, have the incentive to collude to give wrong answers to steal the funds. In such a case, the system will fork and the original system token can become valueless, but the original system token holders will still get away with the returns from whatever asset transfer they misdirected. Stablecoins (see #10) is a special serious case of this.

A way to solve this problem would be a system that assumes that altruistically honest data providers do exist, and creating a mechanism to identify them, and only allowing them to boot slowly so that if malicious ones start getting voted in the users of systems that rely on the oracle can first complete an orderly exit. In all cases, more development of oracle tech is very much an important problem.

Some New Problems

In 2019, the list of these hard problems will be a continuation of the above problems but having significant changes in emphasis, also some important new problems are added. Here are some main options:

  1. Cryptographic obfuscation: like #4
  2. Continuing working on post-quantum cryptography: both hash-based and based on post-quantum-secure “structured” mathematical objects, eg. elliptic curve isogenies, lattices…
  3. Anti-collusion infrastructure: ongoing work and refinement of https://ethresear.ch/t/minimal-anti-collusion-infrastructure/5413, including adding privacy against the operator, multi-party computation in a maximally practical way, etc.
  4. Oracles: like #16, but replace the emphasis on “success metrics” to focus on the general “get real-world data” problem
  5. Unique-human identities (or, semi-unique-human identities): like #15, but with an emphasis on a less “absolute” solution: making it impossible to get multiple identities is both impossible.
  6. Homomorphic encryption and multi-party computation: need to improve for practicality
  7. Decentralized governance mechanisms: DAOs are cool but current are still very primitive; it can do better
  8. Fully formalizing responses to PoS 51% attacks: ongoing work and refinement of https://ethresear.ch/t/responding-to-51-attacks-in-casper-ffg/6363
  9. More sources of public goods funding: the ideal is to charge for congestible resources inside of systems that have network effects (eg. transaction fees), a social problem along with the technical.
  10. Reputation systems: like #12

In conclusion, base-layer problems are slowly but definitely decreasing, however, application-layer problems are only just getting started.

Read more:

Follow us on Telegram

Follow us on Twitter

Follow us on Facebook

You might also like
Ethereum News

Analyzing Ethereum’s Price Consolidation:…

Ethereum News

Bitwise Predicts SEC Could Postpone Ethereum ETF…

Ethereum News

BlackRock’s Ethereum Tokenized Fund Signals…

Ethereum News

Whale Activity Peaks in 2024 as Ethereum Faces…

Ethereum News

Ethereum Sees Record $913M Net Transfer to Exchanges…

Ethereum News

Grayscale Moves Closer to Ethereum ETF with SEC Filing