diff options
| author | Greg Maxwell <gmaxwell@gmail.com> | 2025-05-02 09:07:50 -0700 |
|---|---|---|
| committer | bitcoindev <bitcoindev@googlegroups.com> | 2025-05-02 12:09:14 -0700 |
| commit | 4227ab63090603a573627e2a3cac37bacd95ce97 (patch) | |
| tree | 9143255a2813d87afab85b9649a2de8929d1dd1c | |
| parent | 2e1e777775f48f33440862ab30dbdf0a71ebcbf7 (diff) | |
| download | pi-bitcoindev-4227ab63090603a573627e2a3cac37bacd95ce97.tar.gz pi-bitcoindev-4227ab63090603a573627e2a3cac37bacd95ce97.zip | |
Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
| -rw-r--r-- | 0f/11791d994af3adb5a70c9733f06410f52bc109 | 264 |
1 files changed, 264 insertions, 0 deletions
diff --git a/0f/11791d994af3adb5a70c9733f06410f52bc109 b/0f/11791d994af3adb5a70c9733f06410f52bc109 new file mode 100644 index 000000000..8a0a95b9b --- /dev/null +++ b/0f/11791d994af3adb5a70c9733f06410f52bc109 @@ -0,0 +1,264 @@ +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 <bitcoindev+bncBCJNLJPWXAIBBTNQ2TAAMGQEXRNJGUI@googlegroups.com>) + 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 <bitcoindev@gnusha.org>; 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 <gmaxwell@gmail.com> +To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> +Message-Id: <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com> +In-Reply-To: <CAPv7TjaDGr4HCdQ0rR6_ma5zh2umU9r3_529szdswn_GjjnuCw@mail.gmail.com> +References: <CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr+ShOC1KZi2V3V2zooTXyg@mail.gmail.com> + <cc2dfa79-89f0-4170-9725-894ea189a0e2n@googlegroups.com> + <CAPv7TjaDGr4HCdQ0rR6_ma5zh2umU9r3_529szdswn_GjjnuCw@mail.gmail.com> +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: <bitcoindev.googlegroups.com> +X-Google-Group-Id: 786775582512 +List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com> +List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com> +List-Archive: <https://groups.google.com/group/bitcoindev +List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com> +List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>, + <https://groups.google.com/group/bitcoindev/subscribe> +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 + +<div><div dir=3D"auto">On Friday, May 2, 2025 at 11:01:10=E2=80=AFAM UTC Ru= +ben Somsen wrote:<br /></div><blockquote style=3D"margin: 0px 0px 0px 0.8ex= +; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir= +=3D"ltr"><div>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).</div></div></blockquote><div><br /></div>= +<div>Doh. Right. Got too excited.</div><div>=C2=A0<br /></div><blockquote s= +tyle=3D"margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204= +); padding-left: 1ex;"><div dir=3D"ltr"><div>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.</div></div></blockquote><div><br /></div><div>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.</div><div><br /></div><div>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 <br /></div><div><br /></div><div>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).</div><div><br /></di= +v><div>=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.</div><div><br /></div= +><div><br /></div><div><br /></div><div><br /></div><div><br /></div></div> + +<p></p> + +-- <br /> +You received this message because you are subscribed to the Google Groups &= +quot;Bitcoin Development Mailing List" 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 visit <a href=3D"https://groups.google.com/d/msgid/= +bitcoindev/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com?utm_med= +ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= +ev/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com</a>.<br /> + +------=_Part_60917_759758223.1746202070906-- + +------=_Part_60916_1045498522.1746202070906-- + |