Re: [bitcoin-dev] maximum block height on transaction

From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: Billy Tetrud <billy.tetrud@gmail•com>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] maximum block height on transaction
Date: Fri, 16 Apr 2021 04:24:28 +0000	[thread overview]
Message-ID: <3mg9xnvKEhrXuQ5QriYQcLKmrhdYpO0hlxyRpJwZJZInyHCtva208PTZlIxglcq4afO8ftTFRBjRfG0ZEVPvIqxMJhHnFYpnPYTo_mp3qA0=@protonmail.com> (raw)
In-Reply-To: <CAGpPWDZHKJ8BvD3TqrvP=5pxbAc0ez-ikJmO6a51WDad1xuLSw@mail.gmail.com>

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 hijack this conversation, but I'm very curious if there's something more to this 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 Bitcoin 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 the mempool, its SCRIPT is not re-evaluated.

If the max-blockheight-constraint is implemented as a SCRIPT opcode, then at each block, every SCRIPT in every transaction in the mempool must be re-evaluated, as the SCRIPT might not reject.
During times of high chain bloat, there will be large numbers of transactions in the mempool, only a tiny fraction will be removed at each block before 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 block 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 is generally approached in practice as most transactions are simple singlesig or `OP_CHECKMULTISIG` affairs).

That is, the mempool assumes that once a SCRIPT accepts, it will always accept 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 that the field has a particular value.
Then the mempool can have a separate index according to `maxtime` fields, where 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 techniques similar to what was used in SegWit, i.e. post-maxtime nodes have to "baby talk" to pre-maxtime nodes and pretend transactions do not have this field, 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" transaction ID that contains the `maxtime` field as well.

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

* 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, quadratic sighash, well-defined extensible outputs) that SegWit provides.
* You can do what you want with a second `nLockTime`d transaction that spends the output anyway.

Indeed, it is helpful to realize *why* `OP_CHECKLOCKTIMEVERIFY` and `OP_CHECKSEQUENCEVERIFY` work the way they are implemented.
They are typically discussed and described as if they were imposing time-based constraints, but the *real* implementation only imposes constraints on `nLockTime` and `nSequence` fields --- the SCRIPT interpreter itself does not look at the block that the transaction is in (because that is not available, as the SCRIPT interpreter is invoked at mempool entry, when the transaction *has* no block it is contained in).
There is instead a separate layer (the entry into the mempool) that implements the *actual* time-based cosntraints, based on the fields and not the SCRIPT 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 inputs (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. 
> >
> > 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=1786.msg22119#msg22119:
> > >
> > > > We can't safely do OP_BLOCKNUMBER.  In the event of a block chain reorg after a segmentation, transactions need to be able to get into the chain in a later block.  The OP_BLOCKNUMBER transaction and all its dependants would become invalid.  This wouldn't be fair to later owners of the coins who weren't involved in the time limited transaction.
> > > >
> > > > nTimeLock does the reverse.  It's an open transaction that can be replaced with new versions until the deadline.  It can't be recorded until it locks.  The highest version when the deadline hits gets recorded.  It could be used, for example, to write an escrow transaction that will automatically permanently lock and go through unless it is revoked before the deadline.  The feature isn't enabled or used yet, but the support is there so it could be implemented later.
> > >
> > > Unfortunately, limiting the maximum block height for a specific transaction would have exactly the same problem as cited above for OP_BLOCKNUMBER.
> > >
> > > 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 height 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