Spark FROST

Spark employs a customized version of the FROST (Flexible Round-Optimized Schnorr Threshold) signing scheme to enable transaction signing by a required participant alongside a threshold group of signers known as Signing Operators (SOs).

​

Problem Statement

In Spark, transactions require co-signing by a user and a group of Signing Operators (see SOs), together SOs make up that Spark Entity (SE). The signature must meet these requirements:

• Threshold Signing for SOs: Only $t$ out of $n$ total SOs are needed to complete the signing process.
• Mandatory User Signing: The user’s participation is essential for a valid signature.
• Single Schnorr Signature: The final signature must be aggregated into a single Schnorr signature, ruling out multi-signature schemes like 2-of-2. The final signature is the aggregate of the user’s signature and the SOs’ signatures, where the user is the required participant.

Additionally, the cryptographic keys must support:

• Tweakability: Keys can be modified by adding or multiplying a tweak value.
• Additive Aggregatability: Given all shards of two keys (e.g., key1 and key2), it must be possible to derive all shards for their sum (key1 + key2).

This document presents a modified FROST signing scheme tailored to address these needs in Spark.

​

Key Generation

​

User Key

The user independently generates a single key pair, denoted as $(sk_{user}, pk_{user})$, where $sk_{user}$ is the secret key and $pk_{user}$ is the corresponding public key.

​

SO Keys

The Signing Operators (SOs) collaboratively generate a threshold signing key pair, denoted as $(sk_{so}, pk_{so})$, using a Distributed Key Generation (DKG) protocol. Each SO receives a Shamir secret share $ss_i$ of $sk_{so}$, configured with a threshold $(t, n)$, meaning any $t$ of the $n$ SOs can reconstruct the key.

Note: Details of the secure DKG process are beyond the scope of this document. You can find more information in the FROST paper.

​

Key Aggregation

The user’s key and the SOs’ key are combined into an aggregated key using additive aggregation:

• The aggregated secret key is computed as $sk_{agg} = sk_{user} + sk_{so}$.
• The corresponding public key is $Y = pk_{user} + pk_{so}$.

All participants must know the aggregated public key $Y$.

​

Pre-processing

Mirroring FROST’s pre-processing phase, all participants generate and commit to nonces:

• SO Nonces: Each SO generates nonce pairs $(d_{ij}, e_{ij})$ and their commitments $(D_{ij}, E_{ij})$, where $D_{ij} = g^{d_{ij}}$ and $E_{ij} = g^{e_{ij}}$, using a fixed generator $g$.
• User Nonces: The user generates nonce pairs $(d_{user_i}, e_{user_i})$ and commitments $(D_{user_i}, E_{user_i})$, sharing these commitments with all SOs.

These nonces enhance security during signing by preventing replay attacks.

​

Signing Flow

The signing process involves the user, a coordinator, and a subset of SOs, proceeding as follows:

1. Initiation:

   • The user submits a signing request for message $m$ to a signing operator coordinator.

2. Participant and Nonce Selection:

   • The coordinator selects a set $S$ of $t$ participating SOs.
   • It compiles an unused nonce commitment list $B = \{(D_{ij}, E_{ij}) \mid i \in S\} \cup \{(D_{user_j}, E_{user_j})\}$ and broadcasts $B$ to all participants.

3. Signature Share Calculation by SOs:

   • Each SO $i \in S$ computes:
     • $\rho_i = H_1(i, m, B)$, using a hash function $H_1$.
     • Nonce contribution: $R_i = D_{ij} \cdot E_{ij}^{\rho_i}$.
     • Challenge: $c = H_2(R, Y, m)$, where $R = \prod_{i \in S} R_i$.
     • Signature share: $z_i = d_{ij} + e_{ij} \rho_i + \lambda_i ss_i c$, where $\lambda_i$ is the Lagrange coefficient for reconstructing $sk_{so}$.

4. SO Signature Aggregation:

   • The coordinator aggregates the SO shares: $z_{so} = \sum_{i \in S} z_i$.
   • It computes $R_{so} = \prod_{i \in S} R_i$, validates the partial signature, and sends $(R_{so}, z_{so})$ along with $B$ to the user.

5. User Signature Share Calculation:

   • The user computes:
     • $\rho_{user} = H_1(0, m, B)$ (assuming user index 0).
     • Nonce contribution: $R_{user} = D_{user_j} \cdot E_{user_j}^{\rho_{user}}$.
     • Full nonce: $R = R_{so} \cdot R_{user}$.
     • Challenge: $c = H_2(R, Y, m)$.
     • Signature share: $z_{user} = d_{user_j} + e_{user_j} \rho_{user} + sk_{user} c$.

6. Final Signature:

   • The user aggregates the final signature as $(R, z)$, where $z = z_{so} + z_{user}$.

​

Key Tweaks

The SO key $\mathit{sk_{so}}$ is shared via Shamir secret sharing with the polynomial:

$f(x) = \mathit{sk_{so}} + a_1 x + a_2 x^2 + \cdots + a_{t-1} x^{t-1}$

Each SO $i$ holds the share $(i, f(i))$.

​

Additive Tweak

To tweak $\mathit{sk_{so}}$ by adding $t$ (i.e., $\mathit{sk_{so}'} = \mathit{sk_{so}} + t$):

• Define the new polynomial $f'(x) = f(x) + t$
• Update each share to $f'(i) = f(i) + t$

​

Multiplicative Tweak

For a multiplicative tweak by $t$ (i.e., $\mathit{sk_{so}'} = t \cdot \mathit{sk_{so}}$):

• Update each share to $f'(i) = t \cdot f(i)$

​

Secure Tweak Distribution

Directly sharing $t$ with SOs risks key exposure if the sender is an SO or colludes with one. Instead:

• Construct a polynomial $g(x)$ of degree $t-1$ where $g(0) = t$
• Distribute $g(i)$ to each SO $i$
• Each SO updates their share: $f'(i) = f(i) + g(i)$

This method applies the tweak securely without revealing $t$.

​

Key Split

When splitting a key into $n$ child keys (e.g., for transaction splitting), the property holds:

$\mathit{Alice_{old}} + \mathit{SO_{old}} = \sum_{i=1}^n (\mathit{Alice_i} + \mathit{SO_i})$

Here, $\mathit{Alice_{old}}$ and $\mathit{SO_{old}}$ are the original user and SO keys, and $\mathit{Alice_i}$ and $\mathit{SO_i}$ are the child keys.

​

Process

1. User Key Splitting:

   • The user (Alice) generates $n$ key pairs $(\mathit{sk_{Alice_i}}, \mathit{pk_{Alice_i}})$ for $i = 1$ to $n$
   • Compute $\mathit{sum_{Alice}} = \sum_{i=1}^n \mathit{sk_{Alice_i}}$
   • Calculate $\mathit{Tweak} = \mathit{sk_{Alice_{old}}} - \mathit{sum_{Alice}}$

2. Tweak Communication:

   • The user sends $\mathit{Tweak}$ to the SOs.

3. SO Key Splitting:

   • The SOs use DKG to generate $n-1$ key pairs $(\mathit{sk_{SO_i}}, \mathit{pk_{SO_i}})$ for $i = 1$ to $n-1$
   • Set the $n$-th key as $\mathit{sk_{SO_n}} = \mathit{sk_{SO_{old}}} - \left( \sum_{i=1}^{n-1} \mathit{sk_{SO_i}} - \mathit{Tweak} \right)$

4. Verification:

   • The sum of child keys is: $\sum_{i=1}^n \mathit{sk_{Alice_i}} + \sum_{i=1}^n \mathit{sk_{SO_i}} = \mathit{sum_{Alice}} + \sum_{i=1}^{n-1} \mathit{sk_{SO_i}} + \mathit{sk_{SO_{old}}} - \sum_{i=1}^{n-1} \mathit{sk_{SO_i}} + \mathit{Tweak}$
   • Substituting $\mathit{Tweak} = \mathit{sk_{Alice_{old}}} - \mathit{sum_{Alice}}$: $= \mathit{sum_{Alice}} + \mathit{sk_{SO_{old}}} + (\mathit{sk_{Alice_{old}}} - \mathit{sum_{Alice}}) = \mathit{sk_{Alice_{old}}} + \mathit{sk_{SO_{old}}}$

5. Shard Adjustment:

   • For SOs’ Shamir shares, the $n$-th key’s share for SO $j$ is adjusted as: $f_{SO_n}(j) = f_{SO_{old}}(j) - \left( \sum_{i=1}^{n-1} f_{SO_i}(j) - \mathit{Tweak} \right)$