Class: BSV::Primitives::Polynomial

Inherits:
Object
  • Object
show all
Defined in:
lib/bsv/primitives/polynomial.rb

Overview

A polynomial defined by a set of points, evaluated using Lagrange interpolation.

Used in Shamir’s Secret Sharing Scheme to split and reconstruct a secret. All arithmetic is performed in the finite field GF(P) where P is the secp256k1 field prime.

The secret is encoded as the y-value at x=0. Given threshold distinct points the polynomial can be evaluated at any x by Lagrange interpolation.

Examples:

Construct shares from a private key

poly   = Polynomial.from_private_key(key, threshold: 2)
share1 = poly.value_at(OpenSSL::BN.new('1'))
share0 = poly.value_at(OpenSSL::BN.new('0'))  # recovers the secret

Constant Summary collapse

P = 
PointInFiniteField::P

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(points, threshold = nil) ⇒ Polynomial

Returns a new instance of Polynomial.

Parameters:

  • points (Array<PointInFiniteField>) —

    defining points

  • threshold (Integer) (defaults to: nil) —

    reconstruction threshold (defaults to points.length)



31
32
33
34
 
# File 'lib/bsv/primitives/polynomial.rb', line 31

def initialize(points, threshold = nil)
  @points    = points
  @threshold = threshold || points.length
end

Instance Attribute Details

#points ⇒ Array<PointInFiniteField> (readonly)

Returns the defining points of the polynomial.

Returns:



24
25
26
 
# File 'lib/bsv/primitives/polynomial.rb', line 24

def points
  @points
end

#threshold ⇒ Integer (readonly)

Returns the minimum number of shares needed to reconstruct the secret.

Returns:

  • (Integer) —

    the minimum number of shares needed to reconstruct the secret



27
28
29
 
# File 'lib/bsv/primitives/polynomial.rb', line 27

def threshold
  @threshold
end

Class Method Details

.from_private_key(key, threshold:) ⇒ Polynomial

Build a polynomial whose y-intercept (secret) is the private key scalar.

The first point is (0, key_scalar). The remaining threshold-1 points have random coordinates in [0, P), providing the random coefficients of the underlying polynomial.

Parameters:

  • key (PrivateKey) —

    the private key to split

  • threshold (Integer) —

    the reconstruction threshold (minimum 2)

Returns:



45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/bsv/primitives/polynomial.rb', line 45

def self.from_private_key(key, threshold:)
  secret_y = key.bn
  points   = [PointInFiniteField.new(OpenSSL::BN.new('0'), secret_y)]

  (threshold - 1).times do
    random_x = OpenSSL::BN.rand(256) % P
    random_y = OpenSSL::BN.rand(256) % P
    points << PointInFiniteField.new(random_x, random_y)
  end

  new(points, threshold)
end

Instance Method Details

#value_at(x) ⇒ OpenSSL::BN

Evaluate the polynomial at x using Lagrange interpolation mod P.

Parameters:

  • x (OpenSSL::BN) —

    the x value at which to evaluate

Returns:

  • (OpenSSL::BN) —

    the y value, in [0, P)



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/bsv/primitives/polynomial.rb', line 62

def value_at(x)
  y = OpenSSL::BN.new('0')

  threshold.times do |i|
    term = points[i].y
    threshold.times do |j|
      next if i == j

      xi = points[i].x
      xj = points[j].x

      numerator   = umod(x - xj, P)
      denominator = umod(xi - xj, P)
      denom_inv   = denominator.mod_inverse(P)

      fraction = numerator.mod_mul(denom_inv, P)
      term     = term.mod_mul(fraction, P)
    end
    y = y.mod_add(term, P)
  end

  y
end