Delivery-date: Sat, 03 May 2025 07:26:25 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of gmaxwell@gmail.com designates 2607:f8b0:4864:20::1034 as permitted sender) client-ip=2607:f8b0:4864:20::1034;
MIME-Version: 1.0
References: <CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr+ShOC1KZi2V3V2zooTXyg@mail.gmail.com>
 <cc2dfa79-89f0-4170-9725-894ea189a0e2n@googlegroups.com> <CAPv7TjaDGr4HCdQ0rR6_ma5zh2umU9r3_529szdswn_GjjnuCw@mail.gmail.com>
 <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com> <CAExE9c8XfEH__onX3DhUQh0OnvpoOLwRRp8+Z6PozyKGtqpspw@mail.gmail.com>
 <fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n@googlegroups.com> <CAPv7TjYCaAsJFo3t6A6HmoojnbMNjSRkXHeOW=jrbGBpPYzQVg@mail.gmail.com>
In-Reply-To: <CAPv7TjYCaAsJFo3t6A6HmoojnbMNjSRkXHeOW=jrbGBpPYzQVg@mail.gmail.com>
From: Greg Maxwell <gmaxwell@gmail.com>
Date: Sat, 3 May 2025 13:57:09 +0000
Message-ID: <CAAS2fgQ1CvyxoRckZT2_6dNgKxDaKWvuK46FYMeaHc8Np_gDPg@mail.gmail.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
To: Ruben Somsen <rsomsen@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>, saintwenhao@gmail.com, 
	Sanket Kanjalkar <sanket1729@gmail.com>
Content-Type: multipart/alternative; boundary="00000000000049caa706343ba510"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

--00000000000049caa706343ba510
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hm. Fair point, but I think you cannot escape the assumption that A is
unique (well A and its spend) thanks to TXID uniqueness without weakening
the security argument, since A*n eventually collides.  It's essentially the
same argument you make for characteristic 2, it just takes more
repetitions.  Without knowing the salt you'd need 2^256 repetitions to be
certain, but e.g. see the prior suggestions on truncating the hash to 32
bits or whatever, a practical number of A repeats would then self cancel.

To be clear I'm not arguing that it should be xor here, but pointing out
there is structure here you might not have expected.


On Sat, May 3, 2025 at 1:42=E2=80=AFPM Ruben Somsen <rsomsen@gmail.com> wro=
te:

>   Hey all,
>
>
> @Saint Wenhao
>
> >if you take the sum of hashes, which should be finally zero, then by
> grinding UTXOs, someone could make it zero
>
> That's what the secret salt prevents. You can't grind for a certain numbe=
r
> if you don't know what the number is you are trying to collide with.
>
> >maybe you can avoid hashing at all [...] And then, it is all about mixin=
g
> the salt
>
> Without a concrete solution I'm afraid that's wishful thinking. That last
> part of the sentence is why we currently need the hash, as well as for
> adding more data in the non-assumevalid version.
>
>
> @Sanket Kanjalkar
>
> >What if instead of hash we encrypt with AES
>
> I can't really evaluate whether this might work, but I can see the line o=
f
> reasoning. Conceptually, I think what we need is something that transform=
s
> the data into fixed length blocks for which an attacker can't know the
> relationship between each block (i.e. via a secret). The transformation
> needs to be the same on the input and output side.
>
>
> @Greg Maxwell
>
> >Your reduction function could just be xor
>
> I had initially ruled XOR out. Reason for this is that XOR would lead one
> to conclude that sets [A, B, C, C], [A, B], [A, B, D, D], etc. are all
> equivalent because any two values cancel each other out, regardless of
> whether the sets are on the input or output side. Modular add/sub doesn't
> have this issue. If the speedup actually turns out to be significant then
> there may be some clever way to salvage it like by counting the total
> number of inputs and outputs and relying on the knowledge that every txid
> must be unique, but that's a lot harder to reason about.
>
> >even if its with a quite expensive hash function that the IBD performanc=
e
> will be heavily bottlenecked in network and parallelism related issues an=
d
> be far from the lowest hanging fruit for a while,  considering that this
> has eliminated the big sequential part and a number of annoying to optimi=
ze
> components entirely
>
> Very true, and as you said, we can easily drop-in replace the hash
> function at any future point we like, without adverse consequences.
>
>
> Cheers,
> Ruben
>
> On Sat, May 3, 2025 at 2:07=E2=80=AFPM Greg Maxwell <gmaxwell@gmail.com> =
wrote:
>
>> On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanjalkar wro=
te:
>>
>> > hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) -
>> hash(UTXO_D||salt) =3D=3D 0 (proving (A=3D=3DC && B=3D=3DD) || (A=3D=3DD=
 && B=3D=3DC))
