path: root/d8/c50e756e68e0d9e6ba027c8ae24c623bf709e1

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 <bitcoindev+bncBCMIFYEXXQGRBZUG3HAAMGQEN22ER4Y@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <bitcoindev@googlegroups.com>
        (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 <bitcoindev@googlegroups.com>; 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: <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>
 <CAAS2fgQ1CvyxoRckZT2_6dNgKxDaKWvuK46FYMeaHc8Np_gDPg@mail.gmail.com>
 <CAPv7TjZ_Z_zvBVnH2fH9EeSbOaVuvrVvHsuQD1bOmVq72uc2JA@mail.gmail.com> <a1e589d5-1bd9-4e4b-9824-db22fda77646n@googlegroups.com>
In-Reply-To: <a1e589d5-1bd9-4e4b-9824-db22fda77646n@googlegroups.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Sat, 3 May 2025 18:24:36 +0200
X-Gm-Features: ATxdqUGBRUclh9BwFY30kbDzR-LYS3dQCZGZwzLqRMwP8oeRij5J7suHV71TL0U
Message-ID: <CAPv7TjZes6F0=gMsM6t19H89AWVJ30jYTJqb4fmVMVRm0ZeD6w@mail.gmail.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
To: Greg Maxwell <gmaxwell@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
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: <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 (/)

--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 <gmaxwell@gmail.com> 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 <gmax...@gmail.com> =
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 <rso...@gmail.com> =
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 <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/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
>>>>> <https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb=
-3a7ea31ebf22n%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter>
>>>>> .
>>>>>
>>>> --
> 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
> <https://groups.google.com/d/msgid/bitcoindev/a1e589d5-1bd9-4e4b-9824-db2=
2fda77646n%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/=
CAPv7TjZes6F0%3DgMsM6t19H89AWVJ30jYTJqb4fmVMVRm0ZeD6w%40mail.gmail.com.

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

<div dir=3D"ltr">Ah I see, interesting observation. That&#39;s something I =
hadn&#39;t considered as a potential problem if we truncated the hashes.</d=
iv><br><div class=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" cl=
ass=3D"gmail_attr">On Sat, May 3, 2025 at 6:11=E2=80=AFPM Greg Maxwell &lt;=
<a href=3D"mailto:gmaxwell@gmail.com">gmaxwell@gmail.com</a>&gt; wrote:<br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left:1px solid rgb(204,204,204);padding-left:1ex"><div>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&#39;t known you don&#39;t know the fe=
west repeats to achieve that. But even if you don&#39;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.</div><div><br></div><div><br></div><div><br></di=
v><div><br></div><br><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"=
gmail_attr">On Saturday, May 3, 2025 at 2:56:13=E2=80=AFPM UTC Ruben Somsen=
 wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr">&gt;I think you cannot escape the assumption that A is unique (wel=
l A and its spend) thanks to TXID uniqueness<div><br></div></div><div dir=
=3D"ltr"><div>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&#39;s and B&#39;s can=
cel each other out), while a regular full node (or non-XOR SwiftSync) would=
 reject the chain.</div></div><br><div class=3D"gmail_quote"><div dir=3D"lt=
r" class=3D"gmail_attr">On Sat, May 3, 2025 at 3:57=E2=80=AFPM Greg Maxwell=
 &lt;<a rel=3D"nofollow">gmax...@gmail.com</a>&gt; wrote:<br></div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px=
 solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>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&#39;s essentially the same a=
rgument you make for characteristic 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 suggestions on truncating the hash to 32 bits or w=
hatever, a practical number of A repeats would then self cancel.</div><div>=
<br></div><div>To be clear I&#39;m not arguing that it should be xor here, =
but pointing out there is structure here you might not have expected.</div>=
<div><br></div><div><br></div><div><br></div><div><br></div></div><br><div =
class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, May 3, =
2025 at 1:42=E2=80=AFPM Ruben Somsen &lt;<a rel=3D"nofollow">rso...@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" rel=3D"nofollow">@Saint Wenhao</a><br><div><br></div=
><div>&gt;if you take the sum of hashes, which should be finally zero, then=
 by grinding UTXOs, someone could make it zero</div><div><br></div><div>Tha=
t&#39;s what the secret salt prevents. You can&#39;t grind for a certain nu=
mber if you don&#39;t know what the number is you are trying to collide wit=
h.</div><div><br></div></div><div>&gt;maybe you can avoid hashing at all [.=
..] And then, it is all about mixing the salt</div><div><br></div><div>With=
out a concrete solution I&#39;m afraid that&#39;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.</div><div><br></div><div><b=
r></div><div><a class=3D"gmail_plusreply" rel=3D"nofollow">@Sanket Kanjalka=
r</a><br></div><div><br></div><div>&gt;What if instead of hash we encrypt w=
ith AES</div><div><br></div><div>I can&#39;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&#39;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.</div><div><br></div><div><a class=3D"gmail_plusreply" rel=3D=
"nofollow"><br></a></div><div><a class=3D"gmail_plusreply" rel=3D"nofollow"=
>@Greg Maxwell</a><br></div><div><br></div><div>&gt;Your reduction function=
 could just be xor</div><div><br></div><div>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&#39;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&#39;s a lot harder =
to reason about.</div><div><br></div><div>&gt;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><=
div><br></div><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.</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 rel=3D"nofollow">g=
max...@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" =
style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pa=
dding-left:1ex"><div><div dir=3D"auto">On Saturday, May 3, 2025 at 11:55:28=
=E2=80=AFAM UTC Sanket Kanjalkar wrote:<br></div><blockquote style=3D"margi=
n:0px 0px 0px 0.8ex;border-left:1px solid rgb(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 (proving (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 prov=
e it; but I also don&#39;t see a clear way this is broken.=C2=A0<br><br>1. =
Sample random symmetric key `k`<br>2. Instead 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(provi=
ng (A=3D=3DC &amp;&amp; B=3D=3DD) || (A=3D=3DD &amp;&amp; B=3D=3DC))?</div>=
</blockquote><div><br></div><div>AES in CTR 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 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.</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 rel=3D"nofollow">bitcoindev+...@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" rel=3D"nofollow" target=3D"_blank">htt=
ps://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a7ea31eb=
f22n%40googlegroups.com</a>.<br>
</blockquote></div>
</blockquote></div>
</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" target=
=3D"_blank">bitcoindev+unsubscribe@googlegroups.com</a>.<br>
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/a1e589d5-1bd9-4e4b-9824-db22fda77646n%40googlegroups.com?utm_med=
ium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">https://groups.googl=
e.com/d/msgid/bitcoindev/a1e589d5-1bd9-4e4b-9824-db22fda77646n%40googlegrou=
ps.com</a>.<br>
</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/CAPv7TjZes6F0%3DgMsM6t19H89AWVJ30jYTJqb4fmVMVRm0ZeD6w%40mail.gma=
il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/=
msgid/bitcoindev/CAPv7TjZes6F0%3DgMsM6t19H89AWVJ30jYTJqb4fmVMVRm0ZeD6w%40ma=
il.gmail.com</a>.<br />

--0000000000007cff9006343db40f--