Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 397F4C016F for ; Tue, 29 Sep 2020 17:34:47 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 1B2AA87102 for ; Tue, 29 Sep 2020 17:34:47 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Belp0lW79buN for ; Tue, 29 Sep 2020 17:34:45 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) by hemlock.osuosl.org (Postfix) with ESMTPS id D9EA487005 for ; Tue, 29 Sep 2020 17:34:40 +0000 (UTC) Received: by mail-pf1-f171.google.com with SMTP id x123so5250385pfc.7 for ; Tue, 29 Sep 2020 10:34:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=J0kOQD9YrtRx6rg3N4Q32kWGg92x50z3wyzfi2auSC4=; b=a9yfGQS6orqSL/Miph6xKYBlthOxNctIfiglUauZu8QB5lLZ3aqK5OwXUx/MhdR7SQ JdHr+QzjKQO/DFUDu71+kOjSjqkvJu0b3PwdcTBgl2FVrHgQ1cVixYl1gVpVbVy4hyhY TFc/Isy0BVBtLtUjr04cdw2K8qVVBoLSUWQQU1FgTRFyJylOhuNhd+sNgIaBu/mn2ZIo 0wJa9ex22iLsLl1jLhbrgdpf4eIsA4ERGxoJWvtP9rnpICWJvmub/MXLwjDEssDN8zMa pDl5/aj58je8X94RANwQfksblAGo08rIhSWzSSrzo9JLTJFFLgSWN72zN99S2I5fVy1P 6nNg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=J0kOQD9YrtRx6rg3N4Q32kWGg92x50z3wyzfi2auSC4=; b=CRSqnbJOQoiRjwI7s84RL5TyLnpEsI6neXiFkEroTXFPUUl5qNtUZ+ilV1doYECfkq 49dq9Ue4jWfeWKrGDf4ZBPfawEHm0XWDjXcebKmrZjsUx0RpfYxQMeuR/TtrXVmZmnoy u0ipfX79ZRAxsyDFuWeDFNAHNsAM5NTVoxJImQi1bXOsBX4IXSfGhYKm83TW1t6NvIUK AJXN/MRAwqJq6jQkCL2Dd1oRJYfe/RuWxlUtEx20oqyej2wXkEUKYqymbyO3D/5rZAJg u2M3YjF9Uez3Ud3XXufREjKyE32AukCg0vua4Xvn00VWkHn7W11zDrc8ld094c6BlQWQ 51kA== X-Gm-Message-State: AOAM531ZRoQdPzd0pnKDXktIIbs77mSfcVqCh7A28pMqVP29inycge8l sBWmTt5vXa6+6j/IxOrWldlJ47jv/4nAXgkBmJZSqx1gGpY= X-Google-Smtp-Source: ABdhPJxlXvuOLb9sDQoMhVxTkh+XzdvCH/xkuh6z4nvbyqhLK+nnyOg7EYIptpKPQjecq7+MQ4q4y7rf3dn8XLF+5x8= X-Received: by 2002:aa7:9e43:0:b029:142:2501:34e3 with SMTP id z3-20020aa79e430000b0290142250134e3mr4859148pfq.60.1601400880022; Tue, 29 Sep 2020 10:34:40 -0700 (PDT) MIME-Version: 1.0 From: Leonardo Comandini Date: Tue, 29 Sep 2020 19:34:28 +0200 Message-ID: To: bitcoin-dev@lists.linuxfoundation.org Content-Type: multipart/alternative; boundary="00000000000098c9a805b077328e" X-Mailman-Approved-At: Tue, 29 Sep 2020 18:02:25 +0000 Subject: [bitcoin-dev] Is BIP32's chain code needed? X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 29 Sep 2020 17:34:47 -0000 --00000000000098c9a805b077328e Content-Type: text/plain; charset="UTF-8" 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 --00000000000098c9a805b077328e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi all,

BIP32 [1] says: "In order to prev= ent these from depending solely on the key
itself, we extend both priva= te and public keys first with an extra 256 bits of
entropy. This extens= ion, called the chain code...".

My argument is that the chain c= ode is not needed.
To support such claim, I'll show a schematic of B= IP32 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=3DpG)` and `(p_i, P_i=3Dp_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 th= e
definitions given in BIP32 [2].
Define private and public child der= ivation as follow:

