From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id C6EBCC0051 for ; Mon, 5 Oct 2020 02:50:40 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id ADB0F84078 for ; Mon, 5 Oct 2020 02:50:40 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vK7by22JIDMl for ; Mon, 5 Oct 2020 02:50:39 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-io1-f41.google.com (mail-io1-f41.google.com [209.85.166.41]) by fraxinus.osuosl.org (Postfix) with ESMTPS id 30ADF84070 for ; Mon, 5 Oct 2020 02:50:13 +0000 (UTC) Received: by mail-io1-f41.google.com with SMTP id 67so4248309iob.8 for ; Sun, 04 Oct 2020 19:50:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=5+DwuXU0ZD1kmKzbnXoOpGkjPaQaF3xrd4tInOQuY4s=; b=b7GXaru9+nbI+PNkQ+jIInoFzeOMxUzY6BXTYTFsZCGgHkiBq2E475M2LxvOhWyFJW bZHbZYkLNT23xJbCu8typLu3K2IY4fggWwl2dbX3CSDyECU7lyoHRvxvYbjJD8QdMmr6 DfM5/c1NQZeSAWOzwltcAHhcdzKupHZ8UDywwip3tsk3iqLjASybV31/DTW3vqN1fMva xrE48yA8xvazv3goMqRPQ4E+VSR6AeiI/5nvfxQW2OC0R5Z3rLTyBhmbhrXMGm+YaSOa GxiiEQgsuuAljSfFUb5y46ih5xlnQhBhjbGnP9BGaFJE+4D20ITw63lqejQTtGPoiWzY ZFrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=5+DwuXU0ZD1kmKzbnXoOpGkjPaQaF3xrd4tInOQuY4s=; b=ChNq+UIVIt7LI0oVpuRYcpPoxyLyDl0dQhN9F/GA+O9XI9TgJ4NA/nzmKBLQB5fpar v741JD3/z6gT1rtjF/phC46qGTo300NhVwAlHz3JM3E2NdaLsoehmFK4d8lsY6BIzUiO brNhjLcgMQRIeTuGbKTu7InUh/YZI46zCaDz6bP0Yhl0CMpiEFtbQWvK4Feoqh8bCayx AL0U7GWj1sdfv6+2ZmBL9mDSG5S32peN+iRujZzuiDpOZ2e8+Y6v+WRL/SX57hWfIJ1V qdo+t2SGAteeZrTMzTPUz0+DO11q34OKe7tgHzJ9SB8ng60Mvgtb6H2Md6wnZIg7pO6C 6QAQ== X-Gm-Message-State: AOAM530kBY2/G+7ZDtjlPT8n1jnr0oMuLM4U2/BJeewcVitx8mMX6vbM K+y0OJChxqQjeC3VKk9oHOZdOUcL8v0PD3iZ0Lg= X-Google-Smtp-Source: ABdhPJxYkTGtDQfSFhU6u28QRmG3rmAxDE+RYdyNLn3bwoywZUZDuCgbQkJslUFA8yiZZgieGzzZ4uQHEvNp1t1sRws= X-Received: by 2002:a05:6638:24d1:: with SMTP id y17mr10932701jat.3.1601866212179; Sun, 04 Oct 2020 19:50:12 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Lloyd Fournier Date: Mon, 5 Oct 2020 13:49:48 +1100 Message-ID: To: Leonardo Comandini , Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" X-Mailman-Approved-At: Mon, 05 Oct 2020 08:23:09 +0000 Subject: Re: [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: Mon, 05 Oct 2020 02:50:40 -0000 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 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