From: Peter Todd <pete@petertodd•org>
To: ZmnSCPxj <ZmnSCPxj@protonmail•com>
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, 6 Oct 2019 05:12:21 -0400 [thread overview]
Message-ID: <20191006091221.pq4utwocwwzqir3h@petertodd.org> (raw)
In-Reply-To: <g0JWqeAd0tg8PbmrwuBRz7VP9h_-63H11oMxWzS8pQE7-awPkLlzSGmhVANp2ssbo19KJU_waNUg846YFbvh0WVSejnOMSoVo-eDl-aytpg=@protonmail.com>
[-- Attachment #1: Type: text/plain, Size: 1737 bytes --]
On Sun, Oct 06, 2019 at 08:46:59AM +0000, 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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
next prev parent reply other threads:[~2019-10-06 9:12 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-09-30 13:23 [bitcoin-dev] " 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
2019-10-06 9:12 ` Peter Todd [this message]
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=20191006091221.pq4utwocwwzqir3h@petertodd.org \
--to=pete@petertodd$(echo .)org \
--cc=ZmnSCPxj@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=lightning-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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