From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
To: Peter Todd <pete@petertodd.org>
Cc: Bitcoin Protocol Discussion
<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: Sun, 06 Oct 2019 08:46:59 +0000 [thread overview]
Message-ID: <g0JWqeAd0tg8PbmrwuBRz7VP9h_-63H11oMxWzS8pQE7-awPkLlzSGmhVANp2ssbo19KJU_waNUg846YFbvh0WVSejnOMSoVo-eDl-aytpg=@protonmail.com> (raw)
In-Reply-To: <20191005154902.ck236q65xha25ore@petertodd.org>
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
> > <hash> 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-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
next prev parent reply other threads:[~2019-10-06 8:47 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
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 [this message]
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='g0JWqeAd0tg8PbmrwuBRz7VP9h_-63H11oMxWzS8pQE7-awPkLlzSGmhVANp2ssbo19KJU_waNUg846YFbvh0WVSejnOMSoVo-eDl-aytpg=@protonmail.com' \
--to=zmnscpxj@protonmail.com \
--cc=bitcoin-dev@lists.linuxfoundation.org \
--cc=lightning-dev@lists.linuxfoundation.org \
--cc=pete@petertodd.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