Remove BIP 69 sorting

[TheBlueMatt]

BIP 69 input+output sorting was a very bad idea from day one (it relies on the assumption that all wallets sort their inputs+outputs according to BIP 69 - something that will never happen - in order to provide privacy). It has no place in BDK. Instead, transaction input and output ordering should simply be randomized, making it much harder for a transaction classifier to sort transactions.

[LLFourn]

+1. Thanks for bringing this up. Before depreciating BIP69 I think we should make it possible to set the rng for shuffling so you still have a deterministic sorting option. I'd like this so it's still easy to have two wallets come up with the same input/output ordering.

[notmandatory]

For context BDK currently defaults to Shuffle for input and output ordering, but based on the discussion from rust-bitcoin/rust-bitcoin#810 I agree we should remove the BIP69 option.

bdk/src/wallet/tx_builder.rs

Lines 648 to 663 in b1346d4

	/// Ordering of the transaction's inputs and outputs
	#[derive(Debug, Ord, PartialOrd, Eq, PartialEq, Hash, Clone, Copy)]
	pub enum TxOrdering {
	/// Randomized (default)
	Shuffle,
	/// Unchanged
	Untouched,
	/// BIP69 / Lexicographic
	Bip69Lexicographic,
	}
	impl Default for TxOrdering {
	fn default() -> Self {
	TxOrdering::Shuffle
	}
	}

[notmandatory]

... Before depreciating BIP69 I think we should make it possible to set the rng for shuffling so you still have a deterministic sorting option. I'd like this so it's still easy to have two wallets come up with the same input/output ordering.

@LLFourn Do you need to have deterministic random sorting for testing or are there other uses for it? If only for #[cfg(test)] the sort_tx function already uses a deterministic rng , but if there are other use cases then should we add an optional rng parameter to the TxOrdering.Shuffle variant which seems kind of obtrusive.. maybe better to create a new variant of TxOrdering.ShuffleWIthRng with the extra param or something like that?

bdk/src/wallet/tx_builder.rs

Lines 665 to 691 in b1346d4

	impl TxOrdering {
	/// Sort transaction inputs and outputs by [`TxOrdering`] variant
	pub fn sort_tx(&self, tx: &mut Transaction) {
	match self {
	TxOrdering::Untouched => {}
	TxOrdering::Shuffle => {
	use rand::seq::SliceRandom;
	#[cfg(test)]
	use rand::SeedableRng;
	#[cfg(not(test))]
	let mut rng = rand::thread_rng();
	#[cfg(test)]
	let mut rng = rand::rngs::StdRng::seed_from_u64(0);
	tx.output.shuffle(&mut rng);
	}
	TxOrdering::Bip69Lexicographic => {
	tx.input.sort_unstable_by_key(|txin| {
	(txin.previous_output.txid, txin.previous_output.vout)
	});
	tx.output
	.sort_unstable_by_key(|txout| (txout.value, txout.script_pubkey.clone()));
	}
	}
	}
	}

[TheBlueMatt]

I'm not sure what @LLFourn was specifically looking for, but that makes sense - if you have some two-party protocol (like lightning, but lightning has a different, worse, way of doing this) where two nodes have to agree on a transaction and just want to exchange signatures, you need some way to sort the inputs+outputs such that they both agree, without having to bother communicating. You can do something deterministic (like BIP 69) but its much better to instead take some random secret value that both parties already have and use that to seed your RNG. Of course you have to ensure your RNG then generates deterministic output given the seed (I'm not sure if the rand crate provides that as an API guarantee or not, but its easy to write a shuffler without it).

[LLFourn]

... Before depreciating BIP69 I think we should make it possible to set the rng for shuffling so you still have a deterministic sorting option. I'd like this so it's still easy to have two wallets come up with the same input/output ordering.

@LLFourn Do you need to have deterministic random sorting for testing or are there other uses for it?

I need it for the scenario @TheBlueMatt mentioned.

You can do something deterministic (like BIP 69) but its much better to instead take some random secret value that both parties already have and use that to seed your RNG. Of course you have to ensure your RNG then generates deterministic output given the seed (I'm not sure if the rand crate provides that as an API guarantee or not, but its easy to write a shuffler without it).

Right I currently use BIP69 in https://gun.fun because it's a simple way of agreeing on an order for a dual funded transaction (privacy is not relevant here atm since tx is distinguishable for other reasons). Good point on ensuring it's API stable. Looking at the current implementation of shuffle it's 3 lines of code so should be easy enough to roll our own.

Just looking around it looks like this deterministic sorting of transactions based on secret data is something that people have been wanting: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-October/016457.html. Perhaps if the person who takes this issue feels so inspired they could come up with something that might be easily specifiable (might not be the way rand does it).

[afilini]

Agreed that we can deprecate it to show a warning that it should not be used, but I'm not sure I would remove it completely anytime soon. The way I see BDK is not just as a library to build wallets today, but also as a "swiss army knife" that can do anything. Like, if you have a 5 yr old project and you want to port it to BDK, you should be able to do that.

So in theory anything that has ever been used should be supported here (unless it's completely broken, but I don't think BIP69 is). But I agree that we should discourage new users from building something that relies on it.

For the "custom sorting" scenario, I'm wondering if instead of an Rng we could just take a "comparing" callback like the std sorting functions do, and then internally we just use that. I'm not particularly in favor or against any of the options, just wanted to remind you that this alternative exists.

[TheBlueMatt]

So in theory anything that has ever been used should be supported here (unless it's completely broken, but I don't think BIP69 is)

Right, here is where we (strongly) disagree. BIP 69 is completely and totally broken, IMO. Absent use-cases like @LLFourn's, it has absolutely no place in a Bitcoin wallet whatsoever.

[LLFourn]

Agreed that we can deprecate it to show a warning that it should not be used, but I'm not sure I would remove it completely anytime soon. The way I see BDK is not just as a library to build wallets today, but also as a "swiss army knife" that can do anything. Like, if you have a 5 yr old project and you want to port it to BDK, you should be able to do that.

So in theory anything that has ever been used should be supported here (unless it's completely broken, but I don't think BIP69 is). But I agree that we should discourage new users from building something that relies on it.

Permanent depreciation sounds like a good solution. BIP69 can be useful in some odd cases but asking you to suppress a warning if you actually find yourself in a situation where it is useful seems reasonable.

For the "custom sorting" scenario, I'm wondering if instead of an Rng we could just take a "comparing" callback like the std sorting functions do, and then internally we just use that. I'm not particularly in favor or against any of the options, just wanted to remind you that this alternative exists.

I really like this idea. Actually a custom Rng doesn't even do the whole job because you'd still need to sort everything lexically first. At the cost of doing a sha256 call per input/output you could do the following sort function:

let shared_secret = ...;
let cmp_fn = |a,b| {
    sha256(shared_secret, a).cmp(sha256(shared_secret, b))
};

This will give the same ordering for both parties if they both have shared_secret but will look random to everyone else. I think this is better than lexically sorting and then having a custom rng to shiuffle again afterwards. It's a good candidate for a replacement to BIP69 too.

[Eunoia1729]

Greetings everyone, 👋
I'd be happy to work on this issue.
I'm new to this project and I just started learning rust to contribute here. I hope this will be a good starting point for contributing.

Can I take this up ? I'll also be glad to be guided a bit.

[LLFourn]

@Eunoia1729 Go for it! Probably the best approach right now is to do what @afilini suggested and allowing a custom comparison function. So I guess this means adding a Custom variant to TxOrdering in tx_builder.rs (and deprecating BIP69). Something like:

pub enum TxOrdering {
    /// Randomized (default)
    Shuffle,
    /// Unchanged
    Untouched,
    /// BIP69 / Lexicographic
    #[derprecated = "BIP69 does not improve privacy as was the intention of the BIP"]
    Bip69Lexicographic,
    /// Provide custom comparison functions for sorting
    Custom { 
         inputs: Box<dyn Fn(&TxIn,&TxIn) -> std::cmp::Ordering>,
         outputs: Box<dyn Fn(&TxOut, &TxOut) -> std::cmp::Ordering>
     }
}

I think that makes sense but don't be surprised if you find a better way of doing it :)

[Yureien]

Hey @LLFourn, I was trying to implement it the way you suggested but that would require changing the derived traits since the current ones (Eq/Ord/Hash/Copy straight up won't work, Clone might work but would be weird, Debug will be pointless?) won't work if it's a Fn. It gets really complicated to do it that way, and I don't think it's possible without some major changes.

What if we do it like say,

wallet.build_tx()
    .ordering(TxOrdering::Custom)
    .add_input_ordering(<comparison function here>)
    .add_output_ordering(<comparison function here>)
    ....

This way, either the input or output can be added (if they aren't added, it behaves like Untouched.

[LLFourn]

@fadedcoder do we actually need those derives for anything? I wouldn't have thought so. Try removing them. If we need Clone for some reason just make it an Arc rather than a Box. Also it makes more sense for it to be dyn FnMut rathan than dyn Fn.

What you suggested would work but it'd be suboptimal.

[Yureien]

@LLFourn Yeah that sounds good. Also I think it would be better to use non immutable Fn since if we add mutability with an Arc, it'll become more complex (we'll need to add a Mutex too). Is it worth supporting FnMut against the extra complexity?

[LLFourn]

Is it worth supporting FnMut against the extra complexity?

Ok I see your point. If it does need to be an Arc because of the clone thing then yeah I guess Fn is the right answer for now.

[notmandatory]

@Eunoia1729 have you started looking into this issue? If so can you help @fadedcoder with testing/review for #556 ?

[Eunoia1729]

@notmandatory Yes, I was working on it but paused when a PR was opened. Sure, will be happy to help with testing/review !

[danielabrozzoni]

I'm unassigning @Yureien as he hasn't updated #556 in a long while.

If someone else wants to take a shot at this, it's all yours! You should probably use #556's code, as it was almost done.

[nymius]

@rustaceanrob are you working on this?

[rustaceanrob]

All yours. I would pick up where #556 left off but just remove BIP69 entirely. Adding a closure for input and output is sufficient imo. FYI there might be merge conflicts on your feature branch soon if #1395 gets merged