Is BIP32's chain code needed?
5 messages, 29 Sep to 17 Oct 2020. Started by Leonardo Comandini.
Leonardo Comandini, Lloyd Fournier, Christopher Allen, Pieter Wuille, Adam Back
Hi all,
BIP32 [1] says: "In order to prevent these from depending solely on the key itself, we extend both private and public keys first with an extra 256 bits of entropy. This extension, called the chain code...".
My argument is that the chain code is not needed. To support such claim, I'll show a schematic of BIP32 operations to be compared with an alternative proposal and discuss the differences.
I have two main questions: - Is this claim false? - Has anyone shared this idea before?
## BIP32 schematic
Let `G` be the secp256k1 generator. Let `i` be the child index. Let `(p, P=pG)` and `(p_i, P_i=p_iG)` be the parent and i-th child keypairs respectively. Let `c` and `c_i` be the corresponding chain codes. Let `h1, h2, h3, h4` be hash functions so that the formulae below match the definitions given in BIP32 [2]. Define private and public child derivation as follow:
p_i(p, c, i) = (i < 2^31) p + h1(c, pG, i)
(i >= 2^31) p + h2(c, p, i)
c_i(p, c, i) = (i < 2^31) h3(c, pG, i)
(i >= 2^31) h4(c, p, i)
P_i(P, c, i) = (i < 2^31) P + h1(c, P, i)G
(i >= 2^31) not possible
c_i(P, c, i) = (i < 2^31) h3(c, P, i)
(i >= 2^31) not possible
The above formula for unhardened public derivation resembles a pay-to-contract [3] scheme.
## Alternative proposal
Let `h` be an adequately strong hash function which converts its output to integer. Consider the following derivation scheme:
p_i(p, i) = (i < 2^31) p + h(pG, i)
(i >= 2^31) h(p, i)
P_i(P, i) = (i < 2^31) P + h(P, i)G
(i >= 2^31) not possible
Which is basically the above one without the chaincode.
## Considerations
I claim that this has the same properties as BIP32 [4]:
- The problem of finding `p` given `p_i, i` relies on brute-forcing `h` in
the
same way the analogous problem relies on brute-forcing `h2` in BIP32.
- The problem of determining whether `{p_i, i}_i=1..n` are derived from a
common
parent `p` relies on brute-forcing `h` in the same way the analogous
problem
relies on brute-forcing `h2` in BIP32.
- Given `i < 2^31, p_i, P`, an attacker can find `p`. This is analogous to
BIP32, where the parent extended pubkey is needed (`P, c`). One could
argue
that `c` is never published on the blockchain, while `P` may be. On the
other
hand most wallets either use hardened derivation (so the attack does not
work)
or derive scriptpubkeys from keys at the same depth (so the parent key is
never published on the blockchain).
Anyway, if the parent public key is kept as secret as BIP32 extended keys
are,
then the situation is analogous to BIP32's.
_If_ these claims are correct, the proposed derivation scheme has two main advantages:
1) Shorter backups for public and private derivable keys
Backups are especially relevant for output descriptors. For instance, when using a NofM multisig, each participant must backup M-1 exteneded public keys and its extended private key, which can be included in an output descriptor. Using the proposed derivation reduces the backup size by `~M*32` bytes.
2) User-friendly backup for child keys
Most wallets use user-friendly backups, such as BIP39 [5] mnemonics. They map 16-32 bytes of entropy to 12-24 words. However BIP32 exteneded keys are at least 64(65) bytes (key and chain code), so they cannot be mapped back to a mnemonic.
A common wallet setup is (`->` one-way derivation, `<->` two-way mapping):
entropy (16-32 bytes) <-> user-friendly backup
-> BIP32 extended key (64-65 bytes)
-> BIP32 extended child keys (64-65 bytes)
With the proposed derivation, it would be possible to have:
derivable private key (32 bytes) <-> user-friendly backup
-> derivable public key (33 bytes) <-> user-friendly backup
-> derivable child keys (32-33 bytes) <-> user-friendly backup
This would allow having mnemonics for subaccount keys.
## References
[1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[2] h1, h2, h3 and h4 can be defined as follows
Ip(c, p, i) = (i >= 2^31) HMAC-SHA512(c, 0x00 || ser256(p) || ser32(i))
(i < 2^31) HMAC-SHA512(c, pG || ser32(i))
IP(c, P, i) = (i >= 2^31) not possible
(i < 2^31) HMAC-SHA512(c, P || ser32(i))
h1(c, P, i) = parse256(IP(c, P, i)[:32])
h2(c, p, i) = parse256(Ip(c, p, i)[:32])
h3(c, P, i) = IP(c, P, i)[32:]
h4(c, p, i) = Ip(c, p, i)[32:]
[3] https://blockstream.com/sidechains.pdf Appendix A
[4] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#security
[5] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
Hi Leonardo,
I can't tell you what the BIP32 author was thinking but if I put myself in their shoes these are the reasons I might have done it this way:
1. Use HMAC rather than normal SHA2 -- this is just best practice for key derivation (even though I don't think it would make a difference to security if you are strictly following the spec). 2. Use 512-bit rather than 256-bit -- Probably something to do with (1) -- since I'm using an HMAC I've gotta put something as the key. I don't want re-use the 256-bits for the secp256k1 secret key for this since an integer mod q is not the same as 256 random bits (or I don't want to have to make the argument in the design doc that it actually is; plus what if someone starts using this for different curve and I'm not around to tell them no). So I split the 512-bits and use the last 256bits as the key for the child derivation.
I don't think there is any fundamental flaw with what you suggest (I am doing something similar for a project). I guess the issues you pointed out with the scheme were probably not on the author's mind. To me they don't seem too severe but I haven't spent much time developing wallets.
LL
On Wed, Sep 30, 2020 at 4:02 AM Leonardo Comandini via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (133 lines)
>
> Hi all,
>
> BIP32 [1] says: "In order to prevent these from depending solely on the key
> itself, we extend both private and public keys first with an extra 256 bits of
> entropy. This extension, called the chain code...".
>
> My argument is that the chain code is not needed.
> To support such claim, I'll show a schematic of BIP32 operations to be compared
> with an alternative proposal and discuss the differences.
>
> I have two main questions:
> - Is this claim false?
> - Has anyone shared this idea before?
>
> ## BIP32 schematic
>
> Let `G` be the secp256k1 generator.
> Let `i` be the child index.
> Let `(p, P=pG)` and `(p_i, P_i=p_iG)` be the parent and i-th child keypairs
> respectively.
> Let `c` and `c_i` be the corresponding chain codes.
> Let `h1, h2, h3, h4` be hash functions so that the formulae below match the
> definitions given in BIP32 [2].
> Define private and public child derivation as follow:
>
> p_i(p, c, i) = (i < 2^31) p + h1(c, pG, i)
> (i >= 2^31) p + h2(c, p, i)
>
> c_i(p, c, i) = (i < 2^31) h3(c, pG, i)
> (i >= 2^31) h4(c, p, i)
>
> P_i(P, c, i) = (i < 2^31) P + h1(c, P, i)G
> (i >= 2^31) not possible
>
> c_i(P, c, i) = (i < 2^31) h3(c, P, i)
> (i >= 2^31) not possible
>
> The above formula for unhardened public derivation resembles a pay-to-contract
> [3] scheme.
>
> ## Alternative proposal
>
> Let `h` be an adequately strong hash function which converts its output to
> integer.
> Consider the following derivation scheme:
>
> p_i(p, i) = (i < 2^31) p + h(pG, i)
> (i >= 2^31) h(p, i)
>
> P_i(P, i) = (i < 2^31) P + h(P, i)G
> (i >= 2^31) not possible
>
> Which is basically the above one without the chaincode.
>
> ## Considerations
>
> I claim that this has the same properties as BIP32 [4]:
> - The problem of finding `p` given `p_i, i` relies on brute-forcing `h` in the
> same way the analogous problem relies on brute-forcing `h2` in BIP32.
> - The problem of determining whether `{p_i, i}_i=1..n` are derived from a common
> parent `p` relies on brute-forcing `h` in the same way the analogous problem
> relies on brute-forcing `h2` in BIP32.
> - Given `i < 2^31, p_i, P`, an attacker can find `p`. This is analogous to
> BIP32, where the parent extended pubkey is needed (`P, c`). One could argue
> that `c` is never published on the blockchain, while `P` may be. On the other
> hand most wallets either use hardened derivation (so the attack does not work)
> or derive scriptpubkeys from keys at the same depth (so the parent key is
> never published on the blockchain).
> Anyway, if the parent public key is kept as secret as BIP32 extended keys are,
> then the situation is analogous to BIP32's.
>
> _If_ these claims are correct, the proposed derivation scheme has two main
> advantages:
>
> 1) Shorter backups for public and private derivable keys
>
> Backups are especially relevant for output descriptors. For instance, when using
> a NofM multisig, each participant must backup M-1 exteneded public keys and its
> extended private key, which can be included in an output descriptor. Using the
> proposed derivation reduces the backup size by `~M*32` bytes.
>
> 2) User-friendly backup for child keys
>
> Most wallets use user-friendly backups, such as BIP39 [5] mnemonics. They map
> 16-32 bytes of entropy to 12-24 words. However BIP32 exteneded keys are at least
> 64(65) bytes (key and chain code), so they cannot be mapped back to a
> mnemonic.
>
> A common wallet setup is (`->` one-way derivation, `<->` two-way mapping):
>
> entropy (16-32 bytes) <-> user-friendly backup
> -> BIP32 extended key (64-65 bytes)
> -> BIP32 extended child keys (64-65 bytes)
>
> With the proposed derivation, it would be possible to have:
>
> derivable private key (32 bytes) <-> user-friendly backup
> -> derivable public key (33 bytes) <-> user-friendly backup
> -> derivable child keys (32-33 bytes) <-> user-friendly backup
>
> This would allow having mnemonics for subaccount keys.
>
> ## References
>
> [1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
>
> [2] h1, h2, h3 and h4 can be defined as follows
>
> Ip(c, p, i) = (i >= 2^31) HMAC-SHA512(c, 0x00 || ser256(p) || ser32(i))
> (i < 2^31) HMAC-SHA512(c, pG || ser32(i))
>
> IP(c, P, i) = (i >= 2^31) not possible
> (i < 2^31) HMAC-SHA512(c, P || ser32(i))
>
> h1(c, P, i) = parse256(IP(c, P, i)[:32])
> h2(c, p, i) = parse256(Ip(c, p, i)[:32])
> h3(c, P, i) = IP(c, P, i)[32:]
> h4(c, p, i) = Ip(c, p, i)[32:]
>
> [3] https://blockstream.com/sidechains.pdf Appendix A
>
> [4] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#security
>
> [5] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
>
>
> --
> Leonardo
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation•org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-devLeondardo,
There are a lot of sub-topics related to your questions that deserve at least some response.
I was not involved deeply in bitcoin when BIPs 32/38/39/44/45 emerged, but they were not without some strong differences of opinion and controversy, some of which are reflected in challenges today. Part of the problem is that bitcoin core itself didn't adopt these for a very long time after the various wallet companies had them broadly deployed, so I don't believe that these BIPs have quite the rigor that other BIPs have. Plus some entire sub-topics are missing like a proposed BIP 48 that describes multisig paths for hardware keys.
I encourage you to look back both on the PRs for those BIPs, and also archives of this list. Unfortunately, I don't have a curated list of the "best" of these — maybe a project for a future Blockchain Commons intern.
That being said, one particular focus in your question was on how to you turn a master seed into the master key (m/0). Part of the conflict at the time was a number of vendors wanted to avoid the 256 bits of entropy and felt 128 bits were good enough. A compromise was born of that, that even today not all agree with. However, the proposed scheme was "good enough".
Today, I feel that how a master seed (entropy that has been turned into a 128 or 256 bit seed and that which is stored in hardware on a ledger/trezor) is turned into the 512 byte master key for m/0 really needs to be preserved, unless someone finds something cryptographically unsafe about it. Why? Interoperability and avoiding vendor lock-in.
An example of this is the recent proposal from Satoshi Labs for SLIP-39. We implemented it, but discovered that in practice the same seed restored through BIP39 recovery would result in a different master key than SLIP39 recovery. This is because the Trezor team is one of the parties that were unhappy with the compromise back in the BIP32 days, and thus they've decided that as long as they are replacing BIP39 they would "fix" the method of creation of the master seed.
Satoshi Labs has some rationale for these changes, but we (Blockchain Commons and a small community of airgapped wallet developers), felt that the interoperability and lock-in risks were too high. Once you used SLIP39 to create accounts, you must stick with SLIP39. This means you can only restore seeds to wallets that support SLIP39, and most have chosen not to.
So we worked on instead a very closely related specification called SSKR that also does Shamir, but uses the same seed->master key technique that BIP32 does. This means that you can restore your SSRK shards back to a seed, then move them to another device that only supports BIP39. This prevents lock-in into a singular or small subset of wallet vendors. Our current research spec is https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-011-sskr.md and reference code for sskr is at https://github.com/BlockchainCommons/bc-seedtool-cli and we hope to offer it as a BIP in future months. There is a small GitHub community discussing this and other emerging airgapped and multisig standards at https://github.com/BlockchainCommons/Airgapped-Wallet-Community/discussions
There is a similar problem with seed mnemonics Lightning Labs implementations, which needed to offer metadata in addition to the seed. This means their mnemonics are also incompatible and also have potential lock-in and interoperability issues. You can't use their seeds with C-Lightining. So we are puzzling through how to meet their needs for metadata (and other parties in the multsig ecosystem were seed storage is not enough and some metadata is needed), yet maximize round-trip interoperability with multiple wallet vendors, and tools for conversion to legacy formats like our seedtool.
So though at first glance your math seems correct and there are other, potentially better ways to derive in a hierarchical fashion additional keys, I'd be worried that it would suffer the interoperability and potential lock-in that we are seeing with SLIP-39 and LND.
— Christopher Allen
On Tuesday, September 29, 2020 10:34 AM, Leonardo Comandini via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (13 lines)
> Hi all, > > BIP32 [1] says: "In order to prevent these from depending solely on the key > itself, we extend both private and public keys first with an extra 256 bits of > entropy. This extension, called the chain code...". > > My argument is that the chain code is not needed. > To support such claim, I'll show a schematic of BIP32 operations to be compared > with an alternative proposal and discuss the differences. > > I have two main questions: > - Is this claim false? > - Has anyone shared this idea before?
Hi Leonardo,
It's been a while but I can comment on the history of how the chaincode ended up being in there.
The most direct reason is that BIP32 was inspired by Alan Reiner's Armory software, which had a different homomorphic key derivation scheme, but included something called a chaincode to enable multiple "chains" of keys to be derived from the same keypair. More information about that scheme is here: https://bitcointalk.org/index.php?topic=205999.msg2155696#msg2155696
BIP32 made two improvements to this: * Allow efficient random access into the derived keys (Armory's scheme required iterating the derivation function to get consecutive subkeys - which is probably where the name "chain" in chaincode comes from) * Permit hierarchical derivation, by also constructing a sub-"chaincode" along with every subkey.
If I recall correctly, there was at least one argument at the time about whether the chaincode was necessary at all. My rationale for keeping it was: * xpubs are not as secret as private keys, but they do demand more protection than just public keys (for both privacy reasons, and due to the fact that revealing an xpub + child xprv is ReallyBad(tm)). For that reason, it seems nice that an xpub consists of more than just a public key, as revealing the public key in it means the protection above remains. I don't think there is anything fundamental here; just a distinct encoding for xpubs and pubkeys might have accomplished the same, but this felt safer. * Repeated hashing "felt" dangerous, as it reduces entropy at every step, so it'd go below 256 bits. With a chaincode to maintain extra entropy this is prevented. In retrospect, this is a bogus argument, as it's only a relevant point for information-theoretical security (which means we wouldn't be able to use ECC in the first place), and even then, it's only a minimal effect.
So in short, from a cryptographic point of view, I think that indeed, the chaincode is not needed. It probably has some qualitative advantage in practice, but not very much.
Cheers,
Another advantage of random access from BIP 32 vs iterated chain is that if there is a bit-flip or corruption, you don't destroy access to all future addresses, but only burn one utxo. Empirically not an entirely theoretical issue.
I think the only thing i'd care about is bloating up the number of characters to backup, if the codes are all derived it doesn't matter too much. I tend to think of 128-bits as enough given that is the security target of ECDSA, so long as reasonable key-stretching algorithms are used that don't interact badly with the key use, which seems a very reasonable assumption for PBKF2 and ECDSA.
Agree the iterated hashing argument does not seem a practical concern - eg BIP 39 uses PBKDF2 uses 2048 iterated hash invocations. I suppose it's strictly true that as the hash is deterministic and not a bijection (not a permutation), there are collisions and if you iterate enough unreachable states can be eliminated. But because the domain is so large as to be practically unenumerable it won't creates a brute force short-cut
Adam
On Sat, 17 Oct 2020 at 01:35, Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (59 lines)
> > On Tuesday, September 29, 2020 10:34 AM, Leonardo Comandini via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote: > > Hi all, > > BIP32 [1] says: "In order to prevent these from depending solely on the key > itself, we extend both private and public keys first with an extra 256 bits of > entropy. This extension, called the chain code...". > > My argument is that the chain code is not needed. > To support such claim, I'll show a schematic of BIP32 operations to be compared > with an alternative proposal and discuss the differences. > > I have two main questions: > - Is this claim false? > - Has anyone shared this idea before? > > > Hi Leonardo, > > It's been a while but I can comment on the history of how the chaincode ended up being in there. > > The most direct reason is that BIP32 was inspired by Alan Reiner's Armory software, which had > a different homomorphic key derivation scheme, but included something called a chaincode to > enable multiple "chains" of keys to be derived from the same keypair. More information about > that scheme is here: https://bitcointalk.org/index.php?topic=205999.msg2155696#msg2155696 > > BIP32 made two improvements to this: > * Allow efficient random access into the derived keys (Armory's scheme required iterating the > derivation function to get consecutive subkeys - which is probably where the name "chain" > in chaincode comes from) > * Permit hierarchical derivation, by also constructing a sub-"chaincode" along with every subkey. > > If I recall correctly, there was at least one argument at the time about whether the chaincode was > necessary at all. My rationale for keeping it was: > * xpubs are not as secret as private keys, but they do demand more protection than just public keys > (for both privacy reasons, and due to the fact that revealing an xpub + child xprv is ReallyBad(tm)). > For that reason, it seems nice that an xpub consists of more than just a public key, as revealing > the public key in it means the protection above remains. I don't think there is anything fundamental > here; just a distinct encoding for xpubs and pubkeys might have accomplished the same, but this > felt safer. > * Repeated hashing "felt" dangerous, as it reduces entropy at every step, so it'd go below 256 bits. > With a chaincode to maintain extra entropy this is prevented. In retrospect, this is a bogus > argument, as it's only a relevant point for information-theoretical security (which means we wouldn't > be able to use ECC in the first place), and even then, it's only a minimal effect. > > So in short, from a cryptographic point of view, I think that indeed, the chaincode is not needed. It > probably has some qualitative advantage in practice, but not very much. > > Cheers, > > -- > Pieter > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev