[bitcoindev] BIP54: On fixing time-warp and the (unsoundness) of the forward block idea

[Antoine Riard <antoine.riard@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 7993 bytes --]

Hi devs,

In the process of moving BIP54 past the finish line, as
proposed in one of my previous email [0], I've been through
back the old "forward blocks" idea, as during the design
in the process of BIP54, it was objected that fixing the time-warp
bug would even prevent deployment of a similar-idea to "forward
block" for the rest of bitcoin history.

After reading and looking back on the paper, and as it did  observe
when the objection was made, in my understanding of the "forward block"
idea, I don't think the objection really technically hold, as implementing
a side "forward-chain" still sounds possible, after a BIP54 activation.
Beyond, after musing about the paper again, I think the forward block idea,
with the burden of processing transactions twice is not sound in matters
of cryptoeconomic analysis (unless pay fees twice for the same tx).

Let's explain again the "forward block" idea [2], where it's
basically introducing another chain, the "forward chain" which
would be used as a novel transaction ordering mechanism. The blocks
on the new "forward chain" would be periodically committed on
the compatibility chain until some depth N is reached. Once this
depth is reached, the "forward-chain" cannot be reorged without
a reorg of the compatibility chain.

Once transactions in forward blocks with N or more known confirmations
are added to a novel transaction queue, that is shared between both
the forward chain and the compatibility chain. To avoid the forward
chain to outgrow the processing capacity of the old compatibility chain
nodes, if the transaction queue is full, the time on the compatibility
chain is slowing down to lower the difficulty at the next adjustment, and
therefore allow an outburst of compatibility blocks to catch up with
the forward chain, using the base MTP mechanism as a scalability constraint.

This would be still possible to introduce a mechanism similar to
"forward block" in the future, though in a drastically less efficient
way, that would undermine the efficiency gain brought by the solution,
under its proposed set of assumptions.

Indeed, the main intuition on which rely the "forward block" is to use
the adjustment malleability afforded by the existence of the time-warp
bug to allow more blocks to fit in based on the congestion of a transaction
queue. The point is this adjustment malleability is not removed after
BIP54, it is only more constrained by the new rule to increase the hardness
for a miner to do a time-warp attack, as the latest block in a 2016
period _must_ now have a timestamp equal or superior to the penultimate
block (minus a 7200 seconds window).

After the enforcement of a new rule, the last block can be still within
this window of 7200 seconds, so the equivalent of 12 block expected time,
and leverage this window malleability to lower the difficulty by a rough
0.60% and therefore get a corresponding block rate increase of 0.60%, for
a roughly equivalence in capacity increase.

It should be noted that this "forward block" proposal assume that newer
transactions in forward block might abide by newer consensensus rules,
which will it maintain visibility of all transactions for the old nodes,
it doesn't guarantee that old nodes will meaningfully validate
such new transactions (apart from the characteristic, like not creating
new coins).

Going one step further, if this assumption is made, all the transactions
data coming from the forward chain can be compressed to some kind of zero
-knowledge proof, and only those proofs would be included in the
compatibility
chain, therefore increasing the processing capacity. The intuition reversal
being that instead of compressing time to allow constant data to be process
faster, keep the time constant and compress the data to be processed, it's
just a different time-space trade-off.

Anyway, when one zooms out, the "forward block" proposal does not seem
to hold its validation cost objectives, as non-upgraded nodes still have
to consume more bandwidth and disk space to process all the transactions
coming from the "forward chain". Those bandwidth increases are more likely
to hurt the network decentralization (there is no magic, the 3584x of
capacity
increase still has to be paid bandwidth-wise, one compatibility block every
167 ms is not realistic in face of high-latency network-links or
adversarial
slow-to-validate blocks).

Moreover, there is a bunch of uncertainty about the security model of the
"forward chain" model in itself, as it makes the assumption to increase the
block reward on the "forward chain" at the detriment of the miners on the
compatibility chain, while still making the security finality of the forward
chain relying on the old compatibility chain. Said differently, with this
proposal two set of network validators would have to re-do the same
processing
work twice (once when a transaction is included in a forward block, a second
time when it's included in a compatibility block), while still being having
to share the same *fee reward* (unless the fees are paid twice by the
users).

In a nutshell, and I'm not sure it has been underscored enough in the
previous
discussion about the "forward block" idea, the loosely coupled process of
state synchronization means in fine that the chain validators have to work
in double, or at least a subset of this work in double, the first time when
the state is generated (i.e on the "forward chain") and the second time when
the state is synchronized on the compatibility chain, for still the same
*reward*.

As a conclusion, the fundamental problem with the "forward block" idea is
we're
gaining capacity increase at the price of a significant increase in the
validation
cost of the average transaction (all transaction cost has to be increased
by the
necessity of the cross-chain state synchronization) for the network of
validators
(and as there is no minimal fee, in the worst-case the capacity increase
can be
used as massive denial-of-service garbage for the nodes, it's not because
the
capacity has increased, as there is always guaranteed demand to
*compensate* for
the processing cost of this capacity). [3]

On this analysis, I'll go to propose to add a short footnote on the BIP54
document,
explaining why the "forward block" idea is not reasonable secure enough for
the
bitcoin network and why, in light of the trade-off, it is reasonable to
diminish
the time-warp vulnerability surface, with a proposed mitigation (I'll email
maaku
if he has counter-arguments to this analysis to have a balanced viewpoint
in this
overall BIP54 process).

Minding, all of that the "forward block" paper is still scientifically
interesting,
at least in my opinion, on all the theoretical consensus techniques exposed
and
discussed, and some mechanisms could be interesting to secure the finality
of the
chain in a PQ world, though I guess that's conversation that will be for
another
email.

Cheers,
Antoine
OTS hash: d85c04956cffb941efdb5d026ce0ed327728eac9e46e0218a7fc37c35c456c32

[0] https://groups.google.com/g/bitcoindev/c/TBBakeBK8_E
[1] https://groups.google.com/g/bitcoindev/c/CAfm7D5ppjo/m/Jiurx8AiAgAJ
[2] https://freico.in/forward-blocks-scalingbitcoin-paper.pdf
[3] Of course, this increased denial-of-service surface can be fixed in
theory by
ensuring there is always a "minimal fees reward for stages of capacity
increase"
kind of proportionality rule, though it won't remove the *quasi-double
validation
cost* being introduced due to the loose state coupling and as such the
*entry cost*
for the marginal validation node, being an upgraded or non-upgraded one.

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CALZpt%2BEL_JwYP7iFFWCeVihVV5in7aBOVSc9WcEP6A%2BDYUALzQ%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 9447 bytes --]