Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

В Fri, 3 Jul 2020 21:53:44 +0500
Dmitry Petukhov via bitcoin-dev 
wrote:

> The format for the path templates described in the presented BIP draft
> aims to provide a building block for interoperability between various
> hardware and software vendors in regard to this particular task of
> specifying derivation path restrictions.

One example of an interoperability workflow might be:

A software vendor that utilizes custom derivation paths in their
schemes create a "profile" that contains the constraints on the paths
(and possibly other parameters, but this is out of scope of the
proposal) for their particular scheme. In a simple case it might just
be a path template string provided in the documentation.

A user of a software solution from that vendor takes a hardware wallet
that supports path templates (or richer "profiles") and installs the
profile for that solution into hardware wallet. In a simple case, the
user just pastes a path template string into some configuration utility
program and then confirms the setting on-device.

The device statrts to enforce the constraints specified in the template
(or "profile"), and the software solution works as intended by the
software vendor.





pgp0EDjFTpNgy.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov via bitcoin-dev]

IIUC, key origin identification specify chains of addresses, with
relation to specific keys. As the name suggests, they are for
identidication.

Path templates specify application-specific constraints for the
derivation paths. They are for imposing restrictions.

You could use path templates for identification, too, and in fact the
"path" part of the key origin identification would be a valid path
template. Path templates have potential to identify multiple chains
of addresses though, and I cannot say how useful it can be, if at all.

When a hardware wallet or some other type of autonomous signer signs a
transaction, there are two points where HD derivation can occur: 1) when
signing an input 2) when checking if the output is the change output

The second case is occurs more often, I think (determining actual
amount sent), but the first case can have uses, too -- when an
autonomous signer can impose restrictions on derivation path based on
the identity of the user that request the signing, for example. 

In both of these points an application-specific or usecase-specific
signing scheme might require that only certain whitelisted derivation
paths are used (sending change to the known key, but using derivation
path unknown to the sender allows an attacker to hold the change amount
for ransom, for example)

An autonomous signer might not be aware of the restrictions used in
particular scheme, because it might be developed by different vendor
than the implementor of the particular scheme. Or it might be difficult
to update the firmware of autonomous signer when the checks of the
path constraints are hard-coded in the program code. Having constraints
specified as data would allow to place them in configuration of the
signer.

One particular example of this being a problem is how hardware wallet
vendors seem to be inclined to decide to just restrict the derivation
paths allowed for the change addresses to the set of "well-known"
paths.

Such restrictions, on one hand, break custom schemes used by
various software solutions that rely on the ability of hardware wallet
to sign custom paths, and on the other hand, such hardcoded restrictions
might happen to be too relaxed, if the set of "well-known" path grows,
or the user or software vendor knows for sure that they won't use
addresses past index 1000, for example.

The format for the path templates described in the presented BIP draft
aims to provide a building block for interoperability between various
hardware and software vendors in regard to this particular task of
specifying derivation path restrictions.

Adopting a common format for specifying restictions is a flexible
alternative to everyone adopting a rigid set of "well-known" paths.
Such a set will inevitably grow, and those who really need custom
paths and do not have resources to push for standardization of their
custom paths will be at a disadvantage.

My hope is that having a clear specification and (possibly, in the
future) permissibly licensed quality implementations would make
adopting such format easier for vendors.

В Fri, 3 Jul 2020 10:39:45 -0400
"David A. Harding"  wrote:

> On Thu, Jul 02, 2020 at 09:28:39PM +0500, Dmitry Petukhov via
> bitcoin-dev wrote:
> > 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
> >  
> 
> Hi Dmitry,
> 
> How do path templates compare to key origin identification[1] in
> output script descriptors?
> 
> Could you maybe give a specfic example of how path templates might be
> used?  Are they for backups?  Multisig wallet coordination?  Managing
> data between software transaction construction and hardware device
> signing?
> 
> Thanks,
> 
> -Dave
> 
> [1]
> https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md#key-origin-identification
> (See earlier in the doc for examples)



pgpApkPHbWTwY.pgp
Description: Цифровая подпись OpenPGP
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[David A. Harding via bitcoin-dev]

On Thu, Jul 02, 2020 at 09:28:39PM +0500, Dmitry Petukhov via bitcoin-dev wrote:
> 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

Hi Dmitry,

How do path templates compare to key origin identification[1] in
output script descriptors?

Could you maybe give a specfic example of how path templates might be
used?  Are they for backups?  Multisig wallet coordination?  Managing
data between software transaction construction and hardware device
signing?

Thanks,

-Dave

[1] 
https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md#key-origin-identification
(See earlier in the doc for examples)


signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Ittay,

> Hi all,
>
> Itay from MAD-HTLC here. I feel like some details got lost along the way so 
> please let me get these sorted out.
>
> 1. Myopic and non-myopic miners:
> When we use the term myopic we mean a miner that optimizes transaction 
> selection for the next block with respect only to the next block. The term 
> non-myopic refers to a miner that optimizes transaction selection for the 
> next block with respect to several future blocks. To accommodate for the 
> stochastic nature of block creation these optimizations are of the expected 
> revenue. However, neither of these mean that these miners choose to act in a 
> way that reduces their expected revenue -- specifically, if from a 
> non-myopic's miner perspective including Alice's immediate transaction is 
> better off than waiting for Bob's future transaction, then this is what they 
> do.
>
> Consequently, saying that "being myopic" dominates "being non-myopic" is 
> incorrect -- myopic is included in being non-myopic, thus cannot be better 
> than it.

The term "dominates" here is a technical term in game theory.

A strategy dominates over another strategy if, in a mixed environment, the 
first strategy always wins more points than the second strategy, no matter what 
proportion they may initially start in the mixed environment.

For example, in an environment of prisoner dilemma games, a tit-for-tat 
strategy dominates over the always-betray strategy, which dominates over 
always-cooperate strategy.

The above is the use of the term "dominate", and not that somehow one strategy 
"contains" the other.
Always-betray does not contain always-cooperate.

It is immaterial that the non-myopic "contains" myopic strategy as a 
sub-strategy.
Sometimes, overriding a sub-strategy can lead to worse outcomes and you are 
better off sticking to the sub-strategy rather than an extended strategy that 
sometimes overrides the sub-strategy

(notice how mixed teams of computer+human are no longer dominant in chess, 
because computer chess AIs are now so sophisticated that on average, the human 
overriding the computer strategy often leads to worse outcomes than just 
following the computer; yet about a decade ago such mixed computer+human teams 
were dominant over pure-computer and pure-human teams; yet you could say the 
same, that the computer+human "includes" the pure-computer strategy, but 
nowadays does ***not*** dominate it).

Or: worse is better.


What matters is, if you make them compete in an environment, myopic strategies 
will consistently beat non-myopic strategies because the myopic miners will 
impose costs on the non-myopic miners.


>
> So, the next issue to address is estimation of how much of the hash rate is 
> actually non-myopic. Currently that answer is simple -- probably 0. Bitcoin 
> Core (97% of the blocks) doesn't offer these optimizations, and most likely 
> other clients do not have these as well. But, we showed this is rather 
> trivial to implement (150 LoC in Bitcoin Core), and theoretically can be 
> included in Core's next version AFAIK. Moreover, any miner can simply apply 
> our patch independently, achieving the same effect.
>
> Please note more elaborate optimizations are in miners' best interest, 
> especially as mining incentives transition from block minting to fees -- the 
> latter are becoming the main income source, and I believe less sophisticated 
> miners will miss out substantially. You can check out Phil Daian's paper 
> about front-running in Ethereum for example: https://arxiv.org/abs/1904.05234

Yes, but again: myopic strategies dominate over non-myopic strategies, thus 
implementing non-myopic strategies is pointless, since they will lose revenue 
in an environment where even a single miner is myopic.

It is immaterial that it takes only 150 LoC to implement non-myopia: if it 
earns less money in an environment where even a minority of blocks are created 
by myopic miners (much less 97%), nobody will use the non-myopic strategy and 
they will remain at negligible near-0% hashrate.

As they say, "you can't get to there from here".


