Vitalik: Review the key progress and new challenges of the blockchain in the past 5 years

Original link:https://vitalik.ca/general/2019/11/22/progress.html

Author: Vitalik Buterin

Original link:

Author: Vitalik Buterin

First link of translated articles: http://1t.click/bnSg

This article was translated by the Cortex Labs (CTXC) operations team and posted on the Cortex Forum.

"Special thanks to Justin Drake and Jingjing Wang for their feedback."

These questions fall into three categories:

In 2014, I published an article and a talk laying out a series of hard problems in mathematics, computer science, and economics that I believed to be important to the maturation of (what I then called) the field of cryptocurrencies . A lot of things have changed in the past five years. But how much progress has been made on issues that we thought were important at the time? Where have we succeeded and where have we failed? In what important way have our minds been changed? In this post, I'll look back at the 16 issues from 2014 one by one and see where we are today on each issue. Finally, it will include my new choices for the challenges I face in 2019.

These questions fall into three categories:

(1) cryptography, if they are solvable at all, are expected to be solvable by purely mathematical techniques;

(2) Consensus theory, which mainly improves PoW (Proof of Work, proof of workload) and PoS (Proof of Stake, proof of rights and interests);

(3) Economics, which involves creating structures that give incentives to different actors, and often involves the application layer rather than the protocol layer. We saw significant progress across all categories, although some more than others.

password issue

1. Blockchain scalability (Scalability)

One of the biggest problems facing the cryptocurrency space today is the problem of scalability. The main problem with large-scale blockchains is trust: if only a few entities are able to run full nodes, those entities can collude and agree to give themselves large amounts of additional cryptocurrency; and, without handling the entire blockchain themselves In this case, other users will not be able to see for themselves that a block is illegal.

Problem: Create a blockchain design that maintains Bitcoin-like security guarantees, but where the maximum performance of the strongest nodes required for the network to keep running is essentially sub-linear in the number of transactions.

Status: Great theoretical progress, expect more real-world evaluations.

Scalability is a technical problem, and we have made tremendous progress theoretically. Five years ago, sharding was hardly considered; now, sharded designs are commonplace. Besides Ethereum 2.0, we have OmniLedger, LazyLedger, Zilliqa, and research papers that seem to come out every month. In my own view, further progress at this point is incremental. Fundamentally, we already have a number of techniques that allow groups of validators to securely agree on more data than a single validator can handle, while at the same time allowing users to indirectly verify the full validity and availability of blocks , even below the 51% attack condition.

These are probably the most important technologies:

Random sampling, allowing a randomly selected set of validators to statistically replace the full set of validators;

Fraud proofs, allowing individual nodes who know about a bug to propagate the bug's existence to everyone else;

Proof of custody, allowing verifiers to probabilistically prove that they downloaded and verified some data, respectively;

Proof of Data Availability, which allows users to detect when the data subject of the block whose header resides is unavailable: link. See also the newer coded Merkle tree proposal.

There are other smaller advances like cross-shard communication via receipts, and "constant factor" enhancements like BLS signature aggregation.

2. Timestamping

Status: some progress

Problem: Create distributed incentive-compatible systems that maintain High precision of current time. All legitimate users' clocks are in a normal distribution of some "real" time with a standard deviation of 20 seconds and no two nodes separated by more than 20 seconds. The solution allows relying on the existing concept of "N nodes"; in practice, this would be implemented via proof-of-stake or non-Sybil tokens (see #9). The system should continuously provide time that is within 120s (or less if possible) of the internal clocks of >99% of participating honest nodes. External systems may ultimately depend on this system; therefore, regardless of motivation, it should be kept secure such that no attacker controls more than 25% of the nodes.

Status: some progress

In practice, Ethereum works pretty well with 13 second block times and no particularly advanced timestamping techniques; it uses a simple technique where clients don't accept declared timestamps earlier than the client's local block of time. That said, this has not been tested under serious attacks.

3. Arbitrary calculation proof

Problem: Create the programs POC_PROVE(P, I) -> (O, Q) and POC_VERIFY(P, O, Q) -> {0, 1}. Among them, POC_PROVE executes program P, I is the input of program P, POC_PROVE returns the execution result O of program P and a calculation-based Q; POC_VERIFY verifies whether Q and O are legal operations obtained by POC_PROVE using P result.

Status: Significant theoretical and practical progress

This basically says to build a SNARK (or STARK, SHARK, whatever). We have done it! SNARK is now understood by more and more people, and has even been used in multiple blockchains (including tornado.cash on Ethereum). SNARKs are 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).

Status: slow progress

The main goal is to create an obfuscation function O. Given an arbitrary program P, the obfuscation function can generate a second program O(P)=Q, where P and Q return the same result given the input. Importantly, Q does not display any information about the internals of program P. One can hide passwords, encrypted private keys, or newly invented algorithms themselves in program Q.

Status: slow progress

Generally speaking, what this question wants to express is how to find a method to encrypt the program so that the encrypted program outputs the same result under the same input, but the information inside the source program will be hidden. An example use case for code obfuscation is a program containing a private key that only allows the private key to sign certain messages.

The solution to code obfuscation is extremely useful for blockchain protocols, and its application scenarios are very delicate. Because it is necessary to deal with the possibility that obfuscated programs on the chain are copied and run in another environment different from the chain itself, and there are many other situations. An application scenario that I am personally very interested in is to use obfuscated programs to replace operations that originally included some proof-of-work, so that centralized operations can be removed in anti-collision gadgets, making it possible to try to run with different inputs. It is very expensive to run the operation multiple times to determine the private behavior of the participants.

Unfortunately, this is a very hard problem, and there is still a lot of work to be done on the way to solving this problem. On the one hand, it is to construct to reduce the number of assumptions about mathematical objects that we don't know whether we actually don't know (such as general-purpose cryptographic multilinear maps), and on the other hand, it is to try to actually implement the required mathematical objects. However, all of these paths are far from creating feasible and known security.

Status: some progress

Problem: Create a signature algorithm that does not rely on security assumptions but is based on properties of random oracles for hash values ​​that are maintainable and have optimal size and other properties for classical computers (e.g., a quantum computer designed by Grover's algorithm is equivalent to 80 bits) equivalent to 160 bits of security.

Status: some progress

The main unsolved problem with hash-based cryptography is aggregated signatures, similar to what BLS aggregates do. It is known that we can STARK many Lamport signatures, but this is inefficient and a more efficient scheme would be welcome. (If you're wondering if it's possible to use hash-based public key encryption, the answer is no, you can't do anything with a squaring attack or worse).

6. ASIC-resistant proof of work (PoW)

The solution is to create a very difficult algorithm to solve special problems. For an in-depth discussion of ASICs, please see this: https://blog.ethereum.org/2014/06/19/mining/

Status quo: It is a problem that we have tried our best to solve

About six months after the “hard problem” list was published, Ethereum decided to adopt its ASIC-resistant proof-of-work algorithm: Ethash. Ethash is known as a hard memory algorithm. Theoretically, random access memory in conventional computers is already so well optimized that it is difficult to improve it for special applications. Ethash aims to be ASIC resistant by making memory access an essential part of running PoW calculations. Ethash is not the first algorithm with hard memory requirements, but it does add an innovation: it uses pseudo-random lookups on a two-layer DAG, thus providing two ways of evaluating functions. First, if one has the entire (~2 GB) DAG, it can be computed quickly; this is the "fast path" to satisfy the hard memory requirement. Second, if there is only the top level of the DAG, it needs to be computed slowly (and still verify the result quickly). Used for block verification.

Ethash has proven to be very successful against ASICs. After three years and billions of dollars in block rewards, ASICs do exist, but are at best 2-5x more powerful and costly than GPUs. ProgPoW has been proposed as an alternative, but there is a growing consensus that ASIC-resistant algorithms will inevitably have a finite lifetime, and that ASIC resistance has a downside as it makes 51% attacks cheaper (e.g., See 51% Attack on Ethereum Classic https://cointelegraph.com/news/ethereum-classic-51-attack-the-reality-of-proof-of-work).

7. Useful Proof of Work (PoW)

Make proof-of-work useful beyond proof-of-work; common candidates are something like Folding@home, an existing program that users download to a computer to simulate protein folding, and provide People provide vast amounts of data to help them cure disease.

Status: probably not feasible, with one exception

The challenge with a useful proof of work is that a proof of work algorithm requires a number of properties:

1. Difficult to calculate, easy to prove

2. Does not rely on large amounts of external data

3. Efficient block calculation

Unfortunately, there aren't many useful computations that preserve all of these properties, and most computations that have all of these properties and are "useful" are only "useful" for too short a time to build cryptocurrencies based on them.

However, there is one possible exception: zero-knowledge proofs. Zero-knowledge proofs on the blockchain (e.g., the availability of data for a simple example) are hard to compute and easy to verify. Furthermore, they are computationally difficult. If proofs of "highly structured" computations become too easy, one can simply switch to verifying changes to the state of the entire blockchain, which becomes prohibitively expensive due to the need to model virtual machines and random memory accesses.

8. Proof of Stake (PoS)

Another way to solve the problem of mining centralization is to do away with mining entirely, and turn to other mechanisms to calculate the weight of each node in the consensus. By far the most popular alternative in discussion is "proof of stake" - that is, rather than thinking of the consensus model as turning one vote per CPU into one vote per coin.

Status: Significant theoretical progress, more practical evaluation needed

Casper FFG:

https://arxiv.org/abs/1710.09437

Tendermint: 

https://tendermint.com/docs/spec/consensus/consensus.html

HotStuff: 

https://arxiv.org/abs/1803.05069

Casper CBC: 

https://vitalik.ca/general/2018/12/05/cbc_casper.html

Before the end of 2014, the evidence from the rights community made it clear that some form of "weak subjectivity" was inevitable. To maintain economic security, nodes need to fetch the most recent checkpoint protocol when they first sync, and again if they are offline for more than a few months. This is a big risk. Many PoW proponents still insist on using PoW because in a PoW chain, the "head" of the chain can be found as the only data coming from a trusted source, the blockchain client software itself. However, PoS advocates are willing to take this risk, as the added trust requirements are not significant and the path to long-term proof-of-stake becomes clear.

https://ethresear.ch/t/analysis-of-bouncing-attack-on-ffg/6113

https://ethresear.ch/t/saving-strategy-and-fmd-ghost/6226

Today, the most interesting consensus algorithm is fundamentally similar to PBFT (Practical Byzantine Fault Tolerance, Practical Byzantine Fault Tolerance), but replaces the fixed set of validators with a dynamic list that anyone can send tokens to with a lock. Time-based system-level smart contracts to join dynamic lists that anyone can join (e.g., in some cases, withdrawals can take up to 4 months to complete). In many cases (including Ethereum 2.0), these algorithms achieve "economic finality" by penalizing validators who are found to be violating the protocol in certain ways (see The philosophical point of view here) is as follows:

These also continue to be refined

9. Storage certificate

Status: Some theoretical progress has been made, but there is still a long way to go and more practical evaluation is needed

There are a number of blockchains planned to use proof of storage protocols, including Chia and Filecoin. That said, these algorithms have not been tested in the wild. My own main concern is centralization: are these algorithms actually dominated by smaller users using spare storage capacity, or are they dominated by large mining farms?

Status: some progress

One of the main problems with Bitcoin is its volatility against fiat currencies. Problem: Synthesize encrypted assets that have a stable price against legal currency.

Status: some progress

MakerDAO is live now and has been running stably for almost two years. Its underlying collateral asset, ETH, survived a 93% drop in value and now has more than $100 million in issued synthetic stable token DAI. It has become the backbone of the Ethereum ecosystem, and many Ethereum projects have or are integrating with it. Other synthetic token projects, such as UMA, are also rapidly gaining ground.

But while MakerDAO's system has weathered tough economic conditions in 2019, things are by no means the toughest. In the past, Bitcoin has dropped 75% in two days; the same could happen to Ethereum or any other collateralized asset one day. At the same time, a malicious attack on the bottom layer of the blockchain is a larger untested risk, which is exacerbated by the price drop that this risk is expected to bring; The stability of MakerDAO's system depends on private oracles. Currently, there are indeed different attempts at targeting oracles (see #16), but the jury is still out on whether they will hold up under enormous economic pressure.

Status: some progress

Often, one of the challenges in economic systems is the problem of "public goods". For example, suppose there is a scientific research project that will cost $1 million to complete, and it is known that if this research is completed, the resulting research will save $5 for 1 million people. Overall, the social benefits of public goods are clear, however, from the perspective of each individual's contribution, they are not justified. So far, most solutions to public goods problems have involved centralization. Additional assumptions and requirements: there are perfectly trustworthy oracles for determining whether a certain public goods task has been completed (actually this is wrong, but that's another problem area)

Status: some progress

• It is generally believed that the problem of financing public goods can be divided into two problems: the problem of financing (where to get financing for public goods) and the problem of propensity to aggregate (how to determine what is really a public good and not some individual's private project). The latter is assumed here to be addressed, and this problem is dedicated to the former, the funding problem (for work on this problem, see the section "Distributed Contribution Metrics" below).

• Overall, there are no major new breakthroughs here. There are two categories of solutions. First, we can try to elicit individual contributions, thereby providing people with social rewards. My own proposal for philanthropy through marginal price discrimination is one example; another is Peepeth's Badge of Donation Against Malaria. Second, we can collect funds from applications with network effects. Within the blockchain space, there are several options to do this:

• issue tokens

• Charge transaction fees at the protocol level (e.g. EIP 1559)

Collect transaction fees from some Layer-2 applications (such as Uniswap or some scaling solutions, or even rent fees in the execution environment of Ethereum 2.0)

Charge other fees (e.g. ENS registration)

Outside of the blockchain space, it's just a matter of tradition: governments can collect taxes; businesses or other organizations can charge fees.

Status: slow progress

Problem: Design a formalized reputation system consisting of: a reputation score, rep(A,B) -> V, where V represents a measure of B's ​​reputation from A's perspective; a probabilistic mechanism for determining whether one party can trust another ; and a mechanism for updating the reputation when there is an interaction record in progress or completed."Status: slow progress"Since 2014, there hasn't been a lot of work done on reputation systems. Perhaps the best example is creating a curated list of trusted entities/objects as a token registry; the Kleros ERC20 TCR (yes, this is a registry for legitimate ERC20 tokens) is one example, there are additional interfaces Interface to Uniswap (http://uniswap.ninja), which uses Kleros as a backend, from which it gets a list of tokens and tokens and logos. Reputation systems with subjective diversity have not really been tried, perhaps because of the interconnectedness of traders

social connection graph

prove

Currency that rewards players for proving certain mathematical theorems.

Status: No progress, issues all but forgotten

14. Contribution to decentralization

Unfortunately, incentivizing the production of public goods is not the only problem that centralization solves. Another problem that centralization solves is: first of all, it is necessary to clarify which public goods should be produced, and then determine how much work is required to complete the output of public goods. This challenge deals with the latter question.

Status: Some progress, with a change of focus

Recent advances in determining the value of public goods contributions have not separated the two aspects of 1. determining tasks and 2. determining degrees of completion, because they are difficult to separate in practice. The work done by certain teams is often irreplaceable and subjective, so the most logical approach is to consider the correlation of task and performance quality as a whole and evaluate them using the same techniques.

Fortunately, much progress has been made in this regard, especially with the discovery of "secondary funding". "Quadrafunding" is a mechanism whereby individuals can donate money to a project. Under the condition of perfect coordination of donors, based on the number of people donating and the amount donating, the donation amount is calculated using a formula. (The perfect downward adjustment here means: even if the interests of each donor are taken into account, it will not lead to a collective tragedy of all donations). When donating to a project, the difference between the amount that should have been donated and the amount actually donated is given to the project as a subsidy from some central pool (see Section 11 for the source of the central pool). Note that this mechanic focuses on satisfying some community value rather than satisfying some given goal, regardless of whether anyone cares about it. Due to the complexity of the value problem, this approach may be more robust to unknown unknowns.

15. Anti-sybil attack system

This question is somewhat related to reputation systems, and it's the challenge of creating a "unique identity system". An anti-Sybil attack system is a system that generates tokens that prove one's identity is not part of a Sybil attack. However, we would like to have a better and more egalitarian system than "one dollar, one vote"; arguably, one person, one vote would be ideal.

HumanityDAO: 

https://www.humanitydao.org/

Pseudonym parties: 

https://bford.info/pub/net/sybil.pdf

POAP ("proof of attendance protocol"): 

https://www.poap.xyz/

BrightID: 

https://www.brightid.org/

Status: Some progress. Many attempts have been made to solve uniquely human problems

Conceivable attempts include (non-exhaustive list!):

Status: some progress

Problem: Propose and implement a distributed method for measuring real-world numerical variables. The system should be able to measure any numerical property that humans can currently agree on roughly (e.g., asset prices, temperature, global carbon dioxide concentrations).

This is now commonly referred to as the "oracle problem". The largest known instance of a distributed oracle running is Augur, which has processed millions of dollars in betting outcomes; token-curated registries such as Kleros TCR are another example. However, these systems still haven't seen real-world testing under forking mechanisms (search for "subjectivism" here), either for a highly controversial issue or for attempting to 51% attack. There is also research on oracle problems that take place outside the blockchain space, in the form of "peer predictions"; see here (https://arxiv.org/abs/1911.00272) for recent developments in this area.

new question

encryption obfuscation

If I were to write a hard list again in 2019, the above problems would continue, but with a major shift in focus, and new major problems would emerge. Here are some picks:

encryption obfuscation

Same as #4 above

Anti-collusion infrastructure

Oracle

Work in progress and refinement of https://ethresear.ch/t/minimal-anti-collusion-infrastructure/5413, including adding privacy against operators, adding multi-party computation in the most practical way possible, etc.

Same as #16 above

Homomorphic Encryption and Multi-Party Computation

Homomorphic Encryption and Multi-Party Computation

Decentralized Governance Mechanism

Usability still needs continuous improvement.

Decentralized Governance Mechanism

DAOs are cool, but current DAOs are still primitive and we can do better.

Fully formalizing the response to a PoS 51% attack

Work in progress and complete https://ethresear.ch/t/responding-to-51-attacks-in-casper-ffg/6363

More sources of funding for public goods

It would be ideal to charge for congested resources in a system with network effects (e.g. transaction fees), but doing so in a distributed system requires public legitimacy; thus, it is a social problem as well as a technical problem of finding possible sources .

reputation system