Skip to content

Latest commit

 

History

History
94 lines (78 loc) · 3.38 KB

2021-Q2-halfagg-impl.org

File metadata and controls

94 lines (78 loc) · 3.38 KB
Raw

Intro to Signature Half Aggregation

Goal: implement half aggregation in libsecp256k1-zkp (https://github.com/ElementsProject/secp256k1-zkp)

Standard signatures

  • KeyGen(sk) -> pk
  • Sign(sk, m) -> sig
  • Verify(pk, m, sig) -> {true, false}

Aggregate signatures

  • AggVerify((pk_1, m_1), …, (pk_n, m_n), sig) -> {true, false}
  • Trivial solution: sig = (sig_1, …, sig_n)
  • Goal Nr 2: sig should be short
  • Note the different messages != multisignatures, MuSig, etc.

Schnorr Signature Half Aggregation

  • Aggregate(sig_1, …, sig_n) -> sig
  • AggVerify((pk_1, m_1), …, (pk_n, m_n), sig) -> {true, false}
  1. |sig| ≈ 1/2 (|sig_1| + … + |sig_n|)
  2. aggregation is non-interactive

proposed on Bitcoin mailing list ~2017, recent academic paper (Chalkias et al.)

Applications

  • block-wide signature aggregation (but it has downsides related to adaptor sigs)
  • L2 gossip protocols

Aside: “Full” Schnorr Sig Aggregation

  1. |sig| = |sig_1|
  2. aggregation is interactive

Tx-wide aggregation can be combined with half aggregation

Schnorr signature verification (BIP 340)

Verify(pk, m, sig):
  P = lift_x(int(pk)); fail if that fails
  r = int(sig[0:32]); fail if r ≥ p
  s = int(sig[32:64]); fail if s ≥ N
  R = lift_x(int(r)); fail if that fails

  e = int(hash_{BIP0340/challenge}(bytes(r) || pk || m)) mod N
  Fail if s⋅G ≠ R + e⋅P

Schnorr Signature Half Aggregation

“Concatenate the r-values of the given signatures, and just sum up the s-values sum up the s-values after multiplying them with unpredictable values”

  • Aggregate((pk_1, m_1, sig_1), …, (pk_n, m_n, sig_n)): 
    For i = 1 .. n:
  r_i = sig_i[0:32]
  s_i = int(sig_i[32:64])
For i = 1 .. n:
  z_i = int(hash_{HalfAggregation}(r_1 || pk_1 || m_1 || ... || r_n || pk_n || m_n || i)) mod N
s = z_1⋅s_1 + ... + z_n⋅s_n
Return sig = r_1 || ... || r_n || bytes(s)
  • AggregateVerify((pk_1, m_1), …, (pk_n, m_n)), sig): 
    For i = 1 .. n:
  P_i = lift_x(int(pk_i)); fail if that fails
  r_i = sig[(i-1)⋅32:i⋅32]; fail if r ≥ p
  R_i = lift_x(int(r_i)); fail if that fails
  e_i = int(hash_{BIP0340/challenge}(bytes(r_i) || pk_i || m_i)) mod N
For i = 1 .. n:
  z_i = int(hash_{HalfAggregation}(r_1 || pk_1 || m_1 || ... || r_n || pk_n || m_n || i)) mod N
s = int(sig[n⋅32:(n+1)⋅32]) mod N
Fail if s⋅G ≠ z_1⋅(R_1 + e_1⋅P_1) + ... + z_n⋅(R_n + e_n⋅P_n)
  • Correctness?
    • Example: Given two sigs (r_1, s_1), (r_2, s_2)
      • valid Schnorr signature implies s_i⋅G = lift_x(r_i) + e_i⋅P_i
    • Aggregate sig = (r_1, r_2, z_1⋅s_1 + z_2⋅s_2)
    • And it holds that
      • (z_1⋅s_1 + z_2⋅s_2)⋅G = z_1⋅(lift_x(r_1) + e_1⋅P_1) + z_2⋅(lift_x(r_1) + e_2⋅P_2)
    • Hence, AggregateVerify succeeds

Let’s go!

  1. Implement Aggregate and AggregateVerify interface
  2. Write Test
    • Correctness: Create Schnorr signatures, Aggregate them, AggregateVerify should always succeed
  3. Implement Aggregate and AggregateVerify
  4. Bonus: Write Test
    • “Unforgeability”: Create Schnorr signatures, Aggregate them, any random bit flipped in the input of AggregateVerify will make it fail
  5. Bonus: separate module? API tests? multiexp? z_1 = 1 optimization? streaming api?