path: root/75/215d5605c0ef147418289e5b2f0d1dcfac025f

Delivery-date: Sat, 03 May 2025 07:56:20 -0700
Received: from mail-oo1-f59.google.com ([209.85.161.59])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBCMIFYEXXQGRBCO53DAAMGQEDYC7PDY@googlegroups.com>)
	id 1uBEHr-0001qu-7a
	for bitcoindev@gnusha.org; Sat, 03 May 2025 07:56:20 -0700
Received: by mail-oo1-f59.google.com with SMTP id 006d021491bc7-60601184d87sf2230916eaf.1
        for <bitcoindev@gnusha.org>; Sat, 03 May 2025 07:56:19 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1746284173; cv=pass;
        d=google.com; s=arc-20240605;
        b=Cw9p83rAlDQ/c7f0DLvq64Lg18tv6N1uMhAGTzodqebvGSTEV2gbaxfxR7YqkDNOyG
         Ti23eu7xl58vMXRgEiIFnGOqsqwOnVgFn/j6xgkrggxuTVeIN/8Fx9ErY7zimZ27wL6P
         GPS9cTWlvQMVnbQx+0kRa2I/vcid2y96nxnf+AZUIuMhOuUs6lDD5uGvwLbsWrQvkJFo
         zlHW8QWDldpLxh2cF/W7wb1O21QxMj5A4JvoIPELBtdP5M6ljYz+XpT3KGTd8Xxhl59o
         MOo0LaazzCtIrqvtcRe874qsS+wy5gMT3BBEWIwMsIT5rb7LGG/K4kiO5TKhOg7Sepht
         yIWw==
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=Qj2xDEAgWWMaUUlphYIzArusdFKDf84kYdLnVGycTsk=;
        fh=6K2U+ITeXq3rk/PT1qBmRjhItgWIdq1EbMOo9Ib8ot0=;
        b=lQGT4ZBXS8tyO0tiYNA76NZ5ykxg+U630x5zFoNoerSt1xsyAMCzeYXtTRFvwgjdJ8
         XjSFwYJM2Ath40itbozQ7X9EEvRhjDB5o3rOBRrNZo5UTSKyOCpehA1/OiHN2kTq1Ty2
         QIPxxFbNtW0O9nIU6tArmfNvplyCrDJJ5QVdmWCsbm0K9svy7JxE1ArzEeuGK41haDeR
         sW+fScP2dtU0a3GJXf8b5pZwQpSkTmyHmcTx3kOhpXo4y4ORhbn9pBi060jabjJhs97x
         WcdJzCq2PHXfsqvZxSiNorgS0VQQMeACSKZ6JdRo4L6CtdI5K4mjj6wkkh3vEscnURdk
         3wtA==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Un1M7ifq;
       spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92c 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=1746284173; x=1746888973; 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=Qj2xDEAgWWMaUUlphYIzArusdFKDf84kYdLnVGycTsk=;
        b=PCyXZCXzhURMyDrkiHR1ZsMHOpwfYrRn2uB4rLJplYZXwsjU33mevXnuCeJ7JLE47I
         b8AkDBwWUTXLjdOIwA5ypIjD+5nbI9IAxUXTo5sFFfuFD62oanEmD9sOimKOo0uoURx2
         /Ep2St/rSU8wFXqX7vLeTIPE3d4eo5i45dKQnQvNYVigeNqqUqVZc8eFwYuyuShH7FPa
         drsDIW752LQck34FopBzX/PxbjDG03FN0ljmJyZvO90F7iQjgkygMouObexEHyY+tjq9
         fbHu02IC2ISQPmsbpoxgraUS3H4ucXY9+S/vz7YK983bSnvMweEaPr/sTpzSdXNJNS/u
         AY+g==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1746284173; x=1746888973; 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=Qj2xDEAgWWMaUUlphYIzArusdFKDf84kYdLnVGycTsk=;
        b=hVbD967c2QFcE2S/yQke3xxQuKWb7PUVJGFANzj5+TssnAire9VIDIDYAS1Rv537YF
         pDuC+m9zoQcR55sB2qlUAa4hl0SLUTWIzdCs/ms4B56QAZb/BI/DT367CetaRkHsjbPo
         KjfjdAWQaVUFIH3MqAFJ7/661wC35XkdNb+eaU+QRiFQuho3RzFSWafAV0hL1G54SXBh
         a+BJoZqLvf3+6xWdCuycz/crYEWjKg1BEEw5WwzJx8rmzS2aQTUdczdsAH3Y++LYDyHb
         hEPn6nH03mMfe5IZ8sRCTwHhvjln9p8fUertof+aZWJ/SIVIyaj/FNqmVC8n0kEfwniH
         dEfQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1746284173; x=1746888973;
        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=Qj2xDEAgWWMaUUlphYIzArusdFKDf84kYdLnVGycTsk=;
        b=mQNe5OIaGMOn7euwy5aD/rODPL/mZxvnDeJototDjoG2WgsTvR3PD9CnQG5rjRbjCK
         NYWdK3Qv/2PbWXxlPK0ugicQf7hFopHatKNPZ2PzXqgXdLSRzsmbiq3/Cx6GhdTYV64D
         fL3ISefc0qjHWssM93eJrCH4+mYGCdG9SaxT9jdYPGsuWDepUfm+0lQhBGkdSJmK0ozC
         JPN+Ov4yoGjushbiIIUaIu7G5P5nfLhk3X6Dm7Ertr2aBqNBnM8++gRfQ+51BuFIU3Xa
         eI9XiEzegL6xWFvnNjsueyf7CTJLkevF9RyOl0MCxh0Ob3NST15r0FfwXl5lRjYqwUdx
         mLTg==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUqxu7/S8FkCcbvhBwzynZQbssqTAbhYazOFHOU+hLmfWmvmTZT7iLyn6tfFcnM9G3UzkmwY7huKtEx@gnusha.org
