"Compute Birkoff Coefficeint" in DKG about alice HOT 2 CLOSED

Thank you so much for the clarification!

from alice.

Hi,
"Birkhoff coefficient" is similar to "Lagrange coefficient".
Given a system of paris {(n_i,x_i)}_{i=1}^n, you can compute the "Birkhoff coefficient." Here n_i means the n_i times differentiation and x_i is the x-coordinate. If n_i =0 for all i, then Birkhoff coefficients can be regarded as Lagrange coefficients.

Taking a simple example, assume that f(x)=3x^2+5x+1 and fix (n_1,x_1) = (1,1), (n_2, x_2) = (1,2), (n_3, x_3) = (0, 3).
Then, you can compute share_1 = 11, share_2 = 17, share_3 = 43. (i.e. f'(x) =6x+5 )
By convention, f(0) = 1 is the secret.

In this case. the definition of Birkhoff coefficient {a_i} is a system of coefficient satisfying
\sum_i a_i * share_i = f(0) = the secret.
In this case, a_1 * 11+a_2 * 17+a_3 * 43 = f(0) = 1.

How to compute Birkhoff coefficient?

Assume that f(x) := ax^2+bx+c, you can list a system of linear equation corresponding to (n_1,x_1) = (1,1), (n_2, x_2) = (1,2), (n_3, x_3) = (0,3):

[0 1 2] [c] [ share_1]
[0 1 4]*[b] = [ share_2]
[1 3 9] [a] [ share_3]

Assume that the above 3x3 matrix is called M. Then you can solve the above system by multiplying the inverse matrix of M:

[c] [share_1]
[b] = M^{-1} * [share_2]
[a] [share_3].

Note that you can observe the first row of M^{-1}, which are "Birkhoff coefficient", since
c = M_{11}*share_1+M_{12}*share_2+M_{13}*share.
The above computation is working in a given field.

You can also see the appendix C in this paper: https://eprint.iacr.org/2017/724.pdf

Remark:

1. If the above matrix M is not square, then we generalize this progress by using pseudo-inverse.
   ref:

   alice/crypto/matrix/matrix.go

   Line 550 in f2af6dd

   func (m *Matrix) Pseudoinverse() (*Matrix, error) {

2. In order to ensure recovering the secret, we need to check that a system of pairs "{(n_i,x_i)}" works well.
   ref.

   alice/crypto/birkhoffinterpolation/birkhoffinterpolation.go

   Line 123 in f2af6dd

   func (bks BkParameters) CheckValid(threshold uint32, fieldOrder *big.Int) error {

If you have any question, please let me know. Thanks!

from alice.