> As common in game-theory papers, our analysis does assume Common Knowledge -- 
> all participants know all other participants, their available strategies and 
> utilities (Tejaswi et al.'s paper makes the same assumption). As commented 
> before, true, this is not always the case -- nodes might have different 
> mempools, and some might not have applied the optimization patch and act 
> myopically. Such miners are therefore "resisting" the attack -- as stated, by 
> including Alice's transaction they ruin other miners' potential profit from 
> Bob's high fee transaction.

The only additional assumption you are missing is that miners care about 
*themselves* and not about *all miners*.

Non-myopia may earn more money for *all* miners if *all* miners use it, but if 
a *single* miner starts using myopic strategies in a non-myopic environment, 
they will earn more

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Fri, Jul 3, 2020 at 12:17 PM ZmnSCPxj  wrote:

>
> > In fact, one rule of thumb might be that wherever watchtowers are
> required, a timelocked bribe might be possible.
>
> I think a better heuristic is that, if the logic of the construction
> assumes "transaction with earlier locktime supersedes transaction with
> later locktime", then it is timelocked-bribery-vulnerable.
>

That's true by definition. Timelocked bribes are, well, going to be
possible when there are timelocks. I was going more for an "indirect clue"
that wherever a watchtower is proposed, a timelocked bribe is possible.
This is entirely a pedantic point :-)
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] MAD-HTLC

[ZmnSCPxj via bitcoin-dev]

Good morning Tejaswi,



> > 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".
>
> Agree on the UX. There is a tradeoff between the timelocked value of the 
> channel balance to Alice during benign vs malicious abandonment by Bob. In 
> your opinion, increasing the fees beyond 1% (and thereby cutting into Alice's 
> share itself) is a slightly better tradeoff than increasing to_self_delay. 

Currently, we say `to_self_delay` is a parameter of how long you can be 
offline, and is imposed on your counterparty (so its effect on you is to allow 
the counterparty to safely be offline for that long).
This explanation seems palatable to users; they understand that it is the 
counterparty which is asking this of them, and that they ask a similar number 
of their counterparty, which is also their own protection.

On the other hand, we do not really expect to get beyond 1% unless we are under 
attack, *or* the fee spikes are really, really bad.
So this seems a practical tradeoff for us over in Lightning-land.


