descriptors: Use xpub at last hardened step if possible #18163

achow101 · 2020-02-16T22:16:54Z

When a descriptor contains a private key and has hardened derivation steps, derive the xpub at the last hardened step and convert the derivation into origin info. So the result is that a BIP32PubkeyProvider containing a xprv with hardened derivation steps and ending with unhardened derivation becomes a OriginPubkeyProvider with those hardened derivation steps as the origin info and a new BIP32PubkeyProvider containing the xpub and the unhardened derivation steps.

For example:
wpkh(xprv..../0'/0'/*) becomes wpkh([d34db33f/0'/0']xpub.../*)

If the descriptor has only hardened steps, it is not modified.

This change allows descriptor wallets to derive from such descriptors without needing to be unlocked.

DrahtBot · 2020-02-17T03:53:08Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

descriptors: improve descriptor cache and cache xpubs #18204 (descriptors: improve descriptor cache and cache xpubs by achow101)
UI external signer support (e.g. hardware wallet) #16549 ([WIP] UI external signer support (e.g. hardware wallet) by Sjors)
External signer support - Wallet Box edition #16546 ([WIP] External signer support - Wallet Box edition by Sjors)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

Sjors

Concept ACK

Sjors · 2020-02-19T10:37:31Z

src/script/descriptor.cpp

Travis doesn't like this: https://travis-ci.org/bitcoin/bitcoin/jobs/651243106#L4064

Error: attempt to decrement a dereferenceable (start-of-sequence) iterator.

It sounds like a job for std::find_end with a binary predicate, since you're looking for a hardened path element by an unhardened one.

I was able to use std::find_if for this.

instagibbs · 2020-02-19T13:56:16Z

Is there a practical consideration for this change? It seems to make sense, just wondering if downstream applications are made easier by this or something.

achow101 · 2020-02-19T17:22:32Z

Is there a practical consideration for this change?

It would allow for descriptor wallets that import a descriptor with a private key and hardened steps to be able to derive scriptPubKeys without needing to be unlocked.

instagibbs · 2020-02-19T17:26:05Z

Adding that to OP would be OP

concept ACK!

Sjors

0e54ba78ea7e7468ce5a185c4195b0dd58f3f82d looks good, expect the duplicate line.

That said, I feel a bit ambivalent about adding origin info to descriptors that don't already have it. For example pkh(xprv9...C2U/0'/0'/0) becomes pkh([bd16bee5/0'/0']xpub6AVD...pQKh/0). Perhaps normalisation should only happen for descriptors with origin info. Also, an xpub encodes its depth, so if in the example the original xpriv depth wasn't 0 it would be weird (or maybe not; depends on if we interpret the fingerprint as depth 0).

I personally haven't seen real world descriptors without origin info yet, so I'm sure how they should be handled.

Also, what would be the next step to have InferDescriptor benefit from this change? It would be nice to have getaddressinfo in return an xpub, instead of individual public key, for BIP44/49/84 style watch-only (legacy) wallets.

src/script/descriptor.cpp

achow101 · 2020-02-21T16:25:59Z

That said, I feel a bit ambivalent about adding origin info to descriptors that don't already have it. For example pkh(xprv9...C2U/0'/0'/0) becomes pkh([bd16bee5/0'/0']xpub6AVD...pQKh/0). Perhaps normalisation should only happen for descriptors with origin info.

Then we wouldn't achieve the primary goal of this PR. People could import xprvs without origin info that have some hardened derivation steps and we wouldn't be able to derive the public keys from them.

Also, an xpub encodes its depth, so if in the example the original xpriv depth wasn't 0 it would be weird (or maybe not; depends on if we interpret the fingerprint as depth 0).

The xpub at the end would still contain that depth information. Even without an origin info, an xprv could have a non-zero depth but that doesn't bother us.

Also, what would be the next step to have InferDescriptor benefit from this change? It would be nice to have getaddressinfo in return an xpub, instead of individual public key, for BIP44/49/84 style watch-only (legacy) wallets.

I think that requires changes to SigningProvider.

Sjors · 2020-02-21T18:42:20Z

ACK b674297c7c491ea09cef171ed083533f23c9ffa9

I've never imported keys without origin info, but if you find it useful, I'm fine with supporting it.

Utility function to derive at a path from an CExtKey instead of implementing this externally every time we want to derive at a path.

achow101 · 2020-02-21T19:50:21Z

Had to rebase

Sjors · 2020-02-21T21:43:35Z

Code review re-ACK f827475 (rebased on #18034)

sipa · 2020-02-22T17:53:25Z

I discussed this with @achow101 IRL.

One alternative I'd like to see explored is instead of rewriting the descriptor itself, having an "xpub cache" added to the descriptor interface (and later the wallet itself), similar to the existing pubkey cache, but shared across indexes. This would have all the availability benefits of a change like this, but also speed up operations on descriptors that include several non-hardened steps in xpubs.

Sjors · 2020-02-22T18:57:18Z

That would take case of this TODO, right?

bitcoin/src/script/descriptor.cpp

Lines 286 to 291 in ab9de43

    
           // TODO: optimize by caching 
        
           CExtPubKey extkey = m_extkey; 
        
           for (auto entry : m_path) { 
        
               extkey.Derive(extkey, entry); 
        
           } 
        
           if (m_derive == DeriveType::UNHARDENED) extkey.Derive(extkey, pos);

Rewriting the descriptor has merit in any case; a descriptor like wpkh([d34db33f/xpub /0'/0'].../*) makes no sense, because you can't actually derive any addresses without also knowing the xpriv. Whereas with wpkh([d34db33f/0'/0']xpub.../*) you can. Normalising makes them more straight-forward to share.

For BIP44/49/84 style descriptors (wpkh([d34db33f/84'/0'/0']xpub.../0/*)) it would indeed make sense to cache an xpub for the 0 after the visible xpub. But I think that can be hidden as an ephemeral implementation detail; I don't think it needs to be serialised into the wallet payload. Unlike the individual key cache, the savings don't scale with wallet size.

09e2507 Cache parent xpub inside of BIP32PubkeyProvider (Andrew Chow) deb791c Only cache xpubs that have a hardened last step (Andrew Chow) f76733e Cache the immediate derivation parent xpub (Andrew Chow) 58f54b6 Add DescriptorCache* read_cache and DescriptorCache* write_cache to Expand and GetPubKey (Andrew Chow) 66c2cad Rename BIP32PubkeyProvider.m_extkey to m_root_extkey (Andrew Chow) df55d44 Track the index of the key expression in PubkeyProvider (Andrew Chow) 474ea3b Introduce DescriptorCache struct which caches xpubs (Andrew Chow) Pull request description: Improves the descriptor cache by changing it from a `std::vector<unsigned char>` to a newly introduced `DescriptorCache` class. Instead of serializing pubkeys and whatever else we would want to cache in a way that may not be backwards compatible, we instead create a `DescriptorCache` object and populate it. This object contains only an xpub cache. Since the only `PubkeyProvider` that used the cache is the `BIP32PubkeyProvider` we just have it store the xpubs instead of the pubkeys. This allows us to have both the parent xpub and the child xpubs in the same container. The map is keyed by `KeyOriginInfo`. Sine we are caching `CExtPubKey`s in `DescriptorCache`, `BIP32PubKeyProviders` can use the cached parent xpubs to derive the children if unhardened derivation is used in the last step. This also means that we can still derive the keys for a `BIP32PubkeyProvider` that has hardened derivation steps. When combined with descriptor wallets, this should allow us to be able to import a descriptor with an `xprv` and hardened steps and still be able to derive from it. In that sense, this is an alternative to #18163 To test that this works, the tests have been updated to do an additional `Expand` at the `i + 1` position. This expansion is not cached. We then do an `ExpandFromCache` at `i + 1` and use the cache that was produced by the expansion at `i`. This way, we won't have the child xpubs for `i + 1` but we will have the parent xpubs. So this checks whether the parent xpubs are being stored and can be used to derive the child keys. Descriptors that have a hardened last step are skipped for this part of the test because that will always require private keys. ACKs for top commit: instagibbs: code review re-re-ACK 09e2507 Sjors: re-ACK 09e2507 Tree-SHA512: 95c8d0092274cdf115ce39f6d49dec767679abf3758d5b9e418afc308deca9dc6f67167980195bcc036cd9c09890bbbb39ec1dacffbfacdc03efd72a7e23b276

…xpubs 09e2507 Cache parent xpub inside of BIP32PubkeyProvider (Andrew Chow) deb791c Only cache xpubs that have a hardened last step (Andrew Chow) f76733e Cache the immediate derivation parent xpub (Andrew Chow) 58f54b6 Add DescriptorCache* read_cache and DescriptorCache* write_cache to Expand and GetPubKey (Andrew Chow) 66c2cad Rename BIP32PubkeyProvider.m_extkey to m_root_extkey (Andrew Chow) df55d44 Track the index of the key expression in PubkeyProvider (Andrew Chow) 474ea3b Introduce DescriptorCache struct which caches xpubs (Andrew Chow) Pull request description: Improves the descriptor cache by changing it from a `std::vector<unsigned char>` to a newly introduced `DescriptorCache` class. Instead of serializing pubkeys and whatever else we would want to cache in a way that may not be backwards compatible, we instead create a `DescriptorCache` object and populate it. This object contains only an xpub cache. Since the only `PubkeyProvider` that used the cache is the `BIP32PubkeyProvider` we just have it store the xpubs instead of the pubkeys. This allows us to have both the parent xpub and the child xpubs in the same container. The map is keyed by `KeyOriginInfo`. Sine we are caching `CExtPubKey`s in `DescriptorCache`, `BIP32PubKeyProviders` can use the cached parent xpubs to derive the children if unhardened derivation is used in the last step. This also means that we can still derive the keys for a `BIP32PubkeyProvider` that has hardened derivation steps. When combined with descriptor wallets, this should allow us to be able to import a descriptor with an `xprv` and hardened steps and still be able to derive from it. In that sense, this is an alternative to bitcoin#18163 To test that this works, the tests have been updated to do an additional `Expand` at the `i + 1` position. This expansion is not cached. We then do an `ExpandFromCache` at `i + 1` and use the cache that was produced by the expansion at `i`. This way, we won't have the child xpubs for `i + 1` but we will have the parent xpubs. So this checks whether the parent xpubs are being stored and can be used to derive the child keys. Descriptors that have a hardened last step are skipped for this part of the test because that will always require private keys. ACKs for top commit: instagibbs: code review re-re-ACK bitcoin@09e2507 Sjors: re-ACK 09e2507 Tree-SHA512: 95c8d0092274cdf115ce39f6d49dec767679abf3758d5b9e418afc308deca9dc6f67167980195bcc036cd9c09890bbbb39ec1dacffbfacdc03efd72a7e23b276

instagibbs · 2020-04-08T15:44:15Z

something "like" this is probably nice to have for multisig setups. I'm looking into it for a dumpdescriptors RPC command for that type of setup

…xpubs 09e2507 Cache parent xpub inside of BIP32PubkeyProvider (Andrew Chow) deb791c Only cache xpubs that have a hardened last step (Andrew Chow) f76733e Cache the immediate derivation parent xpub (Andrew Chow) 58f54b6 Add DescriptorCache* read_cache and DescriptorCache* write_cache to Expand and GetPubKey (Andrew Chow) 66c2cad Rename BIP32PubkeyProvider.m_extkey to m_root_extkey (Andrew Chow) df55d44 Track the index of the key expression in PubkeyProvider (Andrew Chow) 474ea3b Introduce DescriptorCache struct which caches xpubs (Andrew Chow) Pull request description: Improves the descriptor cache by changing it from a `std::vector<unsigned char>` to a newly introduced `DescriptorCache` class. Instead of serializing pubkeys and whatever else we would want to cache in a way that may not be backwards compatible, we instead create a `DescriptorCache` object and populate it. This object contains only an xpub cache. Since the only `PubkeyProvider` that used the cache is the `BIP32PubkeyProvider` we just have it store the xpubs instead of the pubkeys. This allows us to have both the parent xpub and the child xpubs in the same container. The map is keyed by `KeyOriginInfo`. Sine we are caching `CExtPubKey`s in `DescriptorCache`, `BIP32PubKeyProviders` can use the cached parent xpubs to derive the children if unhardened derivation is used in the last step. This also means that we can still derive the keys for a `BIP32PubkeyProvider` that has hardened derivation steps. When combined with descriptor wallets, this should allow us to be able to import a descriptor with an `xprv` and hardened steps and still be able to derive from it. In that sense, this is an alternative to bitcoin#18163 To test that this works, the tests have been updated to do an additional `Expand` at the `i + 1` position. This expansion is not cached. We then do an `ExpandFromCache` at `i + 1` and use the cache that was produced by the expansion at `i`. This way, we won't have the child xpubs for `i + 1` but we will have the parent xpubs. So this checks whether the parent xpubs are being stored and can be used to derive the child keys. Descriptors that have a hardened last step are skipped for this part of the test because that will always require private keys. ACKs for top commit: instagibbs: code review re-re-ACK bitcoin@09e2507 Sjors: re-ACK 09e2507 Tree-SHA512: 95c8d0092274cdf115ce39f6d49dec767679abf3758d5b9e418afc308deca9dc6f67167980195bcc036cd9c09890bbbb39ec1dacffbfacdc03efd72a7e23b276

fanquake added the Descriptors label Feb 16, 2020

This was referenced Feb 17, 2020

Get the OutputType for a descriptor #18034

Merged

Native Descriptor Wallets using DescriptorScriptPubKeyMan #16528

Merged

Sjors reviewed Feb 19, 2020

View reviewed changes

achow101 force-pushed the desc-last-hardened branch from c106814 to 0e54ba7 Compare February 19, 2020 23:04

Sjors reviewed Feb 20, 2020

View reviewed changes

src/script/descriptor.cpp Outdated Show resolved Hide resolved

src/script/descriptor.cpp Outdated Show resolved Hide resolved

src/script/descriptor.cpp Outdated Show resolved Hide resolved

achow101 force-pushed the desc-last-hardened branch from 0e54ba7 to b674297 Compare February 21, 2020 17:56

Add DerivePath to CExtKey

136d8f8

Utility function to derive at a path from an CExtKey instead of implementing this externally every time we want to derive at a path.

DrahtBot mentioned this pull request Feb 21, 2020

External signer support - Wallet Box edition #16546

Merged

2 tasks

descriptors: Use xpub at last hardened step if possible

f827475

achow101 force-pushed the desc-last-hardened branch from b674297 to f827475 Compare February 21, 2020 19:49

DrahtBot mentioned this pull request Feb 22, 2020

UI external signer support (e.g. hardware wallet) #16549

Closed

achow101 mentioned this pull request Feb 25, 2020

descriptors: improve descriptor cache and cache xpubs #18204

Merged

achow101 closed this Feb 26, 2020

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

descriptors: Use xpub at last hardened step if possible #18163

descriptors: Use xpub at last hardened step if possible #18163

Uh oh!

Conversation

achow101 commented Feb 16, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Feb 17, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

Sjors left a comment

Choose a reason for hiding this comment

Uh oh!

Sjors Feb 19, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 Feb 19, 2020

Choose a reason for hiding this comment

Uh oh!

instagibbs commented Feb 19, 2020

Uh oh!

achow101 commented Feb 19, 2020

Uh oh!

instagibbs commented Feb 19, 2020

Uh oh!

Sjors left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

achow101 commented Feb 21, 2020

Uh oh!

Sjors commented Feb 21, 2020

Uh oh!

achow101 commented Feb 21, 2020

Uh oh!

Sjors commented Feb 21, 2020

Uh oh!

sipa commented Feb 22, 2020

Uh oh!

Sjors commented Feb 22, 2020

Uh oh!

instagibbs commented Apr 8, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

achow101 commented Feb 16, 2020 •

edited

Loading

DrahtBot commented Feb 17, 2020 •

edited

Loading

Sjors Feb 19, 2020 •

edited

Loading

Sjors left a comment •

edited

Loading