Implement no_std support

[xoloki]

This change implements no_std support for the bulletproofs crate. The changes are mostly mechanical. This is the culmination several PRs worth of work, with changes to curve25519 and merlin crates already merged and released.

It was necessary to make minor modifications to some APIs, particularly in regards to RNGs. As discussed by @isislovecruft in #275, the APIs in this change are backwards compatible for those building the crate in std mode. So current users of the bulletproofs crate will see no change. Users wishing to build bulletproofs in no_std mode will need to call the new *_with_rng prove and verfiy functions, and pass in a RNG.

This change is based on the main branch rather than the develop branch. This is because the main branch in the dalek repo has several changes that are not in the develop branch. This made rebasing my change on the upstream develop branch to be problematic.

[oleganza]

This looks cool. Will check in more detail tomorrow.

[hdevalence]

It looks like one of the CI failures is just because of rustfmt changes that haven't been applied to the codebase yet; I can make a separate change that fixes them so that this branch can be merged cleanly on top of the fixed style.

[arthurgreef]

Hi - I pulled the branch but I cannot bet a clean build. Can you provide me with you build command? Is is cargo build --no-default-features --features alloc? Thanks.

[xoloki]

Hi - I pulled the branch but I cannot bet a clean build. Can you provide me with you build command? Is is cargo build --no-default-features --features alloc? Thanks.

I pushed a change to the branch that forces the rand dependency to 0.6, which appears to fix this. Your cargo build command will now work.

I was testing the no_std support in an application that used bulletproofs in no_std mode, so it is likely that some other dependency was already requesting 0.6 and cargo's dependency resolution was never actually using a 0.5 rand.

[xoloki]

It looks like one of the CI failures is just because of rustfmt changes that haven't been applied to the codebase yet; I can make a separate change that fixes them so that this branch can be merged cleanly on top of the fixed style.

The badly formatted code was all in places that I changed, so I went ahead and fixed my branch @hdevalence

[xoloki]

All checks are now passing.

[arthurgreef]

We are using cargo-nono to see if the libraries reference std and are noticing that the dependencies do. I that expected? Thanks.

curve25519-dalek: FAILURE

• Source code contains an explicit use std:: statement. --> src/backend/vector/ifma/edwards.rs
  • Source code contains an explicit use std:: statement. --> src/prelude.rs clear_on_drop: SUCCESS subtle: SUCCESS byteorder: SUCCESS digest: FAILURE
• Source code contains an explicit use std:: statement

[hdevalence]

Re: curve25519-dalek failure, it might be because the version with no_std fixes hasn't been released yet, I can check and do a new release if not. There's a security audit soon-to-be-released for these libraries with some minor issues so we might batch no_std fixes into those fixes instead of doing two at once.

I updated the develop branch so there should not be any more divergence between the main and develop branches.

[hdevalence]

Hi all, recent changes to Rust nightlies broke the build (by changing the path root for doc(include) path specifiers), so we had to update the develop branch and release 1.0.4 which works on current nightlies. The current develop branch is now back in sync with the main branch, is ready for more changes to be merged in, and won't have any more drastic changes (except to the R1CS code).

[xoloki]

Okay @hdevalence I rebased on upstream/develop, force pushed the branch, and updated the PR to point to develop. Let me know if you want me to do anything else.

[xoloki]

@arthurgreef cargo-nono operates by parsing the source, then analyzing the AST tokens to look for stuff that seems problematic. It is not particularly reliable, and frequently returns false positives. For my merlin PR I actually ended up patching cargo-nono to get it to stop returning false positives.

In this case, it appears that cargo-nono is not properly identifying how curve25519 is using preprocessor directives to selectively enable the use std:: statements. This seems to be a result of the multi-leveled modular structure of the curve25519 crate.

While I was able to easily patch cargo-nono for the merlin PR, there appears to be no way to easily patch it for this PR to remove the false positive on curve25519.

[xoloki]

All tests are now passing @hdevalence.

[hdevalence]

Great! Making the R1CS backend depend on std is fine, it's less clearly useful in an embedded context and the code is under a lot more change than the rangeproof code.

Instead of adding a dependency on cfg_if, it's possible to annotate the import, module, etc. statements directly, e.g., instead of

cfg_if::cfg_if! {
    if #[cfg(feature = "alloc")] {
        extern crate alloc;
        use alloc::vec::Vec;
    }
}

the attributes can be added to the particular statements:

#[cfg(feature = "alloc")]
extern crate alloc;
#[cfg(feature = "alloc")]
use alloc::vec::Vec;

