# Aggregated Ed25519

## Signature flavours

There are signature schemes that provide additional properties to the usual signature property of message authentication and non-repudiation.

Group and ring signatures allow users to sign messages in the name of a group without revealing the identity of the signer. In this case there is usually a group administrator with special privileges that can reveal signer's identity.

For the purpose of DLT it makes sense to consider signatures with multiple signes with equal privileges. Threshold k-of-n signature can only be created by at least k signers of a group of n users. Multisignature can be considered as threshold n-of-n signature where all n group members must sign a message. The focus of this note will be multisignatures.

## Platform

There are a few well-established signature platforms: RSA (factorization), Schnorr (DL/ECDL), El-Gamal (DL/ECDL), bilinear-pairings (gap-ECDH).

Chrysalis2 uses Ed25519 (Schnorr signature over elliptic Curve25519) and BLS. One advantage of ECDL based scheme over gap-ECDH is that the former is much faster than the latter.

Here we consider Ed25519 as the basic platform for the multisignature scheme.

Some important parameters include:
- aggregated public key size;
- aggregated signature size;
- number of rounds;
- size of round messages;
- time complexity or each round.

# Aggregated Ed25519 signature scheme

## Overview

The scheme is based on [[1]](#References), MSDL scheme (section 5). The scheme allows to aggregate public keys and signatures so that they are of fixed size independenlty of the number of signers. The scheme doesn't allow to verify signature for a certain user (i.e. make sure that the user has indeed signed the message) knowing only his public key and aggregated public key. To do so all public keys must be known.


## Notation

- $H : 2^* \rightarrow 2^{512}$ -- hash function used to derive private keys from the seed and one-time signature key k.
- $H_{challenge} : 2^* \rightarrow 2^{512}$ -- hash function used to derive Schnorr signature challenge.
- $H_1 : 2^* \rightarrow 2^{256}$ -- hash function used for public key aggregation.
- $H_2 : 2^* \rightarrow 2^{256}$ -- hash function used for ephemeral public key commitments.
- $H_{nonce} : 2^* \rightarrow 2^{512}$ -- hash function used to derive randomness used for signing.
- $q$ -- order of Curve25519 i.e. $2^{252}+27742317777372353535851937790883648493$.
- $O$ - infinity point - neutral element in elliptic curve group.
- $G$ -- generator of Curve25519, $q*G=O$.
- $twiddle: 2^{256} \rightarrow Scalar$ -- maps random bits to a Scalar by masking out some input bits (ie. reducing input strength/entropy) such that the result is always a valid scalar.
- $reduce: 2^{512} \rightarrow Scalar$ -- maps bits to a Scalar by reducing input value modulo $q$. Since the input is more than 64 bits larger than $q$, almost uniformity of the distribution is assured. (The EdDSA paper recommends $2b$, i.e. 512-bit for Ed25519.)
- $a||b$ -- concatenation of $a$ and $b$.
- $nonce_i$ -- $i$-th user's 256-bit nonce.
- $d_i$ -- $i$-th user's private key.
- $Q_i$ -- $i$-th user's public key.
- $apk$ -- aggregated public key (point).
- $H(Q)$ -- hash of a public key is a hash of compressed y coordinate of the corresponding point.
- $\bot$ - empty/no input/output.

## MSDL Scheme

### Overview

Scheme consists of $KeyGen$ algorithm, $KeyAggregation$ algorithm, $AggregatedSign$ protocol and $Verify$ algorithm. $KeyGen$ and $Verify$ are Ed25519 algorithms, so Ed25519 keypair can be used for aggregated signature, and verification of aggregated signature is just the usual Ed25519 verification with aggregated public key. $AggregatedSign$ is an interactive protocol with 4 computational rounds and 3 communication rounds.

### Algorithm $KeyGen$
Input: $\bot$
Output: $(seed)$ -- private key, $(nonce, d)$ -- extended private key, $Q$ -- public key
Steps:

1. $seed \leftarrow^R 2^{256}$
2. $bits || nonce \leftarrow H(seed)$
3. $d \leftarrow twiddle(bits)$
4. $Q \leftarrow d * G$
5. return $(seed), (nonce, d), Q$

> [name=Wolfgang Welz] This is exactly the same derivation from RFC-8032. As such, we could either use an Ed25519 implementation for this directly or use `curve25519-dalek` to re-implement this.

### Algorithm $KeyAggregation$
Input: $i$, $Q_k, k=\overline{1,n}$
Output: $(s_i, apk)$
Steps:

1. $h_0 \gets H_1(Q_1 || \ldots || Q_n)$
2. for $k$ in $1,\ldots,n$:
2.1. $h_k \leftarrow H_1(Q_k || h_0)$
2.2. $a_k \leftarrow twiddle(h_k)$
3. $apk \leftarrow a_1 Q_1 + \ldots + a_n Q_n$
4. return $(a_i, apk)$

Notes: When given index $i$ algorithm returns corresponding scalar in addition to the aggregated public key.
> [name=Wolfgang Welz] How about using plain $H$, e.g. SHA-512, for $h_0$ and $H_1(Q_k || h_0)$ for $h_k$. Especially when implemented this is a bit nicer and also provides additional protection as the hash functions differ.

### Protocol $AggregatedSign$

#### Overview
Aggregated signature generation is an interactive protocol performed by $n$ users in parallel. In each round each user performs uniform steps and broadcasts the message to all the other users. Upon receiving the messages from all the other users a new round starts. Users must agree in advance on the group membership, ie. who's going to be aggregated in the signature. Each round is performed by each user, user's index $i$ also indexes corresponding keys and messages. At each round there's a possibility of error due to serialization or verification failures. Between rounds users maintain private states that store temporary data and keys. The initial state is empty, after the last round state must be destroyed.

#### Communication Round 0
Initialize signing operation, agree on message to be signed.

#### Computational Round 1
Input: $(nonce_i, d_i)$, $[Q_k, k=\overline{1,n}]$, $message$
Output: $commitment_i$
State: $e_i$, $R_i$, $d_i$, $a_i$, $apk$, $message$
Steps:

1. $z \leftarrow^R 2^{256}$
2. $r \leftarrow H_{nonce}(nonce_i||message||z)$
3. $e_i \leftarrow reduce(r)$
4. $R_i \leftarrow e_i * G$
5. $commitment_i \leftarrow H_2(R_i)$
6. $(a_i, apk) \leftarrow AggregateKeys(i, [Q_k, k=\overline{1,n}])$
7. save $(e_i, R_i, d_i, message, a_i, apk)$
8. return $commitment_i$

Note: This is commitment stage. A users choses ephemeral key pair and commits to using it. This round ensures that each user choses ephemeral key pair independently, not knowing other users' ephemeral public keys.

#### Communication Round 1
Send: $commitment_i$
Receive: $commitment_k, k=\overline{1,i-1},\overline{i+1,n}$

#### Computational Round 2
Input: $[commitment_k, k=\overline{1,n}]$
Output: $R_i$
State: $[commitment_k, k=\overline{1,n}]$, $e_i$, $R_i$, $d_i$, $a_i$, $apk$, $message$
Steps:

1. save $[commitment_k, k=\overline{1,n}]$
2. return $R_i$

Note: Just store commitments to verify later and reveal ephemeral public key, after commitments have been exchanged.

#### Communication Round 2
Send: $R_i$
Receive: $R_k, k=\overline{1,i-1},\overline{i+1,n}$

#### Computational Round 3
Input: $[R_k, k=\overline{1,n}]$
Output: $s_i$
State: $e_i$, $R_i$, $d_i$, $a_i$, $apk$, $message$, $R$, $s_i$
Steps:

1. for $k$ in $1,\ldots,n$:
1.1. $commitment_k' \leftarrow H_2(R_k)$
1.2. verify $commitment_k = commitment_k'$
2. $R \leftarrow R_1 + \ldots + R_n$
3. $h \leftarrow H_{challenge}(R || apk || message)$
4. $k \leftarrow reduce(h)$
5. $s_i \leftarrow e_i + a_i * d_i * k$
6. save $R, s_i$
7. return $s_i$

Note: At this round ephemeral public key commitments are verified and partial signatures are calculated.

#### Communication Round 3
Send: $s_i$
Receive: $s_k, k=\overline{1,i-1},\overline{i+1,n}$

#### Computational Round 4
Input: $[s_k, k=\overline{1,n}]$
Output: $(R, s)$
State: $R$, $s_i$
Steps:

1. $s \leftarrow s_1 + \ldots + s_n$
2. return $(R, s)$

Note: At this round a complete signature is reconstructed.
Note: The following identity holds:

$s = \Sigma_i s_i = \Sigma_i e_i + k * \Sigma_i a_i d_i$
$s * G = \Sigma_i (e_i G) + k * \Sigma_i (a_i d_i G)$
$s * G = \Sigma_i R_i + k * \Sigma_i (a_i Q_i) = R + k * apk$
$k = H_{challenge}(R || apk || message)$

### Algorithm Verify
Input: $apk$ -- aggregated public key, $(R, s)$ -- aggregated signature, $message$
Output: $0$ or $1$
Steps:

1. $h \leftarrow H_{challenge}(R || apk || message)$
2. $k \leftarrow reduce(h)$
3. $R' \leftarrow s * G - k * apk$
4. return $8 * R = 8 * R'$

Notes: Just verify Ed25519 signature.
> [name=Wolfgang Welz] As aggregated signatures are effectively batched signatures, it might be important to always use the batched equation that uses the co-factor. Even though this is not 100% clear in the RFC-8032, IOTA follows the ZIP-215 standard that enforces this.
> Since the verification is identical to regular Ed25519 signatures, this will not be implemented as part of the Aggregated signing.

## Security

The scheme MSDL an unforgeable signature scheme in random-oracle model if discrete logarithm problem is hard.

## Implementation

A proof-of-concept implementation in rust can be found [here](https://github.com/semenov-vladyslav/crypto.rs).

## TODOs
### Crate deps
- sync `digest` crate version
- reuse ed25519_dalek or ed25519_zebra?
### Zeroize
- list secret values
- clean local secret random/hash bytes used to derive secret scalar
- use zeroize/secrecy crate
### Deterministic one-time key vs random
### Hash functions
- list of hash functions:
* Message: * -> 64
* SecretKey: 32(seed) -> 64(nonce+scalar)
* Aggregated public key: 32*(1+n)(pk_i | pk_1 | .. | pk_n) -> 32(apk)
* otk: R,apk,M -> 32(scalar)
- domain separation
- blinding factors randomize hash values
- padding where (var-length) message is concatenated with other strings
### Conversion to/from bytes
- random bytes into a scalar: bit twiddling vs mod
- public key into bytes: compressed Y vs some raw representation
- compare public key point to bytes by converting to bytes vs by converting to point
### Curve arithmetic
- variable-time multiplication

# References
1. ["Compact Multi-Signatures for Smaller Blockchains" paper by Boneh, et.al.](https://eprint.iacr.org/2018/483.pdf)