Filecoin and the natural constant e

[Warning: Mathematics, Probability and Distribution]

e is called a natural constant. In the eyes of mathematicians, this constant is very natural. However, for ordinary people, e is difficult to understand because there is no figurative description. This article hopes to find some points through the application of e in Filecoin to help everyone 1) understand some of the designs of Filecoin; 2) get a little figurative description and impression of e through Filecoin.

There are two common and complex mathematical constants that are interesting. One is π and the other is e. Everyone is very familiar with π because it has a very vivid name, called pi, which is the ratio of the circumference of any circle to its diameter. It is very vivid and easy to understand. If you don't learn it in elementary school, you will learn it in junior high school.

In fact, e is a mathematical constant that is as important as π, and its use in mathematics is no less than π. For example, in the Filecoin blockchain we are discussing today, e is used in many places, while π is not used at all.

But in fact, e and π are closely related in mathematics. We can even say that e is another way to express π. Why? Please see the most elegant mathematical formula - Euler's formula:

Why is it elegant? This simple formula simply unifies the five elements of mathematics (0, 1, i, π, e). Just like physicists hope to unify the force field, mathematicians also have the obsession to summarize simple laws.

This formula also expresses a simple and direct relationship between e and π. Of course, there are some interesting relationships between them, such as:

However, these seem to complicate things and do not help us understand e itself. What exactly is e? In mathematics, we know that e is the base of natural logarithms. One of its main characteristics is that the derivative of e^x is also e^x. At the same time, e can be expressed and calculated by the following formula:

To put it in a more vivid way, in the calculation of compound interest, e represents an interest rate that doubles over a period of time, and is the limit that can be reached by continuous compound interest calculation. In other words, if the annual interest rate is 100%, if you divide a year into n time periods infinitely, then the interest rate for each time period is 1/n, and the income you can get in the end, including principal and interest, is e times, which is a little more than 2.7 times.

This is still not vivid enough, so let’s take a look at the consensus mechanism mapped to Filecoin.

Let's first review the expected consensus described in the Filecoin white paper. In the early implementation of go-filecoin, a simple expected consensus was used, that is, the probability of each miner obtaining the right to produce a block was determined by the ratio of their own computing power to the total computing power. Because the sum of the computing power of all miners is equal to the total computing power, the expected value of the total probability of producing a block in each round of the system is 1. In simple terms, one block is produced on average in each round, but each miner calculates independently, so the number of blocks produced in each round may vary.

In this case, we build a simple (and effective) model to make a deduction. Assuming that the number of miners in the system is n, and the computing power of each miner accounts for 1/n, then the probability of each miner producing a block in each round is 1/n.

In this way, the probability of an empty block appearing in a round is:

If n is large enough, then we can obtain:

In other words, the probability of a blank round is more than one-third, which is too high.

So what is the probability of producing 1 block? You can simply calculate it as follows:

It is still only a little more than one-third. The remaining less than one-third of the probability is all multi-block rounds. This conclusion is completely consistent with the test of the development network at that time.

From here, we found a more vivid explanation for the natural constant e, which is: in an independent voting election with many people (a large number) participating, everyone has the same probability of winning the election, and the expected number of people winning the election is 1, then the probability of not being able to obtain an election result is the reciprocal of e, that is, 1/e.

We simulated the high empty block rate on the development network and discussed it with the Filecoin research and development team. Obviously, such a high empty block round ratio is not good, because the block time is not fixed and the transaction time is difficult to predict.

So, what is a simple change? That is to increase the expected number of blocks in each round. Because the expected consensus may have multiple blocks in one round, and the tipset method is used in the implementation, increasing the expected number of blocks is very simple in terms of design and implementation.

Before the testnet, Filecoin introduced the concept of the expected number of blocks per round, which is defined as E (ExpectedBlocksPerEpoch). The current default is: E = 5

Since the expected number of blocks has increased, the simplest method is to increase the probability of each miner to produce blocks by 5 times. However, the calculation of miners producing blocks is done by rolling dice. That is, a number in a 256-bit space is generated to compare the proportion of one's own computing power, so as to determine whether one has the right to produce blocks. There is a problem of data crossing the boundary here. Filecoin's implementation has gone through three stages in this judgment:

Phase 1: Each miner divides the computing power according to his own computing power, and each miner participates in the election according to a smaller share. If he wins the election, he will get one vote. The same default computing power is uniformly divided into 25 sectors (the remaining part is calculated separately). The advantage of this method is that the computing power of each voter is basically the same, and a fair election is conducted. However, since each 25 sectors must be calculated separately, each part requires I/O access, which consumes a lot of time. The original purpose of the Filecoin team was to put this block production right and the proof of time and space together. However, in the end, from a security perspective, due to the relatively complex calculation, it was abandoned.

Phase 2: Direct extreme simplification, without considering the problem of out-of-bounds, directly multiply by 5 for comparison and calculation. This is a simplified measure when the proof of time and space has replaced SurprisedPoSt with WindowedPoSt. However, there are two problems with this: 1) Miners with a computing power greater than 20% will definitely suffer; 2) When the computing power of miners is large enough, they will definitely win the election. This second problem is more serious. We carefully propose that this is a security issue and should be changed.

Phase 3: Using the cryptographic lottery method, drawing on the algorithm used by Algorand, and gradually moving towards perfection.

Algorand's cryptographic lottery is a very good application of probability distribution in elections, which is great for blockchain POS networks. The implementation is relatively simple and direct. The specific algorithm is as follows:

I won’t explain it in detail here, and those who need it can look up relevant information. Simply put, in the POS election process, when you draw lots based on the verifiable random number you generate, you can use your own share and the corresponding binomial distribution to see which interval you fall into, and thus determine how many votes you have received.

The binomial distribution is a distribution in which n independent times with the same probability are calculated separately and then added together, and the entire distribution just divides the entire probability space. Therefore, you only need to see which space your verifiable random number is in (this part is difficult to explain clearly, and those who are interested can discuss it offline).

For Filecoin, the share participating in the election is your computing power. If we follow the method of Phase 2 mentioned above, we can further subdivide it, and then consider voting for each byte. In this way, the number of voters participating in the vote is very large, and the entire calculation does not need to use the binomial distribution, but can be calculated using the Poisson distribution. The calculation formula of the Poisson distribution is as follows:

Here λ is the product of one’s share and the expected total number of votes. In Filecoin, it is

E * mPow/totPow; k is the number of voting rights obtained.

Look at the above formula, isn’t it amazing? The natural constant e is once again used in the calculation of Filecoin’s election. Using Poisson distribution for calculation is an improvement of Filecoin, which is very consistent with the characteristics of Filecoin and the calculation is also very simple.

After adopting the cryptographic lottery, it is not guaranteed that a miner will get the right to produce a block in every round. This is normal because everyone rolls the dice by themselves and the calculation of the right to produce a block is independent. In this case, what is the probability of winning different votes for producing a block in each round? A simple simulation can produce the following table:

The probability of a blank round here is e^-5.

That is to say, it is expected that there will be an empty round in less than 200 heights. It seems okay. The number of votes per round is 3, 4, 5, 6, and 7, which are more evenly distributed. There are also many cases where the number of votes is as high as 15, which is about 1.6 per 10,000.

Seeing this (if you really have the patience to read this far), you may wonder whether e is more related to probability. In fact, I can tell you that π is sometimes also used in probability calculations. This is because these two constants are closely related.

The use of the natural constant e in elections now seems very natural and elegant.

At the same time, Filecoin also uses e to calculate the release of tokens. This has nothing to do with probability, but with decay. Filecoin does not use the periodic halving method to release tokens, but imitates radioactive decay, that is, exponential decay. The white paper is designed to halve every 6 years. Generally speaking, the decay formula can be written as:

The above formula can be understood as: the initial token is N0, and as time goes by, the system releases it, and the calculation formula for the token amount N(t) that should be retained in the system at time point t is used.

Look here, the natural constant e appears again. Of course, we don't have to use e here. But since e is widely used, it is convenient to use. So basically this is a unified usage now.