# Multiparty Schnorr signatures #

Here a problem of constructing a threshold signature system to be used in IOTA Smart Contracts consensus protocol is considered.

## A Longer TL;DR ##

This post present a DKG and threshold signature protocol for IOTA Smart Contracts consesus protocol. There are two options for a DKG protocol: 1) interactive (more networking rounds with complaints and p2p interaction but simpler crypto), and 2) non-interactive (with publicly verifiable encryption and zero-knowledge proofs, without p2p interaction and extra rounds); non-interactive DKG can be DL-based and pairing-based. And there are two options for signature platform: Schnorr (need to run DKG to generate nonce) and BLS. A DL-based DKG implies Schnorr-based signature, and pairing-based DKG implies BLS-based signature.

During DKG each party generates and shares partial secret, the final secret scalar is derived as a sum of partial secrets from each party. The challenging part is to make sure the shares are correct. An interactive DKG has additional round to verify shares, complaint if verification fails and construct a set of verified parties. A non-interactive DKG uses sketchy verifiable encryption algorithm so that only target recipient can decrypt a secret share but everyone can validate that the share is indeed valid. Groth proposed such verifiable encryption and non-interactive pairing-based DKG in a recent paper. Here we make an attempt at constructing a similar scheme but based on DL problem. Proofs needed to make the protocol secure include: proof that encrypted share is correct, proof that encrypted share can be decrypted by a party, proof that recovered secret is correct. Interactive secret sharing schemes usually allow to verify a *plain* share against a public committed value, non-interactive protocol must be able to verify *encrypted* share.

Verifiable encryption by Groth is a bilinear variant of ElGamal PKE with forward secrecy. The scheme encrypts a scalar by splitting it into reasonably small parts and brute-forcing DL during decryption. The scheme allows to construct a NIZKP of valid sharing. Bilinearity is only used to make encryption scheme forward secure. Also, the scheme allows efficient multi-user encryption. It's not clear how decryptability is proved.

DL-based verifiable encryption proposed in this post is ElGamal encryption.

## Overview ##

The two main platforms for threshold signatures are Schnorr and BLS schemes. A threshold signature scheme consists of KeyGen and Sign *distributed* protocols and Verify algorithm.

KeyGen protocol is usually based on Shamir secret sharing as it provides nice algebraic properties that allow construction of a threshold signature security proof. In such protocols each party acts as a dealer in verifiable secret sharing protocol. One important aspect is the delivery of a secret share to the corresponding party. It can be done via a secure authenticated p2p channel (O(n^2) channels is required in total) followed by verification and complaint resolution rounds, or it can be done with publicly verifiable public key encryption that produces a proof that the ciphertext is indeed a secret share. The former protocols are interactive and the latter non-interactive.

Nonce (one-time private key) for Schnorr-based schemes can be generated either with a protocol similar to KeyGen or deterministically. Deterministic nonce generation procedure is complex and requires an even more complex proof that is has been generated correctly (otherwise, using the same nonce for different messages will leak secret key). BLS signatures have no such nonce and thus are much simpler.

Application where threshold signature is going to be used has a significant impact on adversary model and hence on properties and requirements to the threshold signature system. Such properties include robustness, networking synchrony model, capabilities of an adversary to carry out certain attacks. IOTA Smart Contract consensus protocol makes certain assumptions that will be utilized in our threshold signature system.

## IOTA Smart Contracts consensus ##

The threshold signature system is developed specifically for consensus protocol in IOTA Smart Contracts.

The consensus protocol is a BFT SMR protocol that is run by committee members in order to agree on the next global smart contracts state. Committee members have public signature keys that can be used for authentication. Prior to running the consensus protocol committee members run key generation protocol in order to establish committee public threshold signature key.

After the consensus part of the protocol has completed, the result (ie. hash of the next global state) must be published into the IOTA UTXO ledger as a signed message. The message (including the signature) is assembled and published by a randomly selected party (leader). The message is signed by $t$ out of $n$ committee members.

The consensus protocol assumes partially synchronous networking model with $[2n/3]$ honest members with broadcast channel. It's only natural to use $t=[2n/3]$ number as threshold value and utilize broadcast channel wherever needed in $KeyGen$ and $Sign$ protocols.

## Threshold signature scheme ##

Parameters:

- $n$ -- committee size,
- $P_i$, $i=1,n$ -- $i$-th committee member, ie. signing party,
- $t$ -- threshold size, ie. the minimum number of parties required to produce a valid signature,
- $f$ -- faulty number, ie. the number of parties an adversary is allowed to corrupt,
- $m$ -- message to be signed.

$Setup$ procedure is run prior to the consensus protocol, during $Setup$ parties generate identity (signature and encryption) key pairs $(d_i,D_i)$ and securely exchange public keys, and agree on the committee composition. Details of $Setup$ procedure are outside of scope.

$KeyGen$ protocol is run by each party $P_i$, takes as input $D_j$ for $j=1,n$ -- public keys of the committee members, and produces $s_i$ -- $P_i$-th secret key share and $Q$ -- committee signing public key.

$Sign$ protocol is run by each party $P_i$, takes $s_i$ -- secret key share and $h(m)$ -- hash of the message to be signed, and produces $(u,V)$ -- signature.

$Verify$ algorithm is the base signature scheme verification algorithm that takes $Q$ -- committee public key, $h(m)$ -- hash to be signed and $(u,V)$ -- signature, and returns $true$ or $false$.

## Adversary model ##

We consider two kinds of adversaries.

The objective of the first kind adversary is to disrupt successful execution of a protocol ($KeyGen$ or $Sign$) and effectively block (DoS) the execution of the consensus protocol. The property of a protocol to resist such adversary is called **robustness*. Such adversary can delay (in partially synchronous) or block (ie. delay indefinitely, in asynchronous model) (or corrupt?) messages of up to $f$ parties. Assuming honest 2/3 property of consensus protocol we thus also allow $f=[n/3]$ in such attack.

The objective of the second kind adversary is to forge consensus result. Here we assume that the consensus part of the protocol produces consensus result successfully, so the adversary is allowed to corrupt up to $t-1$ parties during $KeyGen$ or $Sign$ protocols in order to forge signature of the fake consensus result. As consensus protocol is successfully complete if $t=[2n/3]$ parties agree on the same result here we use this value as threshold. Other cryptosystems such (as authenticated encryption, or secure authenticated p2p channel, or homomorphic encryption, or zero-knowledge proof system, or public key encryption) may be a part of a protocol. We allow adversary to perform attacks on these cryptosystems (for example, find out secret keys, modify messages, etc) but the main objective stays the same -- to forge consensus result.

## Requirements ##

- $KeyGen$ and $Sign$ are distributed protcols *without* trusted dealer/leader;
- a reliable *broadcast* channel is available;
- $Verify$ algorithm is the same as for the base signature scheme;
- *robustness* in case of $f=[n/3]$ malicious/corrupted parties, ie. successful execution of $KeyGen$ and $Sign$ protocols in case of at least $t=[2n/3]$ honest (or corrupted but who follow protocol correctly) parties;
- *liveness*
- *existential unforgeability* in case of $t-1$ malicious/corrupted parties;
- *partially synchronous* networking model;
- system must be secure against rogue-key attack, ROS attack, Drijver's attack via Wagner's algorithm.

Notes:

- Although efficient non-robust threshold signature protocols exist we require robustness as consensus protocol is a critical component of IOTA Smart Contract system.
- Existential forgery might product a non-sense message (consensus result), nontheless it's required to perform additional verification steps in order to detect that the message is malformed. So it's more practical to prevent existential forgeries.
- Although asynchronous networking model is appealing the core consensus protocol assumes partially synchronous model, so there's no sense to target asynchronous model.

## Papers overview ##

### BFT ###

### Secret sharing ###

Secret sharing is the basic component for many MPC including threshold signature. [Shamir. How to Share a Secret] presents a secret sharing scheme based on polynomial interpolation. [Feldman. A Practical Scheme for Non-interactive Verifiable Secret Sharing] imporves on that by making the scheme verifiable (ie. parties can verify their shares secret recovery in the exponent against Feldman commitment). [Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing] improves on Feldman's VSS by using Pedersen commitment.

Secret sharing schemes consider only statistical/perfect security and do not consider network adversaries. The next step is build a secret sharing *protocol*. In synchronous (or partially synchronous) networking model the usual approach is for dealer to securely send shares to each party and to include extra rounds to handle complaints in case dealer sent an invalid share. For example, [Gennaro, Rabin, Rabin. Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography] persent a verifiable secret sharing (VSS) protocol in synchronous model with private channels and broadcasts. Another direction is to build asynchronous VSS (AVSS) protocol. Protocols presented in [Patra, Choudhury, Rangan. Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation], [Kokoris-Kogias, Malkhi, Spiegelman. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures] and [Yurek, Luo, Fairoze, Kate, Miller. hbACSS: How to Robustly Share Many Secrets] are robust in asynchronous network but considerably much more complicated.

Another approach to VSS is to avoid p2p interaction between dealer and parties and use publicly verifiable public key encryption instead. Such a non-interactive VSS protocol would only rely on broadcast channel which is assumed in our setting. Verification is usually implemented with some sort of non-interactive zero-knowledge proof (which make the whole VSS protocol non-interactive).

Publicly verifiable SS allows to construct non-interactive protocols as shares can be verified in encrypted form. In literature practical systems include Paillier-based, pairing-based, lattice-based and DL-based. In DL the only viable approach, it seems, is to encrypt scalar "in the exponent". [Gentry, Halevi, Lyubashevsky. Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties] gives a good overview of different approaches and presents a new lattice-based PVSS scheme.

### NIZKP ###

There are a number of platforms for NIZKP. The one is Schnorr-based proofs for one-way homomorphic maps (aka. preimage proofs) poposed in [Maurer. Unifying Zero-Knowledge Proofs of Knowledge]. The proofs system is similar to Schnorr signature scheme with scalar multiplication replaced by one-way group homomorphism.

Another DL-based platform is Bulletproofs presented in [Bünz, Bootle, Boneh, Poelstra, Wuille, Maxwell. Bulletproofs: Short Proofs for Confidential Transactions and More] that builds upon an efficient inner-produce argument and allows to construct range-proofs and proofs for arithmetic circuits.

Yet another general-purpose proof system is [Jawurek, Kerschbaum, Orlandi. Zero-Knowledge Using Garbled Circuits]. It allows to prove non-algebraic statements such as validity of MAC without revealing secret key. The system uses homomorphic encryption.

### VPKE ###

NIZKP are a part of verifiable PKE.

### DKG ###

The basic DKG protocol is presented in [Pedersen. A Threshold Cryptosystem without a Trusted Party]. During it's execution each party acts as a dealer in Feldman's VSS protocol. Each party can verify received share and complain about dealer in case verification fails. [Gennaro, Jarecki, Krawczyk, Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems] includes improvement against an attacker who can enforce non-uniformity of the resulted key by using perfectly hiding commitments.

A number of DKG protocols targeting different properties have been proposed since.

- [Kate, Goldberg. Distributed Key Generation for the Internet] presents HybridVSS and asynchronous DKG.
- [Kate, Huang, Goldberg. Distributed Key Generation in the Wild] presents HybridDKG.
- [Kokoris-Kogias, Malkhi, Spiegelman. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures] present asynchronous DKG.
- [Gurkan, Jovanovic, Maller, Meiklejohn, Stern, Tomescu. Aggregatable Distributed Key Generation] presents pairing-based DKG with publicly-verifiable transcript of linear size.
- [Fouque, Stern. One Round Threshold Discrete-Log Key Generation without Private Channels] presents non-interactive one-round DKG but uses homomorphic encryption.
- [Schindler, Judmayer, Stifter, Weippl. ETHDKG: Distributed Key Generation with Ethereum Smart Contracts].
- [Groth. Non-interactive distributed key generation and key resharing] presents pairing-based non-interactive DKG.

### Multi-party signature ###

BLS is one or the most widely-used pairing-based signature schemes. [Boldyreva. Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme] presents a BLS-based threshold signature one-round protocol where signers compute and broadcast partial signatures and a public party aggregates them into final signature. The only step where DKG is required is $KeyGen$ protocol.

Schnorr-based threshold signatures are more complex as they make use of unique random secret nonce that either must be derived uniquely and provably deterministically or generated randomly.

- [Stinsons, Strobl. Provably Secure Distributed Schnorr Signatures and a (t; n) Threshold Scheme for Implicit Certicates] presents a robust threshold multi-step protocol; drawback is that the protocol is interactive.
- [Gennaro, Jarecki, Krawczyk, Rabin. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems] interactive protocol.
- [Komlo, Goldberg. FROST: Flexible Round-Optimized Schnorr Threshold Signatures] presents efficient but non-robust protocol.
- [Garillot, Kondi. Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions] presents a Schnorr-based threshold signature protocol with deterministic nonces. ZK from garbled circuits is used to prove that the nonce has been derived according to a fixed algorithm. Proofs are too complex and seem impractical for many signers.

Multi-signature:
- [Boneh, Drijvers, Neven. Compact Multi-Signatures for Smaller Blockchains] MuSig.
- [Camenisch, Damgård. Verifiable Encryption and Applications to Group Signatures and Signature Sharing] VGE (verifiable group encryption, sketchy protocol) vs Verifiable signature sharing.
- [Groth. Non-interactive distributed key generation and key resharing] oriented to BLS signatures, PVSS scheme uses forward-secure pairing-based PVPKE scheme, Shamir SS. Correct sharing proofs are preimage NIZKP and work in DL, chunking range proofs are custom weak proofs, also DL-based. Pairings are used to construct forward secure PVPKE scheme.

### Conclusion

The path to threshold Schnorr signature looks like this: DL-based proofs -> PVPKE -> PVSS -> NIDKG -> non-interactive threshold Schnorr signature protocol with randomized nonces. At each step there exist many solutions. The main task is to choose compatible ones.

Alternative approach (in order to avoid costly NIZKP) would be: PKE -> AVSS -> Async interactive DKG -> interactive threshold Schnorr with randomized nonces. Computational complexity is reduced at the cost of increased interactive networking (secure p2p channels, asynchronous reliable broadcast, additional verification rounds).

## Construction ##

### Rationale ###

In order to make a final decision on which threshold scheme to implement we need to answer the following quesitons:

- Schnorr-based vs BLS-based? Schnorr-based is preferable as it doesn't introduce a new cryptographic primitive at IOTA Ledger Layer 1 protocol.
- Deterministic vs non-deterministic nonces? Non-deterministic. DKG protocol is needed anyway and it can be reused for $KeyGen$, proofs for deterministic nonces are too complicated (in terms of implementation, proof generation / verification time, proof size).
- Interactive vs non-interactive DKG? Non-interactive DKG is obviously preferable as we trade off interactive rounds for proof generation / verification.
- Secret sharing? Shamir as it has nice additive homomorphic property and works in DL.
- Feldman vs Pedersen vs ElGamal commitments? Commit to secret polynomial with Feldman/Pedersen commitment, commit to shares with ElGamal commitment.
- PVPKE of secret share? ElGamal-based -- split share into small chunks, encrypt each chunk with ElGamal, add proof of chunking, proof of secret share and decryptability, decrypt small chunks individually by brute-force.
- Proof system? DL-based. Preimage proofs for secret share with polynomial-style aggregation, bulletproofs logarithmic range proofs for decryptability.

### In Layman's terms ###

#### DKG ####

Round 1:

1. Generate secret polynomial and commit to it
2. Share secret into shares for all receivers
3. Encrypt each share for corresponding receiver
4. Add proofs that the correct share was encrypted and that it can be decrypted by the receiver
5. Sign commitment, encrypted shares and proofs
6. Broadcast data to all receivers

Round 2:

1. Receive data from all senders
2. Verify signature, skip if invalid
3. Verify proofs, skip if invalid
4. Decrypt shares (decryption can't fail, there's a valid proof)
5. //Verify shares against commitments (verification can't fail, there's a valid proof)
6. Store shares
7. Virtual common secret is the sum of valid secrets

#### Threshold signature ####

Round 1:

1. Run Round 1 of DKG to share nonce

Round 2:

1. Run Round 2 of DKG to recover nonce shares
2. Reconstruct public nonce
3. Generate partial signature
4. Broadcast partial signature to signature aggregator

Round 3 (by signature aggregator):

1. Receive partial signatures from all signers
2. Verify partial signature
3. Aggregate final signature

### Notation ###

#### Fixed parameters ####

| Symbol | Description |
|:---------------|:-----------------------------|
| $q$ | big prime |
| $\mathbb{Z}_q$ | scalars, integers modulo $q$ |
| $\mathbb{G}$ | group of order $q$ |
| $G$ | fixed group generator |
| $B$ | scalar chunk base |
| $m$ | chunks per scalar, $q<B^m$ |

#### Long-term parameters ####

| Symbol | Description |
|:---------------|:---------------------------------------------------------|
| $n$ | number of parties |
| $t$ | threshold, parties required to produce a valid signature |
| $i=1,n$ | party index/identifier |
| $P_i$ | party |
| $x^i$ | party (signature/encryption) secret/private key |
| $X_j$, $j=1,n$ | (signature/encryption) public keys of other parties |

#### Session values ####

| Symbol | Description |
|:-----------------------------------------|:--------------------------------------------------------------------------------------|
| $j=1,n$ | visavi's index |
| $k=0,t-1$ | $f^i$ polynomial coefficient index |
| $f^i(x)=sum_{k=0}^{t-1} x^k f^i_k$ | $i$-th secret polynomial |
| $s^i = f^i(0) = f^i_0$ | $i$-th secret |
| $deg(f^i) = t-1$ | degree of a secret polynomial $f^i$ |
| $S^i = s^i G = f^i_0 G$ | $i$-th public key |
| $l^J_j(x)$ | $j$-th Lagrange interpolation polynomial for set $J$ |
| $f^i(x) = sum_{j \in J} f^i(j) l^J_j(x)$ | interpolation of $f^i$ for set $J$ |
| $s^i_j = f^i(j)$ | $j$-th secret share of $i$-th secret |
| $f^i_k G$ for $k=0..t-1$ | commitment to polynomial $f^i$, public verification values of secret shares |
| $f^i(j) G ?= sum_{k=0}^t j^k (f^i_k G)$ | verification condition of secret shares of $i$-th secret by $j$-th user |
| $s = sum_{i \in S} s^i$ | common secret for user group $S$ ($S$ subset of $1..n$), not evaluated explicitly |
| $f(x) = sum_{i \in S} f^i(x)$ | secret polynomial, not evaluated explicitly in this form, can be interpolated |
| $s^j = f(j) = sum_{i \in S} f^i(j)$ | $j$-th secret share of common secret $s$ |
| $f(x) = sum_{j \in J} s^j l^J_j(x)$ | interpolation of secret polynomial for allowed group $J$, can be evaluated explicitly |
| $s = f(0) = sum_{j \in J} s^j l^J_j(0)$ | recovery of common secret s for allowed group $J$ |

### Commitments ###

#### Definition ####

#### Feldman ####

Parameters:

- $G \in \mathbb{G}$ -- fixed public base point

Input:

- $x \in \mathbb{Z}_q$ -- secret scalar

Commit:

- $C = x G \in \mathbb{G}$

Properties:

- perfectly binding
- computationally hiding

#### Pedersen ####

Parameters:

- $G \in \mathbb{G}$ -- fixed public base point
- $H \in \mathbb{G}$ -- fixed public base point with unknown DL base $G$

Input:

- $x \in \mathbb{Z}_q$ -- secret scalar
- $r \in \mathbb{Z}_q$ -- blinding

Commit:

- $C = x G + r H \in \mathbb{G}$

Properties:

- perfectly hiding
- computationally binding

#### ElGamal ####

### NIZKP ###

#### Definition ####

API:

- Prover -- constructs prover
- Verifier -- constructs verifier
- Setup -- known/fixed parameters
- Instance -- public data
- Statement -- statement about public data to be proved
- Witness -- secret piece of data that makes statement obvious, not available to Verifier
- Proof -- proof of statement that reveals no knowledge about Witness
- Prove -- algorithm taking Instance and Witness as input and producing Proof
- Verify -- algorithm taking Instance and Proof as input and producing $\top$ or $\bot$

Properties:

- completeness
- soundness
- zero-knowledge (perfect vs computational)

#### Preimage proof ####

Setup:

- $X$, $Y$ -- groups, $\mathbb{Z}_q$-modules
- $g: X \to Y$ -- one-way homomorphism
- $h: (Y,Y) \to \mathbb{Z}_q$ -- one-way hash function, the output can be truncated to $\{0..2^{log_2q/2}-1\}$

Instance:

- $y \in Y$ -- public known image

Statement:

- prover knows $x$: $y = g(x)$

Witness:

- $x \in X$ -- secret preimage

Proof:

- $(s,R) \in (X,Y)$, or
- $(s,c) \in (X,\mathbb{Z}_q)$

Prove:

| Computation | Description |
|:-----------------------------------------|:----------------------------|
| 1. $r \gets^\$ X$ | randomization |
| 2. $R = g(r)$ | commitment to randomization |
| 3. $c = h(R,y)$ | challenge |
| 4. $s = r + c x$ | response |
| 5. return $\pi = (s,R)$ or $\pi = (s,c)$ | proof |

Verify:

| Computation | Description |
|:----------------------------------|:------------|
| 1. $(s,R) = \pi$ | parse proof |
| 2. verify $g(s) ?= R + h(R, y) y$ | |

or

| Computation | Description |
|:----------------------------------|:------------|
| 1. $(s,c) = \pi$ | parse proof |
| 2. verify $c ?= h(g(s) - c y, y)$ | |

NOTE: Proof usually consists of $(s,R) \in (X,Y)$, but it can equivalently be represented as $(s,c) \in (X,\mathbb{Z}_q)$. Also, the second component $c$ can be reduced / truncated in half as hash-function $h$ doesn't have to be collision resistant. If the image space is large enough then the second representation is shorter. If the domain and image spaces are vector spaces then the vector proof can be aggregated via polynomials.

#### Polynomial proof ####

Setup:

- $Y$ -- group, $\mathbb{Z}_q$-module
- $g: \mathbb{Z}_q \to Y$ -- one-way homomorphism
- $h: (Y,Y) \to \mathbb{Z}_q$ -- one-way hash function, the output can be truncated to $\{0..2^{log_2q/2}-1\}$

Instance:

- $n$ -- number of polynomial coefficients, $n-1$ is degree
- $F_j \in Y$ for $j=0..{n-1}$ -- commitments to polynomial coefficients

Statement:

- prover knows $f \in \mathbb{Z}_q[x]$, $f(x) = \sum_{j=0}^{n-1} x^j f_j$: $F_j = g(f_j)$

Witness:

- $f_j \in \mathbb{Z}_q$ for $j=0..n-1$ -- coefficients

Proof:

- $(s,R) \in (\mathbb{Z}_q,Y)$, or
- $(s,c) \in (\mathbb{Z}_q,\mathbb{Z}_q)$

Prove(via Preimage):

| Computation | Description |
|:----------------------------------------------|:------------------------------------------|
| 1. P = Preimage.Prover | construct preimage NIZKP prover |
| 2. P.Setup := ($\mathbb{Z}_q$, $Y$, $g$, $h$) | setup with $g$ as map |
| 3. $z = h([F_j])$ | Fiat-Shamir challenge |
| 4. $g'(x) = \sum_{j=0}^{n-1} x^j F_j$ | one-way polynomial map $g'(x) == g(f(x))$ |
| 5. P.Instance := $g'(z)$ | initialize instance with known image |
| 6. P.Witness := $f(z)$ | initialize witness with known preimage |
| 7. P.Prove() | run prover |
| 8. return P.Proof | return result |

Prove(explicitly):

| Computation | Description |
|:-----------------------------------------|:----------------------------|
| 1. $r \gets^\$ \mathbb{Z}_q$ | randomization |
| 2. $R = g(r)$ | commitment to randomization |
| 3. $z = h([F_j])$ | Fiat-Shamir challenge |
| 4. $c = h(R, g(f(z)))$ | challenge |
| 5. $s = r + c f(z)$ | response |
| 6. return $\pi = (s,R)$ or $\pi = (s,c)$ | proof |

Verify(via Preimage):

| Computation | Description |
|:--------------------------------------|:------------------------------------------|
| 1. V = Preimage.Verifier | construct NIZKP preimage verifier |
| 2. V.Setup := ($X$, $Y$, $g$, $h$) | setup verifier with map $g$, not $g'$ |
| 3. $z = h([F_j])$ | Fiat-Shamir challenge |
| 4. $g'(x) = \sum_{j=0}^{n-1} x^j F_j$ | one-way polynomial map $g'(x) == g(f(x))$ |
| 5. V.Instance := $g'(z)$ | instance with known image $g(f(z))$ |
| 6. V.Proof := $(s,R)$ or $(s,c)$ | tell verifier proof |
| 7. return V.Verify() | verify knowledge of $f(t)$ |

Verify(explicitly):

| Computation | Description |
|:----------------------------------|:----------------------|
| 1. $(s,R) = \pi$ | parse proof |
| 2. $z = h([F_i])$ | Fiat-Shamir challenge |
| 3. $y = \sum_{k=0}^{t-1} z^k F_k$ | image |
| 4. verify $g(s) ?= R + h(R, y) y$ | |

or

| Computation | Description |
|:----------------------------------|:----------------------|
| 1. $(s,c) = \pi$ | parse proof |
| 2. $z = h([F_i])$ | Fiat-Shamir challenge |
| 3. $y = \sum_{k=0}^{t-1} z^k F_k$ | image |
| 4. verify $c ?= h(g(s) - c y, y)$ | |

NOTE:

Polynomial preimage proof can be used to aggregate multiple preimage proofs into one.

#### Sharing proof ####

Setup:

- $\mathbb{G}$ -- group
- $G$ -- base point
- $n$ -- number of parties
- $t$ -- threshold
- $X_j$ for $j=1..n$ -- blinding bases

Instance:

- $F_k \in \mathbb{G}$ for $k=0..t-1$ -- commitments to coefficients
- $E_j \in \mathbb{G}$ for $j=1..n$ -- commitments to shares
- $R \in \mathbb{G}$ -- commitment to blinding

Statement:

- prover knows $r \in \mathbb{Z}_q$: $R = r G$
- prover knows $f(x) \in \mathbb{Z}_q[x]$, $f(x) = \sum_{k=0}^{t-1} x^k f_k$: $F_k = f_k G$ for $k=0..t-1$
- prover knows $s_j \in \mathbb{Z}_q$: $s_j = f(j) = \sum_{k=0}^{t-1} x^k f_k$ and $E_j = \sum_{k=0}^{t-1} x^k f_k G + r X_j$ for $j=1..n$

Witness:

- $r$
- $f_k$ for $k=0..t-1$

Proof:

- $(s,t,U,V,W) \in (\mathbb{Z}_q,\mathbb{Z}_q,\mathbb{G},\mathbb{G},\mathbb{G})$, or
- $(s,t,c,W) \in (\mathbb{Z}_q,\mathbb{Z}_q,\mathbb{Z}_q,\mathbb{G})$

Prove:

| Computation | Description |
|:-----------------------------------------|:----------------------------|
| 1. $u \gets^\$ \mathbb{Z}_q$ | |
| 2. $U = u G$ | |
| 3. $v \gets^\$ \mathbb{Z}_q$ | $\sum_{j=1}^n z^{j-1} v(j)$ |
| 4. $V = v G$ | |
| 5. $z = h(U, V, [F_k], R, [E_j])$ | random point |
| 6. $W = u \sum_{j=1}^n z^j X_j$ | |
| 7. $c = h(W, z)$ | Fiat-Shamir challenge |
| 8. $s = u + c r$ | |
| 9. $t = v + c \sum_{j=1}^n z^{j-1} f(j)$ | |
| 10. $(s,t,U,V,W)$ or $(s,t,c,W)$ | |

Verify:

| Computation | Description |
|:---------------------------------------------------------|:----------------------|
| 1. $(s,t,U,V,W) = \pi$ | parse Proof |
| 2. $z = h(U, V, [F_k], R, [E_j])$ | random point |
| 3. $c = h(W, z)$ | Fiat-Shamir challenge |
| 4. verify $s G ?= U + c R$ | |
| 5. $T = c \sum_k (\sum_j z^{j-1} j^k) F_k$ | |
| 6. verify $t G ?= V + T$ | |
| 7. verify $c \sum_j z^{j-1} E_j + W ?= T + s \sum_j X_j$ | |

or

