public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Leonardo Comandini <leonardocomandini@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Subject: [bitcoin-dev] Is BIP32's chain code needed?
Date: Tue, 29 Sep 2020 19:34:28 +0200	[thread overview]
Message-ID: <CACmzyU-XVNxLQ8o5CQrhmxGocK6yAX1nCFT2WQ-si157y=dfwQ@mail.gmail.com> (raw)

[-- 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 --]

             reply	other threads:[~2020-09-29 17:34 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-09-29 17:34 Leonardo Comandini [this message]
2020-10-05  2:49 ` [bitcoin-dev] Is BIP32's chain code needed? Lloyd Fournier
2020-10-05 20:34 ` Christopher Allen
2020-10-16 21:41 ` Pieter Wuille
2020-10-17  9:14   ` Adam Back

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='CACmzyU-XVNxLQ8o5CQrhmxGocK6yAX1nCFT2WQ-si157y=dfwQ@mail.gmail.com' \
    --to=leonardocomandini@gmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /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