search

nucypher / NuBLS

NuBLS is pure Rust implementation of BLS signatures with nifty threshold protocols
GNU Affero General Public License v3.0
19 stars 6 forks source link

Properly manage fragment indices #12

Closed tuxxy closed 4 years ago

tuxxy commented 4 years ago

With Shamir's Secret Sharing, to perform a recovery, we must know the "fragment index" of the corresponding fragment. A fragment index is used as an input to a Polynomial where the coefficients are the m-1 threshold fragments. The output of the polynomial evaluation, given an index, is the fragment itself. When m fragments and their corresponding fragment_indices are known, it's possible to re-assemble them using Lagrange basis polynomials.

Presently, we have no specification for calculating a "fragment index" (see issue #3) for a given fragment. As such, we naively assume that the fragments provided to PrivateKey::recover are ordered and their corresponding fragment_index is their index in the vector + 1.

This does not work when fragments are collected out of order. See test_unordered_index_recovery for the test demonstrating this failure.

To solve this, we need to have some sort of mechanism to store the fragment_index along with its corresponding fragment. Ideally, #3 will resolve this issue and allow us to deterministically generate these shares so that we no longer need to store them along with the fragment.

tuxxy commented 4 years ago

Presently, this is the only blocking issue in achieving our initial MVP release. There will likely be some refactoring of the API required to resolve this issue.