Since nubls is also a Python module that wraps rust-nubls, we need to scope out an API that makes sense for it.

For NuBLS to be compilable to wasm, the Rust implementation (and its dependencies) need to be no_std capable.

The following libraries need to be checked for no_std compatibility:

• bls12_381 -- https://docs.rs/bls12_381/0.1.1/bls12_381/
• getrandom -- https://docs.rs/getrandom/0.1.14/getrandom/
• rust-nubls -- This repo.

bls12_381

• As per the documentation, this library does not require the standard lib and can be used with no_std.

getrandom

• As per the documentation, this library does not require the standard lib and can be used with no_std.
  • Special note for WASM-based CSPRNGs
• Requires a feature flag for the wasm32-unknown-unknown build target.

rust-nubls

• Presently, the rust-nubls crate uses all no_std compatible libraries.
• Due to #1, we lack full native API compatibility and rely on external libraries to do hash_to_curve.
• no_std compatibility is blocking on #16

When calling recover, the fragment_indices must be passed to lambda_coeff. Due to compile-time size restrictions, we don't know the length of fragment_indices. To get around this, we create a buffer of size 256 for the index Scalars and set the elements of each to the length of fragments. Then we pass a slice with the length of fragments to lambda_coeff.

This can be refactored, but both lambda_coeff and recover will need to be changed a bit. The idea is to pass fragments to lambda_coeff and have it access the index from the fragment directly.

This will take some care because lambda_coeff expects a slice of Scalars and a fragment can be both a PrivateKey and a Signature. This may be evidence of a potential Fragment Trait (or type) peaking through, so this should be investigated.

We need documentation that's as detailed as the rust library for the PyO3 wrapper.

Take note that PyO3 allows our documentation to be reachable to the end user in the Python module as well.

We need test vectors for the lambda_coeff utility function. These need to be made specifically for the BLS12-381 curve. As such, we might have to design these ourselves.

We need CI testing to be added for this codebase. We can likely use CircleCI or GitHub actions.

We should write some tests for the PyO3 wrapper that helps determine the memory profile of a long-running application using the Python NuBLS wrapper. See https://pyo3.rs/master/debugging.html for using Valgrind.

It would be a good idea to have some __dunder__ methods implemented for the PyO3 wrapper.

Some good ones are __eq__, __bytes__, and __repr__.

Similarly to Umbral, it would be ideal if a Signer holding a key fragment could prove that the signature is valid under the corresponding key fragment. I have a suspicion that this can be proved in a similar manner to Umbral's re-encryption proofs.

@arjunhassard it would also be interesting to find the use cases for such proofs. Likely, we can use them to prevent misbehavior on the network, however it would also be nice to know if Users would like these proofs. Furthermore, there may be other proofs associated to this data that Users may want to have.

After running
pip install pynubls
and in python:
from pynubls import PrivateKey
results in
ImportError: cannot import name 'PrivateKey' from 'pynubls' (/home/user/.local/lib/python3.8/site-packages/pynubls/__init__.py)

The API currently has a few places where Vecs are used heavily. Unfortunately, Vec is a part of the Rust stdlib and cannot be used in #![no_std] environments (see #5).

They are currently used in:

1. Signature::assemble
2. PrivateKey::split
3. PrivateKey::recover
4. utils::lambda_coeff

Thankfully, PrivateKey::split is the only method to return a Vec.
Most of these replacements will be simple to replace with fixed-sized arrays.

The PrivateKey::split method will require a breaking change wherein we pass a reference to an array that we then use to fill with fragments. This new signature may look like:

fn split(&self, threshold: usize, frag_buff: &[PrivateKey]) -> &[PrivateKey]

This should be familiar to C developers. It's not the most ergonomic, but it helps us achieve no_std compatibility!

