Module: BLS

Defined in:
lib/bls.rb,
lib/bls/h2c.rb,
lib/bls/math.rb,
lib/bls/curve.rb,
lib/bls/error.rb,
lib/bls/field.rb,
lib/bls/point.rb,
lib/bls/pairing.rb,
lib/bls/version.rb,
lib/bls/point/g1.rb,
lib/bls/point/g2.rb

Defined Under Namespace

Modules: Curve, FQP, Field, H2C Classes: Error, Fp, Fp12, Fp2, Fp6, Fr, PairingError, PointError, PointG1, PointG2, ProjectivePoint

Constant Summary collapse

POW_2_381 = 
2**381
POW_2_382 = 
POW_2_381 * 2
POW_2_383 = 
POW_2_382 * 2
PUBLIC_KEY_LENGTH = 
48
SHA256_DIGEST_SIZE = 
32
UT_ROOT = 
BLS::Fp6.new([BLS::Fp2::ZERO, BLS::Fp2::ONE, BLS::Fp2::ZERO])
WSQ = 
BLS::Fp12.new([UT_ROOT, BLS::Fp6::ZERO])
WSQ_INV = 
WSQ.invert
WCU = 
BLS::Fp12.new([BLS::Fp6::ZERO, UT_ROOT])
WCU_INV = 
WCU.invert
PSI2_C1 =

1 / F2(2)^((p - 1) / 3) in GF(p^2)

0x1a0111ea397fe699ec02408663d4de85aa0d857d89759ad4897d29650fb85f9b409427eb4f49fffd8bfd00000000aaac
BLS_X_LEN = 
Curve::X.bit_length
P_MINUS_9_DIV_16 = 
(Curve::P**2 - 9) / 16
XNUM = 
[
  Fp2.new([
            0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6,
            0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97d6]),
  Fp2.new([
            0x0,
            0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71a]),
  Fp2.new([
            0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71e,
            0x8ab05f8bdd54cde190937e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ffffffffe38d]),
  Fp2.new([
            0x171d6541fa38ccfaed6dea691f5fb614cb14b4e7f4e810aa22d6108f142b85757098e38d0f671c7188e2aaaaaaaa5ed1,
            0x0])
].freeze
XDEN = 
[
  Fp2.new([
            0x0,
            0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa63]),
  Fp2.new([
            0xc,
            0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa9f]),
  Fp2::ONE,
  Fp2::ZERO
].freeze
YNUM = 
[
  Fp2.new([
            0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706,
            0x1530477c7ab4113b59a4c18b076d11930f7da5d4a07f649bf54439d87d27e500fc8c25ebf8c92f6812cfc71c71c6d706]),
  Fp2.new([
            0x0,
            0x5c759507e8e333ebb5b7a9a47d7ed8532c52d39fd3a042a88b58423c50ae15d5c2638e343d9c71c6238aaaaaaaa97be]),
  Fp2.new([
            0x11560bf17baa99bc32126fced787c88f984f87adf7ae0c7f9a208c6b4f20a4181472aaa9cb8d555526a9ffffffffc71c,
            0x8ab05f8bdd54cde190937e76bc3e447cc27c3d6fbd7063fcd104635a790520c0a395554e5c6aaaa9354ffffffffe38f]),
  Fp2.new([
            0x124c9ad43b6cf79bfbf7043de3811ad0761b0f37a1e26286b0e977c69aa274524e79097a56dc4bd9e1b371c71c718b10,
            0x0])
].freeze
YDEN = 
[
  Fp2.new([
            0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb,
            0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa8fb]),
  Fp2.new([
            0x0,
            0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffa9d3]),
  Fp2.new([
            0x12,
            0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaa99]),
  Fp2.new([0x1, 0x0])
].freeze
ISOGENY_COEFFICIENTS = 
[XNUM, XDEN, YNUM, YDEN]
POINT_COMPRESSION_FLAG =

Point serialization flags

0x80
POINT_INFINITY_FLAG = 
0x40
POINT_Y_FLAG = 
0x20
VERSION = 
'0.4.0'

