BIPs 455–457: SwiftSync Specification #2152

   0 | @@ -0,0 +1,86 @@
   1 | +```
   2 | +  BIP: ?
   3 | +  Layer: Applications
   4 | +  Title: SwiftSync initial block download
   5 | +  Authors: Robert Netzke <bips@2140.dev>, Ruben Somsen <bips@2140.dev>
   6 | +  Status: Draft
   7 | +  Type: Specification
   8 | +  Assigned: ?
   9 | +  License: BSD-3-Clause

---

   7 | +  Type: Specification
   8 | +  Assigned: ?
   9 | +  License: BSD-3-Clause
  10 | +  Requires: BIP ?, BIP ?
  11 | +```
  12 | +# Abstract

---

  11 | +```
  12 | +
  13 | +# Abstract
  14 | +
  15 | +Inputs of a Bitcoin block are referenced by the outpoint data structure. This poses a limitation during initial block download (IBD), such that a client must process blocks sequentially to validate the chain history. The SwiftSync protocol allows blocks to be evaluated in arbitrary order, however additional data is required that must be served over the peer-to-peer network. Namely, the creation height, coinbase flag, input script, and amount for each spent coin must be accessible to fully validate a block in a state-less manner. This data cannot be trusted by a peer under usual conditions, however SwiftSync allows a client performing IBD to validate the correctness of this data.
  16 | +# Motivation

---

  10 | +  License: BSD-3-Clause
  11 | +```
  12 | +
  13 | +# Abstract
  14 | +
  15 | +Inputs of a Bitcoin block are referenced by the outpoint data structure. This poses a limitation during initial block download (IBD), such that a client must process blocks sequentially to validate the chain history. The SwiftSync protocol allows blocks to be evaluated in arbitrary order, however additional data is required that must be served over the peer-to-peer network. Namely, the creation height, coinbase flag, input script, and amount for each spent coin must be accessible to fully validate a block in a state-less manner. This data cannot be trusted by a peer under usual conditions, however SwiftSync allows a client performing IBD to validate the correctness of this data.

---

  33 | +
  34 | +The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.
  35 | +## Data structures
  36 | +#### Height Code
  37 | +
  38 | +The height and coinbase flag are encoded as a 32 bit integer. To encode the height and flag, binary left shift the height one bit, treat the boolean as a bit, insert it into the newly opened bit position. To decode the height, binary right shift the code. To decode the coinbase flag, mask the first bit position of the header code and interpret the bit as a boolean.

---

  89 | +| :---------- | :-------------------------------- | -------------------------------------------------------------- |
  90 | +| `blockhash` | 32 byte vector                    | Block hash these coins are spent from                          |
  91 | +| `len`       | `CompactSize(Len(vector<Coins>))` | The length of the coins vector                                 |
  92 | +| `coins`     | `vector<Coin>`                    | Coins that were spent, after filtering on the request `cutoff` |
  93 | +
  94 | +A client supporting the `bspent` MUST include coins created _before_ the `cutoff` field in `getbspent` requests. A client receiving a `bspent` message with un-requested or missing coins MUST disconnect from the serving peer. A client supporting `bspent` MUST adhere to the format of `Coin` specified in the `verion` of the request.

---

  25 | +This section defines how to request and serve block spent coins over the peer-to-peer protocol, as well as signaling support of this feature to peers.
  26 | +## Definitions
  27 | +
  28 | +- `[]byte`: arbitrary byte vector
  29 | +- `<N bytes>`: size `N` byte vector
  30 | +- `vector<Foo>`: arbitrary sized vector of `Foo`

---

  27 | +
  28 | +- `[]byte`: arbitrary byte vector
  29 | +- `<N bytes>`: size `N` byte vector
  30 | +- `vector<Foo>`: arbitrary sized vector of `Foo`
  31 | +- `CompactSize`: encoding of unsigned integers defined in peer-to-peer messages
  32 | +- `CompressAmount`: defined in the Function Appendix section

---

  51 | +| `0x05` | `P2SH`   | `<20 bytes>`                          | `OP_HASH160 20 <20 bytes> OP_EQUAL`                          |
  52 | +| `0x06` | `P2WSH`  | `<32 bytes>`                          | `OP_0 32 <32 bytes>`                                         |
  53 | +| `0x07` | `P2WPKH` | `<20 bytes>`                          | `OP_0 20 <20 bytes>`                                         |
  54 | +| `0x08` | `P2TR`   | `<32 byte X-only public key>`         | `OP_1 32 <32 bytes>`                                         |
  55 | +
  56 | +Scripts are serialized in this format by concatenating the `Prefix` and `Format` fields.

---

  60 | +#### Coin
  61 | +
  62 | +| Field                    | Type                          | Serialization | Description                                                                                                       |
  63 | +| :----------------------- | :---------------------------- | ------------- | ----------------------------------------------------------------------------------------------------------------- |
  64 | +| Input index              | 32 bit unsigned integer       | Little endian | The index in the block inputs for which this coin corresponds. The coinbase inputs are _excluded_ from this index |
  65 | +| Height and coinbase flag | Height code                   | Little endian |                                                                                                                   |

---

  16 | +# Motivation
  17 | +
  18 | +A current limitation of IBD is that it must be done sequentially. This is a result of the height, coinbase flag, input script, and amount of the block inputs being omitted from the data committed to by proof of work in the current block, and, thus, this data cannot be trusted if received over the wire naively. Using the SwiftSync protocol, a client is able to verify the correctness of this data, even if served by a potentially untrusted party. This is a property of the SwiftSync hash aggregate, which commits to the height, coinbase flag, script, and amount when creating and deleting coins.
  19 | +# Specification
  20 | +
  21 | +In Bitcoin Core, to roll-back the chain state in the event of a block reorganization, the height, coinbase flag, script and amount metadata for each input of a block are stored in a data structure known colloquially as "undo data". This terminology stems from its use to "undo" the effect of a block by repopulating the UTXO set with the coins that were spent by the reorganized block. To remain general in language, this data will be referred as "spent coins."

---

  18 | +A current limitation of IBD is that it must be done sequentially. This is a result of the height, coinbase flag, input script, and amount of the block inputs being omitted from the data committed to by proof of work in the current block, and, thus, this data cannot be trusted if received over the wire naively. Using the SwiftSync protocol, a client is able to verify the correctness of this data, even if served by a potentially untrusted party. This is a property of the SwiftSync hash aggregate, which commits to the height, coinbase flag, script, and amount when creating and deleting coins.
  19 | +# Specification
  20 | +
  21 | +In Bitcoin Core, to roll-back the chain state in the event of a block reorganization, the height, coinbase flag, script and amount metadata for each input of a block are stored in a data structure known colloquially as "undo data". This terminology stems from its use to "undo" the effect of a block by repopulating the UTXO set with the coins that were spent by the reorganized block. To remain general in language, this data will be referred as "spent coins."
  22 | +
  23 | +Bitcoin Core full archival nodes store spent coins for all blocks. This is useful in the context of SwiftSync, as no additional index must be created or maintained to serve this data to peers. There are, however, some discrepancies between how this data is serialized on disk in Bitcoin core and how this proposal seeks to serialize this data over the peer-to-peer protocol, which are detailed in the rationale section.

---

  15 | +
  16 | +Inputs of a Bitcoin block are referenced by the outpoint data structure. This poses a limitation during initial block download (IBD), such that a client must process blocks sequentially to validate the chain history. The SwiftSync protocol allows blocks to be evaluated in arbitrary order, however additional data is required that must be served over the peer-to-peer network. Namely, the creation height, coinbase flag, input script, and amount for each spent coin must be accessible to fully validate a block in a state-less manner. This document describes how to share this additional data over the peer to peer network.
  17 | +## Motivation
  18 | +
  19 | +A current limitation of IBD is that it must be done sequentially. This is a result of the height, coinbase flag, input script, and amount of the block inputs being omitted from the data committed to by proof of work in the current block, and, thus, this data cannot be trusted if received over the wire naively. Using the SwiftSync protocol, a client is able to verify the correctness of this data, even if served by a potentially untrusted party. This allows a significant improvement in IBD performance, as block downloads may be done in parallel.
  20 | +## Specification

---

  27 | +### Definitions
  28 | +
  29 | +- `[]byte`: arbitrary sequence of bytes with no fixed length
  30 | +- `<N bytes>`: byte vector of size N, where N is specified inline (e.g. <32 bytes>)
  31 | +- `vector<Foo>`: vector of arbitrary length of elements of type Foo
  32 | +- `CompactSize`: encoding of unsigned integers defined in peer-to-peer messages

---

  25 | +
  26 | +This section defines how to request and serve block spent coins over the peer-to-peer protocol, as well as signaling support of this feature to peers.
  27 | +### Definitions
  28 | +
  29 | +- `[]byte`: arbitrary sequence of bytes with no fixed length
  30 | +- `<N bytes>`: byte vector of size N, where N is specified inline (e.g. <32 bytes>)

---

  67 | +| Height and coinbase flag | Height code                   | Defined above |                                                                                                                   |
  68 | +| Script                   | Reconstructable script format | Defined above |                                                                                                                   |
  69 | +| Amount                   | 64 bit unsigned integer       | Defined above | Satoshi denominated value                                                                                         |
  70 | +### Messages
  71 | +
  72 | +#### MSG_GET_SPENT_COINS

---

  99 | +
 100 | +Support for serving historical block undo data is advertised by a service bit. 
 101 | +
 102 | +| Field             | Value      |
 103 | +| :----------------- | :---------- |
 104 | +| `NODE_BLOCK_UNDO` | `1 << ???` |

---

  81 | +| `blockhash` | 32 byte vector          | Hash of the block for which inputs are requested                          |
  82 | +| `cutoff`    | 32 bit unsigned integer | If set greater than zero, only include coins created _before_ this height |
  83 | +
  84 | +#### MSG_SPENT_COINS
  85 | +
  86 | +`MSG_SPENT_COINS` defines the data structure for inputs of a block.

---

  13 | +## Abstract
  14 | +
  15 | +_SwiftSync_ is a protocol to accelerate initial block download (IBD) using existing cryptographic primitives and minimal state. The protocol is comprised of hash aggregate for a set of elements and a "hintsfile" to indicate the spent-ness of outputs in the chain history. Using these hints, clients may perform IBD in parallel, which maximizes the use of existing system resources and shifts the performance limitations to internet quality.
  16 | +## Motivation
  17 | +
  18 | +Initial block download is the first user experience when using Bitcoin software, and, moreover, is a bootstrapping cost for second layer protocols. Improvements to this process benefit end-users and scaling protocols alike. IBD faces two limitations. First, although the lifetime of coins demonstrates an empirical distribution, cache misses occur for coins that are deleted. This creates unnecessary disk I/O and database compaction. Secondly, given the structure of a block, coins that are spent are indexed by their outpoint. This creates a requirement for clients to maintain a cache to fetch coin metadata associated with an outpoint. _SwiftSync_ alleviates both of these limitations, allowing for IBD in as fast as a client can download blocks and verify signatures.

---

 148 | +
 149 | +An _unspendable output_ is defined as:
 150 | +
 151 | +- An output with script length over 10,000 OR
 152 | +- An output beginning with `OP_RETURN` OR
 153 | +- A BIP-30 unspendable coinbase output

---

 159 | +1. Set the current index to `0`
 160 | +1. While outputs remain:
 161 | +   1. If the output is _unspendable_, continue
 162 | +   1. Query the UTXO set. If the output is not in the UTXO set, increment the current index. Otherwise, write the
 163 | +      current index to the vector and go back to step 3.
 164 | +1. Write the Elias-Fano encoding of the vector to file.

---

 178 | +yet the implementation is concise and does not require dependencies on third party libraries. As of block height
 179 | +930,000, the UTXO set may be represented in 119mb with this method, which is well within the 450mb `dbcache` requirement
 180 | +in Bitcoin Core, and reasonable for most clients to hold directly in memory. This encoding represents elements in $2n +
 181 | +n \\lceil \\log_2(m/n) \\rceil$ bits, which is within a reasonable bound of the theoretical optimum.
 182 | +
 183 | +Partitioning the hints by block is an intuitive choice, and allows for efficient random access of hints. Groupings of

---

 191 | +
 192 | +This document describes how to encode a hintsfile without additional dependencies, but developers and users willing to
 193 | +use generic compression algorithms like `gzip` or `zstd` may be able to compress the hints representation further. This
 194 | +would indicate there are still optimizations to be made with the format of the hints, however the complexity of the
 195 | +encoding and decoding may also increase. Developers and users should encode hints in any format that is suitable for
 196 | +their dependency, size, and memory requirements.

---

 198 | +## Distribution
 199 | +
 200 | +A malicious hintsfile distributor cannot lead a client to accepting an invalid UTXO set state, but they can expend time
 201 | +and resources of a client attempting to perform IBD with SwiftSync. Clients SHOULD obtain a hintsfile from a party that
 202 | +has a moral, financial, or otherwise incentive-aligned reason to provide truthful data. Examples of such a party include
 203 | +local community leaders or meetup organizers that have a direct social incentive to provide a useful hintsfile to users.

---

---

  41 | +output (UTXO) set indeed corresponds to the chain history downloaded from peers.
  42 | +
  43 | +A key invariant is that a UTXO set state at height $n$ is equivalent to all of the outputs created in the chain history,
  44 | +less all of the inputs:
  45 | +
  46 | +$Outputs - UTXO\_{n} = Inputs$

---

  58 | +client may compute two aggregates, and compare the values at the end of the protocol. The _aggregate_ is defined over
  59 | +the data structure of the elements and a hashing function. It is recommended, but not strictly required, that a client
  60 | +uses the typical SHA-256 hash, with an additional randomly generated salt value[^2]. The elements of the set a client
  61 | +compares are _coins_, which are defined as the following:
  62 | +
  63 | +$Coin = Creation Height + Coinbase Flag + Output Script + Amount + Outpoint$

---

  80 | +1. Using the undo data, validate the block. A non-exhaustive but explicit list of steps include:
  81 | +   1. Check the coinbase does not over-claim the block subsidy
  82 | +   1. Check the number of signature operations
  83 | +   1. Validate all script executions succeed
  84 | +   1. Validate non-contextual checks like merkle roots and timestamps
  85 | +   1. If the block is invalid, disconnect the peer. If the block is valid, continue

---

  81 | +   1. Check the coinbase does not over-claim the block subsidy
  82 | +   1. Check the number of signature operations
  83 | +   1. Validate all script executions succeed
  84 | +   1. Validate non-contextual checks like merkle roots and timestamps
  85 | +   1. If the block is invalid, disconnect the peer. If the block is valid, continue
  86 | +1. For all inputs, except the coinbase, add them to $Agg\_{inputs}$

---

  85 | +   1. If the block is invalid, disconnect the peer. If the block is valid, continue
  86 | +1. For all inputs, except the coinbase, add them to $Agg\_{inputs}$
  87 | +1. For all outputs:
  88 | +   1. If the output is _unspendable_, continue
  89 | +   1. Add the output to $UTXO\_{n}$ if the output is in $Hintsfile\_{n}$ and continue
  90 | +   1. Otherwise, add the output to $Agg\_{outputs}$

---

  89 | +   1. Add the output to $UTXO\_{n}$ if the output is in $Hintsfile\_{n}$ and continue
  90 | +   1. Otherwise, add the output to $Agg\_{outputs}$
  91 | +
  92 | +Notice here that a client does not have to download blocks in any particular order, and may download blocks from
  93 | +multiple peers at a time. A client then verifies $Agg\_{outputs} = Agg\_{inputs}$ once they have arrived at height
  94 | +$n$[^1]. If the verification succeeds, the client accepts $UTXO\_{n}$ as valid. In the failure case, the client rejects

---

 130 | +
 131 | +- [`swiftsync`](https://github.com/2140-dev/swiftsync) Rust implementation
 132 | +
 133 | +## Acknowledgements
 134 | +
 135 | +Kudos to my colleague Ruben Somsen for creating the protocol described in this specification

---

  70 | +
  71 | +### Protocol
  72 | +
  73 | +Block validation when performing _SwiftSync_ is nearly the same, only with a few additional steps. First, a client
  74 | +requires a $Hintsfile\_{n}$ and two aggregates, one for block inputs $Agg\_{inputs}$, one for block outputs
  75 | +$Agg\_{outputs}$

---

   0 | @@ -0,0 +1,269 @@
   1 | +```
   2 | +  BIP: ?
   3 | +  Layer: Peer Services
   4 | +  Title: Peer sharing of block spent coins

---

 134 | +Support for serving historical block undo data is advertised by a feature message, introduced by
 135 | +[BIP-434](https://github.com/bitcoin/bips/blob/master/bip-0434.md).
 136 | +
 137 | +| featureid           | featuredata |
 138 | +| :------------------ | :---------- |
 139 | +| `blockspentcoinsv1` | `0x00`      |

---

 146 | +The lifetime, or interval between creation and spending height, of the coins on the Bitcoin blockchain demonstrate an
 147 | +empirical phenomena that the majority of coins are spent within 100 blocks. In fact, approximately 41 percent of coins
 148 | +are spent within 10 blocks at the time of writing[^1]. Clients may leverage this to reduce the bandwidth required to
 149 | +fetch undo data by using an in-memory cache. For example, a client may store coins that were created in a 5 block
 150 | +window, and request only coins that are older than this height via the `cutoff` filter. This results in a significant
 151 | +bandwidth reduction at the cost of a cache that can be set dynamically by the client depending on available memory.

---

   0 | @@ -0,0 +1,267 @@
   1 | +```
   2 | +  BIP: ?
   3 | +  Layer: Peer Services
   4 | +  Title: Peer sharing of block spent coins
   5 | +  Authors: Robert Netzke <bips@2140.dev>
   6 | +  Deputies: Ruben Somsen <bips@2140.dev>

---

  18 | +protocol allows blocks to be evaluated in arbitrary order, however additional data is required that must be served over
  19 | +the peer-to-peer network. This document describes how to share this data over the peer to peer network.
  20 | +
  21 | +## Motivation
  22 | +
  23 | +A current limitation of IBD is that it must be done sequentially. This is a result of the height, coinbase flag, input

---

  22 | +
  23 | +A current limitation of IBD is that it must be done sequentially. This is a result of the height, coinbase flag, input
  24 | +script, and amount of the block inputs being omitted from the data committed to by proof of work in the current block,
  25 | +and, thus, this data cannot be trusted if received over the wire naively. Using the SwiftSync protocol, a client is able
  26 | +to verify the correctness of this data, even if served by a potentially untrusted party. This allows a significant
  27 | +improvement in IBD performance, as block downloads may be done in parallel.

---

  27 | +improvement in IBD performance, as block downloads may be done in parallel.
  28 | +
  29 | +## Specification
  30 | +
  31 | +In Bitcoin Core, to roll-back the chain state in the event of a block reorganization, the height, coinbase flag, script
  32 | +and amount metadata for each input of a block are stored in a data structure known colloquially as "undo data". This

---

  57 | +### Data structures
  58 | +
  59 | +#### Height Code
  60 | +
  61 | +When validating a block, a client must confirm coinbase outputs are mature, which is given by the height of the coin.
  62 | +The height and coinbase flag are encoded as a 32 bit integer. To encode the height and flag, binary left shift the

---

  54 | +The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
  55 | +"OPTIONAL" in this document are to be interpreted as described in RFC 2119.
  56 | +
  57 | +### Data structures
  58 | +
  59 | +#### Height Code

---

  62 | +The height and coinbase flag are encoded as a 32 bit integer. To encode the height and flag, binary left shift the
  63 | +height one bit, treat the coinbase flag as a bit, insert it into the newly opened bit position. To decode the height,
  64 | +binary right shift the code. To decode the coinbase flag, mask the first bit position of the header code and interpret
  65 | +the bit as a boolean.
  66 | +
  67 | +Take, for example, a height with binary encoding `0010 0111`. To encode a coinbase output at this height, one begins

---

  67 | +Take, for example, a height with binary encoding `0010 0111`. To encode a coinbase output at this height, one begins
  68 | +with a left shift: `0100 1110`, and places the coinbase flag in the least significant bit: `0100 1111`.
  69 | +
  70 | +#### Reconstructable Script Format
  71 | +
  72 | +Scripts are serialized in this format by concatenating the `Prefix` and `Format` fields specified below.

---

  75 | +| :----- | :------- | :------------------------------------ | :----------------------------------------------------------- |
  76 | +| `0x00` | Unknown  | `CompactSize(Len([]bytes)) + []bytes` | `[]bytes`                                                    |
  77 | +| `0x01` | `P2PKH`  | `<20 bytes>`                          | `OP_DUP OP_HASH160 20 <20 bytes> OP_EQUALVERIFY OP_CHECKSIG` |
  78 | +| `0x02` | `P2PK`   | `<32-byte public key (0x02 parity)>`  | `33 0x02 <32 byte public key> OP_CHECKSIG`                   |
  79 | +| `0x03` | `P2PK`   | `<32-byte public key (0x03 parity)>`  | `33 0x03 <32 byte public key> OP_CHECKSIG`                   |
  80 | +| `0x04` | `P2PK`   | `<64 byte public key>`                | `65 0x04 <64 byte public key> OP_CHECKSIG`                   |

---

 106 | +Define `cmdString` as `getbspent`. Define BIP-324 message type as ???.
 107 | +
 108 | +| Field       | Type                    | Description                                                          |
 109 | +| :---------- | :---------------------- | :------------------------------------------------------------------- |
 110 | +| `blockhash` | `<32 bytes>`            | Hash of the block for which inputs are requested.                    |
 111 | +| `cutoff`    | 32-bit unsigned integer | If greater than zero, include only coins created before this height. |

---

 121 | +| `blockhash` | `<32 bytes>`                     | Block hash these coins are spent from.            |
 122 | +| `len`       | `CompactSize(Len(vector<Coin>))` | Length of the coins vector.                       |
 123 | +| `coins`     | `vector<Coin>`                   | Coins spent, after filtering on request `cutoff`. |
 124 | +
 125 | +A client supporting the `bspent` MUST include coins created _before_ the `cutoff` field in `getbspent` requests. A
 126 | +client receiving a `bspent` message with un-requested or missing coins MUST disconnect from the serving peer. A client

---

 134 | +| featureid           | featuredata |
 135 | +| :------------------ | :---------- |
 136 | +| `blockspentcoinsv1` | `0x00`      |
 137 | +
 138 | +A client advertising this service bit SHOULD respond to `getbspent` messages, subject to rate-limiting and bandwidth
 139 | +limiting.

---

 143 | +The lifetime, or interval between creation and spending height, of the coins on the Bitcoin blockchain demonstrate an
 144 | +empirical phenomena that the majority of coins are spent within 100 blocks. In fact, approximately 41 percent of coins
 145 | +are spent within 10 blocks at the time of writing[^1]. Clients may leverage this to reduce the bandwidth required to
 146 | +fetch spent coins by using an in-memory cache. For example, a client may store coins that were created in a 5 block
 147 | +window, and request only coins that are older than this height via the `cutoff` filter. This results in a significant
 148 | +bandwidth reduction at the cost of a cache that can be set dynamically by the client depending on available memory.

---

 149 | +
 150 | +Beyond the use of a dynamic coin height filter, there are additional reasons to not simply read the spent coins from
 151 | +disk and send it over the wire. Legacy fields (`nVersion`) are set to `0x00` when writing and reading this data to
 152 | +maintain compatibility of disk format with old clients. Furthermore, using the amount compression specified above, an
 153 | +11gb reduction in bandwidth is achieved. The application of `VARINT` as opposed to `CompactSize` offers a further
 154 | +reduction of 4gb, however the `VARINT` primitive is currently a Bitcoin Core implementation detail. Reusing existing

---

 236 | +```
 237 | +
 238 | +## Compatibility
 239 | +
 240 | +Clients seeking to perform fully-validating SwiftSync require peers that serve undo data. Serving data requires no
 241 | +additional index and may be enabled via the service bit.

---

   5 | +  Authors: Robert Netzke <bips@2140.dev>
   6 | +  Deputies: Ruben Somsen <bips@2140.dev>
   7 | +  Status: Draft
   8 | +  Type: Specification
   9 | +  Assigned: ?
  10 | +  License: BSD-3-Clause

---

  21 | +## Motivation
  22 | +
  23 | +SwiftSync can improve the user experience by accelerating IBD, however the protocol requires the client verify a UTXO
  24 | +set corresponds to the blockchain history they received. Rather than simply encoding and distributing the UTXO set, a
  25 | +far smaller representation may be computed and shared. Intuitively, just as how it is cheap for programs to share
  26 | +pointers to objects in memory, we define a "hintsfile" that encodes pointers to unspent outputs.

---

  56 | +We define the following:
  57 | +
  58 | +- Let ${ i\_{0}, ..., i\_{n-1} }$ be a list of $n$ elements where $i\_{n-1} = m$
  59 | +- Let $\\ell(m, n)$ be the function that determines the number of low bits to use: $\\ell(m, n) = \\left\\lfloor \\log_2
  60 | +  \\ \\left(\\frac{m+1}{n}\\right) \\right\\rfloor$
  61 | +- Let $\\text{unary}(q)$ be the following function: $\\text{unary}(q) = \\underbrace{0\\cdots0}\_{q}1$

---

 193 | +## References
 194 | +
 195 | +- [Research repository](https://github.com/rustaceanrob/swiftsync-research)
 196 | +- [Explanatory article](https://t.holmium.no/dia/elias-fano/#_representation_1_fixed_size_compact_encoding)
 197 | +- [Paper](https://drops.dagstuhl.de/storage/00lipics/lipics-vol078-cpm2017/LIPIcs.CPM.2017.30/LIPIcs.CPM.2017.30.pdf)
 198 | +

---

  43 | +to size $m$? In other words, for a block with $n$ unspent outputs, what is an efficient representation?
  44 | +
  45 | +This formulation has a known theoretical optimum of $\\log_2 \\binom{m}{n}$ bits. _Elias-Fano_ developed a
  46 | +representation that is reasonably close to this optimum in a concise and maintainable format.
  47 | +
  48 | +### Elias-Fano Encoding

---

  32 | +
  33 | +Our goal is to indicate which outputs in a block, or set of blocks, will remain unspent at a particular chain height.
  34 | +There are many ways to do so, however an intuitive representation is a
  35 | +[bitset](https://en.cppreference.com/w/cpp/utility/bitset.html). Each output in a block is assigned a bit, with a `0`
  36 | +bit denoting the output will be spent, and a `1` to denote the output is unspent. For a block of 8 outputs, we may
  37 | +arrive at a bitset of `1000 0010`, which conveys the 0th and 6th index are UTXOs.

---

  38 | +
  39 | +Empirically, this representation does poorly, as the vast majority of outputs are spent. In fact, simply recording the
  40 | +indices within the block that will be unspent is a more optimal approach than the bitset. For our example above, that
  41 | +would be recording the numbers `0, 6`. To efficiently represent this data, we may formulate the problem as the
  42 | +following: what is the most efficient way to represent $n$ random, monotonically increasing indices less than or equal
  43 | +to size $m$? In other words, for a block with $n$ unspent outputs, what is an efficient representation?

---

  46 | +representation that is reasonably close to this optimum in a concise and maintainable format.
  47 | +
  48 | +### Elias-Fano Encoding
  49 | +
  50 | +Suppose we would like to encode $n$ monotonically increasing elements ${ i\_{0}, ..., i\_{n - 1} }$ where $i\_{n - 1} =
  51 | +m$. _Elias-Fano_ builds on the intuition that numbers may share bits in their binary representation. Consider the

---

  48 | +### Elias-Fano Encoding
  49 | +
  50 | +Suppose we would like to encode $n$ monotonically increasing elements ${ i\_{0}, ..., i\_{n - 1} }$ where $i\_{n - 1} =
  51 | +m$. _Elias-Fano_ builds on the intuition that numbers may share bits in their binary representation. Consider the
  52 | +integers 6 and 7. The binary representation of 6 is `0110` while the binary representation of 7 is `0111`, differing by
  53 | +only one bit. This observation may be used to efficiently store elements. For the lowest bits of the elements, we will

---

  49 | +
  50 | +Suppose we would like to encode $n$ monotonically increasing elements ${ i\_{0}, ..., i\_{n - 1} }$ where $i\_{n - 1} =
  51 | +m$. _Elias-Fano_ builds on the intuition that numbers may share bits in their binary representation. Consider the
  52 | +integers 6 and 7. The binary representation of 6 is `0110` while the binary representation of 7 is `0111`, differing by
  53 | +only one bit. This observation may be used to efficiently store elements. For the lowest bits of the elements, we will
  54 | +represent them in a bitset, and for the highest bits, we will represent the difference in bits as unary.

---

  58 | +- Let ${ i\_{0}, ..., i\_{n-1} }$ be a list of $n$ elements where $i\_{n-1} = m$
  59 | +- Let $\\ell(m, n)$ be the function that determines the number of low bits to use: $\\ell(m, n) = \\left\\lfloor \\log_2
  60 | +  \\ \\left(\\frac{m+1}{n}\\right) \\right\\rfloor$
  61 | +- Let $\\text{unary}(q)$ be the following function: $\\text{unary}(q) = \\underbrace{0\\cdots0}\_{q}1$
  62 | +
  63 | +We start by determining $\\ell$ for a given $n$ and $m$. For each $i$, take the $\\ell$ least significant bits and

---

  60 | +  \\ \\left(\\frac{m+1}{n}\\right) \\right\\rfloor$
  61 | +- Let $\\text{unary}(q)$ be the following function: $\\text{unary}(q) = \\underbrace{0\\cdots0}\_{q}1$
  62 | +
  63 | +We start by determining $\\ell$ for a given $n$ and $m$. For each $i$, take the $\\ell$ least significant bits and
  64 | +append them, most significant bit ordering, to a bitset $L$. Next, iterate over each element and take the remaining most
  65 | +significant bits, then record the difference between the last element's high bits and the current element's high bits.

---

  66 | +Record that number using the $\\text unary$ function, and append the unary to a vector $H$. The final representation is
  67 | +$m$, $n$, $L$, $H$.
  68 | +
  69 | +### Worked Example
  70 | +
  71 | +Suppose $S = [3, 7, 12]$. Then $n=3$ and $m=12$.

---

  79 | +
  80 | +| Element | Binary | Upper (`value >> 2`) | Lower (`value & 0b11`) |
  81 | +| :------ | :----- | :------------------- | :--------------------- |
  82 | +| 3       | `0011` | `00` → 0             | `11` → 3               |
  83 | +| 7       | `0111` | `01` → 1             | `11` → 3               |
  84 | +| 12      | `1100` | `11` → 3             | `00` → 0               |

---

  74 | +
  75 | +We start by computing $\\ell$:
  76 | +
  77 | +$\\ell = \\left\\lfloor \\log_2\\left(\\frac{m+1}{n}\\right) \\right\\rfloor = \\left\\lfloor
  78 | +\\log_2\\left(\\frac{13}{3}\\right) \\right\\rfloor = \\lfloor \\log_2(4.33) \\rfloor = \\lfloor 2.11 \\rfloor = 2$
  79 | +

---

  89 | +111100$.
  90 | +
  91 | +#### 3. Encode the high bits
  92 | +
  93 | +The upper values are $0, 1, 3$. We encode the gaps between consecutive upper values in unary. Note that the first
  94 | +element does not have a previous upper value to compare to, so $0$ is used.

---

  13 | +```
  14 | +
  15 | +## Abstract
  16 | +
  17 | +_SwiftSync_ is a protocol to accelerate initial block download (IBD) using existing cryptographic primitives and minimal
  18 | +state. The protocol is comprised of hash aggregate for a set of elements and a "hintsfile" to indicate the spent-ness of

---

  25 | +for second layer protocols. Improvements to this process benefit end-users and scaling protocols alike. IBD faces two
  26 | +limitations. First, although the lifetime of coins demonstrates an empirical distribution, cache misses occur for coins
  27 | +that are deleted. This creates unnecessary disk I/O and database compaction. Secondly, given the structure of a block,
  28 | +coins that are spent are indexed by their outpoint. This creates a requirement for clients to maintain a cache to fetch
  29 | +coin metadata associated with an outpoint. _SwiftSync_ alleviates both of these limitations, allowing for IBD in as fast
  30 | +as a client can download blocks and verify signatures.

---

  33 | +
  34 | +### Definitions
  35 | +
  36 | +- $H$: A hashing function
  37 | +- $Hintsfile\_{n}$: Defined in BIP ???
  38 | +- $UTXO\_{n}$: Unspent outputs at block height $n$

---

  36 | +- $H$: A hashing function
  37 | +- $Hintsfile\_{n}$: Defined in BIP ???
  38 | +- $UTXO\_{n}$: Unspent outputs at block height $n$
  39 | +
  40 | +_SwiftSync_ builds on a common observation in cryptography, that _verification_ is often orders of magnitude more
  41 | +performant than _computation_. What a client seeks to verify when performing _SwiftSync_ is that a unspent transaction

---

  52 | +
  53 | +As a final note, some coins are guaranteed to be impossible to spend. We define an _unspendable output_ is defined as:
  54 | +
  55 | +- An output with script length over 10,000 OR
  56 | +- An output beginning with `OP_RETURN` OR
  57 | +- A [BIP-30](https://github.com/bitcoin/bips/blob/master/bip-0030.mediawiki) unspendable coinbase output

---

  59 | +The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
  60 | +"OPTIONAL" in this document are to be interpreted as described in RFC 2119.
  61 | +
  62 | +### Aggregation
  63 | +
  64 | +A client must compare $Outputs - UTXO\_{n}$ with $Inputs$ in a succinct way. Rather than say, comparing the lists, a

---

  94 | +
  95 | +When downloading blocks, _SwiftSync_ clients will do the following:
  96 | +
  97 | +1. Download the required spent coins data defined in BIP ???.
  98 | +1. Using the undo data, validate the block. If the block is invalid, fail.
  99 | +1. For all inputs, except the coinbase, add the hashes to $Agg\_{inputs}$ using the spent coin data.

---

 101 | +   1. If the output is _unspendable_, continue
 102 | +   1. If the output is in $Hintsfile\_{n}$, add the output to $UTXO\_{n}$. Else, add the hash of the output coin to
 103 | +      $Agg\_{outputs}$.
 104 | +
 105 | +Notice here that a client does not have to download blocks in any particular order, and may download blocks from
 106 | +multiple peers at a time. A client then verifies $Agg\_{outputs} = Agg\_{inputs}$ once they have arrived at height

---

 120 | +## Note on BIP-30 and BIP-34
 121 | +
 122 | +During the period between the genesis block and BIP-34 activation, a _SwiftSync_ client must check for duplicate
 123 | +coinbase outputs. A cache of these outputs is modest in memory footprint, and may be easily added and queried for the
 124 | +fixed block range. More information on this caveat is detailed in
 125 | +[this article](https://gist.github.com/RubenSomsen/a02b9071bf81b922dcc9edea7d810b7c).

---

 144 | +- [`swiftsync`](https://github.com/2140-dev/swiftsync) Rust implementation
 145 | +
 146 | +## References
 147 | +
 148 | +- [Original proposal](https://gist.github.com/RubenSomsen/a61a37d14182ccd78760e477c78133cd)
 149 | +

---