[bitcoin-dev] MAST/Schnorr related soft-forks

[bitcoin-dev] MAST/Schnorr related soft-forks

[Anthony Towns]

Hello world,

After the core dev meetup in March I wrote up some notes of where I
think things stand for signing stuff post-Schnorr. It was mostly for my
own benefit but maybe it's helpful for others too, so...

They're just notes, so may assume a fair bit of background to be able to
understand the meaning of the bullet points. In particular, note that I'm
using "schnorr" just to describe the signature algorithm, and the terms
"key aggregation" to describe turning an n-of-n key multisig setup into
a single key setup, and "signature aggregation" to describe combining
signatures from many inputs/transactions together: those are often all
just called "schnorr signatures" in various places.


Anyway! I think it's fair to split the ideas around up as follows:

1) Schnorr CHECKSIG

  Benefits:
    - opportunity to change signature encoding from DER to save a few
      bytes per signature, and have fixed size signatures making tx size
      calculations easier

    - enables n-of-n multisig key aggregation (a single pubkey and
      signature gives n-of-n security; setup non-interactively via muSig,
      or semi-interactively via proof of possession of private key;
      interactive signature protocol)

    - enables m-of-n multisig key aggregation with interactive setup and
      interactive signature protocol, and possibly substantial storage
      requirements for participating signers

    - enables scriptless scripts and discreet log contracts via
      key aggregation and interactive

    - enables payment decorrelation for lightning

    - enables batch validation of signatures, which substantially reduces
      computational cost of signature verification, provided a single
      "all sigs valid" or "some sig(s) invalid" output (rather than
      "sig number 5 is invalid") is sufficient

    - better than ecdsa due to reducing signature malleability
      (and possibly due to having a security proof that has had more
      review?)

   Approaches:
     - bump segwit version to replace P2WPKH
     - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
     - hardfork to allowing existing addresses to be solved via Schnorr sig
       as alternative to ECDSA

2) Merkelized Abstract Syntax Trees

   Two main benefits for enabling MAST:
    - logarithmic scaling for scripts with many alternative paths
    - only reveals (approximate) number of alternative execution branches,
      not what they may have been

   Approaches:
    - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
      item remaining on the alt stack at the end of script exeution as a
      script and do tail-recursion into it (BIP 116, 117)
    - bump the segwit version and introduce a "pay-to-merkelized-script"
      address form (BIP 114)

3) Taproot

   Requirements:
    - only feasible if Schnorr is available (required in order to make the
      pubkey spend actually be a multisig spend)
    - andytoshi has written up a security proof at
      https://github.com/apoelstra/taproot

   Benefits:
    - combines pay-to-pubkey and pay-to-script in a single address,
      improving privacy
    - allows choice of whether to use pubkey or script at spend time,
      allowing for more efficient spends (via pubkey) without reducing
      flexibility (via script)

   Approaches:
    - bump segwit version and introduce a "pay-to-taproot" address form

4) Graftroot

   Requirements:
    - only really feasible if Schnorr is implemented first, so that
      multiple signers can be required via a single pubkey/signature
    - people seem to want a security proof for this; not sure if that's
      hard or straightforward

   Benefits:
    - allows delegation of authorisation to spend an output already
      on the blockchain
    - constant scaling for scripts with many alternative paths
      (better than MAST's logarithmic scaling)
    - only reveals the possibility of alternative execution branches, 
      not what they may have been or if any actually existed

   Drawbacks:
    - requires signing keys to be online when constructing scripts (cannot
      do complicated pay to cold wallet without warming it up)
    - requires storing signatures for scripts (if you were able to
      reconstruct the sigs, you could just sign the tx directly and wouldn't
      use a script)
    - cannot prove that alternative methods of spending are not
      possible to anyone who doesn't exclusively hold (part of) the
      output address private key
    - adds an extra signature check on script spends

   Approaches:
    - bump segwit version and introduce a "pay-to-graftroot" address form

5) Interactive Signature Aggregation

   Requirements:
    - needs Schnorr

   Description:
    - allows signers to interactively collaborate when constructing a
      transaction to produce a single signature that covers multiple
      inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr
      signatures

   Benefits:
    - reduces computational cost of additional signatures (i think?)
    - reduces witness storage needed for additional signatures to just the
      sighash flag byte (or bytes, if it's expanded)
    - transaction batching and coinjoins potentially become cheaper than
      independent transactions, indirectly improving on-chain privacy

   Drawbacks:
    - each soft-fork introduces a checkpoint, such that signatures that
      are not validated by versions prior to the soft-fork cannot be
      aggregated with signatures that are validated by versions prior to
      the soft-fork (see [0] for discussion about avoiding that drawback)

   Approaches:
    - crypto logic can be implemented either by Bellare-Neven or MuSig
    - needs a new p2wpkh output format, so likely warrants a segwit
      version bump
    - may warrant allowing multiple aggregation buckets
    - may warrant peer-to-peer changes and a new per-tx witness

6) Non-interactive half-signature aggregation within transaction

   Requirements:
     - needs Schnorr
     - needs a security proof before deployment

   Benefits:
     - can halve the size of non-aggregatable signatures in a transaction
     - in particular implies the size overhead of a graftroot script
       is just 32B, the same as a taproot script

   Drawbacks:
     - cannot be used with scriptless-script signatures

   Approaches:
     - ideally best combined with interactive aggregate signatures, as it
       has similar implementation requirements

7) New SIGHASH modes

   These will also need a new segwit version (for p2pk/p2pkh) and probably
   need to be considered at the same time.

8) p2pk versus p2pkh

   Whether to stick with a pubkeyhash for the address or just have a pubkey
   needs to be decided for any new segwit version.

9) Other new opcodes

   Should additional opcodes in new segwit versions be reserved as OP_NOP or
   as OP_RETURN_VALID, or something else?

   Should any meaningful new opcodes be supported or re-enabled?

10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit

   Making existing p2pk or p2pkh outputs spendable via Schnorr with
   interactive signature aggregation would likely be a big win for people
   with old UTXOs, without any decrease in security, especially if done
   a significant time after those features were supported for new outputs.

11) Should addresses be hashes or scripts?

   maaku's arguments for general opcodes for MAST make me wonder a bit
   if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie
   should we have script opcodes as the top level way to write addresses,
   rather than picking the "best" form of address everyone should use,
   and having people have to opt-out of that. probably already too late
   to actually have that debate though.

Anyway, I think what that adds up to is:

 - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes
   really needs to be done via new segwit versions

 - We can evaluate MAST in segwit v0 independently -- use the existing
   BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later
   segwit versions.

 - There is no point deploying any of this for non-segwit scripts

 - Having the taproot script be a MAST root probably makes sense. If so,
   a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes
   sense at some point.

So I think that adds up to:

 a) soft-fork for MAST in segwit v0 anytime if there's community/economic
    support for it?

 b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime

 c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and
    taproot+mast addresses in not too much time

 d) soft-fork for segwit v2 introducing further upgrades, particularly
    graftroot

 e) soft-fork for segwit v2 to support interactive signature aggregation

 f) soft-fork for segwit v3 including non-interactive sig aggregation

The rationale there is:

  (a) and (b) are self-contained and we could do them now. My feeling is
  better to skip them and go straight to (c)

  (c) is the collection of stuff that would be a huge win, and seems
  "easily" technically feasible. signature aggregation seems too
  complicated to fit in here, and getting the other stuff done while we
  finish thinking about sigagg seems completely worthwhile.

  (d) is a followon for (c), in case signature aggregation takes a
  *really* long while. It could conceivably be done as a different
  variation of segwit v1, really. It might turn out that there's no
  urgency for graftroot and it should be delayed until non-interactive
  sig aggregation is implementable.

  (e) and (f) are separated just because I worry that non-interactive
  sig aggregation might not turn out to be possible; doing them as a
  single upgrade would be preferrable.

Cheers,
aj

