Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

On Mon, 16 Sep 2019 at 21:10, ZmnSCPxj via bitcoin-dev
 wrote:

> ‐‐‐ Original Message ‐‐‐
> > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for 
> > segwit
> > v0 for compatibility reasons. Most wallets/exchanges/services now support 
> > sending
> > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and 
> > that
> > will be even more true if Schnorr/Taproot activate in 12+ months time.
> >
> > Apologies for necroing an ancient thread, but I'm echoing my agreement with 
> > John here.
> > We still have plenty of time to have ecosystem upgrade by the time taproot 
> > is likely to activate.

> On the other hand, the major benefit of taproot is the better privacy and 
> homogeneity afforded by Taproot, and supporting both P2SH-wrapped and 
> non-wrapped SegWit v1 addresses simply increases the number of places that a 
> user may be characterized and potentially identified.

I'm starting to lean towards not allowing P2SH wrapped Taproot as well.

Given the progress bech32 adoption has made in the past year or so, I
don't think adding P2SH support would result in many more software
authors deciding to implement receive-to-taproot functionality. And
without that advantage, having the option of supporting P2SH wrapping
actually risks degrading the privacy goals it aims for (see ZmnSCPxj's
argument above).

My main intuition for keeping P2SH is that Segwit was really designed
to support both, and I expect that disallowing P2SH would actually
require (very slightly) more complex validation code. I don't think
this is a sufficiently strong reason, especially as keeping P2SH
support does increase the number of combinations software needs to
test (both in consensus code and wallets).

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[ZmnSCPxj via bitcoin-dev]

Good morning Greg and John,

I am not as sanguine here; SegWit activation was already delayed relative to 
commonly-broadcast expectations, yet many services *still* do not support 
sending to SegWit v0 addresses even now.

On the other hand, the major benefit of taproot is the better privacy and 
homogeneity afforded by Taproot, and supporting both P2SH-wrapped and 
non-wrapped SegWit v1 addresses simply increases the number of places that a 
user may be characterized and potentially identified.

Thus while I disagree with your reasoning, I do agree with your conclusion: no 
P2SH-wrapped SegWit v1.

Regards,
ZmnSCPxj

Sent with ProtonMail Secure Email.

‐‐‐ Original Message ‐‐‐
On Tuesday, September 17, 2019 12:18 AM, Greg Sanders via bitcoin-dev 
 wrote:

> > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for 
> > segwit
> v0 for compatibility reasons. Most wallets/exchanges/services now support 
> sending
> to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and 
> that
> will be even more true if Schnorr/Taproot activate in 12+ months time.
>
> Apologies for necroing an ancient thread, but I'm echoing my agreement with 
> John here.
> We still have plenty of time to have ecosystem upgrade by the time taproot is 
> likely to activate.
>
> On Wed, May 22, 2019 at 10:30 AM John Newbery via bitcoin-dev 
>  wrote:
>
> > Hi,
> >
> > > A Taproot output is a SegWit output [...]  with
> > > version number 1, and a 33-byte witness program whose first byte is 0 or 
> > > 1.
> >
> > Given a secret key k and public key P=(x,y), a signer with the knowledge of 
> > k
> > can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding 
> > the
> > y value of the public key therefore adds no security. As an alternative to
> > providing the y value of the taproot output key Q when constructing the 
> > taproot
> > output, the signer can provide it when signing. We can also restrict the y 
> > value
> > of the internal key P to be even (or high, or a quadratic residue). That 
> > gives
> > us 4 options for how to set the y signs for P and Q.
> >
> > 1. Q sign is explictly set in the witness program, P sign is explicitly set 
> > in the control block
> >     => witness program is 33 bytes, 32 possible leaf versions (one for each 
> > pair of 0xc0..0xff)
> > 2. Q sign is explictly set in the witness program, P sign is implicitly even
> >     => witness program is 33 bytes, 64 possible leaf versions (one for each 
> > 0xc0..0xff)
> > 3. Q sign is explictly set in the control block, P sign is explicitly set 
> > in the control block
> >     => witness program is 32 bytes, 16 possible leaf versions (one for each 
> > 4-tuple of 0xc0..0xff)
> > 4. Q sign is explictly set in the control block, P sign is implicitly even
> >     => witness program is 32 bytes, 32 possible leaf versions (one for pair 
> > of 0xc0..0xff)
> >
> > The current proposal uses (1). Using (3) or (4) would reduce the size of a
> > taproot output by one byte to be the same size as a P2WSH output. That means
> > that it's not more expensive for senders compared to sending to P2WSH.
> >  
> > (Credit to James Chiang for suggesting omitting the y sign from the public 
> > key and
> > to sipa for pointing out the 4 options above)
> >
> > > (native or P2SH-nested, see BIP141)
> >
> > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for 
> > segwit
> > v0 for compatibility reasons. Most wallets/exchanges/services now support 
> > sending
> > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and 
> > that
> > will be even more true if Schnorr/Taproot activate in 12+ months time.
> >
> > On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev 
> >  wrote:
> >
> > > Hello everyone,
> > >
> > > Here are two BIP drafts that specify a proposal for a Taproot
> > > softfork. A number of ideas are included:
> > >
> > > * Taproot to make all outputs and cooperative spends indistinguishable
> > > from eachother.
> > > * Merkle branches to hide the unexecuted branches in scripts.
> > > * Schnorr signatures enable wallet software to use key
> > > aggregation/thresholds within one input.
> > > * Improvements to the signature hashing algorithm (including signing
> > > all input amounts).
> > > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> > > batch validation.
> > > * Tagged hashing for domain separation (avoiding issues like
> > > CVE-2012-2459 in Merkle trees).
> > > * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> > > upgradable pubkey types.
> > >
> > > The BIP drafts can be found here:
> > > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> > > specifies the transaction input spending rules.
> > > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> > > specifies the changes to Script inside such spends.
> > > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> > > 

Re: [bitcoin-dev] Taproot proposal

[Greg Sanders via bitcoin-dev]

> I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for
segwit
v0 for compatibility reasons. Most wallets/exchanges/services now support
sending
to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and
that
will be even more true if Schnorr/Taproot activate in 12+ months time.

Apologies for necroing an ancient thread, but I'm echoing my agreement with
John here.
We still have plenty of time to have ecosystem upgrade by the time taproot
is likely to activate.



On Wed, May 22, 2019 at 10:30 AM John Newbery via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi,
>
> > A Taproot output is a SegWit output [...]  with
> > version number 1, and a 33-byte witness program whose first byte is 0 or
> 1.
>
> Given a secret key k and public key P=(x,y), a signer with the knowledge
> of k
> can sign for -P=(x,p-y) since -k is the secret key for that point.
> Encoding the
> y value of the public key therefore adds no security. As an alternative to
> providing the y value of the taproot output key Q when constructing the
> taproot
> output, the signer can provide it when signing. We can also restrict the y
> value
> of the internal key P to be even (or high, or a quadratic residue). That
> gives
> us 4 options for how to set the y signs for P and Q.
>
> 1. Q sign is explictly set in the witness program, P sign is explicitly
> set in the control block
> => witness program is 33 bytes, 32 possible leaf versions (one for
> each pair of 0xc0..0xff)
> 2. Q sign is explictly set in the witness program, P sign is implicitly
> even
> => witness program is 33 bytes, 64 possible leaf versions (one for
> each 0xc0..0xff)
> 3. Q sign is explictly set in the control block, P sign is explicitly set
> in the control block
> => witness program is 32 bytes, 16 possible leaf versions (one for
> each 4-tuple of 0xc0..0xff)
> 4. Q sign is explictly set in the control block, P sign is implicitly even
> => witness program is 32 bytes, 32 possible leaf versions (one for
> pair of 0xc0..0xff)
>
> The current proposal uses (1). Using (3) or (4) would reduce the size of a
> taproot output by one byte to be the same size as a P2WSH output. That
> means
> that it's not more expensive for senders compared to sending to P2WSH.
>
> (Credit to James Chiang for suggesting omitting the y sign from the public
> key and
> to sipa for pointing out the 4 options above)
>
> > (native or P2SH-nested, see BIP141)
>
> I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for
> segwit
> v0 for compatibility reasons. Most wallets/exchanges/services now support
> sending
> to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption)
> and that
> will be even more true if Schnorr/Taproot activate in 12+ months time.
>
> On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hello everyone,
>>
>> Here are two BIP drafts that specify a proposal for a Taproot
>> softfork. A number of ideas are included:
>>
>> * Taproot to make all outputs and cooperative spends indistinguishable
>> from eachother.
>> * Merkle branches to hide the unexecuted branches in scripts.
>> * Schnorr signatures enable wallet software to use key
>> aggregation/thresholds within one input.
>> * Improvements to the signature hashing algorithm (including signing
>> all input amounts).
>> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
>> batch validation.
>> * Tagged hashing for domain separation (avoiding issues like
>> CVE-2012-2459 in Merkle trees).
>> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
>> upgradable pubkey types.
>>
>> The BIP drafts can be found here:
>> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
>> specifies the transaction input spending rules.
>> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
>> specifies the changes to Script inside such spends.
>> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
>> is the Schnorr signature proposal that was discussed earlier on this
>> list (See
>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html
>> )
>>
>> An initial reference implementation of the consensus changes, plus
>> preliminary construction/signing tests in the Python framework can be
>> found on https://github.com/sipa/bitcoin/commits/taproot. All
>> together, excluding the Schnorr signature module in libsecp256k1, the
>> consensus changes are around 520 LoC.
>>
>> While many other ideas exist, not everything is incorporated. This
>> includes several ideas that can be implemented separately without loss
>> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
>> which we're working on as an independent proposal.
>>
>> The document explains basic wallet operations, such as constructing
>> outputs and signing. However, a wide variety of more complex
>> constructions exist. 

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

On Fri, 9 Aug 2019 at 08:02, Elichai Turkel via bitcoin-dev
 wrote:
>
> Hi,

Since the idea of implicitly even pubkeys has potentially more general
implications, I've started a separate thread [1] about that idea.

> I want to add to John Newbery's suggestion of using implicit even/odd only 
> public keys and tweaked public keys in taproot and suggest the following:
> If everything is implicit then the only reason for the first byte of the 
> control block(`c[0]`) is the tapscript leaf version.

That's unfortunately not correct. If we want to maintain
batch-verifiability of the taproot tweaking (the Q = P + H(P,m)G
relation), we still need a bit in the control block to convey whether
a negation was necessary to make P+H(P,m)G even, even if P and Q both
have implied-even Y coordinates. Not doing that would require
exploring 2^n combinations to batch verify n relations, obviously
destroying any performance savings the batch verification had in the
first place.

> I suggest that this is moved to be the first OP_CODE of the tapscript itself 
> (i.e. OP_0/OP_1 etc.)
> That way having the script *tells* you what does it mean without needing to 
> check the control block.
> That way there's a separation between the tapscript+leaf version and the 
> control block being the merkle path to the script.

If we keep the leaf version idea (it's possible to instead just rely
entirely on OP_SUCCESSx, and drop leaf versions), my preference is to
still keep it separate from script, though just for a fairly banal
reason: that way the script consists entirely of opcodes and can be
treated uniformly by debug tools, rather than needing to treat the
first byte special. I do understand your preference too, but I don't
know how it weighs up.

  [1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017247.html

Cheers,

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

Re: [bitcoin-dev] Taproot proposal

[Elichai Turkel via bitcoin-dev]

Hi,
I want to add to John Newbery's suggestion of using implicit even/odd only
public keys and tweaked public keys in taproot and suggest the following:

If everything is implicit then the only reason for the first byte of the
control block(`c[0]`) is the tapscript leaf version.
I suggest that this is moved to be the first OP_CODE of the tapscript
itself (i.e. OP_0/OP_1 etc.)
That way having the script *tells* you what does it mean without needing to
check the control block.
That way there's a separation between the tapscript+leaf version and the
control block being the merkle path to the script.
-- 
PGP: 5607C93B5F86650C
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot proposal

[Russell O'Connor via bitcoin-dev]

Hmm? If I'm following what you mean, that's not the P2P rules, it's the
> Unserialize code, in particular:
>
>   compat/assumptions.h:52:static_assert(sizeof(int) == 4, "32-bit int
> assumed");
>
>   serialize.h:289:uint64_t ReadCompactSize(Stream& is)
>
>   serialize.h-679-template typename V>
>   serialize.h-680-void Unserialize_impl(Stream& is, prevector& v,
> const V&)
>   serialize.h-681-{
>   serialize.h-682-v.clear();
>   serialize.h:683:unsigned int nSize = ReadCompactSize(is);
>
>   (and other Unserialize_impl implementations)
>
> However, ReadCompactSize throws "size too large" if the return value is
> greater than MAX_SIZE == 0x0200 =~ 33.5M, which prior to the implicit
> cast to 32 bits in Unserialize_impl. And it looks like that check's been
> there since Satoshi...
>
> So as far as I can see, that encoding's just unsupported/invalid, rather
> than equivalent/non-canonical?
>

Thanks for this correction!  I totally missed that MAX_SIZE == 0x0200.
I think I mistook it for SIZE_MAX when reviewing this, or just didn't
notice it at all.

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

Re: [bitcoin-dev] Taproot proposal

[Anthony Towns via bitcoin-dev]

On Wed, Jun 26, 2019 at 08:08:01PM -0400, Russell O'Connor via bitcoin-dev 
wrote:
> I have a comment about the 'input_index' of the transaction digest for taproot
> signatures.  It is currently listed as 2 bytes.  I think it would be better to
> expand that to 4 bytes.

FWIW, I think this would be essentially free, at least for the current
sighash modes, as (I think) all the non-ANYONECANPAY modes have at least
4 bytes of sha256 padding at present.

In addition to (or, perhaps, as a special case of) the reasons Russell
gives, I think this change would also better support proof-of-reserves
via taproot signatures (cf [0] or BIP 127), as it would allow the proof
tx to include more than 65k utxos with each utxo being signed with a
signature that commits to all inputs including the invalid placeholder.

[0] 
https://blockstream.com/2019/02/04/en-standardizing-bitcoin-proof-of-reserves/

If you didn't have this, but wanted to do proof-of-reserves over >65k
taproot UTXOs, you could use ANYONECANPAY signatures, and use the output
amounts to ensure the signatures can't be abused, something like:

   inputs:
 0: spend from txid .. vout 0, no witness data
 1: utxo1, signed with ANYONECANPAY|ALL
 2: utxo2, signed with ANYONECANPAY|ALL
 3: utxo3, signed with ANYONECANPAY|ALL
 [etc]

   outputs:
 0: sum(utxo1..utxoN), pay to self
 1: 209997690001-sum(utxo1..utxo3), payable to whatever

The total output value is therefore one satoshi more bitcoin than there
could ever have been, so none of the utxoK signatures can be reused on the
blockchain (unless there's severe inflation due to bugs or hardforks),
but the values (and sums) all remain less than 21M BTC so it also won't
fail the current "amount too big" sanity checks.

That seems a bit more fragile/complicated than using SIGHASH_ALL for
everything, though it means your cold wallet doesn't have to serialize
your >65k transactions to verify it's signing what it thinks it is.

> [1]The var-integer field for the number of inputs (and the number of outputs)
> in a transaction looks like it should allow upto 2^64-1 inputs; however this 
> is
> an illusion.  The P2P rules dictate that these values are immediately taken
> modulo 2^32 after decoding.  For example, if the number of inputs is a
> var-integer encoding of 0x010001, it is actually just a non-canonical way
> of encoding that there is 1 input.  Try this at home!

Hmm? If I'm following what you mean, that's not the P2P rules, it's the
Unserialize code, in particular:

  compat/assumptions.h:52:static_assert(sizeof(int) == 4, "32-bit int assumed");

  serialize.h:289:uint64_t ReadCompactSize(Stream& is)

  serialize.h-679-template
  serialize.h-680-void Unserialize_impl(Stream& is, prevector& v, const 
V&)
  serialize.h-681-{
  serialize.h-682-v.clear();
  serialize.h:683:unsigned int nSize = ReadCompactSize(is);

  (and other Unserialize_impl implementations)

However, ReadCompactSize throws "size too large" if the return value is
greater than MAX_SIZE == 0x0200 =~ 33.5M, which prior to the implicit
cast to 32 bits in Unserialize_impl. And it looks like that check's been
there since Satoshi...

So as far as I can see, that encoding's just unsupported/invalid, rather
than equivalent/non-canonical?

Cheers,
aj

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

Re: [bitcoin-dev] Taproot proposal

[Russell O'Connor via bitcoin-dev]

I have a comment about the 'input_index' of the transaction digest for
taproot signatures.  It is currently listed as 2 bytes.  I think it would
be better to expand that to 4 bytes.
The two byte limit is derived from the block size / weight limit, which
limits the maximum size of a transaction, which in turn, due to a minimum
size of an inputs, places a limit on the maximum number of inputs.

However, I think it is a mistake to mix limits from the block layer into
the transaction layer of the consensus rules.  For example, I believe that,
as it stands currently, if we wanted to hardfork an increase in the block
weight limit, doing so wouldn't have any impact on the transaction layer
and we could transparently manage larger transactions with the current
transaction format [2].  However if we start incorporating the block limits
into the transaction layer, then we run the risk of such a hard fork
needing to also make consensus changes in the transaction
format/interpretation if we wanted to handle larger transaction sizes,
which, while doable, wouldn't be so great.

The current transaction format limits the number of inputs (and the number
of outputs) to 2^32-1 or less [1].  So using 4 bytes for the 'input_index'
will suffice.

Given that adding 2 bytes to the signed transaction digest isn't a big
deal, it's probably better just to keep block limits and transaction limits
separate.

[1]The var-integer field for the number of inputs (and the number of
outputs) in a transaction looks like it should allow upto 2^64-1 inputs;
however this is an illusion.  The P2P rules dictate that these values are
immediately taken modulo 2^32 after decoding.  For example, if the number
of inputs is a var-integer encoding of 0x010001, it is actually just a
non-canonical way of encoding that there is 1 input.  Try this at home!

[2]If we were to hardfork an increase in the block weight limit, we would
probably want to still keep the limit on the size of transactions that
consume legacy UTXOs in order to avoid the quadratic computation problems
that plagues the legacy transaction digest.

On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here are two BIP drafts that specify a proposal for a Taproot
> softfork. A number of ideas are included:
>
> * Taproot to make all outputs and cooperative spends indistinguishable
> from eachother.
> * Merkle branches to hide the unexecuted branches in scripts.
> * Schnorr signatures enable wallet software to use key
> aggregation/thresholds within one input.
> * Improvements to the signature hashing algorithm (including signing
> all input amounts).
> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> batch validation.
> * Tagged hashing for domain separation (avoiding issues like
> CVE-2012-2459 in Merkle trees).
> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> upgradable pubkey types.
>
> The BIP drafts can be found here:
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> specifies the transaction input spending rules.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> specifies the changes to Script inside such spends.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> is the Schnorr signature proposal that was discussed earlier on this
> list (See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html
> )
>
> An initial reference implementation of the consensus changes, plus
> preliminary construction/signing tests in the Python framework can be
> found on https://github.com/sipa/bitcoin/commits/taproot. All
> together, excluding the Schnorr signature module in libsecp256k1, the
> consensus changes are around 520 LoC.
>
> While many other ideas exist, not everything is incorporated. This
> includes several ideas that can be implemented separately without loss
> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
> which we're working on as an independent proposal.
>
> The document explains basic wallet operations, such as constructing
> outputs and signing. However, a wide variety of more complex
> constructions exist. Standardizing these is useful, but out of scope
> for now. It is likely also desirable to define extensions to PSBT
> (BIP174) for interacting with Taproot. That too is not included here.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] Taproot proposal

[Russell O'Connor via bitcoin-dev]

On Wed, May 22, 2019 at 10:06 PM Pieter Wuille 
wrote:

> On Tue, 21 May 2019 at 10:20, Russell O'Connor 
> wrote:
> >
> > Regarding Tapscript, the specification calls for the final value of the
> stack being a single non-false value:
> >
> >> The tapscript is executed according to the rules in the following
> section, with the initial stack as input
> >> II. If the execution results in anything but exactly one element on
> the stack which evaluates to true with CastToBool(), fail.
> >
> > Perhaps it is worth taking this opportunity here to remove a minor wart
> of the Script language and instead require the stack to be exactly empty
> upon completion.
> >
> > In addition to removing a potential malleability vector, I expect it
> would simplify development of Bitcoin Script.  A rule requiring an empty
> stack means that the conjunction (logical and) of two policies can be
> implemented by the simple concatenation of Bitcoin Scripts.  This combined
> with the taproot ability to form the disjunction (logical or) of policies
> by having multiple Merkle branches, means that the translation of a policy
> written in disjunctive normal form (the logical ors of logical ands of
> primitive policies) can be straightforwardly translated to a taproot of
> tapscript.
> >
> > That said, I think the developers of miniscript <
> http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better
> position to comment on whether my above intuition is correct given that
> they've had to implement a host of various calling conventions.  I
> understand that at least some of this complexity is due to Bitcoin Script's
> one element stack rule.
>
> IIRC I looked into this a few months ago, and found that the spending
> cost (script size + expected witness size) of the optimal script for
> every Miniscript policy at most changes by 1 WU (in either direction)
> by requiring an empty stack rather than a true value, though in a
> (admittedly very arbitrarily biased) distribution, more policies were
> improved by it than degraded. This is not taking Taproot into account
> (as many of those policies in a Taproot-supporting world should
> optimally make use of the internal key and Merkle tree, rather than
> turning everything into a monolithic script). I expect that this may
> make the impact somewhat larger, but still never more than a 1 WU
> gain.
>
> I don't think the spending cost changes justify this change, so the
> remaining criteria are complexity ones. In my view, the main benefit
> would be to authors of hand-written scripts where the consistency
> benefits matter, but this needs to be weighed against the mental cost
> of learning the new semantics. For Miniscript itself, this doesn't
> make much difference - the top level calling convention would become
> 'V' instead of 'T', but 'T' would still exist as a calling convention
> that may be used internally; it's a few lines change.
>
> So overall this feels like something with marginal costs, but also at
> most marginal benefits. Perhaps other people have stronger opinions.
>

Thanks for the info.  I'm surprised to learn that 'T' would still exist
internally.  That does make my proposed ammendment a somewhat more marginal
than I expected.  I still think it would be an improvement, but I guess it
is acceptable the way it is if that is what other people prefer.


> > Even if we choose not to implement the empty stack rule, we should at
> least require that the last element be 0x01 to remove a potential
> malleability vector and bring it in line with MINIMAL_IF semantics.
>
> This feels like the right thing to do; as we're making MINIMALIF part
> of consensus for Tapscript it would make sense to apply the same rule
> to the "return" value of the script. There is a downside though,
> namely that in some places where you'd use "
> OP_CHECKSEQUENCEVERIFY" or " OP_CHECKLOCKTIMEVERIFY" you now need
> to add an additional OP_0NOTEQUAL to convert the left-over element n
> into an exact 0x01. I also can't come up with any practical benefits
> that this would have; if the top stack element in a particular code
> path comes directly from the input, it's insecure regardless; if there
> isn't, it'll generally be a a boolean (or an intentional non-boolean
> true value) computed by the script.
>

That is a very good argument.  If we were to go with an empty stack we'd
probably also want modify to have CSV and CLTV pop their inputs off the
stack.  But at that point perhaps we'd want to change their opcode values
to avoid confusion with old style script.  I guess I'm getting more
convinced to not touch this stuff just and just bear with the somewhat
unfortunate legacy behaviour.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

On Tue, 21 May 2019 at 10:20, Russell O'Connor  wrote:
>
> Regarding Tapscript, the specification calls for the final value of the stack 
> being a single non-false value:
>
>> The tapscript is executed according to the rules in the following section, 
>> with the initial stack as input
>> II. If the execution results in anything but exactly one element on the 
>> stack which evaluates to true with CastToBool(), fail.
>
> Perhaps it is worth taking this opportunity here to remove a minor wart of 
> the Script language and instead require the stack to be exactly empty upon 
> completion.
>
> In addition to removing a potential malleability vector, I expect it would 
> simplify development of Bitcoin Script.  A rule requiring an empty stack 
> means that the conjunction (logical and) of two policies can be implemented 
> by the simple concatenation of Bitcoin Scripts.  This combined with the 
> taproot ability to form the disjunction (logical or) of policies by having 
> multiple Merkle branches, means that the translation of a policy written in 
> disjunctive normal form (the logical ors of logical ands of primitive 
> policies) can be straightforwardly translated to a taproot of tapscript.
>
> That said, I think the developers of miniscript 
>  are in a much better 
> position to comment on whether my above intuition is correct given that 
> they've had to implement a host of various calling conventions.  I understand 
> that at least some of this complexity is due to Bitcoin Script's one element 
> stack rule.

IIRC I looked into this a few months ago, and found that the spending
cost (script size + expected witness size) of the optimal script for
every Miniscript policy at most changes by 1 WU (in either direction)
by requiring an empty stack rather than a true value, though in a
(admittedly very arbitrarily biased) distribution, more policies were
improved by it than degraded. This is not taking Taproot into account
(as many of those policies in a Taproot-supporting world should
optimally make use of the internal key and Merkle tree, rather than
turning everything into a monolithic script). I expect that this may
make the impact somewhat larger, but still never more than a 1 WU
gain.

I don't think the spending cost changes justify this change, so the
remaining criteria are complexity ones. In my view, the main benefit
would be to authors of hand-written scripts where the consistency
benefits matter, but this needs to be weighed against the mental cost
of learning the new semantics. For Miniscript itself, this doesn't
make much difference - the top level calling convention would become
'V' instead of 'T', but 'T' would still exist as a calling convention
that may be used internally; it's a few lines change.

So overall this feels like something with marginal costs, but also at
most marginal benefits. Perhaps other people have stronger opinions.

> Even if we choose not to implement the empty stack rule, we should at least 
> require that the last element be 0x01 to remove a potential malleability 
> vector and bring it in line with MINIMAL_IF semantics.

This feels like the right thing to do; as we're making MINIMALIF part
of consensus for Tapscript it would make sense to apply the same rule
to the "return" value of the script. There is a downside though,
namely that in some places where you'd use "
OP_CHECKSEQUENCEVERIFY" or " OP_CHECKLOCKTIMEVERIFY" you now need
to add an additional OP_0NOTEQUAL to convert the left-over element n
into an exact 0x01. I also can't come up with any practical benefits
that this would have; if the top stack element in a particular code
path comes directly from the input, it's insecure regardless; if there
isn't, it'll generally be a a boolean (or an intentional non-boolean
true value) computed by the script.

On Tue, 21 May 2019 at 13:05, John Newbery  wrote:
>
> Hi,
>
> > A Taproot output is a SegWit output [...]  with
> > version number 1, and a 33-byte witness program whose first byte is 0 or 1.
>
> Given a secret key k and public key P=(x,y), a signer with the knowledge of k
> can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding 
> the
> y value of the public key therefore adds no security.

That's a good point; without security benefit there's no reason to
make pay-to-taproots more expensive. Making them the same cost as
P2WSH is nice in any case.

> As an alternative to
> providing the y value of the taproot output key Q when constructing the 
> taproot
> output, the signer can provide it when signing. We can also restrict the y 
> value
> of the internal key P to be even (or high, or a quadratic residue). That gives
> us 4 options for how to set the y signs for P and Q.
>
> 1. Q sign is explictly set in the witness program, P sign is explicitly set 
> in the control block
> => witness program is 33 bytes, 32 possible leaf versions (one for each 
> pair of 0xc0..0xff)
> 2. Q sign is 

Re: [bitcoin-dev] Taproot proposal

[John Newbery via bitcoin-dev]

Hi,

> A Taproot output is a SegWit output [...]  with
> version number 1, and a 33-byte witness program whose first byte is 0 or
1.

Given a secret key k and public key P=(x,y), a signer with the knowledge of
k
can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding
the
y value of the public key therefore adds no security. As an alternative to
providing the y value of the taproot output key Q when constructing the
taproot
output, the signer can provide it when signing. We can also restrict the y
value
of the internal key P to be even (or high, or a quadratic residue). That
gives
us 4 options for how to set the y signs for P and Q.

1. Q sign is explictly set in the witness program, P sign is explicitly set
in the control block
=> witness program is 33 bytes, 32 possible leaf versions (one for each
pair of 0xc0..0xff)
2. Q sign is explictly set in the witness program, P sign is implicitly even
=> witness program is 33 bytes, 64 possible leaf versions (one for each
0xc0..0xff)
3. Q sign is explictly set in the control block, P sign is explicitly set
in the control block
=> witness program is 32 bytes, 16 possible leaf versions (one for each
4-tuple of 0xc0..0xff)
4. Q sign is explictly set in the control block, P sign is implicitly even
=> witness program is 32 bytes, 32 possible leaf versions (one for pair
of 0xc0..0xff)

The current proposal uses (1). Using (3) or (4) would reduce the size of a
taproot output by one byte to be the same size as a P2WSH output. That means
that it's not more expensive for senders compared to sending to P2WSH.

(Credit to James Chiang for suggesting omitting the y sign from the public
key and
to sipa for pointing out the 4 options above)

> (native or P2SH-nested, see BIP141)

I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for
segwit
v0 for compatibility reasons. Most wallets/exchanges/services now support
sending
to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and
that
will be even more true if Schnorr/Taproot activate in 12+ months time.

On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here are two BIP drafts that specify a proposal for a Taproot
> softfork. A number of ideas are included:
>
> * Taproot to make all outputs and cooperative spends indistinguishable
> from eachother.
> * Merkle branches to hide the unexecuted branches in scripts.
> * Schnorr signatures enable wallet software to use key
> aggregation/thresholds within one input.
> * Improvements to the signature hashing algorithm (including signing
> all input amounts).
> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> batch validation.
> * Tagged hashing for domain separation (avoiding issues like
> CVE-2012-2459 in Merkle trees).
> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> upgradable pubkey types.
>
> The BIP drafts can be found here:
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> specifies the transaction input spending rules.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> specifies the changes to Script inside such spends.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> is the Schnorr signature proposal that was discussed earlier on this
> list (See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html
> )
>
> An initial reference implementation of the consensus changes, plus
> preliminary construction/signing tests in the Python framework can be
> found on https://github.com/sipa/bitcoin/commits/taproot. All
> together, excluding the Schnorr signature module in libsecp256k1, the
> consensus changes are around 520 LoC.
>
> While many other ideas exist, not everything is incorporated. This
> includes several ideas that can be implemented separately without loss
> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
> which we're working on as an independent proposal.
>
> The document explains basic wallet operations, such as constructing
> outputs and signing. However, a wide variety of more complex
> constructions exist. Standardizing these is useful, but out of scope
> for now. It is likely also desirable to define extensions to PSBT
> (BIP174) for interacting with Taproot. That too is not included here.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] Taproot proposal

[Russell O'Connor via bitcoin-dev]

Regarding Tapscript, the specification calls for the final value of the
stack being a single non-false value:

The tapscript is executed according to the rules in the following section,
> with the initial stack as input
> II. If the execution results in anything but exactly one element on
> the stack which evaluates to true with CastToBool(), fail.
>

Perhaps it is worth taking this opportunity here to remove a minor wart of
the Script language and instead require the stack to be exactly empty upon
completion.

In addition to removing a potential malleability vector, I expect it would
simplify development of Bitcoin Script.  A rule requiring an empty stack
means that the conjunction (logical and) of two policies can be implemented
by the simple concatenation of Bitcoin Scripts.  This combined with the
taproot ability to form the disjunction (logical or) of policies by having
multiple Merkle branches, means that the translation of a policy written in
disjunctive normal form (the logical ors of logical ands of primitive
policies) can be straightforwardly translated to a taproot of tapscript.

That said, I think the developers of miniscript <
http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better
position to comment on whether my above intuition is correct given that
they've had to implement a host of various calling conventions.  I
understand that at least some of this complexity is due to Bitcoin Script's
one element stack rule.

Scripts under the old one element rule can be translated to the new rule by
adding an OP_VERIFY operation to the end of the script; however it is
likely that this OP_VERIFY can be folded into the previous operation
yielding an OP_EQUALVERIFY or OP_CHECKSIGVERIFY in many cases.

Even if we choose not to implement the empty stack rule, we should at least
require that the last element be 0x01 to remove a potential malleability
vector and bring it in line with MINIMAL_IF semantics.

Thanks.

On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello everyone,
>
> Here are two BIP drafts that specify a proposal for a Taproot
> softfork. A number of ideas are included:
>
> * Taproot to make all outputs and cooperative spends indistinguishable
> from eachother.
> * Merkle branches to hide the unexecuted branches in scripts.
> * Schnorr signatures enable wallet software to use key
> aggregation/thresholds within one input.
> * Improvements to the signature hashing algorithm (including signing
> all input amounts).
> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> batch validation.
> * Tagged hashing for domain separation (avoiding issues like
> CVE-2012-2459 in Merkle trees).
> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> upgradable pubkey types.
>
> The BIP drafts can be found here:
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> specifies the transaction input spending rules.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> specifies the changes to Script inside such spends.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> is the Schnorr signature proposal that was discussed earlier on this
> list (See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html
> )
>
> An initial reference implementation of the consensus changes, plus
> preliminary construction/signing tests in the Python framework can be
> found on https://github.com/sipa/bitcoin/commits/taproot. All
> together, excluding the Schnorr signature module in libsecp256k1, the
> consensus changes are around 520 LoC.
>
> While many other ideas exist, not everything is incorporated. This
> includes several ideas that can be implemented separately without loss
> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
> which we're working on as an independent proposal.
>
> The document explains basic wallet operations, such as constructing
> outputs and signing. However, a wide variety of more complex
> constructions exist. Standardizing these is useful, but out of scope
> for now. It is likely also desirable to define extensions to PSBT
> (BIP174) for interacting with Taproot. That too is not included here.
>
> Cheers,
>
> --
> Pieter
> ___
> 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] Taproot proposal

[ZmnSCPxj via bitcoin-dev]

Good morning list,


> > Can this "unknown discrete logarithm" be made provably unknown, so all 
> > signers are assured of this property? Bonus points if the outside world 
> > can't tell. The exact mechanism could be outside the scope of the BIP, but 
> > knowing that it's possible is useful.
>
> Yes, that's a TODO that's left in the draft, but this is absolutely
> possible (using a hash-to-curve operation). As ZmnSCPxj already
> suggested, there can even be a fixed known constant you can use for
> this. However, you get better privacy by taking this fixed known
> constant (call it C) and using as internal key a blinded version of it
> (C+rG, for some random value r, and G the normal secp256k1 generator);
> as long as the DL between G and C is unknown, this is safe (and does
> not reveal to the world that in fact no key-path was permitted when
> spending).

Gregory Maxwell commented some days ago:

> 2019-05-11T23:35:02   sipa: also someone might want to point out to 
> ZmnSCPxj  that his scheme for getting a NUMS point is insecure (it must also 
> commit to G because we don't know how G was generated)

I am assuming that gmax is referring to my description of the "hash-to-point" 
or "hash-to-curve" operation.

A little more research shows this: https://crypto.stackexchange.com/a/25603

>From the above, it seems the method that real cryptographers use is:

1.  Generate some random data d.
2.  Get x = h(G | d) where G is the existing generator for secp256k1.
3.  Find a point on secp256k1 with X coordinate x.
4.  If not found, go to 1.

In any case, I am almost sure that for every case where the "everyone agrees" 
path is unwanted in a taproot address, the simple "put your own pubkey lock on 
the door and throw away the privkey" technique would work without requiring a 
NUMS point: the same taproot assumption should also work here.
But generation of a NUMS point might be of independent interest in any case 
(e.g. setting up Pedersen commitments).

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

Re: [bitcoin-dev] Taproot proposal

[ZmnSCPxj via bitcoin-dev]

Good morning Johnson,


> > > Some way to sign an additional script (not committed to by the witness
> > > program) seems like it could be a trivial addition.
> >
> > It seems to me the annex can be used for this, by having it contain both 
> > the script and the signature somehow concatenated.
>
> This is not possible since the whole annex is signed. It is possible if the 
> signed “script” does not require further input, like per-input lock-time, 
> relative lock-time, check block hash

I understand, you are correct.

Possibly the correct way would be to use another leaf version.
The "script" of such a new leaf version would not actually be a script, but a 
delegation key.
Then for this leaf version the actual script and signature from the delegation 
key attesting that script would be on top of the witness stack that will be 
used by the actual script.
This has the nice property that the existence of a delegation key is hidden 
from the output, and that if an alternate script is in the MAST (as an 
alternative to the delegation), use of that alternate script does not reveal 
that delegation could have been possible.

Regards,
ZmnSCPxj


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

Re: [bitcoin-dev] Taproot proposal

[Johnson Lau via bitcoin-dev]

> 
>> 
>> Some way to sign an additional script (not committed to by the witness
>> program) seems like it could be a trivial addition.
> 
> It seems to me the annex can be used for this, by having it contain both the 
> script and the signature somehow concatenated.

This is not possible since the whole annex is signed. It is possible if the 
signed “script” does not require further input, like per-input lock-time, 
relative lock-time, check block hash


> 
> Regards,
> ZmnSCPxj
> ___
> 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] Taproot proposal

[Luke Dashjr via bitcoin-dev]

On Monday 06 May 2019 20:17:09 Luke Dashjr via bitcoin-dev wrote:
> Some way to sign an additional script (not committed to by the witness
> program) seems like it could be a trivial addition.

This would be especially useful for things like OP_CHECKBLOCKATHEIGHT:

https://github.com/bitcoin/bips/blob/master/bip-0115.mediawiki
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot proposal

[ZmnSCPxj via bitcoin-dev]

Good morning Sjors, sorry everyone for the double-posting...

> I believe this is the "hash to a point" technique.
>
> The scalar behind the above point cannot be known, unless either the hash 
> function is broken, or ECDLP is broken.
> (perhaps a better cryptographer can give the proper qualifications, any 
> corrections, and etc etc)
>
> As the point is just an arbitrary point on the curve, it is unknown to the 
> rest of the world whether somebody knows the scalar, or nobody knows.

Now that I think further, everyone can use *the same* point generated from an 
arbitrary "hash to a point".
For example, we can define the "script-only point" as the point whose X 
coordinate (or is it Y...) is equal to SHA256("Pieter Wuille is really great!").
Add more "really " until we get a point on the curve.

Provided everyone knows what the exact data to hash is, and the exact hash 
function, the above procedure is sufficient for everybody to verify that Pieter 
Wuille (and anyone else for that matter) cannot, in fact, spend the coin 
unilaterally, and that nobody can actually spend the coin, except via a script.

Since the point on the output is tweaked by the script merkle tree root, 
varying your pubkey for each use will be enough to blind the use of the 
"script-only point" until you have to reveal it during spending anyway.
If you *absolutely* insist on reusing your pubkeys, then adding a 
`OP_PUSH() OP_DROP` to at least one script, with a random salt, should be 
enough to blind the use of the script-only point until you have to reveal the 
script you want to use.
Or even just further tweak the point before using it as the taproot internal 
pubkey, so that not even a coin spend reveals that the "everyone agrees" branch 
was never actually an option.

> Or just use pubkeys given by both participants, that should be enough to 
> ensure the "everyone agrees" branch is never taken if we write our software 
> such that we never agree to sign with it (i.e. just get points from both 
> sides and MuSig them; then each side can just erase the scalar generating it 
> from memory and whatever caches exist on the system; a node might even just 
> generate a single random point from a scalar it subsequently erases, and just 
> use some non-hardened derivation path from that for every HTLC it has to 
> make).
> This technique is "sufficiently provably unknown" since each participant 
> knows that it deliberately erased the only means of knowing the complete 
> discrete log by erasing its share.
> In short, "everyone agrees" is trivially easy to make "nobody can agree" by a 
> single participant never agreeing to let itself be ripped off.
>

The "taproot assumption" is that there exists some finite set of participants 
that is interested in how the coin will be spent.
Under the taproot assumption then, any "truster" that assigns time-limited 
control of a coin to a "trustee" is part of that finite set interested in the 
coin spend conditions.
So the truster should in fact be asked for a pubkey to be added in the taproot 
internal pubkey that enables the "everyone agrees" branch.
Then the truster can simply generate a point without knowing its private key, 
or by forgetting this private key.

If one is sufficiently schizophrenic, one can split oneself into a "truster" 
and "trustee" as above and deliberately forget the truster private key.
Then one is sufficiently unable to spend under duress by deleting the "truster" 
sub-agent and providing real-world access to the "trustee" sub-agent that can 
only spend under specific SCRIPT-defined conditions.

(the above paragraph should not be taken to mean that I am an agent-based AI)

That is, it should be enough for everyone to agree to lock the "everyone 
agrees" branch and throw away their own key, to keep that branch locked.

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

Re: [bitcoin-dev] Taproot proposal

[ZmnSCPxj via bitcoin-dev]

Good morning Sjors,


Sent with ProtonMail Secure Email.

‐‐‐ Original Message ‐‐‐
On Wednesday, May 8, 2019 4:42 AM, Sjors Provoost via bitcoin-dev 
 wrote:

> Hey Pieter,
>
> I think this is a reasonable collection of changes that make sense in 
> combination. Some initial feedback and questions.
>
> From the BIP:
>
> > If one or more of the spending conditions consist of just a single key 
> > (after aggregation),
> > he most likely one should be made the internal key. If no such condition 
> > exists, it may
> > be worthwhile adding one that consists of an aggregation of all keys 
> > participating in all
> > scripts combined; effectively adding an "everyone agrees" branch. If that 
> > is inacceptable,
> > pick as internal key a point with unknown discrete logarithm (TODO).
>
> I assume Luke Dashjr referred to the above when saying:
>
> > Is there any way to use the Taproot construct here while retaining external
> > script limitations that the involved party(ies) cannot agree to override?
> > For example, it is conceivable that one might wish to have an unconditional
> > CLTV enforced in all circumstances.
>
> One reason why someone would want to avoid a "everone agrees" branch, is 
> duress (or self-discipline, or limiting powers of a trustee). In particular 
> with respect to time-locks.
>
> Can this "unknown discrete logarithm" be made provably unknown, so all 
> signers are assured of this property? Bonus points if the outside world can't 
> tell. The exact mechanism could be outside the scope of the BIP, but knowing 
> that it's possible is useful.

As I understand it, it is possible to take some random data, hash it with 
SHA256 and acquire a 256-bit number.
Then treat that number as an X coordinate (or is it Y...), and see if there 
exists a point on the secp256k1 curve at that coordinate.
If not, try another random data, or just hash the same number again.
As I understand it, about half the possible X coordinates will have a point on 
the curve.

I believe this is the "hash to a point" technique.

The scalar behind the above point cannot be known, unless either the hash 
function is broken, or ECDLP is broken.
(perhaps a better cryptographer can give the proper qualifications, any 
corrections, and etc etc)

As the point is just an arbitrary point on the curve, it is unknown to the rest 
of the world whether somebody knows the scalar, or nobody knows.

>
> Perhaps Lightning devs have an opinion on "everyone agrees" with respect to 
> hash pre-images. I suspect there is no benefit in guaranteeing that a 
> pre-image must be revealed or a timeout must be waited for and there's no way 
> around that condition.

The "everyone agrees" branch in Lightning is basically the "cooperative close" 
of the channel.
So it is not likely we will need an "everyone agrees" branch in the actual 
HTLCs we transfer *within* the channel.
So if we need to use hashes still, we will likely use the "hash to a point" 
technique above.

Or just use pubkeys given by both participants, that should be enough to ensure 
the "everyone agrees" branch is never taken if we write our software such that 
we never agree to sign with it (i.e. just get points from both sides and MuSig 
them; then each side can just erase the scalar generating it from memory and 
whatever caches exist on the system; a node might even just generate a single 
random point from a scalar it subsequently erases, and just use some 
non-hardened derivation path from that for every HTLC it has to make).
This technique is "sufficiently provably unknown" since each participant knows 
that it deliberately erased the only means of knowing the complete discrete log 
by erasing its share.
In short, "everyone agrees" is trivially easy to make "nobody can agree" by a 
single participant never agreeing to let itself be ripped off.

Do note that it is likely Lightning will eventually switch to using payment 
points/scalars instead of hashes/preimages.
This will allow us to have path decorrelation, both within a route, and in 
multiple routes of the same payment.
This is enabled by Schnorr, as this requires Scriptless Script.
(granted 2p-ECDSA also enables Scriptless Script, but we decided to wait for 
Schnorr to hit base layer instead)
This means we would be using the "everyone agrees" path only, with everyone 
agreeing to first create a `nLockTime` backout tx, then everyone agreeing to 
create a transaction where one side has knowledge of a secret scalar that is 
learned by the other side upon completion of the signature.

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

Re: [bitcoin-dev] Taproot proposal

[ZmnSCPxj via bitcoin-dev]

Good morning Luke,


> Is there any way to use the Taproot construct here while retaining external
> script limitations that the involved party(ies) cannot agree to override?
> For example, it is conceivable that one might wish to have an unconditional
> CLTV enforced in all circumstances.

Perhaps this can be enforced offchain, by participants refusing to sign a 
transaction unless it has an `nLockTime` of the agreed-upon "unconditional 
CLTV".
Then the CLTV need only be on branches which have a strict subset of the 
participants as signers.

>
> It may be useful to have a way to add a salt to tap branches.

Would not adding `OP_PUSH() OP_DROP` to the leaves work?
If you enforce always salting with a 32-byte salt, that "only" saves 3 bytes of 
witness data (for the `OP_PUSHDATA1+size` and `OP_DROP` opcodes).
Or do you refer to always salting every node?
(I am uncertain, but would not adding a salt to every leaf be sufficient?)

(in any case, if you use different pubkeys for each contract, rather than 
reusing keys, is that not enough randomization to prevent creating rainbow 
tables of scripts?)

>
> Some way to sign an additional script (not committed to by the witness
> program) seems like it could be a trivial addition.

It seems to me the annex can be used for this, by having it contain both the 
script and the signature somehow concatenated.

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

Re: [bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

Thanks for the comments so far!

I'm going to respond to some of the comments here. Things which I plan
to address with changes in the BIP I'll leave for later.

On Mon, 6 May 2019 at 13:17, Luke Dashjr  wrote:
> Tagged hashes put the tagging at the start of the hash input. This means
> implementations can pre-cache SHA2 states, but it also means they can't reuse
> states to produce data for different contexts. (I'm not sure if there is a
> use for doing so... but maybe as part of further hiding MAST branches?)

It's true you can't cache/precompute things across tags, but I also
think there is no need. The type of data hashed in a sighash vs a
merkle branch/leaf vs a tweak is fundamentally different. I think this
is perhaps a good guidance to include about when separate tags are
warranted vs. simply making sure the input does not collide: there
shouldn't be much or any shared data with things that are expected to
be inputs under other tags.

> Is there any way to use the Taproot construct here while retaining external
> script limitations that the involved party(ies) *cannot* agree to override?
> For example, it is conceivable that one might wish to have an unconditional
> CLTV enforced in all circumstances.

Yes, absolutely - you can use a point with unknown discrete logarithm
as internal key. This will result in only script path spends being
available. For the specific goal you're stating an alternative may be
using a valid known private key, using it to pre-sign a timelocked
transaction, and destroying the key.

> It may be useful to have a way to add a salt to tap branches.

If you don't reuse public keys, effectively every branch is
automatically salted (and the position in the tree gets randomized
automatically when doing so, providing a small additional privacy
benefit).

>> Some way to sign an additional script (not committed to by the witness
>> program) seems like it could be a trivial addition.
> This would be especially useful for things like OP_CHECKBLOCKATHEIGHT:
> https://github.com/bitcoin/bips/blob/master/bip-0115.mediawiki

If you're talking about the ability to sign over the ability to spend
to another script ("delegation"), there are lots of interesting
applications and ways to implement it. But it overlaps with Graftroot,
and doing it efficiently in general has some interesting and
non-obvious engineering challenges (for example, signing over to a
script that enforces "f(tx)=y" for some f can be done by only storing
f and then including y in the sighash).

For the specific example of BIP115's functionality, that seems like a
reasonable thing that could be dealt with using the annex construction
in the proposed BIP. A consensus rule could define a region inside the
annex that functions as a height-blockhash assertion. The annex is
included in all sighashes, so it can't be removed from the input;
later opcodes could include the ability to inspect that assertion
even.

On Tue, 7 May 2019 at 13:43, Sjors Provoost  wrote:
> One reason why someone would want to avoid a "everone agrees" branch, is 
> duress (or self-discipline, or limiting powers of a trustee). In particular 
> with respect to time-locks.>

Indeed, though as I suggested above, you can also use timelocked
transactions (but using only CLTV branches is more flexible
certainly).

> Can this "unknown discrete logarithm" be made provably unknown, so all 
> signers are assured of this property? Bonus points if the outside world can't 
> tell. The exact mechanism could be outside the scope of the BIP, but knowing 
> that it's possible is useful.

Yes, that's a TODO that's left in the draft, but this is absolutely
possible (using a hash-to-curve operation). As ZmnSCPxj already
suggested, there can even be a fixed known constant you can use for
this. However, you get better privacy by taking this fixed known
constant (call it C) and using as internal key a blinded version of it
(C+rG, for some random value r, and G the normal secp256k1 generator);
as long as the DL between G and C is unknown, this is safe (and does
not reveal to the world that in fact no key-path was permitted when
spending).

> Regarding usage of Schnorr: do I understand correctly that the "everyone 
> agrees" internal key MUST use Schnorr, and that individual branches MAY use 
> Schnorr, but only if they're marked as tapscript spend?
>
> Why is tapscript not mandatory?

Spending using the internal key always uses a single Schnorr signature
and nothing else. When you spend using a script path, you must reveal
both the script and its leaf version. If that leaf version is 0xc0,
the script is interpreted as a tapscript (in which only Schnorr
opcodes exist). If that leaf version is not 0xc0, the script is
undefined, and is unconditionally valid. This is one of the included
extension mechanisms, allowing replacing the whole script language
with something else, but without revealing it unless a branch using it
is actually used (different Merkle tree leaves can have a 

Re: [bitcoin-dev] Taproot proposal

[Anthony Towns via bitcoin-dev]

On Mon, May 06, 2019 at 08:17:09PM +, Luke Dashjr via bitcoin-dev wrote:
> Some way to sign an additional script (not committed to by the witness 
> program) seems like it could be a trivial addition.

Aside: if you want to commit to something extra *with* the witness
program, you could use either an unsolvable tapleaf branch (eg, one
that uses OP_RETURN and also pushes the data you want to commit to),
or a p2c construction like:

  Taproot: Q = P + H_TapTweak(P || S)*G

  P2C: P = R + H_"myp2c"(R || Contract)*G

If you don't have any scripts for S, you could set S=["OP_RETURN"]
to ensure there are no scripts. Having either the TapTweak formula or
the H_myp2c hash should be enough to ensure that your contract can't
get maliciously reinterpreted as a valid tapscript, having both is just
belts and suspenders.

But to address your question: if you want to commit to something extra
at spending/signing time rather than when creating the address, then
that's what the annex should be useful for. eg as a simple example,
your annex might be:

0x50 [flag]
0x25 [entry size]
  0x77 [annex entry id]
  0x0008c618 [block height == 575000]
  0x0007df59824a0c86d1cc21b90eb25259dd2dba5170cea5f5
 [block hash for block at 575000]

which would allow you to commit to a particular block hash, and there
could be a soft fork that added the restriction that such a commitment
invalidates the transaction if the block at the given height doesn't
match the provided hash.

You still need to the soft-fork to do the enforcing, but once you have
that, *every* existing taproot address automatically gets "upgraded"
to allow you to make the commitment, including via key path spends,
which seems pretty nice.

(That construction (ie size,id,data) lets you have multiple entries in
the annex reasonably efficiently)

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

Re: [bitcoin-dev] Taproot proposal

[Sjors Provoost via bitcoin-dev]

Hey Pieter,

I think this is a reasonable collection of changes that make sense in 
combination. Some initial feedback and questions.

>From the BIP:
> If one or more of the spending conditions consist of just a single key (after 
> aggregation),
> he most likely one should be made the internal key. If no such condition 
> exists, it may
> be worthwhile adding one that consists of an aggregation of all keys 
> participating in all
> scripts combined; effectively adding an "everyone agrees" branch. If that is 
> inacceptable,
> pick as internal key a point with unknown discrete logarithm (TODO).

I assume Luke Dashjr referred to the above when saying:

> Is there any way to use the Taproot construct here while retaining external 
> script limitations that the involved party(ies) *cannot* agree to override? 
> For example, it is conceivable that one might wish to have an unconditional 
> CLTV enforced in all circumstances.


One reason why someone would want to avoid a "everone agrees" branch, is duress 
(or self-discipline, or limiting powers of a trustee). In particular with 
respect to time-locks.

Can this "unknown discrete logarithm" be made provably unknown, so all signers 
are assured of this property? Bonus points if the outside world can't tell. The 
exact mechanism could be outside the scope of the BIP, but knowing that it's 
possible is useful.

Perhaps Lightning devs have an opinion on "everyone agrees" with respect to 
hash pre-images. I suspect there is no benefit in guaranteeing that a pre-image 
must be revealed or a timeout must be waited for and there's no way around that 
condition.


Regarding usage of Schnorr: do I understand correctly that the "everyone 
agrees" internal key MUST use Schnorr, and that individual branches MAY use 
Schnorr, but only if they're marked as tapscript spend?

Why is tapscript not mandatory?


Misc details:

In the Design section under "Merkle branches" I suggest adding bullet points 
with short descriptions of "various known mechanisms for implementing this". In 
addition to "space savings" maybe also briefly mention a few other pros and 
cons, like implementation complexity and privacy. And then point out which one 
you picked.

In the Design section, explicitly point out you're no longer using the hash of 
a public key (can move some explanation up from rationale section). This is a 
significant change, even if you have good reason to believe it's perfectly safe.

Regarding the 64 byte SHA256(tag) || SHA256(tag) 64-byte long context-specific 
constant: maybe add that sha-2 block size is 512 bits

"Conceptually every Taproot output corresponds to" -> some of this conceptual 
stuff belongs in or before the Specification section. Try briefly explaining 
how tagged hashes and script validation (stack) interact, before specifying 
them in detail. The figure (without the pseudo-code) can be helpful for that. 

In the figure with the merkle tree, the description says there's "3 script 
leaves.". So what's going on in leaf D? If it's a way to indicate an unused 
leaf, why is E different (or is also TapLeaf)? Maybe emphasize that "TapLeaf" 
tag is there so prove to all signers there's no secret conditions (the 
CVE-2012-2459 protection you refer to).

Sjors


> Op 6 mei 2019, om 22:17 heeft Luke Dashjr via bitcoin-dev 
>  het volgende geschreven:
> 
> There are multiple references to "space savings", but no rationale for 
> treating "space" as something to save or even define. The costs are in CPU 
> time and I/O (which "space saving" doesn't necessarily reduce) and bandwidth 
> (which can often be reduced without "space saving" in commitments). The 
> proposal can apparently be made simpler by ignoring this irrelevant "space 
> saving" goal.
> 
> Tagged hashes put the tagging at the start of the hash input. This means 
> implementations can pre-cache SHA2 states, but it also means they can't reuse 
> states to produce data for different contexts. (I'm not sure if there is a 
> use for doing so... but maybe as part of further hiding MAST branches?)
> 
> Is there any way to use the Taproot construct here while retaining external 
> script limitations that the involved party(ies) *cannot* agree to override? 
> For example, it is conceivable that one might wish to have an unconditional 
> CLTV enforced in all circumstances.
> 
> It may be useful to have a way to add a salt to tap branches.
> 
> Some way to sign an additional script (not committed to by the witness 
> program) seems like it could be a trivial addition.
> 
> 
> On Monday 06 May 2019 17:57:57 Pieter Wuille via bitcoin-dev wrote:
>> Hello everyone,
>> 
>> Here are two BIP drafts that specify a proposal for a Taproot
>> softfork. A number of ideas are included:
>> 
>> * Taproot to make all outputs and cooperative spends indistinguishable
>> from eachother.
>> * Merkle branches to hide the unexecuted branches in scripts.
>> * Schnorr signatures enable wallet software to use key
>> aggregation/thresholds 

Re: [bitcoin-dev] Taproot proposal

[Luke Dashjr via bitcoin-dev]

There are multiple references to "space savings", but no rationale for 
treating "space" as something to save or even define. The costs are in CPU 
time and I/O (which "space saving" doesn't necessarily reduce) and bandwidth 
(which can often be reduced without "space saving" in commitments). The 
proposal can apparently be made simpler by ignoring this irrelevant "space 
saving" goal.

Tagged hashes put the tagging at the start of the hash input. This means 
implementations can pre-cache SHA2 states, but it also means they can't reuse 
states to produce data for different contexts. (I'm not sure if there is a 
use for doing so... but maybe as part of further hiding MAST branches?)

Is there any way to use the Taproot construct here while retaining external 
script limitations that the involved party(ies) *cannot* agree to override? 
For example, it is conceivable that one might wish to have an unconditional 
CLTV enforced in all circumstances.

It may be useful to have a way to add a salt to tap branches.

Some way to sign an additional script (not committed to by the witness 
program) seems like it could be a trivial addition.


On Monday 06 May 2019 17:57:57 Pieter Wuille via bitcoin-dev wrote:
> Hello everyone,
>
> Here are two BIP drafts that specify a proposal for a Taproot
> softfork. A number of ideas are included:
>
> * Taproot to make all outputs and cooperative spends indistinguishable
> from eachother.
> * Merkle branches to hide the unexecuted branches in scripts.
> * Schnorr signatures enable wallet software to use key
> aggregation/thresholds within one input.
> * Improvements to the signature hashing algorithm (including signing
> all input amounts).
> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
> batch validation.
> * Tagged hashing for domain separation (avoiding issues like
> CVE-2012-2459 in Merkle trees).
> * Extensibility through leaf versions, OP_SUCCESS opcodes, and
> upgradable pubkey types.
>
> The BIP drafts can be found here:
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
> specifies the transaction input spending rules.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
> specifies the changes to Script inside such spends.
> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
> is the Schnorr signature proposal that was discussed earlier on this
> list (See
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.ht
>ml)
>
> An initial reference implementation of the consensus changes, plus
> preliminary construction/signing tests in the Python framework can be
> found on https://github.com/sipa/bitcoin/commits/taproot. All
> together, excluding the Schnorr signature module in libsecp256k1, the
> consensus changes are around 520 LoC.
>
> While many other ideas exist, not everything is incorporated. This
> includes several ideas that can be implemented separately without loss
> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
> which we're working on as an independent proposal.
>
> The document explains basic wallet operations, such as constructing
> outputs and signing. However, a wide variety of more complex
> constructions exist. Standardizing these is useful, but out of scope
> for now. It is likely also desirable to define extensions to PSBT
> (BIP174) for interacting with Taproot. That too is not included here.
>
> Cheers,

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

[bitcoin-dev] Taproot proposal

[Pieter Wuille via bitcoin-dev]

Hello everyone,

Here are two BIP drafts that specify a proposal for a Taproot
softfork. A number of ideas are included:

* Taproot to make all outputs and cooperative spends indistinguishable
from eachother.
* Merkle branches to hide the unexecuted branches in scripts.
* Schnorr signatures enable wallet software to use key
aggregation/thresholds within one input.
* Improvements to the signature hashing algorithm (including signing
all input amounts).
* Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support
batch validation.
* Tagged hashing for domain separation (avoiding issues like
CVE-2012-2459 in Merkle trees).
* Extensibility through leaf versions, OP_SUCCESS opcodes, and
upgradable pubkey types.

The BIP drafts can be found here:
* https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki
specifies the transaction input spending rules.
* https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki
specifies the changes to Script inside such spends.
* https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki
is the Schnorr signature proposal that was discussed earlier on this
list (See 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html)

An initial reference implementation of the consensus changes, plus
preliminary construction/signing tests in the Python framework can be
found on https://github.com/sipa/bitcoin/commits/taproot. All
together, excluding the Schnorr signature module in libsecp256k1, the
consensus changes are around 520 LoC.

While many other ideas exist, not everything is incorporated. This
includes several ideas that can be implemented separately without loss
of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
which we're working on as an independent proposal.

The document explains basic wallet operations, such as constructing
outputs and signing. However, a wide variety of more complex
constructions exist. Standardizing these is useful, but out of scope
for now. It is likely also desirable to define extensions to PSBT
(BIP174) for interacting with Taproot. That too is not included here.

Cheers,

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