Blockchain circle

One stop hot information platform

About us:

Blockchain circle provides the latest information about blockchain, digital currency, digital wallet, exchange, metauniverse, bitcoin, Ethereum, contract, financial management and so on, and always pays attention to the latest market...

Ten thousand words long article details Trident:, Poseidon, hardware acceleration and implementation of hash algorithm!

Time : 03/06/2022 Author : q09xlf Click : + -
        Poseidon is a new hash algorithm for the design of zero knowledge proof (zkp) cryptographic protocol. Compared with similar algorithms, including the classic SHA-256, Sha-3 and Pedersen hash functions, Poseidon can significantly reduce the computational complexity of proof generation and verification in the application scenario of zero knowledge proof, and greatly improve the overall operation efficiency of the zero knowledge proof system. Based on the above advantages, Poseidon has been widely used in various blockchain projects, including decentralized storage system filecoin, cryptocurrency minaprotocol and dusknetwork, which are mainly used to accelerate the zero knowledge proof system.
 
        Where f represents a function or program, X represents the public input in the function, and W represents the function input that needs to be confidential, that is, only the certifier knows. In the zero knowledge proof system, the prover can prove the validity of the equation to the verifier without revealing W. It can be seen from the above description that the most significant feature of zero knowledge proof and its biggest advantage is privacy protection. The certifier can complete the proof of the calculation result of a function or program without disclosing any important private information. Because zero knowledge proof can give consideration to both computational integrity proof and privacy protection, it has a wide range of application scenarios, including anonymous online auction, anonymous electronic voting, cloud database SQL query verification, decentralized data storage system, etc.
 
        Especially in the field of blockchain and cryptocurrency, zero knowledge proof has won the favor of a large number of developers and designers in recent years with its excellent privacy protection characteristics, including cryptocurrencies zcash and Pinocchio, as well as distributed storage system filecoin. Zk-snark zero knowledge proof algorithm is adopted in its design. In order to ensure the universality of the proof algorithm, zero knowledge proof is usually not designed for a specific function F. If you need to verify the validity of the above formula, you need to convert the specific F function into the ConstraintSystem specified by the zero knowledge proof algorithm. This process can be understood as "program compilation", that is, the program to be proved is transformed into another program with the same function combined by the constraints.
 
        For example, for ZK snarks algorithm, it is necessary to convert the function to be proved into a program composed of a special quadratic polynomial r1cs (r1cs:rank-1 quadristicconstraints). The converted function form is also called arithmetic circuit. Both the prover and the verifier need to perform a series of arithmetic operations on the basis of this circuit to complete the proof generation and verification. Although zero knowledge proof can provide both computational integrity verification and privacy protection, its cost is to increase the computational complexity of proof generation and verification.
 
        At present, whether for the prover or the verifier to complete a zero knowledge proof, it needs to consume a lot of computing resources. Generally, the computational complexity of proof generation and verification is directly proportional to the complexity of the function to be proved after it is converted to the restricted expression system, that is, the number of restricted expressions contained in the conversion result. The number of restricted expressions generated by different functions to be verified after "compilation" is different, and the complexity of calculation and the corresponding proof generation and verification time are also very different. In blockchain applications, the function to be verified is usually related to a hash function. The Poseidon hash algorithm accelerated by Trident optimizes the zero knowledge proof, making its adaptability to the restricted expression system significantly better than similar algorithms.
 
        For example, the number of restricted expressions required after the conversion of Poseidon hash algorithm is about one eighth of that of similar Pedersen hash functions, which means that the amount of computation required for Poseidon to complete zero knowledge proof will be significantly reduced, and the efficiency of the whole zero knowledge proof system will also be greatly improved. The Poseidon accelerator implemented in Trident project is mainly aimed at the Poseidon hash calculation instance applied in filecoin distributed storage network. In the process of providing storage services, filecoin needs to perform Poseidon hash operation on data. This calculation process requires a lot of computing power, which is one of the performance bottlenecks of the entire filecoin system.
 
        Filecoin is a decentralized, distributed, open source cloud storage network based on blockchain technology. Its main network has been running smoothly for a year, and shows the characteristics of high speed, low cost and stability. Because of its open source and decentralized advantages, filecoin has been widely used, including the famous Wikipedia, which has stored its website database on the filecoin network. There are two main roles in filecoin, namely, user (client) and miner. Its basic operation mechanism is that the client sends out the demand for data storage or retrieval and pays the document currency, while the miner obtains the corresponding reward by providing storage service and retrieval service.
 
        Unlike the traditional cloud storage services provided by the data center, any device with idle storage resources can provide storage services on the filecoin network. Therefore, in order to ensure the quality of storage services, filecoin has designed mechanisms including replication proof porep (proofofreplication) and spatiotemporal proof post (proofofspacetime) to ensure the integrity and durability of data storage, and these mechanisms involve a large number of cryptographic algorithms, including hash algorithm SHA-256 and Poseidon and zero knowledge proof ZK Snark, which need a lot of computational support.
 
        At present, these algorithms are mainly based on GPU to achieve computing acceleration, and there is no related open-source FPGA hardware acceleration scheme. At present, the most widely used filecoin software implementation is lotus written by protocollabs based on go language. Lotus can be understood as an interface between users and the entire filecoin storage network. Specifically, lotus is a command-line application running on the Linux operating system. Its functions include: 1) uploading and downloading files; 2) Lease the free storage space to other users; 3) Check the integrity of the data stored in the computer.
 
        At the same time, lotus provides a benchmark program lotus bench for testing the performance of computer hardware under filecoin computing load. Based on Poseidon acceleration circuit, Trident project provides lotus with a software interface to access the underlying FPGA hardware accelerator, and then tests and compares the computing performance of the accelerator through lotus bench. To be exact, Poseidon refers to a set of hash functions optimized for zero knowledge proof algorithm with similar calculation process. By analogy with the object-oriented concept in programming language, Poseidon can be understood as a hash function class, which requires several basic initialization parameters.
 
        In the application process, you need to initialize these basic parameters to generate specific hash calculation instances. The Poseidon instances corresponding to different parameter combinations are basically similar in the calculation process, but there are some differences in security, calculation amount and complexity. The basic parameters required for the initialization of Poseidon hash function class are (P, m, t). From these three parameters, a unique hash calculation instance can be determined. The actual bit width of parameter p is 255 bits, and all arithmetic operations in the hash function are completed in the finite field determined by P, that is, all arithmetic operations are modular operations with modulus P, including 255 bit modular addition and 255 bit modular multiplication; At the same time, parameter P also determines the exponent of modular power operation in S-box stage &alpha= 5;。
 
        From the perspective of input and output, the Poseidon hash function maps the input (T1) finite field elements to an output finite field element. For the filecoinposeidon instance accelerated by this topic, the parameter t∈ {3,5,9,12}, so the number of elements contained in its input data can be 2, 4, 8 or 12, and the output is an element. Since the bit width of parameter p is 255 bits, the bit width of input and output finite field elements is also 255 bits. 5. Output: after completing a total of (rf+rp) cycles in steps 1-4, output the second element in the state vector as the result of hash operation;.
 
        As mentioned above, Poseidon can be regarded as a collection of similar hash function instances. The common features of this kind of hash function calculation process include:. The above four points briefly summarize the characteristics of the whole Poseidon hash calculation, and are also several places that need to be considered in the design and implementation of hardware accelerator. The second section of this chapter will further introduce the Poseidon hash function in combination with the detailed calculation process. The Trident project adopts the scala based hardware generator language spinahdl and the Python based verification framework cocotb to complete the design and verification of the entire Poseidon accelerator IP.
 
        These two new hardware design and verification tools have greatly improved the development efficiency and quality of the accelerator. For developers, spinalhdl can usually be divided into two parts: Scala syntax and circuit component abstraction provided by spinalhdl. Spinalhdl provides abstractions of various basic circuit elements required for hardware design in the form of classes and functions in scala syntax, including registers, logic gates, multiplexers, decoders, arithmetic circuits, etc. What the circuit designer needs to do is to describe the overall structure of the circuit based on Scala syntax, that is, to describe the connection relationship between the basic circuit components.
 
        Because Scala is a multi paradigm programming language, it supports functional programming, object-oriented, recursive and other advanced language features, and can give designers powerful structural modeling ability and code parameterization ability. Use designcompiler or vivadosynthesis to synthesize the RTL code that has passed the functional verification, and generate the corresponding netlist file and the timing, area, power consumption and other information of the circuit. If the synthesis result does not meet the design requirements, return to step 1 to further optimize the circuit structure. Cocotb is an open source digital circuit verification framework based on python. The specific working mode of this verification framework is shown in the figure below.
 
        The circuit verification based on cocotb can be divided into the following two parts:. 1. The test platform code written based on Python: it is completed in parallel based on coroutine in Python: generate the excitation signal at the input of the circuit to be tested; The same excitation signal is transmitted to the reference model to obtain the standard output; Monitor the output port of the circuit to be tested and check whether the output result is consistent with the standard output;. 2. Circuit simulator supporting standard GPI programming interface: receive the input excitation signal generated by Python test code through GPI programming interface, and conduct functional simulation of the circuit to be tested DUT (dut:designundertest).
 
        Using cocotb for circuit function simulation does not need to write additional Verilog or VHDL code. All the work in the test, including generating input excitation signals, implementing the reference model and monitoring the output results, can be completed in Python code, which can interact with the circuit to be tested through the GPI programming interface provided by the simulator. With Python's efficient and concise syntax and powerful ecosystem, verifiers can realize the logical functions of verification code more quickly and accelerate the iteration speed of hardware design. The first section of this chapter mentioned that for developers, spinalhdl can be divided into Scala syntax and circuit component abstraction provided by spinalhdl, and its advantages in circuit design mainly come from these two aspects.
 
        From the perspective of Scala, its high-level language features, including functional programming, object-oriented and recursion, can provide designers with powerful circuit modeling capabilities. From the perspective of spinalhdl itself, the rich circuit abstraction it provides enables developers to avoid the repeated implementation of some common circuit modules, so that they can describe circuits from a higher level of abstraction. The following will describe in detail the four advantages of spinalhdl in circuit design:. Digital circuit modeling can usually be divided into behavior level and structure level. For example, Verilog and VHDL describe the circuit from the structure level, while HLS (high level synthesis) first describes the algorithm behavior through high-level programming language, and then converts it into the RTL code of the corresponding circuit.
 
        In most cases, behavior level modeling can complete circuit design more efficiently, but the circuit obtained in this way is often difficult to meet the requirements of designers in terms of performance and resource consumption. Unlike high-level integrated HLS, spinalhdl is also designed based on high-level programming language Scala, but its essence is still to describe the circuit from the structure level. For developers, if they do not use the high-level language features in scala and the circuit models with high abstraction level in spinalhdl, such as FIFO, counter and bus arbiter, they can model the circuit like Verilog.
 
        Using spinalhdl for circuit description can improve the reliability of design and significantly reduce the probability of code error. The improvement of code reliability can not only reduce the pressure of circuit verification, but also help the later code maintenance. Spinalhdl's powerful modeling and expression of circuits stems from the rich high-level language features provided by Scala, including functional programming, object-oriented and recursion. In addition, the rich circuit abstraction provided by spinalhdl enables developers to avoid the repeated implementation of many underlying modules, and then build circuits from a higher level. Spinalhdl not only provides basic circuit elements such as signals, logical operators, arithmetic operators and registers, but also realizes higher-level circuit models such as FIFO, Axi bus, counters and state machines.
 
        In addition to more powerful circuit modeling capabilities, spinalhdl can also bring changed reusability to hardware design code. The problems that hardware design needs to deal with are often highly customized, and verilo
 
        
Previous:My world announced that it does not support blockchain and NFT
Next:No more

Related articles:



© 2005-2032 | Blockchain Circle & & All Rights Reserved    Sitemap1 Sitemap2 If there is infringement, please contact us at: