From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 02 Jul 2024 09:13:37 -0700 Received: from mail-yb1-f183.google.com ([209.85.219.183]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sOg8O-0006dy-UT for bitcoindev@gnusha.org; Tue, 02 Jul 2024 09:13:37 -0700 Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e039fc8a8e7sf178495276.1 for ; Tue, 02 Jul 2024 09:13:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1719936810; x=1720541610; 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=jEjf9tkTUa/yu7CN/hmDp3JJtJRan6g9f3kMN/OjhnI=; b=Hg11VOUUJiT/ZcDrQ8HVN9ebqGluwtXPVZ9YDOlKIy7cYcY2e2MHeaiwdQSxATE7IX biuZA070dfUbTkJNI0bZVl0HuHCJjTrRydkmvbfOrBMCE6q8h5kqZ0O9isu1QF3DwZnV gGwj3xCxBdff+ooNMKZ92qKkTPfvUKgoTrrSXcjPZLosEvpmbFf5HmctQiH/5paVR3tO BBtn20IIsuwg8Nz9cGgnlpi/emZAZiNbtf6fJOHsyoopqcBoMROEuRpnCqBBXTH1tvOp 55N507krswKfG10EuzSpovGDINrv6vrMWdOJp6Ni6zo74ZtLL7HripgUNXSP8Ra/QaHj EGHw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1719936811; x=1720541611; 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=jEjf9tkTUa/yu7CN/hmDp3JJtJRan6g9f3kMN/OjhnI=; b=Ool1bFhqwXM2jbADXf6FEYpuQHsj5ge8+rqecV/xoXOGuQLjAi2uTZcHvxnDIakIBu bQGNV/RfDqoLgT+asW/KYIxmoyunzuGwTt9ELvABUPm/1s8FJPOCFF7tRjnZJ+XDbOEi qdlW9glSbha865vWqQthpTZH4ae+FCSBF0sZPcCZ6e8uuPnQ/28VCWmynIwrpDBePdQZ pqqfFEQhY2a3TFVLvlklt0XyAiLsj/RExlblKzLb4t4atnQaC7O1PbeHzoBNWd9i74fE Zr0HxaCr7cE67XfRBcGyDEA/uBKpTWaebzYYABgIH9Xrzt4EdxlcYcon5TuoQCwnteSW lJiw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1719936811; x=1720541611; 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=jEjf9tkTUa/yu7CN/hmDp3JJtJRan6g9f3kMN/OjhnI=; b=FSTK82iAliTZjrIclXW0W3EsHEc/s2Di09w5fowJbxg7dydl1oUqbMASQ5Ppi8ESiT 1q6JiaJhhCwjt1pjkVJOpVoXmDzFGrcv3AMW3YRaDGVyNaGewepKkxWFY7N65XoOQ/+5 GeabrUaFY/LRNOqetGZKNYP6tj8Uuuseya+b2/4YoxuAXnXjzoG36ESO3mZvLDpmGDm+ HQnVlPtevuCQ03SThP29WIbBb1OahXdYxKAUBswv59OkV6fNsA3zv9Z3vMuNc3vCtaCm u1ATuTmzTCxb+ereNzbFUWKMUb5yrZgURSNPviWy1YI49GVBhiLnZRDdXZZ2lzJ+lGF4 peVw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUYs1mT04vx5CnHzIuns/22FvixCK6qzBOBp8zyRlh2SFCl2XdovLnyWh+4n3CVSzV8EChvtwdXR17dkqC0LIX4mKo3ll4= X-Gm-Message-State: AOJu0YwSqO+f/yqWe//JLe35jWu36LRmbyCOSIIXDmVqcYAQpTeiD6hb MyDCKfAU0cnuslyX9SY1UazOMBv9xtnqEtJryzSsBbK945NleatJ X-Google-Smtp-Source: AGHT+IF9HWaKjXPLm5Cr7nuQnuQJpGLLNDrzRbw7Z5skDoYfpVz46H1wmshPzN5wxDAAPHRVygMZ8w== X-Received: by 2002:a25:2703:0:b0:dff:323d:349d with SMTP id 3f1490d57ef6-e036e6ea111mr5944790276.0.1719936810227; Tue, 02 Jul 2024 09:13:30 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:120f:b0:df4:e17a:8653 with SMTP id 3f1490d57ef6-e035a569c3bls6678120276.1.-pod-prod-08-us; Tue, 02 Jul 2024 09:13:28 -0700 (PDT) X-Received: by 2002:a05:6902:707:b0:e03:5239:736b with SMTP id 3f1490d57ef6-e036ec370aemr735947276.8.1719936808656; Tue, 02 Jul 2024 09:13:28 -0700 (PDT) Received: by 2002:a81:ae02:0:b0:627:7f59:2eee with SMTP id 00721157ae682-64d36134a0ams7b3; Tue, 2 Jul 2024 08:57:40 -0700 (PDT) X-Received: by 2002:a05:6902:2b09:b0:e02:ba8f:2bd5 with SMTP id 3f1490d57ef6-e036eb5476emr903638276.7.1719935859417; Tue, 02 Jul 2024 08:57:39 -0700 (PDT) Date: Tue, 2 Jul 2024 08:57:39 -0700 (PDT) From: Eric Voskuil To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: <72e83c31-408f-4c13-bff5-bf0789302e23n@googlegroups.com> <5b0331a5-4e94-465d-a51d-02166e2c1937n@googlegroups.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_91341_1351928154.1719935859194" 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_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 >>>> 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.

>>> D= uplicate 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-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.

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.

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

> 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.

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.

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".

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.

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).

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.

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.

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.

e=

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