From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 03 May 2025 06:47:05 -0700 Received: from mail-oi1-f189.google.com ([209.85.167.189]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uBDCp-0003vl-Q5 for bitcoindev@gnusha.org; Sat, 03 May 2025 06:47:04 -0700 Received: by mail-oi1-f189.google.com with SMTP id 5614622812f47-400b3a7e259sf885362b6e.3 for ; Sat, 03 May 2025 06:47:03 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1746280018; cv=pass; d=google.com; s=arc-20240605; b=U5pjuf1YSqgYxGvZL+VHtiFLZml/rXwibJKt7C4YIOkWNsD+fHLu2wskyMYIwCxlTz 2il4d6q6ehKYlqk6r3z0ySBvblp6ZzI1u6jaIi68X4pgAh3M5NiPrzCgB6FM4H2U94iv Wigbs/dIaIg92t20X2VpXu4GWjcsG5HCQuZMI6hdOx9u40H5Rbyy7t6fjycwzTwN4a5L 28KSPzRFkcVsDzxyLFEI8mNo4nwNz44jc2dzKJUF0I026qMv3k8+Y3WasjTJm3l2B+8Q u3PD9+qqCtETzbiADoZjERY9rgsAp7psILNSY58gAWzBbNEn5kbfp+n/7qMw0fFRPWNF VVsQ== 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=GxYewZPXKD6H+fOyOWVjp32G2f+oQd9CE6e+TqNNYfc=; fh=hsathZ3Z74Y5BnNiw26m0aezdffwe7fxpxrRXGJUVcc=; b=eRIrR9W+w9QYrYvkLTaslWf6GfqwwI50uK4GfNCewnhnkniccf/HfYSk9E32YU21J6 YC7L+AKUtBTD00A8So59xU2CO6s5/w1yWY9Fbe6/sAaAatPqMyeC4aYnCVtWFfTNqAiW 3EZMRdg7M1wUTTZvX1DTmhXX1OvNNQ/UL9t9uWIJ2KFUm8uJ872Vn47yXnbSWT7nGsfr bFQU7EkmtLSIs7dE3ZBgr+G860Xu+HDjN4BKy+38iY/lmbjp9uRNvI3uKN4oF9+FtEE3 0YDMHuN0C3e0a9ZmtcygaB+G//uQCp17p0noKWXU9xqWHULUmiNY0MvN8IdBLdixf3rc N7Wg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=SY5xi7AU; spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::a2b 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=1746280018; x=1746884818; 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=GxYewZPXKD6H+fOyOWVjp32G2f+oQd9CE6e+TqNNYfc=; b=TqzLY/JDZntBCOU78vWLdlSLFCY7Ek+WCuogkQC925TnDb0NjvPTyMKeIEdO83Arwi NMMjzy07CdvWdyfLxNbBUX2VX4hvuBOQPs/63fgVSeu9eNt7h892zuzDxE5ob3j4nItO 6CkuFQAEd9y72dND/49zg6bqiTV9V5NgCiHGeo+WYFQw9R1dFzu/G5WQ5B62z94/2Q6V 5ABPR7lGbv0wF6x3/a1dt2KDi2IwOBNy5rukygFb7bsbxU3rCDbJhWN6fRuLIk0y/jWv 8QpAPId0qs8z2ePx7fkiGD9dMhdOLBL4lUJ0cZUMwG396Mg12cI/1xd1zs3gnkEpO5Vb 1g6g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1746280018; x=1746884818; 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=GxYewZPXKD6H+fOyOWVjp32G2f+oQd9CE6e+TqNNYfc=; b=T2LmzhM8+kxK8Gdw7rPKZfXWAEyNxn/EAteXdksTCddyvUiGGCK3VJ6etMwb/Z0Hlv 6+itJ/ycy5iln5VMEmU2oEHzZonz82LLWdW3W/DvSUnhyEJ9Ijw+C4fsKop/7T3q/jfZ W8EgM+l+x9L5NRHgHv8K2P54DA07cQAPvwwV3cf0wlvcl4ehFITh30H6C8voS9T/QzN6 9UOO2LS3GIE2r5CsOgmra+46BHs/qjZkrDwOqpZFrUYz130ob6bmsWV+oKLVkxL5OgUc CA7aBPYeHskzuXH5/GD+7aaLVo22aHjr2D/RtNjJia+eB7L1glCSW3PVfe3J+eA4Ri8S OzXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1746280018; x=1746884818; 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=GxYewZPXKD6H+fOyOWVjp32G2f+oQd9CE6e+TqNNYfc=; b=Qe5huDBUoI9ePhEEYlly81/SHfC/aIxT9Z0VC5nwIAAqQNMoXrl6ozPRlAQNeTqXUg 6D8KczTlnnKEnlYeeFcB2aOTAGiF3ITeUupLyTtvCDwGKvvq7TOWKJOX3AyqpPFaTqyw sPlqspI2DCFo6At/YMdhfJr67zxihdR5dhZkwJqJsohHzzDeKQr4l4bLhbFna3PbiON1 w8B/qfWi8KY/MVo9+IgPWS9K4HEvvm9HW1gPb8orjbhR1Wux0z6e2ujcMK+2NXwPPj+j 2S8es9zLPmqwwbCP2xId3m5yOjS7Ic+IMZioZjm3Ygwh39tjNlZ1g6pq2w51BEX5vLFp vtUA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCWKOzcnU+oiC5PnsIyFNtS7MZIUlVLYvH1KAc1wkgJy+Or0yvOSbpe9HABC3EPEAmt98m1YsRz1CrNG@gnusha.org X-Gm-Message-State: AOJu0YxmjyBJkZLrJZ2+/QwExW+ifE4twOuy/SAgoOXnxpY0BtHlgTzB 1+KGwkZv3KIOal0Bt2YUwz6HEEv7R0F/HxI2erE9Npla1Sk9PSM5 X-Google-Smtp-Source: AGHT+IEtHJYgy5GE7WBFYEjYcaPCm1oFZ/0hs0SvmpzSZSjHZyIMW3oExAPKZPYt4whWm3fkFYYpgA== X-Received: by 2002:a05:6808:1b22:b0:3f9:640b:793e with SMTP id 5614622812f47-4035a5c89e8mr477204b6e.31.1746280017894; Sat, 03 May 2025 06:46:57 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBEAAYkQrgUxUOS8E3+KoaRy+hpQrybB3jk1GXbnHTIOqQ== Received: by 2002:a4a:c802:0:b0:607:f7a8:4be6 with SMTP id 006d021491bc7-607f7a84c1cls201346eaf.1.-pod-prod-06-us; Sat, 03 May 2025 06:46:53 -0700 (PDT) X-Received: by 2002:a05:6808:1994:b0:3f9:aeb6:6eac with SMTP id 5614622812f47-4035a5c85cdmr527761b6e.30.1746280013688; Sat, 03 May 2025 06:46:53 -0700 (PDT) Received: by 2002:a05:6808:2109:b0:403:484c:9068 with SMTP id 5614622812f47-403484c9444msb6e; Sat, 3 May 2025 06:42:50 -0700 (PDT) X-Received: by 2002:a05:6870:1856:b0:2d5:230f:b34a with SMTP id 586e51a60fabf-2dae8345820mr509075fac.9.1746279769596; Sat, 03 May 2025 06:42:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1746279769; cv=none; d=google.com; s=arc-20240605; b=Q+Ys5mEwxJqIFpD92qFdiXaBnfcI9x+OTUueJwdlX4xUtZ7gffCAZLAGojZ7HmN43w qGEHMTs9/7Jk78Ybes0TaHpz07gQYBrSCS4pUGX6jR9fmbs4bzJmKl6DGnL9gi9GMtvX pf8dCViVijMyOVBUOCaHKfLGybFuRD38Ph9bpajBCTXfY6MzrWearXUxLO/FbzVH3dlo ehn7bOiJynKVvoVkWXqmed7VPfd8SUTA6p+GoSAvrfxYB8QE6fTJKZNVqnKPHrSK43gP LhjaYnn+mWQ9mNjXu2UtLJONxLi/QMHpYCPRdEUt+eghDS07ASLwcLcvIyBZzA/GSe5D RFaQ== 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=BthKqgqzTp/5ZTCAh/MdDFIRNRY/TmfjjQJWECjEz2c=; fh=TeCk96/kAeyEXmQ3h4fiYT7Rz3myP2p/QrX59jj+DJE=; b=RQ/W9gU2eZ4kdTo4kLBtRvPRXXXPiVejfbT5t/UWWZPIkrI+NNVNS2AebP23YTU3HA bJQkflSoIWLISaOVuryQGcyroXYe9nAhchKMumUPxBcKTbWs4RAeWuG/yFvlcolQUqmo OhSL/6KGH1zSKvgprrPShLiJ4aEvKwiBUqyUohF8kX2LfFnViHc+HnNligDEiyIADmVp bRWbRWTx67rlxQCrsyrmUAW+snwvLHSE2muWkheGap6R7LwFhn92CQ7/2waLxySABGD4 a29tCwTNyaj9OHT2V3xVdcSGqutfZ7gIRemAqf3WjYzxvLL4++0eVVs2rYtZ9pm79pgR scLQ==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=SY5xi7AU; spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::a2b 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-vk1-xa2b.google.com (mail-vk1-xa2b.google.com. [2607:f8b0:4864:20::a2b]) by gmr-mx.google.com with ESMTPS id 586e51a60fabf-2daa1222639si80054fac.5.2025.05.03.06.42.49 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 03 May 2025 06:42:49 -0700 (PDT) Received-SPF: pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::a2b as permitted sender) client-ip=2607:f8b0:4864:20::a2b; Received: by mail-vk1-xa2b.google.com with SMTP id 71dfb90a1353d-523de5611a3so858333e0c.1 for ; Sat, 03 May 2025 06:42:49 -0700 (PDT) X-Gm-Gg: ASbGncsYe6Hfa3RZjQhEFWVJxULPZ0A9/4LMpZmfY87ddjICYR9EGDihsmkY6g10seA 4G3tBX9xssDN9+N9WZ3/NjPnWA60YmhGn83rw4YV5bvCq33SeYhiKFVVURH2neP/h+M11cLaoB1 eKxJlg/vBi0PS39MG62UmzH5F45Lmy1w8uJflBuePA+q9dvcCPXqawN0fVwhZbYUqj+gU= X-Received: by 2002:a05:6122:d94:b0:50a:c70b:9453 with SMTP id 71dfb90a1353d-52b069ef4f2mr328123e0c.10.1746279768611; Sat, 03 May 2025 06:42:48 -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 15:42:39 +0200 X-Gm-Features: ATxdqUGZXV_toqk_d5Z7kLOfigVL4xWuNk7r1zOEM3hIXxA2L0QlstOvOlMCxIk Message-ID: Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints To: Bitcoin Development Mailing List Cc: Greg Maxwell , saintwenhao@gmail.com, Sanket Kanjalkar Content-Type: multipart/alternative; boundary="0000000000004963bc06343b71c6" 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=SY5xi7AU; spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::a2b 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 (/) --0000000000004963bc06343b71c6 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 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 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 knowledge 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, considering that this has eliminated the big sequential part 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. Cheers, Ruben On Sat, May 3, 2025 at 2:07=E2=80=AFPM Greg Maxwell wr= ote: > On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanjalkar wrot= e: > > > 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 canno= t > 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 birthday > bound with the small block size. I think CMC might be needed to avoid tha= t > 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-3a7e= a31ebf22n%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/= CAPv7TjYCaAsJFo3t6A6HmoojnbMNjSRkXHeOW%3DjrbGBpPYzQVg%40mail.gmail.com. --0000000000004963bc06343b71c6 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
=C2=A0 Hey all,


>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 c= ollide 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 thinkin= g. That last part of the sentence is why we currently need the hash, as wel= l as for adding more data in the non-assumevalid version.



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

I can't really evaluat= e whether this might work, but I can see the=C2=A0line of reasoning. Concep= tually, I think what we need is something that transforms the data into fix= ed length blocks for which an attacker can't know the relationship betw= een each block (i.e. via a secret). The transformation needs to be the same= on the input and output side.



>Your reduction fun= ction 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 valu= es cancel each other out, regardless of whether the sets are on the input o= r 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 s= alvage it like by counting the total number of inputs and outputs and relyi= ng on the knowledge that every txid must be unique, but that's a lot ha= rder to reason about.

>even if its with a quite= expensive hash function that the IBD performance will be heavily bottlenec= ked in network and parallelism related issues and be far from the lowest ha= nging fruit for a while,=C2=A0 considering that this has eliminated the big= sequential part and a number of annoying to optimize components entirely

Very true, and as you said, we can easily drop-in r= eplace the hash function at any future point we like, without adverse conse= quences.


Cheers,
Ruben

On Sat, May 3, 2025 at 2:07=E2=80=AFPM Greg Maxwel= l <gmaxwell@gmail.com> wrot= e:
On Saturday, May 3, 2025 at 11:55:28=E2=80=AFAM UTC Sanket Kanjal= kar 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.=C2=A0

1. Sample random symmetric key `k= `
2. Instead of above; AES_k(UTXO_A) + AES_k(UTXO_B) - AES_k(UTXO_C) - A= ES(UTXO_D) =3D=3D 0 =3D>=C2=A0=C2=A0(proving (A=3D=3DC && B=3D= =3DD) || (A=3D=3DD && B=3D=3DC))?

=
AES in CTR mode is, I'm not sure about other modes? Obviously CTR = mode would be unsuitable! (I mean sure modular add/sub and xor are differen= t operations but they are quite close).=C2=A0 I think that in many modes th= e collision resistance would have to at least be restricted by the birthday= bound with the small block size. I think CMC might be needed to avoid that= sort of 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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.googl= e.com/d/msgid/bitcoindev/fbf06c5b-57b6-4615-99bb-3a7ea31ebf22n%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/CAPv7TjYCaAsJFo3t6A6HmoojnbMNjSRkXHeOW%3DjrbGBpPYzQVg%40ma= il.gmail.com.
--0000000000004963bc06343b71c6--