Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Andrew Poelstra via bitcoin-dev]

On Thu, Oct 03, 2019 at 11:05:52AM -0400, Ethan Heilman wrote:
> 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.
>

Just throwing my two cents in here - as others have noted, OP_CAT
lets you create Merkle trees (allowing e.g. log-sized accountable
threshold sigs, at least in a post-Schnorr future).

It also allows manipulating signatures - e.g. forcing the revelation
of discrete logs by requiring the user use the (1/2) point as a nonce
(this starts with 11 zero bytes, which no other computationally
accessible point does), or by requiring two sigs with the same nonce.

It also lets you do proof-of-work-like computations on hashes or
curvepoints; or enforce that EC points come from a hash and have
no known discrete log. You can also switch on hashes, something
currently impossible because of the 4-byte limitation on numeric
opcodes. I don't have specific application of these in mind but
definitely have cut off many lines of inquiry because they were
impossible.

You could build a crappy Lamport signature, though the key would
be so big that you'd never do this pre-MAST :P.


-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
-Justin Lewis-Webster



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

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd via bitcoin-dev]

On Sun, Oct 06, 2019 at 08:46:59AM +, ZmnSCPxj wrote:
> > Obviously with care you can get the computation right. But at that point 
> > what's
> > the actual advantage over OP_CAT?
> >
> > We're limited by the size of the script anyway; if the OP_CAT output size 
> > limit
> > is comparable to that for almost anything you could use SHA256STREAM on you
> > could just as easily use OP_CAT, followed by a single OP_SHA256.
> 
> Theoretically, `OP_CAT` is less efficient.
> 
> In cases where the memory area used to back the data cannot be resized, new 
> backing memory must be allocated elsewhere and the existing data copied.
> This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case where 
> we add 1 byte per `OP_CAT` and each time find that the memory area currently 
> in use is exactly fitting the data and cannot be resized in-place).

In even that degenerate case allocators also free memory.

Anyway, every execution step in script evaluation has a maximum output size,
and the number of steps is limited. At worst you can allocate the entire
possible stack up-front for relatively little cost (eg fitting in the MB or two
that is a common size for L2 cache).

> Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful 
> in reducing the worst-case `OP_CAT` behavior.
> The question is what limit would be reasonable.
> 64 bytes feels too small if one considers Merkle tree proofs, due to 
> mentioned issues of lack of typechecking.

256 bytes is more than enough for even the most complex summed merkle tree with
512-byte hashes and full-sized sum commitments. Yet that's still less than the
~500byte limit proposed elsewhere.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


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

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj via bitcoin-dev]

Good morning Peter, Jeremy, and lists,

> On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
>
> > Interesting point.
> > The script is under your control, so you should be able to ensure that you
> > are always using a correctly constructed midstate, e.g., something like:
> > scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
> > OP_SHA256STREAM
> >  OP_EQUALVERIFY
> > would hash all the elements on the stack and compare to a known hash.
> > How is that sort of thing weak to midstateattacks?
>
> Obviously with care you can get the computation right. But at that point 
> what's
> the actual advantage over OP_CAT?
>
> We're limited by the size of the script anyway; if the OP_CAT output size 
> limit
> is comparable to that for almost anything you could use SHA256STREAM on you
> could just as easily use OP_CAT, followed by a single OP_SHA256.

Theoretically, `OP_CAT` is less efficient.

In cases where the memory area used to back the data cannot be resized, new 
backing memory must be allocated elsewhere and the existing data copied.
This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case where we 
add 1 byte per `OP_CAT` and each time find that the memory area currently in 
use is exactly fitting the data and cannot be resized in-place).

`OP_SHASTREAM` would not require new allocations once the stream state is in 
place and would not require any copying.


This may be relevant in considering the cost of executing `OP_CAT`.

Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful in 
reducing the worst-case `OP_CAT` behavior.
The question is what limit would be reasonable.
64 bytes feels too small if one considers Merkle tree proofs, due to mentioned 
issues of lack of typechecking.


Regards,
ZmnSCPxj


>
> --
>
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> Lightning-dev mailing list
> lightning-...@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


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

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Lloyd Fournier via bitcoin-dev]

Hi Thread,

I made a reply to the OP but didn't "reply all" so it just went directly to
Ethan. Since the comments were interesting I'll attempt to salvage them by
posting them in full:

== Lloyd's post ==
Hi Ethan,

I'd be interested to know what protocols you need OP_CAT for. I'm trying to
figure out if there really exists any script based protocol that doesn't
have a more efficient scriptless counterpart.  For example,
A²L[1] achieves the same thing as Tumblebit but requires no script. I can
imagine paying based on a merkle path could be useful, but a protocol was
recently suggested on lightning-dev [2] that does this but without OP_CAT
(and without any script!).


[1] https://eprint.iacr.org/2019/589.pdf
[2]
https://www.mail-archive.com/lightning-dev@lists.linuxfoundation.org/msg01427.html
(*I linked to the wrong thread in the original email*).

LL

== Ethan's response ==
Hi Lloyd,

Thanks for your response. I am not sure if you intended to take this off
list or not.

I plan to at some point to enumerate in detail protocols that OP_CAT would
benefit. A more important point is that OP_CAT is a basic building block
and that we don't know what future protocols it would allow. In my own
research I have avoiding going down certain paths because it isn't worth
the time to investigate knowing that OP_CAT wouldn't make the protocol
practical.

In regards to scriptless scripts they almost always require an interactive
protocol and sometimes ZKPs. A2L is very impressive but like TumbleBit it
places a large burden on the developer. Additionally I am aware of no way
to reveal a subset of preimages with scriptless scripts, do a conditioned
reveal i.e. these preimages can only spend under these two pubkeys and
timelockA where after timelockZ this other pubkey can spend without a
preimages. Scriptless scripts are a fantastic tool but they shouldn't be
the only tool that we have.

I'm not sure I follow what you are saying with [2]

This brings me back a philosophical point:
Bitcoin should give people basic tools to build protocols without first
knowing what all those protocols are especially when those tools have very
little downside.

I really appreciate your comments.

Thanks,
Ethan
==

*Back to normal thread*

Hi Ethan,

Thanks for the insightful reply and sorry for my mailing list errors.

> I plan to at some point to enumerate in detail protocols that OP_CAT
would benefit.

Sweet. Thanks.

> Additionally I am aware of no way to reveal a subset of preimages with
scriptless scripts, do a conditioned reveal i.e. these preimages can only
spend under these two pubkeys and timelockA where after timelockZ this
other pubkey can spend without a preimages. Scriptless scripts are a
fantastic tool but they shouldn't be the only tool that we have.

Yes. With adaptor signatures there is no way to reveal more than one
pre-image; you are limited to revealing a single scalar. But you can have
multiple transactions spending from the same output, each with a different
set of scriptless conditions (absolute time locks, relative time locks and
pre-image reveal). This is enough to achieve what I think you are
describing. FWIW there's a growing consensus that you can do lightning
without script [1]. Perhaps we can't do everything with this technique. My
current focus is figuring out what useful things we can't do like this
(even if we were to go wild and add whatever opcodes we wanted). So far it
looks like covenants are the main exception.

> I'm not sure I follow what you are saying with [2]

That is perfectly understandable as I linked the wrong thread (sorry!).
Here's the right one:
https://www.mail-archive.com/lightning-dev@lists.linuxfoundation.org/msg01427.html

I was pointing to the surprising result that you can actually pay for a
merkle path with a particular merkle root leading to a particular leaf that
you're interested in without validating the merkle path on chain (e.g.
OP_CAT and OP_SHA256). The catch is that the leaves have to be pedersen
commitments and you prove the existence of your data in the merkle root by
showing an opening to the leaf pedersen commitment. This may not be general
enough to cover every merkle tree use case (but I'm not sure what those
are!).

> This brings me back a philosophical point:
> Bitcoin should give people basic tools to build protocols without first
knowing what all those protocols are especially when those tools have very
little downside.

This is a really powerful idea. But I've started feeling like you have to
just design the layer 2 protocols first and then design layer 1! It seems
like almost every protocol that people want to make requires very
particular fundamental changes: SegWit for LN-penalty and NOINPUT for eltoo
for example. On top of that it seems like just having the right signature
scheme (schnorr) at layer 1 is enough to enable most useful stuff in an
elegant way.

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

Cheers,

LL

On 

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd via bitcoin-dev]

On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
> Interesting point.
> 
> The script is under your control, so you should be able to ensure that you
> are always using a correctly constructed midstate, e.g., something like:
> 
> scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
> OP_SHA256STREAM
>  OP_EQUALVERIFY
> 
> would hash all the elements on the stack and compare to a known hash.
> How is that sort of thing weak to midstateattacks?

Obviously with care you can get the computation right. But at that point what's
the actual advantage over OP_CAT?

We're limited by the size of the script anyway; if the OP_CAT output size limit
is comparable to that for almost anything you could use SHA256STREAM on you
could just as easily use OP_CAT, followed by a single OP_SHA256.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


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

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy via bitcoin-dev]

Interesting point.

The script is under your control, so you should be able to ensure that you
are always using a correctly constructed midstate, e.g., something like:

scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
OP_SHA256STREAM
 OP_EQUALVERIFY

would hash all the elements on the stack and compare to a known hash.
How is that sort of thing weak to midstateattacks?


--
@JeremyRubin 



On Fri, Oct 4, 2019 at 4:16 AM Peter Todd  wrote:

> On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev wrote:
> > Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> > OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> > function to allow concatenation of an unlimited amount of data, provided
> > the only use is to hash it.
> >
> > You can then use it perhaps as follows:
> >
> > // start a new hash with item
> > OP_SHA256STREAM  (-1) -> [state]
> > // Add item to the hash in state
> > OP_SHA256STREAM n [item] [state] -> [state]
> > // Finalize
> > OP_SHA256STREAM (-2) [state] -> [Hash]
> >
> > <-1> OP_SHA256STREAM<3> OP_SHA256STREAM
> <-2>
> > OP_SHA256STREAM
>
> One issue with this is the simplest implementation where the state is just
> raw
> bytes would expose raw SHA256 midstates, allowing people to use them
> directly;
> preventing that would require adding types to the stack. Specifically I
> could
> write a script that rather than initializing the state correctly from the
> official IV, instead takes an untrusted state as input.
>
> SHA256 isn't designed to be used in situations where adversaries control
> the
> initialization vector. I personally don't know one way or the other if
> anyone
> has analyzed this in detail, but I'd be surprised if that's secure. I
> considered adding midstate support to OpenTimestamps but decided against
> it for
> exactly that reason.
>
> I don't have the link handy but there's even an example of an experienced
> cryptographer on this very list (bitcoin-dev) proposing a design that falls
> victim to this attack. It's a subtle issue and we probably don't want to
> encourage it.
>
> --
> https://petertodd.org 'peter'[:-1]@petertodd.org
> ___
> Lightning-dev mailing list
> lightning-...@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy via bitcoin-dev]

Good point -- in our discussion, we called it OP_FFS -- Fold Functional
Stream, and it could be initialized with a different integer to select for
different functions. Therefore the stream processing opcodes would be
generic, but extensible.
--
@JeremyRubin 



On Fri, Oct 4, 2019 at 12:00 AM ZmnSCPxj via Lightning-dev <
lightning-...@lists.linuxfoundation.org> wrote:

> Good morning Jeremy,
>
> > Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> function to allow concatenation of an unlimited amount of data, provided
> the only use is to hash it.
> >
> > You can then use it perhaps as follows:
> >
> > // start a new hash with item
> > OP_SHA256STREAM  (-1) -> [state]
> > // Add item to the hash in state
> > OP_SHA256STREAM n [item] [state] -> [state]
> > // Finalize
> > OP_SHA256STREAM (-2) [state] -> [Hash]
> >
> > <-1> OP_SHA256STREAM<3> OP_SHA256STREAM
> <-2> OP_SHA256STREAM
> >
> > Or it coul
> >
>
> This seems a good idea.
>
> Though it brings up the age-old tension between:
>
> * Generically-useable components, but due to generalization are less
> efficient.
> * Specific-use components, which are efficient, but which may end up not
> being useable in the future.
>
> In particular, `OP_SHA256STREAM` would no longer be useable if SHA256
> eventually is broken, while the `OP_CAT` will still be useable in the
> indefinite future.
> In the future a new hash function can simply be defined and the same
> technique with `OP_CAT` would still be useable.
>
>
> Regards,
> ZmnSCPxj
>
> > --
> > @JeremyRubin
> >
> > On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman  wrote:
> >
> > > 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 
> 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 

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Peter Todd via bitcoin-dev]

On Thu, Oct 03, 2019 at 10:02:14PM -0700, Jeremy via bitcoin-dev wrote:
> Awhile back, Ethan and I discussed having, rather than OP_CAT, an
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
> function to allow concatenation of an unlimited amount of data, provided
> the only use is to hash it.
> 
> You can then use it perhaps as follows:
> 
> // start a new hash with item
> OP_SHA256STREAM  (-1) -> [state]
> // Add item to the hash in state
> OP_SHA256STREAM n [item] [state] -> [state]
> // Finalize
> OP_SHA256STREAM (-2) [state] -> [Hash]
> 
> <-1> OP_SHA256STREAM<3> OP_SHA256STREAM <-2>
> OP_SHA256STREAM

One issue with this is the simplest implementation where the state is just raw
bytes would expose raw SHA256 midstates, allowing people to use them directly;
preventing that would require adding types to the stack. Specifically I could
write a script that rather than initializing the state correctly from the
official IV, instead takes an untrusted state as input.

SHA256 isn't designed to be used in situations where adversaries control the
initialization vector. I personally don't know one way or the other if anyone
has analyzed this in detail, but I'd be surprised if that's secure. I
considered adding midstate support to OpenTimestamps but decided against it for
exactly that reason.

I don't have the link handy but there's even an example of an experienced
cryptographer on this very list (bitcoin-dev) proposing a design that falls
victim to this attack. It's a subtle issue and we probably don't want to
encourage it.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org


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

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj via bitcoin-dev]

Good morning Jeremy,

> Awhile back, Ethan and I discussed having, rather than OP_CAT, an 
> OP_SHA256STREAM that uses the streaming properties of a SHA256 hash function 
> to allow concatenation of an unlimited amount of data, provided the only use 
> is to hash it.
>
> You can then use it perhaps as follows:
>
> // start a new hash with item
> OP_SHA256STREAM  (-1) -> [state]
> // Add item to the hash in state
> OP_SHA256STREAM n [item] [state] -> [state]
> // Finalize
> OP_SHA256STREAM (-2) [state] -> [Hash]
>
> <-1> OP_SHA256STREAM<3> OP_SHA256STREAM <-2> 
> OP_SHA256STREAM
>
> Or it coul
>

This seems a good idea.

Though it brings up the age-old tension between:

* Generically-useable components, but due to generalization are less efficient.
* Specific-use components, which are efficient, but which may end up not being 
useable in the future.

In particular, `OP_SHA256STREAM` would no longer be useable if SHA256 
eventually is broken, while the `OP_CAT` will still be useable in the 
indefinite future.
In the future a new hash function can simply be defined and the same technique 
with `OP_CAT` would still be useable.


Regards,
ZmnSCPxj

> --
> @JeremyRubin
>
> On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman  wrote:
>
> > 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  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:
> > > > >
> > 

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Jeremy via bitcoin-dev]

Awhile back, Ethan and I discussed having, rather than OP_CAT, an
OP_SHA256STREAM that uses the streaming properties of a SHA256 hash
function to allow concatenation of an unlimited amount of data, provided
the only use is to hash it.

You can then use it perhaps as follows:

// start a new hash with item
OP_SHA256STREAM  (-1) -> [state]
// Add item to the hash in state
OP_SHA256STREAM n [item] [state] -> [state]
// Finalize
OP_SHA256STREAM (-2) [state] -> [Hash]

<-1> OP_SHA256STREAM<3> OP_SHA256STREAM <-2>
OP_SHA256STREAM


Or it coul



--
@JeremyRubin 



On Thu, Oct 3, 2019 at 8:04 PM Ethan Heilman  wrote:

> 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  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
> 

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[Ethan Heilman via bitcoin-dev]

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  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:
> > >
> > >   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 

Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

[ZmnSCPxj via bitcoin-dev]

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:
> >
> >   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:
> >
> >  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
> >