Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Johnson Lau via bitcoin-dev


> On 18 Dec 2018, at 12:58 PM, Anthony Towns  wrote:
> 
> On Mon, Dec 17, 2018 at 10:18:40PM -0500, Russell O'Connor wrote:
>> On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau  wrote:
>>But I’m not sure if that would do more harm than good. For example, people
>>might lose money by copying an existing script template. But they might
>>also lose money in the same way as CHECKMULTISIG is disabled. So I’m not
>>sure.
> 
> Well, if CHECKSIG* and CHECKMULTISIG* are all disabled in favour of
> CHECKDLS, CHECKDLSVERIFY and CHECKDLSADD with both different names and
> different opcodes, copying a script template opcode-for-opcode from v0
> to v1 will always fail. (With taproot, this doesn't necessarily mean you
> lose money, even if the script is impossible to ever satisfy, since you
> may be able to recover via the direct signature path)
> 
>>Another related thing I’d like to bikeshed is to pop the stack after
>>OP_CLTV and OP_CSV. The same pros and cons apply.
>> This one is almost a no-brainer I think.  Nearly every instance of OP_CSV is
>> followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack
>> afterwards.
> 
> It's definitely bikeshedding so whatever; but to me, it seems like it'd
> be easier for everyone to have it so that if you've got the same opcode
> in v0 script and v1.0 script; they have precisely the same semantics.
> 
> (That said, constructions like " CLTV  CHECKSIGVERIFY" that avoid
> the DROP and work when you're expected to leave a true value on the
> stack won't work if you have to end up with an empty stack)
> 
> Cheers,
> aj
> 

I think you mean   CHECKSIGVERIFY  CLTV, but this works only for simple 
script. Most likely you need a DROP if you use IF or CODESEPARATOR.

However, if we change the rule from “one true stack item” to “empty stack”, 
CLTV/CSV popping stack will make more sense. So I think either we change all, 
or change nothing.

The “true stack item” and CLTV/CSV as NOP are tech debt. Fixing them in new 
script version makes script creation easier and sometimes cheaper, but the fix 
itself creates further tech debts in the code. So I don’t have strong opinion 
on this topic.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Anthony Towns via bitcoin-dev
On Mon, Dec 17, 2018 at 10:18:40PM -0500, Russell O'Connor wrote:
> On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau  wrote:
> But I’m not sure if that would do more harm than good. For example, people
> might lose money by copying an existing script template. But they might
> also lose money in the same way as CHECKMULTISIG is disabled. So I’m not
> sure.

Well, if CHECKSIG* and CHECKMULTISIG* are all disabled in favour of
CHECKDLS, CHECKDLSVERIFY and CHECKDLSADD with both different names and
different opcodes, copying a script template opcode-for-opcode from v0
to v1 will always fail. (With taproot, this doesn't necessarily mean you
lose money, even if the script is impossible to ever satisfy, since you
may be able to recover via the direct signature path)

> Another related thing I’d like to bikeshed is to pop the stack after
> OP_CLTV and OP_CSV. The same pros and cons apply.
> This one is almost a no-brainer I think.  Nearly every instance of OP_CSV is
> followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack
> afterwards.

It's definitely bikeshedding so whatever; but to me, it seems like it'd
be easier for everyone to have it so that if you've got the same opcode
in v0 script and v1.0 script; they have precisely the same semantics.

(That said, constructions like " CLTV  CHECKSIGVERIFY" that avoid
the DROP and work when you're expected to leave a true value on the
stack won't work if you have to end up with an empty stack)

Cheers,
aj

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


Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Russell O'Connor via bitcoin-dev
On Mon, Dec 17, 2018 at 3:16 PM Johnson Lau  wrote:

>
> I proposed the same in BIP114. I wish Satoshi had designed that way.
>

Thanks.  I probably read that and internalized it and forgot you wrote it.


> But I’m not sure if that would do more harm than good. For example, people
> might lose money by copying an existing script template. But they might
> also lose money in the same way as CHECKMULTISIG is disabled. So I’m not
> sure.
>
> Another related thing I’d like to bikeshed is to pop the stack after
> OP_CLTV and OP_CSV. The same pros and cons apply.
>

This one is almost a no-brainer I think.  Nearly every instance of OP_CSV
is followed by an OP_DROP and we'd save 1 WU per OP_CSV if we pop the stack
afterwards.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Johnson Lau via bitcoin-dev


> On 16 Dec 2018, at 7:38 AM, Russell O'Connor via bitcoin-dev 
>  wrote:
> 
> On Fri, Dec 14, 2018 at 8:39 AM Anthony Towns via bitcoin-dev 
>  > wrote:
>   5. if there's exactly one, non-zero item on the stack; succeed
> 
> Unless it is too much bikeshedding, I'd like to propose that to succeed the 
> stack must be exactly empty.  Script is more composable that way, removing 
> the need for special logic to handle top-level CHECKSIG, vs mid-level 
> CHECKSIGVERIFY.
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

I proposed the same in BIP114. I wish Satoshi had designed that way. But I’m 
not sure if that would do more harm than good. For example, people might lose 
money by copying an existing script template. But they might also lose money in 
the same way as CHECKMULTISIG is disabled. So I’m not sure.

Another related thing I’d like to bikeshed is to pop the stack after OP_CLTV 
and OP_CSV. The same pros and cons apply.___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-19 Thread Russell O'Connor via bitcoin-dev
On Fri, Dec 14, 2018 at 8:39 AM Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>   5. if there's exactly one, non-zero item on the stack; succeed
>

Unless it is too much bikeshedding, I'd like to propose that to succeed the
stack must be exactly empty.  Script is more composable that way, removing
the need for special logic to handle top-level CHECKSIG, vs mid-level
CHECKSIGVERIFY.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Schnorr and taproot (etc) upgrade

2018-12-18 Thread Anthony Towns via bitcoin-dev
Hi *,

(All the following is heavily informed by talking with other smart people,
and while probably all the clever ideas are theirs, any nonsense and
mistakes are certainly my own. I guess I'll pretend there were Chatham
House rules or something to avoid any blame/responsibility accidently
landing on their shoulders? Anyway, I hope discussing this in public
turns out more useful and productive than disastrous and bikesheddy :)


Rusty wrote "Without a concrete taproot proposal it's hard to make
assertions". I'm not going to offer a completely concrete proposal,
but fwiw, here's my thoughts on what should be included in the segwit v1
proposal, which I think might be concrete enough for discussion purposes:

 - introduce 33-byte v1 witness addresses should encode a secp256k1 ECC
   point (P), spendable either by:

- a direct schnorr signature (s,R) on that point
  (s*G = R + H(R,P,txdigest)*P), with the 1-byte sighash per the
  other thread indicating exactly what goes into the tx digest, etc

- a script (s), the witness data for the script (wit(s)),
  with a taproot/merkle path to the script (P,path(S,s)),
  satisfying the taproot condition (Q = P + H(P,S)*G)

 - the taproot scripts should get a version, and since you have to
   provide P anyway in order to spend by a script, you've got 7-bits spare
   in the byte that encodes the evenness/oddness of P, so that gives you
   v1.0 to v1.127 for free. So if we define script version 0 initially,
   and just automatically accept any script with a later version, we
   can soft-fork arbitrary script upgrades without bumping the segwit
   (major) version.

 - we should replace the ECDSA CHECKSIG/CHECKMULTISIG ops with new
   Schnorr ops. A name that's been suggested for the new ops is "CHECKDLS"
   for discrete-log-signature; I'm using that.

   Rather than CHECKMULTISIG, a simple, more general approach seems to
   be "CHECKDLSADD" which takes a signature, a number, and a pubkey,
   and increments the number if the signature is valid, and leaves it
   untouched if not. So "2 of 3 multisig" becomes "0  CHECKDLSADD
CHECKDLSADD  CHECKDLSADD 2 EQ", eg. That means replacing the
   current four CHECK(multi)SIG(verify) opcodes, with three opcodes:
   CHECKDLS, CHECKDLSVERIFY and CHECKDLSADD.

   To make batch verifiability of signatures work, the only acceptable
   invalid signature for CHECKDLS or CHECKDLSADD needs to be an empty
   vector; anything else should fail the script/transaction/block.

 - adding OP_MASK to support script masking via sighash per the other
   thread; note this only matters for the new CHECKDLS opcodes, since for
   direct signatures on the scriptPubKey, there is no script to mask.
   This means it's completely changeable with new script versions,
   if desired.

 - making (almost) all the currently invalid opcodes upgradeable
   with what I'm calling "OP_SUCCESS" semantics [0], so that we have more
   flexibility than OP_NOP gives us. An approach for those semantics
   that seems fairly easy to analyse is to treat script processing as
   going in phases:

  1. tokenise; check push sizes and overall script size
  2. if any OP_SUCCESS appeared; succeed
  3. if banned opcodes appeared; fail (OP_VERIF, OP_VERNOTIF?)
  4. otherwise, run the script; fail if there's an error
  5. if there's exactly one, non-zero item on the stack; succeed
  6. otherwise; fail

   (Obviously an implementation can do these in parallel if that's more
   efficient)

   That way any of the "OP_SUCCESS" opcodes can be replaced by any
   normal opcode (eg addition, a different sort of signature checking,
   push tx or blockchain data to the stack) in a soft-fork; and you
   can easily be sure that the new functionality is a soft-fork (as
   long as you're not trying to change how pushes work)

   [1]

   This even means you could use an OP_SUCCESS opcode to signal an
   upgrade of other opcodes, eg an OP_ARITH64BIT that upgrades OP_ADD
   etc to support arithmetic on 64 bit inputs.

 - and that's it.

I think this is a fairly modest collection of changes:

 signature/address stuff:
   - schnorr
   - new sighash (including "noinput")
   - taproot
   - merkelized-scripts
   - avoid weird CHECKMULTISIG behaviour
 upgradeability:
   - script minor versions
   - OP_SUCCESS

I think there's a good reason to bundle all those together: the signature
stuff go together with a new address version, and the upgradeability
stuff helps reduce the need to do more new address versions.

Well, it's modest at least compared to what's conceivable: there are a
*lot* of other neat ideas that could theoretically be done in the same
soft-fork, but IMHO are better left for later, eg:

 - graftroot, g'root, cross-input signature aggregation
 - non-interactive half-signature aggregation
 - re-enabling opcodes (CAT, MUL, XOR, etc)
 - check-sig-of-msg-on-stack, push txdata, other covenant-y things
 - different cryptosystems (eg, 384 bit curves for