| Computation | Description |
|:---------------------------------------------------------|:----------------------|
| 1. $(s,t,c,W) = \pi$ | parse Proof |
| 2. $U = s G - c R$ | |
| 3. $T = c \sum_k (\sum_j z^{j-1} j^k) F_k$ | |
| 4. $V = t G - T$ | |
| 5. $z = h(U, V, [F_k], R, [E_j])$ | random point |
| 6. verify $c = h(W, z)$ | Fiat-Shamir challenge |
| 7. verify $c \sum_j z^{j-1} E_j + W ?= T + s \sum_j X_j$ | |

NOTE: Proofs do not actually prove knowledge of $f(x)$ (or rather $f(x)$ is excluded from the statement(?)). Rather knowledge of $f(x)$ is proved indirectly in the third statement about $s_j$ that relates $F_k$ and $E_j$. Other threshold schemes (eg. FROST) include proof of knowledge of corresponding coefficients. TODO: Give a stronger argument in favor of absence of proof of knowledge of discrete logarithms of $F_k$. Is rogue key attack possible where dealer doesn't know $f_k$ but is still able to construct $E_j$ that satisfy verification relation??

#### Range proof ####

Setup:

- $\mathbb{G}$ -- group
- $G \in \mathbb{G}$ -- base point
- $m$ -- number of small scalars
- $X_j \in \mathbb{G}$ for $j=1..m$ -- blinding bases with unknown DL base $G$

Instance:

- $K_j$ for $j=1..m$ -- commitment to randomizations
- $E_j$ for $j=1..m$ -- Pedersen commitments to small scalars

NOTE: Together $(K_j,E_j)$ form an ElGamal commitment.

Statement:

- $K_j = k_j G$ for $j=1..m$
- $E_j = z_j G + r_j X_j$ and $z_j \in \{0,\ldots,B-1\}$ for $j=1..m$

Witness:

- $z_j \in \{0,\ldots,B-1\}$ for $j=1..m$ -- witnesses, small scalars (share parts)
- $r_j \in \mathbb{Z}_q$ for $j=1..m$ -- randomizations

Proof:

- $\pi$

TODO: express bulletproof range proof size in terms of $m$

NOTE: Implementations (bulletproofs) might require $m = 2^d$ for some $d$. We refer to bulletproofs paper for Prove and Verify algorithms.

### DL-bruteforce ###

Chunking and bruteforce idea is not new. It's implemented [here](https://github.com/ZenGo-X/centipede/blob/master/src/juggling/segmentation.rs#L151), although, it's not clear what statemetns about secret segments it proves. We use a slightly better approach.

#### Idea ####

16-bit chunk correspond to 2^16 number of possible points. We can put them in lookup table like HashMap. But its runtime will be variable, and it's difficult the choose a hash function to minimize hash table size and collisions. We need a different approach.

On average, any 16-bit in a given position of a point representation are not distributed uniformly so it can't be used to uniquely determine the point and its discrete logarithm. For a 16-bit chunk there can be at least 0 corresponding point and at most 8 points. Experiments show that 32-bit chunk is enough. We could construct a lookup table with 2^32 entries but that would take 8Gb of space. We can split 32-bit chunk into two parts, use each index to look up a small subset (of at most 8 elements) and then look for a unique intersection in the two subsets. Experiments show that with given parameters there's a unique solution (for a correct input).

#### Algorithm ####

take_index : Point -> (u16, u16)
take_index p = (x[4], x[8]) where
  x: [u16; 16] = compress p

precomp = (table0, table1) where
  table0 = [Set{}; 2^16]
  table1 = [Set{}; 2^16]
  for dl in 0..2^16
    point = dl * BASE
    (i0, i1) = take_index point
    table0[i0].insert(dl)
    table1[i1].insert(dl)
  return (table0, table1)

DL : Point -> Scalar
DL p = dl where
  i = take_index p
  (set0, set1) = (table0[i0], table1[i1])
  dl = intersect set0 set1

### DKG ###

#### Setup ####

$Setup$ establishes long-term parameters:

- parties agree on their number $n$, threshold $t$ and identifiers $i$
- parties generate key pairs and securely exchange and validate public keys (public keys must have prime order)

#### Protocol ####

Input:

- $n$, $t$, $i$, $x_i$, $X_j$ for $j=1,n$ -- long-term parameters
- $sid$ -- session id

Messages:

- $F^i_k \in \mathbb{G}$ for $k=0..t-1$ -- commitment to dealer's secret polynomial
- $s^i_j \in \mathbb{Z}_q$ for $j=1..n$ -- secret shares for party $j$ (including dealer)
- $S^i_j \in \mathbb{G}$ for $j=1..n$ -- commitments to secret shares

Output:

- $r_i$ -- final accumulated secret share

Round 1:

| Computation | Description |
|:-------------------------------------------------------------------|:----------------------------------------|
| Secret sharing stage | |
| 1. $f^i_k \gets^\$ \mathbb{Z}_q$ for $k=0..t-1$ | generate secret random coefficients |
| 2. $s^i = f^i_0$ | dealer's secret is constant coefficient |
| 3. $f^i(x) = \sum_{k=0}^{t-1} x^k f^i_k$ | corresponding secret polynomial |
| 4. $F^i_k = f^i_k G$ for $k=0..t-1$ | commitment to polynomial |
| 5. $s^i_j = \sum_k j^k f^i_k == f^i(j)$ for $j=1..n$ | secret share for recipient $P_j$ |
| Secret share encryption stage | |
| 6. $s^i_j = \sum_{l=0}^{m-1} B^l s^i_{j,l}$ for $j=1..n$ | represent secret share base $B$ |
| 7. $k^i_l \gets^\$ \mathbb{Z}_q$ for $l=0..m-1$ | reusable chunk randomization |
| 8. $k^i = \sum_{l=0}^{m-1} B^l k^i_l$ | secret share randomization |
| 9. $K^i_l = k^i_l G$ for $l=0..m-1$ | commitment to chunk randomization |
| 10. $E^i_{j,l} = s^i_{j,l} G + k^i_l X_j$ for $j=1..n$, $l=0..m-1$ | encrypted secret share part |
| 11. $E^i_j = \sum_{l=0}^{m-1} B^l E^i_{j,l} == s^i_j G + k^i X_j$ | |
| Correct chunking proving stage | TODO: transcript |
| 12. $U = prove-multi-range(m, (s^i_{j,l}, k^i_l, E^i_{j,l}))$ | bulletproofs via inner-product argument |
| Correct secret sharing proving stage | |
| 13. $V = prove-shares(s^i_j,k^i)$ | |
| Signing stage | |
| 14. $D = ([F^i_k],[K^i_l],[E^i_{j,l}],U,V)$ | serialize tbs data |
| 15. $W = sign(x^i;D,sid,[X_j])$ | sign tbs data |
| Communication | |
| 16. broadcast $D,W$ | |

Round 2:

| Computation | Description |
|:----------------------------------------------------------------|:---------------------------------------|
| Communication | |
| 1. receive $D^j,W^j$ for $j=1..n$ | |
| Signature verification stage | |
| 2. $verify(X^j;D^j,W^j) == \top$ | verify authenticity |
| 3. $(F^j_k,K^j_l,E^j_{i',l},U,V) = D$ | deserialize tbs data |
| Correct secret sharing verification stage | |
| 4. $verify-shares(F^j_k;V) == \top$ | verify correct sharing proof |
| Correct chunking verification stage | |
| 5. $verify-multi-range(m, (K^i_l, E^i_{j,l}), U) == \top$ | verify correct chunking proof |
| Secret share decryption stage | can be complete by $P^i$ only |
| 6. $D^j_{i,l} = E^j_{i,l} - x^i K^j_l$ for $j=1..n$, $l=0..m-1$ | decrypt secret share part |
| 7. $D^j_{i,l} == s^j_{i,l} G$ for $j=1..n$, $l=0..m-1$ | bruteforce $s^j_{i,l} \in \{0..B-1\}$ |
| 8. $s^j_i = \sum_{l=0}^{m-1} B^l s^j_{i,l}$ for $j=1..n$ | reconstruct secret share base $B$ |
| 9. $s^j_i = \sum_k i^k f^j_k == f^i(j)$ for $j=1..n$ | compute secret share |
| Decrypted shares verification stage | this stage must always complete |
| 10. $s^j_i G ?= \sum_{k=0}^{t-1} i^k F^j_k$ | reconstruct secret share in exponent |
| Reconstruction stage | |
| 11. $r_i = \sum_{j=1}^n s^j_i$ | add up only valid shares, $r_i = f(i)$ |
| 12. $R_i = r_i G$ | corresponding public key |
| 13. $R_l = \sum_j \sum_k l^k F^j_k$ for $l=1..n$, $l \neq i$ | other parties' public keys |
| 14. $R = r G = f(0) G = F_0 = \sum_{j=1}^n F^j_0$ | common shared public key |
| 15. return $(r_i,[R_j],R)$ | |

NOTE:

Common accumulated shared secret polynomial $f(x)$ equals:

$$f(x) = \sum_{j=1}^n f^j(x) = \sum_{k=0}^{t-1} x^k f_k$$

where $f_k = \sum_{j=1}^n f^j_k$. $f(x)$ can be reconstructed by any honest $t$ parties as follows:

$$f(x) = \sum_{j \in J} l^J_j(x) r_j$$

where $J$ -- different indices of parties, $|J| \geq t$, $l^J_j(x)$ -- Lagrange interpolation polynomial:

$$l^J_j(x) = \prod_{i \in J, i \neq j} \frac{x - i}{j - i}$$

Common secret $r = f(0)$ can be reconstructed as follows:

$$r = \sum_{j \in J} l^J_j(0) r_j$$

and corresponding public key:

$$R = r G = f(0) G = F_0 = \sum_{j=1}^n F^j_0$$

#### Reshare ####

TODO: Combine DKG and Schnorr so that the current committee can distribute and sign a new secret to be used by a new committee.

### Schnorr ###

Schnorr threshold system uses DKG protocol as key generation and nonce generation protocols.

#### Setup ####

Same as for DKG protocol.

#### KeyGen ####

Parties run DKG protocol, the resulting secret share $r_i$ is the share $d_i$ of signature private key. Resulting public key $R$ is signature public key $Q$. Signers store share together with the committee members public keys and identifiers.

#### Sign ####

Input:

- $d_i$ -- $i$-th signer's signature secret key share
- $Q_j$ for $j=1..n$ -- partial signing keys
- $Q$ -- common public key
- $m$ -- message tbs
- $sid$ -- signing session identifier

Output:

- $(s,c)$ or $(s,K)$ -- signature

Round 1:

1. run Round 1 of DKG protocol

Round 2:

| Computation | Description |
|:---------------------------------|:--------------------------------|
| 1. run Round 2 of DKG protocol | |
| 2. let $(k_i,[K_j],K)$ be result | partial nonce and public values |
| 5. $c = h(K,Q,m)$ | Fiat-Shamir challenge |
| 6. $s_i = k_i + c d_i$ | partial signature |
| 7. broadcast $s_i$ | |

Round 3:

| Computation | Description |
|:-------------------------------------|:----------------------------|
| 1. collect $s_j$ | |
| 2. verify $s_j G ?= K_j + c Q_i$ | verify partial signature |
| 3. $J$ | indices of valid signatures |
| 4. $s = \sum_{j \in J} l^J_j(0) s_j$ | recover signature scalar |
| 5. return $(s,c)$ or $(s,K)$ | |

#### Verify ####

Verify algorithm is the same as for single-signer Schnorr signature.

## Implementation ##

### Profiling ###

Choice of implementation tools:

- language -- rust -- safe and efficient; crypto.rs is rust crate;
- crypto library -- dalek-cryptography's or zkcrypto's libs including subtle, curve25519-dalek, ed25519-dalek, x25519-dalek(?), bulletproofs;
- range-proof library -- bulletproofs or a fork (see considerations section below);
- construction curve $\mathbb{G}$ -- ristretto255; proofs require prime-order curve, curve25519 has cofactor h=8, all public keys, commitments must use ristretto255 group and corresponding serialization routines;
- signing curve -- ed25519; in DKG secret and public keys and signature (ie. scalars and points) do not collide/interfere with the rest of the construction, it's safe to use curve25519 in DKG; in threshold signature (and in ed25519 in particular) honest private and public key are of prime order, in dalek implementation ristretto255 point can be safely cast to ed25519 point;
- encryption curve -- ristretto255; encryption values (ciphertext, commitments) are used in proofs, need the same curve here as for the main construction, so Montgomery form of curve25519 used in x25519 is not suitable;
- encryption keys -- same as signing keys with additional validation (see considerations section below);

Choice of implementation details:

- party identifier $i$ -- u32 (u32 is used in bulletproofs implementation);
- session id $sid$ -- u64 (large enough for practical concerns);
- hash function $h$ -- SHA512, as in ed25519;
- transcript -- merlin in bulletproofs, SHA512 in preimage proofs;
- domain strings -- fixed internally vs external supplied by user / app;
- proof representation $(s,R)$ vs $(s,c)$ -- $(s,R)$; although $(s,c)$ is shorter, $(s,R)$ form supports batch verification;

### Considerations ###

#### Choice of library ####

There's bulletproofs and some other nizkp by [ZenGo-X](https://github.com/ZenGo-X/curv). It supports BLS12-381, Ed25519, secp256k1, ristretto curves. Dalek's implementation is already in use and has cleaner API, although it doesn't support BLS curves. [Zkcrypto](https://github.com/zkcrypto) supports dalek API and extends it with finite field, group and pairing abstractions, implements pairings, including JubJub, implements some NIZKP and bellman zk-SNARK library.

#### Ristretto255 and encryption public keys ####

Honest ed25519 public key has prime order, ristretto255 point implementation in curve25519-dalek crate internally uses curve25519 arithmetic (ristretto255-specific stuff is done in encoding functions), so it's safe to cast a honest ed25519 public key to encryption key and reuse the same scalar as ed25519 and encryption private key; however it must be checked that encryption public keys of other parties who may be malicious are indeed in ristretto255 group, this can be achieved by cheking the order of ed25519 public key point to be equal the prime order of ristretto255 curve. TODO: Is there a more efficient approach?

#### Transcript ####

Bulletproofs implementation uses merlin transcripts to derive Fiat-Shamir challenges. Shall merlin transcripts also be used in correct secret sharing proofs? Or shall we use SHA-512 as in the rest of Ed25519?

#### ElGamal encryption in the exponent ####

256-bit scalar is split into 16 16-bit chunks. Each chunk is encrypted as 256-bit compressed point. Bruteforce DL-algorithm uses precomputations of `8*2*2^16*2` bytes = 2 Mb size, it works in O(1) time and non-regular, ie. can leak encrypted scalar bits in side channel attack. We can increase chunks size (and decrese the number of chunks). Decryption of 32-bits chunks would take considerably longer and would require larger precomputations.

#### Preimage proof representation ####

Schnorr-like preimage proofs can either be represented as $(s,R) \in (X,Y)$ or as $(s,c) \in (X,\mathbb{Z}_q)$. Both proofs have the same cost to produce and verify, but the second one is usually shorter. This is one direction for improvements.

#### Proof aggregation and batch verification ####

##### Preimage proof aggregation #####

Preimage NIZKP are used to prove correctness of secret sharing, ie. that the encrypted share parts correspond to the polynomial committed by sender. There's a standard technique of preimage proof aggregation via polynomials that can also be applied here. It will reduce the message size by a linear factor (ie. it'll be O(1) per user instead of O(n) in trivial case).

##### Preimage proof batch verification #####

Verification condition usually boils down to checking for equality in a multi-scalar multiplication expression. Equality checks from different proofs can be combined into one expression via a known randomization technique.

##### Range proof aggregation #####

Currently bulletproofs implementation has limitation: although it can produce a single short proof for multiple values it uses the same base points for deriving Pedersen commitments (see [here](https://github.com/zkcrypto/bulletproofs/blob/4.0.0/src/range_proof/party.rs#L51) and [here](https://github.com/zkcrypto/bulletproofs/blob/4.0.0/src/range_proof/mod.rs#L255)). But in ElGamal encryption the second base point is different for different receivers (actually, it equals to receiver's public key). Essentially that means it's not possible to aggregate range proofs for different receivers. Internally, range-proofs use inner-produce argument with any base point, so in theory it should be possible to aggregate range-proofs with different bases in Pedersen commitments. This will reduce the total size of chunking proofs. It's unclear right now how to do that. TODO: Or maybe there's already such fork in github?

##### Range proof batch verification #####

During DKG at the first round each party produces $n-1$ messages with commitments, ciphertexts and proofs. During the second round each party has to verify $n-1$ messages by $n-1$ parties, hence quadratic complexity. (Multi-)scalar multiplication is the most basic and costly operation in proof verification. We can try to aggregate $n-1$ proofs during verification process into one batch and reduce $n-1$ (multi-)scalar multiplication operations into just one multi-scalar multiplication. This approach is discussed in the bulletproofs paper but not implemented by bulletproofs crate.

## Security ##

TODO: briefly argue security

### Preimage NIZKP ###

- soundness
- correctness
- computational zero-knowledge
- witness extractable

### Bulletproofs range proof ###

### DKG ###

- robustness

### Schnorr and Ed25519 signature scheme ###

- UF
- robustness
- attacks