path: root/2f/8804b6f42f2bcbb9682f5da90a5ba970c1e43f

Delivery-date: Sat, 03 May 2025 04:55:35 -0700
Received: from mail-oa1-f59.google.com ([209.85.160.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+bncBD4YRG7X5UDRBLEI3DAAMGQE5OMHRCQ@googlegroups.com>)
	id 1uBBSw-0007XM-Jf
	for bitcoindev@gnusha.org; Sat, 03 May 2025 04:55:35 -0700
Received: by mail-oa1-f59.google.com with SMTP id 586e51a60fabf-2d031b18c44sf2322901fac.0
        for <bitcoindev@gnusha.org>; Sat, 03 May 2025 04:55:34 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1746273328; cv=pass;
        d=google.com; s=arc-20240605;
        b=DudHNooxju1dsf0SPYPTeMmMCZNkoAunH/XpQUejUdiEdBDuWOgZkT84l6WlfkYUs6
         v6BqywaKHbvc416Errf/O8kdFINOVGJ+0OU3PCCRSKedjs9bFnDEI6BYb+fq70RrUqLG
         HV6nSBI1S9xKpLqgqGk0dEPjC5+/Rm28k3RZrUcXRmjceLUTL9y9S3QtnyIhjfmB2fUA
         k7hGaBbRt7rDPqhh2wcVaw9Cu+o2e2zBvSyEIiZtBGsBOYgfDtZqisznLmwAWPerHZlD
         DLnbTgGuO0KnHPjw8vwaHpYj0eWZAZ3+w11LfIQDLmvj9wzFpY77ppBKGdTTYT8Q0zdv
         mFRw==
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:to:subject:message-id:date:from
         :in-reply-to:references:mime-version:sender:dkim-signature
         :dkim-signature;
        bh=0dd0hSaXKLi09EpX4RmUkns/HNPx3SHJd7rplX7YKq8=;
        fh=0HD7PePsV2ISHdFvszXvhh33NrS1wu+4b68qRPQKxYU=;
        b=eDD3gBy3bGBnOLSLwjJdSLgV01yYviYah602XxL04nWObC9339P/sdEZ931RiUarCf
         KI0y/zgUa69v4J5BW16t/ptOAqOv+0t4XdN3MFZrWnqICxF4XwTU6ClvWQy22Z5kTmsP
         nuKsTbXSjPF/hiRmeQba+5CO1L6M8FQL65jezm/SRsnsQPbXFpiEUXdBhdAgf3jGlFxq
         ZJOUXZ1oyu+WjOcydImk05ZrvesgU9m6SQLj4fhcDfRTBLnnKFTxg0v3Qt8jYkmT4ptM
         wocN5hNRh+dY0WXWQZLEcB565A55WELIQxTxfT77Qjm0pJMAJlYdCjpsoAupqQWZIdxJ
         4h6g==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b="fei0Zs/L";
       spf=pass (google.com: domain of sanket1729@gmail.com designates 2607:f8b0:4864:20::112d as permitted sender) smtp.mailfrom=sanket1729@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=1746273328; x=1746878128; 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:to:subject:message-id:date:from:in-reply-to
         :references:mime-version:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=0dd0hSaXKLi09EpX4RmUkns/HNPx3SHJd7rplX7YKq8=;
        b=vAvXAh9pmYV+ebuXCAcLk++9iao6l7Q1soo2+GurWamSLSXLRqNXrCmL5afe7dBVBc
         Y5f58IxXAhwWVCgdfTx+PRaO6Ark2xBFX4tnxNYhCbKTNDGrPsjTWKe2PIl/6n4Lyimi
         y+0FNmglYSimvFEWKfGWLTfa89f7LbSmyQQ9t+Vn+rcKkXv5MiCOmVd6dNpWjm/VTeoA
         dWHfrrTNEShlwHbbO7gjBI/skY2mSrW7hkpyHt3CQwyfbLDTB01LzKHfW14HPM3gpxKL
         7oslmERQdqNeZgkf00yZF8c7ZExkYsCS6Z/KAPgqectYr2+mdqwbeD2gu7Mpmwh3Fx4v
         h2Eg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1746273328; x=1746878128; 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:to:subject:message-id:date:from:in-reply-to
         :references:mime-version:from:to:cc:subject:date:message-id:reply-to;
        bh=0dd0hSaXKLi09EpX4RmUkns/HNPx3SHJd7rplX7YKq8=;
        b=iZwp6Fyt4GkZtAWEShzMOE2qxf6C7c5Qfgsn/mXptURPF8NP4qLIhVzWrdYnKAZSKj
         9gzqAJvZgG44NGI0hRI3mfnZKwF2pndDR0irYMOROvsQV8W5OFEAYlhiezb6X9nr+4vN
         pho3xDFPzaRcsfydSTL5yZWkxKYnMFWmHJYEO3fdXRP9zgOaFZnPs1tBfC+vypK0vY50
         yff2dSMz+8UQmmqg1EGczp+JRGPi3/1AHaD+rLeXliGIvX9/mKEGz2CdDhHmDclXRKO1
         o5OLqdO1aRdrA9lMpG6PzEqCZJR7ZIKcCJN9xl3Vmu8m86TEA78Cb+Y1i+zo6+ngfsMw
         SXMg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1746273328; x=1746878128;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender: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=0dd0hSaXKLi09EpX4RmUkns/HNPx3SHJd7rplX7YKq8=;
        b=G9pyx5xEvmYwdOSbAXQ5Jy0SXDB1aXvCJdG0JxhtqkgOJRZFoY5mN9OpudOAFKE9kh
         PKc6IX7Op7djdzH9H0lhU83+LmIfeRlp1aA20sMkR9659dNjchnvyD/1t02ZIaJEA+hU
         sqwKD6lYJ5iMNQDqgZ+Z4LcMTSTJd86/BQapGjPLV6/3lYWwQ6cwYkoNCF+BUZAkMxLT
         N9WZR0aVOGSQoaN/qlvMSihGdf9lpQEx+MDvDtfYorGaUPoGR8+AhlE/xe0b3bXOzcy0
         eDEeleUzkYhygArIk03rChlRWEnPZ4lh4y02oSrRd4LkFaj0D7LnatoO/z55EFryp/lO
         TdlA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCXo5ObDCxqUiukUQ3aOZ+QmIz/LOKTyY268WAA2u/pCrKwOUBmCS/Y9k9ASdTliLlqMGD36IEcktbR+@gnusha.org
X-Gm-Message-State: AOJu0YyBaDyvLHlYY6EjDLj23ui8APtpy9oA3BmwtUrJOOzG2GTrBgsn
	2AtGJkvRGnQuuxioJ44/ttN0D8UnugkivOer9HlBULBb3viJWEW5
X-Google-Smtp-Source: AGHT+IGk5+z6eE3rrsAYa8HWyo+6Q0QCUt5wKtBHTnrBgwP4+wDU6IPNI5yw3p8msAIC9RKZ9xc20w==
X-Received: by 2002:a05:6870:164d:b0:2d5:23a3:faa7 with SMTP id 586e51a60fabf-2dab2f3b3f2mr3563258fac.6.1746273328369;
        Sat, 03 May 2025 04:55:28 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBHsynxn1B+Q8lDCDa9V7P6VeyXGRd7XM2ays7QGGn5b5g==
Received: by 2002:a05:6871:210b:b0:2c1:4c52:d40f with SMTP id
 586e51a60fabf-2da8a46a72dls1254953fac.1.-pod-prod-01-us; Sat, 03 May 2025
 04:55:24 -0700 (PDT)
X-Received: by 2002:a05:6808:338b:b0:400:fa6a:6726 with SMTP id 5614622812f47-40341695b18mr3714317b6e.0.1746273324156;
        Sat, 03 May 2025 04:55:24 -0700 (PDT)
Received: by 2002:a05:6808:14d5:b0:3fa:da36:efcd with SMTP id 5614622812f47-403425cae8dmsb6e;
        Fri, 2 May 2025 13:23:15 -0700 (PDT)
X-Received: by 2002:a17:90b:4c12:b0:305:2d68:8d91 with SMTP id 98e67ed59e1d1-30a4e622226mr6237414a91.28.1746217394436;
        Fri, 02 May 2025 13:23:14 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1746217394; cv=none;
        d=google.com; s=arc-20240605;
        b=R1RbWXXXBdTqtOj2SH6qzmmtPzXJoK5LD4ifp7A1HtBjrLesujZANrvbXVMok/DHbV
         FZ+sQo+KM0K4/Q4sn90scXQ5B81M/x4u6njrp4Ip0pFZQuYI1nAf2J9liz5E/doGvyF1
         CqcRPmKf56Gsi9Hh8jn7uWBKE8tnc+mrtjQsMrlYLK8rmKJ6uvfe2HIYGOIqE9yOGXO1
         sr347bjNmPokzxl0dLK7EhSm4LuDkNOkr6rsfL4GuXGAz4o2FlcFPU8iywRFjGGSuVX3
         1h9+BWp//w+UNPu9/a+nY9jTSD9uzJmY19ijrhADmgtMd1OqWWa7h/DcsCYlQifAile8
         qZBg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=to:subject:message-id:date:from:in-reply-to:references:mime-version
         :dkim-signature;
        bh=entzmV81mV2qAMTlHlgdJJY/nmN66BBOrsP2FZuoZX0=;
        fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=;
        b=TVs7tW89JUdjXDlwT0Xs7kFY3716+QYXX2OMmFuiBuca5nC3BpXpOVrPFrQvAzHcEl
         OgCYYLBO3Iw4jX+iG9SVVQa+TZM1bEgdNjBtBKhhIMJBgbx/iU50wayZbFdnFd/NlU37
         ZpH7k4O6wUpXinuPyj9iigGuAqoKFZNCCG5JYflVMAXefOsELl2K/cTPnvsmG+OR/ST3
         5Dx75I0ZnbyLnGSHZWLm5ottPoLgSl+iXV5HmlD1FhlStYTr7iHdQP+0rY4teHZ9aQku
         KEBVGNDM0uKaJBpCfld+GRSQ3MV3Cm8RrBfEBTN+0Ui5OFUI1wsLH5gIzez4yQUngCi7
         TsBg==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b="fei0Zs/L";
       spf=pass (google.com: domain of sanket1729@gmail.com designates 2607:f8b0:4864:20::112d as permitted sender) smtp.mailfrom=sanket1729@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-yw1-x112d.google.com (mail-yw1-x112d.google.com. [2607:f8b0:4864:20::112d])
        by gmr-mx.google.com with ESMTPS id 98e67ed59e1d1-30a244b503asi704953a91.0.2025.05.02.13.23.14
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Fri, 02 May 2025 13:23:14 -0700 (PDT)
Received-SPF: pass (google.com: domain of sanket1729@gmail.com designates 2607:f8b0:4864:20::112d as permitted sender) client-ip=2607:f8b0:4864:20::112d;
Received: by mail-yw1-x112d.google.com with SMTP id 00721157ae682-6ff37565232so20926057b3.3
        for <bitcoindev@googlegroups.com>; Fri, 02 May 2025 13:23:14 -0700 (PDT)
X-Gm-Gg: ASbGncvM3AEo1l3cwcXYSWoVuKhn5HgXmgB4fCVdPjexw7pqJIe9NoFALPwJeChA3w0
	PRVrNj0IUMaassQ/d/ikNtYZ61/EfIdeKdWp5NKrPchVnnDV9cPW4wxNzu+P476zYCw5UQI8+OT
	G+uFCFppbEw0XFxL8BMoWt8PP17fvANoinBVQsSF8GKoPgNqpqZljv3eU=
X-Received: by 2002:a05:690c:360c:b0:703:b5ae:987e with SMTP id
 00721157ae682-708cf00ee24mr66825917b3.2.1746217393618; Fri, 02 May 2025
 13:23:13 -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>
In-Reply-To: <69194329-4ce6-4272-acc5-fd913a7986f3n@googlegroups.com>
From: Sanket Kanjalkar <sanket1729@gmail.com>
Date: Fri, 2 May 2025 13:23:02 -0700
X-Gm-Features: ATxdqUHUDZ2Io8IYC8mx19omZD7qWR124Ffq0auV3lT6wVCobXgkEXN1AYJxSgI
Message-ID: <CAExE9c8XfEH__onX3DhUQh0OnvpoOLwRRp8+Z6PozyKGtqpspw@mail.gmail.com>
Subject: Re: [bitcoindev] Re: SwiftSync - smarter synchronization with hints
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="00000000000072868a06342cebf1"
X-Original-Sender: sanket1729@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b="fei0Zs/L";       spf=pass
 (google.com: domain of sanket1729@gmail.com designates 2607:f8b0:4864:20::112d
 as permitted sender) smtp.mailfrom=sanket1729@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 (/)

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

> 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))?

As mentioned, I don't know if this works or not. But the idea is that AES
is faster than sha256 on most machines.

On Fri, May 2, 2025 at 12:09=E2=80=AFPM Greg Maxwell <gmaxwell@gmail.com> w=
rote:

> On Friday, May 2, 2025 at 11:01:10=E2=80=AFAM UTC Ruben Somsen wrote:
>
> I don't see a practical way to do this without compromising the benefits
> of SwiftSync because of the "later find them being spent" part. For one, =
it
> would require doing a lookup for each input to see if it's in your UTXO
> set, something we currently don't need to do at all. Secondly, it would
> require blocks to be processed in order, limiting parallelization. The
> space savings would also be negligible, considering the hint data is
> already <100MB (compressed).
>
>
> Doh. Right. Got too excited.
>
>
> I think most of the remaining optimization potential (other than the
> engineering work to enable parallel validation) is in the hash
> aggregate, like the midstate reuse. Is there a faster alternative to
> sha256? Can we get away with 16 byte hashes? I could be mistaken, but in
> theory it seems we could even get away with 4 byte hashes if we allowed f=
or
> a 1 in 4 billion chance of accidentally accepting an invalid chain. Leavi=
ng
> consensus to chance feels philosophically improper, but it's a pretty saf=
e
> bet considering it also involves PoW to trigger and even then would only
> affect one or two random unlucky people on Earth.
>
>
> I think the problem isn't so much the size of the hash output, but rather
> the property you need is that each salt gives you a different hash functi=
on
> such that the attacker cannot predictably create collisions. The most
> expedient way to get there is a cryptographic hash function, which limits
> you lower performance choices.  Your reduction function could just be xor
> and if it is I doubt the output size itself matters much for performance.=
..
> and my guess is that e.g. xor with 32 byte hashes will have better
> performance than addition with 16 bytes.
>
> It doesn't need to be so in the initial implementation but ultimately it
> may make sense for the host to benchmark available hashes and pick the
> fastest.  SHA-256 will easily be a winner on hardware with SHA-NI or
> similar.  But there are other cryptographic hashes in the codebase that
> might be faster on systems without sha256 hardware support.
>
> There are argument I can see to prove the security of simpler hashes that
> only work if you assume that the attacker could only insert specific fini=
te
> numbers of bad changes... but they really have completely full control of
> the hash function input except for the salt and that I think makes it har=
d
> to say much positive about the security of any optimization except
> truncating a secure hash (and I don't think truncating will win you much
> security).
>
>  In terms of security keep in mind that a prospective attacker needs to
> also perform POW to get their attack chain up to the users accepted chain
> tip, which means that they have to do the work between the AV point and t=
he
> tip assuming the user isn't isolated.  This fact could be used to justify=
 a
