Composition

This section explores the process of multi-party computation (MPC) of DSAs used within bridging system: secp256k1, secp256k1-schnorr, ed25519 and ed25519-clsag.

Syntax: +...+, ·...· indicates that the computation continues with the result of the expression in another participant's environment, highlighting the collaborative nature of MPC.

secp256k1

Algorithm

### Round 1
P = G·d₁+...+G·dₙ
R = G·k₁+...+kₙ

### Round 2
Pᵢ = kₚ()
Xᵢ = eₚ(kᵢ, Pᵢ)
Yᵢ = eₚ(m·n⁻¹+Rₓ·dᵢ, Pᵢ)

### Round 3
for n if j ≠ i or n = 1 do
    Xdⱼ = eₚ(Xdⱼ+Xⱼ·γᵢ-Xγᵢⱼ, Pⱼ)
    Ydⱼ = eₚ(Ydⱼ+Yⱼ·γᵢ-Yγᵢⱼ, Pⱼ)

### Round 4
Xᵢ = kᵢ·γᵢ+dₚ(Xdᵢ, Pᵢ)+∑(Xγᵢ)
Yᵢ = (m·n⁻¹+Rₓ·dᵢ)·γᵢ+dₚ(Ydᵢ, Pᵢ)+∑(Yγᵢ)
S = ∑(Y)·∑(X)⁻¹ if i = n-1

Overall MPC signature complexity: from O(4n)

The secp256k1 variant is fundamentally different from the Schnorr and ed25519 variants because ECDSA's signing equation involves an inverse of a nonce sum. This prevents simple linear aggregation, so the protocol relies on Paillier homomorphic encryption to compute products of distributed secrets without any single participant ever learning another's private key or nonce.

Round 1 establishes the aggregated public key P by adding the results of multiplying the group generator G with each participant's private key dᵢ, exactly as in the other variants. The main signature component R is generated by adding the results of multiplying G with each participant's nonce scalar kᵢ. Its x-coordinate, Rₓ, becomes the r component of the final ECDSA signature.

Round 2 begins the homomorphic phase. Each participant generates a Paillier keypair via kₚ() and publishes its public key Pᵢ. Under that key, each participant encrypts two values: their nonce share kᵢ, producing ciphertext Xᵢ, and their message-key term m·n⁻¹+Rₓ·dᵢ (the per-participant split of the ECDSA equation), producing ciphertext Yᵢ. These encrypted contributions are broadcast so that all participants can operate on them homomorphically.

Round 3 performs the multiplicative-to-additive step. Each participant i, holding its private masking scalar γᵢ, uses the additive-homomorphic property of Paillier to multiply every other participant's ciphertext by γᵢ and subtract a fresh blinding beta factor (Xγᵢⱼ for the nonce product, Yγᵢⱼ for the message-key product), folding the result into that target's running accumulator Xdⱼ/Ydⱼ. The betas are kept private by their chooser and cancel out once all shares are summed, so they blind intermediate values without affecting the final signature.

Round 4 completes the computation. Each participant decrypts its own accumulated ciphertext with its Paillier secret key to recover an additive share of the masked nonce product (Xᵢ) and the masked message-key product (Yᵢ), then adds back its private beta sum so that all blinding factors cancel across participants. The final signature component S is computed by the last participant as ∑(Y)·∑(X)⁻¹, which reduces to (m+Rₓ·d)/k, exactly matching standard ECDSA's s value when verified against the aggregated public key P.

Definitions

P: Aggregated public key generated through additive aggregation of private keys.
R: Main signature component 1, derived from nonce scalars.
S: Main signature component 2, incorporating a hash function and the inverse of the aggregated masked nonce product.
G: Group generator used as a base point for elliptic curve operations.
m: Message hash scalar or message bytes, incorporated into the signature generation process.
n: Count of participants involved in the MPC protocol.
k₁₋ₙ: Participant nonce scalar array of n elements, ensuring unique contributions to the signature.
d₁₋ₙ: Participant private key scalar array of n elements, aggregated to form the public key.
Rₓ: x-coordinate of the aggregated nonce point R, used as the r component of the ECDSA signature.
γᵢ: Per-participant masking scalar (gamma), chosen privately by each participant and used to blind products during homomorphic computation so that intermediate values can be safely revealed.
Xγᵢⱼ / Yγᵢⱼ: Blinding beta factors chosen by participant i toward participant j, one for the nonce product and one for the message-key product; each is added into its own accumulator and subtracted from another's so that all betas cancel when shares are summed.
Pᵢ: Paillier public key of participant i, generated via kₚ().
eₚ / dₚ: Homomorphic encryption function given a public key p, and the corresponding decryption function given its secret key.
Xᵢ / Yᵢ: Encrypted per-participant contributions to the nonce product (X) and message-key product (Y), accumulated homomorphically across participants.

secp256k1-schnorr

Algorithm

### Round 1
P = G·d₁+...+G·dₙ
R = G·k₁+...+G·kₙ

### Round 2
S = (k₁+hₚ(R||P||m)·d₁·p)+...+(kₙ+hₚ(R||P||m)·(dₙ+t)·p)

Overall MPC signature complexity: O(2n)

The secp256k1-schnorr variant uses an additive aggregation of private keys to generate the aggregated public key P. This is achieved by adding the results of multiplying the group generator G with each participant's private key dᵢ.

Similarly, the main signature component R is generated by adding the results of multiplying G with each participant's nonce scalar kᵢ. This step ensures that each participant contributes uniquely to R.

The main signature component S involves a more complex process using a scheme-specific hash function hₚ. Each participant contributes to S by adding their nonce scalar kᵢ to the product of the hash of the concatenated values of R, P, and m (hₚ(R||P||m)), their private key dᵢ, and the y-coordinate parity p. Additionally, a public key tweak scalar t is incorporated into the last term of the summation. This ensures that the signature component S is uniquely determined by the contributions of all participants.

The tweak t is a Bitcoin-specific option designed to ensure compliance with Taproot signatures. This adjustment helps in achieving enhanced privacy and security features specific to the Bitcoin network.

Definitions

P: Aggregated public key generated through additive aggregation of private keys.
R: Main signature component 1, derived from nonce scalars.
S: Main signature component 2, incorporating a hash function and parity information.
G: Group generator used as a base point for elliptic curve operations.
p: y-coordinate parity of P (1 if even, -1 if odd), incorporated into the signature generation process.
t: Public key tweak scalar or zero, added to the last term of the summation in S.
m: Message hash scalar or message bytes, incorporated into the signature generation process.
n: Count of participants involved in the MPC protocol.
k₁₋ₙ: Participant nonce scalar array of n elements, ensuring unique contributions to the signature.
d₁₋ₙ: Participant private key scalar array of n elements, aggregated to form the public key.
hₚ: Scheme-specific hash function

ed25519

Algorithm

### Round 1
P = G·d₁+...+G·dₙ
R = G·k₁+...+G·kₙ

### Round 2
S = (k₁+hₚ(R||P||m)·d₁)+...+(kₙ+hₚ(R||P||m)·dₙ)

Overall MPC signature complexity: O(2n)

The ed25519 curve also employs an additive aggregation of private keys to generate the aggregated public key P. This is similar to the secp256k1-schnorr variant, achieved by adding the results of multiplying the group generator G with each participant's private key dᵢ .

The main signature component R is generated by adding the results of multiplying G with each participant's nonce scalar kᵢ. This ensures that each participant contributes uniquely to R.

The main signature component S involves a process using a scheme-specific hash function hₚ. Each participant contributes to S by adding their nonce scalar kᵢ to the product of the hash of the concatenated values of R, P, and m (hₚ(R||P||m)) and their private key dᵢ. This ensures that the signature component S is uniquely determined by the contributions of all participants.

Definitions

P: Aggregated public key generated through additive aggregation of private keys.
R: Main signature component 1, derived from nonce scalars.
S: Main signature component 2, incorporating a hash function.
G: Group generator used as a base point for elliptic curve operations.
m: Message hash scalar or message bytes, incorporated into the signature generation process.
n: Count of participants involved in the MPC protocol.
k₁₋ₙ: Participant nonce scalar array of n elements, ensuring unique contributions to the signature.
d₁₋ₙ: Participant private key scalar array of n elements, aggregated to form the public key.
hₚ: Scheme-specific hash function

ed25519-clsag

Algorithm

### Round 1
Pₛ = G·d₁+...+G·dₙ

### Round 2
H = Hₚ(Kₜ)
I = H·d₁+...+H·dₙ+H·dₛ

### Round 3
Pᵥ = G·Hₛ(Pₛ)
Aₕ = H·a₁+...+H·aₙ
A₉ = G·a₁+...+G·aₙ
z = r-r'
D = H·z
Dₜ = D/8
m = H(tx_prefix_hash||rctsig_base_hash||rctsig_prunable_hash)
μP = Hₛ("CLSAG_agg_0"||K₁||...||Kₙ₋₁||C₁||...||Cₙ₋₁||I||Dₜ||C')
μC = Hₛ("CLSAG_agg_1"||K₁||...||Kₙ₋₁||C₁||...||Cₙ₋₁||I||Dₜ||C')
c = Hₛ("CLSAG_round"||K₁||...||Kₙ₋₁||C₁||...||Cₙ₋₁||C'||m||A₉||Aₕ)
i = t+1 mod n
c₁ = [i=0]·c+[i≠0]·c₁
while i ≠ t do
    Hᵢ = Hₚ(Kᵢ)
    zᵢ = Cᵢ-C'
    Lᵢ = G·sᵢ+Kᵢ·(c·μP)+zᵢ·(c·μC)
    Rᵢ = Hᵢ·sᵢ+I·(c·μP)+D·(c·μC)
    c = Hₛ("CLSAG_round"||K₁||...||Kₙ₋₁||C₁||...||Cₙ₋₁||C'||m||Lᵢ||Rᵢ)
    c₁ = [i=0]·c+[i≠0]·c₁
    i = t+1 mod n

### Round 4
sₜ = -c·(μP·dₛ+μC·z)+(a₁-c·μP·d₁)+...+(aₙ-c·μP·dₙ)

Overall MPC signature complexity: O(4n)

The ed25519-CLSAG protocol enables a Multi-Party Computation (MPC) framework for generating Concise Linkable Spontaneous Anonymous Group signatures. This allows multiple parties to jointly sign a transaction without any single participant revealing their private keys. The protocol execution is structured into distinct phases that deviate from standard signature aggregation:

Key Image Prepass: Unlike typical schemes where linkable tags are processed during the ring generation step, this protocol mandates a rigorous "prepass" phase before any aggregation begins. All required Key Images (I) for every input in the transaction must be aggregated first. This is necessary because the challenge message hash (m), which drives the cryptographic binding of the signature, incorporates these key images; without them established upfront, the state machine cannot advance to the commitment phase.
Public Aggregation: Once the prepass ensures linkability across all inputs, the protocol proceeds to aggregate public components. This includes combining spend keys (Pₛ), view keys derived from those spends (to maintain consistency with the network's linking rules), and nonce-based commitments (Aₕ, A₉). Standard elliptic curve operations and hash-to-point functions are used here to construct a unified ring structure that binds all participants cryptographically.
Challenge Generation: After establishing the aggregate ring, the last participant in the sequence computes aggregation coefficients μP and μC. These values serve as weights for each public key within the proof. A global challenge scalar c is then generated by hashing these aggregated elements alongside the pre-calculated message hash (m), ensuring that every subsequent contribution to the signature is tightly bound to this specific transaction event.
Sequential Loop Execution: The computation of intermediate values Lᵢ and Rᵢ which depend on nonces established during setup but do not require active secret sharing is handled sequentially by a single node (the last participant). Since these operations rely solely on public challenges, commitments, and initial random masks, they can be performed locally without real-time collaboration or additional communication overhead.
Collaborative Response Scalar: The final response scalar sₜ, associated with the true signer at index t, is generated through a collaborative additive process to prevent unilateral forgery. This begins with an initialization term based on public values (-c·(μP·dₛ+μC·z)). Following this, every participant contributes their unique secret share, derived from their individual nonce (aᵢ) and derivation scalar (dᵢ), adding them to the cumulative sum. The valid signature sₜ is only realized once all additive shares have been successfully combined.

Definitions

m: MLSAG message hash
G: Group generator used as a base point for elliptic curve operations.
dₛ: Derivation scalar of true vin
dₙ: Participant private key scalar array of n elements
Kₙ: Vout public key point array of n elements
t: Index of true spender within the ring
Aₕ: Aggregated point H scalar multiplied by all nonces
A₉: Public key of all nonces
z: Commitment mask difference
r: Commitment mask of true spender vin
r': Pseudo out mask of true spender vin
D: Image of z
Cₙ: Commitment mask scalar array of n elements
C': Pseudo-output commitment of true spender vin
Pₛ: Aggregated public spend key
Pᵥ: Aggregated public view key
H: Hash to point of Kₜ
I: Key image of true vin
aₙ: Participant nonce scalar array of n elements
Dₜ: D divided by 8, CLSAG output point d
c₁: Set to c when i = 0, CLSAG output scalar c1
sₙ: Response scalars, all random except sₜ, CLSAG output scalar array s
μP: Public-key aggregation coefficient
μC: Commitment aggregation coefficient
c: Challenge scalar
Hₛ: Hash to scalar function
Hₚ: Hash to point function
H: Keccak256 hash function