public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Ethan Heilman <eth3rs@gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Cc: ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>,
	"lightning-dev@lists.linuxfoundation.org"
	<lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout
Date: Thu, 3 Oct 2019 20:48:17 -0400	[thread overview]
Message-ID: <CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com> (raw)
In-Reply-To: <C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com>

I hope you are having an great afternoon ZmnSCPxj,

You make an excellent point!

I had thought about doing the following to tag nodes

|| means OP_CAT

`node = SHA256(type||SHA256(data))`
so a subnode would be
`subnode1 = SHA256(1||SHA256(subnode2||subnode3))`
and a leaf node would be
`leafnode = SHA256(0||SHA256(leafdata))`

Yet, I like your idea better. Increasing the size of the two inputs to
OP_CAT to be 260 Bytes each where 520 Bytes is the maximum allowable
size of object on the stack seems sensible and also doesn't special
case the logic of OP_CAT.

It would also increase performance. SHA256(tag||subnode2||subnode3)
requires 2 compression function calls whereas
SHA256(1||SHA256(subnode2||subnode3)) requires 2+1=3 compression
function calls (due to padding).

>Or we could implement tagged SHA256 as a new opcode...

I agree that tagged SHA256 as an op code that would certainty be
useful, but OP_CAT provides far more utility and is a simpler change.

Thanks,
Ethan

On Thu, Oct 3, 2019 at 7:42 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
>
> > To avoid derailing the NO_INPUT conversation, I have changed the
> > subject to OP_CAT.
> >
> > Responding to:
> > """
> >
> > -   `SIGHASH` flags attached to signatures are a misdesign, sadly
> >     retained from the original BitCoin 0.1.0 Alpha for Windows design, on
> >     par with:
> >     [..]
> >
> > -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> >     [..]
> >     """
> >
> >     OP_CAT is an extremely valuable op code. I understand why it was
> >     removed as the situation at the time with scripts was dire. However
> >     most of the protocols I've wanted to build on Bitcoin run into the
> >     limitation that stack values can not be concatenated. For instance
> >     TumbleBit would have far smaller transaction sizes if OP_CAT was
> >     supported in Bitcoin. If it happens to me as a researcher it is
> >     probably holding other people back as well. If I could wave a magic
> >     wand and turn on one of the disabled op codes it would be OP_CAT. Of
> >     course with the change that size of each concatenated value must be 64
> >     Bytes or less.
>
> Why 64 bytes in particular?
>
> It seems obvious to me that this 64 bytes is most suited for building Merkle trees, being the size of two SHA256 hashes.
>
> However we have had issues with the use of Merkle trees in Bitcoin blocks.
> Specifically, it is difficult to determine if a hash on a Merkle node is the hash of a Merkle subnode, or a leaf transaction.
> My understanding is that this is the reason for now requiring transactions to be at least 80 bytes.
>
> The obvious fix would be to prepend the type of the hashed object, i.e. add at least one byte to determine this type.
> Taproot for example uses tagged hash functions, with a different tag for leaves, and tagged hashes are just prepend-this-32-byte-constant-twice-before-you-SHA256.
>
> This seems to indicate that to check merkle tree proofs, an `OP_CAT` with only 64 bytes max output size would not be sufficient.
>
> Or we could implement tagged SHA256 as a new opcode...
>
> Regards,
> ZmnSCPxj
>
>
> >
> >     On Tue, Oct 1, 2019 at 10:04 PM ZmnSCPxj via bitcoin-dev
> >     bitcoin-dev@lists.linuxfoundation.org wrote:
> >
> >
> > > Good morning lists,
> > > Let me propose the below radical idea:
> > >
> > > -   `SIGHASH` flags attached to signatures are a misdesign, sadly retained from the original BitCoin 0.1.0 Alpha for Windows design, on par with:
> > >     -   1 RETURN
> > >     -   higher-`nSequence` replacement
> > >     -   DER-encoded pubkeys
> > >     -   unrestricted `scriptPubKey`
> > >     -   Payee-security-paid-by-payer (i.e. lack of P2SH)
> > >     -   `OP_CAT` and `OP_MULT` and `OP_ADD` and friends
> > >     -   transaction malleability
> > >     -   probably many more
> > >
> > > So let me propose the more radical excision, starting with SegWit v1:
> > >
> > > -   Remove `SIGHASH` from signatures.
> > > -   Put `SIGHASH` on public keys.
> > >
> > > Public keys are now encoded as either 33-bytes (implicit `SIGHASH_ALL`) or 34-bytes (`SIGHASH` byte, followed by pubkey type, followed by pubkey coordinate).
> > > `OP_CHECKSIG` and friends then look at the public key to determine sighash algorithm rather than the signature.
> > > As we expect public keys to be indirectly committed to on every output `scriptPubKey`, this is automatically output tagging to allow particular `SIGHASH`.
> > > However, we can then utilize the many many ways to hide public keys away until they are needed, exemplified in MAST-inside-Taproot.
> > > I propose also the addition of the opcode:
> > >
> > >     <sighash> <pubkey> OP_SETPUBKEYSIGHASH
> > >
> > >
> > > -   `sighash` must be one byte.
> > > -   `pubkey` may be the special byte `0x1`, meaning "just use the Taproot internal pubkey".
> > > -   `pubkey` may be 33-byte public key, in which case the `sighash` byte is just prepended to it.
> > > -   `pubkey` may be 34-byte public key with sighash, in which case the first byte is replaced with `sighash` byte.
> > > -   If `sighash` is `0x00` then the result is a 33-byte public key (the sighash byte is removed) i.e. `SIGHASH_ALL` implicit.
> > >
> > > This retains the old feature where the sighash is selected at time-of-spending rather than time-of-payment.
> > > This is done by using the script:
> > >
> > >     <pubkey> OP_SETPUBKEYSIGHASH OP_CHECKSIG
> > >
> > >
> > > Then the sighash can be put in the witness stack after the signature, letting the `SIGHASH` flag be selected at time-of-signing, but only if the SCRIPT specifically is formed to do so.
> > > This is malleability-safe as the signature still commits to the `SIGHASH` it was created for.
> > > However, by default, public keys will not have an attached `SIGHASH` byte, implying `SIGHASH_ALL` (and disallowing-by-default non-`SIGHASH_ALL`).
> > > This removes the problems with `SIGHASH_NONE` `SIGHASH_SINGLE`, as they are allowed only if the output specifically says they are allowed.
> > > Would this not be a superior solution?
> > > Regards,
> > > ZmnSCPxj
> > >
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>


  reply	other threads:[~2019-10-04  0:48 UTC|newest]

