BLS Signature Aggregate and Rogue-Key Attacks

BLS Signature

There are

$P_0$,

$P_1$,

$P_2$,

$P_3$ four parties.

$P_0$: secret key

$s{k}_0$, message

$m_0$, public key

$P_0=s{k}_0\cdot G$, signature

$S_0=H(m_0)\cdot s{k}_0$

$P_1$: secret key

$s{k}_1$, message

$m_1$, public key

$P_1=s{k}_1\cdot G$, signature

$S_1=H(m_1)\cdot s{k}_1$

$P_2$: secret key

$s{k}_2$, message

$m_2$, public key

$P_2=s{k}_2\cdot G$, signature

$S_2=H(m_2)\cdot s{k}_2$

$P_3$: secret key

$s{k}_3$, message

$m_3$, public key

$P_3=s{k}_3\cdot G$, signature

$S_3=H(m_3)\cdot s{k}_3$

one by one:

$e(G,S_0)=e(P_0,H(m_0))$ and so on.

$H$, hash to curve, result is a point.

$S=S_0+S_1+S_2+S_3$

$\begin{array}{rl}e(G,S)& =e(G,S_0+S_1+S_2+S_3)\\ & =e(G,S_0)\cdot e(G,S_1)\cdot e(G,S_2)\cdot e(G,S_3)\\ & =e(G,s{k}_0\cdot H(m_0))\cdot e(G,s{k}_1\cdot H(m_1))\cdot e(G,s{k}_2\cdot H(m_2))\cdot e(G,s{k}_3\cdot H(m_3))\\ & =e(s{k}_0\cdot G,H(m_0))\cdot e(s{k}_1\cdot G,H(m_1))\cdot e(s{k}_2\cdot G,H(m_2))\cdot e(s{k}_3\cdot G,H(m_3))\\ & =e(P_0,H(m_0))\cdot e(P_1,H(m_1))\cdot e(P_2,H(m_2))\cdot e(P_3,H(m_3))\end{array}$

Use aggregated signature, we can compute

$n-1$ less expensive pairings. (

$2n$ vs

$n+1$)

Rogue-Key Attacks

if

$m_0=m_1=m_2=m_3=m$, for example, in consensus, different nodes sign the same block.

There are 5 parties: 4 validators and 1 leader.

Normal Process

• The leader broadcasts block(
  $m$) to all the validators
• The validators send back signatures
  $S_0,\dots ,S_3$.
• The leader broadcasts the aggregated signature
  $S=S_0+S_1+S_2+S_3$
• The validators validate
  $e(G,S)=e(P,H(m))$ with
  $P=P_0+P_1+P_2+P_3$, as
  $e(G,S)=e(P_0,H(m))\cdot e(P_1,H(m))\cdot e(P_2,H(m))\cdot e(P_3,H(m))=e(P_0+P_1+P_2+P_3,H(m))$.

As a malicious leader

The malicious leader want to change the block, such as he want to double-spend.

• The leader new a secret key
  $s{k}^{\prime }$, with public key
  $P^{\prime }=s{k}^{\prime }\cdot G$
• The leader sign the new block(
  $m^{\prime }$):
  $S^{\prime }=s{k}^{\prime }\cdot H(m^{\prime })$
• The leader public new public key
  $P_4=P^{\prime }-(P_0+P_1+P_2+P_3)=P^{\prime }-P_{\text{origin}}$
• The leader public new signature
  $S_4=S^{\prime }-(S_0+S_1+S_2+S_3)=S^{\prime }-S_{\text{origin}}$
• Other validators aggregate:
  $S_{\text{new}}=S_0+\cdots +S_4=S^{\prime }$,
  $P_{\text{new}}=P_0+\cdots +P_4=P^{\prime }$,
  $e(G,S_{\text{new}})=e(G,S^{\prime })=e(P^{\prime },H(m^{\prime }))=e(P_{\text{new}},H(m^{\prime }))$, So validators think the new block(
  $m^{\prime })$ is legal.

Reference

• https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716
• https://medium.com/@coolcottontail/rogue-key-attack-in-bls-signature-and-harmony-security-eac1ea2370ee