I think that all of the config statements can be handled this way, I don't think there's a need for cfg_if.

[burdges]

Just fyi, I noticed this does not work

#[cfg(feature = "alloc")]
if foo() { bar() }

while this does work

#[cfg(feature = "alloc")]
{ if foo() { bar() } }

I'm not sure why, but also not really sure what good cfg_if ever does.

[xoloki]

Ok @hdevalence I removed cfg_if and replaced all usage. I also got the vec! macro from alloc::vec and reverted all the macro removal changes, so the diff is much smaller.

Let me know if you need anything else.

[xoloki]

Yeah @burdges I really don't know what the point of cfg_if is either, but the first no_std compliant code I looked at used it so I've always done so. Maybe recent rust modified the #cfg directive so cfg_if is no longer necessary? Either way, I removed it.

[hdevalence]

Great! I tested depending on the bulletproofs crate from a scratch library, and building that library in no_std mode (to prevent criterion or dev-dependencies from re-enabling std), and ran into a few hitches:

• The clear_on_drop crate should probably be selected as

  clear_on_drop = { version = "0.2", default-features = false, features = ["nightly"] }

• The rand crate should be an optional dependency, enabled by the std feature of Bulletproofs:

  rand = { version = "0.6", default-features = false, optional = true }
  ...
  std = ["rand", "rand/std", ...

• The crate has an alloc feature that enables the imports of all of the alloc-related functionality. But the crate can't work without that functionality, so compiling with --no-default-features fails. Since we're not going to have an alloc-free implementation, we know we'll always need alloc, so I think it would be better to remove the alloc feature and use alloc unconditionally, so that --no-default-features selects no_std + alloc, instead of breaking the build.

[xoloki]

Ok @hdevalence I fixed the clear_on_drop and rand dependencies as you wanted.

However, I'm not sure how to have --no-default-dependencies always select no_std + alloc, can you point me to something that does this?

[xoloki]

I could do something like this @hdevalence

#![cfg_attr(not(feature = "std"), feature(alloc))]

but wouldn't I still need to define a Cargo.toml alloc feature so I could chain it down to rand_core, serde, and curve25519?

[xoloki]

BTW the CI failures appear to be spurious, it was just failure to connect to github:

fatal: unable to access 'https://github.com/dalek-cryptography/bulletproofs.git/': Failed to connect to github.com port 443: Connection timed out
The command "eval git clone --depth=50 https://github.com/dalek-cryptography/bulletproofs.git dalek-cryptography/bulletproofs " failed. Retrying, 2 of 3.

[xoloki]

Okay @hdevalence I got rid of the alloc feature and just used alloc everywhere. Building without default features just works now.

Let me know if you want me to do anything else.

[xoloki]

All tests passing now @hdevalence

[hdevalence]

Hey @xoloki, this looks great, I would like to merge it, thanks for all this work!

I was doing a final pass over the combined changes and I spotted something I should have noticed before, but didn't: the functions in the aggregation module that were changed to take RNG parameters are part of the public API of the crate, so they can't be changed without breaking stability. I'm sorry I didn't spot it before and that there's another round of back-and-forth, but I think that that is the only thing left.

[xoloki]

No worries, thanks for all your help getting this in shape.

[xoloki]

Ok @hdevalence I fixed the public API to be backwards compatible in std mode, and renamed the nostd public API elements _with_rng.

Let me know if you need any more changes.

[hdevalence]

I have a cherry-pick'able commit on a copy of this branch (https://github.com/hdevalence/bulletproofs/commit/41917811c2eb856c5846c75ebdcc39e78488d687 ) that undoes the changes to the test code, so that the test code continues to use the previous aggregation API. This way we test that the previous API still works correctly.

[xoloki]

I have a cherry-pick'able commit on a copy of this branch (hdevalence@4191781 ) that undoes the changes to the test code, so that the test code continues to use the previous aggregation API. This way we test that the previous API still works correctly.

The cherry has been picked, thanks!

[xoloki]

Hi @hdevalence, is there anything else you need from me? It would be super helpful if we can get this merged by the end of the month, our auditors would be much happier reviewing an upstream release rather than a fork and a PR.

[hdevalence]

Hey @xoloki -- I was on vacation so I missed this; I'll try to get this merged before the end of the week!

[xoloki]

Excellent, thanks @hdevalence!

[hdevalence]

Planning to get this merged this afternoon!

[hdevalence]

Hey @xoloki, I think I'm out of time to do a release for this today but I will do it at the beginning of next week. Sorry that this took so long and thanks so much for your work on this :)

[xoloki]

Thanks for the merge! Next week is totally fine for a release.