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

From: Adam Back <adam.back@gmail•com>
To: Pieter Wuille <bitcoin-dev@wuille•net>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Is BIP32's chain code needed?
Date: Sat, 17 Oct 2020 11:14:59 +0200	[thread overview]
Message-ID: <CALqxMTG+R=aXwkEGF7eD37qJEgcoOCQmjTBeD+h+n10Hbp3mtQ@mail.gmail.com> (raw)
In-Reply-To: <xudKQNCJGHcx56H5Aajyo8edv-s5PvGDVDrNR4kdjQXawvewOxb1E5zB-ieHY8T9SUu9FJVa2Ea4_oa4LPbXmzK1C4kOJ8pogqvONDXwg70=@wuille.net>

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