[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html

Re: [bitcoin-dev] MAST/Schnorr related soft-forks

[Russell O'Connor]

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

Thanks for writing this up Anthony.

Do you think that a CHECKSIGFROMSTACK proposal should be included within
this discussion of signature soft-forks, or do you see it as an unrelated
issue?

CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See
http://people.csail.mit.edu/ranjit/papers/scd.pdf), enables poor-man's
covenants, and I believe the lightning folks are interested in it as well
for some constant space storage scheme.

On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello world,
>
> After the core dev meetup in March I wrote up some notes of where I
> think things stand for signing stuff post-Schnorr. It was mostly for my
> own benefit but maybe it's helpful for others too, so...
>
> They're just notes, so may assume a fair bit of background to be able to
> understand the meaning of the bullet points. In particular, note that I'm
> using "schnorr" just to describe the signature algorithm, and the terms
> "key aggregation" to describe turning an n-of-n key multisig setup into
> a single key setup, and "signature aggregation" to describe combining
> signatures from many inputs/transactions together: those are often all
> just called "schnorr signatures" in various places.
>
>
> Anyway! I think it's fair to split the ideas around up as follows:
>
> 1) Schnorr CHECKSIG
>
>   Benefits:
>     - opportunity to change signature encoding from DER to save a few
>       bytes per signature, and have fixed size signatures making tx size
>       calculations easier
>
>     - enables n-of-n multisig key aggregation (a single pubkey and
>       signature gives n-of-n security; setup non-interactively via muSig,
>       or semi-interactively via proof of possession of private key;
>       interactive signature protocol)
>
>     - enables m-of-n multisig key aggregation with interactive setup and
>       interactive signature protocol, and possibly substantial storage
>       requirements for participating signers
>
>     - enables scriptless scripts and discreet log contracts via
>       key aggregation and interactive
>
>     - enables payment decorrelation for lightning
>
>     - enables batch validation of signatures, which substantially reduces
>       computational cost of signature verification, provided a single
>       "all sigs valid" or "some sig(s) invalid" output (rather than
>       "sig number 5 is invalid") is sufficient
>
>     - better than ecdsa due to reducing signature malleability
>       (and possibly due to having a security proof that has had more
>       review?)
>
>    Approaches:
>      - bump segwit version to replace P2WPKH
>      - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
>      - hardfork to allowing existing addresses to be solved via Schnorr sig
>        as alternative to ECDSA
>
> 2) Merkelized Abstract Syntax Trees
>
>    Two main benefits for enabling MAST:
>     - logarithmic scaling for scripts with many alternative paths
>     - only reveals (approximate) number of alternative execution branches,
>       not what they may have been
>
>    Approaches:
>     - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
>       item remaining on the alt stack at the end of script exeution as a
>       script and do tail-recursion into it (BIP 116, 117)
>     - bump the segwit version and introduce a "pay-to-merkelized-script"
>       address form (BIP 114)
>
> 3) Taproot
>
>    Requirements:
>     - only feasible if Schnorr is available (required in order to make the
>       pubkey spend actually be a multisig spend)
>     - andytoshi has written up a security proof at
>       https://github.com/apoelstra/taproot
>
>    Benefits:
>     - combines pay-to-pubkey and pay-to-script in a single address,
>       improving privacy
>     - allows choice of whether to use pubkey or script at spend time,
>       allowing for more efficient spends (via pubkey) without reducing
>       flexibility (via script)
>
>    Approaches:
>     - bump segwit version and introduce a "pay-to-taproot" address form
>
> 4) Graftroot
>
>    Requirements:
>     - only really feasible if Schnorr is implemented first, so that
>       multiple signers can be required via a single pubkey/signature
>     - people seem to want a security proof for this; not sure if that's
>       hard or straightforward
>
>    Benefits:
>     - allows delegation of authorisation to spend an output already
>       on the blockchain
>     - constant scaling for scripts with many alternative paths
>       (better than MAST's logarithmic scaling)
>     - only reveals the possibility of alternative execution branches,
>       not what they may have been or if any actually existed
>
>    Drawbacks:
>     - requires signing keys to be online when constructing scripts (cannot
>       do complicated pay to cold wallet without warming it up)
>     - requires storing signatures for scripts (if you were able to
>       reconstruct the sigs, you could just sign the tx directly and
> wouldn't
>       use a script)
>     - cannot prove that alternative methods of spending are not
>       possible to anyone who doesn't exclusively hold (part of) the
>       output address private key
>     - adds an extra signature check on script spends
>
>    Approaches:
>     - bump segwit version and introduce a "pay-to-graftroot" address form
>
> 5) Interactive Signature Aggregation
>
>    Requirements:
>     - needs Schnorr
>
>    Description:
>     - allows signers to interactively collaborate when constructing a
>       transaction to produce a single signature that covers multiple
>       inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr
>       signatures
>
>    Benefits:
>     - reduces computational cost of additional signatures (i think?)
>     - reduces witness storage needed for additional signatures to just the
>       sighash flag byte (or bytes, if it's expanded)
>     - transaction batching and coinjoins potentially become cheaper than
>       independent transactions, indirectly improving on-chain privacy
>
>    Drawbacks:
>     - each soft-fork introduces a checkpoint, such that signatures that
>       are not validated by versions prior to the soft-fork cannot be
>       aggregated with signatures that are validated by versions prior to
>       the soft-fork (see [0] for discussion about avoiding that drawback)
>
>    Approaches:
>     - crypto logic can be implemented either by Bellare-Neven or MuSig
>     - needs a new p2wpkh output format, so likely warrants a segwit
>       version bump
>     - may warrant allowing multiple aggregation buckets
>     - may warrant peer-to-peer changes and a new per-tx witness
>
> 6) Non-interactive half-signature aggregation within transaction
>
>    Requirements:
>      - needs Schnorr
>      - needs a security proof before deployment
>
>    Benefits:
>      - can halve the size of non-aggregatable signatures in a transaction
>      - in particular implies the size overhead of a graftroot script
>        is just 32B, the same as a taproot script
>
>    Drawbacks:
>      - cannot be used with scriptless-script signatures
>
>    Approaches:
>      - ideally best combined with interactive aggregate signatures, as it
>        has similar implementation requirements
>
> 7) New SIGHASH modes
>
>    These will also need a new segwit version (for p2pk/p2pkh) and probably
>    need to be considered at the same time.
>
> 8) p2pk versus p2pkh
>
>    Whether to stick with a pubkeyhash for the address or just have a pubkey
>    needs to be decided for any new segwit version.
>
> 9) Other new opcodes
>
>    Should additional opcodes in new segwit versions be reserved as OP_NOP
> or
>    as OP_RETURN_VALID, or something else?
>
>    Should any meaningful new opcodes be supported or re-enabled?
>
> 10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit
>
>    Making existing p2pk or p2pkh outputs spendable via Schnorr with
>    interactive signature aggregation would likely be a big win for people
>    with old UTXOs, without any decrease in security, especially if done
>    a significant time after those features were supported for new outputs.
>
> 11) Should addresses be hashes or scripts?
>
>    maaku's arguments for general opcodes for MAST make me wonder a bit
>    if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie
>    should we have script opcodes as the top level way to write addresses,
>    rather than picking the "best" form of address everyone should use,
>    and having people have to opt-out of that. probably already too late
>    to actually have that debate though.
>
> Anyway, I think what that adds up to is:
>
>  - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes
>    really needs to be done via new segwit versions
>
>  - We can evaluate MAST in segwit v0 independently -- use the existing
>    BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later
>    segwit versions.
>
>  - There is no point deploying any of this for non-segwit scripts
>
>  - Having the taproot script be a MAST root probably makes sense. If so,
>    a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes
>    sense at some point.
>
> So I think that adds up to:
>
>  a) soft-fork for MAST in segwit v0 anytime if there's community/economic
>     support for it?
>
>  b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime
>
>  c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and
>     taproot+mast addresses in not too much time
>
>  d) soft-fork for segwit v2 introducing further upgrades, particularly
>     graftroot
>
>  e) soft-fork for segwit v2 to support interactive signature aggregation
>
>  f) soft-fork for segwit v3 including non-interactive sig aggregation
>
> The rationale there is:
>
>   (a) and (b) are self-contained and we could do them now. My feeling is
>   better to skip them and go straight to (c)
>
>   (c) is the collection of stuff that would be a huge win, and seems
>   "easily" technically feasible. signature aggregation seems too
>   complicated to fit in here, and getting the other stuff done while we
>   finish thinking about sigagg seems completely worthwhile.
>
>   (d) is a followon for (c), in case signature aggregation takes a
>   *really* long while. It could conceivably be done as a different
>   variation of segwit v1, really. It might turn out that there's no
>   urgency for graftroot and it should be delayed until non-interactive
>   sig aggregation is implementable.
>
>   (e) and (f) are separated just because I worry that non-interactive
>   sig aggregation might not turn out to be possible; doing them as a
>   single upgrade would be preferrable.
>
> Cheers,
> aj
>
> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
> 2018-March/015838.html
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] MAST/Schnorr related soft-forks

