Vitalik: A Review of Advances in Cryptography, Consensus Theory, and Economics
In 2014, I published a post and gave a talk laying out some of the hard problems in mathematics, computer science and economics that I thought were critical to where the field of cryptocurrencies (as I called them at the time) could go Maturity is important. In the past five years, a lot has changed. But how much progress have we made on what we thought was important at the time? Where have we succeeded, where have we failed, and where have we changed our minds about what matters? In this essay, I We'll look back at the 16 issues from 2014 one by one and see how far we've come on each one today. Finally, I'll make my new picks for the 2019 puzzle.
These issues can be divided into three categories:
cryptography, so if they are solvable, then they need to be solved using purely mathematical techniques.
Consensus theory, which improves proof-of-work and proof-of-stake to a large extent.
Economically, structures must be created that involve giving incentives to the different actors, and this often involves the application layer rather than the protocol layer.
first level title
blockchain scalability
blockchain scalability
One of the biggest problems facing the cryptocurrency space today is the problem of scalability... The main problem with [very large blockchains] is trust: if only a few entities are able to run full nodes, then those entities can collude and agree to give themselves a large Of the extra bitcoins, other users cannot see for themselves that a block is invalid without processing the entire block themselves.
Problem: Create a blockchain design that maintains Bitcoin-like security guarantees, but where the maximum size of the most powerful nodes required for the network to keep running is essentially sublinear in the number of transactions.
Status: Great theoretical progress, awaiting more real-world evaluations.
Scalability is a technical problem, and we have made tremendous progress theoretically. Five years ago, almost no one thought about sharding; now, sharding designs are common. In addition to Ethereum 2.0, we have OmniLedger, LazyLedger, Zilliqa, and there seem to be research papers coming out every month. Further development at this point is, in my opinion, incremental. Fundamentally, we already have a number of techniques that allow groups of validators to safely process more data than a single validator, where there is consensus, as well as allowing clients to indirectly verify the full validity and availability of blocks technology, even under the condition of 51% attack.
These are probably the most important technologies:
Random sampling, allowing a randomly selected small committee to be statistically representative of the full set of validators: https://github.com/ethereum/wiki/wiki/Sharding-FAQ#how-can-we-solve-the-single- shard-takeover-attack-in-an-uncoordinated-majority-model
Fraud proofs, allowing a single node that learns of a fault to propagate its existence to everyone else: https://bitcoin.stackexchange.com/questions/49647/what-is-a-fraud-proof
Proof of Custody, allowing verifiers to probabilistically prove that they individually downloaded and verified some data: https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236
Proof of Data Availability, allowing clients to detect if the block body in which their header resides is unavailable: https://arxiv.org/abs/1809.09044. See the updated Merkle tree encoding proposal.
There are other smaller developments like cross-shard communication via receipts, and "constant factor" enhancements like BLS signature aggregation.
timestamp
timestamp
Problem: Create a distributed incentive-compatible system that maintains the current time with high precision, whether it is an overlay on top of a blockchain or its own blockchain. All legitimate users' clocks are normally distributed around some "true" time with a standard deviation of 20 seconds. No two nodes are more than 20 seconds apart.
The solution allows to rely on the existing concept of "N nodes"; in practice, this will be implemented through proof of stake or non-Sybil tokens. The system should keep delivering for less than 120 seconds (less if possible) and be within the internal clock of >99% of honest participating nodes. External systems may end up relying on this system; therefore, regardless of motivation, it should remain secure from attackers controlling less than 25% of nodes.
Status: Making some progress.
Ethereum actually survives well with 13 second block times and no particularly advanced timestamping techniques; it uses a simple technique where clients don't accept declared timestamps older than The block in the client's local time. Still, this has not been verified in serious attacks. The recent network-adjusted timestamp proposal attempts to improve the status quo by allowing consensus for clients to determine the time when the client cannot know the current time with high precision; this has not been tested.
first level title
Arbitrary Proof of Computation
Problem: Problem: Create 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 program outputs O and a Calculate and prove that Q and POC_VERIFY obtain P, O and Q, and output whether Q and O are legally generated by POC_PROVE algorithm using P.
Current status: Great progress has been made both in theory and practice.
This basically says, build a SNARK (or STARK, or SHARK, or…). We did it! SNARKs are now more and more understood and even used in multiple blockchains (including tornado.cash on Ethereum). SNARKs are extremely useful, both as privacy technologies (see Zcash and tornado.cash), and as scalability technologies (see ZK Rollup, STARKDEX, and STARKing Erasure Coded Data Roots).
secondary title
Code obfuscation
The holy grail is to create an obfuscator O such that given any program P, the obfuscator can generate a second program O(P) = Q such that, given the same input, P and Q will return the same output, important Yes, Q shows nothing about the interior of P. Passwords, secret encryption keys can be hidden in Q, or Q can simply be used to hide the proprietary work of the algorithm itself.
Status: Slow progress.
Simply put, the problem is that we want to find a way to "encrypt" a program such that the encrypted program will still give the same output for the same input, but the "inside" of the program will be hidden. An example use case of obfuscation is a program containing a private key, where the program only allows the private key to sign certain messages.
Solutions to code obfuscation are very useful for blockchain protocols. The use case is delicate, as one has to deal with the possibility of on-chain obfuscators being copied and running in a different environment than the chain itself, but there are many possibilities. One I'm personally interested in is removing the centralized operator from collusion-proof gadgets by replacing the operator with some proof-of-work obfuscation program, which allows multiple runs with different inputs to The cost of determining the actions of individual actors is very high.
secondary title
hash-based cryptography
Problem: Create a signature algorithm that does not rely on security assumptions, but instead relies on the random oracle properties of hashes, keeping 160 bits safe against optimal size and other properties of classical computers.
Status: Some progress.
Since 2014, there have been two advances in this direction. SPHINCS is a "stateless" (meaning, meaning it doesn't need to remember information like nonces to use it multiple times) signature scheme, which was released shortly after this "hard problem" list, and provides a A purely hash-based signature scheme with a size of about 41 kB. Additionally, STARKs have been developed from which one can create similarly sized signatures. In fact, not only signatures, but also universal zero-knowledge proofs can be implemented through hashing, which I definitely did not expect five years ago; I am very happy. That said, size is still an issue, and progress is continuing to reduce the size of proofs (such as the recent DEEP FRI), although it looks like further progress will be incremental.
first level title
secondary title
ASIC Resistant Proof of Work
One way to solve this problem is to create a proof-of-work algorithm based on a type of computation that is very difficult to specialize... See https://blog.ethereum.org/2014/06/ for a more in-depth discussion on ASIC-resistant hardware 19/mining/.
Status: We have done our best.
About 6 months after the "hard problem" list was published, Ethereum settled on its ASIC-resistant proof-of-work algorithm: Ethash. Ethash is considered a memory hard algorithm. The theory is that random-access memory in general computers is already so well optimized that it is difficult to improve it in specialized applications. The goal of Ethash is to achieve ASIC resistance by making memory access a major part of running PoW calculations.
Ethash is not the first memory-hard algorithm, but it does add an innovation: it uses pseudo-random lookups on a two-level DAG, allowing functions to be computed in two ways. First, if one has the entire DAG (about 2GB), it can be computed quickly; this is the memory-hard "fast path". Second, if there is only the top layer of the DAG, the computation is much slower (but still able to check individual solutions quickly); this is used for block validation.
secondary title
useful proof of work
Making proof of work useful while making it useful; one project candidate is Folding@home, an existing program where users download software to their computers that simulates protein folding and provides researchers with large amounts of data to help them treat disease .
Status: Probably not feasible, with one exception.
The challenge with useful proof-of-work is that a proof-of-work algorithm requires a number of properties:
hard to calculate
easy to verify
Does not depend on large amounts of external data
Can be computed efficiently in small "bite-sized" blocks.
Unfortunately, there aren't many useful computations that preserve all of these properties, and most computations that are "useful" with all of these properties are only "useful" for too short a time to build a cryptocurrency around them.
However, there may be one exception: the generation of zero-knowledge proofs. Zero-knowledge proofs of blockchain validity (e.g., data availability roots) are difficult to compute but easy to verify. Furthermore, they have always been difficult to compute; if proofs of "highly structured" computations become too easy, one can simply switch to verifying entire state transitions of the blockchain, since virtual machines and random memory accesses need to be modeled, which will become very expensive.
proof of stake
proof of stake
Another way to solve the problem of mining centralization is to eliminate mining altogether and use other mechanisms to calculate the weight of each node in the consensus. By far the most popular alternative in discussions is "proof-of-stake" — that is, instead of viewing the consensus model as "one unit of CPU power, one vote" but "one currency unit, one vote" ".
Status: Great theoretical progress, awaiting more real-world evaluations.
Towards the end of 2014, the proof-of-stake community made it clear that some form of "weak subjectivity" was inevitable. To maintain economic security, nodes need to obtain the latest checkpoint extra agreement when they first sync, and also need to acquire checkpoint extra agreement again if they are offline for more than a few months. It's a tough pill to swallow; many PoW advocates still stick with PoW because in a PoW chain the "head" of the chain can be discovered and the only data from a trusted source is the blockchain client software itself . Proponents of PoS, however, are willing to swallow this pill because they believe the increased trust requirements are not significant. Since then, the path to proof-of-stake through long-term deposits has become clear.
Most of the interesting consensus algorithms today are basically similar to PBFT, but replace the fixed set of validators with a dynamic list that anyone can send tokens to a system-level smart contract (with time-locked withdrawals) Come join this dynamic list. In some cases, withdrawals may take up to 4 months to complete). In many cases (including Ethereum 2.0), these algorithms achieve "economic end" by punishing validators who perform actions that violate the protocol in certain ways.
As of today we have (among many other algorithms):
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
proof of storage
proof of storage
A third way to solve this problem is to use scarce computing resources other than computing power or currency. In this regard, the two main alternatives that have been proposed are storage and bandwidth. In principle, there is no way to provide post-event cryptographic proofs that bandwidth was given or used, so bandwidth proofs should most accurately be considered a subset of social proofs, discussed later, but storage proofs are certainly computable. One of the advantages of Proof of Storage is that it is completely ASIC resistant; our storage in hard drives is already close to optimal.
Status: Many theories have progressed, although much remains to be done and more real-world assessments are needed.
secondary title
economic aspect
Crypto assets with stable value
A major problem with Bitcoin is price volatility. Problem: Construct a price-stable cryptoasset.
Status: Making some progress.
MakerDAO is now live and has been running stably for almost two years. It survived a 93% drop in the value of its underlying collateralized asset (ETH) and now has over $100 million in outstanding DAI. It has become a mainstay 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 support.
However, while the MakerDAO system survived the tough economic climate of 2019, it was by no means the toughest scenario that could have happened. Bitcoin has dropped 75% in two days in the past; the same thing will happen to Ethereum or any other collateral asset in the future. An attack on the underlying blockchain is an even greater untested risk, especially if compounded through price drops at the same time.
secondary title
Decentralized public goods incentives
One of the challenges facing economic systems in general 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 understood that if it is completed, the resulting research will save $5 each for 1 million people. Overall, the social benefits are clear...[but] from everyone's point of view, the contribution is pointless...
Most problems with public goods so far involve centralization. Additional assumptions and requirements: there exists a fully trusted oracle to determine whether a certain public goods task has been completed (actually this is wrong, but that is another problem area).
Status: Making some progress.
The problem of financing public goods is generally understood as being divided into two problems: the financing problem (where does the public good get financed from) and the preference aggregation problem (how to determine what is really a public good and not an individual person's pet project). This question focuses specifically on the former, assuming the latter has been addressed (see the section “Decentralized Contribution Metrics” for work on this problem).
Overall, there have been no new major breakthroughs in this area. There are two main solutions. First, we can try to motivate individual contributions by giving people social rewards for doing so. My own proposal for philanthropy through marginal price discrimination is one example; another is the anti-malarial donation badge on Peepeth. Second, we can collect funds from applications with network effects. Within the scope of the blockchain, there are several that can do this:
issue coins
Charge a portion of transaction fees at the protocol level (e.g. via EIP 1559)
From some layer2 application (for example, Uniswap, or some scalable solutions, or even state rent in the execution environment of Ethereum 2.0)
Some other fees apply (eg ENS registration)
reputation system
reputation system
Problem: Design a formal reputation system consisting of a score rep(A,B) -> V where V is B's reputation from A's perspective, a mechanism for determining the probability that one party can be trusted by another, and A mechanism for updating reputation given a record of a particular public or eventual interaction.
Status: Slow progress.
Since 2014, not much research has been done on reputation systems. Perhaps the best way to do this is to use a token escrow registry to create a custodial list of trusted entities/objects; the Kleros ERC20 TCR (yes, that's a registry for legitimate ERC20 tokens) is an example, and there's even an alternative Ninja uses Uniswap (http://uniswap.ninja) as a backend, from which it gets a list of tokens, tokencodes, and identities.
secondary title
proof of excellence
There is an interesting and largely unexplored solution to the token distribution problem (which is why it cannot be used for mining so easily), using tasks that are socially useful but require primitive humans Driven creative effort and talent. For example, we could come up with a "proof-of-proof" coin that rewards players for coming up with mathematical proofs of certain theorems.
Status: No progress, issues largely forgotten.
secondary title
Anti Witch System
One problem associated with reputation systems is the challenge of creating "unique identity systems" - systems that generate tokens to prove that an identity is not part of a Sybil attack...however, we hope there is a better one than "one dollar one vote" , a more egalitarian system; arguably, one person, one vote would be ideal.
Status: Making some progress.
Quite a few people have tried to solve this uniquely human problem. Thoughts to try include (non-exhaustive list!)
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/
secondary title
Decentralized Contribution Indicators
Unfortunately, incentivizing the production of public goods is not the only problem that centralization solves. Another problem is, first, to determine which public goods are worth producing and, second, to determine the extent to which some kind of effort actually accomplishes the production of the public goods. This challenge deals with the latter question.
Status: Some progress, with a change of focus.
Recent work on determining the value of public benefit contributions has not attempted to separate determining the task from determining the quality of completion; the reason is that the two are difficult to distinguish in practice. The work done by a particular team is often irreplaceable and sufficiently subjective that the most reasonable approach is to consider the relevance of the tasks and the quality of performance as a single package and use the same techniques to evaluate both.
Fortunately, much progress has been made in this regard, especially with the discovery of secondary grants. Quadratic grants are where individuals can donate to a project, and then based on how many people donate and how much they donate, a formula is used to figure out how much they would donate if they were perfectly aligned with each other (ie, how much they donated). considered each other's interests and did not fall prey to the tragedy of the commons).
For any given project, the difference between the amount that might have been donated and the amount actually donated would be given to that project as a subsidy from some central pool of funds. The caveat is that this mechanism is focused on satisfying certain community values rather than satisfying some given goal, whether or not anyone cares about it. Due to the complexity of the value problem, this approach may be more robust to unknown unknowns.
secondary title
Decentralized Success Metrics
Problem: Propose and implement a decentralized method to measure real world numerical variables...the system should be able to measure anything that humans can currently reach a rough consensus on (e.g. asset prices, temperature, global CO2 concentration).
Status: Making some progress.
This is now commonly referred to as the "oracle problem". The largest known running instance of a decentralized oracle is Augur, which processes millions of dollars in staking outcomes. Token curation registries such as Token’s Kleros TCR are another example. However, these systems still haven't seen a real-world test of the forking mechanism either due to a highly controversial issue or due to attempted 51% attacks. There is also research on the oracle problem occurring outside the blockchain space, in the form of the "peer-to-peer prediction" literature.
Another looming challenge is that people want to rely on these systems to guide the transfer of asset quantities that are greater than the economic value of the system's native token. In this case, token holders would theoretically have an incentive to collude to give the wrong answer in order to steal funds.
first level title
new question
If I were to write the list of puzzles again in 2019, some would be a continuation of the questions above, but the emphasis would have changed considerably, and there would have been great new questions.
Here are some questions:
Password Obfuscation: Same as item 4 above.
Ongoing work in post-quantum cryptography: hash-based and post-quantum secure "structured" mathematical objects, eg. Elliptic Curve Constructs…
Anti-collusion infrastructure: work in progress and refinements https://ethresear.ch/t/minimal-anti-collusion-infrastructure/5413, including adding privacy against operators, adding multi-party computation in the most practical way, etc.
Oracles: Same as #16 above, but de-emphasizes "success metrics" and focuses on the general "obtaining real world data" problem.
Unique human identities (or, more realistically, semi-unique human identities): same as written in #15 above, but emphasizing a less "absolute" solution: getting two identities should be better than getting one Much harder, but making multiple identities unobtainable would be both impossible and potentially harmful, even if we succeeded.
Homomorphic encryption and multi-party computation: For practicality, continuous improvement is still needed.
Decentralized governance mechanisms: DAOs are cool, but current DAOs are still very primitive; we can do better.
Fully formalized responses to PoS 51% attacks: see 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 (such as transaction fees) within a system with network effects, but doing so in a decentralized system requires public legitimacy; thus, it is both a social issue , is also a technical matter of finding possible sources.
Reputation System: Same as #12 above.
In general, problems at the base layer are slowly but surely diminishing, but problems at the application layer are just beginning.
Source：https://www.google.com/search?q=%E7%BF%BB%E8%AF%91&oq=%E7%BF%BB%E8%AF%91&aqs=chrome..69i57j0i512j0i433i512l2j46i131i199i433i465i512l2j0i131i433i512j0i433i512l2j46i433i512.1125j0j15&sourceid=chrome&ie=UTF-8
