# FROST Research Update

by Wolf McNally, Blockchain Commons

## September 7, 2024

frost-secp256k1-tr = { git = "https://github.com/zebra-lucky/frost", rev = "d580241e8561ed145a464e6671a511d5a8c218f8" }

## September 2, 2024

### FROST Code Exploration

After studying FROST in general (see below) I tried out some of the variants of the ZCash FROST implementations. In particular, I wanted to see whether the public keys and signatures they generate are compatible with the Schnorr keys and signatures we’re using in Gordian Envelope.

Since our Schnorr signatures are over SecP256k1, I first tried the `frost-secp256k1` crate. I was surprised to discover that the group verification key (public key) it produces has the same form as ECDSA compressed public keys: 33 bytes, where the first byte is `0x02` or `0x03` depending on the parity of the y value. However, the Schnorr public keys we’re using are 32-byte “x-only” public keys, so there is not a drop-in compatibility between the two. I was not aware that Schnorr implementations over SecP256k1 ever used keys of the form that this implementation returns.

Furthermore, the signatures produced by our Schnorr signer are 64 bytes, while `frost-secp256k1` produces signatures that are 65 bytes long. This appears to be a nonstandard length. Again the leading byte is either `0x02` or `0x03`, and I really don’t understand what this means: it’s not always the same as the corresponding public key.

In any case, I don’t have a lot of hope that the public keys and signatures produced by this implementation are compatible with our implementation.

I also looked at a couple other variants of the crate, including `frost-ristretto255` and `frost-ed25519`, both of which do produce 32-byte public keys and 64-byte signatures. Nice, but since those are over different curves then I don’t expect we can drop them in either.

This leaves us with the option of creating new `SigningPublicKey` and `Signature` variants for those output by some variant of the FROST algorithm. These would join our existing suite of signature types that currently include ECDSA, Schnorr, and the SSH variants. If we go that route, I think we should consider adopting Ristretto. I see no reason why those would not be compatible with the keys and signatures produced by `frost-ristretto255`.

### Stack Wallet Code

- Stack Wallet uses the Flutter cross-platform framework and its main language is Dart. It’s FROST implementation is in a fork of the Serai project: https://github.com/kayabaNerve/serai
- The actual FROST implementation is in Rust: https://github.com/kayabaNerve/serai/tree/develop/crypto/frost
- The upstream of the fork appears to be somewhat ahead of the version that Stack Wallet is using: https://github.com/serai-dex/serai/tree/develop/crypto/frost
- Interestingly, the crates of the Serai project are either MIT or AGPL-3.0, which is compatible with StackWallet’s GPL 3 license. But the particular implementation of FROST being used is MIT: https://github.com/serai-dex/serai/blob/develop/crypto/frost/LICENSE
- The crypto suite including the FROST implementation has been reviewed. The report states, “Overall, the implementation is well designed and carefully written with secure deployment in mind. We did not identify any findings of particular immediate concern.” It goes on to recommend a number of possible improvements, some of which deal with the FROST implementation: https://github.com/serai-dex/serai/raw/e1bb2c191b7123fd260d008e31656d090d559d21/audits/Cypher%20Stack%20crypto%20March%202023/Audit.pdf
- I have not had the time (or much inclination) to experiment with running the actual app, as I think there are probably people who are better qualified than me to evaluate whether it meets HRF’s other award requirements.

### FROST 3-of-5 Workflow from User's Perspective

#### Overview

- **Pre-Setup Phase**:
- **You**: Review and agree to the proposal, monitor the secure channel setup.
- **Your Software**: Establishes secure channels, handles key generation, public key exchange, and commitment sharing.
- **Signing Phase**:
- **Round 1**: Receive and validate the signature generation request, generate and exchange nonces and commitments.
- **Round 2**: Aggregate nonces, compute signature shares, handle participant reliability, and complete the process once a quorum is met to generate the final signature.

#### Optional Roles

##### Trusted Dealer

- **Role:** The Trusted Dealer is responsible for generating and securely distributing the private key shares and corresponding public key shares to the participants.
- **Advantages:** This role simplifies the initial setup by centralizing the key generation process.
- **Optional:** This role is optional because participants can also generate their own key shares through a Distributed Key Generation (DKG) protocol, which avoids reliance on a single trusted entity.
- **Security Implications:** The Trusted Dealer must be fully trusted, as they have access to critical cryptographic material. If compromised, they could undermine the security of the entire system.

##### Coordinator/Aggregator

- **Role:** The Coordinator or Aggregator is responsible for orchestrating the signing process. This role includes tasks like collecting the partial signatures from the participants, aggregating them to form the final signature, possibly managing communication between participants, and in the case of Bitcoin transactions, transmitting the signed transaction to the network.
- **Advantages:** The Coordinator/Aggregator can improve efficiency by reducing the complexity of communication and ensuring that the signing process is conducted smoothly and quickly.
- **Optional:** This role is also optional, as in some implementations, participants can perform these tasks collectively or distribute the responsibilities without needing a central coordinator.
- **Security Implications:** The Coordinator/Aggregator does not need access to private keys but must be trusted to correctly aggregate and manage the signature shares. If the Coordinator is compromised, it could result in denial of service or incorrect signature aggregation.

While it is possible for the same party to fulfill both roles, it is not advisable due to the increased security risks and potential for a single point of failure. Separating these roles helps maintain the integrity, security, and decentralization of the FROST-based system.

#### **Pre-Setup Phase**

##### 1. **Proposal to Form the Group**

- **Action by You**:
- **Receive Proposal**: You receive a proposal to form a FROST signing group, including:
- The identities of the proposed group members ${A, B, C, D, E}$ and their contact methods,
- The signing threshold (quorum) that will be required to generate valid signatures, and
- The identity and contact information of a Trusted Dealer if one is to be used.
- The identity and contact information of a signature aggregator/coordinator if one is to be used.
- **Review Proposal**: You review the proposal to ensure the group members are trusted and the contact methods are secure.
- **Agree to Participate**: After reviewing, you consent to join the group and participate in the threshold signature scheme.
- **Action by Your Software**:
- **Store Group Information**: Your software securely stores the identities and contact methods of the group members.
- **Initiate Group Formation**: Your software prepares to establish secure communication channels with the other group members.

##### 2. **Establish Secure Communication Channels**

- **Action by You**:
- **Monitor Channel Setup**: You ensure that the secure communication channels are successfully established between you and the other participants ${B, C, D, E}$.
- **Action by Your Software**:
- **Create Secure Channels**: Your software establishes encrypted communication channels with $B$, $C$, $D$, and $E$, ensuring that all future data exchanges are secure.

##### 3. **Key Generation and Distribution**

Distributed Key Generation (DKG) and Trusted Dealer key generation are two methods for generating cryptographic keys in a multi-party setting. DKG involves all participants separately generating their own key shares without relying on a central authority, ensuring no single party ever possesses the complete private key. This method enhances security and trustlessness, making it suitable for decentralized systems. In contrast, Trusted Dealer key generation relies on a single trusted entity to create and distribute key shares to participants. While this approach is simpler and faster, reducing computational overhead, it introduces a single point of trust and potential vulnerability. DKG is favored in trust-minimized environments, while Trusted Dealer generation is more efficient in contexts where trust in the dealer is acceptable.

###### 3.1. Distributed Key Generation

###### 3.1.1. **Key Generation**

- **Action by Your Software**:
- **Generate Private Key Share**: Your software generates a private key share specific to this group ${A, B, C, D, E}$.
- **Compute Public Key Share**: Your software derives the corresponding public key share from your private key share and prepares it for distribution.
- **Action by You**:
- **No manual action**: Your software handles key generation and preparation automatically.
-
###### 3.1.2. **Public Key Share Exchange**

- **Action by Your Software**:
- **Distribute Public Key Share**: Your software sends your public key share to $B$, $C$, $D$, and $E$ through the secure communication channels.
- **Receive Public Key Shares**: Your software receives the public key shares from $B$, $C$, $D$, and $E$ and combines them to form the group’s public key.
- **Action by You**:
- **No manual action**: Your software manages the exchange and combination of key shares.

###### 3.2. Trusted Dealer Key Generation

- **Action by Trusted Dealer**:
- **Generate Master Key**: The trusted dealer generates the master private key for the group.
- **Distribute Private Key Shares**: The trusted dealer securely distributes individual private key shares to each participant ${A, B, C, D, E}$, along with the corresponding public key shares.
- **Action by Your Software**:
- **Receive Private Key Share**: Your software receives your private key share and stores it securely.
- **Receive Public Key Shares**: Your software receives the public key shares from the trusted dealer for each participant and stores them.
- **Action by You**:
- **No manual action**: Your software handles the reception and storage of the key shares automatically.

##### 4. **Commitment Sharing**

- **Action by Your Software**:
- **Generate Commitment Values**: Your software generates commitment values tied to future nonce generation. These commitments are paired with the nonces to ensure their integrity during the signing phase.
- **Distribute Commitments**: Your software distributes your commitment values to $B$, $C$, $D$, and $E$.
- **Receive Commitments**: Your software receives and stores commitment values from the other participants.
- **Action by You**:
- **No manual action**: Your software handles the commitment generation, exchange, and storage.

#### **Signing Phase**

The signing phase begins with the arrival of a signature generation request and is divided into two main rounds.

##### **Round 1: Signature Generation Request and Nonce/Commitment Exchange**

1. **Arrival of Signature Generation Request**
- **Action by You**:
- **Receive Request**: You receive a signature generation request, including the message that needs to be signed.
- **Review Message**: You review the message to be signed to ensure it is legitimate and appropriate.
- **Consent to Sign**: After reviewing, you consent to participate in the signing process.
- **Action by Your Software**:
- **Validate Request**: Your software validates the request, checking for all necessary information.
- **Prepare for Signing**: Upon your consent, your software prepares to generate the necessary cryptographic elements.
2. **Nonce Generation**
- **Action by Your Software**:
- **Generate Nonce Pair**: Your software generates a nonce pair $(r_A, R_A)$, consisting of a random secret value $r_A$ and a corresponding public value $R_A$. This nonce is paired with the commitment generated during the pre-setup phase.
- **Action by You**:
- **No manual action**: Your software handles nonce generation automatically.
3. **Nonce Exchange and Commitment Verification**
- **Action by Your Software**:
- **Distribute Nonce**: Your software sends your nonce $R_A$ to $B$, $C$, $D$, and $E$, along with the previously generated commitment to ensure the integrity of the nonce.
- **Receive Nonces**: Your software receives nonces $R_B$, $R_C$, $R_D$, and $R_E$ from the other participants along with their associated commitments.
- **Verify Commitments**: Your software verifies that each received nonce is correctly paired with its associated commitment and that the commitment has not been used in any previous signing operations. This ensures the integrity and freshness of the nonce.
- **Action by You**:
- **No manual action**: Your software manages the exchange of nonces, the verification of commitments, and ensures that all commitments are unused.

#### **Round 2: Signature Share Generation and Final Signature**

1. **Nonce Aggregation and Challenge Calculation**
- **Action by Your Software**:
- **Aggregate Nonces**: Your software combines the received nonces to compute the aggregated nonce: $R = R_A + R_B + R_C + R_D + R_E$.
- **Compute Challenge**: Your software calculates the challenge $c$ using the aggregated nonce $R$, the group public key, and the message to be signed: $c = H(R, \text{group public key}, \text{message})$
- **Action by You**:
- **No manual action**: Your software handles nonce aggregation and challenge calculation.
2. **Signature Share Computation**
- **Action by Your Software**:
- **Compute Your Signature Share**: Using your private key share and the calculated challenge $c$, your software computes your signature share $s_A = r_A + c \cdot \text{private key share}_A$.
- **Action by You**:
- **No manual action**: Your software automatically computes the signature share.
3. **Signature Share Exchange**
- **Action by Your Software**:
- **Distribute Signature Share**: Your software sends your signature share $s_A$ to $B$, $C$, $D$, and $E$.
- **Receive Signature Shares**: Your software receives the signature shares from the other participants.
- **Action by You**:
- **No manual action**: Your software handles the exchange of signature shares.
4. **Handling Absences and Unreliable Participants**
- **Action by Your Software**:
- **Monitor Participant Responses**: Your software monitors the signature shares received. If $B$ does not respond or $D$ sends an invalid share, your software automatically excludes them from the quorum.
- **Short Circuit**: As soon as a quorum (3 out of 5 participants) has successfully exchanged valid shares, your software initiates the final signature generation without waiting for the remaining participants.
- **Recalculate Aggregated Nonce and Challenge**: If $B$ is absent or $D$’s share is invalid, your software recalculates the aggregated nonce $R'$ using only valid nonces (e.g., from $A$, $C$, and $E$) and computes the new challenge $c'$.
- **Action by You**:
- **No manual action**: Your software handles these adjustments and the short-circuiting process automatically.
5. **Final Signature Share Aggregation**
- **Action by Your Software**:
- **Aggregate Signature Shares**: Your software aggregates the valid signature shares to produce the final signature: $s = s_A + s_C + s_E$.
- **Generate Final Signature**: The final signature on the message is $(R', s)$.
- **Action by You**:
- **No manual action**: Your software finalizes the signature.
6. **Submit the Final Signature**
- **Action by Your Software**:
- **Send Final Signature**: Your software automatically sends the final signature $(R', s)$ to the requesting party.
- **Action by You**:
- **No manual action**: Your software handles the submission of the final signature.

---

### Adapting FROST to Bitcoin

When adapting the FROST workflow for managing a Bitcoin account, it is crucial to address the possibility of two or more participants generating valid but different signatures for the same transaction. This scenario can arise due to differences in the nonces or challenges used during the signing process, leading to multiple valid signatures. The workflow must include mechanisms for detecting, arbitrating, and deciding which signed transaction gets broadcast to the Bitcoin network.

#### Key Considerations for Adaptation

##### Bitcoin Address Creation (Taproot)

- **Public Key Aggregation** remains the same as described before, with the participants combining their public keys into a Taproot address.

##### Fund Deposit

- **No Changes**: The deposit process remains the same, with participants ensuring the Taproot address is correct before any funds are deposited.

##### Signing Bitcoin Transactions (Schnorr Signature)

- **Round 1 (Signature Request and Nonce Exchange)**:
- The process of signing remains the same initially, with participants validating the transaction and generating/exchanging nonces.
- **Nonce Synchronization**: Consider the need for synchronized nonce generation to minimize the risk of divergent signatures. This could involve a commitment protocol to ensure all participants use the same nonce values.

- **Round 2 (Signature Share Generation and Final Signature)**:
- **Handling Divergence**: After generating signature shares, it is possible that two or more participants could generate different valid final signatures. This divergence could happen due to differences in nonce aggregation or if the signing rounds were initiated separately (e.g., by different participants).
- **Signature Comparison**: Consider including a step where participants compare their final signature (or a hash of the signature) with each other before broadcasting. This step would ensure that all participants agree on a single final signature.

##### Arbitrating Between Different Signatures

- **Consensus Mechanism**:
- **Hash Comparison**: Consider implementing a mechanism where participants exchange hashes of their final signatures before broadcasting. If all hashes match, the signature is broadcast by a designated participant.
- **Majority Voting**: If different signatures are generated, participants should vote on which signature to use based on a majority or predefined rule. For example, the first signature to be shared and receive approval from at least a quorum of participants is chosen for broadcasting.
- **Designated Broadcaster**:
- **Pre-Assigned Broadcaster**: To streamline the process, the group could pre-designate a participant responsible for broadcasting the transaction. This participant will only proceed if they receive matching or majority-agreed signature shares from others.
- **Fallback Mechanism**: If the pre-assigned broadcaster fails to act within a set time (e.g., due to network issues), a secondary participant automatically takes over the broadcasting responsibility.
- **Timeout and Resubmission**:
- **Timeout Protocol**: If the signature comparison process takes too long (e.g., due to network latency or unresponsive participants), the workflow may include a timeout after which the signature with the most agreement is automatically chosen and broadcast.
- **Resubmission Process**: If no consensus is reached, a resubmission process should be triggered where participants are prompted to regenerate and exchange their nonces to produce a new valid signature.

##### Transaction Broadcasting

- **Broadcasting Agreement**: Once a single valid signature is agreed upon, the aggregator/coordinator submits the signed transaction to the Bitcoin network. The broadcast is then confirmed to all participants to ensure transparency and coordination.
- **Redundant Broadcasting**: In some cases, to mitigate the risk of failed broadcasting (e.g., due to network issues), more than one participant may broadcast the same signature. This ensures the transaction is included in the blockchain promptly but must be done cautiously to avoid network spam.

##### Security and Privacy

- **Secure Communication**: Ensure that all signature exchanges, comparisons, and votes on which signature to broadcast are conducted over secure channels.
- **Logging and Auditing**: The workflow should include logging and auditing mechanisms that record which signature was chosen and why, providing transparency and a record of decision-making.

##### Participant Management

- **Handling Disagreements**: In the case of significant disagreement over which signature to broadcast, the workflow should allow for an arbitration process, possibly involving an out-of-band discussion or a fallback to a predefined protocol rule.
- **Incentive Alignment**: To minimize the chances of divergence and disagreement, the group should establish clear rules and incentives to ensure all participants aim to generate and agree on the same signature.

##### Edge Cases and Recovery

- **Handling Signature Collisions**: If two different valid signatures are accidentally broadcast by different participants, only one will be included in the blockchain (the one confirmed by miners first). The workflow should anticipate this by ensuring that once a transaction is confirmed, the other participants stop any further attempts to broadcast the other signature.
- **Recovery Protocol**: If the wrong signature is broadcast or if a disagreement causes a delay, the group should have a recovery protocol that outlines the steps for resubmitting a new transaction or correcting the situation.

By incorporating these considerations, the FROST workflow will be well-adapted to manage Bitcoin transactions securely and efficiently, even in cases where multiple valid signatures are generated. The key is to establish a consensus on which signature to broadcast and to ensure that all participants are aligned and coordinated throughout the process.

---

### Understanding Cryptographic Enforcement of the Threshold

Let’s delve deeper into how FROST enforces the quorum threshold and why it’s cryptographically infeasible to generate a valid signature with fewer participants than the agreed quorum.

#### 1. **Establishing the Quorum Threshold**

##### During Group Creation

- **Threshold Determination**:
- **At the Initial Setup**: During the group creation, all participants agree on a specific threshold (e.g., 3-of-5) that will be required to generate a valid signature. This threshold is critical because it dictates the number of participants needed to sign any transaction or message.
- **Public Key Setup**: The agreed threshold is embedded into the group’s public key structure. This is done through the way individual public keys (derived from private key shares) are combined to form the group public key. The group public key is a function of the agreed threshold and the individual public keys, making the threshold an inherent part of the key generation process.
- **Key Generation and Distribution**:
- **Private Key Shares**: Each participant receives a private key share, generated during the setup, that corresponds to the overall group public key. These private key shares are designed such that a valid signature can only be generated when the number of shares used meets or exceeds the quorum threshold.
- **Mathematical Commitment**: The cryptographic commitment to the threshold is made during this setup. The underlying mathematics of threshold signatures, particularly in FROST, ensures that only the combined contributions from a sufficient number of participants (equal to or greater than the threshold) can produce a valid signature.

#### 2. **Cryptographic Enforcement of the Quorum Threshold**

##### During Signature Generation

- **Multi-Party Computation (MPC)**:
- **Nonce Generation and Sharing**: Each participant generates a nonce, which is then shared among the group. The combined nonce is used to generate a challenge in the signing process. Importantly, the nonces themselves are tied to the threshold. The process of combining nonces from multiple participants is designed to ensure that the aggregated result is valid only if it includes contributions from the quorum.
- **Challenge Calculation**:
- **Threshold-Dependent Challenge**: The challenge `c` used in the signature generation process is calculated based on the combined nonce and the group public key. This challenge is only valid if the quorum of participants has correctly shared their nonces. If fewer participants contribute, the resulting challenge will not match the expected value derived from the group’s public key, making it impossible to generate a valid signature.
- **Signature Share Computation**:
- **Private Key Share Dependency**: Each participant’s signature share is computed using their private key share and the challenge `c`. The structure of these shares is such that combining them into a final signature is only possible if the number of shares meets or exceeds the threshold. The signature shares from fewer than the quorum cannot be correctly combined into a valid final signature.
- **Aggregation and Verification**:
- **Aggregated Signature Validity**: The final signature is a combination of the individual signature shares. The mathematical properties of the signature scheme ensure that if fewer than the threshold number of shares are combined, the final signature will be invalid and will not be accepted by the verification process. The verification process, which involves checking the signature against the group public key and the message, will fail if the threshold has not been met.

#### 3. **Why It’s Cryptographically Infeasible to Sign Below the Threshold**

- **No Valid Shortcut**:
- The structure of FROST and similar threshold signature schemes relies on the principle that every valid signature must satisfy the equation involving the group public key, the aggregated nonce, and the challenge. These components are all tied to the threshold. Attempting to generate a signature with fewer participants (e.g., 1-of-5 instead of 3-of-5) would fail because the cryptographic operations necessary to produce the signature depend on the contributions from the threshold number of participants.
- **Inherent in the Public Key**:
- The group public key, generated during setup, encodes the threshold within its structure. Any signature that does not involve contributions from the quorum of private key shares will not match the group public key, making it impossible to generate a valid signature below the threshold.
- **Mathematical Proofs**:
- The security of threshold signature schemes like FROST is based on well-established cryptographic proofs. These proofs demonstrate that it is computationally infeasible to generate a valid signature without the required number of participants. This infeasibility comes from the fact that the challenge `c` and the resulting signature are inherently linked to the threshold through the way the nonces, shares, and public keys are combined.

The quorum threshold in FROST is established during the group creation process and is cryptographically embedded into the key generation and signing processes. The multi-party computation, nonce aggregation, and challenge calculation steps are all designed to ensure that only contributions from the threshold number of participants can produce a valid signature. This makes it cryptographically infeasible for any participant to unilaterally generate a valid signature with fewer than the quorum, as the underlying cryptographic operations strictly enforce the agreed threshold.

---

### Understanding Pre-Sharing of Commitments

#### General Considerations

Generating and sharing a package of commitments before the first signing phase begins is considered best practice primarily to reduce the number of rounds needed during the signing process, but may also carry security implications (see below). This approach offers several advantages:

1. **Reduced Latency**: By generating and distributing multiple commitments upfront, participants can avoid the need to generate and exchange commitments for each individual signing session. This reduces the communication overhead and speeds up the overall signing process, as fewer rounds of communication are required.
2. **Minimized Interaction**: In threshold signature schemes like FROST, minimizing the number of interaction rounds is crucial for efficiency, especially in distributed systems where communication delays can be significant. Pre-sharing a batch of commitments allows the participants to proceed directly to the nonce exchange and signature generation in future signing rounds without additional setup.
3. **Preparedness for Multiple Signings**: Pre-generating a package of commitments ensures that participants are always ready to sign multiple messages in succession without needing to pause and generate new commitments. This is particularly useful in scenarios where multiple signings may be required in a short period, such as in high-frequency trading or automated systems.
4. **Security and Consistency**: Generating multiple commitments upfront ensures that all participants are committed to a specific set of values before any signing takes place. This consistency prevents any participant from altering their commitments on the fly, which could introduce vulnerabilities or inconsistencies in the signature generation process.
5. **Failure Tolerance**: If a participant fails or is unable to generate new commitments in subsequent rounds, having a pre-shared package of commitments ensures that the signing process can continue with the existing commitments. This improves the robustness of the system.

In summary, pre-generating and sharing a package of commitments reduces the number of communication rounds, improves efficiency, and ensures that the system is prepared for multiple signings, all while maintaining security and consistency.

#### Number of Commitments Typically Shared in a Package, and Best Practices When Running Low on or Out of Pre-Shared Commitments

The number of commitments shared in a package is typically determined based on the expected usage and operational needs of the system. A common practice is to share a package containing **enough commitments to cover multiple signing operations**, with the exact number varying depending on the frequency of signings and the application’s requirements. For example, a package might include commitments for **10, 50, or even 100** signings.

When participants may run low on or exhaust their pre-shared commitments, the following best practices should be followed:

1. **Monitor Commitment Usage**: Software should track the number of remaining commitments and provide alerts when the number is low. This ensures that participants are aware and can initiate a refresh before they run out.
2. **Regenerate and Distribute New Commitments**: Before the pre-shared commitments are fully exhausted, participants should generate a new batch of commitments and share them with the group. This process should be initiated well in advance to avoid any interruption in the signing process.
3. **Automatic Renewal**: Implementing an automatic renewal process can ensure that as soon as commitments fall below a certain threshold (e.g., only 5 commitments left), the system automatically triggers the generation and distribution of a new package. This reduces the risk of running out of commitments during critical operations.
4. **Fallback Mechanism**: If participants do run out of pre-shared commitments unexpectedly, they may temporarily revert to generating and sharing commitments on a per-signing basis. While this reintroduces the need for additional communication rounds, it allows the signing process to continue until a new package of commitments is shared.
5. **Efficient Distribution**: The distribution of new commitments should be done securely and efficiently, leveraging the established secure communication channels to minimize latency and ensure that all participants receive the new commitments simultaneously.

By following these best practices, participants can maintain a smooth and uninterrupted signing process, even when the pool of pre-shared commitments is running low.

### Security Considerations

Beyond merely increasing the number of rounds, sharing one commitment/nonce pair per signing, as opposed to pre-sharing a batch of commitments, can have security implications. These implications include:

1. **Increased Risk of Replay Attacks**
- **Scenario**: If a participant generates and shares a commitment/nonce pair per signing, an attacker with access to previous rounds of communication could attempt to replay a previously used commitment/nonce pair to influence the signing process.
- **Consequence**: This could potentially compromise the integrity of the signature generation process, especially if the replayed nonce leads to predictable or manipulated outcomes.
2. **Exposure to Timing Attacks**
- **Scenario**: If commitments and nonces are generated on-demand for each signing, the timing of these operations could be observed by an attacker. Variations in timing could potentially leak information about the internal state of the participant’s cryptographic operations.
- **Consequence**: This might give an attacker clues that could help them infer private key information or predict future nonces, which could weaken the overall security of the scheme.
3. **Potential for Commitment Manipulation**
- **Scenario**: When generating commitments on a per-signing basis, there is a risk that a dishonest participant might try to manipulate or alter their commitments based on the information they receive from other participants before the final signing round.
- **Consequence**: This could lead to malicious behavior where the participant attempts to bias the signature in their favor or disrupt the signing process.
4. **Increased Attack Surface**
- **Scenario**: Generating and sharing commitments on a per-signing basis requires more frequent communication and cryptographic operations. This increases the overall attack surface since each round of communication presents an opportunity for potential interception or interference by an attacker.
- **Consequence**: The more rounds and communications involved, the more chances there are for an attacker to exploit vulnerabilities in the network, protocols, or implementations.
5. **Reduced Privacy**
- **Scenario**: By generating commitments for each signing, participants are constantly exposing new cryptographic elements to the network. If an attacker can observe multiple such elements over time, they might be able to correlate these to infer information about the participant’s private key or other sensitive details.
- **Consequence**: This could lead to gradual leakage of private information, particularly in systems where high levels of privacy are required.
6. **Nonce Mismanagement**
- **Scenario**: Frequent generation of nonces without pre-sharing commitments might lead to nonce reuse, either accidentally or through a failure in the management system.
- **Consequence**: Reusing a nonce in cryptographic operations can be catastrophic, as it may allow attackers to derive the private key or otherwise compromise the security of the system.

While generating and sharing one commitment/nonce pair per signing might seem like a straightforward approach, it does introduce several potential security risks. These risks can be mitigated by pre-sharing a package of commitments, which not only enhances efficiency but also reduces the attack surface and protects against various cryptographic vulnerabilities.

---

### Blind Trusted Dealer

It is possible for the Trusted Dealer to be an entirely separate third-party service that vends key packages without any knowledge of the specific uses they will be put to. This approach can provide a more secure and privacy-preserving setup by limiting the Trusted Dealer's role to a narrowly defined task. Here's how this can be achieved:

#### Key Features of a Third-Party Trusted Dealer Service

1. **Blind Key Package Generation**:
- The Trusted Dealer can be designed to generate key packages (private key shares and corresponding public key shares) without knowing the identities of the participants or the context in which these keys will be used. This can be achieved using cryptographic techniques that ensure the dealer cannot correlate key packages to specific users or applications.
2. **Minimal Information Exchange**:
- The Trusted Dealer should only be aware of the number of participants and the threshold required (e.g., a 3-of-5 scheme) but not the identities of the participants, the specific use case, or the actual messages that will be signed.
3. **Secure and Verifiable Key Distribution**:
- The Trusted Dealer vends the key packages in a way that ensures each participant receives their private key share securely, using encrypted communication channels. Participants can independently verify the integrity and correctness of their key shares without involving the dealer.
4. **State-Minimized Operation**:
- The Trusted Dealer can operate in a state-minimized manner, where it does not retain any records of the key packages. This reduces the risk of compromise or misuse of stored key material. Once the keys are vended, the dealer has no further involvement in the process.

#### Benefits of Using a Third-Party Trusted Dealer

- **Enhanced Privacy**: The Trusted Dealer has no knowledge of the participants, their identities, or how the keys will be used, thus preserving the privacy of the users and their operations.
- **Limited Trust Requirement**: By restricting the dealer's role to key generation and distribution, and by using cryptographic techniques to blind the process, the level of trust required in the dealer is minimized. The dealer cannot misuse the keys or influence the signing process.
- **Scalability**: Such a service can scale to handle many different key generation requests across various applications and industries without needing to know the details of each use case.
- **Flexibility**: Participants can obtain key packages from the Trusted Dealer and use them in different contexts (e.g., for various signing groups or purposes) without the dealer needing to know the specifics.

#### Possible Security Considerations

1. **Integrity of Key Packages**:
- Participants need to verify that the key packages they receive are correctly generated and not tampered with. This can be done using cryptographic checksums or proofs provided by the dealer.
2. **Trust in the Dealer's Operations**:
- Even though the dealer is designed to be unaware of the use cases, users still need to trust that the dealer is securely generating and distributing key packages without retaining copies or introducing vulnerabilities.
3. **Third-Party Risks**:
- If the Trusted Dealer is compromised, an attacker could potentially interfere with key generation or distribution, so ensuring the dealer's operations are secure and transparent is essential.

#### Blind Trusted Dealer (BTD) Protocol

A proposed protocol for a Blind Trusted Dealer (BTD) using Gordian Sealed Transaction Protocol (GSTP).

1. **Service Advertisement:**
- The BTD service advertises its public key.
- All communications will be encrypted using GSTP, and the BTD service uses Trust on First Use (TOFU), meaning no pre-registration is necessary to use the service.
- Clients of the service can use single-use key pairs for the transaction to avoid correlation with any known identity.
- Clients of the service can use blind channels like TOR to communicate with the BTD service to further enhance privacy.
3. **Threshold Request to TD**:
- **Initiation**: A participant (the "Initiator") sends the desired threshold configuration (e.g., 3-of-5) to the BTD service. The BTD service responds with a unique (“redemption code”) associated with this threshold request. The RC may be contained within an Encrypted State Continuation (ESC) that also contains an expiry date beyond which it cannot be used.
- The ESC can also contain the actual generated key shares, so once the the redemption code is generated it never actually needs to store the keys themselves. This minimizes the amount of state stored by the BTD service.
- The BTD service keeps server-side state so it knows how many times the Redemption Code (RC) has been used.
- While it is desirable to entirely avoid server-side state, in this case, it seems to be necessary to at least have an atomic counter for each RC, which can be deleted after the expiry date.
- **Purpose**: This step creates a specific instance of key distribution tied to the RC, ensuring that the BTD knows how many key shares to generate and distribute, without knowing who will receive them.
4. **Distribution of Redemption Code**:
- **Redemption Code Communication**: The Initiator shares the RC with all other participants in the threshold scheme.
- **Purpose**: The RC serves as a reference that participants use to request their respective key shares from the BTD. This keeps the process coordinated without revealing participant identities to the BTD.
5. **Participants Request Key Shares**:
- **Request to BTD**: Each participant sends the RC to the TD service.
- **Validation by BTD**: The BTD checks the RC and ensures that the number of redemptions does not exceed the number of participants. If the maximum number of key shares has been distributed, the BTD returns an error. Otherwise, it generates and returns an undistributed key share to the requester.
- **Purpose**: This decentralized key distribution process allows participants to independently obtain their key shares without the BTD knowing who the participants are or how they will use the keys.
6. **Public Key Share Exchange**:
- **Exchange Among Participants**: As usual, each participant shares their public key share with the other participants. This step is necessary for the participants to form the group’s public key and perform the signing operations.
- **Purpose**: Ensures that each participant is aware of all other public key shares, which is necessary for aggregating signatures. It also verifies that every participant has exactly one share issued from the RC.

#### Error Detection

The replay protection mechanism ensures that no more than the intended number of key shares are distributed, preventing over-issuance and helping detect potential misuse. Failure modes include:
- A participant uses the RC more than once, in which case at least one participant will receive an error from the BTD.
- An outsider uses the RC, in which case at least one participant will receive an error from the BTD.
- A participant fails to use the RC, or fails to use it by the expiry date, in which case not all participants will have valid key shares.

#### Advantages of This Protocol

- **Decentralized Distribution**: The BTD does not need to know the identities of the participants or their roles. Each participant independently requests and receives their key share, which enhances privacy and decentralization.
- **Minimal BTD Knowledge**: The TD BTD knows the total number of key shares to be distributed and the associated RC. It has no knowledge of how the key shares will be used or who the participants are, which limits the need for trust in the TD.
- **Security**: Assuming all communications are encrypted using participants' public keys, the protocol ensures that key shares are securely distributed and only accessible by the intended recipients.

#### Conclusion

The BTD protocol offers a practical and secure approach to distributing key shares in a threshold cryptography system with the help of a Trusted Dealer. It balances privacy, security, and simplicity, making it well-suited for scenarios where minimizing the dealer's knowledge and decentralizing the distribution process are important.