Re: [bitcoin-dev] Proposal: Extended serialization format for BIP-32

From: Thomas Voegtlin <thomasv@electrum•org>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for BIP-32
Date: Tue, 12 Sep 2017 11:06:15 +0200	[thread overview]
Message-ID: <99643f72-f72f-e4e9-ac2b-72bf519c25b5@electrum.org> (raw)
In-Reply-To: <CABuOfuhN6jXgd+KTjFLjM+YkDOVg9=G3tWpeKBJvpUAkpkzjDg@mail.gmail.com>

On 09.09.2017 16:08, shiva sitamraju via bitcoin-dev wrote:
> Hi,
> 
> I understand the motivation of adding the birthdate field. However, not
> very comfortable with having this in the public key serialization. There
> are privacy implication of both the birthday field and having the complete
> derivation path, which takes space.
> > I am fine with Thomas proposal of {x,y,z}. Having additional version byte
> field looks modular but since since we already have the big enough version
> field in bip32, better to use that instead of adding more bytes.
> 
> Thomas, can you please explain why we require different version for P2WPKH
> or P2WSH versus (P2WPKH or P2WSH) nested in P2SH. It looked to me that they
> would have the same output bitcoin address and under same account.

no, native scripts do not have the same address. see bip173

> 
> On Fri, Sep 8, 2017 at 2:09 AM, <
> bitcoin-dev-request@lists•linuxfoundation.org> wrote:
> 
>> Send bitcoin-dev mailing list submissions to
>>         bitcoin-dev@lists•linuxfoundation.org
>>
>> To subscribe or unsubscribe via the World Wide Web, visit
>>         https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> or, via email, send a message with subject or body 'help' to
>>         bitcoin-dev-request@lists•linuxfoundation.org
>>
>> You can reach the person managing the list at
>>         bitcoin-dev-owner@lists•linuxfoundation.org
>>
>> When replying, please edit your Subject line so it is more specific
>> than "Re: Contents of bitcoin-dev digest..."
>>
>>
>> Today's Topics:
>>
>>    1. Re: Proposal: Extended serialization format for   BIP-32
>>       wallets (Andreas Schildbach)
>>    2. Re: Proposal: Extended serialization format for BIP-32
>>       wallets (Pavol Rusnak)
>>    3. Re: Fast Merkle Trees (Mark Friedenbach)
>>    4. Re: Proposal: Extended serialization format for BIP-32
>>       wallets (Thomas Voegtlin)
>>
>>
>> ----------------------------------------------------------------------
>>
>> Message: 1
>> Date: Thu, 7 Sep 2017 21:35:49 +0200
>> From: Andreas Schildbach <andreas@schildbach•de>
>> To: bitcoin-dev@lists•linuxfoundation.org
>> Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
>>         BIP-32 wallets
>> Message-ID: <oos72e$rjp$1@blaine•gmane.org>
>> Content-Type: text/plain; charset=utf-8
>>
>> On 09/07/2017 06:23 PM, Pavol Rusnak via bitcoin-dev wrote:
>>> On 07/09/17 06:29, Thomas Voegtlin via bitcoin-dev wrote:
>>>> A solution is still needed to wallets who do not wish to use BIP43
>>>
>>> What if we added another byte field OutputType for wallets that do not
>>> follow BIP43?
>>>
>>> 0x00 - P2PKH output type
>>> 0x01 - P2WPKH-in-P2SH output type
>>> 0x02 - native Segwit output type
>>>
>>> Would that work for you?
>>
>> I think that would work.
>>
>>> The question is whether this field should be present only if depth==0x00
>>> or at all times. What is your suggestion, Thomas?
>>
>> In case of Bitcoin Wallet, the depth is not null (m/0'/[0,1]) and still
>> we need this field. I think it should always be present if a chain is
>> limited to a certain script type.
>>
>> There is however the case where even on one chain, script types are
>> mixed. In this case the field should be omitted and the wallet needs to
>> scan for all (known) types. Afaik Bitcoin Core is taking this path.
>>
>>
>>
>> ------------------------------
>>
>> Message: 2
>> Date: Thu, 7 Sep 2017 22:00:05 +0200
>> From: Pavol Rusnak <stick@satoshilabs•com>
>> To: Andreas Schildbach <andreas@schildbach•de>, Bitcoin Protocol
>>         Discussion <bitcoin-dev@lists•linuxfoundation.org>
>> Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
>>         BIP-32 wallets
>> Message-ID: <40ed03a1-915c-33b0-c4ac-e898c8c733ba@satoshilabs•com>
>> Content-Type: text/plain; charset=windows-1252
>>
>> On 07/09/17 21:35, Andreas Schildbach via bitcoin-dev wrote:
>>> In case of Bitcoin Wallet, the depth is not null (m/0'/[0,1]) and still
>>> we need this field.
>>
>> But the depth of exported public key will be null. It does not make
>> sense to export xpub for m or m/0' for your particular case.
>>
>>> I think it should always be present if a chain is
>>> limited to a certain script type.
>>
>> I am fine with having the path there all the time.
>>
>>> There is however the case where even on one chain, script types are
>>> mixed. In this case the field should be omitted and the wallet needs to
>>> scan for all (known) types. Afaik Bitcoin Core is taking this path.
>>
>> Is that really the case? Why come up with a hierarchy and then don't use
>> it?
>>
>> --
>> Best Regards / S pozdravom,
>>
>> Pavol "stick" Rusnak
>> CTO, SatoshiLabs
>>
>>
>> ------------------------------
>>
>> Message: 3
>> Date: Thu, 7 Sep 2017 13:04:30 -0700
>> From: Mark Friedenbach <mark@friedenbach•org>
>> To: Russell O'Connor <roconnor@blockstream•io>
>> Cc: Bitcoin Protocol Discussion
>>         <bitcoin-dev@lists•linuxfoundation.org>
>> Subject: Re: [bitcoin-dev] Fast Merkle Trees
>> Message-ID: <40D6F502-3380-4B64-BCD9-80D361EED35C@friedenbach•org>
>> Content-Type: text/plain; charset="us-ascii"
>>
>> TL;DR I'll be updating the fast Merkle-tree spec to use a different
>>       IV, using (for infrastructure compatability reasons) the scheme
>>       provided by Peter Todd.
>>
>> This is a specific instance of a general problem where you cannot
>> trust scripts given to you by another party. Notice that we run into
>> the same sort of problem when doing key aggregation, in which you must
>> require the other party to prove knowledge of the discrete log before
>> using their public key, or else key cancellation can occur.
>>
>> With script it is a little bit more complicated as you might want
>> zero-knowledge proofs of hash pre-images for HTLCs as well as proofs
>> of DL knowledge (signatures), but the basic idea is the same. Multi-
>> party wallet level protocols for jointly constructing scriptPubKeys
>> should require a 'delinearization' step that proves knowledge of
>> information necessary to complete each part of the script, as part of
>> proving the safety of a construct.
>>
>> I think my hangup before in understanding the attack you describe was
>> in actualizing it into a practical attack that actually escalates the
>> attacker's capabilities. If the attacker can get you to agree to a
>> MAST policy that is nothing more than a CHECKSIG over a key they
>> presumably control, then they don't need to do any complicated
>> grinding. The attacker in that scenario would just actually specify a
>> key they control and take the funds that way.
>>
>> Where this presumably leads to an actual exploit is when you specify a
>> script that a curious counter-party actually takes the time to
>> investigate and believes to be secure. For example, a script that
>> requires a signature or pre-image revelation from that counter-party.
>> That would require grinding not a few bytes, but at minimum 20-33
>> bytes for either a HASH160 image or the counter-party's key.
>>
>> If I understand the revised attack description correctly, then there
>> is a small window in which the attacker can create a script less than
>> 55 bytes in length, where nearly all of the first 32 bytes are
>> selected by the attacker, yet nevertheless the script seems safe to
>> the counter-party. The smallest such script I was able to construct
>> was the following:
>>
>>     <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL
>>
>> This is 56 bytes and requires only 7 bits of grinding in the fake
>> pubkey. But 56 bytes is too large. Switching to secp256k1 serialized
>> 32-byte pubkeys (in a script version upgrade, for example) would
>> reduce this to the necessary 55 bytes with 0 bits of grinding. A
>> smaller variant is possible:
>>
>>     DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160
>> <preimage> EQUAL
>>
>> This is 46 bytes, but requires grinding 96 bits, which is a bit less
>> plausible.
>>
>> Belts and suspenders are not so terrible together, however, and I
>> think there is enough of a justification here to look into modifying
>> the scheme to use a different IV for hash tree updates. This would
>> prevent even the above implausible attacks.
>>
>>
>>> On Sep 7, 2017, at 11:55 AM, Russell O'Connor <roconnor@blockstream•io>
>> wrote:
>>>
>>>
>>>
>>> On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark@friedenbach•org
>> <mailto:mark@friedenbach•org>> wrote:
>>> I've been puzzling over your email since receiving it. I'm not sure it
>>> is possible to perform the attack you describe with the tree structure
>>> specified in the BIP. If I may rephrase your attack, I believe you are
>>> seeking a solution to the following:
>>>
>>> Want: An innocuous script and a malign script for which
>>>
>>>    double-SHA256(innocuous)
>>>
>>> is equal to either
>>>
>>>    fast-SHA256(double-SHA256(malign) || r) or
>>>    fast-SHA256(r || double-SHA256(malign))
>>>
>>> or  fast-SHA256(fast-SHA256(double-SHA256(malign) || r1) || r0)
>>> or  fast-SHA256(fast-SHA256(r1 || double-SHA256(malign)) || r0)
>>> or ...
>>>
>>> where r is a freely chosen 32-byte nonce. This would allow the
>>> attacker to reveal the innocuous script before funds are sent to the
>>> MAST, then use the malign script to spend.
>>>
>>> Because of the double-SHA256 construction I do not see how this can be
>>> accomplished without a full break of SHA256.
>>>
>>> The particular scenario I'm imagining is a collision between
>>>
>>>     double-SHA256(innocuous)
>>>
>>> and
>>>
>>>     fast-SHA256(fast-SHA256(fast-SHA256(double-SHA256(malign) || r2) ||
>> r1) || r0).
>>>
>>> where innocuous is a Bitcoin Script that is between 32 and 55 bytes long.
>>>
>>> Observe that when data is less than 55 bytes then double-SHA256(data) =
>> fast-SHA256(fast-SHA256(padding-SHA256(data)) || 0x8000...100) (which is
>> really the crux of the matter).
>>>
>>> Therefore, to get our collision it suffices to find a collision between
>>>
>>>     padding-SHA256(innocuous)
>>>
>>> and
>>>
>>>     fast-SHA256(double-SHA256(malign) || r2) || r1
>>>
>>> r1 can freely be set to the second half of padding-SHA256(innocuous), so
>> it suffices to find a collision between
>>>
>>>    fast-SHA256(double-SHA256(malign) || r2)
>>>
>>> and the first half of padding-SHA256(innocuous) which is equal to the
>> first 32 bytes of innocuous.
>>>
>>> Imagine the first opcode of innocuous is the push of a value that the
>> attacker claims to be his 33-byte public key.
>>> So long as the attacker doesn't need to prove that they know the
>> discrete log of this pubkey, they can grind r2 until the result of
>> fast-SHA256(double-SHA256(malign) || r2) contains the correct first
>> couple of bytes for the script header and the opcode for a 33-byte push.  I
>> believe that is only about 3 or 4 bytes of they need to grind out.
>>>
>>
>> -------------- next part --------------
>> An HTML attachment was scrubbed...
>> URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/
>> attachments/20170907/63af0292/attachment-0001.html>
>>
>> ------------------------------
>>
>> Message: 4
>> Date: Thu, 7 Sep 2017 22:39:17 +0200
>> From: Thomas Voegtlin <thomasv@electrum•org>
>> To: "bitcoin-dev@lists•linuxfoundation.org"
>>         <bitcoin-dev@lists•linuxfoundation.org>
>> Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
>>         BIP-32 wallets
>> Message-ID: <9e74dc17-105c-b43c-7780-4fa690043fe2@electrum•org>
>> Content-Type: text/plain; charset=windows-1252
>>
>>
>>
>> On 07.09.2017 18:23, Pavol Rusnak wrote:
>>> On 07/09/17 06:29, Thomas Voegtlin via bitcoin-dev wrote:
>>>> A solution is still needed to wallets who do not wish to use BIP43
>>>
>>> What if we added another byte field OutputType for wallets that do not
>>> follow BIP43?
>>>
>>> 0x00 - P2PKH output type
>>> 0x01 - P2WPKH-in-P2SH output type
>>> 0x02 - native Segwit output type
>>>
>>> Would that work for you?
>>>
>>> The question is whether this field should be present only if depth==0x00
>>> or at all times. What is your suggestion, Thomas?
>>>
>>
>>
>> well, in my initial proposal, I wrote that this value should be user
>> visible. That is why I used version bytes. If you create an extra byte
>> field, and then use base58 or bech32 encoding, the value will not be
>> user visible anymore.
>>
>> The initial implementation of segwit xpub/xprv in Electrum used a flag
>> that was not user visible (I added 1 to the bip32 version bytes, which
>> leaves the xpub/xprv prefix unchanged). I have experimented with that
>> invisible flag for more than 6 months now, and I am now convinced that
>> it is better to make that flag user visible.
>>
>> The reason is that when users create wallets with multisig scripts, they
>> need to combine several master public keys. However, these master public
>> keys should all be of the same type: it would not make sense to create a
>> 2 of 3 multisig wallet with a one xpub, one ypub and one zpub. By
>> imposing that all master keys are of the same type, we ensure that all
>> cosigners agree on the script type that will be used to derive addresses.
>>
>> In other words, if users are exposed to master keys and need to
>> manipulate them, it is better to let them see what they are doing.
>>
>> OTOH if you do not plan to expose your users to these keys, you probably
>> do not need a serialization format.
>>
>>
>> ------------------------------
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>>
>> End of bitcoin-dev Digest, Vol 28, Issue 17
>> *******************************************
>>
> 
> 
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

-- 
Electrum Technologies GmbH / Waldemarstr 37a / 10999 Berlin / Germany
Sitz, Registergericht: Berlin, Amtsgericht Charlottenburg, HRB 164636
Geschäftsführer: Thomas Voegtlin