This article understands the characteristics of the threshold signature and its application in the blockchain field.
Written by: Cobo Cryptography Team
This lecture will be divided into four parts to introduce the concept and application of threshold signature: the first part introduces the concept and classification of digital signature, and explains its basic algorithm composition and application functions; the second part focuses on the single point failure risk of digital signature Introduce the concept of threshold signature, and introduce its technical advantages and characteristics; the third part compares threshold signature and multi-signature, and expounds the advantages of threshold signature in terms of flexibility, anonymity and scalability, which is why it can become today's password Finally, it introduces the typical application of threshold signature in the blockchain field, showing how it can empower different application scenarios and generate core value.
Part 1: The concept and classification of digital signatures
A digital signature is not a digitization of a signature
In the early society, handwritten signatures and seals were usually used to sign contracts, documents, treaties, etc., but after the emergence of computer networks, how to sign electronic documents and electronic documents became an urgent problem to be solved, and the strong application requirements also gave birth to The solution to the problem - digital signatures.
Digital signature is a new type of message signature method that is different from traditional handwritten signatures and is transmitted or stored in electronic form. It is not "digitalization of handwritten signatures". At the academic level, **digital signature refers to an algorithm scheme that can verify the integrity of data for the receiver and confirm the identity of the sender of the data, and allow a third party to determine the authenticity of the signature and the signed data. **
Five-tuple representation of digital signature
By abstracting and formalizing the operation principle of digital signatures, the five-tuple representation of digital signatures can be obtained, namely (M, K, S, SIG, VER):
M: message collection, generally the hash digest of the signed object;
K: key set, that is, the range of keys that digital signatures can use, generally a set of 256-bit random numbers;
S: signature set, the output of the signature algorithm, which can be verified by the verification algorithm;
SIG: Signature algorithm, defined as K×M→S, takes message and key as input, and outputs signature;
VER: Verification algorithm, defined as MS{True, False}, to verify the consistency of the message and the signature. Of course, this process also requires the input of the public key corresponding to the signature key.
Classification of digital signatures
Digital signatures can be classified by different dimensions, such as based on mathematical problems, number of signing users, whether the digital signature is recoverable, whether the signer is visible to the message, whether the signature supports delegation, etc. See the figure below for details.
Currently common digital signatures include Shamir backpack digital signature, Rabin digital signature, GOST digital signature, ElGamal digital signature, Schnorr digital signature, RSA digital signature, ECDSA digital signature, BLS digital signature, etc.
Part 2: The birth and technical characteristics of the threshold signature
The Achilles heel of digital signatures
Achilles is the hero in Homer's epic. He is invincible and fearless on the battlefield. However, such a powerful warrior also has his Achilles' heel - his ankle, and his final death is also due to an arrow in his ankle. The same principle also applies to digital signatures. As a powerful cryptographic tool, it can prevent forgery and non-repudiation, but all of this is based on the security of the private key of the signature. Once the private key is leaked, the attacker Malicious acts such as identity forgery and unauthorized access will be easily completed. **
Under the traditional digital signature scheme, the private key of the signature is held by a single subject, which is usually stored through encryption or hardware protection (USB shield), but there are still great risks in use.
Security of the private key: The attacker can invade the signer's computer through network attack, even if it is encrypted and stored, it can also grab the private key in the memory during the signing process, thereby stealing the signing key;
Availability of private key: Whether it is hardware or software storage, there is a single point of failure risk (Single Point of Failure). Once the signature private key is lost, it will not be restored.
Threshold Signature - Eggs are never put in a cage
Threshold signature is the solution to the security risk of centralized control of digital signature private key. The core idea is that the private key is no longer held by a single node, but split into multiple fragments and held by multiple nodes, so as to achieve high security and availability of the private key. Specifically, the threshold signature is the result of the "thresholding" of ordinary digital signatures, which distributes the power of signatures to a group of nodes, and only needs the cooperation of nodes exceeding the threshold value to complete the generation of signatures. Therefore, it can be considered that the signature process of the ordinary digital signature algorithm is "centralized", while the signature process of the threshold signature algorithm is "distributed".
Algorithm composition of threshold signature
The signature generated by the threshold signature algorithm is consistent and indistinguishable from the common signature algorithm, and the signature verification process of the two is the same. Therefore, for the threshold signature algorithm, the focus of attention lies in its key generation process KeyGen and signature process TSig. A (t,n) threshold signature algorithm includes the following two processes:
KeyGen: Take security parameters as input, output signature public key pk and n private key fragments (sks1, sks2,..., sksn). Each private key fragment sksi is only mastered by node Pi, and n private key fragments together constitute the (t,n) secret sharing of the signature private key sk. It should be noted that sk is only a theoretical existence and will not appear in the key generation or signature process;
TSig: Take the message to be signed and no less than t private key fragments as input, and output a legal signature.
Part 3: Comparison and advantages of threshold signature and multi-signature
In addition to threshold signatures, another way to prevent single-point failure is multi-signature (Multi-signature). Simply speaking, under the multi-signature mechanism, there is no longer one public key for signing, but multiple public keys. Only when the number of signatures exceeding the threshold is collected is the signature successful. Although multi-signature can achieve the equivalent application value of threshold signature in a certain sense, threshold signature still has advantages in three aspects of flexibility, anonymity and scalability. The following will explain these three advantages from the perspective of blockchain:
Flexibility
In the multi-party management process of the account, the flexibility of multi-signature is significantly lower than that of threshold signature, which is reflected in two aspects: first, under the multi-signature mechanism, the public key of the signer and other information jointly determine the account address. Once the control logic of the account If there is a change (such as adding or reducing signers), the account address will change, and funds need to be transferred from the old account address to the new account address, which is less flexible; secondly, in Bitcoin, the number of multi-signature public keys There is an upper limit requirement, so multi-party account management scenarios exceeding the upper limit cannot use multi-signature.
Under the threshold signature mechanism, the change of the identity of the signer will be reflected in the redistribution and generation (Reshare) of the private key share of the account, and the account address will not change; at the same time, n and t in the threshold signature can be set arbitrarily. There are any restrictions, and any scene requirements can be supported.
Anonymity
A core feature of the blockchain is anonymity, that is, there is no one-to-one correspondence between the account address on the chain and the real identity. However, the use of multi-signature will lead to a sharp decrease in user anonymity, which is reflected in two aspects: First, although the account address on the chain cannot be one-to-one with the real identity, its related transactions are publicly visible, and multi-signature Under the mechanism, the public key of each signer is exposed, so different accounts will be associated through the public signer, resulting in the destruction of account privacy and anonymity; secondly, the exposure of the multi-signature public key set, and The number of signatures attached to the complete transaction can effectively deduce the control logic of the account, and even link the account behavior with the real business, reducing anonymity.
Under the threshold signature mechanism, the final generated transaction is consistent and indistinguishable from the ordinary transaction data structure, and the signing process is completed off-chain, which does not lead to any anonymity risk.
Scalability
Under the multi-signature mechanism, the digital signatures of all signers need to be attached to the final blockchain transaction, so the transaction size and the number of signers have a linear growth relationship. Therefore, the more complex the control logic (such as the increase in the number of signers), the larger the data volume of the final transaction. This feature leads to two consequences: First, the blockchain transaction fee is linked to the transaction size, so the use of multiple signatures will lead to higher transaction fees and increase its cost of use, which is not suitable for some high-frequency business scenarios; Secondly, the increase in transaction space will also increase the operating load of the entire blockchain, indirectly reducing the operating efficiency of the system.
The threshold signature does not have this concern at all, because its final output is consistent with ordinary digital signatures, but in the signature process, each node needs to carry out relevant communication and calculation.
Specifically, under the threshold signature mechanism, the data structure of the transaction still only contains one signature, which is no different from ordinary transactions, so the transaction fee is lower and will not add additional burden to the blockchain system.
Part 4: The application of threshold signature in the field of blockchain
Ensure blockchain account security
In recent years, encrypted digital currency represented by Bitcoin has developed rapidly, and gradually entered the lives of ordinary people as an emerging means of payment. Unlike traditional payment systems, encrypted digital currency systems do not have a centralized operating organization, and all payment operations are completed by sending transactions with digital signatures from accounts. Therefore, the security of the cryptocurrency account is equivalent to the security of the signature private key, and the leakage of the private key will directly lead to the theft of assets in the account. However, the security of users' encrypted digital currency accounts is facing a huge threat: Hackers send emails with Trojan horses to control users' computers, steal account private keys, and then send transactions to transfer the cryptocurrencies in them to exchanges for sale for profit. Therefore, it is imminent to ensure the security of encrypted digital currency accounts.
Threshold signature algorithm is an effective means to ensure the security of encrypted digital currency accounts. The private key of the user account is no longer generated and stored by a single node, but an account address is generated by cooperation of n nodes, and each node stores a fragment of the private key of the account. When sending a transaction, one of the nodes constructs the transaction content and sends it to other nodes. All nodes then run the Threshold Signature Algorithm and cooperate to generate a legal signature for the transaction. Finally, a node broadcasts the signed transaction to the blockchain network. The attacker needs to successfully attack at least t nodes to recover the account private key. Users can flexibly determine the value of the total number of nodes n and the safety threshold t according to actual needs. Therefore, the threshold signature algorithm can effectively improve the security of encrypted digital currency accounts.
Cross-chain asset lock
Cross-chain technology can enable the free flow of digital assets on different blockchains and break the information islands between different blockchains. An important premise in the cross-chain process is "asset conservation", that is, when digital assets are transferred from one blockchain to another, the digital assets of the original blockchain need to be locked. In order to ensure decentralization, asset locking is often completed by a group of nodes, and unlocking can only be completed if more than a certain number of nodes cooperate.
For blockchains that support smart contracts such as Ethereum and EOS, it is only necessary to write the logic of asset locking as a smart contract, and the user can transfer assets to this specific contract to complete the locking. For blockchains such as Bitcoin that do not support smart contracts, asset locking relies on the establishment of a multi-party custody locking account, and the user transfers assets to this account to complete the locking.
As introduced in the third part, although multi-signatures can also complete multi-party custody of accounts, the advantages of threshold signatures in flexibility, anonymity and scalability are more suitable for cross-chain asset locking scenarios. In terms of flexibility, the values of n and t can be set arbitrarily to meet the needs of different scenarios; in terms of anonymity, the locked account generated by the threshold signature algorithm is exactly the same as the normal account in terms of data structure and usage, and legal signatures cannot expose participating signatures. Process node information; In terms of scalability, each transaction is consistent with ordinary transactions, and only needs to carry a digital signature, which reduces transaction costs.
Design of consensus mechanism
In Byzantine-like (BFT) consensus protocols, consensus nodes need to vote on the content to be agreed upon, and a consensus is reached if the vote exceeds a certain percentage (such as two-thirds). During the algorithm process, "voting" needs to verify the identity of the voter and prevent replay attacks. The solution adopted is to digitally sign the consensus content and then broadcast it. Analyzing the entire consensus process, its core logic is very consistent with the threshold signature, that is, the consensus/signature is successful if the node approval exceeds a certain threshold. Therefore, instead of the consensus nodes needing to collect a sufficient amount of signature information in the network, it is better to construct a common public key based on the threshold signature, and then each consensus node has a private key fragment, and the recognition of the consensus content is to calculate the signature fragment with the private key fragment , the participation of consensus nodes exceeding the threshold can obtain a complete digital signature. This design pattern can effectively reduce the space occupied by consensus results.
View Original
The content is for reference only, not a solicitation or offer. No investment, tax, or legal advice provided. See Disclaimer for more risks disclosure.
Popular Science｜The Concept and Application of Threshold Signature
Written by: Cobo Cryptography Team
This lecture will be divided into four parts to introduce the concept and application of threshold signature: the first part introduces the concept and classification of digital signature, and explains its basic algorithm composition and application functions; the second part focuses on the single point failure risk of digital signature Introduce the concept of threshold signature, and introduce its technical advantages and characteristics; the third part compares threshold signature and multi-signature, and expounds the advantages of threshold signature in terms of flexibility, anonymity and scalability, which is why it can become today's password Finally, it introduces the typical application of threshold signature in the blockchain field, showing how it can empower different application scenarios and generate core value.
Part 1: The concept and classification of digital signatures
A digital signature is not a digitization of a signature
In the early society, handwritten signatures and seals were usually used to sign contracts, documents, treaties, etc., but after the emergence of computer networks, how to sign electronic documents and electronic documents became an urgent problem to be solved, and the strong application requirements also gave birth to The solution to the problem - digital signatures.
Digital signature is a new type of message signature method that is different from traditional handwritten signatures and is transmitted or stored in electronic form. It is not "digitalization of handwritten signatures". At the academic level, **digital signature refers to an algorithm scheme that can verify the integrity of data for the receiver and confirm the identity of the sender of the data, and allow a third party to determine the authenticity of the signature and the signed data. **
Five-tuple representation of digital signature
By abstracting and formalizing the operation principle of digital signatures, the five-tuple representation of digital signatures can be obtained, namely (M, K, S, SIG, VER):
Classification of digital signatures
Digital signatures can be classified by different dimensions, such as based on mathematical problems, number of signing users, whether the digital signature is recoverable, whether the signer is visible to the message, whether the signature supports delegation, etc. See the figure below for details.
Currently common digital signatures include Shamir backpack digital signature, Rabin digital signature, GOST digital signature, ElGamal digital signature, Schnorr digital signature, RSA digital signature, ECDSA digital signature, BLS digital signature, etc.
Part 2: The birth and technical characteristics of the threshold signature
The Achilles heel of digital signatures
Achilles is the hero in Homer's epic. He is invincible and fearless on the battlefield. However, such a powerful warrior also has his Achilles' heel - his ankle, and his final death is also due to an arrow in his ankle. The same principle also applies to digital signatures. As a powerful cryptographic tool, it can prevent forgery and non-repudiation, but all of this is based on the security of the private key of the signature. Once the private key is leaked, the attacker Malicious acts such as identity forgery and unauthorized access will be easily completed. **
Under the traditional digital signature scheme, the private key of the signature is held by a single subject, which is usually stored through encryption or hardware protection (USB shield), but there are still great risks in use.
Threshold Signature - Eggs are never put in a cage
Threshold signature is the solution to the security risk of centralized control of digital signature private key. The core idea is that the private key is no longer held by a single node, but split into multiple fragments and held by multiple nodes, so as to achieve high security and availability of the private key. Specifically, the threshold signature is the result of the "thresholding" of ordinary digital signatures, which distributes the power of signatures to a group of nodes, and only needs the cooperation of nodes exceeding the threshold value to complete the generation of signatures. Therefore, it can be considered that the signature process of the ordinary digital signature algorithm is "centralized", while the signature process of the threshold signature algorithm is "distributed".
Algorithm composition of threshold signature
The signature generated by the threshold signature algorithm is consistent and indistinguishable from the common signature algorithm, and the signature verification process of the two is the same. Therefore, for the threshold signature algorithm, the focus of attention lies in its key generation process KeyGen and signature process TSig. A (t,n) threshold signature algorithm includes the following two processes:
Part 3: Comparison and advantages of threshold signature and multi-signature
In addition to threshold signatures, another way to prevent single-point failure is multi-signature (Multi-signature). Simply speaking, under the multi-signature mechanism, there is no longer one public key for signing, but multiple public keys. Only when the number of signatures exceeding the threshold is collected is the signature successful. Although multi-signature can achieve the equivalent application value of threshold signature in a certain sense, threshold signature still has advantages in three aspects of flexibility, anonymity and scalability. The following will explain these three advantages from the perspective of blockchain:
Flexibility
In the multi-party management process of the account, the flexibility of multi-signature is significantly lower than that of threshold signature, which is reflected in two aspects: first, under the multi-signature mechanism, the public key of the signer and other information jointly determine the account address. Once the control logic of the account If there is a change (such as adding or reducing signers), the account address will change, and funds need to be transferred from the old account address to the new account address, which is less flexible; secondly, in Bitcoin, the number of multi-signature public keys There is an upper limit requirement, so multi-party account management scenarios exceeding the upper limit cannot use multi-signature.
Under the threshold signature mechanism, the change of the identity of the signer will be reflected in the redistribution and generation (Reshare) of the private key share of the account, and the account address will not change; at the same time, n and t in the threshold signature can be set arbitrarily. There are any restrictions, and any scene requirements can be supported.
Anonymity
A core feature of the blockchain is anonymity, that is, there is no one-to-one correspondence between the account address on the chain and the real identity. However, the use of multi-signature will lead to a sharp decrease in user anonymity, which is reflected in two aspects: First, although the account address on the chain cannot be one-to-one with the real identity, its related transactions are publicly visible, and multi-signature Under the mechanism, the public key of each signer is exposed, so different accounts will be associated through the public signer, resulting in the destruction of account privacy and anonymity; secondly, the exposure of the multi-signature public key set, and The number of signatures attached to the complete transaction can effectively deduce the control logic of the account, and even link the account behavior with the real business, reducing anonymity.
Under the threshold signature mechanism, the final generated transaction is consistent and indistinguishable from the ordinary transaction data structure, and the signing process is completed off-chain, which does not lead to any anonymity risk.
Scalability
Under the multi-signature mechanism, the digital signatures of all signers need to be attached to the final blockchain transaction, so the transaction size and the number of signers have a linear growth relationship. Therefore, the more complex the control logic (such as the increase in the number of signers), the larger the data volume of the final transaction. This feature leads to two consequences: First, the blockchain transaction fee is linked to the transaction size, so the use of multiple signatures will lead to higher transaction fees and increase its cost of use, which is not suitable for some high-frequency business scenarios; Secondly, the increase in transaction space will also increase the operating load of the entire blockchain, indirectly reducing the operating efficiency of the system.
The threshold signature does not have this concern at all, because its final output is consistent with ordinary digital signatures, but in the signature process, each node needs to carry out relevant communication and calculation.
Specifically, under the threshold signature mechanism, the data structure of the transaction still only contains one signature, which is no different from ordinary transactions, so the transaction fee is lower and will not add additional burden to the blockchain system.
Part 4: The application of threshold signature in the field of blockchain
Ensure blockchain account security
In recent years, encrypted digital currency represented by Bitcoin has developed rapidly, and gradually entered the lives of ordinary people as an emerging means of payment. Unlike traditional payment systems, encrypted digital currency systems do not have a centralized operating organization, and all payment operations are completed by sending transactions with digital signatures from accounts. Therefore, the security of the cryptocurrency account is equivalent to the security of the signature private key, and the leakage of the private key will directly lead to the theft of assets in the account. However, the security of users' encrypted digital currency accounts is facing a huge threat: Hackers send emails with Trojan horses to control users' computers, steal account private keys, and then send transactions to transfer the cryptocurrencies in them to exchanges for sale for profit. Therefore, it is imminent to ensure the security of encrypted digital currency accounts.
Threshold signature algorithm is an effective means to ensure the security of encrypted digital currency accounts. The private key of the user account is no longer generated and stored by a single node, but an account address is generated by cooperation of n nodes, and each node stores a fragment of the private key of the account. When sending a transaction, one of the nodes constructs the transaction content and sends it to other nodes. All nodes then run the Threshold Signature Algorithm and cooperate to generate a legal signature for the transaction. Finally, a node broadcasts the signed transaction to the blockchain network. The attacker needs to successfully attack at least t nodes to recover the account private key. Users can flexibly determine the value of the total number of nodes n and the safety threshold t according to actual needs. Therefore, the threshold signature algorithm can effectively improve the security of encrypted digital currency accounts.
Cross-chain asset lock
Cross-chain technology can enable the free flow of digital assets on different blockchains and break the information islands between different blockchains. An important premise in the cross-chain process is "asset conservation", that is, when digital assets are transferred from one blockchain to another, the digital assets of the original blockchain need to be locked. In order to ensure decentralization, asset locking is often completed by a group of nodes, and unlocking can only be completed if more than a certain number of nodes cooperate.
For blockchains that support smart contracts such as Ethereum and EOS, it is only necessary to write the logic of asset locking as a smart contract, and the user can transfer assets to this specific contract to complete the locking. For blockchains such as Bitcoin that do not support smart contracts, asset locking relies on the establishment of a multi-party custody locking account, and the user transfers assets to this account to complete the locking.
As introduced in the third part, although multi-signatures can also complete multi-party custody of accounts, the advantages of threshold signatures in flexibility, anonymity and scalability are more suitable for cross-chain asset locking scenarios. In terms of flexibility, the values of n and t can be set arbitrarily to meet the needs of different scenarios; in terms of anonymity, the locked account generated by the threshold signature algorithm is exactly the same as the normal account in terms of data structure and usage, and legal signatures cannot expose participating signatures. Process node information; In terms of scalability, each transaction is consistent with ordinary transactions, and only needs to carry a digital signature, which reduces transaction costs.
Design of consensus mechanism
In Byzantine-like (BFT) consensus protocols, consensus nodes need to vote on the content to be agreed upon, and a consensus is reached if the vote exceeds a certain percentage (such as two-thirds). During the algorithm process, "voting" needs to verify the identity of the voter and prevent replay attacks. The solution adopted is to digitally sign the consensus content and then broadcast it. Analyzing the entire consensus process, its core logic is very consistent with the threshold signature, that is, the consensus/signature is successful if the node approval exceeds a certain threshold. Therefore, instead of the consensus nodes needing to collect a sufficient amount of signature information in the network, it is better to construct a common public key based on the threshold signature, and then each consensus node has a private key fragment, and the recognition of the consensus content is to calculate the signature fragment with the private key fragment , the participation of consensus nodes exceeding the threshold can obtain a complete digital signature. This design pattern can effectively reduce the space occupied by consensus results.