Delivery-date: Tue, 02 Jul 2024 09:13:37 -0700
Sender: bitcoindev@googlegroups.com
Date: Tue, 2 Jul 2024 08:57:39 -0700 (PDT)
From: Eric Voskuil <eric@voskuil.org>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <c8f285b3-bcc4-43f3-b9d8-06fe23ee8303n@googlegroups.com>
In-Reply-To: <wg_er0zMhAF9ERoYXmxI6aB7rc97Cum6PQj4UOELapsHVBBVWktFeOZT7sHDlyrXwJ5o5s9iMb2LW2Od-qacywsh-86p5Q7dP3XjWASXcMw=@protonmail.com>
References: <gnM89sIQ7MhDgI62JciQEGy63DassEv7YZAMhj0IEuIo0EdnafykF6RH4OqjTTHIHsIoZvC2MnTUzJI7EfET4o-UQoD-XAQRDcct994VarE=@protonmail.com>
 <72e83c31-408f-4c13-bff5-bf0789302e23n@googlegroups.com>
 <heKH68GFJr4Zuf6lBozPJrb-StyBJPMNvmZL0xvKFBnBGVA3fVSgTLdWc-_8igYWX8z3zCGvzflH-CsRv0QCJQcfwizNyYXlBJa_Kteb2zg=@protonmail.com>
 <5b0331a5-4e94-465d-a51d-02166e2c1937n@googlegroups.com>
 <yt1O1F7NiVj-WkmnYeta1fSqCYNFx8h6OiJaTBmwhmJ2MWAZkmmjPlUST6FM7t6_-2NwWKdglWh77vcnEKA8swiAnQCZJY2SSCAh4DOKt2I=@protonmail.com>
 <be78e733-6e9f-4f4e-8dc2-67b79ddbf677n@googlegroups.com>
 <jJLDrYTXvTgoslhl1n7Fk9-pL1mMC-0k6gtoniQINmioJpzgtqrJ_WqyFZkLltsCUusnQ4jZ6HbvRC-mGuaUlDi3kcqcFHALd10-JQl-FMY=@protonmail.com>
 <9a4c4151-36ed-425a-a535-aa2837919a04n@googlegroups.com>
 <wg_er0zMhAF9ERoYXmxI6aB7rc97Cum6PQj4UOELapsHVBBVWktFeOZT7sHDlyrXwJ5o5s9iMb2LW2Od-qacywsh-86p5Q7dP3XjWASXcMw=@protonmail.com>
Subject: Re: [bitcoindev] Re: Great Consensus Cleanup Revival
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_91341_1351928154.1719935859194"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_91341_1351928154.1719935859194
Content-Type: multipart/alternative; 
	boundary="----=_Part_91342_507781727.1719935859194"

------=_Part_91342_507781727.1719935859194
Content-Type: text/plain; charset="UTF-8"

>>>> This does not produce unmalleable block hashes. Duplicate tx hash 
malleation remains in either case, to the same effect. Without a resolution 
to both issues this is an empty promise.

>>> Duplicate txids have been invalid since 2012 (CVE-2012-2459).

>> I think again here you may have misunderstood me. I was not making a 
point pertaining to BIP30.

> No, in fact you did. CVE-2012-2459 is unrelated to BIP30, it's the 
duplicate txids malleability found by forrestv in 2012. It's the one you 
are talking about thereafter and the one relevant for the purpose of this 
discussion.

Yes, my mistake. I didn't look up the CVE because malleability has no 
affect on consensus rules (validity). Without BIP30/34/90 a duplicated 
tx/txid (in a given chain) would still be valid (and under the caveats 
previously mentioned, still is). So I assumed you were referring to 
it/them. Malleability pertains strictly to validation implementation 
shortcuts (checkpoints, milestones, invalidity caching), not what is 
actually valid.

>> The proposal does not enable that objective, it is already the case. No 
malleated block is a valid block.

> You are right. The advantage i initially mentioned about how making 
64-bytes transactions invalid could help caching block failures at an 
earlier stage is incorrect.

Hopefully the discussion leads to simpler and more performant 
implementation. As I mentioned previously, the usefulness (i.e. performance 
improving outcome) of block hash invalidity caching is very limited.

Libbitcoin implements an append-only store. And we write a checkpointed, 
milestoned, or current/strong header chains before obtaining blocks. So in 
the case where an invalid block corresponds to a stored header we must 
store the header's invalidity. Obviously this is guarded by PoW and 
therefore extremely rare, but must be accounted for. Otherwise we do not 
under any circumstances store invalidity. This is far more effective than 
storing it, even under heavy/constant "attack".

Given the PoW guard, the worst case scenario is where the witness 
commitment is invalid (it is performed after tx commitment, because it 
relies on the coinbase tx commit). Next worse is where the tx commitment is 
invalid. Neither present any cost to the attacker and neither rely on 
Merkle tree malleability. The latter requires hashing every tx and 
performing the Merkle root calculation. The former requires doing this 
twice. For a block with 4096 txs, that's [2 * (4096 + 4095) = 16382] tx 
hashes.

While that's nothing to sneeze at, in our implementation this constitutes 
1-2% of total sync time on my 7 year old machine (no shani and no avx512). 
But what if we were to cache every invalid hash? Let's say we're under 
constant attack (despite dropping any peer that provides an 
invalid/unrequested block/message). The smart attacker doesn't use 
malleation, since he knows this is mitigated and cheaper in both cases to 
guard against. He just sends block messages with requested headers and a 
maximal set of valid txs (maybe from that actual block) and modifies one 
byte of any witness (or of any script for non-witness blocks). Every time 
sending a unique block, of which he can produce an effectively unlimited 
quantity. With or without caching this requires computation of all 16382 
hashes for each bogus block that includes a requested header (unrequested 
are dismissed at the cost of just one hash).

In this case there is never a cache hit. Each bogus block is unique, but 
"valid enough" to force full double Merkle root computations. Storing the 
cached invalid hash then absorbs additional time and 32 bytes of space plus 
indexation, and achieves nothing. It's as if the hope is that the attacker 
is dumb and just keeps sending the same invalid block. But what's actually 
happening as (1) deoptimization, (2) unnecessary complexity, and (3) 
exposure to a disk-full attack vector which must then also be mitigated.

The other scenarios where parse fails cannot rely on invalidity caching, 
since they don't produce valid commitments, and are dismissed cheaply. That 
leaves only malleability. This comes in two forms, the 64 byte form 
("type64") and what we call "type32" (hashes are 32 bytes and in this form 
they are duplicated). Type64 malleation is the cheapest form of dismissal, 
very early in parse (as discussed). Type32 malleation is far more 
expensive, but no more so than the worst case scenario above. In the Core 
implementation this detection adds a constant (and unnecessarily high) cost 
to the Merkle root computation. This makes it *more* expensive to detect 
than the worst case non-witness scenario above (and its discovery cannot be 
cached). It is possible to reduce this cost significantly by relying on 
some simple math operating over the tx count. So even this scenario is not 
inherently worst case.

So unless one is caching invalidity under PoW and due to an append-only 
store, I can see no reason to ever do it. Getting rid of it would improve 
both performance and security while reducing complexity. Optimally 
dismissing both types of malleation as described would improve performance, 
but is neutral regarding security.

e

-- 
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/c8f285b3-bcc4-43f3-b9d8-06fe23ee8303n%40googlegroups.com.

------=_Part_91342_507781727.1719935859194
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

&gt;&gt;&gt;&gt; This does not produce unmalleable block hashes. Duplicate =
tx hash malleation remains in either case, to the same effect. Without a re=
solution to both issues this is an empty promise.<br /><br />&gt;&gt;&gt; D=
uplicate txids have been invalid since 2012 (CVE-2012-2459).<br /><br />&gt=
;&gt; I think again here you may have misunderstood me. I was not making a =
point pertaining to BIP30.<br /><br />&gt; No, in fact you did. CVE-2012-24=
59 is unrelated to BIP30, it's the duplicate txids malleability found by fo=
rrestv in 2012. It's the one you are talking about thereafter and the one r=
elevant for the purpose of this discussion.<br /><br />Yes, my mistake. I d=
idn't look up the CVE because malleability has no affect on consensus rules=
 (validity). Without BIP30/34/90 a duplicated tx/txid (in a given chain) wo=
uld still be valid (and under the caveats previously mentioned, still is). =
So I assumed you were referring to it/them. Malleability pertains strictly =
to validation implementation shortcuts (checkpoints, milestones, invalidity=
 caching), not what is actually valid.<br /><br />&gt;&gt; The proposal doe=
s not enable that objective, it is already the case. No malleated block is =
a valid block.<br /><br />&gt; You are right. The advantage i initially men=
tioned about how making 64-bytes transactions invalid could help caching bl=
ock failures at an earlier stage is incorrect.<br /><br />Hopefully the dis=
cussion leads to simpler and more performant implementation. As I mentioned=
 previously, the usefulness (i.e. performance improving outcome) of block h=
ash invalidity caching is very limited.<br /><br />Libbitcoin implements an=
 append-only store. And we write a checkpointed, milestoned, or current/str=
ong header chains before obtaining blocks. So in the case where an invalid =
block corresponds to a stored header we must store the header's invalidity.=
 Obviously this is guarded by PoW and therefore extremely rare, but must be=
 accounted for. Otherwise we do not under any circumstances store invalidit=
y. This is far more effective than storing it, even under heavy/constant "a=
ttack".<br /><br />Given the PoW guard, the worst case scenario is where th=
e witness commitment is invalid (it is performed after tx commitment, becau=
se it relies on the coinbase tx commit). Next worse is where the tx commitm=
ent is invalid. Neither present any cost to the attacker and neither rely o=
n Merkle tree malleability. The latter requires hashing every tx and perfor=
ming the Merkle root calculation. The former requires doing this twice. For=
 a block with 4096 txs, that's [2 * (4096 + 4095) =3D 16382] tx hashes.<br =
/><br />While that's nothing to sneeze at, in our implementation this const=
itutes 1-2% of total sync time on my 7 year old machine (no shani and no av=
x512). But what if we were to cache every invalid hash? Let's say we're und=
er constant attack (despite dropping any peer that provides an invalid/unre=
quested block/message). The smart attacker doesn't use malleation, since he=
 knows this is mitigated and cheaper in both cases to guard against. He jus=
t sends block messages with requested headers and a maximal set of valid tx=
s (maybe from that actual block) and modifies one byte of any witness (or o=
f any script for non-witness blocks). Every time sending a unique block, of=
 which he can produce an effectively unlimited quantity. With or without ca=
ching this requires computation of all 16382 hashes for each bogus block th=
at includes a requested header (unrequested are dismissed at the cost of ju=
st one hash).<br /><br />In this case there is never a cache hit. Each bogu=
s block is unique, but "valid enough" to force full double Merkle root comp=
utations. Storing the cached invalid hash then absorbs additional time and =
32 bytes of space plus indexation, and achieves nothing. It's as if the hop=
e is that the attacker is dumb and just keeps sending the same invalid bloc=
k. But what's actually happening as (1) deoptimization, (2) unnecessary com=
plexity, and (3) exposure to a disk-full attack vector which must then also=
 be mitigated.<br /><br />The other scenarios where parse fails cannot rely=
 on invalidity caching, since they don't produce valid commitments, and are=
 dismissed cheaply. That leaves only malleability. This comes in two forms,=
 the 64 byte form ("type64") and what we call "type32" (hashes are 32 bytes=
 and in this form they are duplicated). Type64 malleation is the cheapest f=
orm of dismissal, very early in parse (as discussed). Type32 malleation is =
far more expensive, but no more so than the worst case scenario above. In t=
he Core implementation this detection adds a constant (and unnecessarily hi=
gh) cost to the Merkle root computation. This makes it *more* expensive to =
detect than the worst case non-witness scenario above (and its discovery ca=
nnot be cached). It is possible to reduce this cost significantly by relyin=
g on some simple math operating over the tx count. So even this scenario is=
 not inherently worst case.<br /><br />So unless one is caching invalidity =
under PoW and due to an append-only store, I can see no reason to ever do i=
t. Getting rid of it would improve both performance and security while redu=
cing complexity. Optimally dismissing both types of malleation as described=
 would improve performance, but is neutral regarding security.<br /><br />e=
<br />

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/c8f285b3-bcc4-43f3-b9d8-06fe23ee8303n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/c8f285b3-bcc4-43f3-b9d8-06fe23ee8303n%40googlegroups.com</a>.=
<br />

------=_Part_91342_507781727.1719935859194--

------=_Part_91341_1351928154.1719935859194--