Thread overview: 36+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-09-30 13:23 [bitcoin-dev] Continuing the discussion about noinput / anyprevout Christian Decker
2019-09-30 16:00 ` ZmnSCPxj
2019-09-30 23:28   ` ZmnSCPxj
2019-10-01 14:26     ` Christian Decker
2019-10-01 14:45     ` Anthony Towns
2019-10-01 15:42       ` ZmnSCPxj
2019-10-01 14:20   ` Christian Decker
2019-10-01 15:35     ` ZmnSCPxj
2019-10-03  9:42       ` Christian Decker
2019-10-01 12:23 ` Chris Stewart
2019-10-01 13:31   ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
2019-10-03 10:01     ` Christian Decker
2019-10-03  9:57   ` Christian Decker
     [not found] ` <CACJVCgJ9PL-2jTS71--tXsa=QkK+f5_ciYLwv468WUno=XXAig@mail.gmail.com>
2019-10-01 14:27   ` Ethan Heilman
2019-10-01 15:14   ` Chris Stewart
2019-10-03 10:30     ` Christian Decker
2019-10-01 15:59 ` [bitcoin-dev] " Anthony Towns
2019-10-02  2:03   ` ZmnSCPxj
2019-10-03  1:47     ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
2019-10-03  3:07       ` ZmnSCPxj
2019-10-03 15:05     ` [bitcoin-dev] OP_CAT was " Ethan Heilman
2019-10-03 23:42       ` [bitcoin-dev] [Lightning-dev] " ZmnSCPxj
2019-10-04  0:48         ` Ethan Heilman [this message]
2019-10-04  5:02           ` Jeremy
2019-10-04  7:00             ` ZmnSCPxj
2019-10-04 18:33               ` Jeremy
2019-10-04 11:15             ` Peter Todd
2019-10-04 18:40               ` Jeremy
2019-10-05 15:49                 ` Peter Todd
2019-10-06  8:46                   ` ZmnSCPxj
2019-10-06  9:12                     ` Peter Todd
2019-10-06  7:02       ` Lloyd Fournier
2019-10-09 16:56       ` Andrew Poelstra
2019-10-02 15:11   ` [bitcoin-dev] " s7r
2019-10-03 11:08   ` Christian Decker
2019-10-05 10:06     ` Anthony Towns

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com' \
    --to=eth3rs@gmail.com \
    --cc=ZmnSCPxj@protonmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=lightning-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox