[bitcoin-dev] BIP draft: BIP32 Path Templates

2020-07-02 Thread Dmitry Petukhov via bitcoin-dev
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

2020-07-02 Thread ZmnSCPxj via bitcoin-dev
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

2020-07-02 Thread Oded Leiba via bitcoin-dev
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

2020-07-02 Thread Tejaswi Nadahalli via bitcoin-dev
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

2020-07-02 Thread Tejaswi Nadahalli via bitcoin-dev
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