X-Gm-Message-State: AOJu0YxZMesFICgKk2cbxMlMuiHlhOZiF/SAlvXpLFQ2MHuqhe3nK+se
	PXrHOu6F5zX+BRwS1Oy123G8xnhaQqV1AspbmWjmzQZE5p69/oAz
X-Google-Smtp-Source: AGHT+IEdleS5lhXkko3iQu2eTriSWa5fjmFC+nF6M8mC3I7ZqaAaKmKWF5ThghnFq2sS9Z3Qnn/5Xw==
X-Received: by 2002:a05:6820:2607:b0:606:d85b:570e with SMTP id 006d021491bc7-608002d2e7dmr743477eaf.3.1746284173128;
        Sat, 03 May 2025 07:56:13 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBEpul740l6oot2cfeX8msUIb8KpGKETwCrcoSGRMsTFiA==
Received: by 2002:a4a:d342:0:b0:604:4e1e:cf36 with SMTP id 006d021491bc7-607ded8a7fals731612eaf.0.-pod-prod-08-us;
 Sat, 03 May 2025 07:56:09 -0700 (PDT)
X-Received: by 2002:a05:6808:180b:b0:403:31a4:f3fa with SMTP id 5614622812f47-4035a5d55f7mr578268b6e.35.1746284169134;
        Sat, 03 May 2025 07:56:09 -0700 (PDT)
Received: by 2002:a05:6808:2109:b0:403:484c:9068 with SMTP id 5614622812f47-403484c9444msb6e;
        Sat, 3 May 2025 07:55:41 -0700 (PDT)
X-Received: by 2002:a05:6830:3509:b0:72b:9d5e:9465 with SMTP id 46e09a7af769-731eadc3e3fmr800122a34.13.1746284141329;
        Sat, 03 May 2025 07:55:41 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1746284141; cv=none;
        d=google.com; s=arc-20240605;
        b=VI3Awp/d1p5ilQx8j5IQjhwqTlsGemKqomfDXH46FW5lVeAldvQqJ3ichNUjkizoCD
         sa55EJoBXo1neAUaDp+/AwuFQhDhP+s7bsz/FJFY5DKPjxkh85Va4Smrjuh4bVeH/1rR
         tErDMqX7INGFRGEkZLkUp+TgzJvcwbEKTSvQ8l9X4I41M3h6yBXHv4MR5kJrXM2/52nA
         igaygSyspjRciXB+MUQe4ffpnRp98Zt9nIuTsa3b9pszhXi99iWJjfjUIUzNoyFKpuE8
         72OkoXf1xeiM85PfzfecqMmZh70Q6HKykBUseNyg4ziMaFzjGR8+4oU3Ej3HpomibrLI
         O5Ag==
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=XprJky5uJ7S8NyTMEEMB0EMHN7ymOPLupUZe2V26f4k=;
        fh=bT0+ezvs49vdD1SeY+yzcDniAQC6Cl2XZw1XudLmSuw=;
        b=ZTxW8BfnzvnLBiaJKx6serphndb4QSEVIGLNEOJNjufbbtnQEr2sd2wSoJF3yHzsey
         OBuz4ED80OkdNnN2jzPM7LTvL7Cdhyg03lsxw51hP8i5ywmFIu9vnYOUE/brOpbAe5GY
         iDqDmCKH/fgNnVS/bcKbejhcWKy+3nGKpxsZpPOdJNWdWVeU8ieixKCcrlJ0soR1DiCP
         mgTkOaOphWWTSnsvtU2lWYxN7xP5ZtKIfs5NJNbChIH0vFqNfwR90pjQmxaRRKAuFm2W
         Bw0DZNVzMjcMFEpKfF1Ep1rZgCFu8rM/fbHGNN8da0lUdqG+1X1kIkXeBYgnlii63BXk
         TOGg==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Un1M7ifq;
       spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92c 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-x92c.google.com (mail-ua1-x92c.google.com. [2607:f8b0:4864:20::92c])
        by gmr-mx.google.com with ESMTPS id 46e09a7af769-731d309d779si96965a34.0.2025.05.03.07.55.41
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Sat, 03 May 2025 07:55:41 -0700 (PDT)
Received-SPF: pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92c as permitted sender) client-ip=2607:f8b0:4864:20::92c;
Received: by mail-ua1-x92c.google.com with SMTP id a1e0cc1a2514c-86d3907524cso809411241.0
        for <bitcoindev@googlegroups.com>; Sat, 03 May 2025 07:55:41 -0700 (PDT)
X-Gm-Gg: ASbGncubeTKZBp2my5MLfXSml1PQ/ZRblC27XkL591QzTdXtyUB0IIFe7l/o/1vEVav
	aX6Nr5lc8a/Z6WOmbhxXvsTKC2kUpUDXp8jWZ0SZcGDXeIU8yOLMMsOFoNNHPm9ikHYMN41QpCn
	e1i0emELHKbRKu2ROifQidSgUaN8LoYA7SB+5mL71MNP52FYioKcOJwngNB2p2mfBjJMk=
X-Received: by 2002:a05:6102:8015:b0:4c3:c9:c667 with SMTP id
 ada2fe7eead31-4db14988226mr627610137.24.1746284140436; Sat, 03 May 2025
 07:55:40 -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>
In-Reply-To: <CAAS2fgQ1CvyxoRckZT2_6dNgKxDaKWvuK46FYMeaHc8Np_gDPg@mail.gmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Sat, 3 May 2025 16:55:31 +0200
X-Gm-Features: ATxdqUFcALki_Duqt2zhcF2OuTcQ0mBuE6P1x81xuedDN9twJTO2NPooV2VRu1k
Message-ID: <CAPv7TjZ_Z_zvBVnH2fH9EeSbOaVuvrVvHsuQD1bOmVq72uc2JA@mail.gmail.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Cc: Greg Maxwell <gmaxwell@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000de247906343c75b2"
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=Un1M7ifq;       spf=pass
 (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92c 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 (/)

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

>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 these
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 <gmaxwell@gmail.com> wr=
ote:

> 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 t=
he
> 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> w=
rote:
>
>>   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 wi=
th.
>>
>> >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 las=
t
>> 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
>> 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 on=
e
>> 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 the=
n
>> 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 txi=
d
>> 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 rela=
ted
>> issues and be far from the lowest hanging fruit for a while,  considerin=
g
>> that this has eliminated the big sequential part and a number of annoyin=
g
>> 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 <gmaxwell@gmail.com>=
 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) -
>>> 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
>>> 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 birthd=
ay
>>> bound with the small block size. I think CMC might be needed to avoid t=
hat
>>> 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, send
>>> an email to bitcoindev+unsubscribe@googlegroups.com.
>>> To view this discussion visit
>>> https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a=
7ea31ebf22n%40googlegroups.com
>>> <https://groups.google.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3=
a7ea31ebf22n%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/=
CAPv7TjZ_Z_zvBVnH2fH9EeSbOaVuvrVvHsuQD1bOmVq72uc2JA%40mail.gmail.com.

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

