From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 03 May 2025 09:25:19 -0700 Received: from mail-oo1-f55.google.com ([209.85.161.55]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uBFfy-0001mP-An for bitcoindev@gnusha.org; Sat, 03 May 2025 09:25:19 -0700 Received: by mail-oo1-f55.google.com with SMTP id 006d021491bc7-604adec072esf2804619eaf.1 for ; Sat, 03 May 2025 09:25:18 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1746289512; cv=pass; d=google.com; s=arc-20240605; b=VAVeVsf+2gf5AtayCNUFAJ0MuhW3uVTlg8NWU8c0zr4s+FmClzGfPS8a73Cunvs44C 0WvNTnJaeukcVG7gkl5acfEy89bOX/vy2roCNZiVwODKTcw7lh0qtnO4bnc3+2zbleWE lvWvesdllsE56RMniIixSSG3vHKqsywlczq/GFzkZzFA2kjNcpRV5eVGx1TNSvP9ZSlz Evn+j1M9Q4awFZtmTPN5yxSyfrc383Z/252PtL5uWlD8A4pCTGn+byqR7T3TQHRmz6Nk 04ll+UV2+hhyAL6qOqmAs9UIr+O6Ct7O1UQs9VWezLfWuqIm3wnduVRijOiqR0pUX5Y2 qjOw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=rB2kvWPsWNE8hHjTqrfj+deYAMijoABVWa7vMKRIBv8=; fh=2kCYmnkygdoQCmUPOdooWHzTZOgZnAGDLuCZtU2AS2Q=; b=BFZld1VnW6S0QMyy+9EugNdMAqhohpPGIekKER2H80uqKdwoA10PyAtHu5795vgFjS L+xN4KRHANulRiXLeuJP/WdF+KaxEKd/43QPRFl28kj78OErX8bxFLe78EgxEY1SJnuk U01LbdMRa98ZqfLmInh1lduDxIWu7+WpLGTBxPSp/8KbvbBt5aoYT8RY4MXDnTVKrYJY gjXrV/Zr8lG9Nf3fxWlgnDc3i/yT5Ev0xcL4WJ0t5xMz8F/Rp5cvEvRDJ8B/R+8QppiK ujwj1YfnjMc/ApSpE/3jYtYXJQcjPU91dJF1abzKJHids9v3MtXtQGNdyhC5vdMSOtdD FqWg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=MZfrxNJe; spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::935 as permitted sender) smtp.mailfrom=rsomsen@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1746289512; x=1746894312; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=rB2kvWPsWNE8hHjTqrfj+deYAMijoABVWa7vMKRIBv8=; b=pUlVX2Lkfw8VUoE1OYy7aJDLAwzbc7zov3ZonvTG6uCN/wJxBeX968E8oTYLnyx3cw m+pO8+xSfhNjdSvQvegpeLWipX+03vOqzQeiNhSsxgGyrNTjAZZ1r4VmmX3VxMkEHxFy 1msDBoqaN+jt0j5+shQ7Xo4/8lixiL9uvZ07Ft3YBjKKe+jl4dRrPgsjOgYr79XrZ2rd qJZWM+UlARGWUMNk/eRpq9/BDcfutPYEWb4aio3tNZl6xS1t51J9RXuk7hHOqQDwzt0h dz77QYspNy4OCeNlCmnqelVDZBdW4k9tbh7y+yLXZCWhb/ma3fLuHVJilY4VFbxcG+7E fnAw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1746289512; x=1746894312; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=rB2kvWPsWNE8hHjTqrfj+deYAMijoABVWa7vMKRIBv8=; b=jUUib4QyXg/OJYsWqPdz+0R4hY9NCorVMIxYeGNZFuOC7kT5L9+jHRxvvWaRq4MM3i hKcJZgzJZPDzbYQ7QbclcAzgDrNMEf/OZXEsSI8sks/mTCg3ug+KB41xjeF9qdSdUcGS IX/OWlfrt9W1B6uXmeTNhQnqC7gkBR8FgpVmpF0ivfFttOUiKH2mePoZPT3O8EwEVQI/ u3TPLJxVocMdebxF0l5hrRSn5mOOtbrAywE7AR/mZzw2uHOINI/pEv1TMTCtA3Vc/JQK tRuPBiucPxqe0gWQBBdCrwiNrvsen7ldPRo/vYxn3CWt/4Zkau6At9xnPNZmKX54uyDY R6hA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746289512; x=1746894312; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:x-beenthere:x-gm-message-state:sender:from :to:cc:subject:date:message-id:reply-to; bh=rB2kvWPsWNE8hHjTqrfj+deYAMijoABVWa7vMKRIBv8=; b=QgDV2ZRrmZo6aUweuVxYvlID7uz+kw4VY+s6MtPgWl/qaaejtS2GC0ov/gI5f8cNFN v2DnrUVDNuEV/u1/mxxBBPN/lZyOBcPFE8s0YtPw0rauHOec+1M/B/SK0RaF1Tr6fPFB sRJZLydlsR+LcA9oJcO9Pr9Wp09UAWWH5IR5+NCbzw86JGbBfuzFiLwyqnG+qXUih5vt D7iFwZbWTXnvehx9f1AMt3j+hDXTxnpxDq4wKhCNLH1E/PcH3aN0EHqZwKaS7rOv2gm6 XrMigRWzfJ9KzSbEFbEsNo+i4ocmujHpksp52oM84JbMTT1EeJ2u0AlZLIQduBc5Giy6 6p8g== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCWmo6KxzIW6Mxu+dvjLcX9lnoBP7Cn1JbWgmbOcp+AqoHXg5dvWTieEM0zaKPjkAqQed80APQJcz+NO@gnusha.org X-Gm-Message-State: AOJu0Yx6WizMGHytXhBzxG8kizOgd2J/nXVul5oReTx8niTw8QT3UF4R drjgqABC2xS2+/0vE2V/rnG13UP5UIbYq1gD8ImPMIHqnhhfZF3h X-Google-Smtp-Source: AGHT+IH/4VhCyIP+dgTkM+pjkYX1+lVbC1uQKOAb3WfpV85uX3ukP3cUcJWwQmL/LHrctaeqQOCSYA== X-Received: by 2002:a4a:ee14:0:b0:606:9ed9:c38 with SMTP id 006d021491bc7-608000daa14mr811841eaf.0.1746289512501; Sat, 03 May 2025 09:25:12 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBGkXmwo8NLBPWWjBTP/j7YsW2DohP3YlTQxhATNwRZmBA== Received: by 2002:a05:6820:547:b0:606:44a0:510f with SMTP id 006d021491bc7-607ded83b2als1325120eaf.0.-pod-prod-09-us; Sat, 03 May 2025 09:25:09 -0700 (PDT) X-Received: by 2002:a05:6808:1449:b0:3f9:d5a2:8999 with SMTP id 5614622812f47-4035a5329f0mr705582b6e.3.1746289509826; Sat, 03 May 2025 09:25:09 -0700 (PDT) Received: by 2002:a05:6808:2109:b0:403:484c:9068 with SMTP id 5614622812f47-403484c9444msb6e; Sat, 3 May 2025 09:24:48 -0700 (PDT) X-Received: by 2002:a05:6a00:448a:b0:736:d297:164 with SMTP id d2e1a72fcca58-7406f08c282mr1990443b3a.1.1746289486978; Sat, 03 May 2025 09:24:46 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1746289486; cv=none; d=google.com; s=arc-20240605; b=K5ivX15/AxSrrlIRUFiykuvw/8zHlf4qp40YjmVaSXGwmcE+UNWCr9HP7+NrTtcwyv hrinFHexWz4v0mqU0eRNYAEscoG4LHtqmq6n97+Dh6xzMuNc/Jy1OQxC7Q6qtGC+M1FF 89cc1lHB+XdPHApp14JrSXrmWx/atoZVOdQyr9WgK69C2XLCNSntc5h/RhBdfQujHQyT gbNBgdikBj3ZSqxQEFSK5Q78dxYcE9Euvs+jre9GP7010wHfHkuyaJ3qqzYgp8hdpYMS O5l1ybqkkqRSjIWs6jWIC3UFDDNyD5FmaghjH+u6l5YlbGrP5yc9IB6qEBdpkThMcfWv hGWQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=Wl7Tis1xzN2ICJFrRDLUIED6IDj0mtz2ORdgyJmrZ8s=; fh=buJUvwPPgdi5Z5zmcvUt6NajLrOVgzwZz6n1oNFrtB8=; b=QSpP18QeyqbL8+ZIRv+yeB4ogzjtBZWjMhj+pITvKyRY6ob2c+MAmPCUCMij0BUEHc Uj+lUDuwN5vnQ+tnKBX2IKG/i5Df6zRrW+5K0nhnSAsuciUTd8knwYvKta6QGDE+/122 Q27iOvwqzjbY47zvoGoI7VflgjKv3dDP+EkVBBIOXjo3TqChQVKmbQCaIOoB/nnNxvjo ft+ZXfyhhGeapBtPOrlOmMnbET0nuIEtQ8fjQVj4Iyda17NenbSCyEKAuOaDY449YSar jbAbqLnt488k7GekYE2alJU3zAC7ximygC/950JqgqZIPYh4XEyGzPvbqjgQ+Y9fykoz 1fOA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=MZfrxNJe; spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::935 as permitted sender) smtp.mailfrom=rsomsen@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-ua1-x935.google.com (mail-ua1-x935.google.com. [2607:f8b0:4864:20::935]) by gmr-mx.google.com with ESMTPS id d2e1a72fcca58-7405909c038si44973b3a.6.2025.05.03.09.24.46 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 03 May 2025 09:24:46 -0700 (PDT) Received-SPF: pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::935 as permitted sender) client-ip=2607:f8b0:4864:20::935; Received: by mail-ua1-x935.google.com with SMTP id a1e0cc1a2514c-873a2ba6f7cso762798241.3 for ; Sat, 03 May 2025 09:24:46 -0700 (PDT) X-Gm-Gg: ASbGncvAqONEtTAxIcXB5gdmW9hKV6XpptCK8X9HuXvdKW6yhkxm4HBIA889zI0JgRk 1l6IhGoBaweXHb38m52jAtLlu/zRkM/t6BwSjCsgLrYoC3UL+8PR0ieQ6whbv3TMw7T3uni2x/e 2q71YIX9nSDt8/zB/ix52apYWZHq7/n/z2e3RlhQbfhcQwcdSvY/BUgEcp0NZabXq/7P0= X-Received: by 2002:a05:6102:8013:b0:4da:e6e9:1f56 with SMTP id ada2fe7eead31-4db1495be46mr770863137.23.1746289486001; Sat, 03 May 2025 09:24:46 -0700 (PDT) MIME-Version: 1.0 References: <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com> In-Reply-To: From: Ruben Somsen Date: Sat, 3 May 2025 18:24:36 +0200 X-Gm-Features: ATxdqUGBRUclh9BwFY30kbDzR-LYS3dQCZGZwzLqRMwP8oeRij5J7suHV71TL0U Message-ID: Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints To: Greg Maxwell Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="0000000000007cff9006343db40f" X-Original-Sender: rsomsen@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=MZfrxNJe; spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::935 as permitted sender) smtp.mailfrom=rsomsen@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.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 (/) --0000000000007cff9006343db40f Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Ah I see, interesting observation. That's something I hadn't considered as a potential problem if we truncated the hashes. On Sat, May 3, 2025 at 6:11=E2=80=AFPM Greg Maxwell wr= ote: > 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 > salt the size of the ring will do it. So for example, this is a break of > the passing suggestion of truncating to 32-bits (even 64-bits perhaps). Y= ou > include the transaction with unknown accumulator impact x 2^32 times. 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 >> >> A counter-example would be a chain with two transactions with the exact >> same input A and output B. SwiftSync with XOR would basically treat thes= e >> two transactions as non-existent (the two A's and B's cancel each other >> out), while a regular full node (or non-XOR SwiftSync) would reject the >> chain. >> >> On Sat, May 3, 2025 at 3:57=E2=80=AFPM Greg Maxwell = wrote: >> >>> 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 weakeni= ng >>> 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 3= 2 >>> bits or whatever, a practical number of A repeats would then self cance= l. >>> >>> To be clear I'm not arguing that it should be xor here, but pointing ou= t >>> there is structure here you might not have expected. >>> >>> >>> >>> >>> >>> On Sat, May 3, 2025 at 1:42=E2=80=AFPM Ruben Somsen = wrote: >>> >>>> 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 >>>> number 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 >>>> mixing 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 a= s 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 lin= e >>>> of reasoning. Conceptually, I think what we need 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 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 does= n't >>>> have this issue. If the speedup actually turns out to be significant t= hen >>>> 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 t= xid >>>> 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 re= lated >>>> issues and be far from the lowest hanging fruit for a while, consider= ing >>>> that this has eliminated the big sequential part and a number of annoy= ing >>>> 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. >>>> >>>> >>>> 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 = 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/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 mod= e >>>>> would be unsuitable! (I mean sure modular add/sub and xor are differe= nt >>>>> operations but they are quite close). I think that in many modes the >>>>> collision resistance would have to at least be restricted by the birt= hday >>>>> bound with the small block size. I think CMC might be needed to avoid= that >>>>> sort of issue. >>>>> >>>>> >>>>> >>>>> -- >>>>> 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, sen= d >>>>> an email to bitcoindev+...@googlegroups.com. >>>>> To view this discussion visit >>>>> https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-= 3a7ea31ebf22n%40googlegroups.com >>>>> >>>>> . >>>>> >>>> -- > 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 > email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit > https://groups.google.com/d/msgid/bitcoindev/a1e589d5-1bd9-4e4b-9824-db22= fda77646n%40googlegroups.com > > . > --=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/= CAPv7TjZes6F0%3DgMsM6t19H89AWVJ30jYTJqb4fmVMVRm0ZeD6w%40mail.gmail.com. --0000000000007cff9006343db40f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Ah I see, interesting observation. That's something I = hadn't considered as a potential problem if we truncated the hashes.
On Sat, May 3, 2025 at 6:11=E2=80=AFPM Greg Maxwell <= gmaxwell@gmail.com> wrote:
=
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 fe= west repeats to achieve that. But even if you don't know the salt the s= ize of the ring will do it.=C2=A0 So for example, this is a break of the pa= ssing suggestion of truncating to 32-bits (even 64-bits perhaps). You inclu= de 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 (wel= l A and its spend) thanks to TXID uniqueness

A counter-example would be a chain with two transactions with= the exact same input A and output B. SwiftSync with XOR would basically tr= eat these two transactions as non-existent (the two A's and B's can= cel each other out), while a regular full node (or non-XOR SwiftSync) would= reject the chain.

On Sat, May 3, 2025 at 3:57=E2=80=AFPM Greg Maxwell= <gmax...@gmail.com> wrote:
Hm. Fair po= int, 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 arg= ument, since A*n eventually collides.=C2=A0 It's essentially the same a= rgument you make for characteristic 2, it just takes more repetitions.=C2= =A0 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 w= hatever, 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 <rso...@gmail.c= om> wrote:
=C2=A0 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

Tha= t's what the secret salt prevents. You can't grind for a certain nu= mber if you don't know what the number is you are trying to collide wit= h.

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

With= out a concrete solution I'm afraid that's wishful thinking. That la= st part of the sentence is why we currently need the hash, as well as for a= dding more data in the non-assumevalid version.


>What if instead of hash we encrypt w= ith AES

I can't really evaluate whether this m= ight 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 attacker can't know the relationship between each block (= i.e. via a secret). The transformation needs to be the same on the input an= d output side.



>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 ca= ncel each other out, regardless of whether the sets are on the input or out= put side. Modular add/sub doesn't have this issue. If the speedup actua= lly turns out to be significant then there may be some clever way to salvag= e 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 expe= nsive hash function that the IBD performance will be heavily bottlenecked i= n 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 sequ= ential part and a number of annoying to optimize components entirely
<= div>
Very true, and as you said, we can easily drop-in replac= e the hash function at any future point we like, without adverse consequenc= es.


Cheers,
Ruben

On= Sat, May 3, 2025 at 2:07=E2=80=AFPM Greg Maxwell <g= max...@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/subs? I cannot prov= e 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; AES_k(UTXO_A) + AES= _k(UTXO_B) - AES_k(UTXO_C) - AES(UTXO_D) =3D=3D 0 =3D>=C2=A0=C2=A0(provi= ng (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).=C2=A0 I= think that in many modes the collision resistance would have to at least b= e restricted by the birthday bound with the small block size. I think CMC m= ight 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+...@googlegroups.com.
To view this discussion visit htt= ps://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a7ea31eb= f22n%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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.googl= e.com/d/msgid/bitcoindev/a1e589d5-1bd9-4e4b-9824-db22fda77646n%40googlegrou= ps.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/bitcoindev/CAPv7TjZes6F0%3DgMsM6t19H89AWVJ30jYTJqb4fmVMVRm0ZeD6w%40ma= il.gmail.com.
--0000000000007cff9006343db40f--