Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Hi Peter, Thanks you for investigate my concern and replicate the scenario I drafted. On 27.01.24 02:19, Peter Todd wrote: I actually tried this attack out, and it fails at step #4 due to the Rule #6, PaysMoreThanConflicts, check. While on stacker.news you stated that: tx_HS has 5000 vB and pays 21 s/vB, but since it spends an output from a low-feerate parent, it’s mining score is only 1.95 s/vB. and You RBF tx_LL and tx_HS with tx_LM that has 100,000 vB and pays 3.05 s/vB (fee: 305,000 s) by spending the outputs C1 and C2. This is permitted, since only tx_LL is a direct conflict, so the feerate of tx_HS does not have to be beat directly. tx_HS _is_ considered to be a direct conflict, and its raw fee-rate _does_ have to be beat directly. While ts_HS does spend an unconfirmed output, it appears that the fee-rate PaysMoreThanConflicts uses to calculate if ts_HS can be beaten is ts_HS's raw fee-rate. So looks like your understanding was incorrect on these two points. I agree in the detail, but not about the big picture. You are right that it’s a problem that `tx_LM` and `tx_HS` spend the same input and therefore are direct conflicts. Luckily, it is unnecessary for my scenario that `tx_LM` and `tx_HS` conflict. The scenario only requires that `tx_LM` conflicts with `tx_LL` and `tx_RBFr`. `tx_HS` is supposed to get dropped indirectly per the conflict with `tx_LL`. It seems to me that my example attack should work when a third confirmed input `c3` is introduced as follows: `tx_LM` spends `c3` instead of `c2`, and `tx_RBFr` spends both `c2` and `c3`, which allows the following four conflicts: - `tx_HS` and `tx_RBFr` conflict on spending `c2` - `tx_HS` and `tx_LS` conflict on spending `tx_LL:0` - `tx_LL` and `tx_LM` conflict on spending `c1` - `tx_LM` and `tx_RBFr` conflict on spending `c3` `tx_RBFr` would end up slightly bigger and therefore have a bigger fee, but otherwise the number should work out fine as they are. I have not verified this yet (thanks for sharing your code), but I might be able to take another look in the coming week if you haven’t by then. It seems to me that my main point stands, though: the proposed RBFr rules would enable infinite replacement cycles in combination with the existing RBF rules. Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Hi Peter, On 1/22/24 17:52, Peter Todd wrote: An even simpler fix would be to just require that all unconfirmed inputs in a replacement come from the *same* replaced transaction. That would make certain rare, but economically viable, replacements infeasible. But it would definitely fix the issue. The replacements spend at most a single unconfirmed input in my infinite relay cycle example. Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Hi Peter, On 1/18/24 13:23, Peter Todd via bitcoin-dev wrote: > Reposting this blog post here for discussion: > > https://petertodd.org/2024/one-shot-replace-by-fee-rate I saw your proposal mentioned on Stacker News and read it with interest. In response, I described a replacement cycle that can be used to broadcast the same five transactions repeatedly: https://stacker.news/items/393182 The gist is that by using two confirmed inputs and five transactions, you can use RBFr to reduce the absolute fee while raising the feerate to top block levels, then immediately use the current RBF rules to introduce a high-feerate transaction that beats the RBFr transaction but is hampered by a low-feerate parent and not attractive for mining, then use RBF to replace its low-feerate parent, then use the RBFr transaction again to reduce the absolute feerate. Due to the asymmetric replacements, the same transactions can replace each other in that order in every cycle. Please refer to the linked write-up for details, I’ve included weights, fees, and a transaction graph to make my example comprehensible. Among those five transactions, the only transaction attractive for block inclusion would be the small RBFr transaction with a bottom-of-the-next-block feerate. Today, if it were mined it would amount to fees of around 4000 sats every few blocks to make the entire network relay transactions of more than 205,000 vB every few seconds. Given that my example is minimal, it should be possible to further increase bandwidth cost. Assuming that I did not make a mistake, i.e. all the replacements are viable and my scenario is compatible with your proposal, the described One-Shot Replace-By-Fee-Rate proposal would not be safe for deployment on the network. Best, Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Pull-req to remove the arbitrary limits on OP_Return outputs
Hi John, On 2023-08-06 16:35, John Light via bitcoin-dev wrote: is there ever a case where using OP_RETURN to embed data actually results in fewer bytes onchain than embedding the same data using the segwit/taproot witness space Yes, a back-of-the-envelope calculation has me thinking that only payloads of 135 bytes would be cheaper with transcriptions than with nulldata outputs. In detail: An OP_RETURN output has an overhead of 10 bytes: 8 bytes for the amount, and a byte each for output script length and OP_RETURN. An inscription envelope requires a P2TR output and a P2TR scriptpath input as overhead. A P2TR output weighs 43 vB, a cursory glance suggests that the prevalent inscription input seems to be a depth 0 P2TR scriptpath spend where the leaf script consumes a signature via a CHECKSIG to be followed by the payload envelope. Compared to a P2TR keypath spend this adds something like 8 WU for the leaf script and envelope as well as 34 WU for the controlblock. A keypath spend takes 230 WU, so the total overhead of an inscription lands somewhere around 111 vB (the additional ‘ord’ label and meta header with encoding information are considered part of the payload here). After that, the payload gets a discount of 75%. Solving 111 + 0.25*payload_size = 10 + payload_size we learn that nulldata outputs are cheaper up to a payload size of 134 bytes, only above that inscriptions become a more blockspace efficient data carrier. Further, tooling for OP_RETURNs should be more broadly available than software that creates inscriptions, so it seems to me that dropping this limit would make it cheaper to publish certain data payload sizes to the blockchain, and also make publication of larger payloads significantly more accessible. Anyway, it’s not obvious to me why we should relax restrictions on publication mechanisms just because it’s already happening in a different manner (that also only uses blockspace but doesn’t add to the UTXO set). At that point this proposal neither seems to be a trivial mempool policy change, nor a clear or significant improvement. Especially it’s not clear to me, why we should encourage further data publication on the blockchain. On 2023-08-06 16:35, John Light via bitcoin-dev wrote: Are there any tools available that a full node operator could use to prune this data from their nodes? Yes. Running your Bitcoin Core node in prune mode will discard nulldata outputs when it discards the block. On 2023-08-06 16:35, John Light via bitcoin-dev wrote: i) Is the unspendable output pruning implemented in PR #2791 on by default or is this a flag that needs to be enabled by full node operators? If it's a flag, what is the flag called and how can it be enabled? If it's on by default, how can it be disabled? No other special pruning methods beyond pruning of blockchain data have been implemented in Bitcoin Core. Nor am I aware of any that have significant benefits over just pruning blockchain data. On 2023-08-06 16:35, John Light via bitcoin-dev wrote: ii) If a full node operator does prune OP_RETURN outputs, does that in any way impair their ability to help a new node do IBD to validate the blockchain? And would that answer be any different if we were talking about pruning Taproot witness space (i.e. "envelopes" or "inscriptions") instead of OP_RETURN outputs? A transaction from which inscription data or OP_RETURN data has been removed is incomplete and cannot be validated. If a node operator were to discard either data, they would not be able to serve complete blocks and therefore would no longer be able to assist in IBD. Given that the proposal is obviously controversial, and the social media attention this and a few related pull requests have gotten is already causing brigading, I don’t think it’s going to be a priority for me to further engage with this proposal. Cheers, Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] Seeking concept ACKs for transaction terminology BIP
Hey everyone, Over the years, I have participated in a few conversations about various aspects of transactions. Often a chunk of the conversation is spent on establishing a shared vocabulary. There are many competing terms—e.g. I can think of at least three additional terms that refer to `scriptPubKey`. I’ve drafted an informational BIP that proposes terminology for various components and aspects of transactions. As some established terms are already contradictory, the proposal does not aim for a perfectly consistent selection of terms, but rather just to establish a shared vocabulary to avoid confusion. Draft: https://github.com/Xekyo/bips/pull/1 Please let me know whether you’d be interested in the creation of such a BIP. Cheers, Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Refreshed BIP324
Hi Pieter, hello list, On 26.10.22 12:39, Pieter Wuille via bitcoin-dev wrote: 1. The most straightforward solution is using the BIP process as-is: let BIP324 introduce a fixed initial table, and future BIPs which introduce new messages can introduce new mapping entries for it. In theory, this is no worse than the current coordination difficulty about command strings, but in practice the risk of collisions due to competing proposals is of course significantly larger with 1-byte IDs vs. 12-byte strings. From what I understand we'll have about 35 message types on the network with the addition of BIP324. 256 possible IDs sounds like plenty room to grow, but perhaps we can be a bit more conservative: We could use the first bit to signal a 2-byte message ID. That allows us to express 128 IDs with 1 byte, but if we need more, we get a total of 2^15 IDs across 2 bytes. I would not be too concerned about collisions. Firstly, message types would probably be announced to the mailing list as part of the corresponding BIP, secondly, any overlooked collision should become apparent at implementation time. The risk could perhaps be further mitigated by encouraging less prevalent message types to use a 2-byte ID. Cheers, Murch OpenPGP_signature Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Does Bitcoin require or have an honest majority or a rational one? (re rbf) (Jeremy Rubin)
Hello John, On 17.10.22 02:23, John Carvalho via bitcoin-dev wrote: Simply, 0conf acceptance can be monitored and enforced by the merchant and exposure to doublespends can be both mitigated and limited in size per block. It is less expensive to be double-spent occasionally than to have a delayed checkout experience. Responsible 0conf acceptance is both rational and trusting. 29% of all transactions explicitly signal replaceability (see https://transactionfee.info/charts/transactions-signaling-explicit-rbf/), trend rising. If ignoring risk is an acceptable approach now, why would it no longer work when the remaining 71% of transactions also became subject to replaceability? On 17.10.22 02:23, John Carvalho via bitcoin-dev wrote: Now RBF just kinda haunts us as the establishment keeps baking it deeper and deeper into Bitcoin, despite almost no one using it, and despite it having negative consequences on more popular use cases. How can RBF at the same time be hardly used as well as an incalculable risk? Fact of the matter is that one can neither rely on having seen all transactions that miners are considering for their block templates, nor that a replacement be received by the miners before the original is picked into a block. We're between seats: first-seen is an unstable gentlemen's agreement, inevitable to fail eventually once a few defect. Meanwhile propping up the illusion of "reliable payment promises" is hampering price discovery of blockspace and complicating protocol development. By converging on the inevitable outcome and facilitating replaceability for all transactions, we can rip off the band-aid rather than suffer uncertainty indefinitely—even if it requires some to honestly reassess their business approach in light of the natural modus operandi of Bitcoin's gossip system. Cheers, Murch OpenPGP_0xACFDB93A9175DCAB_and_old_rev.asc Description: OpenPGP public key OpenPGP_signature Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] Improvement on Blockbuilding
Hi Bitcoin Devs,
We are writing to share with you a suggested improvement to the current
bitcoin core block building algorithm. In short, currently Bitcoin Core
uses a straightforward greedy algorithm which evaluates each
transaction’s effective fee rate in the context of its unconfirmed
ancestors. This overlooks situations in which multiple descendant
transactions could be grouped with their shared ancestors to form a more
attractive transaction set for block inclusion.
For example, if we have 4 transactions A,B,C, and D, with fee rates and
weights as follows
Tx Fee Weight
A51
B 101
C 151
D 141
And dependencies:
• B is a descendant of A
• C is a descendant of B
• D is a descendant of A
The current algorithm will consider {A,B,C} best which has an effective
fee rate of 10. Our suggested algorithm will also consider {A,B,C,D},
which has an effective fee rate of 11.
Experimental data shows that our suggested algorithm did better on more
than 94% of blocks (99% for times of high congestion). We have also
compared the results to CBC and SAT Linear Programming solvers. The LP
solvers did slightly better, at the price of longer running times. Greg
Maxwell has also studied LP solvers in the past, and his results suggest
that better running times are possible.
The full details are given in this document, and we are happy to hear
any comment, critic or suggestion!
Best,
Mark and Clara
Full details:
https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-building-md
Research Code:
https://github.com/Xekyo/blockbuilding
signature.asc
Description: OpenPGP digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] On-going work: Coin Selection Simulation
Hello Daniel and others, A recent version of my Coin Selection Simulator is now available on my GitHub repository: https://github.com/Xekyo/CoinSelectionSimulator Please feel free to write an email or open an issue on GitHub, if you happen to find errors, have questions about using the simulator, or (especially!) have interesting results running the simulation on your own data. Note that a log and a csv-table with results are posted to the console by the simulator, so you might want to pipe that somewhere. ;) There are probably some inefficiency issues, and user experience improvement opportunities left as I'm currently focusing on my thesis, yet, I've come to the conclusion that some people might be interested in taking a look nonetheless even though I haven't gotten around to polishing the code repository up yet. Regards Murch Am 23.09.2016 um 11:11 schrieb Murch via bitcoin-dev: > Hi Daniel, > > Thank you for your mail. > My simulation of the Mycelium coin selection does add small change > outputs to the fee, but I did get your boundary wrong. > Instead of the 5460, I dropped at the dust boundary which calculates to > 4440 in my simulation. Therefore, I think that the results in the table > might be slightly too big, but likely indicative of the actual Mycelium > behavior. > I've corrected the boundary in my simulation now and will update my > simulation results before Scaling Bitcoin. Thank you very much for your > correction. > > Sorry, the simulation code has not been published yet, I plan to do that > around Scaling Bitcoin or after I turn in my thesis (End of October). I > will let you know when I do. > > It is my understanding that Mycelium doesn't create small change outputs > but rather hardly ever spends them when received. > > You're probably more familiar with the code base (I think you work for > Mycelium?), so please correct me when I'm wrong: > Mycelium appears to select UTXO in a FIFO approach, but, after the > selection, prunes by removing the smallest selected UTXO until the > excess beyond the spending target is minimized. This post-selection step > seems the likely reason for Mycelium's small UTXO build-up. (Bitcoin > Core intermittenly used post-selection pruning also, and apparently this > did cause a similar increase in UTXO set size then.) > > I assume that this will also cause Mycelium to create a huge transaction > every once in a while when this build-up is enough to fund a transaction > without a bigger UTXO being selected. > > As to how it may be mitigated: BreadWallet uses a very similar FIFO > approach, but doesn't prune. My simulation result indicates that their > average UTXO set is much smaller. This has the downside that users could > be spammed with small transaction outputs that they then would pay for > spending. > A balanced approach between these two approaches might be that instead > of pruning all small inputs, a few of the small inputs could be allowed > to be selected to slowly drain low-value UTXO out of the wallet by > spending them over time. In order to avoid the privacy issues such as > e.g. always spending the oldest UTXO, it would for example be possible > to implement this as a 75% probability to prune an unnecessary output. > > Regards > Murch > > Am 22.09.2016 um 11:33 schrieb Daniel Weigl via bitcoin-dev: >> Hi, >> >> Is your simulation code available somewhere? >> >> I was just wondering why mycelium generates a very big UTXO set for >> <1000sat, because change outputs will never be smaller than >> 5460sat (=TransactionUtils.MINIMUM_OUTPUT_VALUE). If the change would be >> lower, it simply is skipped and added to the miner fee: >> -> >> https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/StandardTransactionBuilder.java#L334 >> >> Does your simulation account for that? >> >> It might also be that the small UTXO came from external tx and we never >> spend them, bec. of pruning/privacy. Not sure how we could optimize that. >> >> Cheers, >> Daniel >> >> On 2016-09-21 14:58, Murch via bitcoin-dev wrote: >>> Hi, >>> >>> I'm currently compiling my Master's thesis about Coin Selection and my >>> presentation proposal to Scaling Bitcoin has been accepted. >>> >>> For my thesis, I have analyzed the Coin Selection problem, created a >>> framework to simulate wallet behavior on basis of a sequence of >>> payments, and have re-implemented multiple coin selection strategies of >>> prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and >>> Android Wallet for Bitcoin). >&g
Re: [bitcoin-dev] On-going work: Coin Selection Simulation
Hi Daniel, Thank you for your mail. My simulation of the Mycelium coin selection does add small change outputs to the fee, but I did get your boundary wrong. Instead of the 5460, I dropped at the dust boundary which calculates to 4440 in my simulation. Therefore, I think that the results in the table might be slightly too big, but likely indicative of the actual Mycelium behavior. I've corrected the boundary in my simulation now and will update my simulation results before Scaling Bitcoin. Thank you very much for your correction. Sorry, the simulation code has not been published yet, I plan to do that around Scaling Bitcoin or after I turn in my thesis (End of October). I will let you know when I do. It is my understanding that Mycelium doesn't create small change outputs but rather hardly ever spends them when received. You're probably more familiar with the code base (I think you work for Mycelium?), so please correct me when I'm wrong: Mycelium appears to select UTXO in a FIFO approach, but, after the selection, prunes by removing the smallest selected UTXO until the excess beyond the spending target is minimized. This post-selection step seems the likely reason for Mycelium's small UTXO build-up. (Bitcoin Core intermittenly used post-selection pruning also, and apparently this did cause a similar increase in UTXO set size then.) I assume that this will also cause Mycelium to create a huge transaction every once in a while when this build-up is enough to fund a transaction without a bigger UTXO being selected. As to how it may be mitigated: BreadWallet uses a very similar FIFO approach, but doesn't prune. My simulation result indicates that their average UTXO set is much smaller. This has the downside that users could be spammed with small transaction outputs that they then would pay for spending. A balanced approach between these two approaches might be that instead of pruning all small inputs, a few of the small inputs could be allowed to be selected to slowly drain low-value UTXO out of the wallet by spending them over time. In order to avoid the privacy issues such as e.g. always spending the oldest UTXO, it would for example be possible to implement this as a 75% probability to prune an unnecessary output. Regards Murch Am 22.09.2016 um 11:33 schrieb Daniel Weigl via bitcoin-dev: > Hi, > > Is your simulation code available somewhere? > > I was just wondering why mycelium generates a very big UTXO set for <1000sat, > because change outputs will never be smaller than > 5460sat (=TransactionUtils.MINIMUM_OUTPUT_VALUE). If the change would be > lower, it simply is skipped and added to the miner fee: > -> > https://github.com/mycelium-com/wallet/blob/master/public/bitlib/src/main/java/com/mrd/bitlib/StandardTransactionBuilder.java#L334 > > Does your simulation account for that? > > It might also be that the small UTXO came from external tx and we never spend > them, bec. of pruning/privacy. Not sure how we could optimize that. > > Cheers, > Daniel > > On 2016-09-21 14:58, Murch via bitcoin-dev wrote: >> Hi, >> >> I'm currently compiling my Master's thesis about Coin Selection and my >> presentation proposal to Scaling Bitcoin has been accepted. >> >> For my thesis, I have analyzed the Coin Selection problem, created a >> framework to simulate wallet behavior on basis of a sequence of >> payments, and have re-implemented multiple coin selection strategies of >> prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and >> Android Wallet for Bitcoin). >> >> As the Scaling Bitcoin site suggests that research should be made >> available to this mailing list, I would like to invite you to have a >> look at: >> >> http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf >> >> The PDF (176 kB) contains a two page description of my on-going work, >> including preliminary simulation results, and three figures showing the >> simulated wallets' UTXO compositions at the end of the simulation. >> >> I can provide further information as requested, and would welcome any >> feedback. >> >> →→ If anyone has another sequence of incoming and outgoing payment >> amounts at hand that I could run my simulation on, I'd love to hear >> about it. >> >> Regards >> >> Murch >> >> >> >> >> ___ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] On-going work: Coin Selection Simulation
Hi, I'm currently compiling my Master's thesis about Coin Selection and my presentation proposal to Scaling Bitcoin has been accepted. For my thesis, I have analyzed the Coin Selection problem, created a framework to simulate wallet behavior on basis of a sequence of payments, and have re-implemented multiple coin selection strategies of prominent Bitcoin wallets (Bitcoin Core, Mycelium, Breadwallet, and Android Wallet for Bitcoin). As the Scaling Bitcoin site suggests that research should be made available to this mailing list, I would like to invite you to have a look at: http://murch.one/wp-content/uploads/2016/09/CoinSelection.pdf The PDF (176 kB) contains a two page description of my on-going work, including preliminary simulation results, and three figures showing the simulated wallets' UTXO compositions at the end of the simulation. I can provide further information as requested, and would welcome any feedback. →→ If anyone has another sequence of incoming and outgoing payment amounts at hand that I could run my simulation on, I'd love to hear about it. Regards Murch signature.asc Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
