Multi-party Schnorr Signature Scheme: Sparkle

This is a Rust implementation of Sparkle, the recent threshold Schnorr signature scheme on CRYPTO 2023 ([1]). While the original paper adopts a centralized key generation, we instead employed the distributed key generation (DKG) from FROST, another threshold Schnorr signature scheme on SAC 2021 ([2]) for better alignment with practical use.

Particularly, thanks to two of winson-wen's contributions:

• the Rust implementation framework (see \luban_core\, \luban_manager\) for communications among multiple parties in the upcoming open-source repository luban
• the Rust open-source repository xuanmi_base_support for gracefully handling exceptions (Result, Option, Error, etc)

we instantiated Sparkle on Curve25519, supported by the crate curve25519_dalek.

Note that, part of this implementation is inspired by the PoC code of FROST released by authors of [2] and the GG18 implementation multi-party-ecdsa by ZenGo-X.

There are a few differences from the original protocol in [1]:

• Replaced the centralized key generation (simple Shamir secret sharing and centralized distribution) by the distributed key generation with Pedersen commitments in FROST
• Added in Combine the validation of local signature shares received from other parties before combining

Following is a high-level comparison among FROST, FROST2, and Sparkle. Please refer to [1] for further details.

Scheme	Static Assumptions	Sign			Combine
		rounds	exp	H	exp	H
FROST	OMDL+ROM	2	t+2	t+1	t	t
FROST2	OMDL+ROM	2	3	2	1	1
Sparkle	DL+ROM	3	1	t+2	0	0

<style> table { margin: auto; } </style>

1. Crites, E., Komlo, C., Maller, M. (2023). Fully Adaptive Schnorr Threshold Signatures. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14081. Springer, Cham. https://doi.org/10.1007/978-3-031-38557-5_22

2. Komlo, C., Goldberg, I. (2021). FROST: Flexible Round-Optimized Schnorr Threshold Signatures. In: Dunkelman, O., Jacobson, Jr., M.J., O'Flynn, C. (eds) Selected Areas in Cryptography. SAC 2020. Lecture Notes in Computer Science(), vol 12804. Springer, Cham. https://doi.org/10.1007/978-3-030-81652-0_2

Build

make release

Launch Manager

cd build
./luban_manager

Keygen

Support the distributed key generation among $n$ parties (if denoted by $P_1$, $P_2$, etc.) under a $(t,n)$ Ed25519 signature scheme. For your information, sample.keygen1.json (and etc.) contains configurations, while k1.json (and etc.) is the path of the keystore file generated by $P_1$.

Need going to the folder \built, then open 3 tabs for each of the following:

./sparkle_test sample.keygen1.json k1.json
./sparkle_test sample.keygen2.json k2.json
./sparkle_test sample.keygen3.json k3.json 

Sign

Support the signing among a quarum of parties (over $t$) under a $(t,n)$ Ed25519 signature scheme. For your information, sample.sign23.json (and etc.) contains configurations for the signing procedure among 2 out of 3 parties from Keygen, while k1.json indicates the keystore file of $P_1$ is involved.

Need going to the folder \built, then open 2 tabs for each of the following:

./sparkle_test sample.sign23.json k1.json
./sparkle_test sample.sign23.json k2.json

Note

For our convenience, we didn't handle many kinds of trivial exceptions, such as:

• when different parameters (like $t,n$) are set among parties;
• when different messages are signed among parties.

Last but not least, due to some out-of-my-league issues in assigning uuid for parties in manager.rs, there will be a trivial bug when calling Sign in the following way:

a consecutive call of Sign with more parties involved than the last call of Sign.

For instance, when calling a $1/3/3$ Sign right after a call of $1/2/3$ Sign, uuid of the two calls are as follows:

$$ \begin{align*} P_1:&{\rm ID} = 1 &{\rm uuid} = {\rm uuid}_1 \\ P_2:&{\rm ID} = 2 &{\rm uuid} = {\rm uuid}_1 \end{align*} $$

$$ \begin{align*} P_1:&{\rm ID} = 3 &{\rm uuid} = {\rm uuid}_1 \\ P_2:&{\rm ID} = 1 &{\rm uuid} = {\rm uuid}_2 \\ P_3:~~&{\rm ID} = 2 &{\rm uuid} = {\rm uuid}_2 \end{align*} $$

It can be avoided by re-running manager. Would appreciate any fix for this.