From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 03 May 2025 09:11:45 -0700 Received: from mail-yw1-f187.google.com ([209.85.128.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uBFSp-000605-QX for bitcoindev@gnusha.org; Sat, 03 May 2025 09:11:45 -0700 Received: by mail-yw1-f187.google.com with SMTP id 00721157ae682-708ac47ab8asf44111837b3.1 for ; Sat, 03 May 2025 09:11:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1746288698; x=1746893498; 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=s5xcEVWmVJIrMuxmHgdvbR4d8PoaOz/SsVbV1DExlkE=; b=eIR41akcVPhTWpXeDeqq6WvZtxzwR6A67V0zdbwoTPb+CuZ01zgRkoQcSKMG/KN+G4 u4lOEBuJ9S9+ti8l7w93unfDHGUIZ91R1s6CJin45hbrOwR1hkGojHZJiKNLakqSaq2G dyCOhwjjc6yHMIjwkbZaZnZHkFFuFZpb87WVpaHxJ4deXJrzfanWHNdfUpLVIXPEU5R5 XLwY+GaJd/ZddafkxKxBmgZKk+CbRSMwQILQnFAtvtyF7KDEbOrD3c7nf7WI8foWfE36 8zk8sN1Rlk5RmZ83MBD2zkbLttzrLjnw7A3dIUoDsJfS0hSkU/UYfe80LnUbfAQ4Wvn0 RUMA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1746288698; x=1746893498; 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=s5xcEVWmVJIrMuxmHgdvbR4d8PoaOz/SsVbV1DExlkE=; b=WXaFAmPaDdDvCZMtmrRFmf99LHKPwvz7YPuFyla/mYO8NFExKAIko5NvuaH9MGeg2m Aakpq1PSU63fDEArDLqEFpaPNzxMtjtTAtpQkvtoviVO7lkr0c747io6THz8TAs9Scbs n2HP+IKTfXebIb+0e0Gn9lTf6xy58odYdud3E7qKaXdOnINcJrhnU4atx37VaZ3MxK+V G01U4dRCjRhwVzIDH2NiFEOAN8PsftNmWMuCREMYardImyFPcK0SSXtvODmr8/3Ut1+J wRvqgrl0SFs2+9PeZ0x/OVkJoM1ZMpJsCrC2e6M4d6UmP2ZeVd8XPifmW1B1UR9O6LOZ OKuw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746288698; x=1746893498; 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=s5xcEVWmVJIrMuxmHgdvbR4d8PoaOz/SsVbV1DExlkE=; b=q5bS9z+BmDEouoObxrw1XmYiaxoYGwjoMlML/NpgZIoEGCGsSsuOrI0tyvIfUsnEyh oKoND7D8Uz+OuzKVBwy0sMxa2F9nZUhzhlxr7xBB59EcHTn339oF3Fj5O/fl/0g9Kf/Q DnHHkjupW7Pf4+ww9zKH3OubSv+X8gnCpznaiWQjuXW5Gn+WiFXywVjhzJyees5G2L85 xykkThBanfJzLE7XQRgzuueIKBv13f4VHcNPlJ1O0tulp9azZeYsrVBS47RzfmTXE/io dtAwUvxao4rZ0t+GgPFLjGJ843NgWzRjM73Kn3PGlC6+1uSaQB88rP/YdD0oT3uz23Ty LYbg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXuc77VhOfNc07552F2onhCRP1ElIkAG9hLXNwJuGuWk9DalVZAit0+j16emMvfojkW6bRemkulNTQe@gnusha.org X-Gm-Message-State: AOJu0YwKq85qHWrR4iuZujHBf0mas41Av5VnEiROrlgzClLdCcP+DViR Yv1o6H7u052SZ3tx4r446SeoF8KL2DPKxMt/iGtoeMPY7gkrJ9n0 X-Google-Smtp-Source: AGHT+IGo6DHdwRIHpV92ikT63RAuAJnWdMOUMODBTAdqCXflNCKe6HzBzxPT+ZEDJ671bYgTeWif5A== X-Received: by 2002:a05:6902:2808:b0:e6d:f0df:9806 with SMTP id 3f1490d57ef6-e757d35150amr1860825276.31.1746288697885; Sat, 03 May 2025 09:11:37 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBEbRXj2TXn783JZM87jPN27tYOyms+QcgGrhSCcKzsUEg== Received: by 2002:a25:e0c3:0:b0:e74:6669:e88f with SMTP id 3f1490d57ef6-e74dc5d0ac8ls54524276.1.-pod-prod-02-us; Sat, 03 May 2025 09:11:34 -0700 (PDT) X-Received: by 2002:a05:690c:c03:b0:708:c2dd:c39f with SMTP id 00721157ae682-708e11cc1ebmr37865487b3.17.1746288694315; Sat, 03 May 2025 09:11:34 -0700 (PDT) Received: by 2002:a81:8544:0:b0:6fd:27d2:c7f1 with SMTP id 00721157ae682-708cfcbcea0ms7b3; Sat, 3 May 2025 08:54:23 -0700 (PDT) X-Received: by 2002:a05:690c:316:b0:6ef:652b:91cf with SMTP id 00721157ae682-708e13438femr42071507b3.27.1746287661406; Sat, 03 May 2025 08:54:21 -0700 (PDT) Date: Sat, 3 May 2025 08:54:20 -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_193184_1016769850.1746287660733" 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_193184_1016769850.1746287660733 Content-Type: multipart/alternative; boundary="----=_Part_193185_1808050734.1746287660733" ------=_Part_193185_1808050734.1746287660733 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Understood. My point was that this exists with the additive type too, If=20 you repeat it N times it will cancel. If the salt isn't known you don't=20 know the fewest repeats to achieve that. But even if you don't know the=20 salt the size of the ring will do it. So for example, this is a break of= =20 the passing suggestion of truncating to 32-bits (even 64-bits perhaps). You= =20 include the transaction with unknown accumulator impact x 2^32 times. x *= =20 2^32 % 2^32 =3D 0. On Saturday, May 3, 2025 at 2:56:13=E2=80=AFPM UTC Ruben Somsen wrote: > >I think you cannot escape the assumption that A is unique (well A and it= s=20 > spend) thanks to TXID uniqueness > > A counter-example would be a chain with two transactions with the exact= =20 > same input A and output B. SwiftSync with XOR would basically treat these= =20 > two transactions as non-existent (the two A's and B's cancel each other= =20 > out), while a regular full node (or non-XOR SwiftSync) would reject the= =20 > chain. > > On Sat, May 3, 2025 at 3:57=E2=80=AFPM Greg Maxwell w= rote: > >> 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 weakenin= g=20 >> the security argument, since A*n eventually collides. It's essentially = the=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 b= e=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 w= rote: >> >>> 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 w= ith. >>> >>> >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=20 >>> last 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= =20 >>> one 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 th= en=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 tx= id=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 rel= ated=20 >>> issues and be far from the lowest hanging fruit for a while, consideri= ng=20 >>> that this has eliminated the big sequential part and a number of annoyi= ng=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 w= rote: >>>> >>>> > 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= =3DD && 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=3D= D && 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 differen= t=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 birth= day=20 >>>> bound with the small block size. I think CMC might be needed to avoid = that=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-3= a7ea31ebf22n%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/= a1e589d5-1bd9-4e4b-9824-db22fda77646n%40googlegroups.com. ------=_Part_193185_1808050734.1746287660733 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Understood. My point was that this exists with the additive type too, = If you repeat it N times it will cancel. If the salt isn't known you don't = know the fewest repeats to achieve that. But even if you don't know the sal= t the size of the ring will do it.=C2=A0 So for example, this is a break of= the passing suggestion of truncating to 32-bits (even 64-bits perhaps). Yo= u include the transaction with unknown accumulator impact x 2^32 times.=C2= =A0=C2=A0 x * 2^32 % 2^32 =3D 0.





On Saturday, May 3, 2025 at 2:56:13=E2=80=AFPM = UTC Ruben Somsen wrote:
>I think you cannot escape the assumption = that A is unique (well A and its spend) thanks to TXID uniqueness

<= /div>
A counter-example would be a chain with tw= o transactions with the exact same input A and output B. SwiftSync with XOR= would basically treat these two transactions as non-existent (the two A= 9;s and B's cancel each other out), while a regular full node (or non-X= OR SwiftSync) would reject the chain.

On Sat, May 3, 2025 at 3:57=E2= =80=AFPM Greg Maxwell <gmax..= .@gmail.com> wrote:
Hm. Fair point, but I think you cannot esc= ape the assumption that A is unique (well A and its spend) thanks to TXID u= niqueness without weakening the security argument, since A*n eventually col= lides.=C2=A0 It's essentially the same argument you make for characteri= stic 2, it just takes more repetitions.=C2=A0 Without knowing the salt you&= #39;d need 2^256 repetitions to be certain, but e.g. see the prior suggesti= ons 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 structu= re here you might not have expected.





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


@Saint Wenhao

>= if you take the sum of hashes, which should be finally zero, then by grindi= ng UTXOs, someone could make it zero

That's wh= at the secret salt prevents. You can't grind for a certain number if yo= u don't know what the number is you are trying to collide with.

>maybe you can avoid hashing at all [...] And th= en, it is all about mixing the salt

Without a conc= rete 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
<= /div>

>What if instead of hash we encrypt with AES

I can't really evaluate whether this might work,= but I can see the=C2=A0line of reasoning. Conceptually, I think what we ne= ed is something that transforms 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 s= ide.



>Your reduction function could jus= t 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 knowl= edge 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 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 eliminated the big sequential par= t and a number of annoying to optimize 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.
<= div>

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||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/sub= s? 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. Instead of above; AE= S_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= 9;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 qui= te 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 s= ize. I think CMC might be needed to avoid that sort of issue.
=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/a1e589d5-1bd9-4e4b-9824-db22fda77646n%40googlegroups.com.
------=_Part_193185_1808050734.1746287660733-- ------=_Part_193184_1016769850.1746287660733--