Class Method Summary collapse

Class Method Details

.aggregate_public_keys(public_keys) ⇒ BLS::PointG1|BLS::PointG2

Aggregate multiple public keys.

WARNING: the aggregate is only meaningful once every input key has been checked with pop_verify. Without that check an attacker who publishes pk_a = g * x - pk_victim can produce, on their own, a signature that verifies against the aggregate, making it look like the victim signed. See fast_aggregate_verify.

Parameters:

Returns:

Raises:



104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/bls.rb', line 104

def aggregate_public_keys(public_keys)
  raise BLS::Error, 'Expected non-empty array.' if public_keys.empty?
  g1_flag = public_keys.first.is_a?(PointG1)
  sum = g1_flag ? PointG1::ZERO : PointG2::ZERO
  public_keys.each do |pubkey|
    if g1_flag && !pubkey.is_a?(PointG1) || !g1_flag && !pubkey.is_a?(PointG2)
      raise BLS::Error, 'Point G1 and G2 are mixed.'
    end
    sum += pubkey
  end
  sum
end

.aggregate_signatures(signatures) ⇒ BLS::PointG2|BLS::PointG1

Aggregate multiple signatures. e(G, S) = e(G, sum(n)Si) = mul(n)(e(G, Si))

Parameters:

Returns:

Raises:



121
122
123
124
125
126
127
128
129
130
131
132
133
 
# File 'lib/bls.rb', line 121

def aggregate_signatures(signatures)
  raise BLS::Error, 'Expected non-empty array.' if signatures.empty?

  g2_flag = signatures.first.is_a?(PointG2)
  sum = g2_flag ? PointG2::ZERO : PointG1::ZERO
  signatures.each do |signature|
    if g2_flag && !signature.is_a?(PointG2) || !g2_flag && !signature.is_a?(PointG1)
      raise BLS::Error, 'Signature G1 and G2 are mixed.'
    end
    sum += signature
  end
  sum
end

.bin_xor(a, b) ⇒ String

Calculate binary xor between a and b.

Parameters:

  • a (String) —

    binary string.

  • b (String) —

    binary string.

Returns:

  • (String) —

    xor binary string.



59
60
61
62
63
64
65
66
 
# File 'lib/bls/math.rb', line 59

def bin_xor(a, b)
  res = Array.new(a.bytesize)
  b_bytes = b.bytes
  a.bytes.each.with_index do |b, i|
    res[i] = b ^ b_bytes[i]
  end
  res.pack('C*')
end

.bit_get(n, pos) ⇒ Object 



21
22
23
 
# File 'lib/bls/math.rb', line 21

def bit_get(n, pos)
  (n >> pos) & 1
end

.fast_aggregate_verify(signature, message, public_keys) ⇒ Boolean

Verify an aggregated signature over a single message signed by every key in public_keys.

WARNING: every public key must have passed pop_verify first. This check cannot be done here because it needs each key's proof, and skipping it reopens the rogue key attack that the pop scheme exists to prevent.

Parameters:

Returns:

  • (Boolean) —

    verification result.



214
215
216
217
218
219
220
221
222
 
# File 'lib/bls.rb', line 214

def fast_aggregate_verify(signature, message, public_keys)
  return false if public_keys.empty? # nothing signed, so nothing is verified
  # KeyValidate every key, not just the aggregate. The identity adds nothing to the sum, so
  # a set containing it would otherwise verify on the strength of the others while counting
  # a key that nobody holds, and could hold, as one of the signers.
  return false if public_keys.any?(&:zero?)

  verify(signature, message, aggregate_public_keys(public_keys), scheme: :pop)
end

.get_public_key(private_key, key_type: :g1) ⇒ BLS::PointG1|BLS::PointG2

Generate public key from private_key.

Parameters:

  • private_key (Integer|String) —

    The private key. Integer or String(hex).

  • key_type (Symbol) (defaults to: :g1) —

    Public key type, :g1 or :g2.

Returns:



49
50
51
52
53
54
55
56
57
58
 
# File 'lib/bls.rb', line 49

