> ## Documentation Index
> Fetch the complete documentation index at: https://docs.spark.money/llms.txt
> Use this file to discover all available pages before exploring further.

# 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

<div>
  In Spark, transactions require co-signing by a user and a group of Signing Operators (see [SOs](/learn/technical-definitions#spark-operator-so)), together SOs make up that Spark Entity [(SE)](/learn/technical-definitions#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.
</div>

## Key Generation

### User Key

<div>
  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.
</div>

### SO Keys

<div>
  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](https://eprint.iacr.org/2020/852.pdf).
</div>

## Key Aggregation

<div>
  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$.
</div>

## Pre-processing

<div>
  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.
</div>

## Signing Flow

<div>
  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}$.
</div>

## Key Tweaks

<div>
  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))$.
</div>

### Additive Tweak

<div>
  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$
</div>

### Multiplicative Tweak

<div>
  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)$
</div>

### Secure Tweak Distribution

<div>
  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$.
</div>

## Key Split

<div>
  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.
</div>

### Process

<div>
  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)$
</div>