=C2=A0 =C2=A0 p_i(p, c, i) =3D (i < 2^31) =C2= =A0p + h1(c, pG, i)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0(i >=3D 2^31) p + h2(c, p, i)

=C2=A0 =C2=A0 c_i(= p, c, i) =3D (i < 2^31) =C2=A0h3(c, pG, i)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(i >=3D 2^31) h4(c, p, i)
=C2=A0 =C2=A0 P_i(P, c, i) =3D (i < 2^31) =C2=A0P + h1(c, P, i)G=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(i &= gt;=3D 2^31) not possible

=C2=A0 =C2=A0 c_i(P, c, i) =3D (i < 2^3= 1) =C2=A0h3(c, P, i)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0(i >=3D 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 has= h function which converts its output to
integer.
Consider the followi= ng derivation scheme:

=C2=A0 =C2=A0 p_i(p, i) =3D (i < 2^31) =C2= =A0p + h(pG, i)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = (i >=3D 2^31) h(p, i)

=C2=A0 =C2=A0 P_i(P, i) =3D (i < 2^31) = =C2=A0P + h(P, i)G
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 (i >=3D 2^31) not possible

Which is basically the above one w= ithout 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
=C2=A0 same way the analogous = problem relies on brute-forcing `h2` in BIP32.
- The problem of determin= ing whether `{p_i, i}_i=3D1..n` are derived from a common
=C2=A0 parent = `p` relies on brute-forcing `h` in the same way the analogous problem
= =C2=A0 relies on brute-forcing `h2` in BIP32.
- Given `i < 2^31, p_i,= P`, an attacker can find `p`. This is analogous to
=C2=A0 BIP32, where = the parent extended pubkey is needed (`P, c`). One could argue
=C2=A0 th= at `c` is never published on the blockchain, while `P` may be. On the other=
=C2=A0 hand most wallets either use hardened derivation (so the attack = does not work)
=C2=A0 or derive scriptpubkeys from keys at the same dept= h (so the parent key is
=C2=A0 never published on the blockchain).
= =C2=A0 Anyway, if the parent public key is kept as secret as BIP32 extended= keys are,
=C2=A0 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 ins= tance, when using
a NofM multisig, each participant must backup M-1 exte= neded 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 mappe= d back to a
mnemonic.

A common wallet setup is (`->` one-way d= erivation, `<->` two-way mapping):

=C2=A0 =C2=A0 entropy (16-3= 2 bytes) <-> user-friendly backup
=C2=A0 =C2=A0 =C2=A0 -> BIP32= extended key (64-65 bytes)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-> BIP= 32 extended child keys (64-65 bytes)

With the proposed derivation, i= t would be possible to have:

=C2=A0 =C2=A0 derivable private key (32= bytes) <-> user-friendly backup
=C2=A0 =C2=A0 =C2=A0 -> deriva= ble public key (33 bytes) <-> user-friendly backup
=C2=A0 =C2=A0 = =C2=A0 -> derivable child keys (32-33 bytes) <-> user-friendly bac= kup

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
=C2=A0 =C2=A0 Ip(c, p, i) =3D (i >=3D 2^31) HMAC-SHA512(c, 0x00 || ser= 256(p) || ser32(i))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 (i < 2^31) =C2=A0HMAC-SHA512(c, pG || ser32(i))

=C2=A0= =C2=A0 IP(c, P, i) =3D (i >=3D 2^31) not possible
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (i < 2^31) =C2=A0HMAC-SHA5= 12(c, P || ser32(i))

=C2=A0 =C2=A0 h1(c, P, i) =3D parse256(IP(c, P,= i)[:32])
=C2=A0 =C2=A0 h2(c, p, i) =3D parse256(Ip(c, p, i)[:32])
= =C2=A0 =C2=A0 h3(c, P, i) =3D IP(c, P, i)[32:]
=C2=A0 =C2=A0 h4(c, p, i)= =3D Ip(c, p, i)[32:]

[3] https://blockstream.com/sidechains.pdf Appendix A

[4] <= a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#se= curity">https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#secu= rity

[5] https://github.com/bitcoin/bips/blob/master/bip-0039.me= diawiki


--
=
Leonardo
--00000000000098c9a805b077328e--