Delivery-date: Fri, 28 Jun 2024 18:09:24 -0700
Sender: bitcoindev@googlegroups.com
Date: Fri, 28 Jun 2024 18:06:49 -0700 (PDT)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <3f0064f9-54bd-46a7-9d9a-c54b99aca7b2n@googlegroups.com>
In-Reply-To: <9a4c4151-36ed-425a-a535-aa2837919a04n@googlegroups.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>
Subject: Re: [bitcoindev] Re: Great Consensus Cleanup Revival
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_142179_1879354373.1719623209197"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_142179_1879354373.1719623209197
Content-Type: multipart/alternative; 
	boundary="----=_Part_142180_1260340459.1719623209197"

------=_Part_142180_1260340459.1719623209197
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Eric,

> It is not clear to me how determining the coinbase size can be done at an=
=20
earlier stage of validation than
> detection of the non-null coinbase. The former requires parsing the=20
coinbase to determine its size, the latter
> requires parsing it to know if the point is null. Both of these can be=20
performed as early as immediately following the socket read.

If you have code in pure C with variables on the stack no malloc, doing a=
=20
check of the coinbase size after the socket
read can be certainly more robust than checking a non-null pointer. And=20
note the attacking game we're solving is a peer
passing a sequence of malleated blocks for which the headers have been=20
already verified, so there we can only have weaker
assumptions on the computational infeasibility.

Introducing a discontinuity like ensuring that both leaf / non-leaf merkle=
=20
tree nodes are belonging to different domains
can be obviously a source of additional software complexity, however from a=
=20
security perspective discontinuities if they're
computational asymmetries at the advantage of validating nodes I think they=
=20
can be worthy of considerations for soft-fork extensions.

After looking on the proposed implementation in bitcoin inquisition, I=20
think this is correct that the efficiency
of the 64 byte technique transaction to check full block malleability is=20
very implementation dependent. Sadly, I
cannot think about other directions to alleviate this dependence on the=20
ordering of the block validation checks
from socket read.

In my reasonable opinion, it would be more constructive to come out with a=
=20
full-fleshout "fast block malleability
validation" algorithm in the sense of SipHash (-- and see to have this=20
implemented and benchmarked in core) before to
consider more the 64 byte transaction invalidity at the consensus level.

Best,
Antoine (the other one).

Le vendredi 28 juin 2024 =C3=A0 19:49:39 UTC+1, Eric Voskuil a =C3=A9crit :

> >> It is not clear to me how determining the coinbase size can be done at=
=20
> an earlier stage of validation than detection of the non-null coinbase.
> > My point wasn't about checking the coinbase size, it was about being=20
> able to cache the hash of a (non-malleated) invalid block as permanently=
=20
> invalid to avoid re-downloading and re-validating it.
>
> This I understood, but I think you misunderstood me. Your point was=20
> specifically that, "it would let node implementations cache block failure=
s=20
> at an earlier stage of validation." Since you have not addressed that=20
> aspect I assume you agree with my assertion above that the proposed rule=
=20
> does not actually achieve this.
>
> Regarding the question of checking coinbase size, the issue is of=20
> detecting (or preventing) hashes mallied via the 64 byte tx technique. A=
=20
> rule against 64 byte txs would allow this determination by checking the=
=20
> coinbase alone. If the coinbase is 64 bytes the block is invalid, if it i=
s=20
> not the block hash cannot have been mallied (all txs must have been 64=20
> bytes, see previous reference).
>
> In that case if the block is invalid the invalidity can be cached. But=20
> block invalidity cannot actually be cached until the block is fully=20
> validated. A rule to prohibit *all* 64 byte txs is counterproductive as i=
t=20
> only adds additional checks on typically thousands of txs per block,=20
> serving no purpose.
>
> >> It seems to me that introducing an arbitrary tx size validity may=20
> create more potential implementation bugs than it resolves.
> > The potential for implementation bugs is a fair point to raise, but in=
=20
> this case i don't think it's a big concern. Verifying no transaction in a=
=20
> block is 64 bytes is as simple a check as you can get.
>
> You appear to be making the assumption that the check is performed after=
=20
> the block is fully parsed (contrary to your "earlier" criterion above). T=
he=20
> only way to determine the tx sizes is to parse each tx for witness marker=
,=20
> input count, output count, input script sizes, output script sizes, witne=
ss=20
> sizes, and skipping over the header, several constants, and associated=20
> buffers. Doing this "early" to detect malleation is an extraordinarily=20
> complex and costly process. On the other hand, as I pointed out, a ration=
al=20
> implementation would only do this early check for the coinbase.
>
> Yet even determining the size of the coinbase is significantly more=20
> complex and costly than checking its first input point against null. That=
=20
> check (which is already necessary for validation) resolves the malleation=
=20
> question, can be performed on the raw unparsed block buffer by simply=20
> skipping header, version, reading input count and witness marker as=20
> necessary, offsetting to the 36 byte point buffer, and performing a byte=
=20
> comparison against=20
> [0000000000000000000000000000000000000000000000000000000000000000ffffffff=
].
>
> This is:
>
> (1) earlier
> (2) faster
> (3) simpler
> (4) already consensus
>
> >> And certainly anyone implementing such a verifier must know many=20
> intricacies of the protocol.
> > They need to know some, but i don't think it's reasonable to expect the=
m=20
> to realize the merkle tree construction is such that an inner node may be=
=20
> confused with a 64 bytes transaction.
>
> A protocol developer needs to understand that the hash of an invalid bloc=
k=20
> cannot be cached unless at least the coinbase has been restricted in size=
=20
> (under the proposal) -or- that the coinbase is a null point (presently or=
=20
> under the proposal). In the latter case the check is already performed in=
=20
> validation, so there is no way a block would presently be cached as inval=
id=20
> without checking it. The proposal adds a redundant check, even if limited=
=20
> to just the coinbase. [He must also understand the second type of=20
> malleability, discussed below.]
>
> If this proposed rule was to activate we would implement it in a late=20
> stage tx.check, after txs/blocks had been fully deserialized. We would no=
t=20
> check it an all in the case where the block is under checkpoint or=20
> milestone ("assume valid"). In this case we would retain the early null=
=20
> point malleation check (along with the hash duplication malleation check)=
=20
> that we presently have, would validate tx commitments, and commit the=20
> block. In other words, the proposal adds unnecessary late stage checks=20
> only. Implementing it otherwise would just add complexity and hurt=20
> performance.
>
> >> I do not see this. I see a very ugly perpetual seam which will likely=
=20
> result in unexpected complexities over time.
> > What makes you think making 64 bytes transactions invalid could result=
=20
> in unexpected complexities? And why do you think it's likely?
>
> As described above, it's later, slower, more complex, unnecessarily broad=
,=20
> and a consensus change. Beyond that it creates an arbitrary size limit -=
=20
> not a lower or upper bound, but a slice out of the domain. Discontinuitie=
s=20
> are inherent complexities in computing. The "unexpected" part speaks for=
=20
> itself.
>
> >> This does not produce unmalleable block hashes. Duplicate tx hash=20
> malleation remains in either case, to the same effect. Without a resoluti=
on=20
> 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 poin=
t=20
> pertaining to BIP30. I was referring to the other form of block hash=20
> malleability, which results from duplicating sets of trailing txs in a=20
> single block (see previous reference). This malleation vector remains, ev=
en=20
> with invalid 64 byte txs. As I pointed out, this has the "same effect" as=
=20
> the 64 byte tx issue. Merkle hashing the set of txs is insufficient to=20
> determine identity. In one case the coinbase must be checked (null point =
or=20
> size) and in the other case the set of tx hashes must be checked for=20
> trailing duplicated sets. [Core performs this second check within the=20
> Merkle hashing algorithm (with far more comparisons than necessary), thou=
gh=20
> this can be performed earlier and independently to avoid any hashing in t=
he=20
> malleation case.]
>
> I would also point out in the interest of correctness that Core reverted=
=20
> its BIP30 soft fork implementation as a consequence of the BIP90 hard for=
k,=20
> following and requiring the BIP34 soft fork that presumably precluded it=
=20
> but didn't, so it is no longer the case that duplicate tx hashes are=20
> invalid in implementation. As you have proposed in this rollup, this=20
> requires fixing again.
>
> > If 64 bytes transactions are also made invalid, this would make it=20
> impossible for two valid blocks to have the same hash.
>
> Aside from the BIP30/34/90 issue addressed above, it is already=20
> "impossible" (cannot be stronger than computationally infeasible) for two=
=20
> *valid* blocks to have the same hash. The proposal does not enable that=
=20
> objective, it is already the case. No malleated block is a valid block.
>
> The proposal aims only to make it earlier or easier or faster to check fo=
r=20
> block hash malleation. And as I've pointed out above, it doesn't achieve=
=20
> those objectives. Possibly the perception that this would be the case is =
a=20
> consequence of implementation details, but as I have shown above, it is n=
ot=20
> in fact the case.
>
> Given either type of malleation, the malleated block can be determined to=
=20
> be invalid by a context free check. But this knowledge cannot ever be=20
> cached against the block hash, since the same hash may be valid. Invalidi=
ty=20
> can only be cached once a non-mallied block is validated and determined t=
o=20
> be invalid. Block hash malleations are and will remain invalid blocks wit=
h=20
> or without the proposal, and it will continue to be necessary to avoid=20
> caching invalid against the malleation. As you said:
>
> > it was about being able to cache the hash of a (non-malleated) invalid=
=20
> block as permanently invalid to avoid re-downloading and re-validating it=
.
>
> This is already the case, and requires validating the full non-malleated=
=20
> block. Adding a redundant invalidity check doesn't improve this in any wa=
y.
>
> Best,
> Eric

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/=
bitcoindev/3f0064f9-54bd-46a7-9d9a-c54b99aca7b2n%40googlegroups.com.

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

<div>Hi Eric,</div><div><br /></div>&gt; It is not clear to me how determin=
ing the coinbase size can be done at an earlier stage of validation than<br=
 />&gt; detection of the non-null coinbase. The former requires parsing the=
 coinbase to determine its size, the latter<br />&gt; requires parsing it t=
o know if the point is null. Both of these can be performed as early as imm=
ediately following the socket read.<br /><br />If you have code in pure C w=
ith variables on the stack no malloc, doing a check of the coinbase size af=
ter the socket<br />read can be certainly more robust than checking a non-n=
ull pointer. And note the attacking game we're solving is a peer<br />passi=
ng a sequence of malleated blocks for which the headers have been already v=
erified, so there we can only have weaker<br />assumptions on the computati=
onal infeasibility.<br /><br />Introducing a discontinuity like ensuring th=
at both leaf / non-leaf merkle tree nodes are belonging to different domain=
s<br />can be obviously a source of additional software complexity, however=
 from a security perspective discontinuities if they're<br />computational =
asymmetries at the advantage of validating nodes I think they can be worthy=
 of considerations for soft-fork extensions.<br /><br />After looking on th=
e proposed implementation in bitcoin inquisition, I think this is correct t=
hat the efficiency<br />of the 64 byte technique transaction to check full =
block malleability is very implementation dependent. Sadly, I<br />cannot t=
hink about other directions to alleviate this dependence on the ordering of=
 the block validation checks<br />from socket read.<br /><br />In my reason=
able opinion, it would be more constructive to come out with a full-fleshou=
t "fast block malleability<br />validation" algorithm in the sense of SipHa=
sh (-- and see to have this implemented and benchmarked in core) before to<=
br />consider more the 64 byte transaction invalidity at the consensus leve=
l.<div><br /></div><div>Best,</div><div>Antoine (the other one).<br /><br /=
></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">Le=
 vendredi 28 juin 2024 =C3=A0 19:49:39 UTC+1, Eric Voskuil a =C3=A9crit=C2=
=A0:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8=
ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">&gt;&gt;=
 It is not clear to me how determining the coinbase size can be done at an =
earlier stage of validation than detection of the non-null coinbase.<br>&gt=
; My point wasn&#39;t about checking the coinbase size, it was about being =
able to cache the hash of a (non-malleated) invalid block as permanently in=
valid to avoid re-downloading and re-validating it.<br><br>This I understoo=
d, but I think you misunderstood me. Your point was specifically that, &quo=
t;it would let node implementations cache block failures at an earlier stag=
e of validation.&quot; Since you have not addressed that aspect I assume yo=
u agree with my assertion above that the proposed rule does not actually ac=
hieve this.<br><br>Regarding the question of checking coinbase size, the is=
sue is of detecting (or preventing) hashes mallied via the 64 byte tx techn=
ique. A rule against 64 byte txs would allow this determination by checking=
 the coinbase alone. If the coinbase is 64 bytes the block is invalid, if i=
t is not the block hash cannot have been mallied (all txs must have been 64=
 bytes, see previous reference).<br><br>In that case if the block is invali=
d the invalidity can be cached. But block invalidity cannot actually be cac=
hed until the block is fully validated. A rule to prohibit *all* 64 byte tx=
s is counterproductive as it only adds additional checks on typically thous=
ands of txs per block, serving no purpose.<br><br>&gt;&gt; It seems to me t=
hat introducing an arbitrary tx size validity may create more potential imp=
lementation bugs than it resolves.<br>&gt; The potential for implementation=
 bugs is a fair point to raise, but in this case i don&#39;t think it&#39;s=
 a big concern. Verifying no transaction in a block is 64 bytes is as simpl=
e a check as you can get.<br><br>You appear to be making the assumption tha=
t the check is performed after the block is fully parsed (contrary to your =
&quot;earlier&quot; criterion above). The only way to determine the tx size=
s is to parse each tx for witness marker, input count, output count, input =
script sizes, output script sizes, witness sizes, and skipping over the hea=
der, several constants, and associated buffers. Doing this &quot;early&quot=
; to detect malleation is an extraordinarily complex and costly process. On=
 the other hand, as I pointed out, a rational implementation would only do =
this early check for the coinbase.<br><br>Yet even determining the size of =
the coinbase is significantly more complex and costly than checking its fir=
st input point against null. That check (which is already necessary for val=
idation) resolves the malleation question, can be performed on the raw unpa=
rsed block buffer by simply skipping header, version, reading input count a=
nd witness marker as necessary, offsetting to the 36 byte point buffer, and=
 performing a byte comparison against [000000000000000000000000000000000000=
0000000000000000000000000000ffffffff].<br><br>This is:<br><br>(1) earlier<b=
r>(2) faster<br>(3) simpler<br>(4) already consensus<br><br>&gt;&gt; And ce=
rtainly anyone implementing such a verifier must know many intricacies of t=
he protocol.<br>&gt; They need to know some, but i don&#39;t think it&#39;s=
 reasonable to expect them to realize the merkle tree construction is such =
that an inner node may be confused with a 64 bytes transaction.<br><br>A pr=
otocol developer needs to understand that the hash of an invalid block cann=
ot be cached unless at least the coinbase has been restricted in size (unde=
r the proposal) -or- that the coinbase is a null point (presently or under =
the proposal). In the latter case the check is already performed in validat=
ion, so there is no way a block would presently be cached as invalid withou=
t checking it. The proposal adds a redundant check, even if limited to just=
 the coinbase. [He must also understand the second type of malleability, di=
scussed below.]<br><br>If this proposed rule was to activate we would imple=
ment it in a late stage tx.check, after txs/blocks had been fully deseriali=
zed. We would not check it an all in the case where the block is under chec=
kpoint or milestone (&quot;assume valid&quot;). In this case we would retai=
n the early null point malleation check (along with the hash duplication ma=
lleation check) that we presently have, would validate tx commitments, and =
commit the block. In other words, the proposal adds unnecessary late stage =
checks only. Implementing it otherwise would just add complexity and hurt p=
erformance.<br><br>&gt;&gt; I do not see this. I see a very ugly perpetual =
seam which will likely result in unexpected complexities over time.<br>&gt;=
 What makes you think making 64 bytes transactions invalid could result in =
