[Bitcoin-development] Small update to BIP 62

[Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

Hi all,

I've sent a pull request to make a small change to BIP 62 (my
anti-malleability proposal) which is still a draft; see:
* https://github.com/bitcoin/bips/pull/90 (the request)
* https://github.com/sipa/bips/blob/bip62up/bip-0062.mediawiki (the result)

It makes two of the 7 new rules mandatory in new blocks, even for
old-style transactions. Both are already non-standard since 0.8.0, and
have no use cases in my opinion.

The reason for this change is dropping the requirement for signature
verification engines to be bug-for-bug compatible with OpenSSL (which
supports many non-standard encodings for signatures). Requiring strict
DER compliance for signatures means any implementation just needs to
support DER.

Comments?

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 548 bytes --]

The rationale doesn't seem to apply to rule #4, what's so special about
that one?

Although I agree not having to support all of DER is nice, in practice I
think all implementations do and libraries to parse DER are widespread.
Given that the last time we modified tx rules without bumping version
numbers we managed to break the only functioning iPhone client, I've become
a big fan of backwards compatibility: seems the default choice should be to
preserve compatibility over technical niceness until the old versions have
been fully phased out.

[-- Attachment #2: Type: text/html, Size: 608 bytes --]

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Fri, Jul 18, 2014 at 5:39 PM, Mike Hearn <mike@plan99.net> wrote:
> The rationale doesn't seem to apply to rule #4, what's so special about that
> one?

Nothing really. If it's controversial in any way, I'm fine with
changing that. It's just one those things that nobody needs, nobody
uses, has never been standard, and shouldn't have been possible in the
first place IMHO. Given that, it's easier to just make it a consensus
rule.

> Although I agree not having to support all of DER is nice, in practice I
> think all implementations do and libraries to parse DER are widespread.
> Given that the last time we modified tx rules without bumping version
> numbers we managed to break the only functioning iPhone client, I've become
> a big fan of backwards compatibility: seems the default choice should be to
> preserve compatibility over technical niceness until the old versions have
> been fully phased out.

I'm not comfortable with dropping OpenSSL-based signature parsing
until we have well-defined rules about which encodings are valid. At
this point I'm not even convinced we *know* about all possible ways to
modify signature encodings without invalidating them.

But perhaps we should investigate how many non-DER signatures still
make it into blocks first...

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Fri, Jul 18, 2014 at 5:45 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> But perhaps we should investigate how many non-DER signatures still
> make it into blocks first...

In the last 11 blocks (4148 transactions), apparently none.

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Fri, Jul 18, 2014 at 7:25 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> On Fri, Jul 18, 2014 at 5:45 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
>> But perhaps we should investigate how many non-DER signatures still
>> make it into blocks first...
>
> In the last 11 blocks (4148 transactions), apparently none.

Or even in the last 389 blocks (159466 transactions).

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Wladimir]

On Fri, Jul 18, 2014 at 5:39 PM, Mike Hearn <mike@plan99.net> wrote:
> The rationale doesn't seem to apply to rule #4, what's so special about that
> one?

> 4. Non-push operations in scriptSig Any non-push operation in a scriptSig invalidates it.

Having non-push operations in the scriptSig is a source of
malleability, as there can be multiple sequences of opcodes that
evaluate to the same result.

Wladimir

Re: [Bitcoin-development] Small update to BIP 62

[Aaron Voisine]

> 9. New signatures by the sender

I'm not suggesting it be required, but it would be possible to
mitigate this one by requiring that all signatures deterministically
generate k per RFC6979. I'm using this in breadwallet.

Aaron Voisine
breadwallet.com


On Fri, Jul 18, 2014 at 1:56 PM, Wladimir <laanwj@gmail.com> wrote:
> On Fri, Jul 18, 2014 at 5:39 PM, Mike Hearn <mike@plan99.net> wrote:
>> The rationale doesn't seem to apply to rule #4, what's so special about that
>> one?
>
>> 4. Non-push operations in scriptSig Any non-push operation in a scriptSig invalidates it.
>
> Having non-push operations in the scriptSig is a source of
> malleability, as there can be multiple sequences of opcodes that
> evaluate to the same result.
>
> Wladimir
>
> ------------------------------------------------------------------------------
> Want fast and easy access to all the code in your enterprise? Index and
> search up to 200,000 lines of code with a free copy of Black Duck
> Code Sight - the same software that powers the world's largest code
> search on Ohloh, the Black Duck Open Hub! Try it now.
> http://p.sf.net/sfu/bds
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Small update to BIP 62

[Gregory Maxwell]

