path: root/10/3a687bd6b5629ff15d781e989f5a0717b4ba3d

Return-Path: <leonardocomandini@gmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 397F4C016F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 29 Sep 2020 17:34:40 +0000 (UTC)
Received: by mail-pf1-f171.google.com with SMTP id x123so5250385pfc.7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <leonardocomandini@gmail.com>
Date: Tue, 29 Sep 2020 19:34:28 +0200
Message-ID: <CACmzyU-XVNxLQ8o5CQrhmxGocK6yAX1nCFT2WQ-si157y=dfwQ@mail.gmail.com>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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

<div dir=3D"ltr">Hi all,<br><div><br>BIP32 [1] says: &quot;In order to prev=
ent these from depending solely on the key <br>itself, we extend both priva=
te and public keys first with an extra 256 bits of <br>entropy. This extens=
ion, called the chain code...&quot;.<br><br>My argument is that the chain c=
ode is not needed.<br>To support such claim, I&#39;ll show a schematic of B=
IP32 operations to be compared<br>with an alternative proposal and discuss =
the differences.<br><br>I have two main questions:<br>- Is this claim false=
?<br>- Has anyone shared this idea before?<br><br>## BIP32 schematic<br><br=
>Let `G` be the secp256k1 generator.<br>Let `i` be the child index.<br>Let =
`(p, P=3DpG)` and `(p_i, P_i=3Dp_iG)` be the parent and i-th child keypairs=
<br>respectively.<br>Let `c` and `c_i` be the corresponding chain codes.<br=
>Let `h1, h2, h3, h4` be hash functions so that the formulae below match th=
e<br>definitions given in BIP32 [2].<br>Define private and public child der=
ivation as follow:<br><br>=C2=A0 =C2=A0 p_i(p, c, i) =3D (i &lt; 2^31) =C2=
=A0p + h1(c, pG, i)<br>=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) p + h2(c, p, i)<br><br>=C2=A0 =C2=A0 c_i(=
p, c, i) =3D (i &lt; 2^31) =C2=A0h3(c, pG, i)<br>=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) h4(c, p, i)<b=
r><br>=C2=A0 =C2=A0 P_i(P, c, i) =3D (i &lt; 2^31) =C2=A0P + h1(c, P, i)G<b=
r>=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<br><br>=C2=A0 =C2=A0 c_i(P, c, i) =3D (i &lt; 2^3=
1) =C2=A0h3(c, P, i)<br>=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<br><br>The above formula =
for unhardened public derivation resembles a pay-to-contract <br>[3] scheme=
.<br><br>## Alternative proposal<br><br>Let `h` be an adequately strong has=
h function which converts its output to<br>integer.<br>Consider the followi=
ng derivation scheme:<br><br>=C2=A0 =C2=A0 p_i(p, i) =3D (i &lt; 2^31) =C2=
=A0p + h(pG, i)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
(i &gt;=3D 2^31) h(p, i)<br><br>=C2=A0 =C2=A0 P_i(P, i) =3D (i &lt; 2^31) =
=C2=A0P + h(P, i)G<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 (i &gt;=3D 2^31) not possible<br><br>Which is basically the above one w=
ithout the chaincode.<br><br>## Considerations<br><br>I claim that this has=
 the same properties as BIP32 [4]:<br>- The problem of finding `p` given `p=
_i, i` relies on brute-forcing `h` in the<br>=C2=A0 same way the analogous =
problem relies on brute-forcing `h2` in BIP32.<br>- The problem of determin=
ing whether `{p_i, i}_i=3D1..n` are derived from a common<br>=C2=A0 parent =
`p` relies on brute-forcing `h` in the same way the analogous problem<br>=
=C2=A0 relies on brute-forcing `h2` in BIP32.<br>- Given `i &lt; 2^31, p_i,=
 P`, an attacker can find `p`. This is analogous to<br>=C2=A0 BIP32, where =
the parent extended pubkey is needed (`P, c`). One could argue<br>=C2=A0 th=
at `c` is never published on the blockchain, while `P` may be. On the other=
<br>=C2=A0 hand most wallets either use hardened derivation (so the attack =
does not work)<br>=C2=A0 or derive scriptpubkeys from keys at the same dept=
h (so the parent key is<br>=C2=A0 never published on the blockchain).<br>=
=C2=A0 Anyway, if the parent public key is kept as secret as BIP32 extended=
 keys are,<br>=C2=A0 then the situation is analogous to BIP32&#39;s.<br><br=
>_If_ these claims are correct, the proposed derivation scheme has two main=
<br>advantages:<br><br>1) Shorter backups for public and private derivable =
keys<br><br>Backups are especially relevant for output descriptors. For ins=
tance, when using<br>a NofM multisig, each participant must backup M-1 exte=
neded public keys and its<br>extended private key, which can be included in=
 an output descriptor. Using the <br>proposed derivation reduces the backup=
 size by `~M*32` bytes.<br><br>2) User-friendly backup for child keys<br><b=
r>Most wallets use user-friendly backups, such as BIP39 [5] mnemonics. They=
 map<br>16-32 bytes of entropy to 12-24 words. However BIP32 exteneded keys=
 are at least<br>64(65) bytes (key and chain code), so they cannot be mappe=
d back to a<br>mnemonic.<br><br>A common wallet setup is (`-&gt;` one-way d=
erivation, `&lt;-&gt;` two-way mapping):<br><br>=C2=A0 =C2=A0 entropy (16-3=
2 bytes) &lt;-&gt; user-friendly backup<br>=C2=A0 =C2=A0 =C2=A0 -&gt; BIP32=
 extended key (64-65 bytes) <br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; BIP=
32 extended child keys (64-65 bytes)<br><br>With the proposed derivation, i=
t would be possible to have:<br><br>=C2=A0 =C2=A0 derivable private key (32=
 bytes) &lt;-&gt; user-friendly backup<br>=C2=A0 =C2=A0 =C2=A0 -&gt; deriva=
ble public key (33 bytes) &lt;-&gt; user-friendly backup<br>=C2=A0 =C2=A0 =
=C2=A0 -&gt; derivable child keys (32-33 bytes) &lt;-&gt; user-friendly bac=
kup<br><br>This would allow having mnemonics for subaccount keys.<br><br>##=
 References<br><br>[1] <a href=3D"https://github.com/bitcoin/bips/blob/mast=
er/bip-0032.mediawiki">https://github.com/bitcoin/bips/blob/master/bip-0032=
.mediawiki</a><br><br>[2] h1, h2, h3 and h4 can be defined as follows<br><b=
r>=C2=A0 =C2=A0 Ip(c, p, i) =3D (i &gt;=3D 2^31) HMAC-SHA512(c, 0x00 || ser=
256(p) || ser32(i))<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 (i &lt; 2^31) =C2=A0HMAC-SHA512(c, pG || ser32(i))<br><br>=C2=A0=
 =C2=A0 IP(c, P, i) =3D (i &gt;=3D 2^31) not possible<br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (i &lt; 2^31) =C2=A0HMAC-SHA5=
12(c, P || ser32(i))<br><br>=C2=A0 =C2=A0 h1(c, P, i) =3D parse256(IP(c, P,=
 i)[:32])<br>=C2=A0 =C2=A0 h2(c, p, i) =3D parse256(Ip(c, p, i)[:32])<br>=
=C2=A0 =C2=A0 h3(c, P, i) =3D IP(c, P, i)[32:]<br>=C2=A0 =C2=A0 h4(c, p, i)=
 =3D Ip(c, p, i)[32:]<br><br>[3] <a href=3D"https://blockstream.com/sidecha=
ins.pdf">https://blockstream.com/sidechains.pdf</a> Appendix A<br><br>[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</a><br><br>[5] <a href=3D"https://github.com/bitcoin/bips/blob/master/=
bip-0039.mediawiki">https://github.com/bitcoin/bips/blob/master/bip-0039.me=
diawiki</a><br><br clear=3D"all"><br>-- <br></div><div><div dir=3D"ltr" cla=
ss=3D"gmail_signature" data-smartmail=3D"gmail_signature"><div dir=3D"ltr">=
</div><div dir=3D"ltr">Leonardo<br></div></div></div></div>

--00000000000098c9a805b077328e--