path: root/c6/6763934f25b65ce5006f0a4dd19cd359a8b452

Delivery-date: Wed, 09 Apr 2025 03:11:37 -0700
Received: from mail-yb1-f189.google.com ([209.85.219.189])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBCMIFYEXXQGRBTUP3G7QMGQEPUAP3MY@googlegroups.com>)
	id 1u2SPA-0002nV-00
	for bitcoindev@gnusha.org; Wed, 09 Apr 2025 03:11:37 -0700
Received: by mail-yb1-f189.google.com with SMTP id 3f1490d57ef6-e6e40ff08b3sf4320780276.3
        for <bitcoindev@gnusha.org>; Wed, 09 Apr 2025 03:11:35 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1744193490; cv=pass;
        d=google.com; s=arc-20240605;
        b=Mou2S5BJisAQLDHRp0KmjGoY/NE8bP437Ro8biVDLe5Ert7CWX4isjmgR/M+ErTykG
         fovbe+qhDsCqp0/lxp4tTv3cfAnK024h8k5Wu9xiKqKvYuPin+GL7MXNAmJLkhp27FnK
         NZBocAYU3DWbXGkgVlA4A3Ql4uqqP4Sy0422gSR0gl5h5axsNNeQkuhoAGdodQEzytgD
         7UUnN3axB4WUXjsBcs2SmTxH2UiTwZSCLP2mI9UYaYadqF51YOukETCRSyEKe64IzbL7
         15gVVqY7okhghketXjVF/7Q7BAHUmPPhj6ZHXlue+LH6vniwrL8QemGhGR8Nynt6YNl3
         kjEw==
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
         :mime-version:sender:dkim-signature:dkim-signature;
        bh=hIrzRtvbqveJQoqYOfJ6nUDiAFa4xiO/cc+uc7vfnkA=;
        fh=5sa5LysiPz8feeDiQsTOf/kLRsZ2lBNAyWeHyHSfvAo=;
        b=D1O+oXeP2fww19HJuVJ/8AzDYaQKZop2cxjZC2K9+EF6CkzPhrvK5Rav0U/2pIguPH
         FrII3iKEZ5RdYGC+bt4/8phb8yX/PVOqiUWPQsi7ykdXvQhcimv4d2NARLp8hyya6tcM
         5o90CWtjQREjNzGuAL/dHrW2OwOXD8pcBME6znKpQhrUq4mT1BT/HPnIP4CuljNxlONK
         amkVzb0unTqljVSVcxY3KTIYWa/yC8rx+DTFjgGjqNIFcWGpaVqQDOPZrsKNHBk79lDg
         BuQSTcbA+VztbdLii6NEBFln+N+RTq0gMIH2wcRXmtMWwv/aQsP0KPRySboYPzluNCMW
         CQ6g==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=OPgcG5v0;
       spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92e 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=1744193490; x=1744798290; 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:mime-version
         :sender:from:to:cc:subject:date:message-id:reply-to;
        bh=hIrzRtvbqveJQoqYOfJ6nUDiAFa4xiO/cc+uc7vfnkA=;
        b=ILsq2+IMLJsYme5jibpwhbNmGySnAsrcV7JBh8uffAX+IreWBOlB/GFQyWHETxFkhp
         4rvinFIeH0HUntl0TPRkP8IDeJsSZYFTMshePbN2VocgVQIkqFe9tZIOZJKSorVl7uPi
         W2rgZamLZrIB6Jkx+CozoT5uWKjoyMrTxjUbybspa47+3wr2jTy04cptLB6rRMK9OP5N
         cankpsDyHAxX5qpkpZIA0jbnuwTxRE9vDIUaiY+t3/tPu1lmK/l7XyfbPdVEmk6xpeeQ
         +7DpBN/kzK6Bvh3eWKI18JZOwCc0jnq8ELuB0nZBwRbjiEg5YYVemYmNzyCrhFpFSB6L
         audw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1744193490; x=1744798290; 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:mime-version:from
         :to:cc:subject:date:message-id:reply-to;
        bh=hIrzRtvbqveJQoqYOfJ6nUDiAFa4xiO/cc+uc7vfnkA=;
        b=Jbvoh+tRQqudZ5ssi9sJs8P5kjr/o+O2SX7N1DJNQnknooKJEvOoHPgb5cv65M9HFm
         yBmelSrOToo7NEZneu1okkJ7I8bDq8i0XOxjMkjeYtEP6yHE/6lblzHiOnTKYemofidD
         gcx2lNi1dQPSmazw6vt2ZoW15d6mNl3E5H3+eWo6kMhXTnijRb1ouWoutMLTvNBZCjBi
         3BGF8g0e1zmT64jT5/MXSQlFRYbJLEoqf0m42idmtYG10+srGgoas6pp9GMTgycjA3wN
         3/A2GnqqpvRM0MW7K7Eu5ypLhEl21Me1Et1NqoC0TWsGOmLNbuYXYGIaEpl/t1v7guUg
         ZhVg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1744193490; x=1744798290;
        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:mime-version
         :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date
         :message-id:reply-to;
        bh=hIrzRtvbqveJQoqYOfJ6nUDiAFa4xiO/cc+uc7vfnkA=;
        b=mOFCyo5cl/sFRi53bt9GnR+IwqEejt0pq4HROILclexM0IfsmLGbjILZT0V4SWweYj
         gk4CveuTpax/6khBXkv2qERKzQTi1u6P2tqLs0/bMJqyXMJzVBSf5IIlxwd0uUfw8UiA
         Af864yPo2AkwZvHTC5FNVUipX/GrwVQTg8wFFwcsmlQIwfOUO8OKtX7FXZbXWTDkBWoJ
         wVzGIwqWYPlVID+8MsUxqe10wCcF8f273PdrpXxORyJqw8OcRPfvDbXqhxASM0iHluAE
         yRwepXRiCZFduiWbXou/B3OnbOAcx8K7JA8vREOE4B1hxc5vmDbLEKBIVu59+4PRY+71
         GP6Q==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCVoI91NXWS98GRQ2xBjkO5LnWP9TVxHJO042h+tIecaTn86oQtrZhp342RkQGUoyTuLxlceQ7VHBwst@gnusha.org
X-Gm-Message-State: AOJu0YyOVe5rmJHEnER3lR6uRk1Pp8l8PyVrcYE0ps2GMKyrY9cBX6mC
	FtBgrwDI9eEvV9QV1cqCZolpHvpIa+c6aWkOxe9TCaZ4OuHbFJzb
X-Google-Smtp-Source: AGHT+IGW3nWSIzS4b5G3x4FHBCLiSkz+U/sHClpYTuIdVD7DPWNidWbRlswOlgWJw8JD89QhFb3hIg==
X-Received: by 2002:a05:6902:2405:b0:e6d:e70f:dbed with SMTP id 3f1490d57ef6-e702ef5851cmr3680366276.16.1744193489531;
        Wed, 09 Apr 2025 03:11:29 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJn1U1pEoihEdSFnozryaVKvJQxaSrAPACh6gd3iEPw+w==
Received: by 2002:a25:d0ce:0:b0:e5d:c536:1cba with SMTP id 3f1490d57ef6-e6e07a6d222ls5052239276.1.-pod-prod-02-us;
 Wed, 09 Apr 2025 03:11:26 -0700 (PDT)
X-Received: by 2002:a05:690c:4903:b0:6fd:42ed:c90 with SMTP id 00721157ae682-705387d4627mr48825657b3.16.1744193486291;
        Wed, 09 Apr 2025 03:11:26 -0700 (PDT)
Received: by 2002:a05:690c:248:b0:703:d6cc:4806 with SMTP id 00721157ae682-70539a44faems7b3;
        Wed, 9 Apr 2025 03:10:33 -0700 (PDT)
X-Received: by 2002:a05:6902:1b07:b0:e6d:f41c:6bdb with SMTP id 3f1490d57ef6-e702ef09bddmr3396865276.6.1744193431798;
        Wed, 09 Apr 2025 03:10:31 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1744193431; cv=none;
        d=google.com; s=arc-20240605;
        b=RXW2toGV2PS85xh79Ftu/U22uGlg9O1cqCNG+l0LdLdgDonfyzKrkTFSYmtSXgVkhV
         JXLZJflNu0ID/i532Skg+fTuJYAjUK6r1v14Vrv4SCzo01Mj5RE8MavSpc4icPc56K1H
         Z7cIMom9TVze0ERHbB8f3zd/X8nhYbgDLBbOICftjoOLdFbGMzqxJNi3AUN4MlU7cdYd
         PJYOM8hGdxzIv4mGWsWxHFYfM04bc/K7VEVz0H70ixk8VH2Gwcu9GDOPLraIkymdrpaV
         AMM7ue4A2bIhUMpChiRPLxKc/0kCRkfxmeOJWSVRYzGX2ll83EYYJYqtrcBFAIK8TJMP
         EboA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=to:subject:message-id:date:from:mime-version:dkim-signature;
        bh=Xp/MALn4XqaVlQZheXvYVO363YO19sSujYNWcF9T+8M=;
        fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
        b=OXdfvyDEjZwYx5z0avC52rXKqzzKi0KR6NSVVJ1yMwkaK2SKZLCW93sHHP+ypjcPMP
         hKLkFQDEVLUFlffJXBPkUM0+QO8Utf7UeDGyBlBBX67StMF3XGGnEjKSHzepxco2JuZt
         AvoJQqTnAbtNkWXa9Le2sKNZI9EC8+mm+/T/m7NnBM3JxDLeJ/4eQq8wCgeOGWPRP7YX
         6OUgmIot8hoS7H3L0VHH8SsXUM14cs4Ui+2ynLFtaucTbZZn4LNMcufgVxEy4bE5IQS9
         6raUkdk576afnJMcZXO3QzJ7zcpvGPqFGJppGV4JLp2eZMMe4cDyMv3EGhL2ycj0xXMs
         DyIw==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=OPgcG5v0;
       spf=pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92e 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-x92e.google.com (mail-ua1-x92e.google.com. [2607:f8b0:4864:20::92e])
        by gmr-mx.google.com with ESMTPS id 3f1490d57ef6-e70324f3eccsi40371276.2.2025.04.09.03.10.31
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Wed, 09 Apr 2025 03:10:31 -0700 (PDT)
Received-SPF: pass (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92e as permitted sender) client-ip=2607:f8b0:4864:20::92e;
Received: by mail-ua1-x92e.google.com with SMTP id a1e0cc1a2514c-86b9d1f7249so5540955241.2
        for <bitcoindev@googlegroups.com>; Wed, 09 Apr 2025 03:10:31 -0700 (PDT)
X-Gm-Gg: ASbGncuL+PEF1EeskQOhCfcwbLAS89ExhngJps4GaRp4+Brg5kFPEniTeaurFanbpjq
	lZcskqNjSa3EYYJQ/USpCxbYY58sIFU/YKGu9VPvDD+QUZ3zo6sdnfvvuSBQvDHVzVtOpNxA82v
	M+O8fPYjy5DlipKsMxs0Vg8RkZKWUm6LXWGGDr9PiBGfqdynZ857na0+5B
X-Received: by 2002:a05:6102:5109:b0:4bb:c8e5:aa6d with SMTP id
 ada2fe7eead31-4c9c444dacemr1562572137.17.1744193431122; Wed, 09 Apr 2025
 03:10:31 -0700 (PDT)
MIME-Version: 1.0
From: Ruben Somsen <rsomsen@gmail.com>
Date: Wed, 9 Apr 2025 12:10:21 +0200
X-Gm-Features: ATxdqUEyzPR8lqbHc3MEn7lwjXIVvjoOjv7dntg79XPiSxKrMyOm_WQZCPeo_K4
Message-ID: <CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr+ShOC1KZi2V3V2zooTXyg@mail.gmail.com>
Subject: [bitcoindev] SwiftSync - smarter synchronization with hints
To: bitcoindev@googlegroups.com
Content-Type: multipart/alternative; boundary="000000000000e1b8a6063255ad40"
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=OPgcG5v0;       spf=pass
 (google.com: domain of rsomsen@gmail.com designates 2607:f8b0:4864:20::92e 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 (/)

--000000000000e1b8a6063255ad40
Content-Type: text/plain; charset="UTF-8"

Hi everyone,

SwiftSync is a new validation method that allows for near-stateless, fully
parallelizable validation of the Bitcoin blockchain via hints about which
outputs remain unspent (<100MB total). All other inputs/outputs are
efficiently crossed off inside a single hash aggregate that only reaches
zero if validation was successful and the hints were correct.

The main observation is that it can be much easier to validate that a given
UTXO set is correct than to compute it yourself. It allows us to no longer
require a stateful moment-to-moment UTXO set during IBD and allows
everything to be order independent. I'll briefly summarize the protocol,
before sharing the link to the full write-up.

Each output gets a boolean hint (e.g. committed into Bitcoin Core) about
whether or not it will still be in the UTXO set after validation completes.
If it does, we write it to disk (append-only - it won't be used until
SwiftSync finishes). If it does not, we hash the UTXO data and add it to an
aggregate. For each input, we once again hash the UTXO data and remove it
from the aggregate.

At the end, for every added output there should have been exactly one
removed input, bringing the end total of the aggregate to zero. If this is
indeed the case, we will have validated that the hints, and the resulting
UTXO set, were correct.

E.g. For spent outputs A, B and inputs C, D we calculate hash(UTXO_A||salt)
+ hash(UTXO_B||salt) - hash(UTXO_C||salt) - hash(UTXO_D||salt) == 0
(proving (A==C && B==D) || (A==D && B==C)).

There is one missing step. The UTXO data is only available when processing
the output, but not when processing the input. We resolve this by either
downloading the outputs that were spent for each block (equivalent to the
undo data, maybe 10-15% of a block), or we lean on assumevalid, making it
sufficient to only hash the outpoints (which are available in both the
output and input) rather than the full UTXO data.

Ignoring bandwidth, the expectation is that the speedup will be most
significant on either RAM limited devices and/or devices with many CPU
cores. Initial PoC benchmarks (thanks to theStack) show a 5.28x speed-up,
while currently still being largely sequential.

Many more details are in the full write-up:
https://gist.github.com/RubenSomsen/a61a37d14182ccd78760e477c78133cd

It will answer the following questions (and more):

- How the hash aggregate can be made secure against the generalized
birthday problem
- How exactly assumevalid is utilized and what the implications are
- How we can still check for inflation when we skip the amounts with
assumevalid
- How we can validate transaction order while doing everything in parallel
- How we can perform the BIP30 duplicate output check without the UTXO set
- How this all relates to assumeutxo

To my knowledge, every validation check involving the UTXO set is covered,
but I'd be curious to hear if anything was overlooked or if you spot any
other issues.

Thanks for reading, and thanks to everyone who provided invaluable feedback
while the idea was coming together.

-- Ruben Somsen

-- 
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/CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr%2BShOC1KZi2V3V2zooTXyg%40mail.gmail.com.

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

<div dir=3D"ltr"><div>Hi everyone,</div><div><br></div>SwiftSync is a new v=
alidation method that allows for near-stateless, fully parallelizable valid=
ation of the Bitcoin blockchain via hints about which outputs remain unspen=
t (&lt;100MB total). All other inputs/outputs are efficiently crossed off i=
nside a single hash aggregate that only reaches zero if validation was succ=
essful and the hints were correct.<br><br>The main observation is that it c=
an be much easier to validate that a given UTXO set is correct than to comp=
ute it yourself. It allows us to no longer require a stateful moment-to-mom=
ent UTXO set during IBD and allows everything to be order independent. I&#3=
9;ll briefly summarize the protocol, before sharing the link to the full wr=
ite-up.<br><br>Each output gets a boolean hint (e.g. committed into Bitcoin=
 Core) about whether or not it will still be in the UTXO set after validati=
on completes. If it does, we write it to disk (append-only - it won&#39;t b=
e used until SwiftSync finishes). If it does not, we hash the UTXO data and=
 add it to an aggregate. For each input, we once again hash the UTXO data a=
nd remove it from the aggregate.<br><br>At the end, for every added output =
there should have been exactly one removed input, bringing the end total of=
 the aggregate to zero. If this is indeed the case, we will have validated =
that the hints, and the resulting UTXO set, were correct.<br><br>E.g. For s=
pent outputs A, B and inputs C, D we calculate hash(UTXO_A||salt) + hash(UT=
XO_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>The=
re is one missing step. The UTXO data is only available when processing the=
 output, but not when processing the input. We resolve this by either downl=
oading the outputs that were spent for each block (equivalent to the undo d=
ata, maybe 10-15% of a block), or we lean on assumevalid, making it suffici=
ent to only hash the outpoints (which are available in both the output and =
input) rather than the full UTXO data.<br><br>Ignoring bandwidth, the expec=
tation is that the speedup will be most significant on either RAM limited d=
evices and/or devices with many CPU cores. Initial PoC benchmarks (thanks t=
o theStack) show a 5.28x speed-up, while currently still being largely sequ=
ential.<br><br>Many more details are in the full write-up:<br><a href=3D"ht=
tps://gist.github.com/RubenSomsen/a61a37d14182ccd78760e477c78133cd">https:/=
/gist.github.com/RubenSomsen/a61a37d14182ccd78760e477c78133cd</a><br><br>It=
 will answer the following questions (and more):<br><br>- How the hash aggr=
egate can be made secure against the generalized birthday problem<div>- How=
 exactly assumevalid is utilized and what the implications are</div><div>- =
How we can still check for inflation when we skip the amounts with assumeva=
lid</div><div>- How we can validate transaction order while doing everythin=
g in parallel</div><div>- How we can perform the BIP30 duplicate output che=
ck without the UTXO set</div><div>- How this all relates to assumeutxo<br><=
br>To my knowledge, every validation check involving the UTXO set is covere=
d, but I&#39;d be curious to hear if anything was overlooked or if you spot=
 any other issues.<br><br>Thanks for reading, and thanks to everyone who pr=
ovided invaluable feedback while the idea was coming together.<br><br>-- Ru=
ben Somsen</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/CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr%2BShOC1KZi2V3V2zooTXyg%40mail.gma=
il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/=
msgid/bitcoindev/CAPv7TjaM0tfbcBTRa0_713Bk6Y9jr%2BShOC1KZi2V3V2zooTXyg%40ma=
il.gmail.com</a>.<br />

--000000000000e1b8a6063255ad40--