Schnorr Aggregated signature

The aggregated signature is based on the work in Compact Multi-Signatures for Smaller Blockchains section 5.1. This protocol is used to aggregate signatures of all counter parties.

Key generation

Signing is an interactive three-round protocol. singer i behaves as follows:

[Round 1] generate r and R:

Choose random $r_i$ , and compute $R_i = r_i \cdot G$
Calc $h_{R_i}= hash(R_i)$
Send $h_{R_i}$ to all other singers corresponding to $Q_1, Q_2,\cdots, Q_n$ and wait to receive $h_{R_j}$ from all other signers $j \not= i$

[Round 2] broadcast and check R:

Send $R_i$ to all other signers corresponding to $Q_1,Q_2,\cdots,Q_n$ and wait to receive $R_j$ from all other signers $j \not= i$ . Check that $h_{R_j}= hash(R_j)$ for all $j=1,2,\cdots,n$ .

[Round 3] :

Calc aggregated publick key $\overline{Q}=\sum_{i=1}^n (\overline{h_Q} \cdot Q_i)$ , when multiple messages are signed with the same set of signers, $\overline{Q}, \overline{h_Q}$ can be stored.
Calc aggregated point R: $\overline{R}=\sum_{i=1}^n R_i$
Hash msg with public params: $h=hash(\overline{R}, \overline{Q}, msg)$
Calc partial signature $s_i = r_i + h \cdot x_i \cdot \overline{h_Q}$
Send $s_i$ to all other signers and wait to receive $s_j$ from all others signers $j \not= i$ .
Calc final signature $s=\sum_{i=1}^{n} s_i$
Output the final signature as $(\overline{R}, s)$

$s \cdot G= (s_1+s_2+\cdots+s_n) \cdot G = [\sum_{i=1}^n (r_i + h \cdot x_i \cdot \overline{h_Q})]\cdot G$
$h \cdot \overline{Q} = h \cdot (\overline{h_Q} \cdot Q_1 + \overline{h_Q} \cdot Q_2 +\cdots+ \overline{h_Q} \cdot Q_n ) = h \overline{h_Q} x_1 G + h \overline{h_Q} x_2 G +\cdots+ h \overline{h_Q} x_n G$
$\therefore \quad lhs=(r_1 + r_2 +\cdots+ r_n)G$
$\because \quad \overline{R}=R_1+R_2+\cdots+R_n$
lhs=rhs

Assume we just have two party, then we can update the shares with equation
$x_1'=x_1-r \bmod{n}$
$x_2'=x_2+r \bmod{n}$