From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 29 Jun 2024 13:42:30 -0700 Received: from mail-yw1-f188.google.com ([209.85.128.188]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sNetx-0006sd-7f for bitcoindev@gnusha.org; Sat, 29 Jun 2024 13:42:30 -0700 Received: by mail-yw1-f188.google.com with SMTP id 00721157ae682-64d2e2aaff0sf2173817b3.2 for ; Sat, 29 Jun 2024 13:42:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1719693743; x=1720298543; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=2nTudNywqu/iU/VvqVmygYWMKnh3m1Pp1+Id1EU8olU=; b=dNwN7kzNHrLs7Vex16MlU+pvQhZhFklcteLMBBcBSGznOEP58Lgs8EouEDodg4/Wlq 7BooBg+LJ2zuMEpvXHDo1fnFOlS3x83jJwcxiyZ5z4JWNspsy6forbk8He2tKnc2zOcN e7vNMjnW0ksHAxrf9u0iLzivWdz15TnjSkgD1r2ejK1kc7ay7XFUCxmsMGVTVmPWjZG/ /1fAyzz+u2Ms9WWiMoOl/8AZwVMehrFQmXQ7nAkTKEqXl9iugA0PfH/liLTk6rGJdD9X yiztvkZnfbUWFIObM6G7vmQLNMPxEzP3QlswFub8BFmM3XO0O2usajw203VUm3BNOGI9 dHHg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1719693743; x=1720298543; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=2nTudNywqu/iU/VvqVmygYWMKnh3m1Pp1+Id1EU8olU=; b=dLz6V/b2+/IWWCLRrDpX+kFcgcdPTlKJAG1uR+79UowaQa+MAlyO1ZqqjdOcmnZxQ8 kNjsb3NpQgILN6GUeKJ/n261MGCjeI/hB2e+99+7CTlzCv2slVdhWrTGqKA5hcPchboe 5XdO+O1J6SuiyjQfHUlW0CReumDglJpSoan+/p7D0sEnpxM7izYFOK/CxmAs1Ils94ja 9VsMf/XuIUa+OAKmxmXMdL1SrsXtVt4UxB9CyBduvGAWuwiTOwQbSBqoxX492EvbzyYM fwiMZZOp51M2+80MM3hqRfeBRVEMvnxqrgIoFLgMA3GlqJv1AruibiXmaSLurS/pEmdp zVVg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1719693743; x=1720298543; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=2nTudNywqu/iU/VvqVmygYWMKnh3m1Pp1+Id1EU8olU=; b=wjmtFnfqI3J8gX84MTnjUpyGjdfs1gkpIV56z81l6R1SlyKzv6jvJxUSb6XP3V4Bzc 09p/agCEul4GiT7W08ADxTDwGoEXkUS5DnxHBAGF9VadvOgLAt11Jzs/nsXL2sBTCHwR yu7hxyjjI+dTogC8ZhqQJAGmfOZN1O5DPJdzxBkIMc6Xyp5/zeE2eNQXha/6YqRNzKwS tcUv8E/bewLP0DXiSINdR2kvVT7n96T048EosGOxypoGqbca6IUjcRe2N6jbab7MqFBh z1881YE3r9SoF5qfEoh/ZlF1C0nAXtE+6HGgmEyiZjRWd6twRJ5lEcQUerfbf6pg7IuZ W4hw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCV1+8RT9AMmZ+vJ2gLHOykkfCcnXjmg+L+6WbKPS4QtsWBzMrxSkozLPF1+NWm3ZbliJeaENW+H9uKFilypT45r878CzD4= X-Gm-Message-State: AOJu0YywMfY+GVbKZ4p3RLCRIWgAy9bArbE3JZa1etRF5LLRtULdLM2W v6nX/ov1LVAgbIvzH5M/IcwvQNPhIXb3mMRuCE8zoipVGRstDO6P X-Google-Smtp-Source: AGHT+IGsGPXprUgIyiwYUdetOPWC3/T65mxFvMfhrpEfB/vX4q3z23gzc5UHK+wOs32wklAzyVSODA== X-Received: by 2002:a25:df50:0:b0:e03:4f45:2ef5 with SMTP id 3f1490d57ef6-e036ec32213mr1803892276.45.1719693742949; Sat, 29 Jun 2024 13:42:22 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:100e:b0:dfa:8028:8bc9 with SMTP id 3f1490d57ef6-e0356251544ls2954120276.1.-pod-prod-06-us; Sat, 29 Jun 2024 13:42:21 -0700 (PDT) X-Received: by 2002:a05:6902:1102:b0:e02:c619:73d with SMTP id 3f1490d57ef6-e036eb1b63dmr85765276.5.1719693741680; Sat, 29 Jun 2024 13:42:21 -0700 (PDT) Received: by 2002:a81:ae02:0:b0:627:7f59:2eee with SMTP id 00721157ae682-64d36134a0ams7b3; Sat, 29 Jun 2024 13:40:40 -0700 (PDT) X-Received: by 2002:a25:b297:0:b0:e02:bd2f:97f5 with SMTP id 3f1490d57ef6-e035c0454fdmr88080276.6.1719693640203; Sat, 29 Jun 2024 13:40:40 -0700 (PDT) Date: Sat, 29 Jun 2024 13:40:39 -0700 (PDT) From: Eric Voskuil To: Bitcoin Development Mailing List Message-Id: <3dceca4d-03a8-44f3-be64-396702247fadn@googlegroups.com> In-Reply-To: <607a2233-ac12-4a80-ae4a-08341b3549b3n@googlegroups.com> References: <72e83c31-408f-4c13-bff5-bf0789302e23n@googlegroups.com> <5b0331a5-4e94-465d-a51d-02166e2c1937n@googlegroups.com> <9a4c4151-36ed-425a-a535-aa2837919a04n@googlegroups.com> <3f0064f9-54bd-46a7-9d9a-c54b99aca7b2n@googlegroups.com> <26b7321b-cc64-44b9-bc95-a4d8feb701e5n@googlegroups.com> <607a2233-ac12-4a80-ae4a-08341b3549b3n@googlegroups.com> Subject: Re: [bitcoindev] Re: Great Consensus Cleanup Revival MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_336776_1807486589.1719693639951" X-Original-Sender: eric@voskuil.org Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.7 (/) ------=_Part_336776_1807486589.1719693639951 Content-Type: multipart/alternative; boundary="----=_Part_336777_264697585.1719693639951" ------=_Part_336777_264697585.1719693639951 Content-Type: text/plain; charset="UTF-8" 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. 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. 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 stated objective for a consensus rule to invalidate all 64 byte txs is: > being able to cache the hash of a (non-malleated) invalid block as permanently invalid to avoid re-downloading and re-validating it. 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. 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. 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. 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. 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/3dceca4d-03a8-44f3-be64-396702247fadn%40googlegroups.com. ------=_Part_336777_264697585.1719693639951 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Caching identity in the case of invalidity is more interesting question tha= n it might seem.

Background: A fully-validated block has establi= shed identity in its block hash. However an invalid block message may inclu= de the same block header, producing the same hash, but with any kind of non= sense following the header. The purpose of the transaction and witness comm= itments is of course to establish this identity, so these two checks are th= erefore necessary even under checkpoint/milestone. And then of course the t= wo Merkle tree issues complicate the tx commitment (the integrity of the wi= tness commitment is assured by that of the tx commitment).

So wh= at does it mean to speak of a block hash derived from:

(1) a blo= ck message with an unparseable header?
(2) a block message with parsea= ble but invalid header?
(3) a block message with valid header but unpa= rseable tx data?
(4) a block message with valid header but parseable i= nvalid uncommitted tx data?
(5) a block message with valid header but = parseable invalid malleated committed tx data?
(6) a block message wit= h 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 t= x data?

Note that only the #9 p2p block message contains an actu= al Bitcoin block, the others are bogus messages. In all cases the message c= an 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 s= trategy. It's already part of the p2p protocol, is orders of magnitude chea= per to produce than a Merkle root, and has no identity issues.

T= he concept of Bitcoin block hash as unique identifier for invalid p2p block= messages is problematic. Apart from the malleation question, what is the B= itcoin block hash for a message with unparseable data (#1 and #3)? Such mes= sages are trivial to produce and have no block hash. What is the useful ide= ntifier for a block with malleated commitments (#5 and #8) or invalid commi= tments (#4 and #7) - valid txs or otherwise?

The stated objectiv= e for a consensus rule to invalidate all 64 byte txs is:

> be= ing able to cache the hash of a (non-malleated) invalid block as permanentl= y invalid to avoid re-downloading and re-validating it.

This see= ms 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 prohib= iting 64 byte txs.

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 a= bove, including the other form of malleation. Furthermore, 64 byte malleati= on 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 f= ar cheaper than any of the other scenarios that again, have no cost to prod= uce. The other type of malleation requires parsing all of the txs in the bl= ock 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 meaningfu= l. In fact all of the other bogus message scenarios (with tx data) will rem= ain more expensive to discard than this one.

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 co= mpute and store and retrieve and recompute and compare hashes when the alte= rative is just dismissing the bogus messages with no hashing at all.
<= br />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 incorporatin= g 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 earl= y dismissal this is where we would put it.

However, there is a t= radeoff in terms of early dismissal. Looking up invalid hashes is a costly = tradeoff, which becomes multiplied by every block validated. For example, e= xpending 1 millisecond in hash/lookup to save 1 second of validation time i= n the failure case seems like a reasonable tradeoff, until you multiply acr= oss 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 e= ncountered 840 such mallied blocks just to break even. Early dismissing the= block for non-null coinbase point (without hashing anything) would be on t= he order of 1000x faster than that (breakeven at 1 encounter). So why the b= lock hash cache requirement? It cannot be applied to many scenarios, and ca= nnot be optimal in this one.

Eric

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg= id/bitcoindev/3dceca4d-03a8-44f3-be64-396702247fadn%40googlegroups.com.=
------=_Part_336777_264697585.1719693639951-- ------=_Part_336776_1807486589.1719693639951--