def get_public_key(private_key, key_type: :g1)
  case key_type
  when :g1
    PointG1.from_private_key(private_key)
  when :g2
    PointG2.from_private_key(private_key)
  else
    raise Error, 'key_type must be :g1 or :g2.'
  end
end

.i2osp(value, length) ⇒ Array[Integer] byte array.

Convert value to byte array of length.

Parameters:

  • value (Integer)
  • length (Integer)

Returns:

  • (Array[Integer] byte array.) —

    Array byte array.

Raises:



42
43
44
45
46
47
48
49
50
51
52
53
 
# File 'lib/bls/math.rb', line 42

def i2osp(value, length)
  raise BLS::Error, "bad I2OSP call: value=#{value} length=#{length}" if value < 0 || value >= (1 << 8 * length)

  res = Array.new(length, 0)
  i = length - 1
  while i >= 0
    res[i] = value & 0xff
    value >>= 8
    i -= 1
  end
  res
end

.miller_loop(ell, g1) ⇒ Object 



699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
 
# File 'lib/bls/field.rb', line 699

def miller_loop(ell, g1)
  f12 = Fp12::ONE
  p_x, p_y = g1
  i = BLS_X_LEN - 2
  j = 0
  while i >= 0
    f12 = f12.multiply_by_014(ell[j][0], ell[j][1] * p_x.value, ell[j][2] * p_y.value)
    unless bit_get(Curve::X, i).zero?
      j += 1
      f12 = f12.multiply_by_014(ell[j][0], ell[j][1] * p_x.value, ell[j][2] * p_y.value)
    end
    f12 = f12.square unless i.zero?
    i -= 1
    j += 1
  end
  f12.conjugate
end

.mod(a, b) ⇒ Object 



7
8
9
 
# File 'lib/bls/math.rb', line 7

def mod(a, b)
  a % b
end

.norm_p1(point) ⇒ Object 



315
316
317
 
# File 'lib/bls/point.rb', line 315

def norm_p1(point)
  point.is_a?(PointG1) ? point : PointG1.from_hex(point)
end

.norm_p1h(point, scheme: :basic) ⇒ Object 



323
324
325
 
# File 'lib/bls/point.rb', line 323

def norm_p1h(point, scheme: :basic)
  point.is_a?(PointG1) ? point : PointG1.hash_to_curve(point, scheme: scheme)
end

.norm_p2(point) ⇒ Object 



319
320
321
 
# File 'lib/bls/point.rb', line 319

def norm_p2(point)
  point.is_a?(PointG2) ? point : PointG2.from_hex(point)
end

.norm_p2h(point, scheme: :basic) ⇒ Object 



327
328
329
 
# File 'lib/bls/point.rb', line 327

def norm_p2h(point, scheme: :basic)
  point.is_a?(PointG2) ? point : PointG2.hash_to_curve(point, scheme: scheme)
end

.normalize_priv_key(private_key) ⇒ BLS::Fr

Normalize private key. A key at or above the group order is reduced rather than rejected, matching the reference implementation and the test vectors. Reducing raw entropy that way is slightly biased, so prefer drawing the key from 0 < k < Fr::ORDER to begin with. or when it reduces to zero.

Parameters:

  • private_key (String|Integer) —

    a private key with hex or number.

Returns:

  • (BLS::Fr) —

    Normalized private key.

Raises:

  • (BLS::Error) —

    Occur when the private key is not a positive hex string or integer,



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/bls/math.rb', line 76

def normalize_priv_key(private_key)
  k = case private_key
      when String
        # String#to_i stops at the first character it cannot read and returns what it has,
        # so a mistyped or truncated key would otherwise turn into a different, much
        # smaller one without any sign that it happened.
        raise BLS::Error, 'Private key must be a hex string.' unless private_key.match?(/\A[0-9a-fA-F]+\z/)

        private_key.to_i(16)
      when Integer
        private_key
      else
        raise BLS::Error, 'Private key must be Integer or String.'
      end
  raise BLS::Error, 'Private key must be positive.' unless k.positive?

  key = Fr.new(k)
  raise BLS::Error, "Private key must not be a multiple of #{Fr::ORDER}." if key.zero?

  key
end

.num_to_hex(num, byte_length) ⇒ String

Convert number to byte_length bytes hex string.

Parameters:

  • num (Integer) —

    number tobe converted.

  • byte_length (Integer) —

    byte length.

Returns:

  • (String) —

    hex value.



102
103
104
 
# File 'lib/bls/math.rb', line 102

def num_to_hex(num, byte_length)
  num.to_s(16).rjust(2 * byte_length, '0')
end

.os2ip(bytes) ⇒ Integer

Convert byte to non-negative integer.

Parameters:

  • bytes (Array[Integer]) —

    byte array.

Returns:

  • (Integer) —

    Integer.



28
29
30
31
32
33
34
35
 
# File 'lib/bls/math.rb', line 28

def os2ip(bytes)
  res = 0
  bytes.each do |b|
    res <<= 8
    res += b
  end
  res
end

.pairing(p, q, with_final_exp: true) ⇒ BLS::Fp12

Parameters:

Returns:

Raises:



10
11
12
13
14
15
16
17
18
19
 
# File 'lib/bls/pairing.rb', line 10

def pairing(p, q, with_final_exp: true)
  raise ArgumentError, 'p should be BLS::PointG1 object' unless p.is_a?(BLS::PointG1)
  raise ArgumentError, 'q should be BLS::PointG2 object' unless q.is_a?(BLS::PointG2)
  raise PairingError, 'No pairings at point of Infinity' if p.zero? || q.zero?

  p.validate!
  q.validate!
  looped = p.miller_loop(q)
  with_final_exp ? looped.final_exponentiate : looped
end

.partial_pairing(p, q) ⇒ BLS::Fp12

Pairing without the final exponentiation, using e(O, Q) = e(P, O) = 1 where pairing raises instead. Verification multiplies several of these together, so a degenerate key or signature has to fall out as a failed check rather than as an exception.

Parameters:

Returns:

Raises:

  • (ArgumentError) 


28
29
30
31
32
33
34
 
# File 'lib/bls/pairing.rb', line 28

def partial_pairing(p, q)
  raise ArgumentError, 'p should be BLS::PointG1 object' unless p.is_a?(BLS::PointG1)
  raise ArgumentError, 'q should be BLS::PointG2 object' unless q.is_a?(BLS::PointG2)
  return Fp12::ONE if p.zero? || q.zero?

  pairing(p, q, with_final_exp: false)
end

.pop_prove(private_key, key_type: :g1) ⇒ BLS::PointG2|BLS::PointG1

Generate a proof of possession for private_key: a signature, under that key, over the public key it belongs to. Producing one requires knowing the private key, which is what makes aggregation safe against rogue key attacks.

Parameters:

  • private_key (Integer|String) —

    The private key. Integer or String(hex).

  • key_type (Symbol) (defaults to: :g1) —

    Public key type, :g1 or :g2. The proof lives in the other group.

Returns:



188
189
190
191
192
193
194
 
# File 'lib/bls.rb', line 188

def pop_prove(private_key, key_type: :g1)
  public_key = get_public_key(private_key, key_type: key_type)
  msg = public_key.to_hex(compressed: true)
  msg_point = public_key.is_a?(PointG1) ? BLS.norm_p2h(msg, scheme: :pop_proof) :
                BLS.norm_p1h(msg, scheme: :pop_proof)
  msg_point * BLS.normalize_priv_key(private_key)
end

.pop_verify(public_key, proof) ⇒ Boolean

Verify a proof of possession produced by pop_prove.

Parameters:

Returns:

  • (Boolean) —

    verification result.



200
201
202
 
# File 'lib/bls.rb', line 200

def pop_verify(public_key, proof)
  verify(proof, public_key.to_hex(compressed: true), public_key, scheme: :pop_proof)
end

.pow_mod(a, power, m) ⇒ Object 



11
12
13
14
15
16
17
18
19
 
# File 'lib/bls/math.rb', line 11

