Malleable booleans

Hi all,

while working on a BIP62 implementation I discovered yet another type of malleability: the interpretation of booleans.

Any byte array with non-zero bytes in it (ignoring the highest bit of the last byte, which is the sign bit when interpreting as a number) is interpreted as true, anything else as false. Other than numbers, they're not even restricted to 4 bytes. Worse, the code for dealing with booleans is not very consistent: OP_BOOLAND and OP_BOOLOR first interpret their arguments as numbers, and then compare them to 0 to turn them into boolean values.

This means that scripts that use booleans as inputs will be inherently malleable. Given that that seems actually useful (passing in booleans to guide some OP_IF's during execution of several alternatives), I would like to change BIP62 to also state that interpreted booleans must be of minimal encoded size (in addition to numbers).

Any opinions for or against?

On Tue, Oct 14, 2014 at 2:34 AM, Pieter Wuille <pieter.wuille@gmail•com> wrote:

> Hi all,
>
> while working on a BIP62 implementation I discovered yet another type
> of malleability: the interpretation of booleans.
>
> Any byte array with non-zero bytes in it (ignoring the highest bit of
> the last byte, which is the sign bit when interpreting as a number) is
> interpreted as true, anything else as false. Other than numbers,
> they're not even restricted to 4 bytes. Worse, the code for dealing
> with booleans is not very consistent: OP_BOOLAND and OP_BOOLOR first
> interpret their arguments as numbers, and then compare them to 0 to
> turn them into boolean values.
>
> This means that scripts that use booleans as inputs will be inherently
> malleable. Given that that seems actually useful (passing in booleans
> to guide some OP_IF's during execution of several alternatives), I
> would like to change BIP62 to also state that interpreted booleans
> must be of minimal encoded size (in addition to numbers).
>
> Any opinions for or against?

An argument against is that you can currently do something like this:

OP_DUP OP_IF OP_HASH160 PUSH OP_EQUALVERIFY OP_ELSE <stuff> OP_CHECKSIGVERIFY OP_ENDIF

E.g. if your input is non-zero you're giving a hash, if it's zero you're skipping that and running another branch.

Of course you could just encode your script another way... but by that same logic you can 1 OP_QUALVERIFY to bool-ize any input in the true path. The inconsistency in handling makes it more likely that script authors will screw up with bad (for them) consequences, however.

[I just asked pieter out of band to clarify if he means "minimal encoded size", or must be 0 or 1 minimally encoded... as the former doesn't fix the malleability, but the later is more disruptive]

On Tuesday 14. October 2014 04.34.16 Pieter Wuille wrote:

> This means that scripts that use booleans as inputs will be inherently
> malleable.

I've ran into this issue in C++ often enough, a funny example is assigning "2" to a native c++ bool and then you can do a if (myBool == true) else if (myBool == false) and neither of them will hit.

> I
> would like to change BIP62 to also state that interpreted booleans
> must be of minimal encoded size (in addition to numbers).

What about rejecting a script where a bool is not explicitly zero or one?

On Tue, Oct 14, 2014 at 7:27 AM, Thomas Zander <thomas@thomaszander•se> wrote:

> What about rejecting a script where a bool is not explicitly zero or one?

I believe this is what he actually meant.

On Tue, Oct 14, 2014 at 9:27 AM, Thomas Zander <thomas@thomaszander•se> wrote:

> On Tuesday 14. October 2014 04.34.16 Pieter Wuille wrote:
>> This means that scripts that use booleans as inputs will be inherently
>> malleable.
>
> I've ran into this issue in C++ often enough,
> a funny example is assigning "2" to a native c++ bool and then you can do a
>  if (myBool == true)
>  else if (myBool == false)
> and neither of them will hit.

Off topic nit: I think you're confused with custom BOOL typedefs in C? C++ booleans are protected against this (C++ standard §4.7/4 according to Google).:

``` #include <stdio.h>

int main()
{
    bool myBool;
    myBool = 2;
    if (myBool == true)
        printf("It is true!\n");
    else if (myBool == false)
        printf("It is false!\n");
    else
        printf("It is something else!\n");
}
```

Prints 'It is true'. You can also use bool(something) as equivalent of `x != 0`; as in `assert(bool(2) == true);`.

Wladimir

On Mon, Oct 13, 2014 at 07:34:16PM -0700, Pieter Wuille wrote:

> Hi all,
>
> while working on a BIP62 implementation I discovered yet another type
> of malleability: the interpretation of booleans.
>
> Any byte array with non-zero bytes in it (ignoring the highest bit of
> the last byte, which is the sign bit when interpreting as a number) is
> interpreted as true, anything else as false. Other than numbers,
> they're not even restricted to 4 bytes. Worse, the code for dealing
> with booleans is not very consistent: OP_BOOLAND and OP_BOOLOR first
> interpret their arguments as numbers, and then compare them to 0 to
> turn them into boolean values.
>
> This means that scripts that use booleans as inputs will be inherently
> malleable. Given that that seems actually useful (passing in booleans
> to guide some OP_IF's during execution of several alternatives), I
> would like to change BIP62 to also state that interpreted booleans
> must be of minimal encoded size (in addition to numbers).
>
> Any opinions for or against?

I noticed this awhile back myself. More interestingly, I remember noticing some non-std scripts on mainnet that had opcodes that appeared to be attempts to solve this issue with variations of the following:

    DUP
    IF
        1 EQUALVERIFY
        <do stuff>
    ELSE
        0 EQUALVERIFY
        <do stuff>
    ENDIF

I'll have to admit, I decided to keep quiet about it because it's a good example of how relying on BIP62 for specialty contract applications that absolutely need to avoid malleability for security reasons is a dubious idea; it's hard to be sure that we've really gotten every relevant case correct.

I think a decent argument *for* doing this is that if a script author fails to properly 'bool-ize' every boolean-using path that can have non-minimal encodings in normal execution, you can always create a nVersion=1 transaction manually to spend the output, preventing funds from getting lost. Meanwhile in the general case of a compenent script author having the canonical bool testing in every boolean-using opcode saves a lot of bytes.

To be clear: I indeed meant to only allow 0 and 1 as booleans (or, more precisely: [] and [0x01]). Evaluating any stack element as a boolean that is not any of these would result in script failure.

The only places where this is relevant: * Inputs to OP_IF and OP_NOTIF (which are currently allowed to be any byte array). * Inputs to OP_BOOLAND and OP_BOOLOR (which are currently allowed to be any valid number). * The resulting final element on the stack for validity.

The code for converting stack elements to booleans is also invoked for all OP_*VERIFY operators, but for those it is always the output of a previous operator, so it will not have any semantic impact.

On Tue, Oct 14, 2014 at 1:09 AM, Peter Todd <pete@petertodd•org> wrote:

> I noticed this awhile back myself. More interestingly, I remember
> noticing some non-std scripts on mainnet that had opcodes that appeared
> to be attempts to solve this issue with variations of the following:
>
>     DUP
>     IF
>         1 EQUALVERIFY
>         <do stuff>
>     ELSE
>         0 EQUALVERIFY
>         <do stuff>
>     ENDIFo.
>
> I'll have to admit, I decided to keep quiet about it because it's a good
> example of how relying on BIP62 for specialty contract applications that
> absolutely need to avoid malleability for security reasons is a dubious
> idea; it's hard to be sure that we've really gotten every relevant case
> correct.

I think my goal is to have the property that for every possible script, there is an equivalent one that is non-malleable. There are likely still holes in that idea, but at least for just standard scripts I think BIP62 (as is) covers this. And as your example points out (Greg and I discussed this, though we didn't come up with such a concise one), it is already possible for boolean inputs too.

> I think a decent argument *for* doing this is that if a script author
> fails to properly 'bool-ize' every boolean-using path that can have
> non-minimal encodings in normal execution, you can always create a
> nVersion=1 transaction manually to spend the output, preventing funds
> from getting lost. Meanwhile in the general case of a compenent script
> author having the canonical bool testing in every boolean-using opcode
> saves a lot of bytes.

The real question is whether there are use cases for not having this requirement. I can't come up with any, as that would imply a boolean that is also interpretable as a hash, a pubkey or a signature - all of which seems crpytographically impossible to ever result in false.

On Tue, Oct 14, 2014 at 11:54:36AM -0700, Pieter Wuille wrote:

> > I think a decent argument *for* doing this is that if a script author
> > fails to properly 'bool-ize' every boolean-using path that can have
> > non-minimal encodings in normal execution, you can always create a
> > nVersion=1 transaction manually to spend the output, preventing funds
> > from getting lost. Meanwhile in the general case of a compenent script
> > author having the canonical bool testing in every boolean-using opcode
> > saves a lot of bytes.
>
> The real question is whether there are use cases for not having this
> requirement. I can't come up with any, as that would imply a boolean
> that is also interpretable as a hash, a pubkey or a signature - all of
> which seems crpytographically impossible to ever result in false.

I'm kinda inclined to agree, however there is an opposing argument too: How often is BOOLAND and BOOLOR applied to unsanitised input from the scriptSig? I can't think of a script type where that would be the case, unlike OP_IF where the logical way of writing scripts is to have the scriptSig select which brance you take. In every script I've ever thought of BOOLAND and BOOLOR is applied to stuff generated within the script itself, which isn't a malleability concern.