I rebased this branch on my validation-2 (#59) already, and can rebase this branch again on the master of this repo if/when that PR is merged.

This PR updates formatting throughout the crate based on the latest Clippy version (as of a few days ago). I think the improvements are good.

I also added Clippy to Travis, and made a few changes that should make the Travis builds go faster, including use of the cache, and fast_finish, so we don't have to wait for the nightly build to finish to get the overall result, since that build is allowed to fail anyway.

Nothing big here: Just changes I did locally while skimming through the code: std::process::exit is stable now and one or two typos. Feel free to ignore if not useful. Looks like a nice job btw :+1:.

The Build fail due to merkle v1.10.0:

   Compiling merkle v1.10.0
error: failed to run custom build command for `merkle v1.10.0`
process didn't exit successfully: `/Users/kaller/IdeaProjects/dssaa_s/target/debug/build/merkle-f78177df6eb47b03/build-script-build` (exit code: 101)
--- stderr
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Os { code: 2, kind: NotFound, message: "No such file or directory" }', src/libcore/result.rs:1009:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

Added

• Introduce split_secret_rng() which allows for use of user-provided random number generators.
• Depend on rand version 0.4.2.

Changed

• Make internal methods generic over R: Rng.

Status

Having shown an earlier version of this branch to @romac, I'm now putting this up for public review. It is still a work in progress, but the main components are in place.

Description

This PR implements most of a complete interface for incrementally computing a secret using barycentric Lagrange interpolation. In cases where not all shares are available at once, it is still possible to start interpolating the secret polynomial, such that when threshold shares are finally present, the final computation time (i.e., the time between receiving the threshold-th share and the secret being recovered) is much smaller. This will be especially noticeable when the secret is very long, or the threshold is very high. (E.g., in Sunder, shares are entered one at a time and this could be useful.)

It is still missing it's highest-level, public-facing interface that would accept &[String]s (shares in string form), parse them, and return Recovery objects. Recovery objects store and update the state of the partially recovered secret.

Under the hood, Recovery objects store:

1. barycentric weights and diffs computed evaluate the polynomial.
2. The ids processed so far.
3. The threshold.
4. The secret length (slen).
5. Optionally, the root_hash of the Merkle tree (i.e., the public key the shares were signed with).
6. Optionally, the secret.

1-3 are needed to correctly compute the secret, and know when it's ready. Since there would be a lot of redundant data among the BarycentricWeightss if we were to store the ids and threshold in that struct, we depend on Recovery to store and update the ids, and provide new points to update each BarycentricWeights. When threshold shares have been processed, the secret, which is initialized at None, is automatically computed (Some<Vec<u8>>), and can then be retrieved with get_secret.

2-5 are needed for validation of the shares and verification of the signatures. If verify_signatures is true Recovery::new() will set the the root_hash to the root hash of the initial share(s) used to create the Recovery object, and this root_hash value is automatically used during subsequent Recover::updates to ensure consistency among the signatures. Likewise, during updates share validation "picks up where it left off" by passing the already processed ids, along with the new shares to be validate, to the new function validate_additional_signed_shares in order to prevent duplicate shares from being processed.

Thoughts/ ideas:

I'm not sure if it is necessary to create {to,from}_string methods for Recovery in order to make a functional interface in regards to the node library. If it is not necessary, I assume this means the node interface can act on an Recovery object in memory, without it having to be in a printable or JS-intelligible/interoperable form. In this case, one could simply wait until threshold shares have been interpolated, and then call get_secret() on the Recovery object, which will return a Result<Vec<u8>> (just as does Recovery::recover_secret, which, though changed under the hood, provides the same interface that SSS::recover_secret used to).

Whether or not it such methods are necessary, they may be useful. The idea being that you could partially interpolate a secret from less than threshold shares, storing a result a fraction of the size the combined shares (and maybe more importantly/ conveniently, as a single piece of data), and then later interpolate more shares to get the final result. To do this we'd need some way to serialize an Recovery for long-term storage (string, or binary for that matter). As a use case, imagine you want to recover a secret using Sunder, and you expect to get shares in person over the course of some time. A useful feature would be the ability to save to disk a serialized Recovery object, so that you don't have to save each share to disk, and then enter them all in once there are sufficient. Good UI would keep you updated on how many shares you've interpolated so far and how many more are needed to fully recover the object using the shares_interpolated() and shares_needed() methods. Especially when recovering multiple secrets at a time in an incremental effort, a good UI built around this functionality could save you a lot of organizational effort and help prevent mistakes.

TODO

• Improve documentation and code comments.
• Add a lot more tests.
• Add a few more benchmarks.
• Create highest-level (user) interface that takes &[String].
  • Protobuf/ {to,from_string} for Recovery?
• Catch and modify any InconsistentSignature errors to correct the ids argument when S::verify_signature is called in validate::validate_additional_signed_shares before re-raising (or whatever the Rustaceans call this) with match and whatever else from the error_chain crate (see this commit message).

Some changes and improvements to the validation process and error messaging. The commits are pretty granular changes, and if it isn't really obvious why a certain change was made, the corresponding commit message should have a detailed justification for said change.

just for fun.

i was checking out the library and thought this was missing if anyone wanted to quickly play around and see what the outputs looked like.

Implements barycentric Lagrange interpolation. Uses algorithm (3.1) from the paper "Polynomial Interpolation: Langrange vs Newton" by Wilhelm Werner to find the barycentric weights, and then evaluates at Gf256::zero() using the second or "true" form of the barycentric interpolation formula.

I also earlier implemented a variant of this algorithm, Algorithm 2, from "A new efficient algorithm for polynomial interpolation," which uses less total operations than Werner's version, however, because it uses a lot more multiplications or divisions (depending on how you choose to write it), it runs slower given the running time of subtraction/ addition (equal) vs multiplication, and especially division in the Gf256 module.

The new algorithm takes n^2 / 2 divisions and n^2 subtractions to calculate the barycentric weights, and another n divisions, n multiplications, and 2n additions to evaluate the polynomial*. The old algorithm runs in n^2 - n divisions, n^2 multiplications, and n^2 subtractions. Without knowing the exact running time of each of these operations, we can't say for sure, but I think a good guess would be the new algorithm trends toward about 1/3 running time as n -> infinity. It's also easy to see theoretically that for small n the original lagrange algorithm is faster. This is backed up by benchmarks, which showed for n >= 5, the new algorithm is faster. We can see that this is more or less what we should expect given the running times in n of these algorithms.

To ensure we always run the faster algorithm, I've kept both versions and only use the new one when 5 or more points are given.

Previously the tests in the lagrange module were allowed to pass nodes to the interpolation algorithms with x = 0. Genuine shares will not be evaluated at x = 0, since then they would just be the secret, so:

1. Now nodes in tests start at x = 1 like scheme::secret_share deals them out.
2. I have added assert statements to reinforce this fact and guard against division by 0 panics.

This meant getting rid of the evaluate_at_works test, but interpolate_evaluate_at_0_eq_evaluate_at provides a similar test.

Further work will include the use of barycentric weights in the interpolate function.

A couple more interesting things to note about barycentric weights:

• Barycentric weights can be partially computed if less than threshold shares are present. When additional shares come in, computation can resume with no penalty to the total runtime.
• They can be determined totally independently from the y values of our points, and the x value we want to evaluate for. We only need to know the x values of our interpolation points.

Supersedes #48. The functional style used in this implementation of Horner's method is more elegant, faster, and does not change the function signature of encode_secret_byte.

Horner's method is an algorithm for calculating polynomials, which consists of transforming the monomial form into a computationally efficient form. It is pretty easy to understand: https://en.wikipedia.org/wiki/Horner%27s_method#Description_of_the_algorithm

This implementation has resulted in a noticeable secret share generation speedup as the RustySecrets benchmarks show, especially when calculating larger polynomials:

Before: test sss::generate_1kb_10_25 ... bench: 3,104,391 ns/iter (+/- 113,824) test sss::generate_1kb_3_5 ... bench: 951,807 ns/iter (+/- 41,067)

After: test sss::generate_1kb_10_25 ... bench: 2,071,655 ns/iter (+/- 46,445) test sss::generate_1kb_3_5 ... bench: 869,875 ns/iter (+/- 40,246)

In the the SSS::secret_share function, the author clearly intended to make col_in an array of threshold bytes, but put a comma where the semi-colon should go in the vec! macro. Thus the code always generates just a single coefficient instead of threshold - 1 coefficients for our secret polynomial. So regardless of how high the threshold is set two shares are enough to uncover the secret.

This did not cause an error in the secret recovery code because of the fundamental uniqueness of the Lagrange polynomial: regardless of the number of nodes (shares) presented in excess of k + 1 for a k degree polynomial, Langrange interpolation finds the unique polynomial of degree k.

Here is an illustration of the problem:

extern crate rand;
use rand::{OsRng, Rng};

fn main() {
    let threshold: u8 = 6;
    let mut col_in = vec![0u8, threshold];
    let mut osrng = OsRng::new().unwrap();
    osrng.fill_bytes(&mut col_in[1..]);
    println!("{:?}", col_in);

    let threshold: u8 = 6;
    let mut col_in = vec![0u8; threshold as usize];
    osrng.fill_bytes(&mut col_in[1..]);
    println!("{:?}", col_in);
}

[0, 234]
[0, 196, 181, 63, 217, 112]

Hi,

I've added a few lints to clean up the code. Tests still pass. The most notable change is that I have broken the public API, recover_secret now takes a slice rather than a Vec.

A couple more things that I didn't fix but that should be addressed:

• The protobuf method make_repeated_bytes_accessor is deprecated. Any reason why that is still used?
• In wrapped_secrets.rs:31 there is a weird for loop over an Option<String>. Is that on purpose? What are you trying to do? I think you're better off with if let Some(mt)
• I didn't want to ruin the whole history and send a million lines PR, but you should really consider to format the code using rustfmt

One last thing, are you planning a release of the signed shares stuff?

Looks like an awesome project, but unsure if this is being actively maintained, but it seems it is not bv the looks of open pull requests awaiting being merged such as https://github.com/SpinResearch/RustySecrets/pull/77.

Any input on this would be appreciated.

Thank you.

Fixes #71 .

ring 0.12 has been yanked. merkle_sigs 1.7 is required for compatibility with ring 0.16. These require newer rust (not totally sure version), so bumping rust to the latest, which required a small fix for E0502.

After #74 is merged. #74 will fix #71, and is a breaking change (since it includes semver breaking updates of multiple dependencies), so it will have to be version 0.3.0 instead of version 0.2.3.

The error I get:

error: multiple packages link to native library `ring-asm`, but a native library can be linked only once

package `ring v0.12.1`
    ... which is depended on by `lamport_sigs v0.5.0`
    ... which is depended on by `merkle_sigs v1.5.0`
    ... which is depended on by `rusty_secrets v0.2.2 (file:///xxx)`
    ... which is depended on by `foo v0.1.0 (file:///xxx)`
links to native library `ring-asm`

package `ring v0.13.2`
    ... which is depended on by `merkle v1.10.0`
    ... which is depended on by `merkle_sigs v1.5.0`
    ... which is depended on by `rusty_secrets v0.2.2 (file:///xxx)`
    ... which is depended on by `foo v0.1.0 (file:///xxx)`
also links to native library `ring-asm`

I've submitted a PR to update lamport_sigs: https://github.com/SpinResearch/lamport_sigs.rs/pull/15

I've tried to do the same for merkle_sigs, but the current master depends on a different version of merkle.rs that I couldn't build on my system due to a build failure in a dependency: https://github.com/SpinResearch/merkle.rs/issues/47