From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 02 May 2025 12:09:14 -0700 Received: from mail-yb1-f192.google.com ([209.85.219.192]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uAvl3-0001Hv-2M for bitcoindev@gnusha.org; Fri, 02 May 2025 12:09:14 -0700 Received: by mail-yb1-f192.google.com with SMTP id 3f1490d57ef6-e72a02f0e5esf2784602276.3 for ; Fri, 02 May 2025 12:09:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1746212947; x=1746817747; 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=U9CVPL5bzW2/UQeyRTzcErMBuYpD6+QynIsi6WRrVFw=; b=KblY4sYuEfYimyhDl3K1gLkFBrRmYSlbhgA+978efUPb3qvP3x9qKpUt8RWDHGGybO ZK6gH4wH/3YZ8H9gP4lJQeK49ik0m+T0SVNsindfzkVr5h6WpOmiftyab3j1qDKmF4zS 2AJfxxgPLvsPLBPE2xHOr2aj10SKnBJ9OTJl9cyNpXBa+6404bYoZ43KNil2Y8a5UQGx hoWm/ZPz5Nr0MV5CLQGi3Pql1k8X9ouFn4q3RaEZRVNtB6+o5F3UKQhp/u90PrmpdUsG kV4BJ4IATFVVGC44Yyp7swJbA14XHD3hRdwunz+u6h52WziLPyasgV03bnNIVRIVSNMG MMZQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1746212947; x=1746817747; 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=U9CVPL5bzW2/UQeyRTzcErMBuYpD6+QynIsi6WRrVFw=; b=YtPtFzthtERFICV6qPqR+kPXnj5PModLMDRCppLENkycDRXRtZNhZMvAxmQw8WnZ5L OpELoHx7JbIZCU7rHQzt6hDFlN2n/hZ4lUrR1nBiBUr0KiMYfxoGQsT4yECNVbk4SZ9K j5DW0h9R3DAO+kzRzMI6gU5/3/WB4qMhMtoG7sO1oJZLy0zi4zrtvxL22M/PCJ1VykOz VJneDTsEBR6Nr74Xx0I8g/OHRkfCDJYHBs7ArsVahUTFewTrl9TNZQ4QZix1zE9eTEem f5X+furFrw8e5qyktFL/wgeh1gA5ohJVc1u1mFg5oMH6IqxQkULk3uTdLzvYrEuN+02B MkfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746212947; x=1746817747; 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=U9CVPL5bzW2/UQeyRTzcErMBuYpD6+QynIsi6WRrVFw=; b=Kqucia+Yv+HvuvceO3x2SRuBe9ioOCkSvi3amBT+PzT8TdU8hha+VAk8MVOgDgAHcp AizyBnumFiny6Bo5mj8fwKSvH/cjrHHI5m8Oph2X+lP5A6dsFh38JIZRIJN9CpWgvu9+ Ap1VdFUjyn3WEjO6NvMjfpZ8Y5ZDAPuNk2x4/PFMV22RLYXphiUumN5P0KWI7OuuFXxX 2FCmt2ivfM0xfjwEz2u7J6Bwd8EZ1YnB7LQyf4Xr8EA1gH6AqaxzgKRkXGL6kwDLOGTL M8vf17acziIUkatiNWNIpyPrYA6/3weygiX1d1wvZpwZt1Fm2EuZPy+M6J1Ur2bvibNA ygEg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCX/fG81dpY7y6HwbZQ6HUkJWgmb3gQM79Ciqo+d11WSG1FQ0FT1rz2hAQr1n26EhwkZAsOcjKmHX3wL@gnusha.org X-Gm-Message-State: AOJu0Yw1FJhx73aEQy/dkm/S1iLS/r0c86Vm0vKbcCoz9epJTy+4PuVb QXsuloj/JG76CIKaT2J5FmAjP2glOr71hA/qzHvCHeAxP9dteu3r X-Google-Smtp-Source: AGHT+IEwg2aA4MtgKqZfG4rVSlnMB1zYxnfLhuG+rnPjzaCzjsBz5nzQdw5z5iilUYOHe9LmiDWcyw== X-Received: by 2002:a05:6902:150a:b0:e72:8aca:d06b with SMTP id 3f1490d57ef6-e756557de61mr5165281276.25.1746212946796; Fri, 02 May 2025 12:09:06 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBGVUra4Nt9NxNJTWp81T6mgriMoJskBCISpW9723JFwgw== Received: by 2002:a25:e087:0:b0:e74:7ce7:2dd8 with SMTP id 3f1490d57ef6-e754b311c0cls782149276.2.-pod-prod-05-us; Fri, 02 May 2025 12:09:01 -0700 (PDT) X-Received: by 2002:a05:690c:700c:b0:6ef:7dde:bdef with SMTP id 00721157ae682-708cede5111mr59480877b3.23.1746212941096; Fri, 02 May 2025 12:09:01 -0700 (PDT) Received: by 2002:a81:d448:0:b0:706:b535:945d with SMTP id 00721157ae682-708cfda3e38ms7b3; Fri, 2 May 2025 09:07:52 -0700 (PDT) X-Received: by 2002:a81:be09:0:b0:708:16b0:59bf with SMTP id 00721157ae682-708cede5268mr38475787b3.26.1746202071504; Fri, 02 May 2025 09:07:51 -0700 (PDT) Date: Fri, 2 May 2025 09:07:50 -0700 (PDT) From: Greg Maxwell To: Bitcoin Development Mailing List Message-Id: <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com> In-Reply-To: References: Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_60916_1045498522.1746202070906" X-Original-Sender: gmaxwell@gmail.com 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.5 (/) ------=_Part_60916_1045498522.1746202070906 Content-Type: multipart/alternative; boundary="----=_Part_60917_759758223.1746202070906" ------=_Part_60917_759758223.1746202070906 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Friday, May 2, 2025 at 11:01:10=E2=80=AFAM UTC Ruben Somsen wrote: I don't see a practical way to do this without compromising the benefits of= =20 SwiftSync because of the "later find them being spent" part. For one, it=20 would require doing a lookup for each input to see if it's in your UTXO=20 set, something we currently don't need to do at all. Secondly, it would=20 require blocks to be processed in order, limiting parallelization. The=20 space savings would also be negligible, considering the hint data is=20 already <100MB (compressed). Doh. Right. Got too excited. =20 I think most of the remaining optimization potential (other than the=20 engineering work to enable parallel validation) is in the hash=20 aggregate, like the midstate reuse. Is there a faster alternative to=20 sha256? Can we get away with 16 byte hashes? I could be mistaken, but in=20 theory it seems we could even get away with 4 byte hashes if we allowed for= =20 a 1 in 4 billion chance of accidentally accepting an invalid chain. Leaving= =20 consensus to chance feels philosophically improper, but it's a pretty safe= =20 bet considering it also involves PoW to trigger and even then would only=20 affect one or two random unlucky people on Earth. I think the problem isn't so much the size of the hash output, but rather= =20 the property you need is that each salt gives you a different hash function= =20 such that the attacker cannot predictably create collisions. The most=20 expedient way to get there is a cryptographic hash function, which limits= =20 you lower performance choices. Your reduction function could just be xor= =20 and if it is I doubt the output size itself matters much for performance...= =20 and my guess is that e.g. xor with 32 byte hashes will have better=20 performance than addition with 16 bytes. It doesn't need to be so in the initial implementation but ultimately it=20 may make sense for the host to benchmark available hashes and pick the=20 fastest. SHA-256 will easily be a winner on hardware with SHA-NI or=20 similar. But there are other cryptographic hashes in the codebase that=20 might be faster on systems without sha256 hardware support. =20 There are argument I can see to prove the security of simpler hashes that= =20 only work if you assume that the attacker could only insert specific finite= =20 numbers of bad changes... but they really have completely full control of= =20 the hash function input except for the salt and that I think makes it hard= =20 to say much positive about the security of any optimization except=20 truncating a secure hash (and I don't think truncating will win you much=20 security). In terms of security keep in mind that a prospective attacker needs to=20 also perform POW to get their attack chain up to the users accepted chain= =20 tip, which means that they have to do the work between the AV point and the= =20 tip assuming the user isn't isolated. This fact could be used to justify a= =20 rather weak hash function, but I think it's not really worth a lot of=20 analysis ahead of the initial functionality. I'm guessing that once this= =20 is implemented, even if its with a quite expensive hash function that the= =20 IBD performance will be heavily bottlenecked in network and parallelism=20 related issues and be far from the lowest hanging fruit for a while, =20 considering that this has eliminated the big sequential part and a number= =20 of annoying to optimize components entirely. --=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 visit https://groups.google.com/d/msgid/bitcoindev/= 69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com. ------=_Part_60917_759758223.1746202070906 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Friday, May 2, 2025 at 11:01:10=E2=80=AFAM UTC Ru= ben Somsen wrote:
I don't see a practical way to do this without compromising t= he benefits of SwiftSync because of the=C2=A0"later find them being spent" = part. For one, it would require doing a lookup for each input to see if it'= s in your UTXO set, something we currently don't need to do at all. Secondl= y, it would require blocks to be processed in order, limiting parallelizati= on. The space savings would also be negligible, considering the hint data i= s already <100MB (compressed).

=
Doh. Right. Got too excited.
=C2=A0
I think most of the remaining = optimization potential (other than the engineering work to enable parallel = validation) is in the hash aggregate,=C2=A0like the midstate reuse. Is ther= e a faster alternative to sha256? Can we get away with 16 byte hashes? I co= uld be mistaken, but in theory it seems we could even get away with 4 byte = hashes if we allowed for a 1 in 4 billion chance of accidentally accepting = an invalid chain. Leaving consensus to chance feels philosophically imprope= r, but it's a pretty safe bet considering it also involves PoW to trigger a= nd even then would only affect one or two random unlucky people on=C2=A0Ear= th.

I think the problem isn't= so much the size of the hash output, but rather the property you need is t= hat each salt gives you a different hash function such that the attacker ca= nnot predictably create collisions. The most expedient way to get there is = a cryptographic hash function, which limits you lower performance choices.= =C2=A0 Your reduction function could just be xor and if it is I doubt the o= utput size itself matters much for performance... and my guess is that e.g.= xor with 32 byte hashes will have better performance than addition with 16= bytes.

It doesn't need to be so in the initial = implementation but ultimately it may make sense for the host to benchmark a= vailable hashes and pick the fastest.=C2=A0 SHA-256 will easily be a winner= on hardware with SHA-NI or similar.=C2=A0 But there are other cryptographi= c hashes in the codebase that might be faster on systems without sha256 har= dware support.=C2=A0

There are argument I= can see to prove the security of simpler hashes that only work if you assu= me that the attacker could only insert specific finite numbers of bad chang= es... but they really have completely full control of the hash function inp= ut except for the salt and that I think makes it hard to say much positive = about the security of any optimization except truncating a secure hash (and= I don't think truncating will win you much security).

=C2=A0In terms of security keep in mind that a prospective attacker = needs to also perform POW to get their attack chain up to the users accepte= d chain tip, which means that they have to do the work between the AV point= and the tip assuming the user isn't isolated.=C2=A0 This fact could be use= d to justify a rather weak hash function, but I think it's not really worth= a lot of analysis ahead of the initial functionality.=C2=A0 I'm guessing t= hat once this is implemented, even if its with a quite expensive hash funct= ion that the IBD performance will be heavily bottlenecked in network and pa= rallelism related issues and be far from the lowest hanging fruit for a whi= le,=C2=A0 considering that this has eliminated the big sequential part and = a number of annoying to optimize components entirely.





--
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 visit https://groups.google.com/d/msgid/bitcoind= ev/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com.
------=_Part_60917_759758223.1746202070906-- ------=_Part_60916_1045498522.1746202070906--