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

P = G·d₁+...+G·dₙ
R = G·k₁·...·kᵤ
I = eₚ(m·n⁻¹+Rₓ·d₁)+...+eₚ(m·n⁻¹+Rₓ·dₙ)
S = dₚ(I·k₁⁻¹·...·kᵤ₋₁⁻¹)·kᵤ

Overall MPC signature complexity: from O(n+2u) to O(3n)

The secp256k1 curve employs a multiplicative aggregation of private keys to generate the aggregated public key P. This is achieved by multiplying the group generator G with each participant's private key d₁, d₂, ..., dₙ. Similarly, the main signature component R is generated by multiplying G with each participant's nonce scalar k₁, k₂, ..., kᵤ.

The intermediate signature component I involves a more complex process using Paillier encryption. Each participant contributes to I by encrypting a value that includes the message hash scalar m, scaled by the inverse of the participant count n⁻¹, and combined with the x-coordinate of R (Rₓ) multiplied by their private key dᵢ. The Paillier encryption function eₚ ensures that these contributions can be aggregated homomorphically.

Finally, the main signature component S is derived by decrypting the aggregated intermediate value I, scaled by the inverses of each participant's nonce scalars k₁⁻¹, k₂⁻¹, ..., kᵤ⁻¹. This step leverages the Paillier decryption function dₚ to reveal the final signature component.

To ensure that the addition of partial S and multiplication by k remains within the range of Paillier modulus, it is important to note that u may be less than n. Current implementation of computation of possibly reduced count of participants u contributing nonces to final signature, followed by computation of Paillier key size b (bits) in range of [2048, 8192] is as follows:

let additions = participants;
let min_bits = 2048;
let max_bits = 8192;
let step_bits = 256;
let nonce_participants = Math.min(additions, 1 + Math.floor((max_bits - step_bits - additions - 1) / step_bits));
let key_bits = Math.ceil(Math.max(min_bits, Math.min(max_bits, 1 + additions + step_bits + step_bits * (nonce_participants - 1))) / 8.0) * 8.0;

[nonce_participants, key_bits]

Definitions

P: Aggregated public key generated through multiplicative aggregation of private keys.
R: Main signature component 1, derived from nonce scalars.
I: Intermediate signature component, encrypted using Paillier encryption.
S: Main signature component 2, obtained through decryption and scaling.
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.
u: Possibly reduced count of participants, used in the generation of R.
k₁₋ₙ: Participant nonce scalar array of n elements (scheme-specific nonce generation)
k₁₋ᵤ: Participant nonce scalar array of u elements
d₁₋ₙ: Participant private key scalar array of n elements
eₚ: Paillier encryption function (homomorphic operations on the result of eₚ are non-modulo based)
dₚ: Paillier decryption function (operations on the result of dₚ are following standard modulo reduction)

secp256k1-schnorr

Algorithm

P = G·d₁+...+G·dₙ
R = G·k₁+...+G·kₙ
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

P = G·d₁+...+G·dₙ
R = G·k₁+...+G·kₙ
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

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

### Phase 2
Pₛ = G·d₁+...+G·dₙ
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
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