> > 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.
>
> We know. Maybe we should have made it clear in the paper that when we use the 
> Poon-Dryja channel construction, we use the idea that the knowledge of the 
> preimage of a hash is equivalent to knowing the private key of the revocation 
> public key. In fact, this is how the Poon-Dryja construction is explained in 
> McCorry's Ph.D thesis, and IMHO is easier to understand than the original 
> description in the Poon-Dryja paper (or Bolt #3, for that matter). 

Yes, I realized it a little after reading MAD-HTLC that it applied to all the 
other known channel mechanisms as well, not just HTLCs, and decided to 
investigate this topic further, and have been circumspect regarding this.

> You could further argue that the hashlock is an incidental artefact, and our 
> paper mostly refers to timelocked transactions. And the rest of your email 
> describes applications of timelocked (and obviously presigned) transactions, 
> which are all vulnerable to the same bribing attack. Additionally, the 
> Wattehnofer in our paper is the same Wattenhofer from the Duplex Channel 
> paper.

Yes, I agree that the hashlock is an incidental artefact.

What MAD-HTLC questions is our assumption that a valid transaction with an 
earlier locktime supersedes a valid transaction spending the same txout with a 
later locktime.
Whether it involves presigned transactions or hashlocks are incidental 
artefacts.
So for example, a SCRIPT `OP_IF  OP_ELSE <1 day> OP_CHECKSEQUENCEVERIFY 
OP_DROP  OP_ENDIF OP_CHECKSIG` would also be vulnerable to the MAD-HTLC 
argument.

(Indeed, BOLT spec uses something very much like that script, now that I look 
at it again; in our case the `` is a combination of keys from both parties, 
that cannot be signed with unless one party knows both sub-keys.)

>
> > My current analysis suggests that in practice, the MAD-HTLC argument does 
> > not apply at all (else I would not be revealing that all channel mechanisms 
> > are broken **if** the MAD-HTLC argument *does* apply), since the myopic 
> > strategy seems to be pretty much inevitably dominant at stable states.
>
> We agree. 
>  
>
> > But it would still be best to investigate further until we are fully 
> > convinced that the MAD-HTLC argument ("'earlier supersedes later' might be 
> > falsified by bribery") does not apply.
>
> I think this is the analysis our paper does, and perhaps it's our mistake 
> that we do not set the context better. We only mention (and propose fixes 
> for) Poon-Dryja channel construction, and Tier Nolan's Atomic Swap 
> construction. 
>
> We could have addressed Spilman's one-way channels or Decker-Wattenhofer 
> duplex channels, but that would have been pointless as they were never going 
> to make it into production after Poon-Dryja and subsequently, Eltoo were 
> proposed.

I suggested that, until `SIGHASH_ANYPREVOUT` gets enabled, the 
Decker-Wattenhofer construction (removing the duplex Spilman-like channels at 
the end and leaving just the decrementing-`nSequence` constructions) could be 
used for Ruben Somsen StateChains, so you might not want to dismiss that so 
readily.

The decrementing-`nSequence` mechanisms have the advantage that it does not 
require a punishment/revocation branch, similar to Decker-Russell-Osuntokun 
"eltoo", and thus would work just as well to implement statechains, at least 
until all the debates around `SIGHASH_ANYPREVOUT` settle and it gets deployed.

Similarly, the proposed CoinPool as well could be implemente

Re: [bitcoin-dev] MAD-HTLC

[Tejaswi Nadahalli via bitcoin-dev]

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj  wrote:

> 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.
>

I agree. The MAD-HTLC authors actually keep the base fee in their
calculations, and we deliberately decided to ignore this. We believe that
this base fee to be much lower than the typical 1% channel balance, and it
actually doesn't change any of our results. This was brushed under the
"without loss of generality" rug. I admit that we should have made this
clear in our Assumptions section though. Point taken.


> 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".
>

Agree on the UX. There is a tradeoff between the timelocked value of the
channel balance to Alice during benign vs malicious abandonment by Bob. In
your opinion, increasing the fees beyond 1% (and thereby cutting into
Alice's share itself) is a slightly better tradeoff than increasing
to_self_delay.


> 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.
>

We know. Maybe we should have made it clear in the paper that when we use
the Poon-Dryja channel construction, we use the idea that the knowledge of
the preimage of a hash is equivalent to knowing the private key of the
revocation public key. In fact, this is how the Poon-Dryja construction is
explained in McCorry's Ph.D thesis
, and IMHO is easier to
understand than the original description in the Poon-Dryja paper (or Bolt
#3, for that matter).

You could further argue that the hashlock is an incidental artefact, and
our paper mostly refers to timelocked transactions. And the rest of your
email describes applications of timelocked (and obviously presigned)
transactions, which are all vulnerable to the same bribing attack.
Additionally, the Wattehnofer in our paper is the same Wattenhofer from the
Duplex Channel paper.

My current analysis suggests that in practice, the MAD-HTLC argument does
> not apply at all (else I would not be revealing that all channel mechanisms
> are broken **if** the MAD-HTLC argument *does* apply), since the myopic
> strategy seems to be pretty much inevitably dominant at stable states.
>

We agree.


> But it would still be best to investigate further until we are fully
> convinced that the MAD-HTLC argument ("'earlier supersedes later' might be
> falsified by bribery") does not apply.
>

I think this is the analysis our paper does, and perhaps it's our mistake
that we do not set the context better. We only mention (and propose fixes
for) Poon-Dryja channel construction, and Tier Nolan's Atomic Swap
construction.

We could have addressed Spilman's one-way channels or Decker-Wattenhofer
duplex channels, but that would have been pointless as they were never
going to make it into production after Poon-Dryja and subsequently, Eltoo
were proposed. But not addressing Eltoo in the paper is an omission that I
am a bit upset about. We additionally do not address more sophisticated
atomic swaps from Somsen or Fournier. Nor do we address Kanzure's vault
proposal. In fact, one rule of thumb might be that wherever watchtowers are
required, a timelocked bribe might be possible.

And again, thanks for the detailed analysis.

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj  wrote:

> 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