How to be fair and efficient without using proof-of-work
foreword
foreword
secondary title
The beauty of POW
Pow is a simple and elegant consensus algorithm. Each node solves a simple encryption puzzle, and the solution is obtained through quick guessing, and whoever guesses correctly first will be selected to generate the next block.
It's that simple.
This simple algorithm also provides true randomness - for fair and decentralized block proposals; a certain delay - to ensure that there is enough time to broadcast, minimizing the probability of forks; economic mortgage - — by investing in hardware and electricity so that miners have a vested interest in working honestly.
secondary title
image description
early assembly lines working side by side
A key problem with the simple and elegant PoW mechanism is that its hard problems can be processed in a high degree of parallelism. These puzzles are usually a hash function, where nodes just keep generating random strings, hashing them, and seeing if the resulting hash matches certain criteria. If you are just a player (e.g. a machine, a thread), suppose you can guess the answer correctly after N seconds on average. But if you're a hundred players, the average time it takes you to guess the correct answer is N/100 seconds, because you can easily distribute the work. For example, if there are a total of M possible answers, you can arrange player 1 to test answer 1 to answer M/100, then arrange player 2 to test answer M/100 to answer M/200, and so on.
Miners working in the PoW blockchain system usually purchase a large number of special-purpose computers, or application-specific integrated circuits (ASICs), and call programs to coordinate the division of labor of these ASICs to guess the answer, so the average speed at which they guess the correct answer will be faster. Over time, different miners decide to team up to share the work of their ASIC groups, hence the mining pools.
For a network like Bitcoin, if the miners guess the answer too quickly, it has a set of internal algorithms that can increase the difficulty of guessing the answer, and finally maintain the block generation time at an average speed of about 10 minutes. Therefore, the faster the miners guess, the more difficult the puzzle is, which incentivizes the miners to speed up or build more ASICs through ASICs.
Mining machines are getting faster and more numerous, consuming more and more energy, until the energy consumption of maintaining the network is ridiculously high.
secondary title
Design Goal: Random Latency
Therefore, if we want to design a system that is not as wasteful of resources as PoW, but can achieve random delays at the same time, we need to achieve the following design goals:
True randomness to ensure fairness and decentralization
Latency cannot be reduced through parallelism to minimize energy consumption
Let's take a look at how to optimize:
image description
White noise is a naturally occurring source of randomness
True randomness is more of a philosophical question. When we say "random", what we really mean is "unpredictable". If the result of our mechanism is unpredictable by any participant in the network, then we consider the result to be random and fair.
Many cryptographic functions appear to generate random outputs, such as hash functions and signature mechanisms. However, they are not specifically designed to generate unpredictable outputs, and observers are able to infer patterns given a sufficiently large number of samples.
In 1999, a paper by Micali, Rabin, and Vadhan was published describing a verifiable random function (VRF) that was specifically designed to generate highly unpredictable outputs. Later, Professor Micali founded the Algorand project, after which Sergey Gorbunov, a core member of the project, wrote a more detailed and understandable article. If you are interested in a more technical treatment of VRF, you can refer to the above articles and papers.
In Taraxa's block DAG architecture, VRF provides randomness for random delays. The output of VRF is:
Block DAG level (L): When the proposer packages the block, the "level" here is the length of the anchor chain + 1. So, if you are the proposer, you calculate the current anchor chain L, and find the final block on the boundary where you will build the ghost pointer (pointer), then the block level you propose is L+1. It should be noted that the definition here is a different concept from the often said "depth".
Block hash (P) of the latest Period block: This is the latest completed block in the block DAG, which can achieve true final confirmation through a parallel PBFT process (detailed in the next article). Considering that the proposer has not received the latest confirmed Period block (P) on the boundary, the protocol will have a certain tolerance, that is, the previous block hash of the latest Period block is also acceptable.
The block proposer's secret VRF key (SK): This is required to build the VRF function. This is different from the transaction signature mechanism, which is specially generated for each node to build VRF.
The output of the VRF function is divided into two parts:
v is a pseudo-random value used to determine the length of the delay.
p is a proof that other nodes can use to verify that the VRF has been executed honestly and correctly. It can be regarded as a signature, and with the VRF public key of the proposer, any other node can easily determine the correctness of the calculation.
Ultimately, we can write a simple equation:
VRF(L, P, SK) → (v, p)
■ Delayed Difficulty Shaping Function
Before the output of the VRF (delay difficulty or delay length) can be converted into a delay, we will need to make it form a certain distribution. The characteristics of the distribution are roughly as follows:
There needs to be a minimum delay because we can't have blocks generated immediately without having time for a proper network broadcast
There needs to be a maximum delay, because we don't want the entire network to be congested, and we don't want blocks to be produced for a long time
Some proposers are fast, while the rest are slow, which is related to the number of qualified proposers and the diameter of the entire network (that is, the time required for a block to reach most of the proposed nodes)
image description
shaping function
Let the type function be S, we can get the following formula:
S(v) = d
Here d is the difficulty coefficient of the next stage.
■ Latency of verifiable delay function
Token is like a bus card, which can generate value transfer by itself, and the alliance chain has no native value transfer. The country is cracking down on pyramid schemes, but in fact there are still many valuable tokens. When the industry develops and the public recognizes it to a certain extent, a high-quality public chain can avoid a one-size-fits-all situation. By this time, there may be more cooperation between the alliance chain and the public chain.
Working hard alone, no one is fighting side by side =(
As discussed at the beginning of this article, PoW is good, but parallel processing is the culprit of its "victimism". Thus, Verifiable Delay Functions (VDFs) emerged, which are specifically designed to simulate latencies that cannot be accelerated by parallel processing.
A function can be strictly classified as a VDF if it meets the following two simple criteria:
must be sequential,In this case, no one can speed up the calculation of the VDF function through multiple parallel processes, which is different from PoW.
must be easily verifiable,The observer can simply verify (that is, the time it takes to verify is much shorter than the time to calculate the function) to confirm that the VDF calculation is correct and the appropriate delay occurs, which is similar to PoW.
Boneh et al., Pietrzak, and Wesolowski et al. all proposed VDFs satisfying these criteria.In particular, Pietrzak and Wesolowski both independently proposed highly similar methods based on the principle of repeated squaring in groups of unknown order, which are effective against parallel processing.
Let's test these functions at a higher level, because the math is very complicated.
These VDFs are constructed to perform repeated squaring calculations that cannot be processed in parallel because each iteration requires input from the previous iteration and no information about future iterations is available in any given iteration. In other words, you won't know the answer until you step through all the iterations. This ensures that the function is sequential.
What makes VDFs easy to verify is that you can build a proof with a random linear combination of VDF intermediate inputs and final outputs. Computation of these limited linear combinations is straightforward because it involves many fewer steps than computing the entire VDF. A simple analogy is the difference between calculating all the values in the entire curve (calculating the entire VDF) and selecting an arrow to push forward a few steps (proving the effectiveness of the VDF). The time taken by the arrow to advance a few steps is obviously much less than the computation. This ensures that the function is easily verifiable.
In Taraxa, we set the following input items in VDF:
Parent Hash (gP), or the parent block your newly created block points to via a ghost pointer
The hash of all transactions (Tx), the hash of all transactions that you plan to include in the block, so you cannot calculate the VDF in advance
d, the difficulty factor of the previous step
Therefore, before the node proposes a block, the VDF function calculation looks like this:
VDF(gP, Tx, d) = z
In practice, to ensure that the verification of the output z is non-interactive, node proposers need to insert intermediate proofs as well as the final output into the proposal block.
image description
For illustration purposes, this is generated from the uniform distribution
As of this writing, VDF is still a very experimental technology and is undergoing active research and testing. Taraxa will cooperate with the best people in the open source field and the academic community to ensure that our ledger adopts the most stable, efficient and secure solution.