On Fri, Jul 18, 2014 at 3:03 PM, Aaron Voisine <voisine@gmail.com> wrote:
>> 9. New signatures by the sender
>
> I'm not suggesting it be required, but it would be possible to
> mitigate this one by requiring that all signatures deterministically
> generate k per RFC6979. I'm using this in breadwallet.

Nope.

Your homework assignment is to explain why. :)

Re: [Bitcoin-development] Small update to BIP 62

[Aaron Voisine]

Well, you could always create a transaction with a different signature
hash, say, by changing something trivial like nLockTime, or changing
the order of inputs or outputs. Is that what you're talking about? Or
is there some sophistry I'm ignorant of having to do with the elliptic
curve math in the signature itself?

Aaron Voisine
breadwallet.com


On Fri, Jul 18, 2014 at 6:28 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> On Fri, Jul 18, 2014 at 3:03 PM, Aaron Voisine <voisine@gmail.com> wrote:
>>> 9. New signatures by the sender
>>
>> I'm not suggesting it be required, but it would be possible to
>> mitigate this one by requiring that all signatures deterministically
>> generate k per RFC6979. I'm using this in breadwallet.
>
> Nope.
>
> Your homework assignment is to explain why. :)

Re: [Bitcoin-development] Small update to BIP 62

[Gregory Maxwell]

On Fri, Jul 18, 2014 at 9:38 PM, Aaron Voisine <voisine@gmail.com> wrote:
> Well, you could always create a transaction with a different signature
> hash, say, by changing something trivial like nLockTime, or changing
> the order of inputs or outputs. Is that what you're talking about? Or
> is there some sophistry I'm ignorant of having to do with the elliptic
> curve math in the signature itself?

No, though thats true too. I was talking about the properties of the DSA nonce:

An attacker is not obligated to follow your protocol unless you can
prevent him. You can _say_ use derandomized DSA all you like, but he
can just not do so, there is no (reasonable) way to prove you're using
a particular nonce generation scheme without revealing the private key
in the process. The verifier cannot know the nonce or he can trivially
recover your private key thus he can't just repeat the computation
(well, plus if you're using RFC6979 the computation includes the
private key), so short of a very fancy ZKP (stuff at the forefront of
cryptographic/computer science) or precommiting to a nonce per public
key (e.g. single use public keys), you cannot control how a DSA nonce
was generated in the verifier in a way that would prevent equivalent
but not identical signatures.

(I believe there was some P.O.S. altcoin that was vulnerable because
of precisely the above too— thinking specifying a deterministic signer
would prevent someone from grinding signatures to improve their mining
odds... there are signature systems which are naturally
randomness-free: most hash based signatures and pairing short
signatures are two examples that come to mind... but not DSA, schnorr,
or any of their derivatives).

Re: [Bitcoin-development] Small update to BIP 62

[Aaron Voisine]

Ah, good point. For some reason I was thinking the k value was
generated only from the hash being signed, but it's derived from both
the private key and the hash, so as you say there's no way for the
verifier to tell if the scheme is being followed.



Aaron Voisine
breadwallet.com


On Fri, Jul 18, 2014 at 11:56 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> On Fri, Jul 18, 2014 at 9:38 PM, Aaron Voisine <voisine@gmail.com> wrote:
>> Well, you could always create a transaction with a different signature
>> hash, say, by changing something trivial like nLockTime, or changing
>> the order of inputs or outputs. Is that what you're talking about? Or
>> is there some sophistry I'm ignorant of having to do with the elliptic
>> curve math in the signature itself?
>
> No, though thats true too. I was talking about the properties of the DSA nonce:
>
> An attacker is not obligated to follow your protocol unless you can
> prevent him. You can _say_ use derandomized DSA all you like, but he
> can just not do so, there is no (reasonable) way to prove you're using
> a particular nonce generation scheme without revealing the private key
> in the process. The verifier cannot know the nonce or he can trivially
> recover your private key thus he can't just repeat the computation
> (well, plus if you're using RFC6979 the computation includes the
> private key), so short of a very fancy ZKP (stuff at the forefront of
> cryptographic/computer science) or precommiting to a nonce per public
> key (e.g. single use public keys), you cannot control how a DSA nonce
> was generated in the verifier in a way that would prevent equivalent
> but not identical signatures.
>
> (I believe there was some P.O.S. altcoin that was vulnerable because
> of precisely the above too— thinking specifying a deterministic signer
> would prevent someone from grinding signatures to improve their mining
> odds... there are signature systems which are naturally
> randomness-free: most hash based signatures and pairing short
> signatures are two examples that come to mind... but not DSA, schnorr,
> or any of their derivatives).

Re: [Bitcoin-development] Small update to BIP 62

[Aaron Voisine]

Thanks g.maxwell, your explanation of *why* you can't just generate k
in a way that the verifier can duplicate is really helpful. This also
servers as a great illustration why engineers should never try to
designing their own crypto protocols! I knew enough to know not try
that at least.

Aaron Voisine
breadwallet.com


On Fri, Jul 18, 2014 at 11:56 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> On Fri, Jul 18, 2014 at 9:38 PM, Aaron Voisine <voisine@gmail.com> wrote:
>> Well, you could always create a transaction with a different signature
>> hash, say, by changing something trivial like nLockTime, or changing
>> the order of inputs or outputs. Is that what you're talking about? Or
>> is there some sophistry I'm ignorant of having to do with the elliptic
>> curve math in the signature itself?
>
> No, though thats true too. I was talking about the properties of the DSA nonce:
>
> An attacker is not obligated to follow your protocol unless you can
> prevent him. You can _say_ use derandomized DSA all you like, but he
> can just not do so, there is no (reasonable) way to prove you're using
> a particular nonce generation scheme without revealing the private key
> in the process. The verifier cannot know the nonce or he can trivially
> recover your private key thus he can't just repeat the computation
> (well, plus if you're using RFC6979 the computation includes the
> private key), so short of a very fancy ZKP (stuff at the forefront of
> cryptographic/computer science) or precommiting to a nonce per public
> key (e.g. single use public keys), you cannot control how a DSA nonce
> was generated in the verifier in a way that would prevent equivalent
> but not identical signatures.
>
> (I believe there was some P.O.S. altcoin that was vulnerable because
> of precisely the above too— thinking specifying a deterministic signer
> would prevent someone from grinding signatures to improve their mining
> odds... there are signature systems which are naturally
> randomness-free: most hash based signatures and pairing short
> signatures are two examples that come to mind... but not DSA, schnorr,
> or any of their derivatives).

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

[-- Attachment #1: Type: text/plain, Size: 887 bytes --]

On Jul 18, 2014 4:56 PM, "Wladimir" <laanwj@gmail.com> wrote:
>
> On Fri, Jul 18, 2014 at 5:39 PM, Mike Hearn <mike@plan99.net> wrote:
> > The rationale doesn't seem to apply to rule #4, what's so special about
that
> > one?
>
> > 4. Non-push operations in scriptSig Any non-push operation in a
scriptSig invalidates it.
>
> Having non-push operations in the scriptSig is a source of
> malleability, as there can be multiple sequences of opcodes that
> evaluate to the same result.

Well yes, but that is true for each of the rules and is already covered by
the previous specification in BIP62. Making it mandatory even for old
transaction does not really protect much against malleability as there are
several other sources of malleability that cannot be made mandatory in old
transactions left.

The reason for including #4 is just "allowing this does not benefit anyone".

-- 
Pieter

[-- Attachment #2: Type: text/html, Size: 1167 bytes --]

Re: [Bitcoin-development] Small update to BIP 62

[Wladimir]

On Fri, Jul 18, 2014 at 5:14 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> Hi all,
>
> I've sent a pull request to make a small change to BIP 62 (my
> anti-malleability proposal) which is still a draft; see:
> * https://github.com/bitcoin/bips/pull/90 (the request)
> * https://github.com/sipa/bips/blob/bip62up/bip-0062.mediawiki (the result)
>
> It makes two of the 7 new rules mandatory in new blocks, even for
> old-style transactions. Both are already non-standard since 0.8.0, and
> have no use cases in my opinion.

Looks good to me.

> The reason for this change is dropping the requirement for signature
> verification engines to be bug-for-bug compatible with OpenSSL (which
> supports many non-standard encodings for signatures). Requiring strict
> DER compliance for signatures means any implementation just needs to
> support DER.

This is certainly a good thing. Not even OpenSSL is guaranteed to be
bug-for-bug compatible with its own prior versions forever, so better
to strictly define what is allowed.

Wladimir

Re: [Bitcoin-development] Small update to BIP 62

[Gregory Maxwell]

On Fri, Jul 18, 2014 at 8:14 AM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> Hi all,
>
> I've sent a pull request to make a small change to BIP 62 (my
> anti-malleability proposal) which is still a draft; see:
> * https://github.com/bitcoin/bips/pull/90 (the request)
> * https://github.com/sipa/bips/blob/bip62up/bip-0062.mediawiki (the result)
>
> It makes two of the 7 new rules mandatory in new blocks, even for
> old-style transactions. Both are already non-standard since 0.8.0, and
> have no use cases in my opinion.
>
> The reason for this change is dropping the requirement for signature
> verification engines to be bug-for-bug compatible with OpenSSL (which
> supports many non-standard encodings for signatures). Requiring strict
> DER compliance for signatures means any implementation just needs to
> support DER.

Not related to this change but the definition of rule 4 may not be
sufficiently specific— without a definition someone could reasonably
reach a different conclusion about OP_1NEGATE being a "push
operation", or might even decide any operation which added to the
stack was a "push operation".

Any particular reason to enforce 2 and 4 but not also 5?  Violation of
5 is already non-standard and like 2,4 should be safely enforceable.

Perhaps the rules should be reordered so that the applicable to all
transactions ones are contiguous and first?

> The first six and part of the seventh can be fixed by extra consensus rules.

This should clarify that the scriptPubkey can still specify rules that
are inherently malleable— e.g. require the input stack contain two
pushes which OP_ADD to 11.  Or a more elaborate one— a 1 of 2 check
multisig where the pubkey not selected for signing is selected by a
push in the signature. The current text seems to ignore isomorphisms
of this type. ... they're not important for what the BIP is trying to
achieve, but the document shouldn't cause people to not think that
sort of thing exists.

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Mon, Sep 1, 2014 at 10:48 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> Not related to this change but the definition of rule 4 may not be
> sufficiently specific-- without a definition someone could reasonably
> reach a different conclusion about OP_1NEGATE being a "push
> operation", or might even decide any operation which added to the
> stack was a "push operation".

Good catch - I'll write an update soon.

> Any particular reason to enforce 2 and 4 but not also 5?  Violation of
> 5 is already non-standard and like 2,4 should be safely enforceable.

Perhaps we can go further, and include 6 as well? I see zero use cases
for zero-padded numbers, as their interpretation is already identical
to the non-padded case. I wouldn't include 1 (as it would break a
large amount of wallets today), 3 (which may have a use case in more
complex scripts with conditionals) or 7 (the superfluous element
consumed by CHECKMULTISIG could potentially be used for something in
the future).

> Perhaps the rules should be reordered so that the applicable to all
> transactions ones are contiguous and first?

Ok.

>> The first six and part of the seventh can be fixed by extra consensus rules.
>
> This should clarify that the scriptPubkey can still specify rules that
> are inherently malleable-- e.g. require the input stack contain two
> pushes which OP_ADD to 11.  Or a more elaborate one-- a 1 of 2 check
> multisig where the pubkey not selected for signing is selected by a
> push in the signature. The current text seems to ignore isomorphisms
> of this type. ... they're not important for what the BIP is trying to
> achieve, but the document shouldn't cause people to not think that
> sort of thing exists.

I'll try to reword.

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Wed, Sep 3, 2014 at 6:34 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> On Mon, Sep 1, 2014 at 10:48 PM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
>> Not related to this change but the definition of rule 4 may not be
>> sufficiently specific-- without a definition someone could reasonably
>> reach a different conclusion about OP_1NEGATE being a "push
>> operation", or might even decide any operation which added to the
>> stack was a "push operation".
>
> Good catch - I'll write an update soon.

>> Perhaps the rules should be reordered so that the applicable to all
>> transactions ones are contiguous and first?
> Ok.

>>> The first six and part of the seventh can be fixed by extra consensus rules.
>>
>> This should clarify that the scriptPubkey can still specify rules that
>> are inherently malleable [...]
> I'll try to reword.

I've sent out a new pull request
(https://github.com/bitcoin/bips/pull/102/files) that:
* Changes the order of the rules.
* Adds more reference documentation about minimal pushes and number encodings.
* Clarified that extra consensus rules cannot prevent someone from
creating outputs whose spending transactions will be malleable.

I haven't changed which rules are mandatory in v3, so this is a pure
clarification & reorganization of the text.

Any comments?

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Mon, Sep 8, 2014 at 1:31 AM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> I've sent out a new pull request
> (https://github.com/bitcoin/bips/pull/102/files) that:
> * Changes the order of the rules.
> * Adds more reference documentation about minimal pushes and number encodings.
> * Clarified that extra consensus rules cannot prevent someone from
> creating outputs whose spending transactions will be malleable.
>
> I haven't changed which rules are mandatory in v3, so this is a pure
> clarification & reorganization of the text.

Changes: https://github.com/bitcoin/bips/pull/102/files

Gregory, Jeff: does this address your concerns?
Others: comments?

-- 
Pieter

Re: [Bitcoin-development] Small update to BIP 62

[Pieter Wuille]

On Fri, Sep 12, 2014 at 6:35 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
> Changes: https://github.com/bitcoin/bips/pull/102/files
>
> Gregory, Jeff: does this address your concerns?
> Others: comments?

I've made another change in the PR, as language about strictly only
compressed or uncompressed public keys was missing; please have a
look.

-- 
Pieter