Remove `rand` dependency from `bdk`

[rustaceanrob]

Description

WIP towards removing rand #871

The rand dependency was imported explicitly, but rand is also implicitly used through the rand-std feature flag on bitcoin.

Notes to he reviewers

Updated:

rand was used primarily in two parts of bdk. Particularly in signing and in building a transaction.

Signing:

• Used implicitly in sign_schnorr, but nowhere else within signer.

Transaction ordering:

• Used to shuffle the inputs and outputs of a transaction, the default
• Used in the single random draw as a fallback to branch and bound during coin selection. Branch and bound is the default coin selection option.

See conversation for proposed solutions.

Changelog notice

• Remove the rand dependency from bdk

Checklists

All Submissions:

• [x] I've signed all my commits
• [x] I followed the contribution guidelines
• [x] I ran cargo fmt and cargo clippy before committing

New Features:

• [ ] I've added tests for the new feature
• [ ] I've added docs for the new feature

Bugfixes:

• [x] This pull request breaks the existing API
• [x] I've added tests to reproduce the issue which are now passing
• [x] I'm linking the issue being fixed by this PR

[LLFourn]

Description

WIP towards removing rand #871

The rand dependency was imported explicitly, but rand is also implicitly used through the rand-std feature flag on bitcoin. In this PR, I used the bitcoin::secp256k1::rand re-export from bitcoin to remove the explicit import of rand.

Per my understanding, the rand-std feature flag is used for signing transactions, and was being used outside of tx_builder and coin_selection. I wanted to open up some discussion on if there should be additional effort to remove rand-std as a feature flag from bitcoin, since rand is brought in there anyway.

Good question. I think we want to remove the dependency on the bitcoin feature too because otherwise we have the same problem with wasm. If we want randomness during signing (it's a good default), then we should make the caller pass in an Rng and call: sign_schnorr_wth_aux_rand rather than the one that needs the rand feature. We could also make randomness here optional (deterministic by default) by adding a field to SignOptions to pass in an Option<&mut R> where R: RngCore

Notes to the reviewers

While experimenting with this, allowing the user to pass in an impl RngCore to finish a transaction resulted in redundant impl RngCore arguments for algorithms that implement the coin selection trait. I just want to confirm tx.finish(&mut rng) is the type of API change that is worth removing the rand-std feature flag from bitcoin before proceeding.

Yeah, I think it's worth it tbh if that's what it comes to. Annoying thing is that not every TxBuilder ordering needs randomness. Shuffling could be done outside of building in theory but that would require an extra step by the user to engage it.

[rustaceanrob]

Thanks, will keep chipping at this

[rustaceanrob]

If we want randomness during signing (it's a good default), then we should make the caller pass in an Rng and call: sign_schnorr_wth_aux_rand rather than the one that needs the rand feature. We could also make randomness here optional (deterministic by default) by adding a field to SignOptions to pass in an Option<&mut R> where R: RngCore

After thinking about this I am a little confused at how the sign_schnorr family of functions works. sign_schnorr_wth_aux_rand makes sense and is easy enough to implement with SignOptions. sign_schnorr_no_aux_rand is tripping me up. How is it possible to sign with no auxiliary random entropy? Is there something going here with a deterministic nonce based on the secret and the message? In the case where the user signs with SignOptions::default(), which I imagine most of the time, what is the implication for repeated nonces?

Another aside, to shuffle inputs and outputs, and I think in BnB, an extension trait on slices from rand was used to call shuffle on Vec<T>. A way for me to add this functionality back was to use a crate called shuffle, which allows slice shuffling with any impl RngCore. So far I am not a fan of it, as it adds new possibility of errors and another dependency. I will have to home brew a shuffle algorithm to avoid using the crate shuffle. Might take some time and a more careful review.

[LLFourn]

If we want randomness during signing (it's a good default), then we should make the caller pass in an Rng and call: sign_schnorr_wth_aux_rand rather than the one that needs the rand feature. We could also make randomness here optional (deterministic by default) by adding a field to SignOptions to pass in an Option<&mut R> where R: RngCore

After thinking about this I am a little confused at how the sign_schnorr family of functions works. sign_schnorr_wth_aux_rand makes sense and is easy enough to implement with SignOptions. sign_schnorr_no_aux_rand is tripping me up. How is it possible to sign with no auxiliary random entropy? Is there something going here with a deterministic nonce based on the secret and the message?

Yes. See BIP340. The secret and the message are hashed together if the aux rand bytes are null so that' swhat no_aux_rand is doing.

In the case where the user signs with SignOptions::default(), which I imagine most of the time, what is the implication for repeated nonces?

There are no implications in most scenarios. People making a Bitcoin HSM using BDK that needs to be robust against an attacker who can inject faults into the power supply or something should look for the option and add randomness. It'd be nice if we could easily make it the default or nudge people towards. We'll have an opportunity when we redesign transaction building. But for now making it optional is fine.

Another aside, to shuffle inputs and outputs, and I think in BnB, an extension trait on slices from rand was used to call shuffle on Vec<T>. A way for me to add this functionality back was to use a crate called shuffle, which allows slice shuffling with any impl RngCore. So far I am not a fan of it, as it adds new possibility of errors and another dependency. I will have to home brew a shuffle algorithm to avoid using the crate shuffle. Might take some time and a more careful review.

Definitely shouldn't add a dependency. I think rolling your own is the right thing to do in this case. I wonder why we would be shuffling things in BnB but hopefully that goes away soon.

[rustaceanrob]

Definitely shouldn't add a dependency. I think rolling your own is the right thing to do in this case. I wonder why we would be shuffling things in BnB but hopefully that goes away soon.

I vastly overestimated the difficulty. No issues on the shuffling algo.

There are no implications in most scenarios. People making a Bitcoin HSM using BDK that needs to be robust against an attacker who can inject faults into the power supply or something should look for the option and add randomness. It'd be nice if we could easily make it the default or nudge people towards. We'll have an opportunity when we redesign transaction building. But for now making it optional is fine.

I am thinking of a few ways to go about this. There can be an Option<[u8; 32]> called aux_rand on SignOptions, but I assume this will be frequently None. Another approach, easiest for the bindings, would be to make an explicit argument on sign named aux_rand that takes an Option<[u8; 32]> that forces the user to opt out of adding randomness by at least acknowledging they are opting out. Likewise, an Option<Box<dyn RngCore>> or even a forced &mut impl RngCore could be passed to sign. I like this approach, but bindings would have to alter this API I would imagine.

[rustaceanrob]

Updated: The PR now uses Option<[u8; 32]> as a SignOptions for additional entropy on Schnorr signatures. While I think this is the lowest hanging fruit so-to-speak, I think it would be somewhat hard to find for users. Adding a generic over SignOptions propagates all the way up to Wallet, adding a generic. Removing generics from the wallet is mentioned as an issue (#1363), so I don't think this is much of an option.

SignOptions could contain a Option<Box<dyn RngCore>>, if the entropy should remain as an option for users.

I like the idea of having a user pass an Option<R> where R: RngCore when calling sign on wallet. They would have to explicitly opt out of using additional randomness, whereas they can passively ignore this feature if it is a member of SignOptions.

On building transactions, using randomness depends on the TxOrdering and if the user selected the single random draw coin selection algorithm. I added a mandatory &mut R to finish, but I would like to hear other suggestions here!

cc @ValuedMammal

[LLFourn]

Updated: The PR now uses Option<[u8; 32]> as a SignOptions for additional entropy on Schnorr signatures. While I think this is the lowest hanging fruit so-to-speak, I think it would be somewhat hard to find for users. Adding a generic over SignOptions propagates all the way up to Wallet, adding a generic. Removing generics from the wallet is mentioned as an issue (#1363), so I don't think this is much of an option.

Option<[u8;32]> being passed down to the schnorr signing function is not really using it in the right way. Each call is meant to have fresh randomness. I think you can add a generic to SignOptions without it going on Wallet. You're idea of doing a Box<dyn RngCore> is also fine.

TBH I'm thinking we should just drop randomness for the schnorr signing function for now (use the no_aux_rand function). I don't imagine BDK's PSBT signing being used in a context where synthetic nonce's theoretical benefits will translate into real world security. It is desirable to have the ability but I imagine all this stuff being re-imagined in the future.

[rustaceanrob]

TBH I'm thinking we should just drop randomness for the schnorr signing function for now (use the no_aux_rand function).

I would prefer this. Ultimately I think this is a feature that can be handled outside of this PR.

I thought longer about input/output shuffling and greater concept of TxOrdering. The TxOrdering the user selects should determine whether or not there should be randomness involved. To reflect this I decided to add Box<dyn RngCore> on the Shuffle enumeration. An Option<Box<dyn RngCore>> on the TxParams does not properly couple the TxOrdering and the source for randomness, and would lead to confusing error cases when the user does not provide RngCore. Due to this change, TxOrdering is unable to keep Shuffle as the Default enumeration. Rather than use Untouched as a default, I do not think this enum should derive Default.

From the docs:

Sometimes, you want to fall back to some kind of default value, and don’t particularly care what it is.

I would argue we do care what the ordering is for BDK user transactions as there are privacy implications, and the user should hand select the TxOrdering. I demonstrated in all example crates how to use Shuffle.

Along the same vein, I took the opportunity to try to resolve #534 by deprecating BIP69 lexicographical sorting. As discussed in that thread, BIP69 does not preserve privacy as intended. Likewise, I added a Custom enumeration for the user to provide arbitrary sorting functions for inputs and outputs.

I referenced the coin_selection crate for how the coin selection process might look in the future. It looks like single random draw would not be implemented, as it would require a dependency. I removed single random draw for now, but there should be a deterministic fallback (i.e. largest first), as there are high failure rates when trying to create 0 change transactions. Either that, or more consideration into adding rand_core in future coin selection.

The TxOrdering enum for reference:

pub enum TxOrdering {
    /// Randomized
    Shuffle(Box<dyn RngCore>),
    /// Unchanged
    Untouched,
    /// BIP69 / Lexicographic
    #[deprecated = "BIP69 does not improve privacy as was the intention of the BIP"]
    Bip69Lexicographic,
    /// A custom ordering of inputs and outputs
    Custom {
        /// The custom function to order the inputs of the transaction
        input_ordering: Box<dyn Fn(&TxIn, &TxIn) -> core::cmp::Ordering>,
        /// The custom function to order the outputs of the transaction
        output_ordering: Box<dyn Fn(&TxOut, &TxOut) -> core::cmp::Ordering>,
    },
}

[ValuedMammal]

Here's how I think we can keep single random draw as a fallback to BNB: don't implement SRD on the type BranchAndBoundCoinSelection directly, but instead pull it out of the impl block and make it pub(crate). Then call it directly in Wallet::create_tx in the case that BNB fails, passing roughly the same arguments. Add a parameter to create_tx called mut rng: Option<Box<dyn RngCore>> that can be used both during coin selection as well as tx ordering. Also add a parameter for the rng to the function TxOrdering::sort_tx. This lets us avoid dealing with the Default behavior of TxParams.

I was a bit skeptical of adding an argument to TxBuilder::finish because that seems like a poor design, but actually this is probably the right move considering the bulk of the logic occurs after finish is called. As an aside: given the chance, I would probably replace the name build_tx with something like Wallet::new_tx or TxBuilder::new and replace the name finish with build_tx to reflect this point. In any case, finish can then accept an argument rng: Box<dyn RngCore>, similar to what you propose, only generalized to work whenever randomness is needed. Then we add a second function finish_no_aux_rand that takes no additional arguments and passes None as the optional rng to create_tx. I'm still open to debate if you have another opinion.

[rustaceanrob]

In any case, finish can then accept an argument rng: Box<dyn RngCore>, similar to what you propose, only generalized to work whenever randomness is needed. Then we add a second function finish_no_aux_rand that takes no additional arguments and passes None as the optional rng to create_tx. I'm still open to debate if you have another opinion.

I am hesitant about finish_no_aux_rand because let's say a user has some TxOrdering::Custom and defaults to BnB. They try finish_no_aux_rand and BnB fails and throws an error because there was no RNG source. That leaves the user to investigate why BnB should have randomness at all. Why I proposed having the RngCore associated with the enum variant on TxOrdering was so the user clearly understands why randomness is occurring. To your point, it would be strange if not nonsensical to have arguments TxOrdering::Shuffle(Box<dyn RngCore> followed by some other Box<dyn RngCore> for the SRD fallback. So we are left with a general Box<dyn RngCore>. If we go this generalized approach, I would rather the user only have finish and be forced to provide the RNG so there aren't any new error cases with this PR.

Here's how I think we can keep single random draw as a fallback to BNB

Agree with this. I looked at the coin_selection crate though, and there was a zero dependency policy. In an effort of being future oriented, I'd like to confirm core_rand can be made an exception and SRD will be implemented there. If not, we should find a zero dependency (deterministic-selection) solution.

cc @evanlinjin

[ValuedMammal]

They try finish_no_aux_rand and BnB fails and throws an error because there was no RNG source.

In that case, fallback to LargestFirst. maybe simpler to just require the rng in all cases, though.

[rustaceanrob]

I exchanged a message with Murch on that. He said that would be a bad idea because they might end up grinding down their UTXO pool. LargestFirst isn't something we want to have happening in the background. I was going to go with that but got convinced otherwise

[ValuedMammal]

Seeing that it's common for our upstream deps to make rand-std a cargo feature, the idea came up that BDK should do the same, but that still leaves the question of how to obtain randomness when the feature is not enabled. I think we agree that a discussion of the optimal coin-select strategy probably belongs in a separate PR. If we were to do nothing else but try and drop the dependency on rand, I think it would look similar to what you have in this PR - while keeping SRD in the picture, since currently this is the only thing BDK knows to fallback on (even if bdk_coin_select doesn't include SRD, should that necessarily preclude the wallet from implementing it?). But if the end result is deemed awkward or unwieldy, I don't rule out possibly taking a step back to reevaluate. This is sort of the vision I have in mind:

Add the parameter rng: &mut impl RngCore in these places

• generate for GeneratableKey
• TxBuilder::finish
• Wallet::create_tx
• single_random_draw (now a standalone function)
• TxOrdering::sort_tx
• the new shuffle_slice

With a minimal approach, we simply require a user-provided rng everywhere. I don't think this interferes with the idea of custom tx ordering, nor does it create strange new error cases.

new snippet of calling coin_select from inside the function create_tx

        // Try BNB. If that fails, fallback to single random draw
        let coin_selection = match coin_selection.coin_select(
            required_utxos.clone(),
            optional_utxos.clone(),
            fee_rate,
            outgoing + fee_amount,
            &drain_script,
        ) {
            Ok(res) => res,
            Err(e) => match e {
                coin_selection::Error::InsufficientFunds { .. } => {
                    return Err(CreateTxError::CoinSelection(e));
                }
                coin_selection::Error::BnBNoExactMatch
                | coin_selection::Error::BnBTotalTriesExceeded => {
                    coin_selection::single_random_draw(
                        required_utxos,
                        optional_utxos,
                        fee_rate,
                        outgoing + fee_amount,
                        &drain_script,
                        rng,
                    )
                }
            },
        };

[LLFourn]

The plan above sounds good. As an aside I'm going to work on replacing the coin selection code with bdk_coin_select. We will probably fall back to "largest first" if BnB fails -- but in this case BnB is very unlikely to fail because it is allowed to find solutions with change. Just noting this because the problem of randomness during coin selection will go away (hopefully!).

[rustaceanrob]

This is sort of the vision I have in mind:

Will prep this for tomorrows PR review club. There is still plenty to discuss but I think we are in agreement on how this should be implemented. Thanks for the input @ValuedMammal

but in this case BnB is very unlikely to fail because it is allowed to find solutions with change

I'm interested to see how this works. Admittedly coin selection is an area I need to study up on, but relaxing BnB to find solutions with change makes randomness a non-issue as you said.

[storopoli]

Will prep this for tomorrows PR review club.

It's on Thursday no?

@rustaceanrob

[rustaceanrob]

Oops mixed it up with team meeting. Regardless of me rebasing and making these changes, we should have a discussion on feature flags for the review club

[rustaceanrob]

Updated with the notes from PR review club. Will have a few follow up PRs after this, but this ready for review.

[rustaceanrob]

What happens if someone doesn't have/bring his own PRNG? He/She can't finish the transaction builder, since we only expose finish_with_aux_rand and no more finish (no PRNG)?

In a no_std environment like embedded devices you can compile rand, in WASM you can use the getrandom build for JS, and the bindings team can just use rand. Otherwise the user is just using normal Rust builds. I am unsure how this function signature would effect downstream users at all, especially because it doesn't have to be cryptographic secure. I was going to make a separate PR to introduce a feature flag to bring back finish as a method to build transactions, but that was mostly for user convenience and shouldn't be covered here.

[storopoli]

I was going to make a separate PR to introduce a feature flag to bring back finish as a method to build transactions, but that was mostly for user convenience and shouldn't be covered here.

Yes, that was what I was recollecting. Great, agreed!

[notmandatory]

@rustaceanrob can you please rebase this one to pick up all the recent changes? Then if it's all still good please move it to ready to review and hopefully can be one of the next ones in.

[rustaceanrob]

rebased and CI passing

[notmandatory]

I added #1479 as a reminder to add back finish() and sort_tx() functions with rand when std is enabled.

[rustaceanrob]

@notmandatory was nice enough to go through the effort to make each of the public functions and methods that require an RngCore have a feature-gated alternative that uses the same naming as before. His commit is strictly better than my first commit because 1. it reduces the size of the diff and makes the changes more legible 2. would be non-breaking for the majority of users, excluding WASM. I cherry-picked it and added it to this PR, would appreciate a quick review.

[notmandatory]

Thanks for pulling in my commit @rustaceanrob, this now fixes #1479 too.