# Digital Signature Scheme

:::note[Technical Summary For Cryptographers]
We give a succinct summary of the cryptographic protocols used in the SDK:

* For **ECDSA** we use [DKLs23](https://eprint.iacr.org/2023/765.pdf).
  * We used [SoftSpokenOT](https://eprint.iacr.org/2022/192.pdf) to realize the $\mathcal{F}^{\eta}_{\sf COTe}$ functionality.
  * We used [MRR21](https://eprint.iacr.org/2021/682.pdf) to realize the $\mathcal{F}^{2,kn_{\mathcal{C}},{\mathcal{L}}}_{\sf OT-\bar{1}}$ to realize endemic 1-out-of-2 base OT of batch size $k\cdot n_{\mathcal{C}}$.
* For **EdDSA**, **BIP-340** and **Sr25519** we use [FROST](https://datatracker.ietf.org/doc/rfc9591/).
* We use [BLAKE3](https://github.com/BLAKE3-team/BLAKE3/) official [Rust crate](https://docs.rs/blake3/latest/blake3/) as a pseudorandom generator/function.
:::

## What is a Digital Signature Scheme?

A digital signature scheme realizes, in a sense, classical (i.e. "non-digital", handwritten) signatures but with stronger security guarantees.
Unlike classical signatures, we wish that only a certain entity who owns some *secret key* ($\sf sk$) to be able to authorize some message $\sf m$ by producing a *signature* $\sf s$ which can later be verified by any entity using a public key ($\sf pk$).

More explicitly, a signature scheme is a set of three algorithms: $\sf KeyGen, Sign, Verify$ such that:

* ${\sf KeyGen}$ outputs a pair $\sf (sk,pk)$ where $\sf sk$ is a secret key, held by the key generator while $\sf pk$ is a public key, that is, it is published to the public.
* ${\sf Sign(sk,m)}$ is a method taking a secret key $\sf sk$ and a message $\sf m$ and outputs a signature $\sf sig$.
* ${\sf Verify(pk,m, sig)}$ is a method taking a public $\sf pk$, a message $\sf m$ and a signature $\sf sig$ and verifies whether $\sf sig$ was created by the owner of $\sf sk$. If the verification succeeds it returns $\sf success$ and if it fails it returns $\sf fail$.

A signature scheme should be both *correct* and *secure* that is:

* **Correctness** means that a signature generated by an "honest" signer (i.e. a signer who knows the secret key $\sf sk$) should always be successfully verified. In mathematical notation it means that for all $\sf (sk,pk)$ output by $\sf KeyGen$ and for all message $\sf m$ we have:

$$
\sf Verify(pk,m, Sign(sk,m)) = success
$$

* **Security** means that a malicious entity who doesn't know the secret key $\sf sk$ and wishes to sign some predetermined message $\sf m^*$ should not be able to do this \[^1] even if it is being given signatures of other messages of its choice.\[^2]

:::warning
Notice that the security guarantees do not hold against the scenario where the secret key falls into the hands of a malicious entity. This is a key reason to use Sodot MPC SDK.
:::

### Types of Digital Signature Schemes

Along the years a large number of digital signature schemes have been introduced and in the past few decades two main families of signature schemes have become prevalent in a wide range of use cases:

* [Elliptic Curve Digital Signature Algorithm (ECDSA)](https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)
* [Edwards-curve Digital Signature Algorithm (EdDSA)](https://en.wikipedia.org/wiki/EdDSA)
* [Schnorr Digital Signature Algorithm (used for BIP-340)](https://en.wikipedia.org/wiki/Schnorr_signature)

Indeed, each of these schemes has its own triple of $\sf KeyGen, Sign, Verify$ algorithms.
We will not be elaborating on these schemes here, the interested reader can follow the links above for further reading.

:::note
While these digital signature algorithms have similar names, they are very different from one another.
:::

:::tip[Feature]
Sodot MPC SDK supports ECDSA, EdDSA and BIP-340 schemes.
:::

## What is a Threshold Signature Scheme?

As we've seen, the security of the signature scheme holds as long as the secret key is stored **securely**.
But what does it even mean "securely" in this context?
Well, the private key should be both *secret* and *persistent*.

* Secret in the sense that no malicious entity should be able to retrieve the key.
* Persistent in the sense that the entity who is eligible to use the key is indeed able to use it.

One way to ensure these two properties is by storing the secret key in a [Hardware Security Module (HSM)](https://en.wikipedia.org/wiki/Hardware_security_module).
This, however, introduces a [single point of failure](https://en.wikipedia.org/wiki/Single_point_of_failure), as in the case of a loss or corruption of the HSM, the key material stored inside of it is lost.
Another, more engineering-oriented argument against HSMs is that they introduce a [scalability](https://en.wikipedia.org/wiki/Scalability) bottleneck as they possess limited processing capacity.

To address the issues above, cryptographers have come up with threshold signature schemes (TSS).
These signature schemes operate in a distributed manner, between a set of $N$ clients with respect to a predetermined threshold $T$ where $T \leq N$.
Informally, the secret key is split between the $N$ clients such that any subset of at least $T$ of them is capable of signing any message.

Slightly more formally, we say a signature scheme is a threshold signature scheme if on top of the existing $\sf KeyGen, Sign, Verify$ two additional algorithms are introduced:

* $\sf DistributedKeyGen$ is a distributed algorithm between the $N$ clients resulting in a public key $\sf pk$ and $N$ secret key shares ${\sf sk_1,\ldots,sk}_N$ where client number $i$ holds $\sf sk_i$.
* $\sf DistributedSign(sk_{i_1},\ldots,sk_{i_T}, m)$ is a distributed algorithm taking place between $T$ clients with secret shared $\sf sk_{i_1},\ldots,sk_{i_T}$ resulting in a signature $\sf sig$ on a message $\sf m$.

Similarly, we require both *correctness* and *security*:

* **Correctness** for every $N$ and every $1\leq T\leq N$, and every public key $\sf pk$ and secret key shares $\sf sk_1,\ldots,sk_N$ generated by $\sf DistributedKeyGen$ and every subset of $T$ secret shared $\sf sk_{i_1},\ldots,sk_{i_T}$ and every message $m$ it holds that:

$$
\sf Verify(pk, m, DistributedSign(sk_{i_1},\ldots,sk_{i_T},m)) = success
$$

* **Security** every malicious entity holding less than $T$ secret shares should not be able to sign a predetermined message $m^*$ even if being given signatures of other messages of its choice.

:::warning
The security guarantees of the TSS do not hold against the leakage of $T$ secret shares.
Therefore, $T$ should be set sufficiently high.
:::

:::warning
Generating a valid signature is impossible if $N-T$ shares have been lost.
Therefore, $T$ should be set not too close to $N$.
:::

### How should $T$ be set with respect to $N$?

The above two notes result in a somewhat contradictory conclusion, that is:

* We want persistency, so we can't have $T=N$ as in this extreme case, the loss of a single key share implies inability to sign any message.
* We also want security, so we can't have $T=1$ as in this extreme case, the loss of a single key share implies loss of all security guarantees.

Therefore, setting $T$ somewhere in the middle makes most sense in practice.

:::tip[Feature]
Sodot MPC SDK supports ECDSA, EdDSA and BIP-340 TSS for all values of threshold $T$ and any number of participants $N$.
:::

\[^1]: Cryptographers usually refer to this "inability" as being able to do this with very small probability.
\[^2]: This notion is known as "EUF-CMA" security.