[bitcoin-dev] Is BIP32's chain code needed?

[bitcoin-dev] Is BIP32's chain code needed?

[Leonardo Comandini]

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

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

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

Re: [bitcoin-dev] Is BIP32's chain code needed?

[Lloyd Fournier]

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:
>
> 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-dev

Re: [bitcoin-dev] Is BIP32's chain code needed?

[Christopher Allen]

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

Leondardo,

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

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

Re: [bitcoin-dev] Is BIP32's chain code needed?

[Pieter Wuille]

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

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

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

Re: [bitcoin-dev] Is BIP32's chain code needed?

[Adam Back]

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