PyFrost TSS Protocol
This document provides an in-depth overview of the protocols integrated into PyFrost, specifically focusing on the Distributed Key Generation (DKG) and signing procedures. PyFrost adopts a single-round standard FROST protocol for its signing operations, enhancing the security and efficiency of the process. Additionally, a customised variant of the FROST protocol is employed in the context of DKG to detect and address potential malicious behaviour where cheating entities abort to share secrets selectively with some honest players to exclude them from the DKG process. This modification enhances PyFrost DKG mechanism, ensuring immunity against all kinds of malicious activities.
To achieve a verified data set without relying on a single source, verifications must be done by multiple players. Verifications done by multiple players raise the concern of one or a few of them going down and not providing their verifications. To address the problem above, a threshold number of players must verify the data set for it to be considered verified and usable.
Implementing a t out of n verification structure is often done by Multisig contracts. In these contracts, verifying a data set requires t signatures in a single or t number of transactions, where each signature must be verified individually. This verification is t times more costly than verifying a single signature on a blockchain. This high cost prevents approaching higher t to promote decentralisation.
Threshold Signature is an alternative method to the above approach that enables t out of n players to sign a data set in a way that can be verified at the cost of a single verification. This method entails t out of n players collaborating off-chain to produce a single signature regardless of the number of players.
To achieve the above, a private key must be shared among n players so that t players can make up the whole key together and produce a signature. But how do we make this sharing?
One way to share a secret private key among n players and have t of them able to find it is using the Shamir Secret Sharing method. Using this method, a random polynomial f(x) = a0 + a1x + a2x2+ … + at-1xt-1 is created where f(0) or a0 is the secret to be shared and then n points of it are distributed among n players. Polynomials of degrees t - 1 can be fully reconstructed if t points of them are spotted.
Let's assume we want to share a secret number between 3 players where any 2 of them could find the secret number by collaborating together. For that, we can make a 1-degree polynomial f(x) = ax + b, where b is a secret number to be shared, and a is a random number. If f(1), f(2) and f(3) are calculated and privately shared among 3 players, only 2 them are enough to collaborate and reconstruct the whole graph, and therefore, its cross point with the Y axis, that is, the secret number or b.
A 1-degree polynomial can be reconstructed by having 2 points, like two dots on a line. Similarly, a 2-degree polynomial needs only three points to be reconstructed. And so forth and so on. That way, any t - 1 polynomial can be reconstructed if the t number of its points is spotted.
Reconstruction could be done with Lagrange Interpolation, which provides a mathematical formula that helps reconstruct the complete polynomial of t - 1 degree if t points are provided.
Suppose we have a 2-degree polynomial f(x) where f(2) = 1942, f(4) = 3402, and f(5) = 4414 and we aim to reconstruct the whole polynomial. With Lagrange Interpolation, we calculate three basis 2-degree polynomials with the following formula:
For instance, for the three points mentioned above where x = (2, 4, 5), the three basis polynomials are calculated as follows:
Then multiply the Y property of each point by its corresponding basis formula and sum up all three results to calculate the complete polynomial.
Accordingly, we will have the following polynomial:
This is the polynomial where f(2)=1942, f(4)=3402, and f(5)=4414. Having the complete polynomial passing these 3 points, we can now calculate f(0)=1234 which is the secret key that is shared between the three players.
The risk to Shamir Secret Sharing is that a single player has access to the whole private key before it is shared among other players. This is due to the private key being available in the hands of the dealer who is responsible for sharing it before sharing it among players. But can we generate the key in a way that is not accessible as a whole by any single player at no point in time?
A typical approach to achieve the above is Pedersen's Distributed Key Generation protocol. In this protocol, each n player produces a polynomial individually and shares it with others by the Shamir Secret Sharing method. A polynomial is then formed by summing up all these individually produced polynomials. This summed-up polynomial is accessible to no single player. But, if each of the n players has a point on it, t of them can figure it out as a whole. But how so?
For instance, consider players 1, 2 and 3 and have them produce and privately hold the polynomials f(x), g(x), and h(x), respectively. And, s(x) is the summed-up polynomials.
For player 1 to calculate s(1), he calculates f(1) and then privately receives g(1) and h(1) from players 2 and 3. By summing up all these values, he then calculates s(1) = f(1) + g(1) + h(1)
Players 2 and 3 also go through a similar process to calculate s(2) and s(3).
We now have three players who have a point of the summed-up polynomial, and, even though none of them has it as a whole, only 2 of them can reconstruct it completely by collaborating.
The exact process stands for sharing a t - 1 degree polynomial between N players so that t of them can use the Lagrange Interpolating method to reconstruct it.
What if instead of producing a polynomial f(x) of t - 1 degree and sharing f(i) with player i, a malicious player shares some junk data with other players to prevent the formation of a consistent summed-up polynomial of t - 1 degree? A successful attack in the above scenario results in different combinations of t players producing different polynomials in their collaboration to reconstruct the whole. Feldman’s Scheme for Verifiable Secret Sharing is a typical approach to stop such attacks.
In this scheme, all nodes must produce a public commitment based on the randomly produced polynomial of t - 1 degree. These commitments that are assumed to be visible by all players enable them to verify that the f(i) they receive is calculated based on the public commitment.
The public commitment disables the production of inconsistent DKGs and enables the detection of malicious players.
An alarming concern in the scenario is a player sharing different commitments with different players. There are two ways to address this concern.
One way is to have an additional round where players share all commitments they have received from each player with others so that all players can verify their consistency. A risk is that a malicious player might share invalid commitments and wrongly claim that they have received them from others. Requiring a signature of the issuer on each commitment prevents such an attack.
We could also take another approach to prevent inconsistent commitments and require all nodes to share their commitments via a trusted broadcast channel with others instead of sharing them peer-to-peer. The broadcast channel is trusted to share the same commitment to different players. This approach eradicates the additional round to have a quicker process but is not as decentralised as the peer-to-peer sharing method, although the worst thing that a malicious broadcast channel can do is prevent the DKG process from completing successfully.
Feldman’s verifiable secret sharing works fine with low threshold schemes with up to (n - 1) / 2 malicious players. However, a well-known Rogue-key attack needs to be addressed in high-threshold schemes. In this attack, which is only possible with t > n / 2 DKGs, (n - t) + 1 malicious player can collude and obtain the whole key.
For instance, Feldman’s VSS only supports up to 4 out of 10 DKGs, but for a high threshold DKGs, e.g. 8 out of 10, only 3 malicious players can collude and obtain the whole key with a rogue-key attack.
To protect against the rogue-key attack, a popular approach suggested by the FROST protocol requires each participant to demonstrate knowledge of the secret they intend to share by providing other participants with a zero-knowledge proof. This proof is a simple Schnorr signature by their secret key on a hash created based on their id, a context string preventing replay attacks, and the public keys of their secret and a nonce.
Upon receiving the zero-knowledge proof, each player recalculates the hash based on the data they have received from other players and verifies if it is signed by the proper secret key corresponding to the shared public key.
What should be done when a player shares invalid data with others or is nonresponsive? An approach would be requiring players to calculate their secret share as the sum of all secret shares they have received and successfully verified and ignoring the ones they have not or failed to verify. However, this enables a single malicious player to, for instance, stop a 5 out of 7 DKG by being responsive to 3 players while not responding to the other 3. In this scenario, 3 honest players will reach one whole polynomial while the others reach a different one.
This is why a round is usually added to process broadcasted complaints against non-responsive or malicious players where verification of their shared secrets fails. In this round, each player acts as follows:
-
Form a graph with all the participating nodes.
-
Remove the nodes he has complained against.
-
Iterate over all complaints received from others and remove the edges between all complaint makers and the ones that the complaints are against.
-
Find the largest complete graph accordingly
-
Sum up the shares he has received from nodes that belong to the largest complete graph.
Using complete graphs for handling complaints, all six honest players reach a consistent complete graph where the malicious player is removed because of missing 3 edges and the DKG is successfully finalised with six honest players.
But what if 2 malicious players refuse to respond to only one player each? The DKG is supposed to still work out with 5 honest players, but let's see if that is actually the case.
Using the above graph-based approach, our 3 honest players, who are adversaries of no complaints, find four different complete graphs, one of which they must select randomly. In this scenario, there is a high chance for one or both malicious players to be included in the randomly selected 5-node graphs that honest players reach to form while one or two honest players are removed. The high chance of excluding honest players and including malicious players enables malicious players to stop the network from generating signatures in the future.
At first, it might seem to be reasonable to remove only the players who have complaints against them and not the ones who are placing the complaints. But it must be considered that complaints about nonresponsiveness are impossible to handle and identify the actual malicious player among the adversaries. At first glance, the adversary the complaint is about is offline, overloaded, or maliciously refusing to participate. But the other adversary could also be a malicious player trying to disqualify honest adversaries.
The inability to identify the actual malicious adversary in any chosen strategy taken to handle complaints and randomly selecting one of the adversaries might put the system at risk of removing honest players from the DKG.
This problem is sourced in the fact that players privately send the secret shares with no intermediate party involved to judge the validity of complaints. As suggested in Identiable Cheating Entity in FROST Signature Protocol, adding an intermediate party would solve the problem with a precaution in mind: The secrets that are supposed to be shared between nodes should only be readable privately by each player while transmitted through the intermediate party.
Accordingly, players can use asymmetric encryption to encrypt the secret share in a way that can only be decrypted by the intended player’s private key.
With the intermediate player present, complaints of not receiving are eradicated. The only possible complaints could be about receiving data that cannot be decrypted by the private key or lead to junk data after decryption.
Judging such complaints requires the complaining adversary to share their private key with the intermediate so that they can verify. To prevent the intermediate from gaining full access to the private key of the adversary, all players create an additional temporary key pair for the current DKG in the very first round just to transmit encrypted secret shares.
This temporary key pair is signed by their permanent private key. This signature prevents the intermediate player from impersonating players by creating and sharing temporary key pairs of its own instead of the actual key pairs provided by players.
The Schnorr signature is generally preferred among various signing algorithms for TSS since its linear nature makes it more straightforward to use in threshold settings.
Providing that the secret key is x, and the public key is y, where y = gx; the Standard Schnorr signature on the message m takes the following steps:
-
First, a random nonce k is chosen where its public key is r = gk
-
The challenge is then computed as e = H (r , m)
-
Let s = k - x . e, and the signature is instantiated as (s , e).
The following is done to verify the standard signature:
-
The verification r is calculated as rv = gs . ye
-
Then the verification e is ev = H(rv, m).
The signature is verified if the verification ev is identical to the challenge shared as e.
But how do we make a threshold signature with a distributed key as if a single secret key does it and can be verified as a standard Schnorr signature without revealing the shared secret?
It is usual practice in threshold signature schemes to have a separate DKG to create a key pair for the nonce besides the DKG for the main key pair. As shown in the equations below, if all players make a standard Schnorr signature using their own share of nonce and key and multiply their signatures by their Lagrange basis polynomial, the sum is identical to a signature made by the secret nonce and the secret key that is not accessible to any players.
Σ λi . si = Σ λi . (ki - xi . e) = (Σ λi . ki) - (Σ λi xi . e) = k - x . e = s
In the approach above, each signature requires a new DKG to be used as a nonce. This is a multi-round and time-consuming process.
A well-known alternative approach is the FROST protocol, which has a preprocessing stage in which all nodes share a batch of nonces with a signature aggregator. The aggregator uses each nonce to finalise a new signature in a single round.
The disadvantage to FROST is that its signing process is not robust. FROST trades off robustness for more efficient signing operations, such that a misbehaving player can cause the signing operation to abort, but the operation is finalised in a single round. This tradeoff is practical in blockchain systems where players must stake assets that might be slashed if they misbehave.
FROST achieves improved efficiency in the optimistic case that no participant misbehaves. However, when a misbehaving player contributes malformed values during the protocol or simply refuses to participate, honest players can identify and exclude the misbehaving player and re-run the protocol.
Further, because FROST does not provide robustness, FROST is secure so long as the adversary controls fewer than the threshold t participants, an improvement over robust designs, which can, at best, provide security for t <= n/2.