def pow_mod(a, power, m)
  res = 1
  while power.positive?
    res = mod(res * a, m) unless (power & 1).zero?
    power >>= 1
    a = mod(a * a, m)
  end
  res
end

.psi(x, y) ⇒ Object 



689
690
691
692
693
 
# File 'lib/bls/field.rb', line 689

def psi(x, y)
  x2 = WSQ_INV.multiply_by_fp2(x).frobenius_map(1).multiply(WSQ).coeffs[0].coeffs[0]
  y2 = WCU_INV.multiply_by_fp2(y).frobenius_map(1).multiply(WCU).coeffs[0].coeffs[0]
  [x2, y2]
end

.psi2(x, y) ⇒ Object 



695
696
697
 
# File 'lib/bls/field.rb', line 695

def psi2(x, y)
  [x * PSI2_C1, y.negate]
end

.sgn0(x) ⇒ Integer

sgn0 for GF(p^2), from RFC 9380 section 4.1. Combined with | and & rather than || and &&: sign_0 is 0 or 1, and 0 is truthy in Ruby, so a disjunction would always short circuit on it and x_1 would never be reached.

Parameters:

Returns:

  • (Integer) —

    0 or 1.



724
725
726
727
728
729
730
 
# File 'lib/bls/field.rb', line 724

def sgn0(x)
  x0, x1 = x.values
  sign_0 = x0 % 2
  zero_0 = x0.zero? ? 1 : 0
  sign_1 = x1 % 2
  sign_0 | (zero_0 & sign_1)
end

.sign(message, private_key, sig_type: :g2, scheme: :basic) ⇒ PointG2

Generate BLS signature: s = pk x H(m) If :g1 is specified, the signature is a point on G1 and the public key is a point on G2. If :g2 is specified, the signature is a point on G2 and the public key is a point on G1. do not verify under the other, so signer and verifier must agree on it.

Parameters:

  • message (String) —

    Message digest(hex format) to be signed.

  • private_key (Integer|String) —

    The private key used for signing. Integer or String(hex).

  • sig_type (Symbol) (defaults to: :g2) —

    Signature type, :g1 or :g2.

  • scheme (Symbol) (defaults to: :basic) —

    Signature scheme, :basic or :pop. Signatures made under one scheme

Returns:

  • (PointG2) —

    The signature point.



33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/bls.rb', line 33

def sign(message, private_key, sig_type: :g2, scheme: :basic)
  msg_point = case sig_type
              when :g1
                BLS.norm_p1h(message, scheme: scheme)
              when :g2
                BLS.norm_p2h(message, scheme: scheme)
              else
                raise Error, 'sig_type must be :g1 or :g2.'
              end
  msg_point * BLS.normalize_priv_key(private_key)
end

.sqrt_div_fp2(u, v) ⇒ Object 



732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
 
# File 'lib/bls/field.rb', line 732

def sqrt_div_fp2(u, v)
  uv7 = u * v**7
  uv15 = uv7 * v**8
  gamma = uv15**P_MINUS_9_DIV_16 * uv7
  success = false
  result = gamma
  positive_roots_of_unity = Fp2::ROOTS_OF_UNITY[0...4]
  positive_roots_of_unity.each do |root|
    candidate = root * gamma
    if (candidate**2 * v - u).zero? && !success
      success = true
      result = candidate
    end
  end
  [success, result]
end

.verify(signature, message, public_key, scheme: :basic) ⇒ Boolean

Verify BLS signature. Verify one of the following:

  • Public key is a point on G1, signature is a point on G2 or
  • Public key is a point on G2, signature is a point on G1.

Parameters:

  • signature (BLS::PointG1|BLS::PointG2)
  • message (String) —

    Message digest(hash value with hex format) to be verified.

  • public_key (BLS::PointG2|BLS::PointG1) —

    Public key with hex format or PointG1.

  • scheme (Symbol) (defaults to: :basic) —

    Signature scheme the signature was made under, :basic or :pop.

Returns:

  • (Boolean) —

    verification result.



68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/bls.rb', line 68

