Closed vihu closed 3 years ago
It's been a while since I worked on this, so I might misremember, but:
In the i
-th iteration of the loop, base
is a nonzero i
-th degree polynomial that is zero on the first i
sample points. Since an i
-th degree polynomial can have at most i
zeros, if the points are distinct, the value at the next point x
must always be nonzero.
Specifically, base
is the polynomial (X - s[0]) * (X - s[1]) * … * (X - s[i - 1])
, which is nonzero in s[i]
unless s[i]
is a duplicate of one of the earlier sample points.
It's been a while since I worked on this, so I might misremember, but:
In the
i
-th iteration of the loop,base
is a nonzeroi
-th degree polynomial that is zero on the firsti
sample points. Since ani
-th degree polynomial can have at mosti
zeros, if the points are distinct, the value at the next pointx
must always be nonzero.Specifically,
base
is the polynomial(X - s[0]) * (X - s[1]) * … * (X - s[i - 1])
, which is nonzero ins[i]
unlesss[i]
is a duplicate of one of the earlier sample points.
I see, so as long as the points are distinct it's impossible for base to go to zero. Thanks for the explanation :)
Relevant line: https://github.com/poanetwork/threshold_crypto/blob/a7fbfa4522835010b6037fb45388c7b04ee14194/src/poly.rs#L407
I was wondering whether the error message here could be a little more precise, it's not technically a case of duplicate points right? The
base_value
has evaluated to0
and we cannot calculate the inverse of a zero. If the maintainers think this is a legit issue, I can write a simple PR to handle the error whenbase_val = 0
slightly better.