From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 03 May 2025 07:55:23 -0700 Received: from mail-yb1-f186.google.com ([209.85.219.186]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uBEGw-00037Q-5d for bitcoindev@gnusha.org; Sat, 03 May 2025 07:55:23 -0700 Received: by mail-yb1-f186.google.com with SMTP id 3f1490d57ef6-e6de4ddbb3bsf3688578276.0 for ; Sat, 03 May 2025 07:55:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1746284116; x=1746888916; 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=7M0y3YfJ2R53Rb8bo9+K3i9lFlBlHRuKfio1Cc5D5fc=; b=lsd3SvSl5wSzYNT4BQvxKzXE6+OAo8DH6JMh9TLfltzruw8IxJkm7LqlwwE9HVmPLP JVMj8UPGOAMxLpNrtWMfmvCx20MOOiXIxo7h8mf4dfTSlZI8nQt1hnn9VQoyAxcz37an xGW9doJUH9VxAcluCjqoHSiOsLmvujaHWdfx0pve4RTV0A7ytU+jX7boZ8LYrjUOymLZ P5F9bSUAio3txOvpV2mjfa702r9btM8NSYnGJ+8SIfSCH1dBmsW/UN+1KHqayqVly+Wx /qT6MRNb5Kv9cgbI70NihTxReKZ0mbSRJtdINVjBfvmLCCKHwfBr3gLY8nT6VFlAdVgG s2Wg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1746284116; x=1746888916; 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=7M0y3YfJ2R53Rb8bo9+K3i9lFlBlHRuKfio1Cc5D5fc=; b=iM3uL4+kPaBFk2XzmSjnSQ0iBF0rBiJJD6gEksouOKlPKrGj9Xdh7TRWpBDilWG0vV 6gMNEP3InDGQQN5pdIhUT0tLXWO8cmU/sWeblRo8k/LhXvj5uFJgdQYoa0e3/wOVqb/9 lsUh9ar8TEQhUnvB5CgllafuHc+RJD6FuA1HVzDnMRMoWvntodHDGVCLcgJ+1BpTeTQ6 YJB9FcvcyblFGQIo3F5fAmC8M2FBQjVehlhVfRve0bWJBV75i3wyPpCd0t2tk7IDjz8Y pc84vqw7gMGMA21IeuZP32xj/lGPQW6NjogYgzssgkGwyHsFcoQYBCNNrmTAf2RvFC7x 1WMg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746284116; x=1746888916; 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=7M0y3YfJ2R53Rb8bo9+K3i9lFlBlHRuKfio1Cc5D5fc=; b=RdXzH3Uw87LOpyAOHQksQRwzhikwAWRUm2+wAH+/U8q7iNyOKAJhvKL393A/PWXpw8 l7HXlHuIHQ8B0yilUUAnlJJUClH+89Gzb5wY/8lLzWDpCxEDCrGG4zFkl4QQRze7Y+kk cMjbIu9wrQcYeI4ZZTWJrVcvwJ5UK/n4YZpvlTkRCzLfZHg7C23Z4qAq3GAtHgR7hjgJ 50czgm0Mr/4Md+xMNhTYGKAtL+VRzm23JNmQDXEiOUFWaDIsh0nmeu10dUeMMHiILA+n 9ekdVPkOO98y9DC56OJVtI6W1RsMzVeUlC/6Ul/aaOzixQ8I3ufAmfx0LKub3HcguV4h s0VQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWCzvzqnbxGGnAbC7CUrbCh4aSmMGrPZBV/VBFpt4JOyJSmDfaaJ/yKRI+CNx6kk9pWOb0jz0JNdp1k@gnusha.org X-Gm-Message-State: AOJu0YwmCh+/nS0blu68e5YgU7E/h5wUW9gn3PVbx95i4ww3udlUA2Eo 8FdPo5c+3glXuiQs48qnRaTvcD2suxXx5sdyZmJb66nXZMMNOIBH X-Google-Smtp-Source: AGHT+IHDm+4pU2P4B9lBrw3vfivIJU+zX9KXVBiWkC5oAOw1pSYJCkxOMQcMo3GmZ6bVtF6qNBFMpg== X-Received: by 2002:a05:6902:4901:b0:e6b:8025:a9d2 with SMTP id 3f1490d57ef6-e757d2fabd4mr1477377276.24.1746284116385; Sat, 03 May 2025 07:55:16 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBEVxCqsBcNHHmLwRLLl0lObBP/T3sHWFnrP4PJAY2OWGw== Received: by 2002:a25:d305:0:b0:e74:7dfc:1c16 with SMTP id 3f1490d57ef6-e74dc7c5279ls1191824276.1.-pod-prod-05-us; Sat, 03 May 2025 07:55:12 -0700 (PDT) X-Received: by 2002:a05:690c:6213:b0:708:16b0:59bf with SMTP id 00721157ae682-708eaf5245emr18079307b3.26.1746284112616; Sat, 03 May 2025 07:55:12 -0700 (PDT) Received: by 2002:a05:690c:a10:b0:708:1ea1:3cd5 with SMTP id 00721157ae682-708cfde0f15ms7b3; Sat, 3 May 2025 07:36:53 -0700 (PDT) X-Received: by 2002:a05:690c:360d:b0:708:170c:a699 with SMTP id 00721157ae682-708eaf52804mr16129637b3.27.1746283011799; Sat, 03 May 2025 07:36:51 -0700 (PDT) Date: Sat, 3 May 2025 07:36:51 -0700 (PDT) From: Greg Maxwell To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com> Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_165114_873342410.1746283011198" 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_165114_873342410.1746283011198 Content-Type: multipart/alternative; boundary="----=_Part_165115_1770387500.1746283011198" ------=_Part_165115_1770387500.1746283011198 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable If you go look at the original muhash thread on the list there is some=20 pretty extensive discussion around accumulators, including this point. But= =20 I don't think it applies here because there is no reason for the salt to be= =20 anything but unique and private to the user. On Saturday, May 3, 2025 at 2:26:18=E2=80=AFPM UTC Greg Maxwell wrote: > Hm. Fair point, but I think you cannot escape the assumption that A is=20 > unique (well A and its spend) thanks to TXID uniqueness without weakening= =20 > the security argument, since A*n eventually collides. It's essentially t= he=20 > same argument you make for characteristic 2, it just takes more=20 > repetitions. Without knowing the salt you'd need 2^256 repetitions to be= =20 > certain, but e.g. see the prior suggestions on truncating the hash to 32= =20 > 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= =20 > there is structure here you might not have expected. > > > > > > On Sat, May 3, 2025 at 1:42=E2=80=AFPM Ruben Somsen wr= ote: > >> Hey all, >> >> >> @Saint Wenhao >> >> >if you take the sum of hashes, which should be finally zero, then by=20 >> grinding UTXOs, someone could make it zero >> >> That's what the secret salt prevents. You can't grind for a certain=20 >> number if you don't know what the number is you are trying to collide wi= th. >> >> >maybe you can avoid hashing at all [...] And then, it is all about=20 >> mixing the salt >> >> Without a concrete solution I'm afraid that's wishful thinking. That las= t=20 >> part of the sentence is why we currently need the hash, as well as for= =20 >> 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= =20 >> of reasoning. Conceptually, I think what we need is something that=20 >> transforms the data into fixed length blocks for which an attacker can't= =20 >> know the relationship between each block (i.e. via a secret). The=20 >> 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 on= e=20 >> to conclude that sets [A, B, C, C], [A, B], [A, B, D, D], etc. are all= =20 >> equivalent because any two values cancel each other out, regardless of= =20 >> whether the sets are on the input or output side. Modular add/sub doesn'= t=20 >> have this issue. If the speedup actually turns out to be significant the= n=20 >> there may be some clever way to salvage it like by counting the total=20 >> number of inputs and outputs and relying on the knowledge that every txi= d=20 >> must be unique, but that's a lot harder to reason about. >> >> >even if its with a quite expensive hash function that the IBD=20 >> performance will be heavily bottlenecked in network and parallelism rela= ted=20 >> issues and be far from the lowest hanging fruit for a while, considerin= g=20 >> that this has eliminated the big sequential part and a number of annoyin= g=20 >> to optimize components entirely >> >> Very true, and as you said, we can easily drop-in replace the hash=20 >> 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 = wrote: >> >>> On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanjalkar wr= ote: >>> >>> > hash(UTXO_A||salt) + hash(UTXO_B||salt) - hash(UTXO_C||salt) -=20 >>> hash(UTXO_D||salt) =3D=3D 0 (proving (A=3D=3DC && B=3D=3DD) || (A=3D=3D= D && B=3D=3DC)) >>> >>> What if instead of hash we encrypt with AES and modular add/subs? I=20 >>> cannot prove it; but I also don't see a clear way this is broken.=20 >>> >>> 1. Sample random symmetric key `k` >>> 2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) -=20 >>> 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= =20 >>> would be unsuitable! (I mean sure modular add/sub and xor are different= =20 >>> operations but they are quite close). I think that in many modes the= =20 >>> collision resistance would have to at least be restricted by the birthd= ay=20 >>> bound with the small block size. I think CMC might be needed to avoid t= hat=20 >>> sort of issue. >>> >>> =20 >>> >>> --=20 >>> You received this message because you are subscribed to the Google=20 >>> Groups "Bitcoin Development Mailing List" group. >>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>> an email to bitcoindev+...@googlegroups.com. >>> To view this discussion visit=20 >>> https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a= 7ea31ebf22n%40googlegroups.com=20 >>> >>> . >>> >> --=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/= cf54cf8a-72ae-4687-a2e5-5511d68542can%40googlegroups.com. ------=_Part_165115_1770387500.1746283011198 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable If you go look at the original muhash thread on the list there is some pret= ty extensive discussion around accumulators, including this point.=C2=A0 Bu= t I don't think it applies here because there is no reason for the salt to = be anything but unique and private to the user.

On Saturday, May 3, 2025 = at 2:26:18=E2=80=AFPM UTC Greg Maxwell wrote:
Hm. Fair point, bu= t 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.=C2=A0 It's essentially the same argument= you make for characteristic 2, it just takes more repetitions.=C2=A0 Witho= ut 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 point= ing out there is structure here you might not have expected.

=




On Sat, May 3, 2025 at 1= :42=E2=80=AFPM Ruben Somsen <= rso...@gmail.com> wrote:
=C2=A0 Hey all,


@Saint Wenhao
=

>if you take the sum of hashes, which should be fina= lly zero, then by grinding UTXOs, someone could make it zero

=
That's what the secret salt prevents. You can't grind fo= r a certain number if you don't know what the number is you are trying = to collide with.

>maybe you can avoid has= hing at all [...] And then, it is all about mixing the salt

<= /div>
Without a concrete solution I'm afraid that's wishful thi= nking. 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.


>What if instead of has= h we encrypt with AES

I can't really evaluate = whether this might work, but I can see the=C2=A0line of reasoning. Conceptu= ally, I think what we need is something that transforms the data into fixed= length blocks for which an attacker can't know the relationship betwee= n each block (i.e. via a secret). The transformation needs to be the same o= n the input and output side.



>Your redu= ction function could just be xor

I had initially r= uled XOR out. Reason for this is that XOR would lead one to conclude that s= ets [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 th= e 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 wit= h a quite expensive hash function that the IBD performance will be heavily = bottlenecked in network and parallelism related issues and be far from the = lowest hanging fruit for a while,=C2=A0 considering that this has eliminate= d the big sequential part and a number of annoying to optimize components e= ntirely

Very true, and as you said, we can easily = drop-in replace the hash function at any future point we like, without adve= rse consequences.


Cheers,
Ruben

On Sat, May 3, 2025 at 2:07=E2=80=AFPM Greg Maxwell <gmax...@gmail.com> wrote:
On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanjalkar wrote= :
> hash(UTXO_A||s= alt) + 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.=C2=A0

1. Sample random symmetric key `k`
2. I= nstead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) - AES(UTXO_D= ) =3D=3D 0 =3D>=C2=A0=C2=A0(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 operation= s but they are quite close).=C2=A0 I think that in many modes the collision= resistance would have to at least be restricted by the birthday bound with= the small block size. I think CMC might be needed to avoid that sort of is= sue.

=C2=A0

--
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 bitcoindev+...@googlegro= ups.com.
To view this discussion visit https= ://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a7ea31ebf2= 2n%40googlegroups.com.

--
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/cf54cf8a-72ae-4687-a2e5-5511d68542can%40googlegroups.com.
------=_Part_165115_1770387500.1746283011198-- ------=_Part_165114_873342410.1746283011198--