Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Anthony Towns via bitcoin-dev]

On Wed, Nov 21, 2018 at 12:07:30PM -0500, Russell O'Connor via bitcoin-dev 
wrote:
> Given that we want to move away from OP_CODESEPARATOR, because each call to
> this operation effectively takes O(script-size) time, we need a replacement 
> for
> the functionality it currently provides.  While perhaps the original 
> motivation
> for OP_CODESEPARTOR is surrounded in mystery, it currently can be used (or
> perhaps abused) for the task of creating signature that covers, not only which
> input is being signed, but which specific branch within that input Script code
> is being signed for.

Would it be sufficient to sign the position within the script of the
last OP_CODESEPARATOR? That is, if your script is:

   DUP DUP CHECKSIG CODESEP CHECKSIG CODESEP CHECKSIG

with the idea being that it can be spent by providing any pub key and
three different signatures by that key, with the first sig committing
to a "codesep position" of 0, the second a "codesep position" of 4,
and the third a "codesep position" of 6? In each case, the signature
also commits to the full (possibly masked) script as well.

I think that covers all the behaviour you can currently achieve with
CODESEP (which is pretty limited since every sig effectively commits
to the full redeem script, and you can't commit to subsets of the
signature/witness), and it keeps the things you can do with the various
features a bit orthogonal:

 NOINPUT -- lets the sig apply to different transactions
 OP_MASK -- lets the different txes have variations in the script the
sig applies to
 CODESEP -- lets you require different sigs for different parts of a
single script
 MAST[0] -- provides alternative scripts, doesn't affect sigs
 IF/etc  -- provides control flow within a script, doesn't affect sigs

Cheers,
aj

[0] (I think I'm going to claim "MAST" stands for "merkelized alternative
 script tree" these days, since they're not "abstract syntax trees")

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Russell O'Connor via bitcoin-dev]

On Thu, Nov 22, 2018 at 3:53 PM Johnson Lau  wrote:

> Assuming a script size of 128 bytes (including SHA256 padding), 2^20
> scripts is 134MB. Double it to 268MB for the merkle branch hashes. With
> roughly 100MB/s, this should take 2.5s (or 42min for 30 levels). However,
> memory use is not considered.
>
> >each call to this operation effectively takes O(script-size) time
> I’m not sure if this is correct. Actually,
> CTransactionSignatureSerializer() scans every script for OP_CODESEPARATOR.
> Scripts with and without OP_CODESEPARATOR should take exactly the same
> O(script-size) time (see https://github.com/bitcoin/bitcoin/pull/14786)
> Also, this is no longer a concern under segwit (BIP143), which
> CTransactionSignatureSerializer() is not used. Actually, OP_CODESEPARATOR
> under segwit is way simpler than the proposed OP_MASK. If one finds OP_MASK
> acceptable, there should be no reason to reject OP_CODESEPARATOR.
>

Even still, each call to OP_CODESEPARATOR / OP_CHECKSIG pair requires
recomputing a new #5. scriptCode from BIP 143, and hence computes a new
transaction digest.  I understood that this issue was the main motivation
for wanting to deprecate OP_CODESEPARATOR and remove it from later versions
of script.

However, given that we are looking at a combinatorial explosion in SIGHASH
flag combinations already, coupled with existing SigOp limitations, maybe
the cost of recomputing scriptCode with OP_CODESEPARATOR isn't such a big
deal.

And even if we choose remove the behavior of OP_CODESEPARATOR in new
versions of Script, it seems more than 30 layers of sequential OP_IFs can
be MASTified, so there is no need to use OP_CODESEPARATOR within that limit.

>One suggestion I heard (I think I heard it from Pieter) to achieve the
above is to add an internal counter that increments on every control flow
operator,……...

> If I have to choose among OP_CODESEPARATOR and “flow operator counting”,
> I’d rather choose OP_CODESEPARATOR. At least we don’t need to add more
> lines to the consensus code, just for something that is mostly archivable
> with MAST.
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Johnson Lau via bitcoin-dev]

Assuming a script size of 128 bytes (including SHA256 padding), 2^20 scripts is 
134MB. Double it to 268MB for the merkle branch hashes. With roughly 100MB/s, 
this should take 2.5s (or 42min for 30 levels). However, memory use is not 
considered.

>each call to this operation effectively takes O(script-size) time
I’m not sure if this is correct. Actually, CTransactionSignatureSerializer() 
scans every script for OP_CODESEPARATOR. Scripts with and without 
OP_CODESEPARATOR should take exactly the same O(script-size) time (see 
https://github.com/bitcoin/bitcoin/pull/14786)
Also, this is no longer a concern under segwit (BIP143), which 
CTransactionSignatureSerializer() is not used. Actually, OP_CODESEPARATOR under 
segwit is way simpler than the proposed OP_MASK. If one finds OP_MASK 
acceptable, there should be no reason to reject OP_CODESEPARATOR.

>One suggestion I heard (I think I heard it from Pieter) to achieve the above 
>is to add an internal counter that increments on every control flow 
>operator,……...
If I have to choose among OP_CODESEPARATOR and “flow operator counting”, I’d 
rather choose OP_CODESEPARATOR. At least we don’t need to add more lines to the 
consensus code, just for something that is mostly archivable with MAST.


> On 23 Nov 2018, at 12:23 AM, Russell O'Connor  wrote:
> 
> I see, so your suggestion is that a sequence of OP_IF ... OP_ENDIF can be 
> replaced by a Merklized Script tree of that depth in practice.
> 
> I'm concerned that at script creation time it takes exponential time to 
> complete a Merkle root of depth 'n'.  Can anyone provide benchmarks or 
> estimates of how long it takes to compute a Merkle root of a full tree of 
> various depths on typical consumer hardware?  I would guess things stop 
> becoming practical at a depth of 20-30.
> 
> On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau  wrote:
> With MAST in taproot, OP_IF etc become mostly redundant, with worse privacy. 
> To maximise fungibility, we should encourage people to use MAST, instead of 
> improve the functionality of OP_IF and further complicate the protocol.
> 
> 
>> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev 
>>  wrote:
>> 
>> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev 
>>  wrote:
>> So my question is whether anyone can see ways in which this introduces
>> redundant flexibility, or misses obvious use cases?
>> 
>> Hopefully my comment is on-topic for this thread:
>> 
>> Given that we want to move away from OP_CODESEPARATOR, because each call to 
>> this operation effectively takes O(script-size) time, we need a replacement 
>> for the functionality it currently provides.  While perhaps the original 
>> motivation for OP_CODESEPARTOR is surrounded in mystery, it currently can be 
>> used (or perhaps abused) for the task of creating signature that covers, not 
>> only which input is being signed, but which specific branch within that 
>> input Script code is being signed for.
>> 
>> For example, one can place an OP_CODESEPARATOR within each branch of an IF 
>> block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG operation.  
>> By doing so, signatures created for one clause cannot be used as signatures 
>> for another clause.  Since different clauses in Bitcoin Script may be 
>> enforcing different conditions (such as different time-locks, hash-locks, 
>> etc), it is useful to be able to sign in such a way that your signature is 
>> only valid when the conditions for a particular branch are satisfied.  In 
>> complex Scripts, it may not be practical or possible to use different public 
>> keys for every different clause. (In practice, you will be able to get away 
>> with fewer OP_CODESEPARATORS than one in every IF block).
>> 
>> One suggestion I heard (I think I heard it from Pieter) to achieve the above 
>> is to add an internal counter that increments on every control flow 
>> operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the signature cover 
>> the value of this counter.  Equivalently we divide every Bitcoin Script 
>> program into blocks deliminated by these control flow operator and have the 
>> signature cover the index of the block that the OP_CHECKSIG occurs within.  
>> More specifically, we will want a SigHash flag to enables/disable the 
>> signature covering this counter.
>> 
>> There are many different ways one might go about replacing the remaining 
>> useful behaviour of OP_CODESEPARATOR than the one I gave above. I would be 
>> happy with any solution.
>> ___
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] BIP- & SLIP-0039 -- better multi-language support

[Weiji Guo via bitcoin-dev]

Hi Everyone,

Thank you very much in this thanks giving day for the detailed and well
thought out responses. :)

Steven Hatzakis via bitcoin-dev https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>>:

>* *Option 2*: Perhaps a revision is needed to how the BIP39 seed is
*>* generated in the first place, such as by hashing the entropy instead of the
*>* words. Any thoughts on how viable that could be where the initial entropy
*>* is fed into the PBKDF2 function and not the words?*

If we go this direction, I'd suggest that we pull Shamir's Secret Sharing
into the game. Trezor's
SLIP-0039 proposal is great and has many security aspects already covered.
However, it does
not allow any language other than English and Trezor team clearly stated
that no other language
will be supported.

While I really want to keep the language independent design. So in the
revision, I'd like to see
a language id (allocated to each one having a defined wordlist) in the SSS
share, as well as
share id, threshold, index, share value, checksum etc.

Regarding checksum scheme, SLIP-0039 proposals a 3-word Reed-Solomon
design. It has a very
good error checking capability but not very good at providing hints to
error recovery. Trezor team
opposes to the idea of providing hints to users regarding how to fix an
error. This could lead to
difficulties for some vendors, and in small probability, confusions to
users (when there is a 2-word
error)

I do agree with Trezor team that it should be users' responsibility to
recover from a detected error.
However, there is a better way than solely rely on checksum. That is, as in
our revision, we can
support mnemonic in multiple languages simultaneously, why don't we use two
languages, or one
language + numbers to check each other? In Steven's example (language id,
share id, etc. skipped)
we could record a SSS share (assuming it is one of the shares just for the
sake of example) like:

>* *In English*: minimum fee sure ticket faculty banana gate purse caught
*>* valley globe shift
*>* *In Spanish*: mercado faja soledad tarea evadir aries gafas peine búho
*>* tumor gerente reja*

Or

>* *In English*: minimum fee sure ticket faculty banana gate purse caught
*>* valley globe shift*

>* Word Indexes: 1128, 676, 1744, 1805, 653, 145, 770, 1396, 291, 1927,
794, 1582*


Then software will have to check checksum as well as to check if words
match each other. For
example, "minimum"'s index value in English wordlist should equal to "
*mercado*"'s in Spanish,
or should equal to 1128.

If any error is detected, combining the checksum value and dual-encoding
information, it is much
easier to figure out which word was handprinted incorrectly.

BTW, it is very error prone to handprint. Some study suggests about 0.9%
per word rate. See
http://panko.shidler.hawaii.edu/HumanErr/Basic.htm

Hotopf [1980]

W sample (written exam). Per word

0.9%

It is important to have an error recovery mechanism easy to understand and
implement.

Thanks,
Weiji
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Russell O'Connor via bitcoin-dev]

I see, so your suggestion is that a sequence of OP_IF ... OP_ENDIF can be
replaced by a Merklized Script tree of that depth in practice.

I'm concerned that at script creation time it takes exponential time to
complete a Merkle root of depth 'n'.  Can anyone provide benchmarks or
estimates of how long it takes to compute a Merkle root of a full tree of
various depths on typical consumer hardware?  I would guess things stop
becoming practical at a depth of 20-30.

On Thu, Nov 22, 2018 at 9:28 AM Johnson Lau  wrote:

> With MAST in taproot, OP_IF etc become mostly redundant, with worse
> privacy. To maximise fungibility, we should encourage people to use MAST,
> instead of improve the functionality of OP_IF and further complicate the
> protocol.
>
>
> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> So my question is whether anyone can see ways in which this introduces
>> redundant flexibility, or misses obvious use cases?
>>
>
> Hopefully my comment is on-topic for this thread:
>
> Given that we want to move away from OP_CODESEPARATOR, because each call
> to this operation effectively takes O(script-size) time, we need a
> replacement for the functionality it currently provides.  While perhaps the
> original motivation for OP_CODESEPARTOR is surrounded in mystery, it
> currently can be used (or perhaps abused) for the task of creating
> signature that covers, not only which input is being signed, but which
> specific branch within that input Script code is being signed for.
>
> For example, one can place an OP_CODESEPARATOR within each branch of an IF
> block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG
> operation.  By doing so, signatures created for one clause cannot be used
> as signatures for another clause.  Since different clauses in Bitcoin
> Script may be enforcing different conditions (such as different time-locks,
> hash-locks, etc), it is useful to be able to sign in such a way that your
> signature is only valid when the conditions for a particular branch are
> satisfied.  In complex Scripts, it may not be practical or possible to use
> different public keys for every different clause. (In practice, you will be
> able to get away with fewer OP_CODESEPARATORS than one in every IF block).
>
> One suggestion I heard (I think I heard it from Pieter) to achieve the
> above is to add an internal counter that increments on every control flow
> operator, OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the signature cover
> the value of this counter.  Equivalently we divide every Bitcoin Script
> program into blocks deliminated by these control flow operator and have the
> signature cover the index of the block that the OP_CHECKSIG occurs within.
> More specifically, we will want a SigHash flag to enables/disable the
> signature covering this counter.
>
> There are many different ways one might go about replacing the remaining
> useful behaviour of OP_CODESEPARATOR than the one I gave above. I would be
> happy with any solution.
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Safer sighashes and more granular SIGHASH_NOINPUT

[Johnson Lau via bitcoin-dev]

With MAST in taproot, OP_IF etc become mostly redundant, with worse privacy. To 
maximise fungibility, we should encourage people to use MAST, instead of 
improve the functionality of OP_IF and further complicate the protocol.


> On 22 Nov 2018, at 1:07 AM, Russell O'Connor via bitcoin-dev 
>  wrote:
> 
> On Mon, Nov 19, 2018 at 10:22 PM Pieter Wuille via bitcoin-dev 
>  > wrote:
> So my question is whether anyone can see ways in which this introduces
> redundant flexibility, or misses obvious use cases?
> 
> Hopefully my comment is on-topic for this thread:
> 
> Given that we want to move away from OP_CODESEPARATOR, because each call to 
> this operation effectively takes O(script-size) time, we need a replacement 
> for the functionality it currently provides.  While perhaps the original 
> motivation for OP_CODESEPARTOR is surrounded in mystery, it currently can be 
> used (or perhaps abused) for the task of creating signature that covers, not 
> only which input is being signed, but which specific branch within that input 
> Script code is being signed for.
> 
> For example, one can place an OP_CODESEPARATOR within each branch of an IF 
> block, or by placing an OP_CODESEPARATOR before each OP_CHECKSIG operation.  
> By doing so, signatures created for one clause cannot be used as signatures 
> for another clause.  Since different clauses in Bitcoin Script may be 
> enforcing different conditions (such as different time-locks, hash-locks, 
> etc), it is useful to be able to sign in such a way that your signature is 
> only valid when the conditions for a particular branch are satisfied.  In 
> complex Scripts, it may not be practical or possible to use different public 
> keys for every different clause. (In practice, you will be able to get away 
> with fewer OP_CODESEPARATORS than one in every IF block).
> 
> One suggestion I heard (I think I heard it from Pieter) to achieve the above 
> is to add an internal counter that increments on every control flow operator, 
> OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF, and have the signature cover the value of 
> this counter.  Equivalently we divide every Bitcoin Script program into 
> blocks deliminated by these control flow operator and have the signature 
> cover the index of the block that the OP_CHECKSIG occurs within.  More 
> specifically, we will want a SigHash flag to enables/disable the signature 
> covering this counter.
> 
> There are many different ways one might go about replacing the remaining 
> useful behaviour of OP_CODESEPARATOR than the one I gave above. I would be 
> happy with any solution.
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev