module BLS

Constants

BLS_X_LEN
DST_LABEL
ISOGENY_COEFFICIENTS
POW_2_381
POW_2_382
POW_2_383
PSI2_C1

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

PUBLIC_KEY_LENGTH
P_MINUS_9_DIV_16
SHA256_DIGEST_SIZE
UT_ROOT
VERSION
WCU
WCU_INV
WSQ
WSQ_INV
XDEN
XNUM
YDEN
YNUM

Public Instance Methods

aggregate_public_keys(public_keys) click to toggle source

Aggregate multiple public keys. @param [Array] public_keys the list of public keys. @return [BLS::PointG1] aggregated public key.

# File lib/bls.rb, line 61
def aggregate_public_keys(public_keys)
  raise BLS::Error, 'Expected non-empty array.' if public_keys.empty?

  public_keys.map { |p| BLS.norm_p1(p) }.inject(PointG1::ZERO) { |sum, p| sum + p }
end
aggregate_signatures(signatures) click to toggle source

Aggregate multiple signatures. e(G, S) = e(G, sum(n)Si) = mul(n)(e(G, Si)) @param [Array] signatures multiple signatures. @return [BLS::PointG2] aggregated signature.

# File lib/bls.rb, line 71
def aggregate_signatures(signatures)
  raise BLS::Error, 'Expected non-empty array.' if signatures.empty?

  signatures.map { |s| BLS.norm_p2(s) }.inject(PointG2::ZERO) { |sum, s| sum + s }
end
bin_xor(a, b) click to toggle source

Calculate binary xor between a and b. @param [String] a binary string. @param [String] b binary string. @return [String] xor binary string.

# 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) click to toggle source
# File lib/bls/math.rb, line 22
def bit_get(n, pos)
  (n >> pos) & 1
end
clear_cofactor_g2(p) click to toggle source
# File lib/bls/point.rb, line 446
def clear_cofactor_g2(p)
  t1 = p.multiply_unsafe(Curve::X).negate
  t2 = p.from_affine_tuple(BLS.psi(*p.to_affine))
  p2 = p.from_affine_tuple(BLS.psi2(*p.double.to_affine))
  p2 - t2 + (t1 + t2).multiply_unsafe(Curve::X).negate - t1 - p
end
expand_message_xmd(message, len_in_bytes) click to toggle source

@param [String] message hash value with hex format. @param [Integer] len_in_bytes length @return [Array] byte array. @raise BLS::Error

# File lib/bls/point.rb, line 490
def expand_message_xmd(message, len_in_bytes)
  b_in_bytes = BigDecimal(SHA256_DIGEST_SIZE)
  r_in_bytes = b_in_bytes * 2
  ell = (BigDecimal(len_in_bytes) / b_in_bytes).ceil
  raise BLS::Error, 'Invalid xmd length' if ell > 255

  dst_prime = DST_LABEL.bytes + BLS.i2osp(DST_LABEL.bytesize, 1)
  z_pad = BLS.i2osp(0, r_in_bytes)
  l_i_b_str = BLS.i2osp(len_in_bytes, 2)
  b = Array.new(ell)
  payload = z_pad + [message].pack('H*').bytes + l_i_b_str + BLS.i2osp(0, 1) + dst_prime
  b_0 = Digest::SHA256.digest(payload.pack('C*'))
  b[0] = Digest::SHA256.digest((b_0.bytes + BLS.i2osp(1, 1) + dst_prime).pack('C*'))
  (1..ell).each do |i|
    args = BLS.bin_xor(b_0, b[i - 1]).bytes + BLS.i2osp(i + 1, 1) + dst_prime
    b[i] = Digest::SHA256.digest(args.pack('C*'))
  end
  b.map(&:bytes).flatten[0...len_in_bytes]
end
get_public_key(private_key) click to toggle source

Generate public key from private_key. @param [Integer|String] private_key The private key. Integer or String(hex). @return [BLS::PointG1] public key.

# File lib/bls.rb, line 38
def get_public_key(private_key)
  PointG1.from_private_key(private_key)
end
hash_to_field(message, degree, random_oracle: true) click to toggle source

Convert hash to Field. @param [String] message hash value with hex format. @return [Array] byte array.

# File lib/bls/point.rb, line 468
def hash_to_field(message, degree, random_oracle: true)
  count = random_oracle ? 2 : 1
  l = 64
  len_in_bytes = count * degree * l
  pseudo_random_bytes = BLS.expand_message_xmd(message, len_in_bytes)
  u = Array.new(count)
  count.times do |i|
    e = Array.new(degree)
    degree.times do |j|
      elm_offset = l * (j + i * degree)
      tv = pseudo_random_bytes[elm_offset...(elm_offset + l)]
      e[j] = BLS.mod(BLS.os2ip(tv), Curve::P)
    end
    u[i] = e
  end
  u
end
i2osp(value, length) click to toggle source

Convert value to byte array of length. @param [Integer] value @param [Integer] length @return [Array byte array. @raise [BLS::Error]

# 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
isogeny_map_g2(x, y, z) click to toggle source

3-isogeny map from E' to E Converts from Jacobi (xyz) to Projective (xyz) coordinates.

# File lib/bls/math.rb, line 106
def isogeny_map_g2(x, y, z)
  mapped = Array.new(4, Fq2::ZERO)
  z_powers = [z, z**2, z**3]
  ISOGENY_COEFFICIENTS.each.with_index do |k, i|
    mapped[i] = k[-1]
    arr = k[0...-1].reverse
    arr.each.with_index do |a, j|
      mapped[i] = mapped[i] * x + z_powers[j] * a
    end
  end
  mapped[2] *= y
  mapped[3] *= z
  z2 = mapped[1] * mapped[3]
  x2 = mapped[0] * mapped[3]
  y2 = mapped[1] * mapped[2]
  [x2, y2, z2]
end
map_to_curve_sswu_g2(t) click to toggle source

Optimized SWU Map - FQ2 to G2': y^2 = x^3 + 240i * x + 1012 + 1012i

# File lib/bls/math.rb, line 70
def map_to_curve_sswu_g2(t)
  iso_3_a = Fq2.new([0, 240])
  iso_3_b = Fq2.new([1012, 1012])
  iso_3_z = Fq2.new([-2, -1])
  t = Fq2.new(t) if t.is_a?(Array)
  t2 = t**2
  iso_3_z_t2 = iso_3_z * t2
  ztzt = iso_3_z_t2 + iso_3_z_t2**2
  denominator = (iso_3_a * ztzt).negate
  numerator = iso_3_b * (ztzt + Fq2::ONE)
  denominator = iso_3_z * iso_3_a if denominator.zero?
  v = denominator**3
  u = numerator**3 + iso_3_a * numerator * denominator**2 + iso_3_b * v
  success, sqrt_candidate_or_gamma = BLS.sqrt_div_fq2(u, v)
  y = success ? sqrt_candidate_or_gamma : nil
  sqrt_candidate_x1 = sqrt_candidate_or_gamma * t**3
  u = iso_3_z_t2**3 * u
  success2 = false
  Fq2::ETAS.each do |eta|
    eta_sqrt_candidate = eta * sqrt_candidate_x1
    temp = eta_sqrt_candidate**2 * v - u
    if temp.zero? && !success && !success2
      y = eta_sqrt_candidate
      success2 = true
    end
  end
  raise BLS::PointError, 'Hash to Curve - Optimized SWU failure' if !success && !success2

  numerator *= iso_3_z_t2 if success2
  y = y.negate if BLS.sgn0(t) != BLS.sgn0(y)
  y *= denominator
  [numerator, y, denominator]
end
miller_loop(ell, g1) click to toggle source
# File lib/bls/field.rb, line 647
def miller_loop(ell, g1)
  f12 = Fq12::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) click to toggle source
# File lib/bls/math.rb, line 7
def mod(a, b)
  res = a % b
  res >= 0 ? res : b + res
end
norm_p1(point) click to toggle source
# File lib/bls/point.rb, line 453
def norm_p1(point)
  point.is_a?(PointG1) ? point : PointG1.from_hex(point)
end
norm_p2(point) click to toggle source
# File lib/bls/point.rb, line 457
def norm_p2(point)
  point.is_a?(PointG2) ? point : PointG2.from_hex(point)
end
norm_p2h(point) click to toggle source
# File lib/bls/point.rb, line 461
def norm_p2h(point)
  point.is_a?(PointG2) ? point : PointG2.hash_to_curve(point)
end
normalize_priv_key(private_key) click to toggle source

Normalize private key. @param [String|Integer] private_key a private key with hex or number. @return [BLS::Fq] private key field. @raise [BLS::Error] Occur when the private key is zero.

# File lib/bls/math.rb, line 128
def normalize_priv_key(private_key)
  k = private_key.is_a?(String) ? private_key.to_i(16) : private_key
  fq = Fq.new(k)
  raise BLS::Error, 'Private key cannot be 0' if fq.zero?

  fq
end
num_to_hex(num, byte_length) click to toggle source

Convert number to byte_length bytes hex string. @param [Integer] num number tobe converted. @param [Integer] byte_length byte length. @return [String] hex value.

# File lib/bls/math.rb, line 140
def num_to_hex(num, byte_length)
  num.to_s(16).rjust(2 * byte_length, '0')
end
os2ip(bytes) click to toggle source

Convert byte to non-negative integer. @param [Array] bytes byte array. @return [Array] byte array.

# 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) click to toggle source

@param [BLS::PointG1] p @param [BLS::PointG2] q @param [Boolean] with_final_exp @return [BLS::Fq12] @return [BLS::PairingError] Occur when p.zero? or q.zero?

# File lib/bls/pairing.rb, line 11
def pairing(p, q, with_final_exp: true)
  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) click to toggle source
# 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) click to toggle source
# File lib/bls/field.rb, line 637
def psi(x, y)
  x2 = WSQ_INV.multiply_by_fq2(x).frobenius_map(1).multiply(WSQ).coeffs[0].coeffs[0]
  y2 = WCU_INV.multiply_by_fq2(y).frobenius_map(1).multiply(WCU).coeffs[0].coeffs[0]
  [x2, y2]
end
psi2(x, y) click to toggle source
# File lib/bls/field.rb, line 643
def psi2(x, y)
  [x * PSI2_C1, y.negate]
end
sgn0(x) click to toggle source
# File lib/bls/field.rb, line 667
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) click to toggle source

Generate BLS signature: s = pk x H(m) @param [String] message Message digest(hash value with hex format) to be signed. @param [Integer|String] private_key The private key used for signing. Integer or String(hex). @return [PointG2] The signature point.

# File lib/bls.rb, line 30
def sign(message, private_key)
  msg_point = BLS.norm_p2h(message)
  msg_point * BLS.normalize_priv_key(private_key)
end
sqrt_div_fq2(u, v) click to toggle source
# File lib/bls/field.rb, line 675
def sqrt_div_fq2(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 = Fq2::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) click to toggle source

Verify BLS signature. @param [String] signature @param [String] message Message digest(hash value with hex format) to be verified. @param [String|BLS::PointG1] public_key Public key with hex format or PointG1. @return [Boolean] verification result.

# File lib/bls.rb, line 47
def verify(signature, message, public_key)
  p = BLS.norm_p1(public_key)
  hm = BLS.norm_p2h(message)
  g = PointG1::BASE
  s = BLS.norm_p2(signature)
  ephm = BLS.pairing(p.negate, hm, with_final_exp: false)
  egs = BLS.pairing(g, s, with_final_exp: false)
  exp = (egs * ephm).final_exponentiate
  exp == Fq12::ONE
end
verify_batch(signature, messages, public_keys) click to toggle source

Verify aggregated signature. @param [BLS::PointG2] signature aggregated signature. @param [Array] messages the list of message. @param [Array] public_keys the list of public keys with hex or BLS::PointG1 format. @return [Boolean] verification result.

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

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