public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant
@ 2022-11-07 20:17 Peter Todd
  2022-11-07 21:17 ` [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime Peter Todd
  2022-11-07 21:21 ` [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Suhas Daftuar
  0 siblings, 2 replies; 7+ messages in thread
From: Peter Todd @ 2022-11-07 20:17 UTC (permalink / raw)
  To: bitcoin-dev

[-- Attachment #1: Type: text/plain, Size: 3576 bytes --]

tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all
transactions in the mempool are always replaceable.


Currently Bitcoin Core implements rule #5 of BIP-125:

    The number of original transactions to be replaced and their descendant
    transactions which will be evicted from the mempool must not exceed a total
    of 100 transactions.

As of Bitcoin Core v24.0rc3, this rule is implemented via the
MAX_REPLACEMENT_CANDIDATES limit in GetEntriesForConflicts:

    // Rule #5: don't consider replacing more than MAX_REPLACEMENT_CANDIDATES
    // entries from the mempool. This potentially overestimates the number of actual
    // descendants (i.e. if multiple conflicts share a descendant, it will be counted multiple
    // times), but we just want to be conservative to avoid doing too much work.
    if (nConflictingCount > MAX_REPLACEMENT_CANDIDATES) {
        return strprintf("rejecting replacement %s; too many potential replacements (%d > %d)\n",
                         txid.ToString(),
                         nConflictingCount,
                         MAX_REPLACEMENT_CANDIDATES);
    }

There is no justification for this rule beyond avoiding "too much work"; the
exact number was picked at random when the BIP was written to provide an
initial conservative limit, and is not justified by benchmarks or memory usage
calculations. It may in fact be the case that this rule can be removed entirely
as the overall mempool size limits naturally limit the maximum number of
possible replacements.


But for the sake of argument, let's suppose some kind of max replacement limit
is required. Can we avoid rule #5 pinning? The answer is yes, we can, with the
following invariant:

    No transaction may be accepted into the mempool that would cause another
    transaction to be unable to be replaced due to Rule #5.

We'll call this the Replaceability Invariant. Implementing this rule is simple:
for each transaction maintain an integer, nReplacementCandidates. When a
non-conflicting transaction is considered for acceptance to the mempool, verify
that nReplacementCandidates + 1 < MAX_REPLACEMENT_CANDIDATES for each
unconfirmed parent. When a transaction is accepted, increment
nReplacementCandidates by 1 for each unconfirmed parent.

When a *conflicting* transaction is considered for acceptance, we do _not_ need
to verify anything: we've already guaranteed that every transaction in the
mempool is replaceable! The only thing we may need to do is to decrement
nReplacementCandidates by however many children we have replaced, for all
unconfirmed parents.

When a block is mined, note how the nReplacementCandidates of all unconfirmed
transactions remains unchanged because a confirmed transaction can't spend an
unconfirmed txout.

The only special case to handle is a reorg that changes a transaction from
confirmed to unconfirmed. Setting nReplacementCandidates to
MAX_REPLACEMENT_CANDIDATES would be fine in that very rare case.


Note that like the existing MAX_REPLACEMENT_CANDIDATES check, the
Replaceability Invariant overestimates the number of transactions to be
replaced in the event that multiple children are spent by the same transaction.
That's ok: diamond tx graphs are even more unusual than unconfirmed children,
and there's no reason to bend over backwards to accomodate them.

Prior art: this proposed rule is similar in spirit to the package limits aready
implemented in Bitcoin Core.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

^ permalink raw reply	[flat|nested] 7+ messages in thread

• * [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime
    2022-11-07 20:17 [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Peter Todd
  @ 2022-11-07 21:17 ` Peter Todd
    2022-11-07 22:55   ` Antoine Riard
    2022-11-11  3:00   ` David A. Harding
    2022-11-07 21:21 ` [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Suhas Daftuar
    1 sibling, 2 replies; 7+ messages in thread
  From: Peter Todd @ 2022-11-07 21:17 UTC (permalink / raw)
    To: Bitcoin Protocol Discussion
  
  [-- Attachment #1: Type: text/plain, Size: 5001 bytes --]
  
  On Mon, Nov 07, 2022 at 03:17:29PM -0500, Peter Todd via bitcoin-dev wrote:
  > tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all
  > transactions in the mempool are always replaceable.
  
  With Rule #5 solved, let's look at the other pinning attack on multi-party
  transactions: BIP-125 Rule #3
  
  tl;dr: In conjunction with full-RBF, nLockTime'd, pre-signed, transactions can
  ensure that one party is not forced to pay for all the cost of a rule #3
  replacement.
  
  
  # What is the problem?
  
  When a transaction contains inputs from multiple parties, each party can lock
  up funds from the other party by spending their input with a transaction that
  is difficult/expensive to replace. Obviously, the clearest example of "difficult to
  replace" is a non-BIP-125 (Opt-in-RBF) transaction. But here, we'll assume that
  full-rbf is implemented and all transactions are replaceable.
  
  BIP-125 Rule #3 states that:
  
      The replacement transaction pays an absolute fee of at least the sum paid
      by the original transactions.
  
  The attack is that the malicious party, who we'll call Mallory, broadcasts a
  transaction spending their input(s) with a low fee rate transaction that's
  potentially quite large, during a time of high mempool demand. Due to the low
  fee rate this transaction will take a significant amount of time to mine. The
  other parties to the transaction - who we'll collectively call Alice - are now
  unable to spend their inputs unless they broadcast a transaction "paying for"
  Mallory's.
  
  This attack works because Mallory doesn't expect the conflicting tx to actually
  get mined: he assumes it'll either expire, or Alice will get frustrated and
  have to double spend it. By simple tying up money, Mallory has caused Alice to
  actually lose money.
  
  
  # Fixing the problem with nLockTime
  
  Conversely, in the case of an honest multi-party transaction, whose parties
  we'll call Alice and Bob, the parties genuinely intend for one of two outcomes:
  
  1) The multi-party transaction to get mined within N blocks.
  2) The transaction to be cancelled (most likely by spending one of the inputs).
  
  We can ensure with high probability that the transaction can be cancelled/mined
  at some point after N blocks by pre-signing a transaction, with nLockTime set
  sufficiently far into the future, spending one or more inputs of the
  transaction with a sufficiently high fee that it would replace transaction(s)
  attempting to exploit Rule #3 pinning (note how the package limits in Bitcoin
  Core help here).
  
  There's a few different ways to implement this, and exactly which one makes
  sense will depend on the specifics of the multi-party protocol. But the general
  approach is to defeat the attack by ensuring that Mallory will have to pay the
  cost of getting the multi-party transaction unstuck, at some point in the
  future.
  
  For example, in a two party transaction where there's a clearly more reputable
  party (Alice), and an untrusted party (Mallory), Alice could simply require
  Mallory to provide a nLockTime'd transaction spending only his input to fees,
  multiple days into the future. In the unlikely event that Mallory holds up the
  protocol, he will be severely punished. Meanwhile, Alice can always cancel at
  no cost.
  
  In a many party transaction where both parties are equally (un)trustworthy the
  protocol could simply have both parties sign a series of transactions,
  nLockTimed at decreasingly far into a future, paying a decreasingly amount of
  fees. If either party holds up the transaction intentionally, they'll both pay
  a high cost. But again, at some point Mallory will have paid the full price for
  his attack. This approach also has the beneficial side effect of implementing
  fee discovery with rbf. This approach is easier as the number of parties
  increases, eg the Wasabi/Joinmarket transactions with hundreds of inputs and
  outputs: they collectively already have to pay a significant fee to get the
  transaction mined, making the extra poential cost needed to defeat pinning
  minimal.
  
  
  # Coordinator Spent Bonds with Package Relay/Replacement
  
  For schemes with a central semi-trusted coordinator, such as Wasabi coinjoins,
  with package relay/replacement we can use a two party punishment transaction
  consisting of:
  
      tx1 - spends Mallory's input to a txout spendable by:
             IF
                 <coordinator> CheckSig
             Else
                 <delay> CheckSequenceVerify
                 <mallory> CheckSig
             EndIf
  
      tx2 - spends tx1 output to as much fees as needed
  
  Whether or not Mallory cheated with a double-spend is provable to third
  parties; the second transaction ensures that Mallory can't simply release tx1
  on their own to frame the coordinator. The use of CheckSequenceVerify ensures
  that if mallory did try to frame the coordinator, they don't have to do
  anything to return the funds to Mallory.
  
  -- 
  https://petertodd.org 'peter'[:-1]@petertodd.org
  
  [-- Attachment #2: signature.asc --]
  [-- Type: application/pgp-signature, Size: 833 bytes --]
  
  ^ permalink raw reply	[flat|nested] 7+ messages in thread

• • * Re: [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime
      2022-11-07 21:17 ` [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime Peter Todd
    @ 2022-11-07 22:55   ` Antoine Riard
      2022-11-09 12:41     ` Peter Todd
      2022-11-11  3:00   ` David A. Harding
      1 sibling, 1 reply; 7+ messages in thread
    From: Antoine Riard @ 2022-11-07 22:55 UTC (permalink / raw)
      To: Peter Todd, Bitcoin Protocol Discussion
    
    [-- Attachment #1: Type: text/plain, Size: 8120 bytes --]
    
    Hi Peter,
    
    > We can ensure with high probability that the transaction can be cancelled/mined
    > at some point after N blocks by pre-signing a transaction, with nLockTime set
    > sufficiently far into the future, spending one or more inputs of the
    > transaction with a sufficiently high fee that it would replace transaction(s)
    > attempting to exploit Rule #3 pinning (note how the package limits in Bitcoin
    > Core help here).
    
    From my understanding, there are many open questions to such a
    pre-signed high-fee solution aiming to address Rule #3 pinning.
    Determining the high-fee to guarantee replacements with high odds. I
    think it should be superior to current top network mempools sat/vb *
    MAX_STANDARD_TX_WEIGHT, otherwise an adversary can pin the multi-party
    funded transaction on the ground of Core's
    replacement rule ("The replacement transaction's feerate is greater
    than the feerates of all directly conflicting transactions''). Though
    note the difficulty, the sat/vb is an unknown fact at time of
    signatures exchange among the multi-party funded transaction
    participants. Solving this issue probably requires from then to
    overshoot, and adopt a historical worst-case mempool feerate.
    
    This "historically-worst" sat/vb introduces two new issues, first I
    think this is an economic lower bound on the funds that can be staked
    in the collaborative transaction. Second I believe this constitutes a
    griefing vector, where a participant could deliberately pin to inflict
    an asymmetric damage, without entering into any fee competition. This
    griefing vector could be leveraged as hard as being triggered by a
    miner-as-participant in so-called miner harvesting attacks.
    
    Further, I think this solution relying on nLocktime doesn't solve the
    timevalue DoS inflicted to the participants UTXOs, until the
    pre-signed high-fee transaction is final. If participants prefer to
    save the timevalue of their contributed UTXOs over operation success,
    a better approach could be for them to unilaterally spend after a
    protocol/implementation timepoint (e.g LN's funding timeout recovery
    mechanism).
    
    A more workable solution I believe could be simply to rely on
    package-relay, an ephemeral anchor output, and a special replacement
    regime (e.g nVersion=3) to allow the multi-party funded transaction
    coordinator to unilateral fee-bump, in a step-by-step approach. I.e
    without making assumptions on the knowledge of network mempools and
    burning directly the worst amount in fees.
    
    Best,
    Antoine
    
    
    Le lun. 7 nov. 2022 à 16:18, Peter Todd via bitcoin-dev <
    bitcoin-dev@lists•linuxfoundation.org> a écrit :
    
    > On Mon, Nov 07, 2022 at 03:17:29PM -0500, Peter Todd via bitcoin-dev wrote:
    > > tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all
    > > transactions in the mempool are always replaceable.
    >
    > With Rule #5 solved, let's look at the other pinning attack on multi-party
    > transactions: BIP-125 Rule #3
    >
    > tl;dr: In conjunction with full-RBF, nLockTime'd, pre-signed, transactions
    > can
    > ensure that one party is not forced to pay for all the cost of a rule #3
    > replacement.
    >
    >
    > # What is the problem?
    >
    > When a transaction contains inputs from multiple parties, each party can
    > lock
    > up funds from the other party by spending their input with a transaction
    > that
    > is difficult/expensive to replace. Obviously, the clearest example of
    > "difficult to
    > replace" is a non-BIP-125 (Opt-in-RBF) transaction. But here, we'll assume
    > that
    > full-rbf is implemented and all transactions are replaceable.
    >
    > BIP-125 Rule #3 states that:
    >
    >     The replacement transaction pays an absolute fee of at least the sum
    > paid
    >     by the original transactions.
    >
    > The attack is that the malicious party, who we'll call Mallory, broadcasts
    > a
    > transaction spending their input(s) with a low fee rate transaction that's
    > potentially quite large, during a time of high mempool demand. Due to the
    > low
    > fee rate this transaction will take a significant amount of time to mine.
    > The
    > other parties to the transaction - who we'll collectively call Alice - are
    > now
    > unable to spend their inputs unless they broadcast a transaction "paying
    > for"
    > Mallory's.
    >
    > This attack works because Mallory doesn't expect the conflicting tx to
    > actually
    > get mined: he assumes it'll either expire, or Alice will get frustrated and
    > have to double spend it. By simple tying up money, Mallory has caused
    > Alice to
    > actually lose money.
    >
    >
    > # Fixing the problem with nLockTime
    >
    > Conversely, in the case of an honest multi-party transaction, whose parties
    > we'll call Alice and Bob, the parties genuinely intend for one of two
    > outcomes:
    >
    > 1) The multi-party transaction to get mined within N blocks.
    > 2) The transaction to be cancelled (most likely by spending one of the
    > inputs).
    >
    > We can ensure with high probability that the transaction can be
    > cancelled/mined
    > at some point after N blocks by pre-signing a transaction, with nLockTime
    > set
    > sufficiently far into the future, spending one or more inputs of the
    > transaction with a sufficiently high fee that it would replace
    > transaction(s)
    > attempting to exploit Rule #3 pinning (note how the package limits in
    > Bitcoin
    > Core help here).
    >
    > There's a few different ways to implement this, and exactly which one makes
    > sense will depend on the specifics of the multi-party protocol. But the
    > general
    > approach is to defeat the attack by ensuring that Mallory will have to pay
    > the
    > cost of getting the multi-party transaction unstuck, at some point in the
    > future.
    >
    > For example, in a two party transaction where there's a clearly more
    > reputable
    > party (Alice), and an untrusted party (Mallory), Alice could simply require
    > Mallory to provide a nLockTime'd transaction spending only his input to
    > fees,
    > multiple days into the future. In the unlikely event that Mallory holds up
    > the
    > protocol, he will be severely punished. Meanwhile, Alice can always cancel
    > at
    > no cost.
    >
    > In a many party transaction where both parties are equally (un)trustworthy
    > the
    > protocol could simply have both parties sign a series of transactions,
    > nLockTimed at decreasingly far into a future, paying a decreasingly amount
    > of
    > fees. If either party holds up the transaction intentionally, they'll both
    > pay
    > a high cost. But again, at some point Mallory will have paid the full
    > price for
    > his attack. This approach also has the beneficial side effect of
    > implementing
    > fee discovery with rbf. This approach is easier as the number of parties
    > increases, eg the Wasabi/Joinmarket transactions with hundreds of inputs
    > and
    > outputs: they collectively already have to pay a significant fee to get the
    > transaction mined, making the extra poential cost needed to defeat pinning
    > minimal.
    >
    >
    > # Coordinator Spent Bonds with Package Relay/Replacement
    >
    > For schemes with a central semi-trusted coordinator, such as Wasabi
    > coinjoins,
    > with package relay/replacement we can use a two party punishment
    > transaction
    > consisting of:
    >
    >     tx1 - spends Mallory's input to a txout spendable by:
    >            IF
    >                <coordinator> CheckSig
    >            Else
    >                <delay> CheckSequenceVerify
    >                <mallory> CheckSig
    >            EndIf
    >
    >     tx2 - spends tx1 output to as much fees as needed
    >
    > Whether or not Mallory cheated with a double-spend is provable to third
    > parties; the second transaction ensures that Mallory can't simply release
    > tx1
    > on their own to frame the coordinator. The use of CheckSequenceVerify
    > ensures
    > that if mallory did try to frame the coordinator, they don't have to do
    > anything to return the funds to Mallory.
    >
    > --
    > https://petertodd.org 'peter'[:-1]@petertodd.org
    > _______________________________________________
    > bitcoin-dev mailing list
    > bitcoin-dev@lists•linuxfoundation.org
    > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
    >
    
    [-- Attachment #2: Type: text/html, Size: 9275 bytes --]
    
    ^ permalink raw reply	[flat|nested] 7+ messages in thread

  • • * Re: [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime
        2022-11-07 22:55   ` Antoine Riard
      @ 2022-11-09 12:41     ` Peter Todd
        0 siblings, 0 replies; 7+ messages in thread
      From: Peter Todd @ 2022-11-09 12:41 UTC (permalink / raw)
        To: Antoine Riard; +Cc: Bitcoin Protocol Discussion
      
      [-- Attachment #1: Type: text/plain, Size: 4397 bytes --]
      
      On Mon, Nov 07, 2022 at 05:55:59PM -0500, Antoine Riard wrote:
      > Hi Peter,
      > 
      > > We can ensure with high probability that the transaction can be cancelled/mined
      > > at some point after N blocks by pre-signing a transaction, with nLockTime set
      > > sufficiently far into the future, spending one or more inputs of the
      > > transaction with a sufficiently high fee that it would replace transaction(s)
      > > attempting to exploit Rule #3 pinning (note how the package limits in Bitcoin
      > > Core help here).
      > 
      > From my understanding, there are many open questions to such a
      > pre-signed high-fee solution aiming to address Rule #3 pinning.
      > Determining the high-fee to guarantee replacements with high odds. I
      > think it should be superior to current top network mempools sat/vb *
      > MAX_STANDARD_TX_WEIGHT, otherwise an adversary can pin the multi-party
      > funded transaction on the ground of Core's
      > replacement rule ("The replacement transaction's feerate is greater
      > than the feerates of all directly conflicting transactions''). Though
      > note the difficulty, the sat/vb is an unknown fact at time of
      > signatures exchange among the multi-party funded transaction
      > participants. Solving this issue probably requires from then to
      > overshoot, and adopt a historical worst-case mempool feerate.
      
      First of all, since this is a punishment scenario, overshooting in general is a
      good thing provided that the bad actor is the one paying for the overshoot.
      
      I may be mistaken on this point. But IIRC rule #6, "The replacement
      transaction's feerate is greater than the feerates of all directly conflicting
      transactions.", refers to the overall package feerate including all
      transactions that would need to be mined.
      
      This is relevant as we have two scenarios for pinning that could try to exploit
      rule #6 while pinning, and neither works:
      
      1) A large, low fee rate, transaction is spent by a high fee rate transaction.
      In this case the package fee rate of the second tx is still low, because the
      low fee rate tx would need to be mined first.
      
      2) A small, high fee rate tx, is spent by a large low fee rate tx. In this case
      the second low fee rate tx is irrelevant, because the high fee rate tx will get
      mined soon, breaking the pin and costing the attacker money.
      
      
      Now, if my understanding of rule #6 is incorrect, obviously we should fix that!
      It's incentive incompatible to reject a high fee rate replacement that overall
      pays more in fees (rule #3), on the basis that we expect a *different* miner to
      mine the low fee rate tx it spends. Because unless we're expecting the
      transaction to somehow get mined by someone else in the near future, why aren't
      we mining what pays more money now?
      
      > This "historically-worst" sat/vb introduces two new issues, first I
      > think this is an economic lower bound on the funds that can be staked
      > in the collaborative transaction. Second I believe this constitutes a
      > griefing vector, where a participant could deliberately pin to inflict
      > an asymmetric damage, without entering into any fee competition. This
      > griefing vector could be leveraged as hard as being triggered by a
      > miner-as-participant in so-called miner harvesting attacks.
      > 
      > Further, I think this solution relying on nLocktime doesn't solve the
      > timevalue DoS inflicted to the participants UTXOs, until the
      > pre-signed high-fee transaction is final. If participants prefer to
      > save the timevalue of their contributed UTXOs over operation success,
      > a better approach could be for them to unilaterally spend after a
      > protocol/implementation timepoint (e.g LN's funding timeout recovery
      > mechanism).
      > 
      > A more workable solution I believe could be simply to rely on
      > package-relay, an ephemeral anchor output, and a special replacement
      > regime (e.g nVersion=3) to allow the multi-party funded transaction
      > coordinator to unilateral fee-bump, in a step-by-step approach. I.e
      > without making assumptions on the knowledge of network mempools and
      > burning directly the worst amount in fees.
      
      Note that if you are considering miner harvesting attacks as part of the threat
      model, it's not clear to me that the v3 rules that depend on miners arbitrarily
      rejecting transactions from their mempools are actually sufficiently incentive
      compatible to work.
      
      -- 
      https://petertodd.org 'peter'[:-1]@petertodd.org
      
      [-- Attachment #2: signature.asc --]
      [-- Type: application/pgp-signature, Size: 833 bytes --]
      
      ^ permalink raw reply	[flat|nested] 7+ messages in thread

  • * Re: [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime
      2022-11-07 21:17 ` [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime Peter Todd
      2022-11-07 22:55   ` Antoine Riard
    @ 2022-11-11  3:00   ` David A. Harding
      1 sibling, 0 replies; 7+ messages in thread
    From: David A. Harding @ 2022-11-11  3:00 UTC (permalink / raw)
      To: Peter Todd, Bitcoin Protocol Discussion
    
    On 2022-11-07 11:17, Peter Todd via bitcoin-dev wrote:
    > We can ensure with high probability that the transaction can be 
    > cancelled/mined
    > at some point after N blocks by pre-signing a transaction, with 
    > nLockTime set
    > sufficiently far into the future, spending one or more inputs of the
    > transaction with a sufficiently high fee that it would replace 
    > transaction(s)
    > attempting to exploit Rule #3 pinning (note how the package limits in 
    > Bitcoin
    > Core help here).
    
    This implies a floor on the funds involved in a contract.  For example, 
    if the pinning transaction is 100,000 vbytes at a feerate of 1 sat/vb, 
    the minimum contract amount must be a bit over 100,000 sats (about $17 
    USD at current prices).  However, participants in a contract not meant 
    to settle immediately probably need to assume the worst case future 
    pinning, for example where transactions paying even 100 sat/vb won't be 
    mined promptly; in which case the minimum contract amount becomes 
    something like $1,700 USD.
    
    That seems sub-optimal to me.
    
    -Dave
    
    
    ^ permalink raw reply	[flat|nested] 7+ messages in thread

• * Re: [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant
    2022-11-07 20:17 [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Peter Todd
    2022-11-07 21:17 ` [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime Peter Todd
  @ 2022-11-07 21:21 ` Suhas Daftuar
    2022-11-07 21:27   ` Peter Todd
    1 sibling, 1 reply; 7+ messages in thread
  From: Suhas Daftuar @ 2022-11-07 21:21 UTC (permalink / raw)
    To: Bitcoin Protocol Discussion
  
  [-- Attachment #1: Type: text/plain, Size: 4888 bytes --]
  
  Hello bitcoin-dev,
  
  The description in the OP is completely broken for the simple reason that
  Bitcoin transactions can have multiple inputs, and so a single transaction
  can conflict with multiple in-mempool transactions. The proposal would
  limit the number of descendants of each in-mempool transaction to
  MAX_REPLACEMENT_CANDIDATES (note that this is duplicative of the existing
  Bitcoin Core descendant limits), but a transaction that has, say, 500
  inputs might arrive and conflict with 500 unrelated in-mempool
  transactions. This could result in 12,500 evictions -- far more than the
  100 that was intended.
  
  Also, note that those 500 transactions might instead have 24 ancestors each
  (again, using the default chain limits in Bitcoin Core) -- this would
  result in 12,000 transactions whose state would be updated as a result of
  evicting those 500 transactions. Hopefully this gives some perspective on
  why we have a limit.
  
  
  On Mon, Nov 7, 2022 at 3:17 PM Peter Todd via bitcoin-dev <
  bitcoin-dev@lists•linuxfoundation.org> wrote:
  
  > tl;dr: We can remove the problem of Rule #5 pinning by ensuring that all
  > transactions in the mempool are always replaceable.
  >
  >
  > Currently Bitcoin Core implements rule #5 of BIP-125:
  >
  >     The number of original transactions to be replaced and their descendant
  >     transactions which will be evicted from the mempool must not exceed a
  > total
  >     of 100 transactions.
  >
  > As of Bitcoin Core v24.0rc3, this rule is implemented via the
  > MAX_REPLACEMENT_CANDIDATES limit in GetEntriesForConflicts:
  >
  >     // Rule #5: don't consider replacing more than
  > MAX_REPLACEMENT_CANDIDATES
  >     // entries from the mempool. This potentially overestimates the number
  > of actual
  >     // descendants (i.e. if multiple conflicts share a descendant, it will
  > be counted multiple
  >     // times), but we just want to be conservative to avoid doing too much
  > work.
  >     if (nConflictingCount > MAX_REPLACEMENT_CANDIDATES) {
  >         return strprintf("rejecting replacement %s; too many potential
  > replacements (%d > %d)\n",
  >                          txid.ToString(),
  >                          nConflictingCount,
  >                          MAX_REPLACEMENT_CANDIDATES);
  >     }
  >
  > There is no justification for this rule beyond avoiding "too much work";
  > the
  > exact number was picked at random when the BIP was written to provide an
  > initial conservative limit, and is not justified by benchmarks or memory
  > usage
  > calculations. It may in fact be the case that this rule can be removed
  > entirely
  > as the overall mempool size limits naturally limit the maximum number of
  > possible replacements.
  >
  >
  > But for the sake of argument, let's suppose some kind of max replacement
  > limit
  > is required. Can we avoid rule #5 pinning? The answer is yes, we can, with
  > the
  > following invariant:
  >
  >     No transaction may be accepted into the mempool that would cause
  > another
  >     transaction to be unable to be replaced due to Rule #5.
  >
  > We'll call this the Replaceability Invariant. Implementing this rule is
  > simple:
  > for each transaction maintain an integer, nReplacementCandidates. When a
  > non-conflicting transaction is considered for acceptance to the mempool,
  > verify
  > that nReplacementCandidates + 1 < MAX_REPLACEMENT_CANDIDATES for each
  > unconfirmed parent. When a transaction is accepted, increment
  > nReplacementCandidates by 1 for each unconfirmed parent.
  >
  > When a *conflicting* transaction is considered for acceptance, we do _not_
  > need
  > to verify anything: we've already guaranteed that every transaction in the
  > mempool is replaceable! The only thing we may need to do is to decrement
  > nReplacementCandidates by however many children we have replaced, for all
  > unconfirmed parents.
  >
  > When a block is mined, note how the nReplacementCandidates of all
  > unconfirmed
  > transactions remains unchanged because a confirmed transaction can't spend
  > an
  > unconfirmed txout.
  >
  > The only special case to handle is a reorg that changes a transaction from
  > confirmed to unconfirmed. Setting nReplacementCandidates to
  > MAX_REPLACEMENT_CANDIDATES would be fine in that very rare case.
  >
  >
  > Note that like the existing MAX_REPLACEMENT_CANDIDATES check, the
  > Replaceability Invariant overestimates the number of transactions to be
  > replaced in the event that multiple children are spent by the same
  > transaction.
  > That's ok: diamond tx graphs are even more unusual than unconfirmed
  > children,
  > and there's no reason to bend over backwards to accomodate them.
  >
  > Prior art: this proposed rule is similar in spirit to the package limits
  > aready
  > implemented in Bitcoin Core.
  >
  > --
  > https://petertodd.org 'peter'[:-1]@petertodd.org
  > _______________________________________________
  > bitcoin-dev mailing list
  > bitcoin-dev@lists•linuxfoundation.org
  > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
  >
  
  [-- Attachment #2: Type: text/html, Size: 5963 bytes --]
  
  ^ permalink raw reply	[flat|nested] 7+ messages in thread

• • * Re: [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant
      2022-11-07 21:21 ` [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Suhas Daftuar
    @ 2022-11-07 21:27   ` Peter Todd
      0 siblings, 0 replies; 7+ messages in thread
    From: Peter Todd @ 2022-11-07 21:27 UTC (permalink / raw)
      To: Suhas Daftuar, Bitcoin Protocol Discussion
    
    [-- Attachment #1: Type: text/plain, Size: 1172 bytes --]
    
    On Mon, Nov 07, 2022 at 04:21:11PM -0500, Suhas Daftuar via bitcoin-dev wrote:
    > Hello bitcoin-dev,
    > 
    > The description in the OP is completely broken for the simple reason that
    > Bitcoin transactions can have multiple inputs, and so a single transaction
    > can conflict with multiple in-mempool transactions. The proposal would
    > limit the number of descendants of each in-mempool transaction to
    > MAX_REPLACEMENT_CANDIDATES (note that this is duplicative of the existing
    > Bitcoin Core descendant limits), but a transaction that has, say, 500
    > inputs might arrive and conflict with 500 unrelated in-mempool
    > transactions. This could result in 12,500 evictions -- far more than the
    > 100 that was intended.
    
    That's easy to fix: just sum up the number of nReplacementCandidates for each
    input in the multiple input case. Again, it'll overcount in the diamond case.
    But so does the existing code.
    
    The goal is to defeat pinning by ensuring that you can always replace a
    transaction by double-spending an output; not that any possible way of
    double-spending multiple outputs at once would work.
    
    -- 
    https://petertodd.org 'peter'[:-1]@petertodd.org
    
    [-- Attachment #2: signature.asc --]
    [-- Type: application/pgp-signature, Size: 833 bytes --]
    
    ^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2022-11-11  3:01 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-11-07 20:17 [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Peter Todd
2022-11-07 21:17 ` [bitcoin-dev] Using Full-RBF to fix BIP-125 Rule #3 Pinning with nLockTime Peter Todd
2022-11-07 22:55   ` Antoine Riard
2022-11-09 12:41     ` Peter Todd
2022-11-11  3:00   ` David A. Harding
2022-11-07 21:21 ` [bitcoin-dev] Removing BIP-125 Rule #5 Pinning with the Always-Replaceable Invariant Suhas Daftuar
2022-11-07 21:27   ` Peter Todd

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox