Ratio Chain Research Institute | A Threshold Signature System under the Hypochronous Network Hypothesis

In recent years, threshold cryptography has gradually been applied in the blockchain system, which is divided into threshold encryption and threshold signature. It is generally found in random oracles, anti-censorship, reduction of communication complexity (HotStuff), and anti-Byzant in consensus networks (HoneyBadgerBFT). The common coin used in the BA link and the important primitives of the distributed pseudo-random number generator (coin tossing), its superior asset collaborative anti-theft feature is slowly being valued by the emerging digital asset custody mechanism. Today we mainly discuss Threshold signature mechanism in key cryptography (PKC). An ideal threshold signature system is capable of non-forgeability in an asynchronous network environment, and has an extremely reliable and secure message transmission channel. The generation and verification of signature shares is completely non-interactive. An asynchronous distributed key generation (DKG) mechanism that prevents Byzantine behavior during the initial key phase.

Similar to the basic signature mechanism, Threshold Signature Schemes are also divided into two parts:

Threshold Key Generation (Thresh-Key-Gen): Constructs a distributed key generation protocol DKG based on security parameters. The protocol runs a common public key pk and shares the private key shares of the different participants. A private key sk can be constructed from the private key share that satisfies the threshold number.

• Bitcoin developers: 51% of attacks are not terrible, terrible is the disregard of decentralization
• Introduction to Technology | Solidity Programming Language: Introduction to Basic Compilation Principles and Adding New Instructions
• Blockchain company SimplyVital Health receives a $225,000 grant from the National Science Foundation to help reduce medical costs

Threshold Signature (Thresh-Sig): Based on the distributed communication network, each participant completes the distributed collaborative signing of the message m through its own private key share ski and outputs the final verifiable signature Sig(sk, m). The same is true for the checkout with the sk private key, which can be verified locally using the verification function in the underlying signature mechanism, without the need for communication interaction verification.

However, in most cases, the generation and distribution of private key shares is achieved by using a trusted central node (dealer). Shamir Secret Sharing is the simplest method of threshold key generation relying on the central dealer node. The basic principle is Lagrangian interpolation. In the (t, n) threshold construction, the dealer will choose one (t- 1) The random polynomial f of the power, let f(0)=s, s be the secret value to be shared, and then distribute the point si=f(i) on the polynomial curve to each node as the respective secret share value. In simple terms, three points determine a Lagrange interpolation formula. In order to solve the problem of the center, people continue to explore the verifiable secret sharing (VSS, PVSS) based on commitment, and VSS applied to the asynchronous network (Cobalt BFT also tried to combine PoW access in the blockchain system. Mechanism of AVSS). There are many excellent mature commit schemes that can be used for reference. Simply put, the commit algorithm [C(M), D(M)]=Com(pk, M, r) is the public key associated with the commitment mechanism. M is the original value to be promised, r is a random dice, C is the commit of the algorithm, and D is the decommitment value that needs to be kept in secret. Before the official disclosure of M, the commitment C of M is disclosed, that is, the first is to be announced. The message is a God guarantee that it is impossible to replace M, and for M's audience or recipients, they can be verified for uniqueness through previously published commitments and verification algorithms. Here we focus on non-interactive VSS implementations.

In addition, in the past research, the generation and verification of signatures (Sig) are mostly interactive, and rely on a synchronous communication network and a broadcast channel. After receiving certain messages, the nodes receive certain messages. At the same time, the signature protocol is started and the timeout mechanism is strictly followed. In the Internet environment and blockchain network, the network assumptions are limited. Therefore, in order to successfully operate the threshold system, in addition to constructing the real DKG protocol and non-interactive signature mechanism, a commercial-grade network system is required. Verified mature code implementation. Here we (Bytom) try to propose and construct a threshold signature distributed system under the assumption of weak synchronization network, mainly carry out some innovative combination and application of network model, DKG construction and signature mechanism, and explore the least practical in the actual network environment. Threshold signature system prototype.

The threshold system is a (t, k, n) type fault-tolerance system, where t represents the maximum fault tolerance of the network, k represents the minimum threshold, and n is the number of nodes. Generally, k>=t+1 is set, but this pair The network partition is powerless, so in an asynchronous Byzantine network we still use the classic setting k=nt & t<n/3 to reach a majority consensus in the system.

Threshold networks or communication models are a key point in achieving a practical threshold system that requires careful consideration. Near-asynchronous communication networks built by HoneyBadgerBFT are rare in real-world cases, generally increasing message complexity and communication rounds. The asynchronous network model mainly relies on the type and number of messages received because of the time factor (time- Based) does not distinguish between who is a slow node and who is a malicious node. But here we are more inclined to adopt the efficient weak synchronization network hypothesis, that is, the message delay and clock offset have an upper limit (actually acceptable) but unknown, the gradual delay is reasonable, and the lifeness (safety can be handled by compromise); Can handle different situations such as crash, network failure, byzantine, etc., such as setting a crash threshold that can be tolerated within a specified time, recovering from a specified state after an honest node crashes; and assuming that the network fault can always be The repaired and suffered DoS attacks will always stop; finally, the TLS link can be built with the PKI and the external CA on the communication path, and the classic RBC protocol (reliable broadcast channel).

DKG is the core of the threshold signature and the first phase, responsible for the generation and distribution of threshold keys. VSS is an important part of DKG. The basic principle of VSS mentioned above is the commitment mechanism, which is generally based on Pedersen commitment, and the commitment to construct a shape such as C=mG+nH (here we have omitted some definitions and assumptions for elliptic curve group operation features, which can be simply understood as elliptic curve calculations. ), where m is derived from the key construction polynomial f(x) coefficient, and n is derived from the coefficient of a random polynomial h(x) constructed by the dealer, the commitment set {Ci, 0<i<t} is publicly available The coefficient "evidence" is used to prove that the dealer only recognizes a legal key polynomial. Each participant obtains f(i)G+h(i)H after obtaining the key share f(i) and the secret value share h(i) distributed by the dealer to itself, if the corresponding commitment value (polynomial calculation) If they are equal, they are considered to be legal. If they are inconsistent, they think that the dealer has committed a malicious act and began to submit their own protests to the network. Others can verify it. If it is found, the agreement will be stopped immediately. If other people verify that the complaint is not found, If it is legal, the node that initiated the complaint will be marked as untrusted. The VSS process consists of three parts: central initialization key distribution, build commitment and rebuild key. The entire network interaction has two rounds of all-to-all agreement, and finally the key share and Commitment is passed to each participating node, where we define three message types for marking multiple rounds of message sequences and carrying enough information to calculate the threshold key.

The real DKG is to remove the center in VSS, generate secrets under distributed collaboration, avoid the risk of single-point leakage, and the principle is very simple, which is equivalent to n nodes simultaneously selecting secret values ​​and running their own VSS, each The node collects the secret shares from other nodes to complete the assembly. The assembled result is the share of the real private key, and the secret values ​​distributed by each legal node are aggregated to be the final constructed private key, and finally the commitment verification is performed. This seems like a Multi-valued Validated Byzantine Agreement (MVBA) protocol (a widely studied consensus protocol algorithm that can be used to achieve high efficiency for multiple proposals, with multiple variants, such as the asynchronous common subset Common Subset) .

However, we try to avoid this complicated implementation, generally by electing the Leader node, uniformly coordinating the completion of these VSS and the final consensus, defining the sequence, when most nodes (nt) complete their respective VSS phases and are all other honest nodes. After confirmation, Leader collects and reorganizes these completed VSS information, and after two rounds of full-net broadcast, each node will determine their final secret share, so the guarantee of liveness is critical for our system. of. If there is malicious behavior on either side of the DKG Agreement, the agreement will cease immediately, ie DKG will need to ensure the integrity of all parties involved. At this point, a public threshold public key and a threshold private key share belonging to different participants are constructed.

The signing phase is simply based on the key shares obtained above, each signing its own signature share, and finally completing the unified assembly to obtain the final threshold signature. The specific implementation of the Thresh-Sig phase has a lot to do with the digital signature algorithm based on it. For example, the secret value k that the Schnorr algorithm relies on when calculating the signature s value is in the constant term, s=kz(H(K||M)) So you can simply group the secret value shares. The secret value k in ECDSA is non-linear, that is, s=(H(M)+zr)/k (where r is also obtained by exponential operation of k), and there are two multiplication operations of secret values ​​(k and z). Therefore, each node can not complete the assembly of the final signature value only by having the k secret value share. It needs to transform the formula, redefine the combined secret value kz, and distribute the secret share calculation and distribution of kz distributedly, even with the help of secure multiparty calculation. (Under the premise of not leaking the respective k and z shares, the result of kz is calculated and the secret share of kz is output to the corresponding party), the homomorphic encryption mechanism and the zero proof (range proof), so the multi-party ECDSA threshold signature is Implementation and efficiency will be more complicated, and at present, most of them can be studied with practical 2-2 programs.

Whether using ECDSA or Schnorr algorithm, the core problem is still based on the principles of DKG and multi-party computing to generate and distribute the secret values ​​needed in the signature algorithm. Each participant completes its own based on its own key share and secret value share. The signature process, and finally the final legal signature is obtained through the overall interactive assembly. Similarly, if a legitimate signer with a sufficient threshold threshold is not reached, the signature agreement will stop immediately. According to different application scenarios, we need to seriously study the underlying signature algorithms used to implement the threshold signature mechanism, such as ECDSA, EdDSA, Schnorr, BLS, etc. The threshold mechanism corresponding to different signature algorithms is different in complexity and efficiency.

In addition, a complete threshold system may have a need for member changes. The original key share will require a new round of changes. The most intuitive approach is to introduce the concept of a cycle and initiate a new round of confidentiality through a synchronous network and a consensus protocol. Key generation, generating new master and private key shares, and using a timeout mechanism to prevent blocking. Member changes and DKG are a more elaborate (or fragile) system, and any member fail or fault will cause a situation. In implementation, we use the state machine replication principle to build a threshold (DKG) node and replace its state based on message input (eg node_remove, leader_change, group_update).

Threshold cryptography has been increasing with the research of the application scenarios, and constantly improving its maturity, especially with the increase of highly reliable code implementation. With the maturity of the system architecture in complex network environments, it is hopeful to play the role of "gate gods" in the value network. The important role of this will also promote the further scenario application of zero-knowledge proof and homomorphic encryption technology. It is one of the few research areas in the current blockchain new technology field that deserves in-depth research and practical research. Modern cryptography and the value network complement each other. The former gives the latter "God's protection" and the latter gives the former a "great battlefield."

Liu Qiushan

We will continue to update Blocking; if you have any questions or suggestions, please contact us!