Date: Wed, 2 Nov 2022 13:52:09 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <Y2HpaWnAC5dIGkx+@erisian.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Cc: John Carvalho <john@synonym.to>
Subject: [bitcoin-dev] Preventing/detecting pinning of jointly funded txs
Precedence: list

On Fri, Oct 28, 2022 at 03:21:53AM +1000, Anthony Towns via bitcoin-dev wrote:
> What should folks wanting to do coinjoins/dualfunding/dlcs/etc do to
> solve that problem if they have only opt-in RBF available?

ref: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-October/021124.html

So, having a go at answering my own question.

I think ultimately the scenario here is:

 * you have a joint funding protocol, where everyone says "here's
   an unspent utxo that will be my contribution", collaborates on signing
   a transaction spending all those utxos, and then broadcasts it

 * everyone jointly agrees to pay some amount in fees for that
   transaction, targeting confirmation within N blocks

 * the goal is to have the transaction confirm, obviously; but it's also
   acceptable to discover a conflicting transaction, as that will
   demonstrate that a particular participant has been dishonest (their
   utxo was not "unspent"), allowing the overall protocol to make progress

The question then is how much effort do you have to go to to make such a
protocol work?

As an extreme example, you could always have each participant maintain
a dedicated amount of hashpower: eg, if each participant individually
controls 0.5% of hashpower, then having two honest participants would
give you a 75% chance of confirmation within 137 blocks (roughly a day),
even if your transaction failed to relay at all, and the only way to
prevent confirmation is for a conflicting transaction to be confirmed
earlier. Of course, needing to have 0.5% of hashpower would mean fewer
than 200 people globally could participate in such a protocol, and
requires something like $10M in capital investment just for ASICs in
order to participate.

I think the next step from that pretty much requires introducing the
assumption that the vast majority of the bitcoin p2p network (both nodes
and hashrate) will accept your transaction, at least in a world where all
your collaborators are honest and don't create conflicting transactions.
You can limit that assumption a little bit, but without most p2p peers
being willing to relay your tx, you start having privacy issues; and
without most miners being willing to mine your tx, you start getting
problems with predicting fees. And in any event, I don't think anyone's
trying to make weird transactions here, just get their otherwise normal
transactions to actually confirm.

I think the same approach used to detect double spend races by people
accepting zeroconf would work here too. That is setup a couple of
anonymous bitcoin nodes, let them sit for a couple of weeks so their
mempools are realistic, then when you broadcast a jointly funded
transaction, query their mempools: if your new tx made it there, it
likely made it to mining pools too, and you're fine; if it didn't, then
the transaction that's blocking it almost certainly did, so you can find
out what that is and can go from there.

(If you don't see either your tx, or a conflicting one, then it likely
means the nodes that broadcasted your tx are being sybil attacked, either
because their peers are directly controlled by an attacker, or they've
been identified by an attacker and attacked in some other way; presumably
you could pick a couple of node that have been confirmed by both your
anonymous nodes' as valid and reachable, and connect to them to break
out of the sybil attack; if that doesn't work either, you probably need
to change ISPs or put your active node via a (different) VPN provider...)

Your capital expenses are much lower that way: perhaps on the order of
$20/month to run a couple of nodes on AWS or linode or similar.

But, you might say, what if I don't even want to run multiple bitcoin
nodes 24/7 indefinitely? Can we outsource that, like we outsource mining
by paying tx fees?

That seems harder, particularly if you want to avoid whoever you're
outsourcing too from associating you with the jointly funded transaction
you're interested in.

If you're *not* worried about that association, it's probably easy:
just find some public explorers, and see if they list any conflicts in
their mempool, or use the "broadcast tx" feature and see if it gives an
error identifying the conflicting transaction.

I think it's probably hard to make that behaviour a normal part of p2p tx
relay though: if someone's trying to relay tx T but you reject it
because of a conflicting tx C; then it's easy to tell the node that
first relayed T to you about C -- but how does that information get back
to the original broadcaster?

One way would be to broadcast "C" back to whoever announced T to you,
and let C propogate all the way back to whoever originally proposed T --
but that only works if everyone's running a mempool policy where there's
a total ordering for tx replacement, ie for any conflicting txs, either
T replaces C or C replaces T, and that's not something we have now or
would have even with full RBF, and seems pretty hard to actually achieve.
(And if it was achieved, you could just keep replacing T with a more
attractive T' so that it did eventually replace C)

Another way might be to have the original broadcaster retry the broadcast:
connect to new peers, reannounce T, and see what happens.  Then eventually
they'll connect to a peer that has C in their mempool, and just needs a
"reject" message of some kind that can identify C.  But in that case,
the peer that's going to send the reject message needs to be able to
efficiently associate T back to C, even though it doesn't have T in
the mempool -- it won't want to redownload T each time, because that's
a waste of bandwidth, and it can't re-validate T to find the conflict
fresh without having a copy of T.

Using BIP 37 mempool filters or something might be an approach if there
are plenty of nodes around that _are_ willing to dedicate extra resources
to helping people find potentially conflicting txs.  Unfortunately that
probably is pretty bad for privacy: if your adversary is blocking your
coinjoin T with a pinned tx C, then the fact that you've asked for a
filter that happens to match C is probably a good indication that you're
involved in the coinjoin T; and there's a decent chance that the only
people will to dedicate the extra resources to offer those services to
the public will be people who want to invade your privacy...

A problem with mempool filters (or telling other nodes what's in your
mempool in general) is that that can provide a way for attackers to
identify who your peers are: if you create a bunch of conflicting txs,
and give a different one to many nodes other than you, then see which
tx you end up with, that identifies which peers are close to you, and
that information could be used to attack those peers, which in turn may
allow more effective sybil attacks against you.

So I think my best answer is:

 - if you really want to do things with untrusted peers in bitcoin,
   investing in hashpower maybe isn't that unreasonable a thing to
   do. $10M in capital giving you the ability to usually make progress
   within a day even if everyone else dislikes you? surprisingly
   reasonable, especially if more progress is made on stratumv2...

 - if you don't care about privacy (eg, you're funding a lightning
   channel that's going to be gossiped anyway), just query an explorer
   (or some other centralised service) to find out the conflicting tx
   and go from there.

 - if you do care about privacy, run a few "anonymous" bitcoind nodes
   that don't announce transactions, and see what their mempool
   contains.

 - we can probably make it easier to run anonymous bitcoind nodes
   by making transaction broadcasts more private (tor/i2p? dandelion? have
   lightning nodes send channel open/close txs to another lightning
   node to announce to bitcoin p2p?) -- for cases where you're already
   running a bitcoin node 24/7 (or trusting someone else that does), I
   think that gives you a pretty good method of either being confident
   your tx made it to a decent percentage of hashrate, or spotting a
   conflicting tx to be able to assign blame

Anyone got any improvements on the above?

Cheers,
aj