shiva sitamraju via bitcoin-dev
2017-09-09 14:08:21 UTC
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.
On Fri, Sep 8, 2017 at 2:09 AM, <
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.
On Fri, Sep 8, 2017 at 2:09 AM, <
Send bitcoin-dev mailing list submissions to
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
You can reach the person managing the list at
When replying, please edit your Subject line so it is more specific
than "Re: Contents of bitcoin-dev digest..."
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
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
BIP-32 wallets
Content-Type: text/plain; charset=utf-8
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.
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
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
BIP-32 wallets
Content-Type: text/plain; charset=windows-1252
sense to export xpub for m or m/0' for your particular case.
it?
--
Best Regards / S pozdravom,
Pavol "stick" Rusnak
CTO, SatoshiLabs
------------------------------
Message: 3
Date: Thu, 7 Sep 2017 13:04:30 -0700
Cc: Bitcoin Protocol Discussion
Subject: Re: [bitcoin-dev] Fast Merkle Trees
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
<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
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.
really the crux of the matter).
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
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
BIP-32 wallets
Content-Type: text/plain; charset=windows-1252
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
End of bitcoin-dev Digest, Vol 28, Issue 17
*******************************************
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
You can reach the person managing the list at
When replying, please edit your Subject line so it is more specific
than "Re: Contents of bitcoin-dev digest..."
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
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
BIP-32 wallets
Content-Type: text/plain; charset=utf-8
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 notfollow 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?
In case of Bitcoin Wallet, the depth is not null (m/0'/[0,1]) and stillor at all times. What is your suggestion, Thomas?
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
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
BIP-32 wallets
Content-Type: text/plain; charset=windows-1252
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 makewe need this field.
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.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.
Is that really the case? Why come up with a hierarchy and then don't usemixed. 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.
it?
--
Best Regards / S pozdravom,
Pavol "stick" Rusnak
CTO, SatoshiLabs
------------------------------
Message: 3
Date: Thu, 7 Sep 2017 13:04:30 -0700
Cc: Bitcoin Protocol Discussion
Subject: Re: [bitcoin-dev] Fast Merkle Trees
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
<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
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.
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
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).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
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) ||
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 isObserve that when data is less than 55 bytes then double-SHA256(data) =
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 betweenpadding-SHA256(innocuous)
and
fast-SHA256(double-SHA256(malign) || r2) || r1
r1 can freely be set to the second half of padding-SHA256(innocuous), so
fast-SHA256(double-SHA256(malign) || r2)
and the first half of padding-SHA256(innocuous) which is equal to the
first 32 bytes of innocuous.and the first half of padding-SHA256(innocuous) which is equal to the
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 offast-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
Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for
BIP-32 wallets
Content-Type: text/plain; charset=windows-1252
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 notfollow 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?
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
End of bitcoin-dev Digest, Vol 28, Issue 17
*******************************************