<div dir=3D"ltr">&gt;I think you cannot escape the assumption that A is uni=
que (well A and its spend) thanks to TXID uniqueness<div><br></div><div>A c=
ounter-example would be a chain with two transactions with the exact same i=
nput A and output B. SwiftSync with XOR would basically treat these two tra=
nsactions as non-existent (the two A&#39;s and B&#39;s cancel each other ou=
t), while a regular full node (or non-XOR SwiftSync) would reject the chain=
.</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 3:57=E2=80=AFPM Greg M=
axwell &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;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr"><div>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 w=
eakening the security argument, since A*n eventually collides.=C2=A0 It&#39=
;s essentially the same argument you make for characteristic 2, it just tak=
es more repetitions.=C2=A0 Without knowing the salt you&#39;d need 2^256 re=
petitions to be certain, but e.g. see the prior suggestions on truncating t=
he hash to 32 bits or whatever, 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 n=
ot have expected.</div><div><br></div><div><br></div><div><br></div><div><b=
r></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmai=
l_attr">On Sat, May 3, 2025 at 1:42=E2=80=AFPM Ruben Somsen &lt;<a href=3D"=
mailto:rsomsen@gmail.com" target=3D"_blank">rsomsen@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);padding-left:1ex"><div dir=3D"lt=
r">=C2=A0 Hey all,<div><br></div><div><br></div><div><a class=3D"gmail_plus=
reply" id=3D"m_5845153051774357764m_7194414729081378160gmail-plusReplyChip-=
0">@Saint Wenhao</a><br><div><br></div><div>&gt;if you take the sum of hash=
es, which should be finally zero, then by grinding UTXOs, someone could mak=
e 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 n=
umber is you are trying to collide with.</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>Without a concrete solution I&#39;m afrai=
d that&#39;s wishful thinking. That last part of the sentence is why we cur=
rently need the hash, as well as for adding more data in the non-assumevali=
d version.</div><div><br></div><div><br></div><div><a class=3D"gmail_plusre=
ply" id=3D"m_5845153051774357764m_7194414729081378160plusReplyChip-0">@Sank=
et Kanjalkar</a><br></div><div><br></div><div>&gt;What if instead of hash w=
e encrypt with AES</div><div><br></div><div>I can&#39;t really evaluate whe=
ther this might work, but I can see the=C2=A0line of reasoning. Conceptuall=
y, I think what we need is something that transforms the data into fixed le=
ngth blocks for which an attacker can&#39;t know the relationship between e=
ach block (i.e. via a secret). The transformation needs to be the same on t=
he input and output side.</div><div><br></div><div><a class=3D"gmail_plusre=
ply"><br></a></div><div><a class=3D"gmail_plusreply" id=3D"m_58451530517743=
57764m_7194414729081378160plusReplyChip-2">@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. ar=
e all equivalent because any two values cancel each other out, regardless o=
f whether the sets are on the input or output side. Modular add/sub doesn&#=
39;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 n=
umber of inputs and outputs and relying on the knowledge that every txid mu=
st be unique, but that&#39;s a lot harder to reason 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 network and parallelism related=
 issues and be far from the lowest hanging fruit for a while,=C2=A0 conside=
ring that this has eliminated the big sequential part and a number of annoy=
ing 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"_bla=
nk">gmaxwell@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,2=
04);padding-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=
"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-le=
ft:1ex"><div dir=3D"ltr">&gt; hash(UTXO_A||salt) + hash(UTXO_B||salt) - has=
h(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=
 prove it; but I also don&#39;t see a clear way this is broken.=C2=A0<br><b=
r>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(=
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 CTR mode is, I&#39;m not sure =
about other modes? Obviously CTR mode would be unsuitable! (I mean sure mod=
ular 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 le=
ast be restricted by the birthday bound with the 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>
</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/CAPv7TjZ_Z_zvBVnH2fH9EeSbOaVuvrVvHsuQD1bOmVq72uc2JA%40mail.gmail=
.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/ms=
gid/bitcoindev/CAPv7TjZ_Z_zvBVnH2fH9EeSbOaVuvrVvHsuQD1bOmVq72uc2JA%40mail.g=
mail.com</a>.<br />

--000000000000de247906343c75b2--