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

From: Lloyd Fournier <lloyd.fourn@gmail•com>
To: Leonardo Comandini <leonardocomandini@gmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Is BIP32's chain code needed?
Date: Mon, 5 Oct 2020 13:49:48 +1100	[thread overview]
Message-ID: <CAH5Bsr2FKJoroxnv+TLh6gs7KeaHT2fJDEA8JByrSTTLFf0_5A@mail.gmail.com> (raw)
In-Reply-To: <CACmzyU-XVNxLQ8o5CQrhmxGocK6yAX1nCFT2WQ-si157y=dfwQ@mail.gmail.com>

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