bip-340: Reduce size of batch verification randomizers to 128 bits

[jonasnick]

For public keys pk_1, ..., pk_u, messages m_1, ..., m_u, signatures sig_1, ..., sig_u, the probability that BatchVerify(pk_1, ..., pk_u, m_1, ..., m_u, sig_1, ..., sig_u) with 128-bit uniform randomizers succeeds and there exists i in [1, u] such that Verify(pk_i, m_i, sig_i) fails is less than 2^-128.

This speeds up batch verification in libsecp by up to about 9%. If people agree that this is a good idea, I'll open a PR upstream.

Proof sketch

For i in [1, u] let
   P_i = lift_x(int(pk_i)),
   r_i = int(sig[0:32]),
   R_i = lift_x(r_i),
   s_i = int(sig[32:64]).
If there exists an i such that lift_x for P_i or R_i fails or r_i >= p or s_i >=
n, then both Verify(pk_i, m_i, sig_i) and BatchVerify(pk_1, ..., pk_u, m_1, ...,
m_u, sig_1, ..., sig_u) fail.

Otherwise Verify(pk_i, m_i, sig_i) fails if and only if C_i := s_i*G - R_i -
e_i*P_i != 0. We let c_i to be the discrete logarithm of C_i with respect to a
fixed group generator and define the polynomial f_u(a_2, ..., a_u) = c_1 +
a_2*c_2 + .... + a_u*c_3. BatchVerify succeeds if and only if f_u evaluated on
uniform randomizers a_2, ..., a_u is 0. Assume there exists i in [1, u] such
that Verify(pk_i, m_i, sig_i) fails, then f_u is not the zero polynomial. We can
make the following inductive argument (similar to the Schwartz-Zippel lemma with
d = 1, a_1 = 1):

u = 1: Pr(f_1() = c1 = 0) = 0
       By assumption.
u > 2: Pr(f_u(a_2, ..., a_u) = 0) <= 2^-128
       We can write the polynomial as f_u(a_2, ..., a_u) = a_u*c_u +
       f_{u-1}(a_2, ..., a_{u-1}). If c_u != 0 then there is at most a single
       value for a_u such that f_u(a_2, ..., a_u) = 0. Otherwise, c_u = 0,
       f_{u-1} is a non-zero polynomial and we can apply the induction
       hypothesis.
qed

Ping @sipa @real-or-random

[real-or-random]

That's a very neat way to spell out this argument and leaves no doubt. I polished it a little bit to help my understanding:

For i in [1, u] let
   P_i = lift_x(int(pk_i)),
   r_i = int(sig[0:32]),
   R_i = lift_x(r_i),
   s_i = int(sig[32:64]).
If there exists an i such that lift_x for P_i or R_i fails or r_i >= p or s_i >=
n, then both Verify(pk_i, m_i, sig_i) and BatchVerify(pk_1, ..., pk_u, m_1, ...,
m_u, sig_1, ..., sig_u) fail.

Otherwise Verify(pk_i, m_i, sig_i) fails if and only if C_i := s_i*G - R_i -
e_i*P_i != 0. We let c_i to be the discrete logarithm of C_i with respect to a
fixed group generator and define the polynomial f_u(a_2, ..., a_u) = c_1 +
a_2*c_2 + .... + a_u*c_u. BatchVerify succeeds if and only if f_u evaluated on
uniform randomizers a_2, ..., a_u is 0. Assume there exists i in [1, u] such
that Verify(pk_i, m_i, sig_i) fails. Then f_u is not the zero polynomial and we 
make the following inductive argument to prove that 
  forall u >= 1, Pr(f_u(a_2, ..., a_u) = 0) <= 2^-128.
(similar to the Schwartz-Zippel lemma with d = 1, a_1 = 1):

u = 1: By assumption, Verify(pk_1, m_1, sig_1) fails, which implies c_1 != 0.
       We have Pr(f_1() = c_1 = 0) = 0 <= 2^-128.

u > 1: We can write the polynomial as 
           f_u(a_2, ..., a_u) = a_u*c_u + f_{u-1}(a_2, ..., a_{u-1}). 
       
       Case a) If Verify(pk_u, m_u, sig_u) fails, then c_u != 0. Since f_u is not
       the zero polynomial, we have that for fixed values a_2, ..., a_{u-1}, there
       is at most a single value for a_u such that f_u(a_2, ..., a_u) = 0. 
       Since a_u is chosen independently from a_2, ..., a_{u-1} and uniformly from
       a space of 2^128 values, we have
          Pr(f_u(a_2, ..., a_u) = 0) <= 2^-128.
       
       Case b) If Verify(pk_u, m_u, sig_u) succeeds, then c_u = 0 and
       f_u = f_{u-1}. By assumption there exists an i in [1, u-1] such that
       Verify(pk_i, m_i, sig_i) fails. By the induction hypothesis we have
           Pr(f_u(a_2, ..., a_u) = 0) = Pr(f_{u-1}(a_2, ..., a_u) = 0) <= 2^-128.
qed

But is there a reason why we can't simply invoke the Schwartz–Zippel lemma? I think this would work directly:

Assume there exists i in [1, u] such that Verify(pk_i, m_i, sig_i) fails. Then f_u is
not the zero polynomial and by the Schwartz–Zippel lemma, f_u(a_2, ..., a_u) <= 2^-128.

[jonasnick]

But is there a reason why we can't simply invoke the Schwartz–Zippel lemma?

I think we can. Initially I thought that the Schwartz-Zippel Lemma as stated on wikipedia required the indeterminates to be in the same field as the coefficients but after looking at it again, I can see that that's not actually the case.

[jonasnick]

@sipa if you have no objections or concerns, I'd open a PR to the main BIP repo.

[real-or-random]

You could also open a PR against this repo and we could batch a few changes. Not sure which is better, I'm fine with both options.