def verify(signature, message, public_key, scheme: :basic)
  unless signature.is_a?(PointG1) && public_key.is_a?(PointG2) ||
    signature.is_a?(PointG2) && public_key.is_a?(PointG1)
    raise BLS::Error, 'Invalid signature or public key. If the public key is PointG1, the signature must be an element of Point::G2 or vice versa.'
  end
  # KeyValidate of draft-irtf-cfrg-bls-signature section 2.5. The identity is not a public
  # key anybody holds, and pairing it away would leave the identity signature verifying
  # against every message.
  return false if public_key.zero?

  g = public_key.is_a?(PointG1) ? PointG1::BASE : PointG2::BASE
  ephm = if public_key.is_a?(PointG1)
           hm = BLS.norm_p2h(message, scheme: scheme)
           BLS.partial_pairing(public_key.negate, hm)
         else
           hm = BLS.norm_p1h(message, scheme: scheme)
           BLS.partial_pairing(hm, public_key.negate)
         end
  egs = if public_key.is_a?(PointG1)
          BLS.partial_pairing(g, signature)
        else
          BLS.partial_pairing(signature, g)
        end
  exp = (egs * ephm).final_exponentiate
  exp == Fp12::ONE
end

.verify_batch(signature, messages, public_keys, scheme: :basic) ⇒ Boolean

Verify aggregated signature.

Under the :basic scheme the messages must all be distinct: repeating one is reported as an invalid signature, since that scheme has nothing but message distinctness to stop a rogue key from signing on another key's behalf. Use :pop, whose proofs of possession rule that out, to verify several signatures over the same message.

Parameters:

  • signature (BLS::PointG2|BLS::PointG1) —

    aggregated signature(BLS::PointG2 or BLS::PointG1).

  • messages (Array[String]) —

    the list of message.

  • public_keys (Array[BLS::PointG1]|Array[BLS::PointG2]) —

    the list of public keys(BLS::PointG1 or BLS::PointG2).

  • scheme (Symbol) (defaults to: :basic) —

    Signature scheme the signatures were made under, :basic or :pop.

Returns:

  • (Boolean) —

    verification result.

Raises:



147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/bls.rb', line 147

def verify_batch(signature, messages, public_keys, scheme: :basic)
  raise BLS::Error, 'Public keys count should equal msg count.' unless messages.size == public_keys.size
  return false if messages.empty? # nothing was signed, so nothing is verified

  sig_g2_flag = signature.is_a?(PointG2)
  public_keys.each do |public_key|
    if sig_g2_flag && !public_key.is_a?(PointG1) || !sig_g2_flag && !public_key.is_a?(PointG2)
      raise BLS::Error, "Public key must be #{sig_g2_flag ? 'PointG1' : 'PointG2'}"
    end
  end
  return false if public_keys.any?(&:zero?) # KeyValidate, as in #verify

  n_message = messages.map { |m| sig_g2_flag ? BLS.norm_p2h(m, scheme: scheme) : BLS.norm_p1h(m, scheme: scheme)}

  # Keys that signed the same message are summed so that message is paired exactly once:
  # e(P1, Q) * e(P2, Q) == e(P1 + P2, Q). Grouping on the serialized point rather than on
  # the message keeps this independent of how equal messages happened to be spelled.
  zero = sig_g2_flag ? PointG1::ZERO : PointG2::ZERO
  grouped = {}
  n_message.each_with_index do |message, i|
    group = (grouped[message.to_hex(compressed: true)] ||= [message, zero])
    group[1] += public_keys[i]
  end
  return false if scheme == :basic && grouped.size < n_message.size

  paired = grouped.each_value.map do |message, group_pubkey|
    sig_g2_flag ? BLS.partial_pairing(group_pubkey, message) :
      BLS.partial_pairing(message, group_pubkey)
  end
  paired << (sig_g2_flag ? BLS.partial_pairing(PointG1::BASE.negate, signature) :
               BLS.partial_pairing(signature, PointG2::BASE.negate))
  product = paired.inject(Fp12::ONE) { |a, b| a * b }
  product.final_exponentiate == Fp12::ONE
end