[bitcoin-dev] BIP draft: BIP32 Path Templates
I think there should be standard format to describe constraints for BIP32 paths. I present a BIP draft that specifies "path templates" for BIP32 paths: https://github.com/dgpv/bip32_template_parse_tplaplus_spec/blob/master/bip-path-templates.mediawiki Matching against these templates allow to easily discern 'valid' paths, that match the constraints, and 'invalid' paths, that exceed the constraints. Extended motivation is given at the end of this message, and in the text of the BIP draft. A formal spec in TLA+ of a finite state machine implementing the parser for the described format (and the matching operation) accompanies this BIP draft: https://github.com/dgpv/bip32_template_parse_tplaplus_spec This formal spec can be used with TLC model checker and a helper script to generate thorough test data for implementations. One (python) implementation of template parsing and matching already exists (linked in the BIP draft). Examples of the templates: "m/[44,49,84]'/0'/0'/[0-1]/[0-5]" specifies a full template that matches both external and internal chains of BIP44, BIP49 and BIP84 paths, with a constraint that the address index cannot be larger than 5 "[0-2,33,123]/*" specifies a partial template that matches non-hardened values 0, 1, 2, 33, 123 as first index, and any non-hardened value at second index "*h/0" specifies a partial template that matches any hardened index followed by any non-hardened index Motivation: BIP32 derivation path format is universal, and a number of schemes for derivation were proposed in BIP43 and other documents, such as BIPs 44,45,49,84. The flexibility of the format allowed industry participants to implement custom derivation shemes that fit particular purposes, but not necessarily useful in general. Unrestricted derivation path usage might be unsafe in certain contexts. In particular, when "change" outputs of a transaction are sent to the addresses derived via paths unknown to the sender, the sender might loose access to the whole change amount. A simplistic approach of hard-coding the checks for well-known paths into software and firmware leads to reduced interoperability. Vendors cannot choose custom paths that are appropriate for their particular, non-general-purpose applications, and are forced to shoehorn their solutions into using well-known paths, or convince other vendors to support their custom paths. This approach scales poorly. A flexible approach proposed is to define a standard notation for "BIP32 path templates" that succintly describes the constraints to impose on the derivation path. Wide support for these path templates will increase interoperability and flexibility of solutions, and will allow vendors and individual developers to easily define their own custom restrictions. This way, they will be able to deal with the risks of accidental or malicious use of unrestricted derivation paths in a more flexible and precise manner. Well-known path templates can be pre-configured by default on devices and applications, but users can have an option to turn off the templates that are not relevant to their uses. Having standardized format for custom path templates will enable a common approach to be developed to the enforcement of application-specific path restrictions in devices and applications. One example of such approach might be for devices to allow to install application-specific profiles with path templates and possibly other custom parameters. Care must be taken to prevent accidental installation of malicious or incorrect profile, though. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MAD-HTLC
Good morning Tejaswi, > > So it looks to me that scorched-earth is a possible mitigation against this > > attack. > > I don't follow this. We show that a reasonable value of fees and timelock are > enough to avoid the attack. Why scorch the earth? Because your model only considers that a block might have only 0 or 1 transactions, and there is no such thing as a mempool containing alternative, fee-paying transactions that the miner could include *instead*. In reality, what a miner can earn from adding Alice transaction is the *difference* between the Alice transaction fee and the transaction that *just* misses getting included in the block because of feerate. Thus, the f will not, in fact, *quite* be the Alice fee, but instead less than that. Indeed if the Alice transaction fee is lower than the top 4 Mweight transactions in the mempool, the miner would be *losing* funds by including the Alice transaction. My understanding is that we expect mempools to eventually never empty, as the block subsidy reduces over time, thus the payoff f for including the Alice transaction *instead of* some other transaction will be less than the Alice fee. This effect also holds for Bob, but we can probably expect, all things being equal, that approximately the same value will be deducted from both the Bob bribe and Alice fee by the mempool effect. Thus the ratio should really be (f - x) / (b - x), where x is the fee-of-transaction-that-just-misses-the-block. At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be far smaller than f / b and might even become negative, in which case the Alice transaction will not be confirmed even by myopic miners, because the Alice transaction will be below the top 4Mweight transactions in the mempool. So it seems to me reasonable to use a *gradual* scorched earth policy, as it is not only resilient against this attack, but also to fee spikes. Alice starts at the 1% reserve, then for every block that goes by, bumps up the fee. Then Alice will settle at an (f - x) / (b - x) level that achieves the least weak miner that is known to run the myopic strategy. I believe this is also better for UX --- people already accept that during high fee spikes, they end up paying more for onchain activities. But boosting up `to_self_delay` is bad because it makes honest unilateral closes take longer, and we already get frownie faces from users about this parameter. By using a gradual scorched-earth strategy we can start at the reserve level, and if we are not under attack and there is no fee spike, do not lose anything other than the reserve funds of the thief (which is not ours, but is instead that of the thief). But if an attack happens during a fee spike, then even though we retain our current default `to_self_delay` of 144, we still have the ability to gradually and automatically move to higher fee regions until our transaction confirms, and we have a good excuse for it to present to users: "a fee spike was happening at the time, so you had to pay some extra miner fees". And since you and your paper openly discusses it anyway, I would like to reveal that the MAD-HTLC argument does not apply to *just* HTLCs. You make recommendations about `to_self_delay` and `channel_reserve_satoshis`, which are not parameters of Lightning HTLCs (those are stuff like `cltv_delta` and `final_cltv`), but are channel parameters. The MAD-HTLC argument applies just as well to channel mechanisms themselves, ***independently of*** any HTLCs they transport. The MAD-HTLC paper has the following core argument: * We currently assume that currently-valid transactions will inevitably supersede alternate transactions that are valid at a later block height, simply because of the time advantage. * However, the owner of a later-block-height transaction can bribe miners to defer confirmation of currently-valid transactions, until its later-block-height transaction is valid and confirms. The above core argument is presented as applying to HTLCs. However, the same argument actually **also** applies to all current offchain multiparticipant cryptocurrency systems (i.e. "channel mechanisms"). * Spilman * Poon-Dryja (what we currently use in Lightning) * Decker-Wattenhofer decrementing-`nSequence` * Decker-Russell-Osuntokun The [Khabbazian-Nadahalli-Wattenhofer "Timelocked Bribing" paper](https://eprint.iacr.org/2020/774.pdf) mentions the use of revoked transactions in a Poon-Dryja mechanism, but seems to imply that the issue is with the HTLC instantiated inside the revoked transaction. But note that the paper describes recommendations for the `to_self_delay` parameter and also analyzes the `channel_reserve_satoshis` parameter, which are parameters of the ***Poon-Dryja*** mechanism, and **not** of the HTLCs instantiated inside it. So, to be very clear, the MAD-HTLC argument applies to all the above mechanisms *even if HTLCs are not used at all*. Or put anot
[bitcoin-dev] Tool for checking a wallet's handling of reverted 0-conf transactions
As was disclosed today, several wallets have been found not to handle well the scenario of reverted transactions at zero confirmations. This includes showing an increased balance to the user without decreasing it when a transaction is replaced and also preventing the user from being able to spend other valid coins. You can test the behavior of your own wallet (either that you use or develop) and read more about it in this new tool: https://github.com/KZen-networks/big-spender Oded ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MAD-HTLC
On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj wrote: > And your paper posits that if a miner is weak, its best strategy is to > take the myopic strategy and include the currently-valid Alice transaction. > Yes. The proof is quite trivial and follows from the definition of weak: if the myopic miner's hashpower percentage is p_i, and it's lower than f/b, that means that f > b*p_i. By including the currently-valid Alice transaction, the myopic miner could make f, which is higher than their expected gain, which is b*p_i. The myopic miner has a p_i chance of mining the first block when Bob's transaction becomes valid, and it's most likely to stay valid for just 1 block, as every miner would want that immediately when it gets valid. This is where we disagree with the MAD-HTLC paper. They assume that there are not any miners with sub-1% hashrate around. We find that there are many such miners, and with channel_reserve_satoshi set to 1% of the channel value, Alice can bump her fees to at least 1% of the channel value without worry (because she will get Bob's channel_reserve_satoshi's for herself if Bob is cheating by releasing a previous commitment TXN). We additionally also show that when strong miners know that weak miners are around, some of their strategies get dominated as well, and they will be forced to include Alice's transaction as well. This, if there is just one *known* weak miner, things are good for Alice. As an FYI, in our paper Alice is the cheater and Bob is the victim. There were reasons to "reverse the convention", so to speak - but that's for another day :-) > > Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is > 1.0 implying a miner can only be powerful if it has already 51%-attacked > Bitcoin (which tends to invalidate all our security assumptions of > higher-layer protocols anyway, since a 51% attacker can censor anything > with impunity). > We assume that Bob will bribe with the entire channel value - because he has received commensurate goods and services off-chain. So, Alice will find it difficult to match Bob's bribe, but she doesn't have to. > > Of course, Bob can offer up to the entire fund amount, for free, to miners > as a bribe, without loss to Bob. > Yes. Precisely. > > For more realistic scenarios where no miner has 100% hashrate, then Alice > can make all miners weak by being willing to pay up to 50% of the fund as > fee, as a miner that achieves greater than 50% hashrate share would already > effectively pwnzored Bitcoin and gained UNLIMITED POWAH anyway. > But she doesn't have to go as far as 50%. Just 1% seems quite reasonable, given a reasonable timelock. We have a closed form solution for the timelock T as well. In Lightning's case, with 1% channel_reserve_satoshis around, we arrive at T = 316, which is much longer than the current default of 144. > > So it looks to me that scorched-earth is a possible mitigation against > this attack. > I don't follow this. We show that a reasonable value of fees and timelock are enough to avoid the attack. Why scorch the earth? ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] MAD-HTLC
On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj wrote: > Another analysis, similar but a little off-tangent to yours, would be to > consider miners as a breeding group with various strategies, and see which > one is able to gain more utilons (with which it creates more miners) and > outbreed the other miners. > > This models the fact that miners can use their earnings to reinvest into > their mining operations and increase their mining hashrate, and the amount > they can reinvest is proportional to their earnings. > A miner that "gives birth" to a child miner with the same strategy is, in > the so-called "real world", simply a miner that has earned enough and > reinvested those earnings to double the hashrate of their business (which, > logically speaking, would use the same strategy throughout the entire > business). > > Let us start with a population of 4 miners, 3 of which follow the > non-myopic strategy, and the remaining following the myopic strategy. > Let us postulate that all miners have the same unit hashrate. > Thus, this starting population is 75% non-myopic, 25% myopic. > > If there exists a timelocked bribe, then if non-myopic miner is chosen at > a block, it will have to sacrifice the Alice fee minus whatever lesser > transaction fee it can replace in its block. > If the Alice transaction is successfully delayed until the Bob transaction > is valid, then the non-myopic miners can get the Bob transaction confirmed. > > However, even in the case that the Alice transaction is delayed, the > myopic miner still has its 25% chance --- equal to the 25% chance of the > three non-myopic miners --- to confirm the Bob transaction and earn the > increased bribe that Bob offers. > > Thus, the non-myopic miners can end up sacrificing fee earnings, and in > the end the myopic miner still has the 25% chance to get the Bob > transaction fee later when it becomes valid. > So the non-myopic miners do not impose any loss on myopic miners. > > On the other hand, if the non-myopic miners sacrificed their chances to > include the Alice transaction in the hope of getting the later 25% chance > to get the Bob higher-fee timelocked transaction, and then the myopic miner > gets the next block, the myopic miner gets the Alice transaction confirmed > and the 25% chance to get the Bob higher fee is lost by the non-myopic > miners. > Thus, the myopic miner is able to impose costs on their non-myopic > competitors. > > So even if by chance for the entire locktime, only the non-myopic miners > are selected, the myopic miner still retains its 25% chance of getting the > block at locktime + 1 and confirming and earning the bigger Bob fee. > > Thus, we expect that the myopic miner will earn more than 25% of subsidies > and fees than the non-myopic miners, in such a mixed environment. > This is exactly our analysis, and is covered in section 2.5 of our paper. We formalize the ideas a bit more, and are able to relate the values of Alice-fee, Bob-bribe, timelock, and miner's hashpower percentage. We go a bit further into #reckless territory as well - reducing the timelock value to super low values. That's in Algorithm #1 of our paper, and is a bit more involved. > > We can then consider that the myopic miner, being able to earn more, is > able to increase its progeny (i.e. expand its mining business and inspire > new miners to follow its strategy towards success) faster than the > non-myopic miners. > > We can thus conclude that the myopic miners will eventually dominate over > the breeding population and drive the non-myopic miners to near-extinction. > This is an interesting direction that we chose to not look at. Like the MAD-HTLC authors, we assume a constant hash-rate distribution across time, which is obviously not a great assumption. It might work in the local context of an HTLC's timelock, but in our approach, we are also interested in *weak* miners, and finding them across 1000's of blocks might get tricky. > It is helpful to remember that rationality is about success *in the > universe you exist in*. > While miners may step back and consider that, ***if*** all of them were to > use non-myopic strategy, they would all earn more, the fact of the matter > is that each miner works for themselves, and themselves alone, in a highly > competitive environment. > Thus, even though they know *all of them* will benefit if they use the > non-myopic strategy, they cannot be sure, unless they are all perfectly > synchronized mind-clones of each other, that the other miners will rather > be selfish and mine for themselves, even if in the end every miner earns > less > The standard for success is to earn more *than your competitors*, not > ensure that *every* miner earns more. > > Fortunately, since miners are running a business, this competition leads > to better services to the the customers of the mining business, a known > phenomenon of the free market, yay free market greed is good. > The user Alice is a customer of the mining bus
