Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (1.0)
From: Eric Voskuil <eric@voskuil.org>
In-Reply-To: <6F2B3EA2-4245-4A0E-8E19-12D02A871815@xbt.hk>
Date: Thu, 17 Nov 2016 22:20:52 -0500
Content-Transfer-Encoding: quoted-printable
Message-Id: <11B3C69E-5F1B-4D25-86CE-E5F3B603266F@voskuil.org>
References: <CABm2gDr2-MCiaFFjgUFP5Xc0fQfuqJ3=ZkrzjHqmOiwRZ50CBw@mail.gmail.com>
	<d58ee114-00fd-23c8-9ca7-9a4b28c26f27@voskuil.org>
	<CAE-z3OX5vak25UWcmBSe63OmoOVoGB394WmwyWwUcSxWeDOLhw@mail.gmail.com>
	<e0e6679f-aec6-a579-667d-b5b58ea2360b@voskuil.org>
	<CAE-z3OXfJa3Lewtrafm25bdfPa=eiarOAXBNbgc3ccTi7Qoe6A@mail.gmail.com>
	<5ef23296-5909-a350-ab11-e717f8fffc41@voskuil.org>
	<CAPWm=eW9X77+qQZGHkAOjN-k7KFwq06gKS6HOVOTE1+SmYBhWA@mail.gmail.com>
	<34949746-c0c9-7f14-0e92-69d5a7d44b04@voskuil.org>
	<FA128F93-7E79-47FE-8270-225D07DD6FEF@xbt.hk>
	<8d92ae05-ac6a-30b7-5ef3-f7aa1298e46d@voskuil.org>
	<632B36D5-74AF-41E2-8E21-359F02645066@xbt.hk>
	<59D27CC6-120C-4673-9F20-6B5E95EA60C6@voskuil.org>
	<6F2B3EA2-4245-4A0E-8E19-12D02A871815@xbt.hk>
To: Johnson Lau <jl2012@xbt.hk>
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP30 and BIP34 interaction (was Re: [BIP
	Proposal] Buried Deployments)
Precedence: list

You are suggesting that, since a node implements a denial of service policy t=
hat actually denies itself otherwise valid blocks, those blocks are conditio=
nally invalid. And that, since the validity condition is based on order of a=
rrival and therefore independently unverifiable, Bitcoin consensus is broken=
 in the face of a hash collision.

I am aware of two other hash collision scenarios that cause Core to declare b=
locks invalid based on ordering. The block hash duplicate check (it's not fo=
rk-point relative) and signature verification caching. Like the "block banni=
ng" issue above, the latter is related to an internal optimization. I would c=
ategorize the former as a simple oversight that presumably goes way back.

What then is the consequence of validity that is unverifiable? You believe t=
his means that Bitcoin consensus is broken. This is incorrect. First underst=
and that it is not possible for consensus rules to invalidate blocks based o=
n order of arrival. As such any *implementation* that invalidates blocks bas=
ed on order of arrival is broken. It is an error to claim that these behavio=
rs are part of consensus, despite being implemented in the satoshi node(s).

Validity must be verifiable independent of the state of other nodes. Consens=
us is a function of block history and time alone. Time is presumed to be uni=
versally consistent. To be a consensus rule all nodes must be able to indepe=
ndently reach the same validity conclusion, given the same set of blocks, in=
dependent of order. If this is not the case the behavior is not a consensus r=
ule, it is simply a bug.=20

Deviating from such bugs is not a break with consensus, since such non-rules=
 cannot be part of consensus. One node implementation can behave determinist=
ically while others are behaving non-deterministically, with the two nodes r=
emaining consistent from a consensus standpoint (deterministic produces a su=
bset of non-deterministic results). But, unlike arbitrary nodes, determinist=
ic nodes will not cause disruption on the network.

You imply that these determinism bugs are necessary, that there is no fix. T=
his is also incorrect.

The block banning hash collision bug is avoided by not using non-chain/clock=
 state to determine validity. Doing otherwise is clearly a bug. The hash of a=
 block is not the block itself, a logically-correct ban would be to compare t=
he wire serialization of the block as opposed to the hash, or not maintain t=
he feature at all.

The signature verification caching hash collision bug is the same problem, a=
n optimization based on an invalid assumption. A full serialization comparis=
on (true identity), or elimination of the feature resolves the  bug.

The block hash check collision bug is trivially resolved by checking at the f=
ork point as opposed to the tip. This prevents arbitrary (and irrational) in=
validity based on conflict with irrelevant blocks that may or may not exist a=
bove the fork point.

Libbitcoin is deterministic in all three cases (although the third issue is n=
ot made consistent until v3). I am not aware of any other non-determinism in=
 Core, but I don't spend a lot of time there. There is no need to study othe=
r implementations to ensure determinism, as that can be verified independent=
ly.

Any situation in which a node cannot provide deterministic validation of uno=
rdered blocks constitutes a non-consensus bug, as the behavior is not consis=
tently verifiable by others under any conditions. Fixing/preventing these bu=
gs is responsible development behavior, and does not require forks or BIPs, s=
ince Bitcoin doesn't inherently contain any such bugs. They are the conseque=
nce of incorrect implementation, and in two of the three cases above have re=
sulted from supposed optimizations. But any code that creates non-determinis=
m in exchange for speed, etc. is not an optimization, it's a bug. A node mus=
t implement its optimizations in a manner that does not alter consensus.

The BIP30 regression hard fork is not a case of non-determinism. This will p=
roduce deterministic results (apart from the impact of unrelated bugs). Howe=
ver the results are both a clear break from previous (and documented) consen=
sus but also produce a very undesirable outcome - destruction of all unspent=
 outputs in the "replaced" transaction for starters. So this is a distinct c=
ategory, not a determinism bug but a hard fork that produces undesired conse=
quences.

The BIP30 regression hard fork actually enables the various pathological sce=
narios that you were describing, where no such issues existed in Bitcoin con=
sensus previously. It is now possible to produce a block that mutates anothe=
r arbitrarily deep block, and forces a reorg all the way back to the mutated=
 block. This was done to save microseconds per block. Despite the improbabil=
ity of hash collisions, I find this deplorable and the lack of public discus=
sion on the decision concerning.

With respect to the original post, the point at issue is the introduction of=
 another hard fork, with some odd behaviors, but without any justification a=
part from tidying up the small amount of necessary code. These issues are re=
lated in that they are both consensus forks that have been introduced as sup=
posed optimizations, with no public discussion prior to release (or at least=
 merging to master with the presumption of shipping in the latter case). Two=
 of the three hash collision issues above are also related in that they are b=
ugs introduced by a desire to optimize internals.

The engineering lesson here should be clear - watch out for developers beari=
ng optimizations. A trade against correctness is not an optimization, it's a=
 break. Satoshi was clearly a fan of the premature optimization. FindAndDele=
te is a howler. So this is a tradition in Bitcoin. My intent is not to sling=
 mud but to improve the situation.

It is very possible to produce straightforward and deterministic code that a=
bides consensus and materially outperforms Core, without any of the above op=
timization breaks, even avoiding the utxo set optimization. Even the tx (mem=
ory) and block (orphan) pools are complex store denormalizations implemented=
 as optimizations. Optimizing before producing a clean conceptual model arch=
itecture and design is a software development anti-pattern (premature optimi=
zation). The proposed fork is a premature optimization. There are much more s=
ignificant opportunities to better organize code (and improve performance). I=
 cannot support the decision to advance it.

I was unaware Core had regressed BIP30. Given that the behavior is catastrop=
hic and that it introduces the *only* hash-collision consensus misbehavior (=
unless we consider a deep reorg sans the otherwise necessary proof of work d=
esirable behavior), I strongly recommend it be reverted, with a post-mortem B=
IP.

Finally I recommend people contemplate the difference between unlikely and i=
mpossible. The chance of random collision is very small, but not zero. Colli=
ding hashes is extremely difficult, but not impossible. But Bitcoin does not=
 rely on impossibility for correct behavior. It relies of difficulty. This i=
s a subtle but important distinction that people are missing.

Difficulty is a knowable quantity - a function of computing power.  If hash o=
perations remain difficult, Bitcoin is undeterred. Collisions will have no i=
mpact, even if they happen with unexpected frequency (which would still be v=
anishingly infrequent). If the difficulty of producing a collision is reduce=
d to the point where people cannot rely on addresses (for example), then Bit=
coin has a problem, as it has become a leaky ship (and then there's mining).=
 But with the unnecessary problems described above, a single hash collision c=
an be catastrophic. Unlike difficulty, which is known, nobody can know when a=
 single collision will show up. Betting Bitcoin, and potentially the world's=
 money, on the unknowable is poor reasoning, especially given that the cost o=
f not doing so is so very low.

e

> On Nov 17, 2016, at 10:08 AM, Johnson Lau <jl2012@xbt.hk> wrote:
>=20
> The fact that some implementations ban an invalid block hash and some do n=
ot, suggests that it=E2=80=99s not a pure p2p protocol issue. A pure p2p spl=
it should be unified by a bridge node. However, a bridge node is not helpful=
 in this case. Banning an invalid block hash is an implicit =E2=80=9Cfirst s=
een=E2=80=9D consensus rule.
>=20
> jl2012
>=20
>> On 18 Nov 2016, at 01:49, Eric Voskuil <eric@voskuil.org> wrote:
>>=20
>> Actually both possibilities were specifically covered in my description. S=
orry if it wasn't clear.
>>=20
>> If you create a new valid block out of an old one it's has potential to c=
ause a reorg. The blocks that previously built on the original are still abl=
e to do so but presumably cannot build forever on the *new* block as it has a=
 different tx. But other new blocks can. There is no chain split due to a di=
fferent interpretation of valid, there are simply two valid competing chains=
.
>>=20
>> Note that this scenario requires not only block and tx validity with a tx=
 hash collision, but also that the tx be valid within the block. Pretty far t=
o reach to not even get a chain split, but it could produce a deep reorg wit=
h a very low chance of success. As I keep telling people, deep reorgs can ha=
ppen, they are just unlikely, as is this scenario.
>>=20
>> If you create a new invalid block it is discarded by everyone. That does n=
ot invalidate the hash of that block. Permanent blocking as you describe it w=
ould be a p2p protocol design choice, having nothing to do with consensus. L=
ibbitcoin for example does not ban invalidated hashes at all. It just discar=
ds the block and drops the peer.
>>=20
>> e
>=20
>=20