Re: [bitcoindev] Re: Great Consensus Cleanup Revival

[Eric Voskuil <eric@voskuil.org>]

[-- Attachment #1.1: Type: text/plain, Size: 15974 bytes --]

Hi Antoine R,

>> Ok, thanks for clarifying. I'm still not making the connection to 
"checking a non-null [C] pointer" but that's prob on me.

> A C pointer, which is a language idiome assigning to a memory address A 
the value o memory address B can be 0 (or NULL a standard macro defined in 
stddef.h).
> Here a snippet example of linked list code checking the pointer 
(`*begin_list`) is non null before the comparison operation to find the 
target element list.
> ...
> While both libbitcoin and bitcoin core are both written in c++, you still 
have underlying pointer derefencing playing out to access the coinbase 
transaction, and all underlying implications in terms of memory management.

I'm familiar with pointers ;).

While at some level the block message buffer would generally be referenced 
by one or more C pointers, the difference between a valid coinbase input 
(i.e. with a "null point") and any other input, is not nullptr vs. 
!nullptr. A "null point" is a 36 byte value, 32 0x00 byes followed by 4 
0xff bytes. In his infinite wisdom Satoshi decided it was better (or 
easier) to serialize a first block tx (coinbase) with an input containing 
an unusable script and pointing to an invalid [tx:index] tuple (input 
point) as opposed to just not having any input. That invalid input point is 
called a "null point", and of course cannot be pointed to by a "null 
pointer". The coinbase must be identified by comparing those 36 bytes to 
the well-known null point value (and if this does not match the Merkle hash 
cannot have been type64 malleated).

> I think it's interesting to point out the two types of malleation that a 
bitcoin consensus validation logic should respect w.r.t block validity 
checks. Like you said the first one on the merkle root committed in the 
headers's `hashMerkleRoot` due to the lack of domain separation between 
leaf and merkle tree nodes.

We call this type64 malleability (or malleation where it is not only 
possible but occurs).

> The second one is the bip141 wtxid commitment in one of the coinbase 
transaction `scriptpubkey` output, which is itself covered by a txid in the 
merkle tree.

While symmetry seems to imply that the witness commitment would be 
malleable, just as the txs commitment, this is not the case. If the tx 
commitment is correct it is computationally infeasible for the witness 
commitment to be malleated, as the witness commitment incorporates each 
full tx (with witness, sentinel, and marker). As such the block identifier, 
which relies only on the header and tx commitment, is a sufficient 
identifier. Yet it remains necessary to validate the witness commitment to 
ensure that the correct witness data has been provided in the block message.

The second type of malleability, in addition to type64, is what we call 
type32. This is the consequence of duplicated trailing sets of txs (and 
therefore tx hashes) in a block message. This is applicable to some but not 
all blocks, as a function of the number of txs contained.

>> Caching identity in the case of invalidity is more interesting question 
than it might seem.
>> Background: A fully-validated block has established identity in its 
block hash. However an invalid block message may include the same block 
header, producing the same hash, but with any kind of nonsense following 
the header. The purpose of the transaction and witness commitments is of 
course to establish this identity, so these two checks are therefore 
necessary even under checkpoint/milestone. And then of course the two 
Merkle tree issues complicate the tx commitment (the integrity of the 
witness commitment is assured by that of the tx commitment).
>>
>> So what does it mean to speak of a block hash derived from:
>> (1) a block message with an unparseable header?
>> (2) a block message with parseable but invalid header?
>> (3) a block message with valid header but unparseable tx data?
>> (4) a block message with valid header but parseable invalid uncommitted 
tx data?
>> (5) a block message with valid header but parseable invalid malleated 
committed tx data?
>> (6) a block message with valid header but parseable invalid unmalleated 
committed tx data?
>> (7) a block message with valid header but uncommitted valid tx data?
>> (8) a block message with valid header but malleated committed valid tx 
data?
>> (9) a block message with valid header but unmalleated committed valid tx 
data?
>>
>> Note that only the #9 p2p block message contains an actual Bitcoin 
block, the others are bogus messages. In all cases the message can be 
sha256 hashed to establish the identity of the *message*. And if one's 
objective is to reject repeating bogus messages, this might be a useful 
strategy. It's already part of the p2p protocol, is orders of magnitude 
cheaper to produce than a Merkle root, and has no identity issues.

> I think I mostly agree with the identity issue as laid out so far, there 
is one caveat to add if you're considering identity caching as the problem 
solved. A validation node might have to consider differently block messages 
processed if they connect on the longest most PoW valid chain for which all 
blocks have been validated. Or alternatively if they have to be added on a 
candidate longest most PoW valid chain.

Certainly an important consideration. We store both types. Once there is a 
stronger candidate header chain we store the headers and proceed to 
obtaining the blocks (if we don't already have them). The blocks are stored 
in the same table; the confirmed vs. candidate indexes simply point to them 
as applicable. It is feasible (and has happened twice) for two blocks to 
share the very same coinbase tx, even with either/all bip30/34/90 active 
(and setting aside future issues here for the sake of simplicity). This 
remains only because two competing branches can have blocks at the same 
height, and bip34 requires only height in the coinbase input script. This 
therefore implies the same transaction but distinct blocks. It is however 
infeasible for one block to exist in multiple distinct chains. In order for 
this to happen two blocks at the same height must have the same coinbase 
(ok), and also the same parent (ok). But this then means that they either 
(1) have distinct identity due to another header property deviation, or (2) 
are the same block with the same parent and are therefore in just one 
chain. So I don't see an actual caveat. I'm not certain if this is the 
ambiguity that you were referring to. If not please feel free to clarify.

>> The concept of Bitcoin block hash as unique identifier for invalid p2p 
block messages is problematic. Apart from the malleation question, what is 
the Bitcoin block hash for a message with unparseable data (#1 and #3)? 
Such messages are trivial to produce and have no block hash.

> For reasons, bitcoin core has the concept of outbound `BLOCK_RELAY` (in 
`src/node/connection_types.h`) where some preferential peering policy is 
applied in matters of block messages download.

We don't do this and I don't see how it would be relevant. If a peer 
provides any invalid message or otherwise violates the protocol it is 
simply dropped.

The "problematic" that I'm referring to is the reliance on the block hash 
as a message identifier, because it does not identify the message and 
cannot be useful in an effectively unlimited number of zero-cost cases.

>> What is the useful identifier for a block with malleated commitments (#5 
and #8) or invalid commitments (#4 and #7) - valid txs or otherwise?

> The block header, as it commits to the transaction identifier tree can be 
useful as much for #4 and #5.

#4 and #5 refer to "uncommitted" and "malleated committed". It may not be 
clear, but "uncommitted" means that the tx commitment is not valid (Merkle 
root doesn't match the header's value) and "malleated committed" means that 
the (matching) commitment cannot be relied upon because the txs represent 
malleation, invalidating the identifier. So neither of these are usable 
identifiers.

> On the bitcoin core side, about #7 the uncommitted valid tx data can be 
already present in the validation cache from mempool acceptance. About #8, 
the malleaed committed valid transactions shall be also committed in the 
merkle root in headers.

It seems you may be referring to "unconfirmed" txs as opposed to 
"uncommitted" txs. This doesn't pertain to tx storage or identifiers. 
Neither #7 nor #8 are usable for the same reasons.

>> This seems reasonable at first glance, but given the list of scenarios 
above, which does it apply to?

>> This seems reasonable at first glance, but given the list of scenarios 
above, which does it apply to? Presumably the invalid header (#2) doesn't 
get this far because of headers-first.
>> That leaves just invalid blocks with useful block hash identifiers (#6). 
In all other cases the message is simply discarded. In this case the 
attempt is to move category #5 into category #6 by prohibiting 64 byte txs.

> Yes, it's moving from the category #5 to the category #6. Note, 
transaction malleability can be a distinct issue than lack of domain 
separation.

I'm making no reference to tx malleability. This concerns only Merkle tree 
(block hash) malleability, the two types described in detail in the paper I 
referenced earlier, here again:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20190225/a27d8837/attachment-0001.pdf

>> The requirement to "avoid re-downloading and re-validating it" is about 
performance, presumably minimizing initial block download/catch-up time. 
There is a > computational cost to producing 64 byte malleations and none 
for any of the other bogus block message categories above, including the 
other form of malleation. > Furthermore, 64 byte malleation has almost zero 
cost to preclude. No hashing and not even true header or tx parsing are 
required. Only a handful of bytes must be read > from the raw message 
before it can be discarded presently.

>> That's actually far cheaper than any of the other scenarios that again, 
have no cost to produce. The other type of malleation requires parsing all 
of the txs in the block and > hashing and comparing some or all of them. In 
other words, if there is an attack scenario, that must be addressed before 
this can be meaningful. In fact all of the other bogus message scenarios 
(with tx data) will remain more expensive to discard than this one.

> In practice on the bitcoin core side, the bogus block message categories 
from #4 to #6 are already mitigated by validation caching for transactions 
that have been received early. While libbitcoin has no mempool (at least in 
earlier versions) transactions buffering can be done by bip152's 
HeadersAndShortIds message.

Again, this has no relation to tx hashes/identifiers. Libbitcoin has a tx 
pool, we just don't store them in RAM (memory).

> About #7 and #8, introducing a domain separation where 64 bytes 
transactions are rejected and making it harder to exploit #7 and #8 
categories of bogus block messages. This is correct that bitcoin core might 
accept valid transaction data before the merkle tree commitment has been 
verified.

I don't follow this. An invalid 64 byte tx consensus rule would definitely 
not make it harder to exploit block message invalidity. In fact it would 
just slow down validation by adding a redundant rule. Furthermore, as I 
have detailed in a previous message, caching invalidity does absolutely 
nothing to increase protection. In fact it makes the situation materially 
worse.

>> The problem arises from trying to optimize dismissal by storing an 
identifier. Just *producing* the identifier is orders of magnitude more 
costly than simply dismissing this > bogus message. I can't imagine why any 
implementation would want to compute and store and retrieve and recompute 
and compare hashes when the alterative is just dismissing the bogus 
messages with no hashing at all.

>> Bogus messages will arrive, they do not even have to be requested. The 
simplest are dealt with by parse failure. What defines a parse is entirely 
subjective. Generally it's
>> "structural" but nothing precludes incorporating a requirement for a 
necessary leading pattern in the stream, sort of like how the witness 
pattern is identified. If we were
>> going to prioritize early dismissal this is where we would put it.

> I don't think this is that simple - While producing an identifier comes 
with a computational cost (e.g fixed 64-byte structured coinbase 
transaction), if the full node have a hierarchy of validation cache like 
bitcoin core has already, the cost of bogus block messages can be slashed 
down.

No, this is not the case. As I detailed in my previous message, there is no 
possible scenario where invalidation caching does anything but make the 
situation materially worse.

> On the other hand, just dealing with parse failure on the spot by 
introducing a leading pattern in the stream just inflates the size of p2p 
messages, and the transaction-relay bandwidth cost.

I think you misunderstood me. I am suggesting no change to serialization. I 
can see how it might be unclear, but I said, "nothing precludes 
incorporating a requirement for a necessary leading pattern in the stream." 
I meant that the parser can simply incorporate the *requirement* that the 
byte stream starts with a null input point. That identifies the malleation 
or invalidity without a single hash operation and while only reading a 
handful of bytes. No change to any messages.

>> However, there is a tradeoff in terms of early dismissal. Looking up 
invalid hashes is a costly tradeoff, which becomes multiplied by every 
block validated. For example, expending 1 millisecond in hash/lookup to 
save 1 second of validation time in the failure case seems like a 
reasonable tradeoff, until you multiply across the whole chain. > 1 ms 
becomes 14 minutes across the chain, just to save a second for each mallied 
block encountered. That means you need to have encountered 840 such mallied 
blocks > just to break even. Early dismissing the block for non-null 
coinbase point (without hashing anything) would be on the order of 1000x 
faster than that (breakeven at 1 > encounter). So why the block hash cache 
requirement? It cannot be applied to many scenarios, and cannot be optimal 
in this one.

> I think what you're describing is more a classic time-space tradeoff 
which is well-known in classic computer science litterature. In my 
reasonable opinion, one should more reason under what is the security 
paradigm we wish for bitcoin block-relay network and perduring 
decentralization, i.e one where it's easy to verify block messages proofs 
which could have been generated on specialized hardware with an asymmetric 
cost. Obviously encountering 840 such malliead blocks to make it break even 
doesn't make the math up to save on hash lookup, unless you can reduce the 
attack scenario in terms of adversaries capabilities.

I'm referring to DoS mitigation (the only relevant security consideration 
here). I'm pointing out that invalidity caching is pointless in all cases, 
and in this case is the most pointless as type64 malleation is the cheapest 
of all invalidity to detect. I would prefer that all bogus blocks sent to 
my node are of this type. The worst types of invalidity detection have no 
mitigation and from a security standpoint are counterproductive to cache. 
I'm describing what overall is actually not a tradeoff. It's all negative 
and no positive.

Best,
Eric

-- 
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 on the web visit https://groups.google.com/d/msgid/bitcoindev/d9834ad5-f803-4a39-a854-95b2439738f5n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 16846 bytes --]