Open in app

Sign in

Write

Sign in

Threshold Signature Schemes

Ahmet
Nethermind.eth
26 min readOct 17, 2022

--

by Ahmet Ramazan Agirtas, Jorge Arce-Garro, Yevgeny Zaytman and Jelilat Anofiu

Special thanks to Albert Garreta and Ignacio Manzur for their valuable advice and comments, and to Michal Zajac for reviewing.

This post reviews two popular digital signature schemes, along with their Threshold Signature Scheme (TSS) versions. TSSs are essential for trustlessly generating signatures from a private key previously split and shared among several parties via a Distributed Key Generation (DKG) protocol.

The text can be read either on its own or as the fourth and final installment of our series on Distributed Validator Technology (DVT) and the cryptographic primitives that enable it.

Table of contents

Recap
Threshold Signature Schemes
Well-known constructions
∘ Threshold BLS
∘ Threshold Schnorr Signature
∘ FROST
∘ Comparison of the TSS schemes
TSS in DVT
∘ Re-sharing
Conclusion
References

Recap

From our article Sorting Out Distributed Validator Technology, recall that:

  1. Implementing DVT requires a Distributed Key Generation (DKG) protocol to share a secret key (in this case, the validator signing key) among several committee members in the form of partial signing keys called shares, while keeping the full secret key unknown to any individual party. For a refresher on DKG, see A tour of Verifiable Secret Sharing schemes and Distributed Key Generation protocols.
  2. Once a DKG is carried out, the setup for the DVT committee is completed and it can start to perform validator duties. To that end, committee members should reach a consensus on which message (block proposal) should be signed. See our post on consensus protocols: How to reach consensus with strangers.
  3. We also need a way for committee members to jointly sign messages with their shares, and to prevent any individual party to reconstruct the full secret on its own (if we were not able to avoid this, the purpose of using DKG would be defeated!). Furthermore, we want t + 1 shares out of n to be necessary (t or fewer shares cannot generate a valid signature) and sufficient (any set of t + 1 shares or more can be used to produce a valid signature) to construct the aggregated signature, where t < n is a threshold parameter.

Threshold Signature Schemes (TSS), which were the missing cryptographic primitive for a functional DVT solution, fulfill the third requirement.

We will first review and define key cryptographic concepts related to digital signatures and threshold signature schemes. These will be referred to further on, where we describe a selection of popular TSS implementations used nowadays — first in their simpler, one-party version, and then in their TSS versions. Specifically, we will go over:

  • BLS signature and Threshold BLS,
  • Schnorr signature and Threshold Schnorr Signature,
  • Flexible Round-Optimized Schnorr Threshold Signatures (FROST).

We conclude by mentioning applications of TSS in the context of blockchain, one of the main ones being DVT.

Digital signatures

Digital signatures are used to authenticate a message on behalf of an individual. It is similar to how an individual appends their signature at the end of a document to certify their identity and approval. Digital signatures, however, offer more security than their non-digital counterpart.

A digital signature uses public key cryptography to sign/approve messages. If designed and implemented correctly, it is virtually impossible to forge the signer’s signature. Compare this with a traditional signature, where it is relatively easy for others to forge it by merely looking at it and practicing enough.

In cases where the message is sent by more than one individual (e.g. a group of friends, the board members of a company, etc.), one signature won’t be enough. Each of these individuals needs to append their signature to the message for it to be valid. Appending each signer’s signature to the message is quite a naive approach. Better options exist in the literature for the multiple signer case.

Throughout the post, we will use the following notation and terminology. See our previous posts for a more detailed discussion of these concepts.

💡 Definition. (Lagrange interpolation)
Let S be a set of at least t + 1 points (xⱼ, yⱼ) for distinct xⱼ ’s, and xⱼ, yⱼ ∈ 𝔽ₚ for j ∈ S, the unique polynomial f of degree t with f(xⱼ) = yⱼ is the following linear combination of Lagrange basis polynomials ϕⱼ(X):

where the Lagrange basis polynomial is defined as

We call ϕⱼ(0) the Lagrange coefficient with respect to j ∈ S and denote it by λⱼ.

Threshold Signature Schemes

Consider a group of n users P₁, …, Pₙ. A (t, n) threshold signature scheme (TSS) enables any subgroup of t + 1 users to jointly generate a signature, but any subgroup with a size t or less cannot. A TSS consists of three algorithms.

1. Threshold key generation algorithm (TKG)
TKG is a Distributed Key Generation (DKG) protocol as described in our previous post A tour of Verifiable Secret Sharing schemes and Distributed Key Generation protocols.

Assume that it is run by n users P₁, …,Pₙ and it outputs a partial secret key skᵢ for user Pᵢ and a common public key pk for verification. The partial secret key skᵢ is a (t, n) secret share of the corresponding secret key sk, i.e. if the scheme works as expected,

Note that TKG is a one-time setup for a TSS, i.e., once it is completed, the partial secret keys can be used many times.

2. Threshold signature generation (TSG)
TSG is an interactive protocol that runs in two steps:
∘ Partial signature generation: Takes a partial secret key skᵢ and a message M as inputs, and outputs a partial signature σᵢ.
∘ Partial signature aggregation: Takes partial signatures and indices of a subgroup of signers as inputs, and outputs an aggregated signature σ.

3. Verification
The verification algorithm takes a message M, a signature σ, and a public key pk as inputs, and returns accept or reject. As we will see, the verification of a threshold signature scheme is identical to the verification of its non-threshold equivalent.

Security. The security of a TSS is defined by the notion of unforgeability. We say that a (t, n) threshold signature scheme is unforgeable if no adversary (who can corrupt up to t signers) can generate a signature on a previously unsigned message that passes the verification algorithm with non-negligible probability.

Well-known constructions

Threshold Signature Schemes have been studied by cryptographers for more than two decades. Various types of TSSs have been proposed according to the specifications of the protocols they are used in. Next, we cover three well-known TSSs that are based on the most common digital signature schemes.

Threshold BLS

BLS signature scheme

In 2001, Boneh, Lynn, and Shacham (hence the name) proposed the so-called BLS signature scheme in the Short Signatures from the Weil Pairing paper [Boneh, Lynn, Shacham, 2001]. Below is a high-level description of such a scheme.

In the key generation phase, a secret key is chosen as a random field element, and its public companion is computed as a point on a predetermined elliptic curve. In the signature generation phase, a hash function is used to convert the message to be signed into a point on the elliptic curve. Signing is performed simply by multiplying the hash of the message (a curve point) by the secret key (a scalar). To verify, the signature a bilinear pairing is used.

💡 Definition. (Bilinear pairing)
Let 𝔽ₚ be the finite field with prime order p, 𝔾₁ and 𝔾₂ be two additive cyclic groups with prime order p, and 𝔾₃ be a multiplicative target group with the same order. Let g₁, g₂ be generators of 𝔾₁, 𝔾₂, respectively. A bilinear pairing is a map e : 𝔾₁ × 𝔾₂ → 𝔾₃ that satisfies:

(1) Bilinearity: For all field elements a, b ∈ 𝔽ₚ and for all group elements
P ∈ 𝔾₁ and Q ∈ 𝔾₂, it holds that e(a⋅ P, b⋅ Q) = e(P, Q)ᵃᵇ.

(2) Non-degeneracy: There exists A ∈ 𝔾₁ and B ∈ 𝔾₂ such that e(A, B) ≠ 1.

For further details about pairings, we refer to Pairings for beginners by Craig Costello.
Next, we state a formal definition of the BLS signature scheme:

System parameters: {𝔾₁, 𝔾₂, 𝔾₃, g₁, g₂, H, e}
∘ Let 𝔾₁, 𝔾₂, 𝔾₃, g₁, g₂ and e be as above.
∘ Let H : {0,1}* → 𝔾₁ is a hash function that maps arbitrary length binary inputs onto the group 𝔾₁.

Key generation phase:
∘ Pick a secret key uniformly at random, sk ← 𝔽ₚ.
∘ Compute the public key pk ← sk ⋅ g₂. Note that pk ∈ 𝔾₂.

Signature generation phase:
∘ Compute the hash h ∈ 𝔾₁ of the message M, i.e. h ← H(M).
∘ Compute the signature σ ∈ 𝔾₁ of M as σ ← sk ⋅ h.

Verification phase:
Given system parameters, a message M and a signature σ, anyone can verify the signature as follows.
∘ Accept if e(h, pk) = e(σ, g₂), reject otherwise.

The verification algorithm always outputs “accept” if everything has been computed correctly. Indeed, using the bilinearity property of e :

To guarantee the security of the BLS scheme, one needs to use a type of group called a Gap Diffie-Hellman group (GDH). These are groups where the Computational Diffie-Hellman (CDH) problem is hard but the Decision Diffie-Hellman (DDH) problem is easy. We omit the definitions of these problems since they are out of the scope of this post. We refer to the “Short Signatures from the Weil Pairing” paper of [Boneh, Lynn, Shacham, 2001] for further details.

Note that, 𝔾₁, 𝔾₂ are usually taken to be subgroups of elliptic curve groups E₁ and E₂ over finite fields, respectively, where E₁ is assumed to have a more compact representation than E₂ (because it is assumed that E₁ is defined over a smaller finite field than E₂). That is why the size of an element of 𝔾₁ is smaller than the size of an element of 𝔾₂ (for example, for the choice of BLS12–381 curve, 48 and 96 bytes, respectively). Here we assume that the signature is in 𝔾₁ and the public key is in 𝔾₂. However, in Beacon Chain specs, the choice is just the opposite, i.e., public keys are assumed to be in 𝔾₁ and the signatures in 𝔾₂. The idea behind this choice is as follows. The signature aggregation is an off-chain operation. Once it is performed, it is sent to the Beacon Chain. On the other hand, the public key aggregation is performed on-chain whenever the aggregated signature needs to be verified. Therefore, assuming that the signatures are in 𝔾₂ and the public keys are in 𝔾₁ the computational overhead is left off-chain. Another reason for choosing smaller public keys is that the public keys of the validators are stored in the state. For more details about this design choice, see this post by Ben Edgington.

Threshold BLS

In 2003, Boldyreva proposed the threshold variant of the BLS signature scheme. In this scheme, signers generate their partial signatures independently. Then they aggregate the partial signatures via Lagrange interpolation.

Threshold key generation phase
Threshold key generation is achieved by all the users jointly performing a Distributed Key Generation (DKG) protocol. At the end of the DKG protocol, each user Pᵢ obtains a partial secret key skᵢ, and a unique public key pk is created. Remember that partial secret keys are (t, n) shares of the secret key sk, i.e.

for a set S of at least t + 1 participant indices.

Threshold signature generation phase
Pᵢ computes its partial signature using its partial secret key as described in the BLS signature scheme, i.e. σᵢ ← skᵢ ⋅ h, where h = H(M) is the hash of the message M. Then, Pᵢ broadcasts σᵢ. Upon receiving at least t + 1 partial signatures, Pᵢ aggregates the partial signatures to generate the threshold signature, i.e.

Note that aggregation can be done either by the signers themselves or by a designated aggregator.

Verification phase
As we mentioned above the verification process is identical to the verification of a single BLS signature, we check that e(h, pk) = e(σ, g₂).

Note that the partial signature aggregation always results in a valid BLS signature if everything has been computed correctly:

A special property of BLS signatures: Aggregation

