With The Emergence Of The Explosive Product Chia, The Mining Industry Has A More Innovative And People-friendly Gameplay, That Is, A Low-threshold Hard Disk Mining Method. This Mining Method Allows More And More Ordinary People To Participate In Mining. , Feel The Upsurge Of The Blockchain Industry Together.
According To Chia’s White Paper, The Consensus Mechanism Adopted By Chia Is Proof Of Space (Pos, Proof Of Space) And Proof Of Time (Pot, Proof Of Time). Pos Is Mainly Used To Prove That Users Do Have Unused Space For Storage, While Pot Is Used To Ensure The Security Of The Entire System. Its Main Algorithm Is Vdf Verifiable Delay Function, And The Calculation Result Obtained By Vdf Must After A Certain Period Of Time, It Can Be Quickly Authenticated By Any Node In The Network, Which Increases The Probability Of Pos Obtaining The Right To Produce Blocks.
Verifiable: After a certain number of calculations, the prover can quickly generate a small proof to prove the validity of the calculation, and the verifier can know the correctness of the calculation without repeating the calculation;
Delay: That is, the prover can get the correct result only after the correct number of calculations is performed, and there will be no situation where the correct result is obtained before the specified number of times;
Function: That is, the result is deterministic. Enter x and you will get y.
Calculation of VDF
Based on Chia’s design pattern, if the VDF calculation speed of a node is higher than that of other nodes, a certain security attack may be launched. Therefore, in order to avoid this threat, Chia hopes that the VDF algorithm running in the node is the most efficient, so there is basically no room for optimization. To this end, Chia also held two VDF efficiency competitions, attracting industry elites to participate in this event with high rewards, and widely absorbing everyone’s wisdom to obtain the most efficient VDF.
As shown in the figure above, the VDF algorithm used in Chia is actually very simple, that is, a continuous T-th square calculation is performed on a number x, where x is an element of a group of unknown order. Why is it an unknown group? The reason is also very simple:
If the order of the group is d, then according to the nature of the group: x2^T = x(2^T)% d
There Will Be Cases Where The Specified Number Of Times T Is Not Reached, And The Correct Result Will Be Obtained, Which Is Inconsistent With Chia’s Design; Therefore, The Order Of The Group Cannot Be Known; There Are Two Ways To Generate A Group Of Unknown Order:
Rsa-based Group;
Virtual Quadratic Domain Group;
When The Rsa-based Method Is Selected, The Order Of The Group N=pq, Where P And Q Are Both Very Large Prime Numbers And Cannot Be Disclosed. Therefore, The Difficulty Of Calculating The Order Of This Group Is As Difficult As Decomposing A Large Number N. Therefore, It Is Considered Safe, But This Method Requires Trusted Settings, That Is, P And Q Are Generated By A Trusted Third Party, Or Mpc May Also Be Used, But In Short, It Requires Trusted Settings;
The cluster based on the imaginary quadratic field can eliminate the credible setting, because a cluster generated by a negative large prime number that satisfies the relationship of |d|=3 mod 4, it is difficult to calculate its order (why it is difficult, will be in another article The detailed explanation involves many mathematical concepts, and I will try to write it as concise and easy to understand.) Since this large prime number can be made public, this method can easily generate groups of unknown order without credible settings.
After understanding the mathematical concepts behind it, let us look at how to calculate the square of the elements based on the imaginary quadratic field group, as shown in the following figure (algorithm refer to the NUDUPL paper):
The NUDUPL algorithm is by far the most effective method for calculating the square of the imaginary quadratic field. This is also the method that contestants choose most in the two VDF algorithm competitions. Figure 2 and Figure 3 show the two main branches of the algorithm, where m = (a,b,c) and M = (A,B,C) are all representations of elements in the group.
Proof of VDF
It can be seen from Figure 1 that in addition to T calculations, the prover also needs to generate a proof to prove the correctness of the calculation. Regarding the proof of the correctness of the VDF, two classic methods are given in this paper. Chia uses It is Wesolowski’s method of argumentation. The process of this method is shown in the figure below:
The algorithm itself is simple and easy to understand. Compared with the Pietrzak algorithm in the paper, this algorithm generates smaller proofs and verifies proofs faster.
Concluding remarks
After a period of research and testing, the VDF algorithm currently used by Chia is indeed quite efficient. From the algorithm, it has been unable to find a point that can be greatly optimized. “If the soft doesn’t work, then the hard” is one of the reasons why we still insist on studying Chia’s VDF algorithm very deeply. At present, we have started the hardware optimization design. In theory, VDF calculation with higher efficiency can achieve higher mining efficiency, which is also our goal.