> rather weak hash function, but I think it's not really worth a lot of
> analysis ahead of the initial functionality.  I'm guessing that once this
> is implemented, 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.
>
>
>
>
>
> --
> 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/69194329-4ce6-4272-acc5-fd91=
3a7986f3n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/69194329-4ce6-4272-acc5-fd9=
13a7986f3n%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter>
> .
>


--=20
Sanket Kanjalkar

--=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/=
CAExE9c8XfEH__onX3DhUQh0OnvpoOLwRRp8%2BZ6PozyKGtqpspw%40mail.gmail.com.

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

<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=3D=
D) || (A=3D=3DD &amp;&amp; B=3D=3DC))<br><br>What if instead of hash we enc=
rypt 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><br>1. Sample random symmetric ke=
y `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))?<br><br>As mentioned, I don&#39=
;t know if this works or not. But the idea is that AES is faster than sha25=
6 on most machines.=C2=A0</div><br><div class=3D"gmail_quote gmail_quote_co=
ntainer"><div dir=3D"ltr" class=3D"gmail_attr">On Fri, May 2, 2025 at 12:09=
=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;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div><div dir=3D"auto">On Friday, May 2, 2025 at 11:01:10=E2=80=
=AFAM UTC Ruben Somsen wrote:<br></div><blockquote style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr"><div>I don&#39;t see a practical way to do this without compromisi=
ng the benefits of SwiftSync because of the=C2=A0&quot;later find them bein=
g spent&quot; part. For one, it would require doing a lookup for each input=
 to see if it&#39;s in your UTXO set, something we currently don&#39;t need=
 to do at all. Secondly, it would require blocks to be processed in order, =
limiting parallelization. The space savings would also be negligible, consi=
dering the hint data is already &lt;100MB (compressed).</div></div></blockq=
uote><div><br></div><div>Doh. Right. Got too excited.</div><div>=C2=A0<br><=
/div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>I think most of the =
remaining optimization potential (other than the engineering work to enable=
 parallel validation) is in the hash aggregate,=C2=A0like the midstate reus=
e. Is there a faster alternative to sha256? Can we get away with 16 byte ha=
shes? I could be mistaken, but in theory it seems we could even get away wi=
th 4 byte hashes if we allowed for a 1 in 4 billion chance of accidentally =
accepting an invalid chain. Leaving consensus to chance feels philosophical=
ly improper, but it&#39;s a pretty safe bet considering it also involves Po=
W to trigger and even then would only affect one or two random unlucky peop=
le on=C2=A0Earth.</div></div></blockquote><div><br></div><div>I think the p=
roblem isn&#39;t so much the size of the hash output, but rather the proper=
ty you need is that each salt gives you a different hash function such that=
 the attacker cannot predictably create collisions. The most expedient way =
to get there is a cryptographic hash function, which limits you lower perfo=
rmance choices.=C2=A0 Your reduction function could just be xor and if it i=
s I doubt the output size itself matters much for performance... and my gue=
ss is that e.g. xor with 32 byte hashes will have better performance than a=
ddition with 16 bytes.</div><div><br></div><div>It doesn&#39;t need to be s=
o in the initial implementation but ultimately it may make sense for the ho=
st to benchmark available hashes and pick the fastest.=C2=A0 SHA-256 will e=
asily be a winner on hardware with SHA-NI or similar.=C2=A0 But there are o=
ther cryptographic hashes in the codebase that might be faster on systems w=
ithout sha256 hardware support.=C2=A0 <br></div><div><br></div><div>There a=
re argument I can see to prove the security of simpler hashes that only wor=
k if you assume that the attacker could only insert specific finite numbers=
 of bad changes... but they really have completely full control of the hash=
 function input except for the salt and that I think makes it hard to say m=
uch positive about the security of any optimization except truncating a sec=
ure hash (and I don&#39;t think truncating will win you much security).</di=
v><div><br></div><div>=C2=A0In terms of security keep in mind that a prospe=
ctive attacker needs to also perform POW to get their attack chain up to th=
e users accepted chain tip, which means that they have to do the work betwe=
en the AV point and the tip assuming the user isn&#39;t isolated.=C2=A0 Thi=
s fact could be used to justify a rather weak hash function, but I think it=
&#39;s not really worth a lot of analysis ahead of the initial functionalit=
y.=C2=A0 I&#39;m guessing that once this is implemented, even if its with a=
 quite expensive hash function that the IBD performance will be heavily bot=
tlenecked in network and parallelism related issues and be far from the low=
est hanging fruit for a while,=C2=A0 considering that this has eliminated t=
he big sequential part and a number of annoying to optimize components enti=
rely.</div><div><br></div><div><br></div><div><br></div><div><br></div><div=
><br></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/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegroups.com?utm_med=
ium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">https://groups.googl=
e.com/d/msgid/bitcoindev/69194329-4ce6-4272-acc5-fd913a7986f3n%40googlegrou=
ps.com</a>.<br>
</blockquote></div><div><br clear=3D"all"></div><div><br></div><span class=
=3D"gmail_signature_prefix">-- </span><br><div dir=3D"ltr" class=3D"gmail_s=
ignature"><div dir=3D"ltr">Sanket Kanjalkar<br></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">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/CAExE9c8XfEH__onX3DhUQh0OnvpoOLwRRp8%2BZ6PozyKGtqpspw%40mail.gma=
il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/=
msgid/bitcoindev/CAExE9c8XfEH__onX3DhUQh0OnvpoOLwRRp8%2BZ6PozyKGtqpspw%40ma=
il.gmail.com</a>.<br />

--00000000000072868a06342cebf1--