We can also aggregate many signatures into a single signature using the BLS scheme. This can provide a significant decrease in storage, communication, and computational costs. For example, assume that we have n BLS signatures σ₁, …, σₙ on n different messages M₁, …, Mₙ by m distinct signers P₁, …,Pₘ. These signers can aggregate the signatures by simply adding all of them, that is by setting Σ = ∑ᵢ σᵢ. The verification of all the signatures for the messages M₁, …, Mₙ can be reduced to the verification of the aggregated signature Σ as follows:

where hᵢ = H(Mᵢ) and uᵢ, vᵢ are the secret and the public keys of the signers of the signature σᵢ, respectively. Note that here the verification algorithm computes m+1 pairings.

On the other hand, if the messages are the same, i.e., M₁ = … = Mₙ = M, then verification is much more efficient. Using the bilinearity property of e, then equation (1) can be rewritten into

where h = H(M). Notice that in this case, the verification algorithm computes only two pairings.

In practice, one cannot directly aggregate the signatures on the same message because of the so-called rogue-key attack. To avoid such attacks, extra safety measures have to be taken. For further information about these measures, one can see the paper Compact Multi-signatures for Smaller Blockchains in [Boneh, Drijvers, Neven, 2018].

What makes the BLS signature scheme special is its aggregatable structure, rather than its computational or storage efficiency. In the literature, there are also signature schemes with shorter signature or public key sizes and more efficient verification algorithms. Next, we describe two of them.

Threshold Schnorr Signature

Schnorr signature scheme

Schnorr signature was proposed by Claus Schnorr in 1989. It has the advantage of being simpler to compute than DSA-based schemes. In particular, it does not require computing modular inverses. However, since it was under patent until 2008, it has not seen as much use.

The original Schnorr signature scheme works over multiplicative groups. We focus on a variant by [Stinson, Strobl, 2001], which works on elliptic curve groups. We provide a formal definition of the Schnorr signature scheme below:

System parameters: {𝔾, g, H}
∘ 𝔾 is an additive group of prime order p. We will take 𝔾 to be the prime index subgroup of an elliptic curve group.
∘ g is a generator of the group 𝔾,
∘ H is a cryptographic hash function, i.e. H : {0,1}* → 𝔽ₚ that maps arbitrary length binary inputs to the integers modulo p.

Key generation phase:
∘ Pick a secret key uniformly at random, i.e., sk ← 𝔽ₚ.
∘ Compute the public key pk ← sk ⋅ g. Note that pk ∈ 𝔾.

Signature generation phase:
∘ Pick a secret nonce (a number that can only be used once) uniformly at random, i.e., k ← 𝔽ₚ.
∘ Define an elliptic curve point R as R ← k ⋅ g.
∘ Compute s ← k + sk ⋅ H(M || R) (mod p). Here M is the message to be signed and || denotes bitwise concatenation.
∘ The signature of M is set to be σ ← (R, s) ∈ 𝔾 × 𝔽ₚ.

Verification phase:
Given system parameters, a message M and a signature σ = (R, s),
∘ Accept if s ⋅ g = R + H(M || R) ⋅ pk, reject otherwise.

If everything has been computed correctly, signature generation results in a valid signature. This can be verified using the computation below:

⚠️ Note that, for the signature generation, it is very important to use a different k for each new signature. Some suggest taking k ← H(sk || M) in case one does not trust one’s source of randomness. However, this is not strictly necessary.

Threshold Schnorr Signature

In 2001, Stinson and Strobl proposed a threshold variant of the Schnorr signature scheme. Note that we skip the robustness checks to give a simplified version of their construction. Further details can be found in [Stinson, Strobl, 2001].

Threshold key generation
Threshold key generation is carried out by all the users jointly participating in a modified version of Pedersen DKG protocol. At the end of the threshold key generation each user Pᵢ obtains a secret and public key pair, i.e. skᵢ ∈ 𝔽ₚ and pkᵢ ∈ 𝔾, and a common public key pk ∈ 𝔾 for verification.

Threshold signature generation
Adapting the Schnorr signature scheme to any of the DKG/VSS protocols described in our previous blog post can be done in the following way. Each user participating in the signature generation jointly performs a modified version of Pedersen DKG protocol to obtain partial nonces, i.e. kᵢ, and a common value

where S and λᵢ are as in the above definition of Lagrange interpolation. Once all the participants agree on R, they can compute the partial signatures sᵢ’s, i.e. sᵢ ← kᵢ + skᵢ ⋅ H(M || R). These partial signatures are broadcasted among the participants and aggregated using Lagrange interpolation as

The Threshold Schnorr Signature is set to be σ ← (R, s) ∈ 𝔾 × 𝔽ₚ.

Verification phase
The verification algorithm is identical to the verification of the non-threshold version, i.e. checking whether the below equation holds:

Note that the partial signature aggregation always results in a valid Threshold Schnorr Signature if the protocol has been followed correctly:

FROST

Just like BLS, there are ways to extend Schnorr signatures to a TSS implementation — the Threshold Schnorr Signature we have seen is an example of how to carry out such a construction. However, we are interested in discussing a different protocol, named FROST (Flexible Round-Optimized Schnorr Threshold Signatures). This protocol, introduced in 2020, is currently used by organizations in the blockchain space, such as Coinbase and the ZCash Foundation.

There are at least two factors that make FROST superior to other Schnorr-based TSS protocols, motivating our choice of featuring it in this article:

1. Reduced number of network rounds during signing operations. FROST improves upon the state of the art and generates threshold signatures in the following number of rounds:
∘ 1 round if we have a trusted signature aggregator and a preprocessing phase,
∘ 2 rounds if we have a trusted signature aggregator, but no preprocessing phase,
∘ 3 rounds without a trusted signature aggregator or preprocessing phase.

2. Protection against forgery attacks. Although other Schnorr-based TSS implementations can also generate threshold signatures in 2 rounds, they must limit signing concurrency (i.e., the number of operations executed in parallel) to protect against a forgery attack (discovered by Drijvers et al. in 2019) that can take place when an attacker controls t shares. Such concurrency limits slow down the execution of other algorithms, while FROST is immune to this attack (and has no concurrency limits) due to its preprocessing phase. The attack in question is beyond the scope of the article and will not be discussed here — we refer the interested reader to section 2.4 of the FROST paper.

Next, we discuss the different phases of FROST, in its fastest, 1-round form. Let 𝔾 be a group of prime order p in which the Decisional Diffie-Hellman (DDH) problem is hard, and g be a generator of 𝔾.

We assume that the DKG protocol already took place, and every signer Pᵢ,
i ∈ {1, …, n} has their pair of secret key skᵢ and public key pkᵢ, respectively, with pkᵢ = skᵢ ⋅ g. (Refer to the beginning of the Schnorr signature and BLS signature sections for details).

Preprocessing phase
Before signing, each participant Pᵢ generates (and publishes) a list of N ordered commitment pairs of elliptic-curve points

It can be shown that, by binding every signing operation to one of these previously-committed pairs, the aforementioned attack by Drijvers et al. can no longer be carried out. Therefore, preprocessing N pairs will allow N signing operations to be performed before requiring another preprocessing step.

The list is generated by randomly choosing N pairs of random nonces
(dᵢⱼ, eᵢⱼ) ← 𝔽ₚ* × 𝔽ₚ* and computing the pairs (Dᵢⱼ, Eᵢⱼ) ← (dᵢⱼ ⋅ g, eᵢⱼ ⋅ g). The Lᵢ’s should then be published to a predetermined location for other participants (and the signature aggregator) to see, while each participant privately stores their (dᵢⱼ, eᵢⱼ) pairs for future use in signing operations.

Note that if we do not wish to store these commitment pairs ahead of time, we can simply have each participant generate a pair (dᵢ, eᵢ) and commit the respective (Dᵢ, Eᵢ) as the first round of the signing protocol.

Signing phase
For the signing phase, pick a subset of indices for at least t + 1 participants S ⊆ {1, 2, …, n} that will construct the signature (it can be all of them). Let pk be the (group) public key, and H₁ and H₂ be hash functions that output elements in 𝔽ₚ*. Let M be the message to be signed. Finally, choose a signature aggregator, which can be an external party or one of the participants. The signing phase then takes place as follows:

1. The signature aggregator fetches the next available commitment (Dᵢ, Eᵢ) in the lists Lᵢ for each participant Pᵢ and constructs the list of triples
B ← [(i, Dᵢ, Eᵢ): i ∈ S].

2. The aggregator sends the pair (M, B) to each participant Pᵢ.

3. Upon receipt, each participant confirms that M is the message they want to sign and that commitment B matches their stored nonces (dᵢ, eᵢ).

4. Each participant computes the binding values ρₗ for all protocol participants Pₗ. That is, everyone computes the field element values
ρₗ ← H₁(l, M, B), l ∈ S. These are then used to derive the commitments
Rₗ ← Dₗ + ρₗ ⋅ Eₗ, the group commitment

and the challenge c ← H₂(R, pk, M). Note that Rₗ and R are points in the elliptic curve, while c is a field element.

5. Each participant computes the response (a field element)
zᵢ ← dᵢ + eᵢρᵢ + c λᵢ(skᵢ). As before, λᵢ is the Lagrange coefficient with respect to the signer Pᵢ for the set S.

6. Each participant securely deletes the values dᵢ, Dᵢ, eᵢ and Eᵢ from their local storage, and sends the response zᵢ to the aggregator.

⚠️ This step is essential. If a participant accidentally reuses one of their nonces (dᵢ, eᵢ), their secret key skᵢ can be leaked!

7. The signature aggregator performs the following steps:

a. Derive the values ρₗ, R, and c, which are public due to the commitments (Dᵢ, Eᵢ) being public.

b. Verify the validity of each response zᵢ by checking the equality between elliptic curve points zᵢ ⋅ g = Rᵢ + c λᵢ ⋅ pk. If equality does not hold, identify and report the misbehaving participant, then abort. Otherwise, continue.

c. Compute the group’s response z ← ∑ zᵢ ∈ 𝔽ₚ.

d. Publish the signature σ ← (R, z) along with the message M.

Verification
Given system parameters, a message M and a signature σ = (R, z),

1. From σ = (R, z), parse out R to compute the challenge c ← H₂(R, pk, M).

2. Compute the point R’ ← z ⋅ g - c ⋅ pk.

3. Check R’ = R; output “success” if true, “failure” otherwise.

If FROST is followed correctly, R’ = R always holds. To show this, start from the definition of the responses zᵢ in Step 5:

Now recall from step 4 that R = ∑ (Dᵢ + ρᵢEᵢ). Rearranging and using
R’ = z ⋅ g - c ⋅ pk we conclude R’ = R.

A note on robustness
For FROST to allow for unlimited concurrent operations, it must sacrifice robustness — the ability to complete the signing process even in the presence of malicious parties. Notice (from step 7b) that a single dishonest participant is enough to sabotage the signing process, forcing the process to start over (after kicking out the dishonest participant). This loss of robustness is a theoretical necessity to provide security against t malicious signers, given that robust designs only tolerate up to n/2 attackers (as mentioned in Gennaro et al.’s 2007 paper).

Comparison of the TSS schemes

We have seen three different TSS schemes. Each has advantages and disadvantages in terms of the size of the signatures and public keys, the verification efficiency, etc. Note that for the Threshold BLS scheme, one should choose a so-called pairing-friendly curve (hence we assume the most common one, i.e. BLS12–381), while Threshold Schnorr Signature and FROST can work on any group where the Discrete Logarithm Problem (DLP) is hard.

Comparison of TSSs

¹ We give the signature and public key sizes the number of field/group elements in the table. We also provide concrete sizes (in bytes) in brackets for the most common groups that provide ~128-bit security.

² Here l denotes the number of participants (signers) in the signature generation phase, and N denotes the number of commitment pairs in the preprocessing phase of FROST. Note that integer additions and multiplications are omitted, as they are much cheaper than elliptic curve operations, i.e., point addition and scalar multiplication. Note that scalar multiplication refers to elliptic curve points being multiplied by field elements.

³ The pairing operation requires much more time than scalar multiplications and point additions. For a time estimate on elliptic curve operations regarding the BLS12–381 curve and more details about signature aggregation, one can check Justin Drake’s post on Pragmatic signature aggregation with BLS.

⁴ Note that here we are specifying the aggregation property of distinct signatures, not the aggregation of partial signatures.

So, if the other schemes’ signature size, public key size, and verification time are better, why did Ethereum Foundation choose to use the BLS signature, although ECDSA signatures are still in use for signing transactions?

The reason is the transition from Proof-of-Work (PoW) to Proof-of-Stake (PoS). In PoW systems, a miner proposes a block, and other nodes verify it. No attestations are needed. In contrast, PoS systems have no miners, only validators. A validator proposes a block with a signature, and some other validators attest to that proposal with their signatures. Considering the number of validators on the Ethereum network (which is more than 400k at the time of writing), each block proposal requires many attestations, which would bring a huge verification overhead if we were to use a signature scheme without the aggregation property. This is the exact point where the BLS signature scheme comes into play.

As we mentioned above, BLS signatures have this wonderful property of aggregation. If the messages are the same, then the different signatures can be aggregated into one (the same is true for the public keys). This requires as many point additions as the number of signatures to be aggregated, but the verification requires only two pairings as in the single signer case. For more information about aggregation, we suggest Justin Drake’s post Pragmatic signature aggregation with BLS.

What about the other schemes?

They are all superior to the BLS scheme when used in systems that do not require aggregation property. Remember that both Threshold Schnorr Signature and FROST beat the Threshold BLS scheme in terms of signature size, public key size, and verification time.

TSS in DVT

Now we can see how DVT allows a group of operators to jointly perform an Ethereum validator’s tasks in a secure and trustless manner. These tasks are executed by using the validator’s public/secret key pair to sign messages (block proposals). After jointly performing a DKG protocol and reaching a consensus on the message to be signed, the members of a DVT committee can now perform a Threshold BLS to jointly and securely sign this message, given that Ethereum utilizes the BLS signature scheme. Importantly, there is no need for a trusted third party, and no member of the DVT committee knows the full validator secret key.

Members of a DVT committee may need to be changed from time to time because some of them could leave or behave maliciously, sometimes even causing the validator to be slashed. For example, consider the following figure, from our previous post on DVT technology.

Suppose that Operator 4 behaves maliciously while running Node 4.1. Then the other members of Committee 3, i.e., Operator 2 and Operator 3, may wish to kick Operator 4 out of Committee 3. After that, Committee 3 will be run by two operators.

How can we handle members leaving or needing to be kicked out of a DVT committee? Remember that the validator’s public key is fixed once 32 ETH is staked in Ethereum. Hence it is not possible to change the validator’s secret and public keys for now, although there is a proposal to change this feature. The easiest solution to that problem is to “complete” the DVT committee by removing malicious operators and adding new operators if necessary. Here, two natural questions come up:

  1. How can we distribute partial signing keys to the new members?
  2. How can we make the shares held by the malicious parties irrelevant?

Luckily there is a well-known solution to these problems: re-sharing techniques. These may be seen as a complementary part of DKG protocols. Next, we describe some of these methods.

Re-Sharing

For purposes of this analysis, it will be helpful to break up the basic DKG protocol in the following manner:

Phase 1. Each of n players Pᵢ selects uᵢ ∈ 𝔽ₚ, and shares yᵢ = uᵢ ⋅ g. The public key is pk = ∑ᵢ yᵢ with secret key sk = ∑ᵢ uᵢ.

Phase 2. Each player creates a random degree t polynomial fᵢ over 𝔽ₚ with fᵢ(0) = uᵢ, and sends the j-th player the share vᵢⱼ = fᵢ(j). The players then add the shares they received to form skⱼ = ∑ᵢ vᵢⱼ.

The resulting skⱼ’s are the shares of a (t, n) Shamir’s secret sharing scheme (SSS) of the secret key sk. In particular for each subset S of at least t + 1 players, there exist Lagrange coefficients λⱼ such that

Full reset

The simplest approach (conceptually) is to rerun the algorithm above and obtain a new secret key. This has both the advantages and disadvantages of starting from scratch. However, in the DVT case, we can skip it since it is impossible (for now) to change an Ethereum validator’s signing key immediately.

Full re-sharing keeping the public key

This approach keeps the same public key while resetting everyone’s shares by rerunning Phase 2 of the keying algorithm and incurring its full cost. This requires enough players from the previous re-sharing to still be around. One nice feature is that the new shares can’t be combined with old shares to reconstruct the secret key.

We now describe the re-sharing in more detail. Let S be a set of t + 1 players Pᵢ still around from either the previous re-sharing or the initialization of the protocol. Let there be n’ new players P’ⱼ (some of whom might be the same as the old players Pᵢ). We will recombine the keys into a (t’, n’) Shamir’s SSS. (Note that the new values t’ and n’ can be different from the old t and n.)

As in Phase 2 above, each old player Pᵢ created a random degree t’ polynomial fᵢ over 𝔽ₚ with fᵢ(0) = skᵢ, its old share, and sends the Pⱼ the share vᵢⱼ = fᵢ(j). The players then add the shares they received to form

The resulting sk’ⱼ ’s are the shares of a (t’, n’) Shamir’s SSS of the same secret key sk.

Note that for purposes of the next section, after a re-sharing we will refer to the old players Pᵢ as elders.

Adding and removing new players without a full re-sharing

This is a lighter-weight way to add or remove players (people only have to talk to the new player) but requires elders from before the last full re-sharing to still be around. Removing players is easy: since this is a t + 1 of n protocol, we don’t have to do anything as long as t + 1 players are still around.

To add a new player P’ⱼ , as long as at least t + 1 elders Pᵢ from before the last full rekeying are still around, each elder simply sends the new player the value fᵢ(j) and the new player P’ⱼ combines them into

Note that this protocol cannot change the value of t. Also note that any t + 1 players from before the last full re-sharing can work together to reconstruct the secret key, even if they were never active at the same time.

Adding a player using a secure multi-party computation

If we are willing to incur the cost of running a protocol for a secure multi-party sum, we can dispense with the elders in the previous version. Instead a set S of any t + 1 players. Let λᵢ be the Lagrange coefficients that satisfy

for any degree t polynomial f. Then we just need the players to perform a secure multiparty sum that gives player Pⱼ the sum

with each player Pᵢ in S contributing λᵢskᵢ.

Conclusion

This is the fourth and last post in our series explaining Distributed Validator Technology (DVT). We have covered the three most popular TSSs and their non-threshold variants. Moreover, we have compared these TSSs in terms of signature/key size and verification efficiency. We have also touched upon the use of TSS in DVT.

So where should we go next?

We have already started preparing new articles (both technical and non-technical) which will cover a large array of topics related to the blockchain ecosystem.

Stay tuned for the following posts!

References

Nethermind is a team of world-class builders and researchers. We empower enterprises and developers worldwide to access and build upon the decentralized web. Our work touches every part of the Web3 ecosystem, from our Nethermind node to fundamental cryptography research and application-layer protocol development. We’re always looking for passionate people to join us in solving Ethereum’s most difficult challenges. Are you interested? Check out our job board https://nethermind.io/company/

Cryptography
Research
Distributed Validators
Threshold Signature

--

--

Ahmet
Nethermind.eth

Written by Ahmet

23 Followers
Writer for

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams