# Interactive BLS multisignatures

We have threshold signature schemes that require interaction for the DKG and maybe signing a message. Can we get an accoutable succinct multisignature scheme i.e. one where we know the set of signers, but our signature and proof of correctness are constant size?

We know we can do this with a 2-chain of pairing friendly elliptic curves without interaction. We also know that we can get a log-sized proof without interaction using MIPP type protocls. But can we get a constant size proof working in BLS12-381 or a similar curve without a 2-chain?

We can do this by using ideas from threshold signature schemes. The idea is that we'll require interaction for both setup and proving the correctness of agregated signatures. However, because nothing we are sharing is actually secret, our interaction can be more robust than threshold signature protocols. Concretely, whenever an actor needs to send a message to all potential signers and requires a reply from them, then it is ok for only 1/3 of them to respond correctly, so long as 2/3 respond and no more than 1/3 are incorrect. Most interestingly, it does not have to be the same set of honest parties for every interaction: e.g. the initial broadcast step for the setup requires every signer to send a message to every other signer, but it is ok if a different 2/3 of signers recieves each message.

We achieve this by using a Lagrange basis KZG commitment to the secret keys. The committed polynomial is unkown to all parties, which makes it much harder to generate opeings of! There are $n^2$ pieces of information that are needed to produce the final proof, opening the polynomial of party i at position j. So we distribute this, each of the $n$ participants has $O(n)$ pieces. Since these satisfy a polynomial relation, we can erasure code them eassily, and in fact we have each party own $3n$ of these pieces of data. This will allow the final proof to be constructed even if only $n/3$ parties contribute. Each party, including the prover does only $O(n)$ group operations.

## A very long set of perliminaries of independent interest

### Hidden value KZG openings

We write $[p(X)]_i = p(\alpha) g_i$ for a KZG commitment in $G_i$ for $i \in \{1,2\}$ to the polynomial $p(X)$ with trapdoor $\alpha$.

A KZG opening of a commitment $C \in G_1$ at a point $x$ to a value $y$ is a point $C_q \in G_1$ with
$$e(C - y[1]_1, [1]_2) = e(C_q, [X]_2 - x [1]_2)$$

A hidden value KZG opening of $C$ at $x$ to a point $h \in G_1$ is a $C_q$ with
$$e(C - [h]_1, [1]_2) = e(C_q, [X]_2 - x[1]_2)$$

together with a proof that $h$ is a commitment to a constant polynomial. That is $h=g_1^y$ for some $y$ that the prover knows.

Unless the trapdoor is known, $h$ must be a KZG commitment to some polynomial under appropriate cryptographic assumptions.

To force $h$ to be a commitment to a constant polynomial, we'd need to give either a Schnorr signature proving that $h=g_1^y$ for a known $y$ or a zero degree test, that is, showing a $f \in G_2$ with
$$e(h,[X^k]_2)=e(f,[1]_2)$$
where $k$ is the highest integer such that $\alpha^k g_1$ is in the SRS. If $[X^k]_2$ is not in the SRS, then we also need to include a point $e \in G_2$ and show that
$$e([1]_1,e)=e(h,[1]_2)$$
and
$$e([X^k]_1, e)=e(f,[1]_2))$$
in this case we can take $k$ to be the highest integer such that $\alpha^k g_1$ and $\alpha^k g_2$ are in the SRS.

We can also do the zero degree test with Fiat Shamir, but that would match batching and interpolating harder or impossible later.

### KZG openings of the same low degree polynomial are low degree and hence erasure coded

Suppose that $p(x)$ is a polynomial of degree $d > 0$. Then KZG openings, hidden or otherwise $q_1,\dots, q_n$ at $x_1,\dots,x_n$ have $$q_i=\frac{p(\alpha)-p(x_i)}{\alpha-x_i} g_1$$

$\alpha-X$ divides $p(\alpha)-p(X)$ since $X=\alpha$ is a root of the latter and so $r(X)= \frac{p(\alpha)-p(x_i)}{\alpha-x_i}$ is a degree $d-1$ polynomial.

Thus given $d$ evaluations of $r$, we can interpolate to find any other. The coefficents used to do this can also be used to find $g_1^{r(x')}$ for any $x'$ in terms of a multiexponentiation in $g_1^{r(x_1)},\dots, g^{r(x_n)}$

Concretely, given a set $S$ of points $x_1,\dots, x_n$ for $n \geq d$, we define the vanishing polynomial $v_S(X)=\prod_{i=1}^n (X-x_i)$, the lagrange interpolating polynomials $L_{i,S}=\frac{v_S(X)}{v'_S(X)(X-x_i)}$ (where $v'_S(X)$ is the formal derivative of $v_S(X)$) and then we have
$$r(x')=\sum_i L_{i,S}(x') r(x_i)$$
and so
$$r(x') g_1 = \sum_i L_{i,S}(x') r(x_i) g_1 \; .$$

We can compute $L_{i,S}(x')$ for all $i$ in time $O(d \log^2 d)$. To do this, we compute $v_S(X)$ and $v'_S(X)$ in the monomial basis and then use a multipoint evaluation to compute $v'_S(X)$ at $x_1,\dots,x_d$. Alin Tomescu has code for this somewhere.

For any $x'$ we can compute a (hidden) opening of $p$ at $X$ given $d+1$ (hidden) openings at $x_1,\dots, d+1$. In the hidden case we also require the proof of zero degree form of the hidden opening. We let $S=\{x_1,\dots, x_{d+1}\}$, and then take

$$q'=\sum_i L_{i,S}(x') q_i$$.

In the plain opening case, we take
$$y'=\sum_i L_{i,S}(x') y_i$$
and in the hidden case
$$h'=\sum_i L_{i,S}(x') h_i$$
and
$$f'=\sum_i L_{i,S}(x') h_i$$
for the proof of zero degree.

These work because $h_i=g_1^{p(x_i)}$ and $f_i=g^{\alpha^k p(x_i)}$ respectively have polynomials of degree $d$ in the exponent.

### Alternative Lagrange KZG openings.

Let $\omega$ be a primitive $n$ root of unity for some power of two $n$. We define $$L_i(X)=\frac{\omega^i (X^n-1)}{n (X-\omega^i)}$$
Note that this is a langrange interpolation polynomial for the set $S$ of $n$th roots of unity since $v_S(X)=X^n-1$,$v'_S(X)=n{X^n-1}$ and $v'_S(\omega^i)=n \omega^{i(n-1)}=n/\omega^i$. We suppress the $S$ from the notation for $L_i$ for $n$th roots of unity

An AL KZG opening of $C$ at $\omega^i$ to $y$ is a $q$ with
$$e(C−y[L_i(X)]_1,[1]_2)=e(q,[X]_2−\omega^i[1]_2)$$
if $p(\omega^i)=y$, then $p(X)-yL_i(X)$ is zero at $y$ and so divides $X=\omega^i$ in a similar way to using 1 instead of $L_i(X)$.

Note that, for openings with value zero, a regular and AL KZG opening are identical.

To make this into a hidden value opening, we need to show that $h=y[L_i(X)]_1$ without revealing $y$. To do that, we either use a DLEQ proof of knowledge or reveal $e,f$ with

$$e([L_1(X)]_1,e)=e(h,[1]_2)$$
and
$$e([X^k]_1,e) = e(f,[1]_2))$$
where $k$ is the highest power such that $\alpha^k g_2$ is in the SRS.

For the interpolation, note that $\frac{p(\alpha)-p(\omega^i) L_i(X)}{X-\omega^i}$ is a polynomial of degree $\max \{d,n-1 \} -1$. $h_i=p(x_i)[L_1(X)]_1$ is still the exponentiation of a constant with expinent a polynomial of degree $d$. This means that at least $\max \{d, n\}$ points are required to interpolate the proofs and opening/hidden openings and their zero degree proofs.

### Another Lagrange thing

We can consider the polynomial $L(X,Y)$ of degree $n-1$ in both $X$ and $Y$ individually with $L(X,\omega^i)=L_i(X)$. By Lagrange interpolation on $Y$, this satisfies
$$L(X,Y)= \sum_{i=0}^{n-1} L_i(X) L_i(Y)$$
and so $L(X,Y)=L(Y,X)$.

**Lemma 1**: There exists a polynomial $W_i(X,Y)$ with
$$L_i(X) L(X,Y)=L_i(X)L_i(Y) + (X^n-1)W_i(X,Y)$$

**Proof**: We just need to show that $L_i(X)(L(X,Y)-L_i(Y))$ divides $X^n-1$. To show that, it suffices to show that $L_i(\omega^j)(L(\omega^j,Y)-L_i(Y))$ is identically $0$ for all $0 \leq j \leq n-1$. When $j \neq i$, $L_i(\omega^j)=0$. When $j=i$, $L(\omega^j,Y)-L_i(Y)=L_j(Y)-L_i(Y)=0$. This completes the proof of Lemma 1.

Substituting $\omega^j$ for $y$, we obtain that

$$L_i(X) L_j(X)= \delta_{ij} L_i(X) + (X^n-1)W_i(X,\omega^j)$$

### Revealing group elements to the power of $sk$ had better not hurt BLS's security.

A validator with secret key $sk$, normally reveals public key $sk g_1$ or $sk g_2$. We'd like to note that they can reveal both and indeed $sk h_1 ,\dots,sk h_n$ for arbitrary elements $h_1,
\dots,h_n$ in $G_1 \cup G_2$, as long as, when they sign a message $m$, it is computationally hard to find $sk H_1(m)$ or another solution $h'$ to $e(H_1(m), sk g_2)=e(h',g_2)$.

For arbitrary $h_i$, we can probably only do this by using $H_1(H(g_1,h_1,\dots,h_n) || m)$ in place of $H_1$. However we can probably do better for the elements we are interested in.

If $H_1$ is a random oracle, then it should suffice to find$g_1$ in a way that is unrealted to $H_1$ or else to set it to $H_1(m')$ for $m'$ outside the space of messages or if push comes to shove, do $H_1(g_1||m)$ instead of $H_1(m)$.

Revealing $sk h_i$ for $h_i \in G_2$, should not help solve $e(H_1(m), sk g_2)=e(h',g_2)$ under sensible assumptions.

For the $h_i \in G_1$, it should be the case that if $h_i =sk [p(X)]_1$ for known $p$ that revealing these does not help either. For this, we only need to assume that the KZG setup is generated by computationally bounded parties, and so they and an adversary cannot solve $H_1(m)=[q(X)]_1$ for any message $m$ and polynomial $q$.

This will probably work, but it will need a proof.

### Having the public keys in both $G_1$ and $G_2$

One advantage of having both $pk_1=skg_1$ and $pk_2=sk g_2$ public for multisignatures is the following. $G_1$ operations are much cheaper than $G_2$ operations, so we'd like to do the hashing to curve in $G_1$ and also the combining public keys part in $G_1$. This especially holds for multisigs without proofs of possession, when we'd have to do a multiexponentiation to get the public key. This is impossible, since they need to be on opposite sides of the pairing i.e. either we have

$$e(apk, H(m))=e(g_1,asig)$$
with a hash to $G_2$ or
$$e(H(m),apk)=e(asig,g_2)$$
with the $apk$ needing to be computed in $G_2$.

But with public keys in both $G_1$ and $G_2$, we can delegate to the prover constructing an aggegate public key $apk_2$ in $G_2$ and have a verifier only compute an agregate key $apk_1$ in $G_1$. The verifier computes $apk_1$ and needs to check
$$e(apk_1,g_2)=e(g_1, apk_2)$$
and
$$e(H(m),apk_2)=e(asig,g_2) \; .$$
But since the right side of these parings are the same, they can combine them, and check for a random scalar $r$ that
$$e(asig + r apk_1,g_2)=e(H(m) + r g_1, apk_2) \; .$$
This is only two $G_1$ exponetiations more expensive than BLS verification with the hash to $G_1$, which was the cheaper way round. But all the verifier's expensive operations are now in $G_1$.

## Committee key scheme

There are $m$ validators. $n$ is a power of two bigger than $m$. Each validator is known by its index $0 \leq i \leq m-1$ and knows this index and a BLS secret key $sk_i$.

### Polynomials

We consider the polynomials

$$p_i(X)=sk_i n L_i(X)$$
and
$$q_{i,j}=sk_i n W_{i,j}= \frac{p_i(X)(L_j(X)-\delta_{ij})}{X^n-1}$$
Thus we have
$$p_i(X) L_j(X) = \delta_{ij} p_i(X) + q_{i,j}(X)(X^n-1)$$
For any subset $S$ of $0,1,\dots,n-1$, we define
$$p_S(X) =\sum_{i \in S} p_i(X)$$
and
$$b_S(X)=\sum_{i \in S} L_i(X)$$
For two subsets $S \subset T$ of $0,1,\dots,n-1$, we define
$$q_{T,S}(X)= \sum_{i \in T \sum_{i in S}} q_{i,j}(X)$$

Now we have
$$p_T(X) b_S(X)=p_S(X)+(X^n-1)q_{T,S}(X)$$

Also note that $p_S(0)= n \sum_{i=0} sk_i L_i(0)=\sum_{i \in S} sk_i$

We will also use polynomials
$$r_i(X)=(p_i(X) - sk_i)/X$$
$$s_i(X)=X^{max KZG coef - (n-1)} p_i(X) $$
and define sums over subsets, e.g. $r_S(X)$, $s_S(X)$ similarly.

### Public keys

Validator $i$ publishes public keys

$pk_i=sk_i g_2$,$C_{p_i}=[p_i(X)]_2$,$C_{r_i}=[r_i(X)]_1$,$C_{s_i}=[s_i(X)]_1$ and for all $0 \leq j \leq n$, $C_{q_{i,j}}=[q_{i,j}]_1$.
(below we discuss an alternative where all the $C_{q_{i,j}}$ are not broadcast.)

They also need to publish a proof of possession for these public keys which is a Chaum Pedersen DLEQ proof showing that $pk_i$ and $C_{p_i}$ are the same known multiple of $g_2$ and $[L_i(X)]_2$ repsectively.

To verify the public keys, we check the DLEQ proof and that the following pairing checks hold

$$e([1]_1,C_{p_i}-pk_i)=e(C_{r_i}, [X]_2)$$

$$e([X^{max KZG coef - (n-1)}]_1, C_{p_i})=e(C_{s_i},[1]_2)$$

## DKG for multisigs

There are $m$ validators. $n$ is a power of two bigger than $m$. Each validator is known by its index $0 \leq i \leq m-1$ and knows this index and a BLS secret key $sk_i$.

### Setup

Firstly, each validator posts to the chain $sk_i g_1, sk_i g_2, sk_i [L_i(X)]_1$ and a Schnorr/Chaum-Pedersen style DLEQ proof that these are exponentiations of $g_1,g_2,[L_i(X)]_1$ with the same known expenent. This doubles as a proof of possession for BLS. They also post a hidden opeing of $sk_i [L_i(X)]_1$ at $0$, which is to $(sk_i/n) g_1$, since $L_i(0)=1/n$ for all $i$.

Here $L_i(X)=\frac{X^n-1}{n \omega^i(X-\omega^i)}$ are the lagrange interpolation polynomials for the $n$th roots of unity $\omega^i$.

Secondly, each validator $i$ sends to each other validator $j$, $sk [W_i(X,y)]_1$ for each of $y=\omega^j,y=\omega^j \omega_{4n}, y= \omega^j \omega_{4n}^2$ where $\omega_{4n}$ is a primitive $4n$th root of unity with $\omega_{4n}^4=\omega$ and $W_i(X,Y)$ is defined as in Lemma 1 above.

Validator $j$ then checks that the claimed commitment $C_{i,y}$ to $sk [W_i(X,y)]_1$ against the already verified commitment to $sk_i [L_i(X)]_1$ using
$$e(sk_i [L_i(X)]_1, [L(X,y)]_2)=e(L_i(y) sk_i [L_i(X)]_1, [1]_2) + e([W_i(X,y)]_1, [X^n-1]_2)$$.
Note that they can precompute $[L(X,y)]_2$ for their values of $y$ and batch this equation across $i$s.

Now each validator votes as to which validators it received correct $C_{i,y}$s from. Any validator with $>2n/3$ other validators attesting to them doing this correctly is included in a set $T$ of validators.

If any validator did not receive valid $C_{i,y}$ for their values of $y$, then they or another validator can reconstruct this from valid $C_{i,y}$ for $\geq n$ values of $y$ which they can obtain from $\geq n/3$ from other validators who recieved all correct commitments, since $sk W(X,Y)$ is a degree $n-1$ polynomial in $y$.

Now we compute a commitment the polynomial

$$p_T(X) = \sum_{i \in T} sk_i L_i(X)$$
by summing the commitments to each term.

## How to generate a proof of multisig.

The idea here is that we prove the correctness of $p_S(X)= \sum_{i \in S} sk_i L_i(X)$ for a set $S \subseteq T$ of signers against the commitment to $p_T(X)$. We also generate a hidden opening of the commitment to $p_S(X)$ at $0$ and proof that $p_S(X)$ has degree at moset $d-1$. Now, by Aurora's univerate sumcheck, we have verified that

$$n p_S(0) g_1 =n \sum_{i \in S} sk_i L_i(0) g_1 = \sum_{i \in S} sk_i g_1$$

which gives an aggregate public key.

To do this, the prover provides a commitment $C_S$ supposedly equal to $[p_S(X)]_1$ and the commitment to a quotient $C_W$ and the verifier checks that

$$e([p_T(X)]_1,[b(X)] ))= e(C_S,[1]_2)+e(C_W,[X^n-1]_2)$$
where $b(\omega^i)=1$ if $i \in S$ and $b(\omega^i)=0$ otherwise.

The prover proves the coreectness of $[b(X)]_2$ using one of the accountable or unaccountable schemes we describe in other HackMDs/ our paper.

Then the prover provides an hidden opening $q_0$ of $C_S$ at $0$ to $apk_1$ and the verifier checks that

$$e(n C_S-apk_1,[1]_2=e(n q_0,[x]_2) \; .$$

Also, the verifier needs to check that $C_S$ is a commitment to a polynomial of degree at most $d-1$

Finally the verifier can check the BLS signature with an $apk_2$ provided by the prover as

$$e(asig + r apk_1,g_2)=e(H(m) + r g_1, apk_2) \; .$$

Before detailing how the proof is constructed, we should sketch a bit the proof of why this is enough. The BLS check ensures that $apk_1$ is a KZG commitment to a constant polynomial, because the SRS doesn't contain terms like $\alpha^iH(m)$. As a result, the hidden opening check is sound.

### The interactive part

How does the prover find $C_W$? Well it is a commitment to a polynomial $p_W(X)$ with

$$p_T(X)b(X)=p_S(X)+p_W(X) (X^n-1)$$

Now we use

$$L_i(X) L_j(X)= \delta_{ij} L_j(X) + (X^n-1) W_i(X,\omega^j)$$
to obtain

\begin{align*}
p_T(X)b(X) & = \sum_{i=0}^{n-1} \sum_{j \in S} sk_i L_i(X) L_j(X) \\
& = \sum_{i=0}^{n-1} \sum_{j \in S} sk_i (\delta_{ij} L_j(X) + (X^n-1) W_i(X,\omega^j)) \\
& = \left(\sum_{j \in S} sk_i L_j(X) \right) + \sum_{i=0}^{n-1} \sum_{j \in S} sk_i W_i(X,\omega^j)) (X^n-1)\\
&= p_S(X) + (X^n-1) \sum_{i=0}^{n-1} \sum_{j \in S} sk_i W_i(X,\omega^j)
\end{align*}

Thus

$$p_W(X) = \sum_{i=0}^{n-1} \sum_{j \in S} sk_i W_i(X,\omega^j)$$