Module: BLS

Defined in:
lib/bls.rb,
lib/bls/h2c.rb,
lib/bls/math.rb,
lib/bls/curve.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.3.0'

Class Method Summary collapse

Class Method Details

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

Aggregate multiple public keys.

Parameters:

Returns:

Raises:



91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/bls.rb', line 91

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:



108
109
110
111
112
113
114
115
116
117
118
119
120
 
# File 'lib/bls.rb', line 108

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.



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

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 



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

def bit_get(n, pos)
  (n >> pos) & 1
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:



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

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:



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

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 



683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
 
# File 'lib/bls/field.rb', line 683

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
10
 
# File 'lib/bls/math.rb', line 7

def mod(a, b)
  res = a % b
  res >= 0 ? res : b + res
end

.norm_p1(point) ⇒ Object 



238
239
240
 
# File 'lib/bls/point.rb', line 238

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

.norm_p1h(point) ⇒ Object 



246
247
248
 
# File 'lib/bls/point.rb', line 246

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

.norm_p2(point) ⇒ Object 



242
243
244
 
# File 'lib/bls/point.rb', line 242

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

.norm_p2h(point) ⇒ Object 



250
251
252
 
# File 'lib/bls/point.rb', line 250

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

.normalize_priv_key(private_key) ⇒ BLS::Fr

Normalize private key.

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 zero.



73
74
75
76
77
 
# File 'lib/bls/math.rb', line 73

def normalize_priv_key(private_key)
  k = private_key.is_a?(String) ? private_key.to_i(16) : private_key
  raise BLS::Error, "Private key must be 0 < private_key < #{Fr::ORDER}" if k <= 0
  Fr.new(k)
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.



83
84
85
 
# File 'lib/bls/math.rb', line 83

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.



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

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:



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

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

.pow_mod(a, power, m) ⇒ Object 



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

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 



673
674
675
676
677
 
# File 'lib/bls/field.rb', line 673

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 



679
680
681
 
# File 'lib/bls/field.rb', line 679

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

.sgn0(x) ⇒ Object 



703
704
705
706
707
708
709
 
# File 'lib/bls/field.rb', line 703

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

.sign(message, private_key, sig_type: :g2) ⇒ 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.

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.

Returns:

  • (PointG2) —

    The signature point.



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

def sign(message, private_key, sig_type: :g2)
  msg_point = case sig_type
              when :g1
                BLS.norm_p1h(message)
              when :g2
                BLS.norm_p2h(message)
              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 



711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
 
# File 'lib/bls/field.rb', line 711

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) ⇒ 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:

Returns:

  • (Boolean) —

    verification result.



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/bls.rb', line 66

def verify(signature, message, public_key)
  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
  g = public_key.is_a?(PointG1) ? PointG1::BASE : PointG2::BASE
  ephm = if public_key.is_a?(PointG1)
           hm = BLS.norm_p2h(message)
           BLS.pairing(public_key.negate, hm, with_final_exp: false)
         else
           hm = BLS.norm_p1h(message)
           BLS.pairing(hm, public_key.negate, with_final_exp: false)
         end
  egs = if public_key.is_a?(PointG1)
          BLS.pairing(g, signature, with_final_exp: false)
        else
          BLS.pairing(signature, g, with_final_exp: false)
        end
  exp = (egs * ephm).final_exponentiate
  exp == Fp12::ONE
end

.verify_batch(signature, messages, public_keys) ⇒ Boolean

Verify aggregated signature.

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).

Returns:

  • (Boolean) —

    verification result.

Raises:



127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
# File 'lib/bls.rb', line 127

def verify_batch(signature, messages, public_keys)
  raise BLS::Error, 'Expected non-empty array.' if messages.empty?
  raise BLS::Error, 'Public keys count should equal msg count.' unless messages.size == public_keys.size

  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

  n_message = messages.map { |m| sig_g2_flag ? BLS.norm_p2h(m) : BLS.norm_p1h(m)}
  paired = []
  zero = sig_g2_flag ? PointG1::ZERO : PointG2::ZERO
  n_message.each do |message|
    group_pubkey = n_message.each_with_index.inject(zero)do|group_pubkey, (sub_message, i)|
      sub_message == message ? group_pubkey + public_keys[i] : group_pubkey
    end
    paired << (sig_g2_flag ? BLS.pairing(group_pubkey, message, with_final_exp: false) :
                 BLS.pairing(message, group_pubkey, with_final_exp: false))
  end
  paired << (sig_g2_flag ? BLS.pairing(PointG1::BASE.negate, signature, with_final_exp: false) :
               BLS.pairing(signature, PointG2::BASE.negate, with_final_exp: false))
  product = paired.inject(Fp12::ONE) { |a, b| a * b }
  product.final_exponentiate == Fp12::ONE
end