[Bram Cohen]

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

I'm not sure about the best way to approach soft-forking (I've opined on it
before, and still find the details mind-numbing) but the end goal seems
fairly clearly to be an all of the above: Have aggregatable public keys
which support simple signatures, taproot with BIP 114 style taproot, and
Graftroot. And while you're at it, nuke OP_IF from orbit and make all the
unused opcodes be return success.

This all in principle could be done in one fell swoop with a single new
script type. That would be a whole lot of stuff to roll out at once, but at
least it wouldn't have so many painstaking intermediate soft forks to
administer.

On Thu, May 10, 2018 at 7:23 AM, Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Thanks for writing this up Anthony.
>
> Do you think that a CHECKSIGFROMSTACK proposal should be included within
> this discussion of signature soft-forks, or do you see it as an unrelated
> issue?
>
> CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See
> http://people.csail.mit.edu/ranjit/papers/scd.pdf), enables poor-man's
> covenants, and I believe the lightning folks are interested in it as well
> for some constant space storage scheme.
>
> On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hello world,
>>
>> After the core dev meetup in March I wrote up some notes of where I
>> think things stand for signing stuff post-Schnorr. It was mostly for my
>> own benefit but maybe it's helpful for others too, so...
>>
>> They're just notes, so may assume a fair bit of background to be able to
>> understand the meaning of the bullet points. In particular, note that I'm
>> using "schnorr" just to describe the signature algorithm, and the terms
>> "key aggregation" to describe turning an n-of-n key multisig setup into
>> a single key setup, and "signature aggregation" to describe combining
>> signatures from many inputs/transactions together: those are often all
>> just called "schnorr signatures" in various places.
>>
>>
>> Anyway! I think it's fair to split the ideas around up as follows:
>>
>> 1) Schnorr CHECKSIG
>>
>>   Benefits:
>>     - opportunity to change signature encoding from DER to save a few
>>       bytes per signature, and have fixed size signatures making tx size
>>       calculations easier
>>
>>     - enables n-of-n multisig key aggregation (a single pubkey and
>>       signature gives n-of-n security; setup non-interactively via muSig,
>>       or semi-interactively via proof of possession of private key;
>>       interactive signature protocol)
>>
>>     - enables m-of-n multisig key aggregation with interactive setup and
>>       interactive signature protocol, and possibly substantial storage
>>       requirements for participating signers
>>
>>     - enables scriptless scripts and discreet log contracts via
>>       key aggregation and interactive
>>
>>     - enables payment decorrelation for lightning
>>
>>     - enables batch validation of signatures, which substantially reduces
>>       computational cost of signature verification, provided a single
>>       "all sigs valid" or "some sig(s) invalid" output (rather than
>>       "sig number 5 is invalid") is sufficient
>>
>>     - better than ecdsa due to reducing signature malleability
>>       (and possibly due to having a security proof that has had more
>>       review?)
>>
>>    Approaches:
>>      - bump segwit version to replace P2WPKH
>>      - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
>>      - hardfork to allowing existing addresses to be solved via Schnorr
>> sig
>>        as alternative to ECDSA
>>
>> 2) Merkelized Abstract Syntax Trees
>>
>>    Two main benefits for enabling MAST:
>>     - logarithmic scaling for scripts with many alternative paths
>>     - only reveals (approximate) number of alternative execution branches,
>>       not what they may have been
>>
>>    Approaches:
>>     - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
>>       item remaining on the alt stack at the end of script exeution as a
>>       script and do tail-recursion into it (BIP 116, 117)
>>     - bump the segwit version and introduce a "pay-to-merkelized-script"
>>       address form (BIP 114)
>>
>> 3) Taproot
>>
>>    Requirements:
>>     - only feasible if Schnorr is available (required in order to make the
>>       pubkey spend actually be a multisig spend)
>>     - andytoshi has written up a security proof at
>>       https://github.com/apoelstra/taproot
>>
>>    Benefits:
>>     - combines pay-to-pubkey and pay-to-script in a single address,
>>       improving privacy
>>     - allows choice of whether to use pubkey or script at spend time,
>>       allowing for more efficient spends (via pubkey) without reducing
>>       flexibility (via script)
>>
>>    Approaches:
>>     - bump segwit version and introduce a "pay-to-taproot" address form
>>
>> 4) Graftroot
>>
>>    Requirements:
>>     - only really feasible if Schnorr is implemented first, so that
>>       multiple signers can be required via a single pubkey/signature
>>     - people seem to want a security proof for this; not sure if that's
>>       hard or straightforward
>>
>>    Benefits:
>>     - allows delegation of authorisation to spend an output already
>>       on the blockchain
>>     - constant scaling for scripts with many alternative paths
>>       (better than MAST's logarithmic scaling)
>>     - only reveals the possibility of alternative execution branches,
>>       not what they may have been or if any actually existed
>>
>>    Drawbacks:
>>     - requires signing keys to be online when constructing scripts (cannot
>>       do complicated pay to cold wallet without warming it up)
>>     - requires storing signatures for scripts (if you were able to
>>       reconstruct the sigs, you could just sign the tx directly and
>> wouldn't
>>       use a script)
>>     - cannot prove that alternative methods of spending are not
>>       possible to anyone who doesn't exclusively hold (part of) the
>>       output address private key
>>     - adds an extra signature check on script spends
>>
>>    Approaches:
>>     - bump segwit version and introduce a "pay-to-graftroot" address form
>>
>> 5) Interactive Signature Aggregation
>>
>>    Requirements:
>>     - needs Schnorr
>>
>>    Description:
>>     - allows signers to interactively collaborate when constructing a
>>       transaction to produce a single signature that covers multiple
>>       inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr
>>       signatures
>>
>>    Benefits:
>>     - reduces computational cost of additional signatures (i think?)
>>     - reduces witness storage needed for additional signatures to just the
>>       sighash flag byte (or bytes, if it's expanded)
>>     - transaction batching and coinjoins potentially become cheaper than
>>       independent transactions, indirectly improving on-chain privacy
>>
>>    Drawbacks:
>>     - each soft-fork introduces a checkpoint, such that signatures that
>>       are not validated by versions prior to the soft-fork cannot be
>>       aggregated with signatures that are validated by versions prior to
>>       the soft-fork (see [0] for discussion about avoiding that drawback)
>>
>>    Approaches:
>>     - crypto logic can be implemented either by Bellare-Neven or MuSig
>>     - needs a new p2wpkh output format, so likely warrants a segwit
>>       version bump
>>     - may warrant allowing multiple aggregation buckets
>>     - may warrant peer-to-peer changes and a new per-tx witness
>>
>> 6) Non-interactive half-signature aggregation within transaction
>>
>>    Requirements:
>>      - needs Schnorr
>>      - needs a security proof before deployment
>>
>>    Benefits:
>>      - can halve the size of non-aggregatable signatures in a transaction
>>      - in particular implies the size overhead of a graftroot script
>>        is just 32B, the same as a taproot script
>>
>>    Drawbacks:
>>      - cannot be used with scriptless-script signatures
>>
>>    Approaches:
>>      - ideally best combined with interactive aggregate signatures, as it
>>        has similar implementation requirements
>>
>> 7) New SIGHASH modes
>>
>>    These will also need a new segwit version (for p2pk/p2pkh) and probably
>>    need to be considered at the same time.
>>
>> 8) p2pk versus p2pkh
>>
>>    Whether to stick with a pubkeyhash for the address or just have a
>> pubkey
>>    needs to be decided for any new segwit version.
>>
>> 9) Other new opcodes
>>
>>    Should additional opcodes in new segwit versions be reserved as OP_NOP
>> or
>>    as OP_RETURN_VALID, or something else?
>>
>>    Should any meaningful new opcodes be supported or re-enabled?
>>
>> 10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit
>>
>>    Making existing p2pk or p2pkh outputs spendable via Schnorr with
>>    interactive signature aggregation would likely be a big win for people
>>    with old UTXOs, without any decrease in security, especially if done
>>    a significant time after those features were supported for new outputs.
>>
>> 11) Should addresses be hashes or scripts?
>>
>>    maaku's arguments for general opcodes for MAST make me wonder a bit
>>    if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie
>>    should we have script opcodes as the top level way to write addresses,
>>    rather than picking the "best" form of address everyone should use,
>>    and having people have to opt-out of that. probably already too late
>>    to actually have that debate though.
>>
>> Anyway, I think what that adds up to is:
>>
>>  - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes
>>    really needs to be done via new segwit versions
>>
>>  - We can evaluate MAST in segwit v0 independently -- use the existing
>>    BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later
>>    segwit versions.
>>
>>  - There is no point deploying any of this for non-segwit scripts
>>
>>  - Having the taproot script be a MAST root probably makes sense. If so,
>>    a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes
>>    sense at some point.
>>
>> So I think that adds up to:
>>
>>  a) soft-fork for MAST in segwit v0 anytime if there's community/economic
>>     support for it?
>>
>>  b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime
>>
>>  c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and
>>     taproot+mast addresses in not too much time
>>
>>  d) soft-fork for segwit v2 introducing further upgrades, particularly
>>     graftroot
>>
>>  e) soft-fork for segwit v2 to support interactive signature aggregation
>>
>>  f) soft-fork for segwit v3 including non-interactive sig aggregation
>>
>> The rationale there is:
>>
>>   (a) and (b) are self-contained and we could do them now. My feeling is
>>   better to skip them and go straight to (c)
>>
>>   (c) is the collection of stuff that would be a huge win, and seems
>>   "easily" technically feasible. signature aggregation seems too
>>   complicated to fit in here, and getting the other stuff done while we
>>   finish thinking about sigagg seems completely worthwhile.
>>
>>   (d) is a followon for (c), in case signature aggregation takes a
>>   *really* long while. It could conceivably be done as a different
>>   variation of segwit v1, really. It might turn out that there's no
>>   urgency for graftroot and it should be delayed until non-interactive
>>   sig aggregation is implementable.
>>
>>   (e) and (f) are separated just because I worry that non-interactive
>>   sig aggregation might not turn out to be possible; doing them as a
>>   single upgrade would be preferrable.
>>
>> Cheers,
>> aj
>>
>> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018
>> -March/015838.html
>>
>> _______________________________________________
>> 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
>
>

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

Re: [bitcoin-dev] MAST/Schnorr related soft-forks

[Chris Belcher]

Thanks for the summary,

It may be worth emphasizing the fungibility aspects of all this.

That summary contains ideas to possibly have separate address types,
opcodes and scriptSigs/witnesses for different feature, at least to
start with. To me this would seem bad because it may miss out on the
fungibility gain from having everything look exactly the same.

With schnorr we may have a unique opportunity to greatly improve
fungibility. It's not too hard to imagine a world where users of
Lightning Network, coinswap, MAST, scriptless scripts, multisig,
taproot, graftroot, etc and regular single-signature on-chain payments
all appear completely indistinguishable. Tracking and data mining could
become pointless when coins can teleport undetectably to a different
place on the blockchain via any number of off-chain protocols.

Of course the downside of doing it like this is that every feature would
probably have to be developed, reviewed, tested and deployed together,
rather than one at a time.

On 10/05/18 13:10, Anthony Towns via bitcoin-dev wrote:
> Hello world,
> 
> After the core dev meetup in March I wrote up some notes of where I
> think things stand for signing stuff post-Schnorr. It was mostly for my
> own benefit but maybe it's helpful for others too, so...
> 
> They're just notes, so may assume a fair bit of background to be able to
> understand the meaning of the bullet points. In particular, note that I'm
> using "schnorr" just to describe the signature algorithm, and the terms
> "key aggregation" to describe turning an n-of-n key multisig setup into
> a single key setup, and "signature aggregation" to describe combining
> signatures from many inputs/transactions together: those are often all
> just called "schnorr signatures" in various places.
> 
> 
> Anyway! I think it's fair to split the ideas around up as follows:
> 
> 1) Schnorr CHECKSIG
> 
>   Benefits:
>     - opportunity to change signature encoding from DER to save a few
>       bytes per signature, and have fixed size signatures making tx size
>       calculations easier
> 
>     - enables n-of-n multisig key aggregation (a single pubkey and
>       signature gives n-of-n security; setup non-interactively via muSig,
>       or semi-interactively via proof of possession of private key;
>       interactive signature protocol)
> 
>     - enables m-of-n multisig key aggregation with interactive setup and
>       interactive signature protocol, and possibly substantial storage
>       requirements for participating signers
> 
>     - enables scriptless scripts and discreet log contracts via
>       key aggregation and interactive
> 
>     - enables payment decorrelation for lightning
> 
>     - enables batch validation of signatures, which substantially reduces
>       computational cost of signature verification, provided a single
>       "all sigs valid" or "some sig(s) invalid" output (rather than
>       "sig number 5 is invalid") is sufficient
> 
>     - better than ecdsa due to reducing signature malleability
>       (and possibly due to having a security proof that has had more
>       review?)
> 
>    Approaches:
>      - bump segwit version to replace P2WPKH
>      - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY
>      - hardfork to allowing existing addresses to be solved via Schnorr sig
>        as alternative to ECDSA
> 
> 2) Merkelized Abstract Syntax Trees
> 
>    Two main benefits for enabling MAST:
>     - logarithmic scaling for scripts with many alternative paths
>     - only reveals (approximate) number of alternative execution branches,
>       not what they may have been
> 
>    Approaches:
>     - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an
>       item remaining on the alt stack at the end of script exeution as a
>       script and do tail-recursion into it (BIP 116, 117)
>     - bump the segwit version and introduce a "pay-to-merkelized-script"
>       address form (BIP 114)
> 
> 3) Taproot
> 
>    Requirements:
>     - only feasible if Schnorr is available (required in order to make the
>       pubkey spend actually be a multisig spend)
>     - andytoshi has written up a security proof at
>       https://github.com/apoelstra/taproot
> 
>    Benefits:
>     - combines pay-to-pubkey and pay-to-script in a single address,
>       improving privacy
>     - allows choice of whether to use pubkey or script at spend time,
>       allowing for more efficient spends (via pubkey) without reducing
>       flexibility (via script)
> 
>    Approaches:
>     - bump segwit version and introduce a "pay-to-taproot" address form
> 
> 4) Graftroot
> 
>    Requirements:
>     - only really feasible if Schnorr is implemented first, so that
>       multiple signers can be required via a single pubkey/signature
>     - people seem to want a security proof for this; not sure if that's
>       hard or straightforward
> 
>    Benefits:
>     - allows delegation of authorisation to spend an output already
>       on the blockchain
>     - constant scaling for scripts with many alternative paths
>       (better than MAST's logarithmic scaling)
>     - only reveals the possibility of alternative execution branches, 
>       not what they may have been or if any actually existed
> 
>    Drawbacks:
>     - requires signing keys to be online when constructing scripts (cannot
>       do complicated pay to cold wallet without warming it up)
>     - requires storing signatures for scripts (if you were able to
>       reconstruct the sigs, you could just sign the tx directly and wouldn't
>       use a script)
>     - cannot prove that alternative methods of spending are not
>       possible to anyone who doesn't exclusively hold (part of) the
>       output address private key
>     - adds an extra signature check on script spends
> 
>    Approaches:
>     - bump segwit version and introduce a "pay-to-graftroot" address form
> 
> 5) Interactive Signature Aggregation
> 
>    Requirements:
>     - needs Schnorr
> 
>    Description:
>     - allows signers to interactively collaborate when constructing a
>       transaction to produce a single signature that covers multiple
>       inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr
>       signatures
> 
>    Benefits:
>     - reduces computational cost of additional signatures (i think?)
>     - reduces witness storage needed for additional signatures to just the
>       sighash flag byte (or bytes, if it's expanded)
>     - transaction batching and coinjoins potentially become cheaper than
>       independent transactions, indirectly improving on-chain privacy
> 
>    Drawbacks:
>     - each soft-fork introduces a checkpoint, such that signatures that
>       are not validated by versions prior to the soft-fork cannot be
>       aggregated with signatures that are validated by versions prior to
>       the soft-fork (see [0] for discussion about avoiding that drawback)
> 
>    Approaches:
>     - crypto logic can be implemented either by Bellare-Neven or MuSig
>     - needs a new p2wpkh output format, so likely warrants a segwit
>       version bump
>     - may warrant allowing multiple aggregation buckets
>     - may warrant peer-to-peer changes and a new per-tx witness
> 
> 6) Non-interactive half-signature aggregation within transaction
> 
>    Requirements:
>      - needs Schnorr
>      - needs a security proof before deployment
> 
>    Benefits:
>      - can halve the size of non-aggregatable signatures in a transaction
>      - in particular implies the size overhead of a graftroot script
>        is just 32B, the same as a taproot script
> 
>    Drawbacks:
>      - cannot be used with scriptless-script signatures
> 
>    Approaches:
>      - ideally best combined with interactive aggregate signatures, as it
>        has similar implementation requirements
> 
> 7) New SIGHASH modes
> 
>    These will also need a new segwit version (for p2pk/p2pkh) and probably
>    need to be considered at the same time.
> 
> 8) p2pk versus p2pkh
> 
>    Whether to stick with a pubkeyhash for the address or just have a pubkey
>    needs to be decided for any new segwit version.
> 
> 9) Other new opcodes
> 
>    Should additional opcodes in new segwit versions be reserved as OP_NOP or
>    as OP_RETURN_VALID, or something else?
> 
>    Should any meaningful new opcodes be supported or re-enabled?
> 
> 10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit
> 
>    Making existing p2pk or p2pkh outputs spendable via Schnorr with
>    interactive signature aggregation would likely be a big win for people
>    with old UTXOs, without any decrease in security, especially if done
>    a significant time after those features were supported for new outputs.
> 
> 11) Should addresses be hashes or scripts?
> 
>    maaku's arguments for general opcodes for MAST make me wonder a bit
>    if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie
>    should we have script opcodes as the top level way to write addresses,
>    rather than picking the "best" form of address everyone should use,
>    and having people have to opt-out of that. probably already too late
>    to actually have that debate though.
> 
> Anyway, I think what that adds up to is:
> 
>  - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes
>    really needs to be done via new segwit versions
> 
>  - We can evaluate MAST in segwit v0 independently -- use the existing
>    BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later
>    segwit versions.
> 
>  - There is no point deploying any of this for non-segwit scripts
> 
>  - Having the taproot script be a MAST root probably makes sense. If so,
>    a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes
>    sense at some point.
> 
> So I think that adds up to:
> 
>  a) soft-fork for MAST in segwit v0 anytime if there's community/economic
>     support for it?
> 
>  b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime
> 
>  c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and
>     taproot+mast addresses in not too much time
> 
>  d) soft-fork for segwit v2 introducing further upgrades, particularly
>     graftroot
> 
>  e) soft-fork for segwit v2 to support interactive signature aggregation
> 
>  f) soft-fork for segwit v3 including non-interactive sig aggregation
> 
> The rationale there is:
> 
>   (a) and (b) are self-contained and we could do them now. My feeling is
>   better to skip them and go straight to (c)
> 
>   (c) is the collection of stuff that would be a huge win, and seems
>   "easily" technically feasible. signature aggregation seems too
>   complicated to fit in here, and getting the other stuff done while we
>   finish thinking about sigagg seems completely worthwhile.
> 
>   (d) is a followon for (c), in case signature aggregation takes a
>   *really* long while. It could conceivably be done as a different
>   variation of segwit v1, really. It might turn out that there's no
>   urgency for graftroot and it should be delayed until non-interactive
>   sig aggregation is implementable.
> 
>   (e) and (f) are separated just because I worry that non-interactive
>   sig aggregation might not turn out to be possible; doing them as a
>   single upgrade would be preferrable.
> 
> Cheers,
> aj
> 
> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>