>>
>> What if instead of hash we encrypt with AES and modular add/subs? I
>> cannot prove it; but I also don't see a clear way this is broken.
>>
>> 1. Sample random symmetric key `k`
>> 2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) -
>> AES(UTXO_D) =3D=3D 0 =3D>  (proving (A=3D=3DC && B=3D=3DD) || (A=3D=3DD =
&& B=3D=3DC))?
>>
>>
>> AES in CTR mode is, I'm not sure about other modes? Obviously CTR mode
>> would be unsuitable! (I mean sure modular add/sub and xor are different
>> operations but they are quite close).  I think that in many modes the
>> collision resistance would have to at least be restricted by the birthda=
y
>> bound with the small block size. I think CMC might be needed to avoid th=
at
>> sort of issue.
>>
>>
>>
>> --
>> You received this message because you are subscribed to the Google Group=
s
>> "Bitcoin Development Mailing List" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n
>> email to bitcoindev+unsubscribe@googlegroups.com.
>> To view this discussion visit
>> https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a7=
ea31ebf22n%40googlegroups.com
>> <https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a=
7ea31ebf22n%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter>
>> .
>>
>

--=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/=
CAAS2fgQ1CvyxoRckZT2_6dNgKxDaKWvuK46FYMeaHc8Np_gDPg%40mail.gmail.com.

--00000000000049caa706343ba510
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hm. Fair point, but I think you cannot escape the ass=
umption that A is unique (well A and its spend) thanks to TXID uniqueness w=
ithout weakening the security argument, since A*n eventually collides.=C2=
=A0 It&#39;s essentially the same argument you make for characteristic 2, i=
t just takes more repetitions.=C2=A0 Without knowing the salt you&#39;d nee=
d 2^256 repetitions to be certain, but e.g. see the prior suggestions on tr=
uncating the hash to 32 bits or whatever, a practical number of A repeats w=
ould then self cancel.</div><div><br></div><div>To be clear I&#39;m not arg=
uing that it should be xor here, but pointing out there is structure here y=
ou might not have expected.</div><div><br></div><div><br></div><div><br></d=
iv><div><br></div></div><br><div class=3D"gmail_quote gmail_quote_container=
"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, May 3, 2025 at 1:42=E2=80=
=AFPM Ruben Somsen &lt;<a href=3D"mailto:rsomsen@gmail.com">rsomsen@gmail.c=
om</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex=
"><div dir=3D"ltr">=C2=A0 Hey all,<div><br></div><div><br></div><div><a cla=
ss=3D"gmail_plusreply" id=3D"m_7194414729081378160gmail-plusReplyChip-0">@S=
aint Wenhao</a><br><div><br></div><div>&gt;if you take the sum of hashes, w=
hich should be finally zero, then by grinding UTXOs, someone could make it =
zero</div><div><br></div><div>That&#39;s what the secret salt prevents. You=
 can&#39;t grind for a certain number if you don&#39;t know what the number=
 is you are trying to collide with.</div><div><br></div></div><div>&gt;mayb=
e you can avoid hashing at all [...] And then, it is all about mixing the s=
alt</div><div><br></div><div>Without a concrete solution I&#39;m afraid tha=
t&#39;s wishful thinking. That last part of the sentence is why we currentl=
y need the hash, as well as for adding more data in the non-assumevalid ver=
sion.</div><div><br></div><div><br></div><div><a class=3D"gmail_plusreply" =
id=3D"m_7194414729081378160plusReplyChip-0">@Sanket Kanjalkar</a><br></div>=
<div><br></div><div>&gt;What if instead of hash we encrypt with AES</div><d=
iv><br></div><div>I can&#39;t really evaluate whether this might work, but =
I can see the=C2=A0line of reasoning. Conceptually, I think what we need is=
 something that transforms the data into fixed length blocks for which an a=
ttacker can&#39;t know the relationship between each block (i.e. via a secr=
et). The transformation needs to be the same on the input and output side.<=
/div><div><br></div><div><a class=3D"gmail_plusreply"><br></a></div><div><a=
 class=3D"gmail_plusreply" id=3D"m_7194414729081378160plusReplyChip-2">@Gre=
g Maxwell</a><br></div><div><br></div><div>&gt;Your reduction function coul=
d just be xor</div><div><br></div><div>I had initially ruled XOR out. Reaso=
n for this is that XOR would lead one to conclude that sets [A, B, C, C], [=
A, B], [A, B, D, D], etc. are all equivalent because any two values cancel =
each other out, regardless of whether the sets are on the input or output s=
ide. Modular add/sub doesn&#39;t have this issue. If the speedup actually t=
urns out to be significant then there may be some clever way to salvage it =
like by counting the total number of inputs and outputs and relying on the =
knowledge that every txid must be unique, but that&#39;s a lot harder to re=
ason about.</div><div><br></div><div>&gt;even if its with a quite expensive=
 hash function that the IBD performance will be heavily bottlenecked in net=
work and parallelism related issues and be far from the lowest hanging frui=
t for a while,=C2=A0 considering that this has eliminated the big sequentia=
l part and a number of annoying to optimize components entirely</div><div><=
br></div><div>Very true, and as you said, we can easily drop-in replace the=
 hash function at any future point we like, without adverse consequences.</=
div><div><br></div><div><br></div><div>Cheers,</div><div>Ruben</div></div><=
br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat,=
 May 3, 2025 at 2:07=E2=80=AFPM Greg Maxwell &lt;<a href=3D"mailto:gmaxwell=
@gmail.com" target=3D"_blank">gmaxwell@gmail.com</a>&gt; wrote:<br></div><b=
lockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le=
ft:1px solid rgb(204,204,204);padding-left:1ex"><div><div dir=3D"auto">On S=
aturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanjalkar wrote:<br>=
</div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid r=
gb(204,204,204);padding-left:1ex"><div dir=3D"ltr">&gt; hash(UTXO_A||salt) =
+ hash(UTXO_B||salt) - hash(UTXO_C||salt) - hash(UTXO_D||salt) =3D=3D 0 (pr=
oving (A=3D=3DC &amp;&amp; B=3D=3DD) || (A=3D=3DD &amp;&amp; B=3D=3DC))<br>=
<br></div><div dir=3D"ltr">What if instead of hash we encrypt with AES and =
modular add/subs? I cannot prove it; but I also don&#39;t see a clear way t=
his is broken.=C2=A0<br><br>1. Sample random symmetric key `k`<br>2. Instea=
d of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) - AES(UTXO_D) =3D=
=3D 0 =3D&gt;=C2=A0=C2=A0(proving (A=3D=3DC &amp;&amp; B=3D=3DD) || (A=3D=
=3DD &amp;&amp; B=3D=3DC))?</div></blockquote><div><br></div><div>AES in CT=
R mode is, I&#39;m not sure about other modes? Obviously CTR mode would be =
unsuitable! (I mean sure modular add/sub and xor are different operations b=
ut they are quite close).=C2=A0 I think that in many modes the collision re=
sistance would have to at least be restricted by the birthday bound with th=
e small block size. I think CMC might be needed to avoid that sort of issue=
.</div><div><br></div><div>=C2=A0</div></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" target=
=3D"_blank">bitcoindev+unsubscribe@googlegroups.com</a>.<br>
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n%40googlegroups.com?utm_med=
ium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">https://groups.googl=
e.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n%40googlegrou=
ps.com</a>.<br>
</blockquote></div>
</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 visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/CAAS2fgQ1CvyxoRckZT2_6dNgKxDaKWvuK46FYMeaHc8Np_gDPg%40mail.gmail=
.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/ms=
gid/bitcoindev/CAAS2fgQ1CvyxoRckZT2_6dNgKxDaKWvuK46FYMeaHc8Np_gDPg%40mail.g=
mail.com</a>.<br />

--00000000000049caa706343ba510--