The IETF BLS draft specification does not have test vectors yet (see https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-02#appendix-B).

It would be ideal to find something we can use in in the meantime.

We need a hash_to_curve implementation that follows the IETF hash_to_curve draft specification.

The specification can be found here: https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06.
The paper referenced by the IETF spec is found here: https://eprint.iacr.org/2019/403.pdf.

There is a possibility that there already exists an implementation in Rust. A library worth digging into is: https://docs.rs/paired/0.19.1/ (which is a fork of https://gihtub.com/ZKCrypto/pairing).

Currently, we provide a very simple hash_message function in the nubls Python module that can be used to hash arbitrary bytes onto the BLS12-381 curve.

Instead, we should write a pub(crate) visible function in the PyO3 wrapper that accepts PyBytes and executes the py_ecc.hash_to_curve.hash_to_G2 returning a G2Affine type.

The signature for such a function may look like this:

pub(crate) fn hash_message(bytes: &PyBytes) -> &G2Affine

The API in which we can execute the modules in py_ecc can be accessed via PyO3's PyModule::import function.

Inside the Python nubls module, we need to build a rust-nubls wrapping crate that uses PyO3 to provide an interface between rust-nubls and nubls.

The READMEs are quite bare and need more than just a line of text. We should put API usage examples and more relevant info about our BLS implementation.

We need to implement serialization methods on the types that are going to be serialized during common API usage. This includes: PublicKey, PrivateKey, and Signature.

Fortunately, all of these types wrap underlying BLS12_381 types like G1Affine, Scalar, and G2Affine respectively. This makes it easy to serialize, because BLS12_381 offers serialization methods in each of these modules (see https://docs.rs/bls12_381/0.1.1/bls12_381/).

A simple from_bytes and to_bytes pattern would work here for each of these types, though better patterns may exist. It's also worth looking into using serde.

Special note: For group elements (G1Affine and G2Affine), these must serialize/deserialize from/to the compressed format. This ensures API safety by requiring that the library check each deserialized group element for validity.

When we split a secret, we need share indices so that we can recover it. The method by which we derive these shares needs to be figured out. Presumably, it can be done similarly to how it currently works in PyUmbral.

Ideally, it can be done in such a way that even if m shares get leaked, it will not be possible without Alice's key or similar.

The Python module of NuBLS needs a Domain Separation Tag when calling hash_message. This should be a string probably from the BLS Signature draft spec.

Note that this issue is tied with #15 where this DST may have to be defined in the PyO3 wrapper.

The title is self-explanatory; rust-nubls needs to finish the implementation of ThresholdSignature.

Since rust-nubls currently lacks a hash_to_curve API (see #1) , we need to use the hash_to_curve API in the py-ecc library.
To do this, we need to have the py-ecc hash_to_curve get called in the Python nubls module and then pass the serialized output via the PyO3 ffi interface to rust-nubls.

This should hold us over for an MVP until we get a proper hash_to_curve implementation and modify the rust-nubls API accordingly.

Minimal code example:

use nubls::{PrivateKey};
use std::num::ParseIntError;

fn main() {
    let scalar_bytes= decode_hex("575f1e8e02e173ef6b006b8255f5444585b19071f5ccd9811be6b40f1e5618c9").unwrap();
    let pk = PrivateKey::from_bytes(&scalar_bytes[..]);
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DecodeHexError {
    OddLength,
    ParseInt(ParseIntError),
}
impl From<ParseIntError> for DecodeHexError {
    fn from(e: ParseIntError) -> Self {
        DecodeHexError::ParseInt(e)
    }
}

pub fn decode_hex(s: &str) -> Result<Vec<u8>, DecodeHexError> {
    let mut result= String::new();
    if s.len() % 2 != 0 {
        result.push_str(&format!("{:0>width$}", s, width = s.len()+1).as_str());
    } else{
        result.push_str(s);
    }
    (0..result.len())
        .step_by(2)
        .map(|i| u8::from_str_radix(&result[i..i + 2], 16).map_err(|e| e.into()))
        .collect()
}

Stack

     Running `target/debug/nubls_test`
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `0`,
 right: `1`', /home/vadym/.cargo/registry/src/github.com-1ecc6299db9ec823/subtle-2.4.0/src/lib.rs:550:9
stack backtrace:
   0:     0x55be6dc21930 - std::backtrace_rs::backtrace::libunwind::trace::hdcf4f90f85129e83
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/../../backtrace/src/backtrace/libunwind.rs:90:5
   1:     0x55be6dc21930 - std::backtrace_rs::backtrace::trace_unsynchronized::h2669e30cb82f6732
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x55be6dc21930 - std::sys_common::backtrace::_print_fmt::hfbda19e17f6db318
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/sys_common/backtrace.rs:67:5
   3:     0x55be6dc21930 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h1a8751bf59281272
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/sys_common/backtrace.rs:46:22
   4:     0x55be6dc3bd1f - core::fmt::write::h7aa6cd0067dca82a
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/core/src/fmt/mod.rs:1094:17
   5:     0x55be6dc20205 - std::io::Write::write_fmt::hd7dd3a1df9b6befb
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/io/mod.rs:1580:15
   6:     0x55be6dc2357b - std::sys_common::backtrace::_print::h551e9ec8a9fa8106
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/sys_common/backtrace.rs:49:5
   7:     0x55be6dc2357b - std::sys_common::backtrace::print::ha4b1c5e95fa040b3
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/sys_common/backtrace.rs:36:9
   8:     0x55be6dc2357b - std::panicking::default_hook::{{closure}}::h0b34c9ab7fb9f857
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:208:50
   9:     0x55be6dc2305d - std::panicking::default_hook::h3067e8318decd17a
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:225:9
  10:     0x55be6dc23b2d - std::panicking::rust_panic_with_hook::h81b8facc50f34daa
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:591:17
  11:     0x55be6dc23727 - std::panicking::begin_panic_handler::{{closure}}::ha376ab85d95a000e
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:497:13
  12:     0x55be6dc21dec - std::sys_common::backtrace::__rust_end_short_backtrace::h6795c8afdd1a77e6
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/sys_common/backtrace.rs:141:18
  13:     0x55be6dc23689 - rust_begin_unwind
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:493:5
  14:     0x55be6dc06dd1 - core::panicking::panic_fmt::hbe99dddd3092ba3c
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/core/src/panicking.rs:92:14
  15:     0x55be6dc3afb8 - core::panicking::assert_failed_inner::h4fdb1013d187f202
  16:     0x55be6dc0cffa - core::panicking::assert_failed::h50a028724598e99d
                               at /home/vadym/snap/rustup/common/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/panicking.rs:117:5
  17:     0x55be6dc0d2be - subtle::CtOption<T>::unwrap::h14be526285d46bbd
                               at /home/vadym/.cargo/registry/src/github.com-1ecc6299db9ec823/subtle-2.4.0/src/lib.rs:550:9
  18:     0x55be6dc0c7a9 - nubls::keys::PrivateKey::from_bytes::he7eac9e9726e43e3
                               at /home/vadym/.cargo/registry/src/github.com-1ecc6299db9ec823/nubls-0.1.0/src/keys.rs:92:20
  19:     0x55be6dc076fe - nubls_test::main::hd26c91ea8c2adb98
                               at /home/vadym/WebstormProjects/nubls_test/src/main.rs:6:14
  20:     0x55be6dc0bbeb - core::ops::function::FnOnce::call_once::hf4759dd1853b5dc0
                               at /home/vadym/snap/rustup/common/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
  21:     0x55be6dc07c1e - std::sys_common::backtrace::__rust_begin_short_backtrace::h0b621b637b10955a
                               at /home/vadym/snap/rustup/common/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
  22:     0x55be6dc08071 - std::rt::lang_start::{{closure}}::h53231fb7f07ae317
                               at /home/vadym/snap/rustup/common/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:66:18
  23:     0x55be6dc23f2a - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once::h3b8c329143d7638a
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/core/src/ops/function.rs:259:13
  24:     0x55be6dc23f2a - std::panicking::try::do_call::h4b72c261b4eefc1b
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:379:40
  25:     0x55be6dc23f2a - std::panicking::try::h703d31b7896cbd49
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panicking.rs:343:19
  26:     0x55be6dc23f2a - std::panic::catch_unwind::h37cad9b35388a915
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/panic.rs:431:14
  27:     0x55be6dc23f2a - std::rt::lang_start_internal::hab5a8a909af4f90e
                               at /rustc/42816d61ead7e46d462df997958ccfd514f8c21c/library/std/src/rt.rs:51:25
  28:     0x55be6dc08050 - std::rt::lang_start::h45652820d41ad91b
                               at /home/vadym/snap/rustup/common/rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5
  29:     0x55be6dc07c0c - main
  30:     0x7f91829970b3 - __libc_start_main
  31:     0x55be6dc074ce - _start
  32:                0x0 - <unknown>

Process finished with exit code 101

Explore implementing distributed key generation on rust-nubls. See this paper for details: https://sci-hub.se/https://link.springer.com/chapter/10.1007%2F3-540-48910-X_21

It would be helpful to include research into use cases for DKG, as well (cc @arjunhassard).

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.

Should also allow the creation of re-signing keys in advance for redundant/failover validator machines that are not yet spun up

We need Python tests for the PyO3 wrapper that test the core functionalities and lifecycle of the Python NuBLS API.