unexpected complexities? And why do you think it&#39;s likely?<br><br>As de=
scribed above, it&#39;s later, slower, more complex, unnecessarily broad, a=
nd a consensus change. Beyond that it creates an arbitrary size limit - not=
 a lower or upper bound, but a slice out of the domain. Discontinuities are=
 inherent complexities in computing. The &quot;unexpected&quot; part speaks=
 for itself.<br><br>&gt;&gt; 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.<br>&gt; Dupli=
cate txids have been invalid since 2012 (CVE-2012-2459).<br><br>I think aga=
in here you may have misunderstood me. I was not making a point pertaining =
to BIP30. I was referring to the other form of block hash malleability, whi=
ch results from duplicating sets of trailing txs in a single block (see pre=
vious reference). This malleation vector remains, even with invalid 64 byte=
 txs. As I pointed out, this has the &quot;same effect&quot; as the 64 byte=
 tx issue. Merkle hashing the set of txs is insufficient to determine ident=
ity. In one case the coinbase must be checked (null point or size) and in t=
he other case the set of tx hashes must be checked for trailing duplicated =
sets. [Core performs this second check within the Merkle hashing algorithm =
(with far more comparisons than necessary), though this can be performed ea=
rlier and independently to avoid any hashing in the malleation case.]<br><b=
r>I would also point out in the interest of correctness that Core reverted =
its BIP30 soft fork implementation as a consequence of the BIP90 hard fork,=
 following and requiring the BIP34 soft fork that presumably precluded it b=
ut didn&#39;t, so it is no longer the case that duplicate tx hashes are inv=
alid in implementation. As you have proposed in this rollup, this requires =
fixing again.<br><br>&gt; If 64 bytes transactions are also made invalid, t=
his would make it impossible for two valid blocks to have the same hash.<br=
><br>Aside from the BIP30/34/90 issue addressed above, it is already &quot;=
impossible&quot; (cannot be stronger than computationally infeasible) for t=
wo *valid* blocks to have the same hash. The proposal does not enable that =
objective, it is already the case. No malleated block is a valid block.<br>=
<br>The proposal aims only to make it earlier or easier or faster to check =
for block hash malleation. And as I&#39;ve pointed out above, it doesn&#39;=
t achieve those objectives. Possibly the perception that this would be the =
case is a consequence of implementation details, but as I have shown above,=
 it is not in fact the case.<br><br>Given either type of malleation, the ma=
lleated block can be determined to be invalid by a context free check. But =
this knowledge cannot ever be cached against the block hash, since the same=
 hash may be valid. Invalidity can only be cached once a non-mallied block =
is validated and determined to be invalid. Block hash malleations are and w=
ill remain invalid blocks with or without the proposal, and it will continu=
e to be necessary to avoid caching invalid against the malleation. As you s=
aid:<br><br>&gt; it was about being able to cache the hash of a (non-mallea=
ted) invalid block as permanently invalid to avoid re-downloading and re-va=
lidating it.<br><br>This is already the case, and requires validating the f=
ull non-malleated block. Adding a redundant invalidity check doesn&#39;t im=
prove this in any way.<br><br>Best,<br>Eric</blockquote></div>

<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/3f0064f9-54bd-46a7-9d9a-c54b99aca7b2n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/3f0064f9-54bd-46a7-9d9a-c54b99aca7b2n%40googlegroups.com</a>.=
<br />

------=_Part_142180_1260340459.1719623209197--

------=_Part_142179_1879354373.1719623209197--