Delivery-date: Wed, 09 Apr 2025 03:11:37 -0700
Sender: bitcoindev@googlegroups.com
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;
MIME-Version: 1.0
From: Ruben Somsen <rsomsen@gmail.com>
Date: Wed, 9 Apr 2025 12:10:21 +0200
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"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

--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=
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--