Date: Fri, 16 Apr 2021 04:24:28 +0000
To: Billy Tetrud <billy.tetrud@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <3mg9xnvKEhrXuQ5QriYQcLKmrhdYpO0hlxyRpJwZJZInyHCtva208PTZlIxglcq4afO8ftTFRBjRfG0ZEVPvIqxMJhHnFYpnPYTo_mp3qA0=@protonmail.com>
In-Reply-To: <CAGpPWDZHKJ8BvD3TqrvP=5pxbAc0ez-ikJmO6a51WDad1xuLSw@mail.gmail.com>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
 <CAKzdR-pnvystx5H+P+OCXm73aVmWdyesCymerSgx=pCuXx+YGA@mail.gmail.com>
 <9FD4AF03-28A5-4B8A-9C12-CBCB1BC2E22C@friedenbach.org>
 <CAKzdR-r6u4J+_T5X516A=-tLWZ8zFFFsRokReiJndDE_S64OqQ@mail.gmail.com>
 <CAPg+sBi+WnzpJkcG6XACdpqqz9ZA3rHX8+H9b5eExUdgXaeiWQ@mail.gmail.com>
 <CAJowKg+kbnExgKt7H8GD6Kc-iLJEOvZhtw0uVbophhLCszvOHg@mail.gmail.com>
 <CAMZUoKmQyV67dhWS_+t1CmqNYT490_7g3WwKgxB-jiYfje+F+Q@mail.gmail.com>
 <CAD5xwhhZpQ9AQEFHgGYvPh2ad9HyQqq9WwEZje1H1siioB6eLQ@mail.gmail.com>
 <CAGpPWDZHKJ8BvD3TqrvP=5pxbAc0ez-ikJmO6a51WDad1xuLSw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] maximum block height on transaction
Precedence: list

Good morning Billy,


> I've come across this argument before, and it seems kind of like Satoshi'=
s word here is held as gospel. I haven't heard any deep discussion of this =
topic, and I even asked a question on the bitcoin SE about it. Sorry to hij=
ack this conversation, but I'm very curious if there's something more to th=
is or if the thinking was simply decided that OP_BLOCKNUMBER wasn't useful =
enough to warrant the (dubious) potential footgun of people accepting sub-6=
-block transactions from a transaction that uses an expired spend-path?

Another argument I have encountered has to do with the implementation of Bi=
tcoin Core.

As an optimization, SCRIPT is evaluated only when a transaction enters the =
mempool.
It is not evaluated at any other time.
Indeed, when accepting a new block, if a transaction in that block is in th=
e mempool, its SCRIPT is not re-evaluated.

If the max-blockheight-constraint is implemented as a SCRIPT opcode, then a=
t each block, every SCRIPT in every transaction in the mempool must be re-e=
valuated, as the SCRIPT might not reject.
During times of high chain bloat, there will be large numbers of transactio=
ns in the mempool, only a tiny fraction will be removed at each block befor=
e the mempool finally clears, leading to effective O(n^2) CPU time spent (n=
 blocks are needed in order to empty a mempool with n transactions, each bl=
ock triggers re-evaluation of SCRIPT of n transactions in the mempool).
That O(n^2) assumes a single SCRIPT is O(1), which is untrue as well (but i=
s generally approached in practice as most transactions are simple singlesi=
g or `OP_CHECKMULTISIG` affairs).

That is, the mempool assumes that once a SCRIPT accepts, it will always acc=
ept in the future.
Thus, any SCRIPT opcode cannot change from "accept" (because at the current=
 blockheight the max-block is not yet reached) to "reject" (because the max=
-block constraint is now violated).

Thus, we cannot use an opcode to impose the max-block cosntraint.

The alternative is to add a new field `maxtime` to the transaction.
Then possibly, we can have an `OP_CHECKMAXTIMEVERIFY` opcode that checks th=
at the field has a particular value.
Then the mempool can have a separate index according to `maxtime` fields, w=
here it can remove the indexed transactions at each block.
The index will be likely O(log n), and the filtering at each block would be=
 O(n log n), which is an improvement.
Note in particular that the index itself would require O(n) storage.

However, adding a new field to the transaction format would require techniq=
ues similar to what was used in SegWit, i.e. post-maxtime nodes have to "ba=
by talk" to pre-maxtime nodes and pretend transactions do not have this fie=
ld, in much the same way post-SegWit nodes "baby talk" to pre-SegWit nodes =
and pretend transactions do not have a `witness` field.
We would then need a third Merkle Tree to hold the "really real" transactio=
n ID that contains the `maxtime` field as well.

Thus, it seems to me that the tradeoffs are simply not good enough, when yo=
u can get 99% of what you need using just another transaction with `nLockTi=
me`:

* Using an opcode would greatly increase CPU usage because the script cache=
 would need to be reworked (and probably cannot be made to work).
* Adding a field would greatly increase the code complexity to the level of=
 SegWit, without all the important bugfixes+features (tx malleability, quad=
ratic sighash, well-defined extensible outputs) that SegWit provides.
* You can do what you want with a second `nLockTime`d transaction that spen=
ds the output anyway.

Indeed, it is helpful to realize *why* `OP_CHECKLOCKTIMEVERIFY` and `OP_CHE=
CKSEQUENCEVERIFY` work the way they are implemented.
They are typically discussed and described as if they were imposing time-ba=
sed constraints, but the *real* implementation only imposes constraints on =
`nLockTime` and `nSequence` fields --- the SCRIPT interpreter itself does n=
ot look at the block that the transaction is in (because that is not availa=
ble, as the SCRIPT interpreter is invoked at mempool entry, when the transa=
ction *has* no block it is contained in).
There is instead a separate layer (the entry into the mempool) that impleme=
nts the *actual* time-based cosntraints, based on the fields and not the SC=
RIPT opcodes.

Regards,
ZmnSCPxj

>
> On Fri, Apr 9, 2021 at 5:55 AM Jeremy via bitcoin-dev <bitcoin-dev@lists.=
linuxfoundation.org> wrote:
>
> > You could accomplish your rough goal by having:
> >
> > tx A: desired expiry at H
> > tx B: nlocktime H, use same inputs as A, create outputs equivalent to i=
nputs (have to be sure no relative timelocks)
> >
> > Thus after a timeout the participants in A can cancel the action using =
TX B.
> >
> > The difference is the coins have to move, without knowing your use case=
 this may or may not help you.=C2=A0
> >
> > On Fri, Apr 9, 2021, 4:40 AM Russell O'Connor via bitcoin-dev <bitcoin-=
dev@lists.linuxfoundation.org> wrote:
> >
> > > From https://bitcointalk.org/index.php?topic=3D1786.msg22119#msg22119=
:
> > >
> > > > We can't safely do OP_BLOCKNUMBER.=C2=A0 In the event of a block ch=
ain reorg after a segmentation, transactions need to be able to get into th=
e chain in a later block.=C2=A0 The OP_BLOCKNUMBER transaction and all its =
dependants would become invalid.=C2=A0 This wouldn't be fair to later owner=
s of the coins who weren't involved in the time limited transaction.
> > > >
> > > > nTimeLock does the reverse.=C2=A0 It's an open transaction that can=
 be replaced with new versions until the deadline.=C2=A0 It can't be record=
ed until it locks.=C2=A0 The highest version when the deadline hits gets re=
corded.=C2=A0 It could be used, for example, to write an escrow transaction=
 that will automatically permanently lock and go through unless it is revok=
ed before the deadline.=C2=A0 The feature isn't enabled or used yet, but th=
e support is there so it could be implemented later.
> > >
> > > Unfortunately, limiting the maximum block height for a specific trans=
action would have exactly the same problem as cited above for OP_BLOCKNUMBE=
R.
> > >
> > > On Fri, Apr 9, 2021 at 7:21 AM Erik Aronesty via bitcoin-dev <bitcoin=
-dev@lists.linuxfoundation.org> wrote:
> > >
> > > > is there any way to specify a maximum block height on a transaction=
?
> > > >
> > > > ie: this tx is only valid if included in a block with a certain hei=
ght or less
> > > >
> > > > i feel like this would be useful
> > > > _______________________________________________
> > > > 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
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev