Transaction Signing

Overview

Transaction signing is a basic process in blockchain systems to verify the ownership and validity of a transaction so that only authorized parties can initiate or authorize transfers of digital assets. Transactions would be open to fraud, unauthorized access or tampering without a valid cryptographic signature, risking the security and trust in the blockchain.

Figure 1: Signing transaction in Blockchain

MPC Transaction Signing

Multi-Party Computation (MPC) wallets enhance this process by enabling decentralized, secure, and private transaction signing. Unlike their single private key competitors, MPC wallets distribute the key into secret shares across different participants or devices, with the following benefits:

• Enhanced Security: The private key is never stored in one place or reconstructed. Participants safely construct an authentic signature (e.g., ECDSA) without exposing their shares, reducing the threat of key theft or loss.

• Privacy through Zero-Knowledge: MPC prevents any participant from learning others' secret shares during signing, keeping confidentiality and avoiding misuse.

• Threshold-Based Authorization: There should be a pre-defined threshold (e.g., t+1 of n participants) that must sign, providing fault tolerance against individual failures or attacks while maintaining operational flexibility.

• Blockchain Compatibility: MPC wallets provide standard cryptographic signatures required by blockchain networks like Bitcoin or Ethereum, allowing secure and auditable transactions.

• Resistance to Attacks: Because the key is distributed among multiple participants, MPC wallets dampen the impact of a single attacked participant, thus enhancing overall security.

Briefly, MPC wallet transaction signing offers secure, private, and fault-tolerant approval of blockchain transactions without the need for a centralized private key. MPC wallets are thus optimized for high-security applications, such as institutional custody or multi-user crypto management.

Figure 2: Signing transaction in MPC wallet

Algorithms for Transaction Signing

Numerous algorithms are used for transaction signing across different blockchains. However, not all blockchains rely on the same signature schemes, which can lead to compatibility issues. In this section, we introduce several signature algorithms that offer distinct advantages in terms of security, efficiency, and suitability for Multi-Party Computation (MPC) environments. While these algorithms are not universally compatible with all blockchains, they provide strong foundations for secure and collaborative signing protocols:

1. Schnorr Signature

The Schnorr signature algorithm is a cryptographic method for signing messages. The Schnorr signature scheme is not threshold-based in its original form, but its mathematical structure makes it an ideal foundation for designing threshold signatures and multisignature (multisig) schemes. It is renowned for its ability to generate short, compact signatures quickly, making it efficient for a variety of applications. Schnorr signatures employ elliptic curve cryptography to provide high security with lower computational complexity. For a detailed explanation of the algorithm, refer to Wikipedia: Schnorr Signature and Crypto StackExchange: EC-Schnorr Multiple Standards. It is high-performance and simple and is a fundamental building block for more advanced signing schemes.

Algorithm

Assume the private key $x$ and public key $P = xG$ are already generated, with an elliptic curve defined by a generator $G$ of order $q$, and a hash function $H$ (e.g., SHA-256).

Signing

For a message $m$ and private key $x$, the nonce $k$ must be random and unique for each signature to prevent private key exposure:

Sign$(m, x)$:

• $k = \text{random\_number}(1, q - 1)$   // Generate a random nonce
• $R = k \cdot G$   // Compute point $R$ on the elliptic curve
• $e = H(R \,\|\, m)$   // Hash of $R$ and message $m$
• $s = (k + e \cdot x) \mod q$   // Compute $s$
• return $(R, s)$   // Signature is the pair $(R, s)$

Verification

For a message $m$, signature $(R, s)$, and public key $P$:

Verify$(m, R, s, P)$:

• $e = H(R \,\|\, m)$   // Hash of $R$ and message $m$
• If $s \cdot G = R + e \cdot P$, return True // Signature is valid
• Else, return False // Signature is invalid

Figure 3: Illustration of the Schnorr signature algorithm

2. MuSig2 (Simple Two-Round Schnorr Multi-Signatures)

MuSig2 is an advanced multi-signature scheme derived from the Schnorr signature system. It is the successor to MuSig1, which enabled multiple parties to collaboratively sign a message by aggregating their individual keys into a single public key and producing a single aggregate signature for a specific transaction. This aggregation reduces data size, lowers associated costs, and enhances privacy by concealing individual signer identities. MuSig2 simplifies the previous scheme by requiring only two rounds of communication among participants to produce a valid signature, making coordination easier and reducing complexity compared to MuSig1’s three-round protocol. For a detailed explanation of the algorithm, refer to https://eprint.iacr.org/2020/1261. This makes it particularly well-suited for distributed signing scenarios.

Algorithm

Assumptions:

• An elliptic curve with a generator $G$ of order $q$.

• A hash function $H$ (e.g. SHA-256).

• A group of $n$ signers, where each signer $i$ has:

  • Private key $x_i$
  • Public key $P_i = x_i G$

• A message $m$ that all signers wish to sign.

• The aggregated public key $P$ is computed as $P = \sum_{i=1}^{n} a_i P_i$ , where $a_i$ are key aggregation coefficients (e.g., $a_i = H(P_1, \ldots, P_n, i)$).

• Each signer generates two nonces (or more, depending on configuration, but we describe the variant with $=2$).

Steps:

MuSig2 consists of two communication rounds, where the first round can be preprocessed before the message $m$ is known, enabling nearly non-interactive signing.

1. First Round: Nonce Sharing

   1.1. Nonce Generation:

   • Each signer $i$ generates two random nonces $k_{i,1}, k_{i,2} \in [1, q-1]$.

   • Computes the corresponding elliptic curve points: $R_{i,1} = k_{i,1} G, \quad R_{i,2} = k_{i,2} G$

   1.2. Nonce Sharing:

   • Each signer $i$ sends their nonce points $R_{i,1}, R_{i,2}$ to the other signers (via a secure channel).

   • This round can be performed in advance, before the message $m$ is known.

2. Second Round: Signing

   2.1. Prepare Aggregated Values:

   • All signers receive the nonce points $R_{i,j}$ from others.

   • Compute a hash coefficient: $b = H(P, m, R_{1,1}, R_{1,2}, \ldots, R_{n,1}, R_{n,2})$, used for linear combination of nonces.

   • For each signer $i$, compute the aggregated nonce point: $R_i = R_{i,1} + b R_{i,2}$

   • The total nonce point is: $R = \sum_{i=1}^{n} R_i$

   2.2. Compute Message Hash:

   • Compute $e = H(R \| P \| m)$, where $P$ is the aggregated public key.

   2.3. Generate Partial Signature:

   • Each signer $i$ computes their partial signature: $s_i = k_{i,1} + b k_{i,2} + e a_i x_i \mod q$
   • Signer $i$ sends $s_i$ to the other signers.

   2.4. Aggregate Signature:

   • All partial signatures are summed: $s = \sum_{i=1}^{n} s_i \mod q$
   • The final signature is the pair $(R, s)$.

Verification

Verification of a MuSig2 signature is identical to standard Schnorr verification.

For message $m$, signature $(R, s)$, and aggregated public key $P$:

• Compute: $e = H(R \| P \| m)$
• Check if: $s G = R + e P$
• If the equality holds, the signature is valid; otherwise, it is invalid.

Figure 4: Illustration of the MuSig2 algorithm with two signers

3. FROST (Flexible Round-Optimized Schnorr Threshold Signatures)

FROST is a Schnorr-based threshold signature scheme which achieves flexibility in the signing process. Depending on the application, it supports single-round and two-round signing protocols. The minimum number of signers needed (e.g., 3 of 5) is set as the threshold, which allows partial participation without sacrificing security. FROST provides mechanisms to deal with critical signers; if a participant fails or acts maliciously, the protocol can abort the participation of the party and proceed without it. This adds flexibility in dynamic environments. An example implementation of FROST is available at University of Waterloo Git: FROST, which is a useful reference for its implementation.

Algorithm

Initialization (Distributed Key Generation - DKG)

Goal: Generate a shared public key and distribute secret shares of the private key among participants.

1. System Parameters

   • Define cryptographic parameters: an elliptic curve, a generator point $G$, and the group order $q$.
   • Set the threshold $t$ (minimum number of participants needed for signing) and the total number of participants $n$ (where $t \leq n$).

2. Polynomial Generation

   • Each participant $P_i$ (for $i = 1, \dots, n$) chooses a random polynomial $f_i(x)$ of degree $t - 1$ where the constant term is their secret key $s_i$.

   • The polynomial is:

     $$f_i(x) = s_i + a_{i,1} x + \dots + a_{i,t-1} x^{t-1}$$

     with random coefficients in $\mathbb{Z}_q$.

3. Commitment Sharing

   • Each participant computes public commitments for their polynomial coefficients:

     $$C_{i,j} = a_{i,j} G \quad \text{for } j = 0, \dots, t - 1$$

   • These commitments are shared with all participants to enable verification.

4. Secret Share Distribution

   • Each participant $P_i$ computes a secret share for every other participant $P_j$:

     $$f_i(j)$$

   • These shares are sent to participant $P_j$ over a secure channel.

5. Verification and Aggregation

   • Each participant $P_j$ verifies the received shares using the commitments $C_{i,j}$.

   • If valid, each participant computes their private key share:

     $$s_j = \sum_{i=1}^{n} f_i(j)$$

   • The shared public key is:

     $$Y = \sum_{i=1}^{n} C_{i,0}, \quad \text{where } C_{i,0} = s_i G$$

Result: Each participant holds a private key share $s_j$, and the group has a shared public key $Y$.

Signing (Two-Round Signing)

Goal: Generate a valid Schnorr signature for a message $m$ using at least $t$ participants.

1. First Round: Nonce Generation

   • Each participant $P_i$ selects two random scalars $d_i, e_i \in \mathbb{Z}_q$.

   • They compute two commitments:

     $$R_{i,1} = d_i G, \quad R_{i,2} = e_i G$$

   • The nonce commitments $(R_{i,1}, R_{i,2})$ are sent to all participants.

2. Nonce Aggregation

   • A coordinator (or each participant) collects the nonces and computes the aggregated nonce:

     $$R = \sum_{i \in S} (R_{i,1} + \iota_i R_{i,2})$$

   • Where:

     • $S$ is the set of $t$ participants.
     • $\iota_i$ is a hash specific to the message and participant (e.g., $\iota_i = H(m, R_{i,1}, R_{i,2}, i)$).

3. Second Round: Partial Signature Generation

   • Each participant $P_i$ computes the challenge:

     $$c = H(R, Y, m)$$

   • They generate a partial signature:

     $$z_i = d_i + \iota_i e_i + \lambda_i s_i c$$

   • Where $\lambda_i$ is the Lagrange coefficient for interpolation at point $i$.

   • Each participant sends $z_i$ to the coordinator.

4. Signature Aggregation

   • The coordinator verifies the partial signatures and aggregates them:

     $$z = \sum_{i \in S} z_i$$

   • The final signature is the pair $(R, z)$.

5. Signature Verification

   • The signature $(R, z)$ is verified using standard Schnorr verification $z G \stackrel{?}{=} R + c Y$, where $c = H(R, Y, m)$

Figure5: Illustration of the FROST algorithm with two signers

Threshold Signature Schemes (TSS)

Threshold Signature Schemes (TSS) are an excellent match for MPC wallets. TSS enables the creation of different combinations of distributed key shares that all together amount to the equivalent of the same private key, without needing to re-create the private key when adding or removing participants or thresholds. This flexibility also allows adding new members to a pre-existing key without altering existing users' private keys, making group management easier. Signing occurs off-chain, with a minimum of data being sent to the blockchain, which accelerates transaction execution and lowers costs. TSS is highly adaptable, allowing for the modification of various underlying algorithms (e.g., Schnorr-based schemes) for threshold signing, making it an agile solution for MPC applications.

Figure 6: Illustration of the TSS algorithm with three signers. Source: https://mirror.xyz

Algorithm

Assumptions

• There are $n$ participants, with $t$ required to sign.
• The private key $x$ is split into $n$ shares $x_1, x_2, \dots, x_n$ using Shamir Secret Sharing.
• The public key $Y = xG$ is known to all (where $G$ is the elliptic curve generator).
• The message to sign is $m$ with its hash $z = \text{hash}(m)$.
• The elliptic curve has parameters: $q$ (group order), $G$ (generator).

Steps of the Algorithm

1. Initialization

   • Each participant $i$ holds their private key share $x_i$.
   • Participants agree on a random nonce $k$ using a distributed key generation protocol (e.g., Pedersen DKG).

2. Nonce Generation

   • Each participant $i$ generates their nonce share $k_i$ (split via Shamir Secret Sharing).

   • Participants jointly compute $R = kG$ using their $k_i$ shares without revealing $k$.

   • Compute:

     $$r = R_x \mod q$$

     where $R_x$ is the $x$-coordinate of point $R$.

3. Signature Computation

   • Each participant $i$ computes their signature share $s_i$:

     $$s_i = k_i^{-1}(z + r x_i) \mod q$$

     where $k_i^{-1}$ is the modular inverse of $k_i$.

   • A subset $S$ of $t$ participants combine their $s_i$ shares using Lagrange interpolation (in field $q$) to obtain the final $s$:

     $$s = \sum_{i \in S} \lambda_i s_i \mod q$$

     where $\lambda_i$ are the Lagrange coefficients.

   • The final signature is the pair $(r, s)$.

4. Signature Verification

   Verification follows the standard ECDSA procedure:

   • Compute:

     $$u_1 = z s^{-1} \mod q, \quad u_2 = r s^{-1} \mod q$$

   • Compute:

     $$P = u_1 G + u_2 Y$$

   • Check if:

     $$P_x \mod q = r$$

   • If true, the signature is valid.

TSS based on ECDSA

The efficiency of different TSS implementations depends greatly on the underlying signature algorithm. For example, Schnorr-based signature schemes offer a simpler and more efficient solution for TSS compared to ECDSA-based TSS, due to the linear and additive nature of Schnorr signatures, which makes secure distribution and aggregation easier. Although Schnorr-based signatures are more TSS-friendly, ECDSA-based TSS is more commonly used because ECDSA is widely adopted in existing systems, wallets, and platforms like Bitcoin and Ethereum, ensuring compatibility. Despite being more complex, ECDSA preserves interoperability with established cryptographic infrastructure.

For the above-mentioned reasons, significant research efforts have been devoted to improving the efficiency of ECDSA-based TSS. Zero-knowledge proofs (ZKPs) enable one to verify the validity of a statement without revealing the underlying data, a feature that has become increasingly significant for cryptographic protocols such as threshold signature schemes (TSS). While such algorithms can enhance the security of TSS, they are often computationally demanding, which can impact the overall efficiency of these systems. The MacKenzie-Reiter algorithm, an early TSS solution, utilized zero-knowledge proofs heavily in the Distributed Key Generation (DKG) process. Due to its computational heaviness and resource demand it failed to keep up with the pace of practical engineering demands. Recent advancements in ZKP technology have spurred the development of more efficient TSS algorithms, which are being utilized heavily in multi-signature wallet solutions in the blockchain ecosystem. One of these algorithms is Lindell's 2017 protocol, which optimized the MacKenzie–Reiter protocol by minimizing the complexity of ZKP proofs. Below, we outline the top TSS algorithms based on the Elliptic Curve Digital Signature Algorithm (ECDSA).

1. Lindell17

The Lindell17 protocol, eprint.iacr.org/2017/552.pdf, is a two-party TSS protocol designed for ECDSA. It significantly improves the efficiency of MacKenzie–Reiter by optimizing cryptographic proofs and interactions. One of the implementation examples is the Gotham City project by ZenGo-X.

• Mechanism: Lindell17 employs homomorphic encryption, the Paillier cryptosystem, to calculate an ECDSA signature. It adopts a client-server model in which both entities hold a share of the private key. The signature is finalized by one of the two entities, generally the server.

• Properties: The protocol is two-party fast signing optimized, with Paillier encryption used to securely compute the signature without fully reconstructing the private key.

• Vulnerabilities: Vulnerabilities were discovered by Fireblocks in certain open-source implementations (e.g., ZenGo and Coinbase WaaS) that deviate from the scientific paper.

Algorithm

1. Setup & Key Generation (Offline)

   1.1. Participants in the protocol, $P_1$ and $P_2$, generate random numbers $x_1$ and $x_2$, respectively, which represent their secret key shares.
   1.2. $P_1$ computes $Q_1 = x_1 \cdot G$ and $P_2$ computes $Q_2 = x_2 \cdot G$.
   1.3. $P_1$ and $P_2$ exchange Pedersen commitments for shares.
   1.4. Participants prove in zero-knowledge that exchanged commitments contain valid discrete logarithms.
   1.5. One participant generates a Paillier keypair and proves in zero-knowledge its correctness to the other participant.
   1.6. Both parties compute the public key $Q = x_1 x_2 G$ and verify proofs.

Result: Both participants hold additive shares of the private key and the common public key $Q$.

2. Online Signing (2 rounds)

When signing a message $m$:

• Round 1: Share Randomness
  • Both participants generate random shares $\rho_i$ and nonce shares $k_i$, keeping them secret.
  • Participants exchange Pedersen commitments of these shares along with zero-knowledge proofs to validate correctness.
• Round 2: Computations
  • Both parties compute $R = k \cdot G, \quad \text{where } k = k_1 + k_2 \; mod \; q,$ in the same way $Q$ is computed in the first part, and extract $r$ as the $x$-coordinate of point $R$.
  • Based on $\rho_1$ and $\rho_2$ (where $\rho = \rho_1 + \rho_2$), parties compute $\beta = \rho \cdot (H(m) + x \cdot r) \mod q$ by using homomorphic encryption and modular arithmetic to securely multiply shared secrets without revealing them.
  • Similarly, they compute $\gamma = \rho \cdot k \mod q$ using the shared values and homomorphic methods.
  • Parties reveal the (homomorphically computed) values $\beta$ and $\gamma$; both agree on the results.
  • Both parties calculate $s = \gamma^{-1} \cdot \beta \mod q,$ which provides them with a valid ECDSA signature $(r, s)$.

2. GG18

GG18 protocol https://eprint.iacr.org/2019/114.pdf, suggested by Gennaro and Goldfeder, is DSA and ECDSA compatible and is a simple multi-party TSS with zero-knowledge extensions.

• Mechanism: GG18 uses four rounds in the DKG phase: three for sharing keys and one for public key verification. Nine rounds are required for signing, with two Multiplicative-to-Additive (MtA) procedures between each pair of participants. These MtA steps, secured with zero-knowledge proofs, convert multiplicative shares to additive ones for ECDSA computation.

• Properties: While viable for any threshold (t, n), the high round complexity of GG18 (nine rounds for signing) is computationally costly. The protocol halts when a malicious participant is detected, but it cannot identify the misbehaving party, which limits accountability.

• Use Case: Its security strength is suitable for use cases requiring strong security, albeit at the cost of its efficiency.

Algorithm

1. Key Generation Phase (Distributed Key Generation - DKG)

1. Initialization

   • A group of $n$ participants aims to generate a shared public key and distributed shares of a private key.
   • A threshold $t$ is defined, where at least $t+1$ participants are needed to reconstruct the secret, but fewer than $t+1$ learn nothing (zero-knowledge property).
   • A cryptographic system is used, typically based on elliptic curves or similar structures.

2. Polynomial Generation

   • Each participant $P_i$ (for $i=1,2,\ldots,n$) randomly generates a secret polynomial $f_i(x)$ of degree $t$
   • The polynomial is of the form $f_i(x) = a_{i,0} + a_{i,1}x + a_{i,2}x^2 + \ldots + a_{i,t}x^t,$, where $a_{i,0}$ is the participant’s secret, and coefficients $a_{i,j}$ are randomly chosen from a finite field.

3. Commitment

   • Each participant $P_i$ computes Pedersen commitments for the coefficients of their polynomial $C_{i,j} = g^{a_{i,j}}$, where $g$ is a group generator (e.g., on elliptic curves).
   • These commitments are publicly broadcast to ensure verifiability and prevent later changes.

4. Sharing Secret Values

   • Each participant $P_i$ computes secret shares for every other participant $s_{i,j} = f_i(j)$, where $j$ is the index of another participant.
   • These shares $s_{i,j}$ are sent privately (e.g., encrypted) to participant $P_j$.

5. Verification of Shares

   • Each participant $P_i$ receives secret shares $s_{i,j}$ from others and verifies them using the commitments $C_{i,j}$.
   • Verification is done via the equation $g^{s_{i,j}} \stackrel{?}{=} \prod_{k=0}^t (C_{i,k})^{j^k}.$
   • If verification fails, participant $P_j$ can complain against $P_i$ for sending invalid shares.

6. Handling Complaints

   • If complaints arise, the system identifies misbehaving participants.
   • Participants who send invalid shares are disqualified, and the process continues with remaining participants.
   • Continuation requires a mutual informal agreement, a sufficient number of honest parties, and trust that all honest parties share the same view of the group.
   • Note: This method does not provide cryptographic proof of misbehavior.

7. Computing Final Shares

   • Each participant $P_i$ sums all valid shares received: $s_i = \sum_j s_{j,i}.$
   • This $s_i$ becomes the secret share of the private key for participant $P_i$.

8. Generating the Public Key

   • The shared public key is computed as: $Y = g^x, \quad \text{where} \quad x = \sum_i a_{i,0}$ is the secret private key (which no single participant knows).
   • The public key can be derived using commitments: $Y = \prod_i C_{i,0},$ since $C_{i,0} = g^{a_{i,0}}$.

9. Zero-Knowledge Property

   • No single participant knows the full private key $x$.
   • The secret is distributed so that $t+1$ participants are needed to reconstruct it (e.g., via Lagrange interpolation), but fewer reveal nothing (zero-knowledge).

2. Signing Protocol (Threshold ECDSA)

Goal: Given the shared private key $x$ (from Part 1, DKG) and the message hash $z = H(m)$, a threshold $t+1$ parties (out of $n$) can compute a valid ECDSA signature: $(r,s) = (x_R \bmod q, k^{-1}(z + r \cdot x) \bmod q)$

The core challenge is to compute $s = k^{-1}(z + r \cdot x)$ without revealing the secret shared key $x$ and the shared nonce $k$.

To do this securely, GG18 uses:

• Paillier homomorphic encryption (for secure multiparty multiplication).
• Multiplicative-to-additive (MtA) protocol.
• Zero-knowledge proofs (for security against malicious behavior).

Signing Steps (GG18):

1. Each party $P_i$ samples a random $k_i \in \mathbb{Z}_q$, computes $R_i = k_i \cdot G,$ and publishes $R_i$ to others. Then everyone computes the public nonce point $R = \sum_i R_i = k \cdot G$ and the $x$-coordinate of $R$ becomes $r = x_R \bmod q.$ All parties agree on $r$.

2. Each party $P_i$ generates a Paillier encryption keypair $(pk_i, sk_i)$ and publicly shares $pk_i$. Paillier enables homomorphic addition/multiplication over encrypted data used for secure computation of $r \cdot x$.

3. Run the Multiplicative-to-Additive (MtA) Protocol. Each pair $(P_i, P_j)$ engages in a two-party MtA protocol to securely compute partial products $k_i \cdot x_j$ without learning each other's secrets. The procedure:

   • $P_j$ encrypts its secret $x_j$ under $P_i$’s Paillier public key $E_{pk_i}(x_j)$
   • $P_i$ homomorphically computes $E(k_i \cdot x_j + \text{noise})$
   • $P_i$ sends the ciphertext and a zero-knowledge proof of correctness to $P_j$.
   • $P_j$ decrypts and obtains a share of $k \cdot x$.
     This repeats for all pairs; all parties combine results to get $z + r \cdot x = z + r \cdot \left(\sum_i x_i\right).$ Thus, additive shares of numerator $z + r \cdot x$ are distributed.

4. Each party holding additive shares of $k = \sum k_i$ and $z + r \cdot x = \sum$ partials from MtA, inverts $k$ collaboratively (e.g., with precomputed inverses or MPC) and computes their share $s_i = k^{-1} \cdot (z + r \cdot x)_i.$ After combining shares $s = \sum_i s_i \bmod q,$ the final signature $(r, s)$ is obtained.

5. Each party checks if $s \neq 0$ and $r \neq 0$. If so, $(r, s)$ is a valid ECDSA signature under the public key.

3. GG20

GG20 https://eprint.iacr.org/2020/540.pdf, which succeeds GG18, streamlines the process with greater efficiency and accountability. Implementations are available at Safeheron/multi-party-sig-cpp, ZenGo-X/multi-party-ecdsa, and Thorchain/tss-lib.

• Mechanism: GG20 signing requires seven rounds, where the first six rounds are message-independent and thus preprocessable. It is the same as GG18 in that it uses Paillier encryption and zero-knowledge proofs for MtA operations to provide secure share computation. GG20 is different from GG18 in that GG20 has an identifiable abort mechanism, i.e., it can determine a cheating participant when the protocol aborts.

• Properties: Seven-round reduction and the ability to preprocess six of them enhance efficiency, while the abortable identification thwarts continued malicious behavior, e.g., denial-of-service-like attacks. This makes GG20 better suited for real-world multi-signature wallet deployments.

• Improvements: Introduced in 2020, GG20 addresses GG18 weaknesses by reducing round complexity and adding fault attribution, leveraging zero-knowledge proofs for privacy and security in the signing process.

Algorithm

1. Key Generation Phase (Distributed Key Generation - DKG)

The key generation phase of GG20 is largely the same as in the GG18 protocol; therefore, we will present only the additions introduced by the GG20 protocol to the key generation phase described in the GG18 section.

1. Initialization
   GG20 enhances the corresponding step in GG18 by introducing session ID binding, each DKG instance is tied to a unique session identifier to prevent replay attacks. Additionally, GG20 uses domain separation tags in hashing to clearly distinguish between different protocol phases.

2. Commitment
   GG20 adds optional range proofs on commitments to the corresponding step in GG18, ensuring that the coefficients are within the expected size for field soundness.

3. Sharing Secret Values
   GG20 improves on GG18 by adding encryption of shares (e.g., via Paillier or ElGamal) to ensure confidentiality, and by requiring a zero-knowledge proof that each party’s Paillier modulus N=p⋅q was generated correctly using safe primes preventing trapdoor attacks that GG18 did not guard against.

4. Handling complaints
   In this step, GG18 does not provide a formal mechanism to prove misbehavior. GG20 introduces Identifiable Abort, which allows a recipient of an invalid share or message to generate a zero-knowledge transcript proving that the sender misbehaved. This non-interactive dispute resolution mechanism enables malicious parties to be identified and excluded from the group, allowing the protocol to proceed with the remaining honest participants.

2: Signing Protocol (Threshold ECDSA)

Step 1: In GG20’s MPC protocol, nonce generation is similar to GG18 but strengthened with robust zero-knowledge proofs that bind each nonce $k_i$​ to its corresponding $R_i$​, preventing rogue-key and bias attacks. Additionally, GG20 employs commitments and ZKPs to prove knowledge of discrete logs without revealing $k_i$​, sometimes using augmented proofs to ensure non-malleability and stronger soundness.

Step 2: GG20 retains a similar Paillier key generation process but introduces more efficient, modular zero-knowledge proofs for correct key generation, often leveraging improved, non-interactive proof systems, like those based on the Fiat-Shamir transform, to reduce proof size and complexity.

Step 3: GG20 retains the core MtA concept but enhances it with stronger composable zero-knowledge proofs often using bulletproofs or aggregated proofs to ensure correctness and reduce overhead when proving many operations simultaneously. It also introduces formal guarantees against leakage and malleability, explicit noise binding to prevent replay attacks, and a modular design that makes MtA a standalone, securely composable sub-protocol.

Step 4: GG20 enhances the collaborative inversion step by using a more robust MPC subprotocol with explicit zero-knowledge proofs that each partial signature $s_i$ is consistent with secret shares, preventing rogue key and substitution attacks. It also improves synchronization and state management to ensure protocol compliance and often includes abort-resilient mechanisms to tolerate misbehaving parties below the threshold.

Step 5: GG20 maintains the same final signature validation but adds collective verification steps, including proofs that the signature was honestly computed, and often uses post-signature zero-knowledge proofs to prevent manipulation during share combining. It also optionally provides non-interactive proofs to enable third-party verification of the signature’s validity under the distributed key.

Summary

A variety of protocols exist for transaction signing, each offering different trade-offs in efficiency, scalability, and security. Schnorr signatures provide a minimal single-party baseline, while MuSig2 enhances coordination among multiple parties. FROST, a modern Threshold Signature Scheme (TSS), offers flexible threshold capabilities and efficient signing. More broadly, TSS protocols integrate well with MPC wallets to enable distributed and cost-effective signing. Lindell17, GG18, and GG20 demonstrate the evolution of zero-knowledge techniques in ECDSA-based threshold schemes. Lindell17 is the most efficient two-party solution with fast signing but must be carefully implemented to avoid vulnerability. GG18 provides a secure multiparty computation protocol at the expense of efficiency, and GG20 achieves a trade-off between security, efficiency, and accountability, which is a more desirable protocol for modern blockchain multi-signature wallets. The final choice for the CryptoProcessor project will depend on specific requirements, including the desired threshold, communication constraints, and blockchain integration needs.