public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Robert Spigler <RobertSpigler@protonmail.ch>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Cc: SomberNight <somber.night@protonmail.com>
Subject: Re: [bitcoin-dev] Signature and Script Independent Hierarchy for Deterministic Wallets.
Date: Thu, 18 Mar 2021 20:44:48 +0000	[thread overview]
Message-ID: <oIgV5u9J6iyoWCDtouomT3mNi6D5cxXjOgIWNYiZ_uQIqd2FksfvkIDvAEbdE9L37tAIGAC3QUxzyfBrDYtleBEX80WAO7O6CQNjniE6Omc=@protonmail.ch> (raw)
In-Reply-To: <CANYHNmJsiho0SxUUe7pmpQkkd-xAMnc2H8yHsGB_Urd9dw3usg@mail.gmail.com>

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

Please keep comments in the ML. That way it can be archived, seen be anyone interested in the proposal, and have as much review and improvements as necessary/possible. The ML isn't taproot activation discussion only :)

For summary:

David Harding commented to Craig's post:

[Replying off list as I'm not sure this is an important point and the
list is already noisy these days.]

On Wed, Mar 17, 2021 at 09:26:50AM +0200, Craig Raw via bitcoin-dev wrote:
> I think it's important to note that [not encoding the script type in
> the derivation path] shifts more burden of wallet backup onto the
> user, who now has an additional item (the output descriptor) to backup
> correctly.

I don't think that's correct. Most wallets today that allow you to
restore with just a seed by deriving the keys for that seed in the BIP32
paths the wallet supports (i.e, including the purpose field) and then
scanning for outputs paying addresses derived from those keys.

If you try entering your seed into a different wallet (or one that's not
maintaining backwards compatibility with earlier versions of itself), it
won't necessarily support the same addresses you used earlier and so may
not work even if it fully supports BIP44 in principle. You'll need to
use different software and may need to tell that software the addresses
and paths your previous software used.

Under this proposed standard, I don't think any of that changes. If you
try to restore a seed into the same wallet that created it, it can scan
for the address types it supports. A different or
backwards-incompatible wallet may not work and you may need to find
software that can handle your old address type and specific path
information, which descriptors (and miniscript) makes easier.

The way I see it, there's not really a change to the information the
user needs to record for the normal case (seed phrase + name of software
used) or the unusual case (seed phrase + address types + paths).

Where I think this new proposal excels is in handling multisigs, where
the user needs to record the other signers' keys anyway. In those
cases, the fairly small overhead of descriptors compared to a minimalist
encoding is worth descriptor's benefits of providing an error detection
code and BIP32 fingerprints/paths that allow key location.

> 2. Use a standard set of derivation paths that encode the script type,
> ensuring that even if users do not back this up, they can check against a
> handful of common derivations and recover the funds.

I think the scanning work in this case is the same whether you use
descriptors or not.

- Under the current BIP44-style paths, a wallet that supports P2PKH and
P2WPKH with a single account and a gap limit of 50 needs to scan:

pkh([deadbeef/44'/0'/0'/0/0])
pkh([deadbeef/44'/0'/0'/0/1])
pkh([deadbeef/44'/0'/0'/0/...])
pkh([deadbeef/44'/0'/0'/0/49])

wpkh([deadbeef/84'/0'/0'/0/0])
wpkh([deadbeef/84'/0'/0'/0/1])
wpkh([deadbeef/84'/0'/0'/0/...])
wpkh([deadbeef/84'/0'/0'/0/49])

- Under the proposed standard, a wallet that suports P2PKH and P2WPKH
with a single account and a gap limit of 50 needs to scan:

pkh([deadbeef/XY'/0'/0'/0/0])
pkh([deadbeef/XY'/0'/0'/0/1])
pkh([deadbeef/XY'/0'/0'/0/...])
pkh([deadbeef/XY'/0'/0'/0/49])

wpkh([deadbeef/XY'/0'/0'/0/0])
wpkh([deadbeef/XY'/0'/0'/0/1])
wpkh([deadbeef/XY'/0'/0'/0/...])
wpkh([deadbeef/XY'/0'/0'/0/49])

It's essentially the same amount of work in either case. (It's
technically less work under the new standard as you only need to derive
the set of keys once---but since the actual scanning process typically
takes many orders of magnitude longer than key derivation, this doesn't
matter.)

There is a one-time cost of transaction, where wallets that previously
supported BIP44-style purposes and switch to the new proposal need to
scan both sets of paths. That can be avoided if the new paths are only
implemented for new address types (e.g. wallet previously supported
P2PKH with 44', P2WPKH with 84', but now the wallet adds P2TR support
with XY').

-Dave

***********

To which ghost43 replied:

Hi Dave,

>> 2. Use a standard set of derivation paths that encode the script type,
>> ensuring that even if users do not back this up, they can check against a
>> handful of common derivations and recover the funds.
>
> I think the scanning work in this case is the same whether you use
> descriptors or not.
>
> - Under the current BIP44-style paths, a wallet that supports P2PKH and
> P2WPKH with a single account and a gap limit of 50 needs to scan:
>
> pkh([deadbeef/44'/0'/0'/0/0])
> pkh([deadbeef/44'/0'/0'/0/...])
> pkh([deadbeef/44'/0'/0'/0/49])
>
> wpkh([deadbeef/84'/0'/0'/0/0])
> wpkh([deadbeef/84'/0'/0'/0/...])
> wpkh([deadbeef/84'/0'/0'/0/49])
>
> - Under the proposed standard, a wallet that suports P2PKH and P2WPKH
> with a single account and a gap limit of 50 needs to scan:
>
> pkh([deadbeef/XY'/0'/0'/0/0])
> pkh([deadbeef/XY'/0'/0'/0/1])
> pkh([deadbeef/XY'/0'/0'/0/...])
> pkh([deadbeef/XY'/0'/0'/0/49])
>
> wpkh([deadbeef/XY'/0'/0'/0/0])
> wpkh([deadbeef/XY'/0'/0'/0/1])
> wpkh([deadbeef/XY'/0'/0'/0/...])
> wpkh([deadbeef/XY'/0'/0'/0/49])

That is not how I understand the BIP draft. I think the text specifically
mentions avoiding key reuse between different scripts (by increasing the
account index); unlike your example list which reuses keys between pkh and
wpkh.

From the draft BIP's text [0]:

> It is crucial that this level is increased for each new wallet joined or
> private/public keys created; for both privacy and cryptographic purposes.
> For example, in multisignature wallets, before sending a new key record
> to a coordinator, the wallet must increment the account' level. Before
> creating it's own single signature wallet, the account' level must again
> be incremented. This prevents key reuse - across single signature and
> multisignature wallets, across ECDSA and Schnorr signatures, and inbetween
> the same wallet types.

It is good not to reuse keys. However this raises a new issue, which is what
I was alluding to in my previous email: when restoring from seed the wallet
will have to try all scripts for all account indices. Continuing your example,
it could be that account 0 is pkh and account 1 is wpkh or it could be the
other way around. Or the user might have created two wpkh accounts -- after all,
BIP44 allows that, and this new BIP is trying to be even more generic so why not?

> It's essentially the same amount of work in either case.

No, it is more work; and it will be even more in the future as new script types
come. It is the same amount of work only in the best case if the user backed up
descriptors; it is a lot more if they did not.

ghost43

*****************

David replied back:

On Wed, Mar 17, 2021 at 11:29:26PM +0000, SomberNight wrote:
> That is not how I understand the BIP draft. I think the text specifically
> mentions avoiding key reuse between different scripts (by increasing the
> account index); unlike your example list which reuses keys between pkh and
> wpkh.

There's no actual reuse there. Let's say the Foo Wallet v1 used P2PKH
and v2 defaulted to P2WPKH (but still allowed spending from P2PKH).
User Alice started with v1, so Foo Wallet gave her addresses,

pkh([a11ce000/XY'/0'/0'/0/0])
pkh([a11ce000/XY'/0'/0'/0/1])
pkh([a11ce000/XY'/0'/0'/0/...])

When she upgraded to v2, it gave her the following new addresses (note
the antepenultimate path level (the account level) is incremented):

wpkh([a11ce000/XY'/0'/1'/0/0])
wpkh([a11ce000/XY'/0'/1'/0/1])
wpkh([a11ce000/XY'/0'/1'/0/...])

Now we consider Bob who started with the v2 version of the wallet that
defaulted to P2WPKH. His addresses are:

wpkh([b0bb10c5/XY'/0'/0'/0/0])
wpkh([b0bb10c5/XY'/0'/0'/0/1])
wpkh([b0bb10c5/XY'/0'/0'/0/...])

This means that, when Alice restores from backup, the wallet looks
through the zeroeth account to see if it finds any P2PKH outputs; when it
does, it also checks the first account to see if there are any P2WPKH
outputs. When Bob restores from backup, it scans for P2PKH, doesn't find
any, scans fro P2WPH and finds them.

> It is good not to reuse keys. However this raises a new issue, which is what
> I was alluding to in my previous email: when restoring from seed the wallet
> will have to try all scripts for all account indices. Continuing your example,
> it could be that account 0 is pkh and account 1 is wpkh or it could be the
> other way around. Or the user might have created two wpkh accounts -- after all,
> BIP44 allows that, and this new BIP is trying to be even more generic so why not?

So to make sure I understand your corncern, following the example abole
there is an edge case there where Alice creates a v1 wallet, hands out
a P2PKH address that doesn't get used, and then upgrades to v2 and
starts using P2WPKH addresses. Is that your concern?

I agree, that's a problem. I'll have to think about that (and maybe Robert
already has).

-Dave

******************

ghost43 clarifies concerns:

Consider Carol, who creates 5 pkh accounts, then creates 1 wpkh account, then 1 wpkh-sh account, then 2 more wpkh (9 accounts overall).

If Carol is using BIP44/49/84, she will then have used:
- BIP44 account indices 0-4 inclusive,
- BIP49 account index 0,
- BIP84 account indices 0-2

If using new BIP XY, she will then have used:
- BIPXY account indices 0-4 for p2pkh
- BIPXY account index 5 for p2wpkh
- BIPXY account index 6 for p2wpkh-p2sh
- BIPXY account indices 7-8 for p2wpkh

The issue is that when restoring, with BIPXY, the wallet software will have to try all script types for all account indices: if it does not find an account, it might stop there, and miss all subsequent accounts too.

If using BIP44/49/84, when restoring, the wallet will scan:
- for p2pkh, BIP44, indices 0-5, stopping at 5 as it has not been used: scanned 5 accounts worth of addresses (+1 extra address for account idx 5)
- for p2wpkh-p2sh, BIP49, indices 0 and 1, stopping at 1 as it has not been used: scanned 1 account worth of addresses (+1 extra address for account idx 1)
- for p2wpkh, BIP84, indices 0-3, stopping at idx 3 as it has not been used: scanned 3 accoutns worth of addresses (+1 extra address for account idx 3)
All together the wallet needs to scan ~9 accounts worth of addresses which matches the 9 accounts the user actually created.

If using new BIP XY, when restoring, the wallet will scan:
- address index 0, hmmm wonder what script type the user might have used here, let's try p2wpkh as that is the cool thing today... --- ends up trying all script types (in worst case) until it finds p2pkh
- address index 1, hmmm surely the user used the new script type by then? tries all script types in worst case again
- ...
All together the wallet might end up scanning 9 * n (maybe three for now; but what about p2pk; or p2tr?) accounts worth of addresses.

ghost43

***********

ghost43 clarifies further:

> If using new BIP XY, she will then have used:
> - BIPXY account indices 0-4 for p2pkh
> - BIPXY account index 5 for p2wpkh
> - BIPXY account index 6 for p2wpkh-p2sh
> - BIPXY account indices 7-8 for p2wpkh

> The issue is that when restoring, with BIPXY, the wallet software will have to try all script types for all account indices: if it does not find an account, it might stop there, and miss all subsequent accounts too.

In fact note that if an older wallet does not support p2wpkh; only p2pkh and p2wpkh-p2sh, it only find accounts 0-4, and miss account 6.
This is a regression compared to BIP44/49.

**********

David Replies:

On Thu, Mar 18, 2021 at 12:22:48AM +0000, SomberNight wrote:
> > If using new BIP XY, she will then have used:
> > - BIPXY account indices 0-4 for p2pkh
> > - BIPXY account index 5 for p2wpkh
> > - BIPXY account index 6 for p2wpkh-p2sh
> > - BIPXY account indices 7-8 for p2wpkh
>
> > The issue is that when restoring, with BIPXY, the wallet software will have to try all script types for all account indices: if it does not find an account, it might stop there, and miss all subsequent accounts too.
>
> In fact note that if an older wallet does not support p2wpkh; only p2pkh and p2wpkh-p2sh, it only find accounts 0-4, and miss account 6.
> This is a regression compared to BIP44/49.

Agreed. The risk that older wallet software will reuse keys because it's
unaware of what a newer version of itself is doing negates my whole
premise of being able to use seeds without explicit descriptors.

Thank you for your insight and for arguing with me!

-Dave

*******

Craig response:

Great explanation SomberNight.

A pity now this isn't on-list, would like to share it in future!

Craig

*********

I (Robert Spigler) will respond in a next post.

Thanks for your comments!

[-- Attachment #2: Type: text/html, Size: 18131 bytes --]

  reply	other threads:[~2021-03-18 20:45 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-03-14 15:13 [bitcoin-dev] Signature and Script Independent Hierarchy for Deterministic Wallets SomberNight
2021-03-14 20:46 ` Robert Spigler
2021-03-17  7:26   ` Craig Raw
2021-03-18 15:29   ` Jochen Hoenicke
2021-03-18 20:44     ` Robert Spigler [this message]
2021-03-18 21:42       ` Robert Spigler
2021-03-19  7:54         ` Craig Raw
2021-03-19  8:59           ` Robert Spigler
  -- strict thread matches above, loose matches on Subject: below --
2021-03-14  1:51 Robert Spigler

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='oIgV5u9J6iyoWCDtouomT3mNi6D5cxXjOgIWNYiZ_uQIqd2FksfvkIDvAEbdE9L37tAIGAC3QUxzyfBrDYtleBEX80WAO7O6CQNjniE6Omc=@protonmail.ch' \
    --to=robertspigler@protonmail.ch \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=somber.night@protonmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox