These are the 3 BIPs that describe Utreexo, a consensus-compatible (non-soft fork) way to send and verify transactions without storing the full UTXO set.
The 3 BIPs are for:
Mailing list post: https://groups.google.com/g/bitcoindev/c/W1lxBraKG_E
21 | +This document **does not** describe how to validate blocks and transactions using the provided data, see [Utreexo - Validation Layer](./utreexo-validation-bip.md) for more details. 22 | + 23 | +## Motivation 24 | + 25 | +Utreexo nodes require the inclusion proof to fully validate blocks and transactions. 26 | +Each block has an corresponding inclusion proof with it and this inclusion proof for blocks up to height 906,937 requires an additional 631.85GB, which is roughly 40GB less than the size of the block data.
an -> a
there are two, would be this one
Each block has a corresponding inclusion proof with it and this inclusion proof for blocks up to height 906,937 requires an additional 631.85GB, which is roughly 40GB less than the size of the block data.
Addressed in the latest push
22 | + 23 | +## Motivation 24 | + 25 | +Utreexo nodes require the inclusion proof to fully validate blocks and transactions. 26 | +Each block has an corresponding inclusion proof with it and this inclusion proof for blocks up to height 906,937 requires an additional 631.85GB, which is roughly 40GB less than the size of the block data. 27 | +Each transaction also has an corresponding inclusion proof with it and for normal transaction relay, the proof is roughly 3 times the size of the transaction.
an -> a
Addressed in the latest push
45 | +3. Archive nodes 46 | + 47 | +CSNs have the goal of minimizing data storage and download while performing block validation. 48 | +Archive and bridge nodes store more data and provide this data to CSNs. 49 | + 50 | +Bridge nodes are nodes that can add inclusion proofs to mempool transactions, support the same set of messages as CSNs, and are in fact should be indistinguishable from CSNs on the network.
are in fact should -> should in fact
Addressed in the latest push
93 | +### Transaction relay 94 | + 95 | + 96 | + 97 | +Current transaction relay is done by sending an inv message with the hash of the transaction and a type field that denotes that this hash represents a transaction. 98 | +If the node receiving the inv is does not have a tx matching that hash, it then requests for it using a getdata message.
Removed in the latest push
100 | + 101 | + 102 | +The transaction relay for Utreexo nodes doesn't add any extra round trips. 103 | +However, it does include extra inventory vectors in the inv message. 104 | + 105 | +We introduce a new inventory vector type called `utreexoproofhash` which make up the extra information that a Utreexo node will receive.
make -> includes
s/ which make/, which makes/
I'll go with , which makes since includes sounds like the utreexoproofhash invvect has other information as well
EDIT: Replaced with , which makes in the latest push
297 | +| Field | Type | Description | 298 | +|----------------------------|-------------------------------------|-----------------------------------------------| 299 | +| length of the Utreexo TTLs | varint | The length of the Utreexo summaries | 300 | +| Utreexo TTLs | vector of Utreexo summaries | The vector of the requested Utreexo summaries | 301 | +| length of the proof hashes | varint | The length of the proof hashes | 302 | +| proof hashes | vector of 32 byte hashes | The vector of the requested Utreexo summaries |
requested proof hashes*?
Addressed in the latest push
237 | + 238 | +| Field | Type | Description | 239 | +|--------------|---------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------| 240 | +| block height | uint32 | The time-to-live value of a leaf in the Utreexo merkle forest. The value is determined by the amount of leaves that were added to the accumulator since its creation | 241 | +| length | varint | The length of the TTLs | 242 | +| TTLs | vector of TTL infos | position in the Utreexo merkle forest when the leaf was removed |
description?
Added the correct description in the latest push
189 | +A compact leaf data is defined as: 190 | + 191 | +| Field | type | Description | 192 | +|--------------|------------------------------|-----------------| 193 | +| header code | uint32 | This is a value obtained by left shifting the block height that confirmed this transaction, and then OR-ing it with 1, only if this transaction is a coinbase. | 194 | +| amount | int64 | The amount in sats locked on this output |
should probably be unsigned
It makes sense to have it as int64 as CAmount is represented as int64 in code https://github.com/bitcoin/bitcoin/blob/273e600e65c2e31a6e9a0bd72b40672aaa503b08/src/consensus/amount.h#L12
Other implementations follow this as well:https://github.com/btcsuite/btcd/blob/baebb836c2d4692da3de3b0d437f4da6ce915546/wire/msgtx.go#L337
some typos
8 | +Comments-URI: TBD 9 | +Status: Draft 10 | +Type: Specification 11 | +Created: 2024-08-08 12 | +License: BSD-3-Clause 13 | +Depends: BIP-???? (Utreexo - Peer Services)
Per BIPs 2 and 3, this would be "Requires" (and currently refers to the same BIP)
Requires: BIP-???? (Utreexo - Peer Services)
Addressed in the latest push
8 | +Comments-URI: TBD 9 | +Status: Draft 10 | +Type: Specification 11 | +Created: 2023-10-01 12 | +License: BSD-3-Clause 13 | +Depends: BIP-???? (Utreexo Accumulator Specification)
Per BIPs 2 and 3, this would be "Requires"
Requires: BIP-???? (Utreexo Accumulator Specification)
Addressed in the latest push
8 | +Comments-URI: TBD 9 | +Status: Draft 10 | +Type: Specification 11 | +Created: 2025-06-18 12 | +License: BSD-3-Clause 13 | +Depends: BIP-???? (Utreexo Accumulator Specification)
Refers to the same document. If correct, this line should be dropped.
Dropped in the latest push
51 | +the accumulator tracks the current set of unspent transaction outputs (UTXOs). 52 | + 53 | +The Utreexo accumulator is based on an append-only Merkle tree design introduced in [^1], 54 | +which provides logarithmic-sized inclusion proofs. Utreexo extends this design to support dynamic updates, 55 | +specifically enabling deletions from the set—a requirement for tracking UTXO spends in Bitcoin. 56 | +To accommodate this, Utreexo increases the storage requirement for the accumulator state to O(log₂(N)),
"increases the requirement" -- perhaps mention here "compared to the UTXO set"
To accommodate this, Utreexo increases the storage requirement for the accumulator state to $O(log_2(N))$,
LaTeX renderers don't play nice with this unicode symbol.
Ah the paragraph could be worded better.
It's referring to how the merkle forest is expanded to support more leaves. Like sparse merkle trees, you pre-allocate the Utreexo accumulator to hold 2^n leaves. If you want to hold (2^n)+1 leaves, you need to resize the accumulator to hold 2^n+1 leaves.
Oh I read it wrong too. It increases the requirements vs the paper referenced in [^1].
Fixing this...
Changed the sentence to improve legibility
Addressed in the latest push
34 | +long-term scalability concern. 35 | + 36 | +Utreexo is a dynamic accumulator that enables the UTXO set to be represented in just a few kilobytes, 37 | +by requiring peers to provide additional proof data to verify the inclusion of a UTXO in the 38 | +accumulator. This allows for the construction of extremely lightweight nodes capable of performing 39 | +the same validation as a full node, without the need to store the entire UTXO set.
The preceding 3 paragraphs seem to be duplicates of the accumulator BIP that this BIP requires. Can perhaps remove them or refer to the accumulator BIP motivation.
Removed the preceding 3 paragraphs in the latest push
550 | +While RSA accumulators and similar constructions offer significant advantages in proof size—often allowing a 551 | +single proof to cover an entire block's worth of UTXOs—the trade-offs in proof generation cost and latency are 552 | +substantial. In RSA-based designs, creating a proof for any given UTXO at arbitrary times can be computationally 553 | +intensive, especially as the number of UTXOs grows. 554 | + 555 | +Utreexo's design is driven by the need for Bridge Nodes: nodes that maintain backward compatibility with existing
This BIP appears to be missing a required backwards compatibility section.
Added a backwards compatibility section
Thank you for proposing these drafts. They already look quite complete with respect to the editorial requirements (BIPs 2 and 3). I've done a cursory first pass. No immediate conceptual feedback. A few editorial comments follow; feel free to ignore them during conceptual review until they are applicable.
61 | +The Utreexo accumulator consists of a set of Merkle trees: specifically, perfect binary trees with $2^n$ elements, 62 | +where each node in the tree contains a 32-byte hash. The elements being stored appear at the leaves—the bottom layer of the tree. 63 | +The topmost node is referred to as the "root," while nodes located between the leaves and the root are called "intermediate nodes." 64 | + 65 | +Any integer number of elements ($N$) can be represented as a forest of such trees. On average, a set of N elements will require 66 | +approximately $\frac{log₂(N)}{2}$ trees. The number and sizes of trees are determined by the binary representation of $N$:
approximately $\frac{log_2(N)}{2}$ trees. The number and sizes of trees are determined by the binary representation of $N$:
LaTeX renderers don't play nice with this unicode symbol.
Addressed in the latest push
You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol. Right now you just link to a paper from 2011. But that paper is out of date now that hardware support for SHA-256 has become common.
I strongly recommend replacing SHA-256 with SHAKE256 (from the SHA-3 standard) for the following reasons:
| Characteristic | SHA-256 | SHAKE256 |
|---|---|---|
| Algorithm Family | SHA-2 | SHA-3 (Keccak) |
| Output Flexibility | Fixed 256-bit | Arbitrary length |
| Security Properties | Vulnerable to length-extension | Resistant to length-extension |
| Internal Structure | Merkle-Damgård | Sponge function |
| Standardization | NIST FIPS 180-4 | NIST FIPS 202 |
Input: Bitcoin
SHAKE256 (512-bit output):
6beb0661ba1fa7289bf359fbb81550bd9641cf5abc62a14d466c421c8a86e528e027632ec0e7ceb994650566f3c8258af2240333b6d0e9186766fd2c1ebb763a
SHAKE256 (256-bit output):
6beb0661ba1fa7289bf359fbb81550bd9641cf5abc62a14d466c421c8a86e528
For detailed cryptographic differences:
Cryptographic Comparison: SHA-2 vs SHA-3
You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol. Right now you just link to a paper from 2011. But that paper is out of date now that hardware support for SHA-256 has become common.
Sure we can update the accumulator BIP with benchmarks for SHA512/256 vs SHA256.
But could you link to the aforementioned justifications for the other parts of the Bitcoin protocol that use SHA512?
I strongly recommend replacing SHA-256 with SHAKE256 (from the SHA-3 standard) for the following reasons:
SHAKE256 is not used in Bitcoin and introduces a new hash which increases the trust-assumption. We do not want to do this.
The reliance of Bitcoin on SHA-2—a legacy hash function designed by the National Security Agency (NSA)—introduces non-trivial security risks, particularly when considering the often-dismissed threat posed by quantum adversaries.
Migrating to SHAKE256 (a variant of SHA-3) would represent a meaningful improvement, though such a change merely delays the inevitable: Bitcoin must eventually transition to a quantum-resistant cryptographic framework. When this occurs—and it will, regardless of opposition—SHA-2, along with ECDSA private keys, public keys, and signatures, will become obsolete.
See: Lenght extension attack (Bitcoin is vulnerable because it's using SHA-256)
Some friendly moderation to keep the discussion focused on technical review -- thanks.
The reliance of Bitcoin on SHA-2—a legacy hash function designed by the National Security Agency (NSA)—introduces non-trivial security risks, particularly when considering the often-dismissed threat posed by quantum adversaries.
SHA256 and SHA512 are quantum resistent.
Migrating to SHAKE256 (a variant of SHA-3) would represent a meaningful improvement, though such a change merely delays the inevitable: Bitcoin must eventually transition to a quantum-resistant cryptographic framework. When this occurs—and it will, regardless of opposition—SHA-2, along with ECDSA private keys, public keys, and signatures, will become obsolete. See: Lenght extension attack (Bitcoin is vulnerable because it's using SHA-256)
Ok but this has nothing to do with this BIP.
@1BitcoinBoWP1FZ4xwTNkq6XksKidmgYYw, please cut out the LLM generated comments. If any of us were interested in seeing an LLM’s prediction of what might be said about a topic, we could prompt one ourselves.
On Mon, Aug 18, 2025 at 04:06:51AM -0700, Calvin Kim wrote:
kcalvinalvin left a comment (bitcoin/bips#1923)
You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol. Right now you just link to a paper from 2011. But that paper is out of date now that hardware support for SHA-256 has become common.
Sure we can update the accumulator BIP with benchmarks for SHA512/256 vs SHA256.
But could you link to the aforementioned justifications for the other parts of the Bitcoin protocol that use SHA512?
No part of the Bitcoin consensus protocol uses SHA512.
On Mon, Aug 18, 2025 at 04:06:51AM -0700, Calvin Kim wrote: kcalvinalvin left a comment (bitcoin/bips#1923) > You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol. Right now you just link to a paper from 2011. But that paper is out of date now that hardware support for SHA-256 has become common. Sure we can update the accumulator BIP with benchmarks for SHA512/256 vs SHA256. But could you link to the aforementioned justifications for the other parts of the Bitcoin protocol that use SHA512? No part of the Bitcoin consensus protocol uses SHA512.
Ok but you've stated in your previous comment "You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol". Would be very helpful to see what type of justifications the other protocols have made.
Second, I don't think it matters if SHA512 wasn't used in the Bitcoin consensus protocol. SHA512 is used in BIP32 and the argument that SHA512 is safe for generating private keys but not safe for Bitcoin consensus isn't sound.
I think our original justification (better performance with SHA512/256) mentioned in the BIP is sound. Happy to provide the benchmarks, they're being worked on at the moment.
SHA512 is safe for generating private keys
Lol, what did you say?
SHA512 is safe for generating private keys
Lol, what did you say?
Dude, go look up on chatgpt how SHA512/256 works. Length extension attacks that you mentioned DOES NOT work on it because the outputs are truncated. BIP32 uses HMAC-SHA512 which is just a keyed SHA512.
Why do I even have to deal with this guy. It's clear he doesn't know anything. His comments are worthless and this is wasting my time and energy.
This is the type of email he sends me after I block him. I'm sorry for posting unrelated comments here but imho he should be blocked from this repo.
61 | +hash, you must compute the SHA-512/256 hash of the following data: 62 | + 63 | +| Name | Type | Description | 64 | +| ----------------- | ------------------------ | ----------------------------------------- | 65 | +| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | 66 | +| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. |
For clarification, is the Utreexo_Tag_V1 really used twice in preimage to the hash?
My guess would be that this duplication is unintended.
| Name | Type | Description |
| ----------------- | ------------------------ | ----------------------------------------- |
| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. |
Oh no the duplication is intended.
Since we use SHA512/256 as the hash function, each chunk is 128 bytes. Since the version tag is only 64 bytes, we need two of them.
On Mon, Aug 18, 2025 at 04:06:51AM -0700, Calvin Kim wrote: kcalvinalvin left a comment (bitcoin/bips#1923) > You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol. Right now you just link to a paper from 2011. But that paper is out of date now that hardware support for SHA-256 has become common. Sure we can update the accumulator BIP with benchmarks for SHA512/256 vs SHA256. But could you link to the aforementioned justifications for the other parts of the Bitcoin protocol that use SHA512? No part of the Bitcoin consensus protocol uses SHA512.
Ok but you've stated in your previous comment "You need to justify why you're using SHA-512/256 rather than SHA-256, like the rest of the Bitcoin protocol". Would be very helpful to see what type of justifications the other protocols have made.
Second, I don't think it matters if SHA512 wasn't used in the Bitcoin consensus protocol. SHA512 is used in BIP32 and the argument that SHA512 is safe for generating private keys but not safe for Bitcoin consensus isn't sound.
I think our original justification (better performance with SHA512/256) mentioned in the BIP is sound. Happy to provide the benchmarks, they're being worked on at the moment.
The question is 1) why are we added one new dependency to consensus implementations, and 2) is this actually a performance increase, given that dedicated SHA256 hardware is becoming common?
Length-extension attacks are not relevant for this use-case as we are only committing to public data.
5 | +Authors: Tadge Dryja <rx@awsomnet.org> 6 | + Calvin Kim <bip@calvinkim.info> 7 | + Davidson Souza <bip@dlsouza.dev> 8 | +Comments-URI: TBD 9 | +Status: Draft 10 | +Type: Specification
Nit: BIP 2 is still active, so this should be "Standard Track" for the time being.
12 | +License: BSD-3-Clause 13 | +``` 14 | + 15 | +## Abstract 16 | + 17 | +This BIP describes the Utreexo accumulator and it's operations. It lays down how to update the
This BIP describes the Utreexo accumulator and its operations. It lays down how to update the
51 | + 52 | +The Utreexo accumulator is based on an append-only Merkle tree design introduced in [^1], 53 | +which provides logarithmic-sized inclusion proofs. Utreexo extends this design to support dynamic updates, 54 | +specifically enabling deletions from the set—a requirement for tracking UTXO spends in Bitcoin. 55 | +To accommodate this, Utreexo changes the storage requirement from the accumulator design in [^1] to $O(log_2(N))$, 56 | +where N is the number of elements ever added to the set, while still keeping proof sizes small and verification efficient.
In case this doesn’t get discussed later, it might be interesting to compare how O(log<sub>2</sub>(N)) for all transaction outputs ever created compare to the current UTXO set size.
Technically the current Utreexo design is O(log2(N)) of all txos since the forest doesn't shrink on a deletion. We just move the leaf up so it has the same affect as shrinking the forest.
171 | + 172 | +## Utility Functions 173 | + 174 | +The following utility functions are required for performing accumulator operations: 175 | + 176 | +**parent_hash(left, right):** Returns the hash of the concatenation of two child hashes (`left` and `right`).
Does this ambiguity regarding the depth of the leaf in the tree not introduce similar weaknesses as the original Merkle tree construction? Why would we float up leaf-hashes rather than create a tagged hash at each level?
Is this fully mitigated due to the number of leaves being known?
Does this ambiguity regarding the depth of the leaf in the tree not introduce similar weaknesses as the original Merkle tree construction?
Not quite sure which weakness you're referring to here. Is it CVE-2012-2459 (one from calculating the Bitcoin block header commitment)? Since we don't duplicate hashes, it's not vulnerable to that particular attack.
Why would we float up leaf-hashes rather than create a tagged hash at each level?
Since we float up the leaf hashes, we can save on the proofs being sent over for the sibling later on.
On a tree like so, proof for 01 is 00, 09, 13.
14
|---------------\
12 13
|-------\ |-------\
08 09 10 11
|---\ |---\ |---\ |---\
00 01 02 03 04 05 06 07
If we delete 00, then 01 moves up to 08. The proof for 01 is now 09 and 13. The proof got shorter.
14
|---------------\
12 13
|-------\ |-------\
01 09 10 11
|---\ |---\ |---\ |---\
02 03 04 05 06 07
That's a good point, and we can add a bit about this potential issue in the BIP.
Leaves can move up, and it's no longer leaves getting hashed with leaves, but leaf/internal node pairs happen often. An attack would be to grind through transactions to get two leaf hashes that together could look like a leaf data preimage for a rogue UTXO.
The reason this isn't a problem is that in all cases when a node is verifying a UTXO proof, the full UTXO data is known and a keyed hash is used (see "UTXO Hash Preimages" section of the validation BIP) to get from the UTXO data to the leaf. The first 128 bytes input to the hash function are the tags (the hash of "UtreexoV1"). Since this tag is only used for UTXO data, and not in internal accumulator hashes, this should prevent any internal hashes from being interpreted as UTXO data.
186 | + if right is None: return left 187 | + 188 | + return sha512_256(left + right) 189 | +``` 190 | + 191 | +**treerows(numleaves):** Returns the minimum number of bits required to represent `numleaves - 1`. This corresponds to the height of the largest tree in the forest. Returns `0` if `numleaves` is `0`.
The numleaves - 1 throws me off here. It’s not obvious to me, why the function would be defined that way rather than the "minimum number of bits required to represent numleaves"? Perhaps a bit more context would help?
Ah it's because we wanted treerows to return the index of the largest tree not the length.
For the below tree, numleaves = 4 but we want treerows to return 2 not 3.
row 2: 06
|-------\
row 1: 04 05
|---\ |---\
row 0: 00 01 02 03
If we just took the minimum number of bits to represent numleaves = 4, we'd get 3. So to account for this, we take the minimum number of bits needed to represent numleaves-1. This off-by-one happens when numleaves is a power of two.
@adiabat did talk about wanting to make treerows return the length and not the index a while back so last chance to speak up? :)
I've added the explanation in the bip as well.
I think I understand the calculation that you are doing, but what’s a bit unclear is the reasoning behind it. What’s the relationship between the thing you are calculating vs the input?
236 | +Implementation: 237 | + 238 | +```python 239 | +def parent(position: int, total_rows: int) -> int: 240 | + return (position >> 1) | (1 << total_rows) 241 | +```
I could have used a little more explanation why this returns the parent, but staring at it for a bit, it seems to me that a fully filled tree with 2<super>n</super> leaves would have 2<super>n</super>-1 inner nodes, meaning that all leaves start with a zero in the first position and all inner nodes starting with a one.
E.g. for four leaves, the leaves are 000, 001, 010, and 011, and the inner nodes would be 100, 101, 110.
For 000 and 001, shifting to the right gives 00 and setting the top bit makes the parent 100. For 010 and 011, it works out to be 101. For 100 and 101, it works out to 110.
Gotcha, cool.
549 | +While RSA accumulators and similar constructions offer significant advantages in proof size—often allowing a 550 | +single proof to cover an entire block's worth of UTXOs—the trade-offs in proof generation cost and latency are 551 | +substantial. In RSA-based designs, creating a proof for any given UTXO at arbitrary times can be computationally 552 | +intensive, especially as the number of UTXOs grows. 553 | + 554 | +Utreexo's design is driven by the need for Bridge Nodes: nodes that maintain backward compatibility with existing
New jargon is usually italicized on introduction, perhaps consider:
Utreexo's design is driven by the need for *bridge nodes*: nodes that maintain backward compatibility with existing
I had a look at most of the Accumulator Specification for the first helping. Looks very good already. I only reviewed the function definitions up to root_position, then skimmed the rest, before reading on from Rationale.
0 | @@ -0,0 +1,328 @@ 1 | +``` 2 | +BIP: TBD 3 | +Layer: Peer Services 4 | +Title: Utreexo - Validation Layer
The title feels a bit odd to me. It could be a bit more descriptive, I was thinking "Utreexo - Transaction and block validation" or smth?
5 | +Authors: Tadge Dryja <rx@awsomnet.org> 6 | + Calvin Kim <bip@calvinkim.info> 7 | + Davidson Souza <bip@dlsouza.dev> 8 | +Comments-URI: TBD 9 | +Status: Draft 10 | +Type: Specification
Nit: Until BIP 3 activates, this should be Standards Track.
15 | + 16 | +## Abstract 17 | + 18 | +This BIP defines the rules for validating blocks and transactions using the 19 | +Utreexo accumulator. It is important to note that this BIP does not define the 20 | +Utreexo accumulator itself, for that see BIP-????. This document is only concerned with
Maybe for the time being:
Utreexo accumulator itself, for that see [BIP Utreexo Accumulator](utreexo-accumulator-bip.md). This document is only concerned with
47 | +## Specification 48 | + 49 | +### Node Hashes 50 | + 51 | +During a node's normal operation, it will need to compute the leaf hash for UTXOs 52 | +being added or removed from the accumulator. The leaf hash is a 32 byte hash that
being added or removed from the accumulator. The leaf hash is a 32-byte hash that
55 | + 56 | +Unless otherwise specified, all fields are in little-endian format. 57 | + 58 | +#### UTXO Hash Preimages 59 | + 60 | +Individual UTXOs are represented as 32 byte hashes in the Utreexo accumulator. To obtain this
Individual UTXOs are represented as 32-byte hashes in the Utreexo accumulator. To obtain this
74 | + 75 | +Each field being defined as follows: 76 | + 77 | +##### Version tag 78 | + 79 | +We use tagged hashes for the hashes committed in the accumulator for versioning
Maybe link to the section introducing tagged hashes in BIP 340: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#user-content-Design
79 | +We use tagged hashes for the hashes committed in the accumulator for versioning 80 | +purposes. This is added so that if there are changes in the preimage of the 81 | +hash, the version tag helps to avoid misinterpretation. 82 | + 83 | +The Utreexo version tag is the SHA512 hash of the string `UtreexoV1`, which is represented as the vector 84 | +`[85 116 114 101 101 120 111 86 49]` and hex `0x5574726565786f5631`. (The resulting 64 byte output is
`[85 116 114 101 101 120 111 86 49]` and hex `0x5574726565786f5631`. (The resulting 64-byte output is
62 | + 63 | +| Name | Type | Description | 64 | +| ----------------- | ------------------------ | ----------------------------------------- | 65 | +| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | 66 | +| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | 67 | +| BlockHash | 32 byte array | The hash of the block in which this tx was confirmed. |
On all lines in this table, when the byte count is used as an adjective:
-32 byte array
+32-byte array
and
-4 bytes unsigned integer
+4-byte unsigned integer
65 | +| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | 66 | +| Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | 67 | +| BlockHash | 32 byte array | The hash of the block in which this tx was confirmed. | 68 | +| TXID | 32 byte array | The transaction's TXID | 69 | +| Vout | 4 bytes unsigned integer | The output index of this UTXO | 70 | +| Header code | 4 bytes unsigned integer | The block height and iscoinbase. This is a value obtained by left shifting the block height that confirmed this transaction, and then OR-ing it with 1, only if this transaction is a coinbase. |
| Header code | 4 bytes unsigned integer | The block height and iscoinbase. This is a value obtained by left shifting the block height that confirmed this transaction by one bit, and then OR-ing it with 1, only if this transaction is a coinbase. |
105 | +The output index of the UTXO in the transaction. 106 | + 107 | +##### Header code 108 | + 109 | +This field stores the block height and a boolean for marking that the UTXO is 110 | +part of a coinbase transaction. Mostly serves to save space as the coinbase
This field stores the block height and a boolean for marking that the UTXO was
created by a coinbase transaction. Mostly serves to save space as the coinbase
109 | +This field stores the block height and a boolean for marking that the UTXO is 110 | +part of a coinbase transaction. Mostly serves to save space as the coinbase 111 | +boolean can be stored in a single bit. 112 | + 113 | +This field is a value obtained by left shifting the block height that 114 | +confirmed this transaction, and then setting the least significant bit to 1 only
confirmed this transaction by one bit, and then setting the least significant bit to 1 only
125 | +The block height is needed as during transaction validation, it is used during 126 | +the check of BIP-0065 CLTV. In current nodes, the block height is stored locally 127 | +as a part of the UTXO set. Since Utreexo nodes get this data from peers, we need 128 | +to commit to the block height to avoid security vulnerabilities. 129 | + 130 | +The boolean for coinbase is needed as they may not be spent before having 100 confirmations.
The boolean for coinbase outputs is needed as they may not be spent before having 100 confirmations.
145 | +##### script pubkey 146 | + 147 | +This field is added to commit to the locking script of the UTXO. With current 148 | +nodes, this is stored in the UTXO set but since we receive this in the proof 149 | +from our peers, we need to commit to this value to avoid malicious peers that 150 | +may send over the wrong locking script.
Perhaps consider "output script" as "scriptPubKey" is just Bitcoin Core’s variable name for that field.
##### Output script size
As the output script ("scriptPubKey" in Bitcoin Core) is a variable length byte array, we prepend it with the
length.
##### Output Script
This field is added to commit to the output script of the UTXO. With current
nodes, this is stored in the UTXO set but since we receive this in the proof
from our peers, we need to commit to this value to avoid malicious peers that
may send over the wrong output script.
168 | +##### Provably unspendable transaction outputs 169 | + 170 | +There are outputs in the Bitcoin network that we can guarantee that they cannot 171 | +be spent without a hard-fork of the network. The following output types are not 172 | +added to the accumulator: 173 | +- Outputs that start with an OP_RETURN (0x6a)
- Outputs whose output script starts with an OP_RETURN (0x6a)
169 | + 170 | +There are outputs in the Bitcoin network that we can guarantee that they cannot 171 | +be spent without a hard-fork of the network. The following output types are not 172 | +added to the accumulator: 173 | +- Outputs that start with an OP_RETURN (0x6a) 174 | +- Outputs with a scriptPubkey larger than 10,000 bytes
- Outputs with an output script larger than 10,000 bytes
181 | +In Utreexo, nodes inspect blocks and identify which outputs are being created 182 | +and destroyed in the same block, and exclude them from the accumulator and proofs. 183 | + 184 | +There's no need to provide proofs for outputs which have been created in the same 185 | +block. Adding and then immediately removing the output from the accumulator would be 186 | +possible but doesn't serve any purpose - once outputs are spent their past existence
possible but doesn't serve any purpose - once outputs are spent, their past existence
194 | +The Utreexo accumulator lacks associative properties during addition and the 195 | +ordering of which UTXO hash gets added first is consensus critical. For 196 | +the modification of the accumulator the steps are as follows: 197 | + 198 | +1. Batch remove the UTXOs that were spent in the block based on the algorithm 199 | + defined in BIP-????. Deletions itself are order-independent.
For the time being, maybe just use [BIP Utreexo Accumulator](utreexo-accumulator-bip.md) to clarify whether you are referring to one or the other.
199 | + defined in BIP-????. Deletions itself are order-independent. 200 | +2. Batch add all non-excluded outputs in the order they're included in the 201 | + Bitcoin block. Additions are order-dependent. 202 | + 203 | +The removal and the addition of the hashes follow the algorithms defined in 204 | +BIP-????.
Ditto
208 | +The UTXO proof has 2 elements: the accumulator proof and the leaf data. The 209 | +leaf data provides the necessary UTXO data for block validation that would be 210 | +stored locally for non-Utreexo nodes. The accumulator proof proves that the 211 | +given UTXO hash preimages are committed in the accumulator. 212 | + 213 | +Accumulator proof is defined in BIP-????, and contains two elements:
Ditto
213 | +Accumulator proof is defined in BIP-????, and contains two elements: 214 | + 215 | +1. A vector of positions of the UTXO hashes in the accumulator. 216 | +2. A vector of hashes required to hash up to the roots. 217 | + 218 | +For (1), positions are in the order of the leaves that are being proved in
For (1), positions are in the order of the leaves that are being proven in
219 | +the accumulator. These are all the inputs in the natural blockchain order that 220 | +excludes the same block spends. 221 | + 222 | +The UTXO hash preimages follow the same ordering as (1) in the accumulator 223 | +proofs. Each of the positions in (1) refer to the UTXO hash preimage in the same 224 | +index.
For some reason I had thought that the accumulator proof was a Merkle branch, but now reading this, it makes me think that the proofs are built-up from the leaf preimages. Which of the two is correct, and could you perhaps check whether some more clarification should be added here to make it unambiguous? This might also just be me mixing up something as I’m trying to puzzle together everything that is going on.
For some reason I had thought that the accumulator proof was a Merkle branch, but now reading this, it makes me think that the proofs are built-up from the leaf preimages. Which of the two is correct, and could you perhaps check whether some more clarification should be added here to make it unambiguous?
You are right, there's the merkle branches themselves and the leaf preimages are an entirely separate data apart from that.
I'll read it over again and make clarifications where needed.
Yeah it's both. First the merkle branch is needed to verify that the UTXO exists at all, then the UTXO data / leaf preimage is needed to feed in to the normal script & transaction validation. We can make it clear that there's really 2 things stuck together here.
232 | + 233 | +For each block, the UTXO proof must be provided with the bitcoin block for 234 | +validation to be possible. Without the UTXO proof, it's not possible to 235 | +validate that the inputs being referenced exists in the UTXO set. 236 | + 237 | +The end result of the UTXO proof validation results us in the vector of UTXO
The end result of the UTXO proof validation results in the vector of UTXO
253 | +of this check affect the consensus validation for Utreexo nodes. 254 | + 255 | +### BIP-0030 and BIP-0034 consensus check 256 | + 257 | +Before `BIP-0030`, the Bitcoin consensus rules allowed for duplicate TXIDs. If two 258 | +transactions shared a same TXID, the transaction outputs of the preceding
transactions shared a same TXID, the transaction outputs of the succeeding
256 | + 257 | +Before `BIP-0030`, the Bitcoin consensus rules allowed for duplicate TXIDs. If two 258 | +transactions shared a same TXID, the transaction outputs of the preceding 259 | +transaction would overwrite the previously created UTXOs. It was assumed that 260 | +TXIDs were unique but it's trivially easy to create a transaction that share 261 | +the same `TXID` for coinbase transactions by re-using the same bitcoin address.
Nit: It’s not just that the TXID is the same, the entire transaction is the same.
259 | +transaction would overwrite the previously created UTXOs. It was assumed that 260 | +TXIDs were unique but it's trivially easy to create a transaction that share 261 | +the same `TXID` for coinbase transactions by re-using the same bitcoin address. 262 | + 263 | +`BIP-0030` check is a consensus check that enforces that newly created transactions 264 | +do not have outputs that overwrites an existing UTXO.
do not have outputs that overwrite an existing UTXO.
261 | +the same `TXID` for coinbase transactions by re-using the same bitcoin address. 262 | + 263 | +`BIP-0030` check is a consensus check that enforces that newly created transactions 264 | +do not have outputs that overwrites an existing UTXO. 265 | + 266 | +`BIP-0034` was a rule where the block height was included in the script signature
What was called originally "generator transaction" is now more familiarly referred to as a "coinbase transaction" after the "scriptSig" equivalent being called "coinbase field" in that context.
`BIP-0034` introduces a rule that requires the block height to be included in the coinbase field
262 | + 263 | +`BIP-0030` check is a consensus check that enforces that newly created transactions 264 | +do not have outputs that overwrites an existing UTXO. 265 | + 266 | +`BIP-0034` was a rule where the block height was included in the script signature 267 | +of the coinbase transaction. One of the reason for the change was to make
As far as I can tell, the rest of BIP 34 explains the activation mechanism of BIP 34, so I would claim that this is the main reason.
of the coinbase transaction. The main reason for the change was to make
266 | +`BIP-0034` was a rule where the block height was included in the script signature 267 | +of the coinbase transaction. One of the reason for the change was to make 268 | +coinbase transactions unique so that the expensive check of going through the 269 | +UTXO set wouldn't be needed. However, there were blocks in the past that had 270 | +random bytes that could be interpreted as block heights. The lowest block 271 | +heights are: 209,921, 490,897, and 1,983,702.
random bytes that could be interpreted as block heights. The lowest implicated block
heights are: 209,921, 490,897, and 1,983,702.
280 | +will remove the checkpoints[^1], as they are not needed anymore to prevent attacks 281 | +against nodes during Initial Block Download. This is effectively a hard-fork, 282 | +that will probably never actually happen, however. 283 | + 284 | +Block 1,983,702 is the first block that Utreexo nodes would be in danger of a 285 | +consensus failure due to the inability to perform the BIP-0030 checks. However,
consensus failure due to the inability to perform the BIP-0030 checks, if someone were to reuse coinbase transaction from block 164,384 . However,
286 | +this block will happen in roughly 21 years from now, and some mitigations have been 287 | +proposed [^2]. 288 | + 289 | +### Historical BIP-0030 violations 290 | + 291 | +There were two UTXOs that were overwritten due to this consensus rule are:
Not due to this rule, but rather before it was introduced:
There were two UTXOs that were overwritten by repeated transactions:
295 | +Since the leaf hashes that are committed to the Utreexo accumulator commit to 296 | +the block hash as well, all the leaf hashes are unique and the two historical 297 | +violations do not happen with how the UTXO set is represented with the Utreexo 298 | +accumulator. To be consensus compatible with clients that do have the historical 299 | +violations, the leaves representing these two UTXOs in the Utreexo accumulator 300 | +are hardcoded as unspendable.
If I’m understanding this right:
accumulator. To be consensus compatible with clients that retain only the second
occurrences of these outputs, the leaves representing the corresponding first UTXOs in the Utreexo accumulator
are hardcoded as unspendable.
This time I took a look at the "Validation Layer" BIP. Also looks very good already. I noticed that there is no Rationale section, and the title seemed a little less informative than it could be.
23 | +## Motivation 24 | + 25 | +Utreexo nodes require the inclusion proof to fully validate blocks and transactions. 26 | +Each block has a corresponding inclusion proof with it and this inclusion proof for blocks up to height 906,937 requires an additional 631.85GB, which is roughly 40GB less than the size of the block data. 27 | +Each transaction also has a corresponding inclusion proof with it and for normal transaction relay, the proof is roughly 3 times the size of the transaction. 28 | +It's still reasonable for a single node to download this extra data but little caching goes a long way in reducing the amount of data that one has to download.
little caching ↦ almost no caching a little caching ↦ some caching
I think you mean the latter:
It's still reasonable for a single node to download this extra data but a little caching goes a long way in reducing the amount of data that one has to download.
45 | +3. Archive nodes 46 | + 47 | +CSNs have the goal of minimizing data storage and download while performing block validation. 48 | +Archive and bridge nodes store more data and provide this data to CSNs. 49 | + 50 | +Bridge nodes are nodes that can add inclusion proofs to mempool transactions, support the same set of messages as CSNs, and should in fact be indistinguishable from CSNs on the network.
It’s not clear to me how "bridge nodes should in fact be indistinguishable from CSNs on the network". By whom are they indistinguishable. In what regard are they indistinguishable? Shouldn’t they, e.g., be frequently the first peer to notify about new transactions appearing in the mempool and blocks having been found as they act as the translation layer and therefore the initial source of data for the Utreexo-portion of the node network?
It’s not clear to me how "bridge nodes should in fact be indistinguishable from CSNs on the network". By whom are they indistinguishable. In what regard are they indistinguishable?
They're indistinguishable as we don't explicitly specify which nodes are bridges. The sentence was an attempt at clarifying a common misconception that a CSN must connect to bridge nodes.
Shouldn’t they, e.g., be frequently the first peer to notify about new transactions appearing in the mempool and blocks having been found as they act as the translation layer and therefore the initial source of data for the Utreexo-portion of the node network?
Yes this is true. They usually should be the first to notify utreexo peers about new txs and blocks
Maybe "indistinguishable" is too strong -- it would be great if nobody could tell, but if there are a small number of bridge nodes and a large number of CSNs it might be traceable.
The main thing is bridge nodes don't announce themselves as such; they just pass proofs and transactions around just like CSNs. If you're a CSN connected directly to a bridge node, you might see a lot of INVs and proofs originate from that node, and they might be a bridge, but they might just be a well connected CSN.
It's similar to trying to prevent people from tracing new transactions to originating nodes, though probably in one sense harder (bridge nodes keep being bridge nodes all the time vs only getting one shot with a wallet broadcasting) but also lower stakes (determining that a node is a bridge doesn't hurt privacy or network strength that much).
46 | + 47 | +CSNs have the goal of minimizing data storage and download while performing block validation. 48 | +Archive and bridge nodes store more data and provide this data to CSNs. 49 | + 50 | +Bridge nodes are nodes that can add inclusion proofs to mempool transactions, support the same set of messages as CSNs, and should in fact be indistinguishable from CSNs on the network. 51 | +Archive nodes are able to serve the blocks and the inclusion proofs. However, they are not able to generate the inclusion proofs as they do not keep the full UTXO set.
Does "Bridge node" refer to the aspect of whether the node has the UTXO set, and does "archive node" refer to having the full set of data? I.e., are these different dimensions? Would you run an "archive bridge node" if you want to offer all services?
Edit: Oh, never mind, you answer that right below.
55 | +The one exception to this flexibility is that archive nodes must provide both the blocks and the inclusion proofs. 56 | +While theoretically possible to split these two resources, the blocks are quite small relative to the block proofs, and it simplifies clients to be able to rely on being able to request both over the same connection. 57 | + 58 | +### Pre-P2P: Bridge Building 59 | + 60 | +When introducing Utreexo into an existing network, there are 2 thing needed before CSNs can operate.
When introducing Utreexo into an existing network, there are two things needed before CSNs can operate.
56 | +While theoretically possible to split these two resources, the blocks are quite small relative to the block proofs, and it simplifies clients to be able to rely on being able to request both over the same connection. 57 | + 58 | +### Pre-P2P: Bridge Building 59 | + 60 | +When introducing Utreexo into an existing network, there are 2 thing needed before CSNs can operate. 61 | +First, archive nodes need to build proofs for old blocks to serve during the initial-block download (IBD).
First, archive nodes need to build proofs for old blocks to serve during the initial block download (IBD).
66 | + 67 | +### Initial Block Download 68 | + 69 | + 70 | + 71 | +Current IBD is done by a headers-first block download, in which the node downloads all the Bitcoin block headers, verifies that they connect, and start downloading the actual block data for validation.
"Verifies that they connect" feels a bit overly reductive.
Conventionally, IBD is done by a headers-first block download, in which the node downloads all the Bitcoin block headers, verifies that they connect, and follows up by by downloading the block data for validation.
73 | + 74 | + 75 | +Utreexo nodes still perform the headers-first phase. 76 | +However, in addition to blocks, they also require the inclusion proof for UTXOs spent in that block. 77 | +Hence a Utreexo node will send a `getutreexoproof` message along with the `getdata` message for a given block. 78 | +This flow is the simplest change and allows a Utreexo node to validate and perform IBD but this method does require downloading about 2 times compared to the current nodes as the inclusion proof for a block is roughly the same size as the block itself.
This flow is the simplest change and allows a Utreexo node to validate and perform IBD but this method does require downloading about two times as much data as a conventional node due to the inclusion proof for a block being roughly the same size as the block itself.
84 | +With these TTL values, a node receiving the `TTL` message will be able to determine which output to cache with the Clairvoyant algorithm[^1] which allows the IBD-ing node to reduce the bandwidth required in syncing the node in the most efficient way possible. 85 | + 86 | +The node will have the block and the TTLs for the outputs of the given block which it can then use to cache parts of the inclusion proof and only request the needed parts of an inclusion proof for future blocks. 87 | + 88 | +We note that it is feasible for a node to receive incorrect TTL values from malicious nodes and this can negatively impact the bandwidth savings. 89 | +Nodes can mitigate this by not downloading TTL values too far into the future or by checking if the `TTL` message received was included in the accumulator hard-coded into the binary.
I don’t understand what you mean with "hard-coded in the binary".
Oh I should clarify this.
Since nothing is being committed to the TTL messages, a node can just lie about the values in the message. To prevent this, the node should either:
1: don't download too far into the future since the damage done will be greater. 2: rely on the pre-committed (aka "hard coded into the binary") ttl accumulator in the node software. The ttl accumulator has ttls for each of the blocks accumulated. With this accumulator, the node can check if the received ttl is valid or invalid by checking for its existence in the ttl accumulator.
86 | +The node will have the block and the TTLs for the outputs of the given block which it can then use to cache parts of the inclusion proof and only request the needed parts of an inclusion proof for future blocks. 87 | + 88 | +We note that it is feasible for a node to receive incorrect TTL values from malicious nodes and this can negatively impact the bandwidth savings. 89 | +Nodes can mitigate this by not downloading TTL values too far into the future or by checking if the `TTL` message received was included in the accumulator hard-coded into the binary. 90 | + 91 | +This TTL commitment scheme is described in detail [here](#Commitment scheme for TTL messages).
The TTL commitment scheme is described in detail in the section [Commitment scheme for TTL messages](#commitment-scheme-for-ttl-messages) below.
92 | + 93 | +### Transaction relay 94 | + 95 | + 96 | + 97 | +Current transaction relay is done by sending an inv message with the hash of the transaction and a type field that denotes that this hash represents a transaction.
Throughout this BIP: I don’t think "current" is a future-proof term to distinguish the established behavior of nodes from Utreexo nodes. Perhaps "conventional" or "non-Utreexo nodes" would be a better fit?
93 | +### Transaction relay 94 | + 95 | + 96 | + 97 | +Current transaction relay is done by sending an inv message with the hash of the transaction and a type field that denotes that this hash represents a transaction. 98 | +If the node receiving the inv does not have a tx matching that hash, it then requests for it using a getdata message.
If the node receiving the inv does not have a transaction matching that hash, the node then requests the transaction using a getdata message.
102 | +The transaction relay for Utreexo nodes doesn't add any extra round trips. 103 | +However, it does include extra inventory vectors in the inv message. 104 | + 105 | +We introduce a new inventory vector type called `utreexoproofhash`, which makes up the extra information that a Utreexo node will receive. 106 | + 107 | +A hash with the type `utreexoproofhash` represents 4 Utreexo merkle tree positions, each of them little endian serialized and taking up 8 bytes in the 32 byte hash.
A hash with the type `utreexoproofhash` represents four Utreexo merkle tree positions, each of them little-endian serialized and taking up 8 bytes in the 32-byte hash.
103 | +However, it does include extra inventory vectors in the inv message. 104 | + 105 | +We introduce a new inventory vector type called `utreexoproofhash`, which makes up the extra information that a Utreexo node will receive. 106 | + 107 | +A hash with the type `utreexoproofhash` represents 4 Utreexo merkle tree positions, each of them little endian serialized and taking up 8 bytes in the 32 byte hash. 108 | +When sending an inv message to a Utreexo node for a tx, we append `utreexoproofhash` inventory vectors to represent the merkle tree positions for each of the UTXOs being referenced in the inputs of the tx.
Please don’t use abbreviations like "tx" in the running text.
When sending an inv message to a Utreexo node for a transaction, we append `utreexoproofhash` inventory vectors to represent the merkle tree positions for each of the UTXOs being referenced in the inputs of the transaction.
When you write "send an inv message" do you actually mean "announce a new transaction" rather than literally a inv message being sent?
The use of inv message here seems confusing. It’s not clear to me whether it is meant literal or as a stand in for "transaction announcement". First I even thought you were describing the message that transfers the entire transaction because you already were sending the utreexoproofhash along. If this is actually describing how Utreexo nodes announce transactions to each other, instead of saying "to send an inv message", it could better be introduces e.g., as
"Where conventional nodes us a
invmessage to announce a new transaction, Utreexo nodes use theinvvectmessage to announce new transactions to Utreexo peers."
It would perhaps also help if you explain why the utreexoproofhash would need to be sent with announcement of the transaction—I would have expected them to only be necessary when the transaction data is sent.
Either way, this section is confusing to me.
104 | + 105 | +We introduce a new inventory vector type called `utreexoproofhash`, which makes up the extra information that a Utreexo node will receive. 106 | + 107 | +A hash with the type `utreexoproofhash` represents 4 Utreexo merkle tree positions, each of them little endian serialized and taking up 8 bytes in the 32 byte hash. 108 | +When sending an inv message to a Utreexo node for a tx, we append `utreexoproofhash` inventory vectors to represent the merkle tree positions for each of the UTXOs being referenced in the inputs of the tx. 109 | +The Utreexo merkle tree positions are explained in detail in the bip "Utreexo Accumulator Specification".
The Utreexo merkle tree positions are explained in detail in "BIP Utreexo Accumulator Specification".
100 | + 101 | + 102 | +The transaction relay for Utreexo nodes doesn't add any extra round trips. 103 | +However, it does include extra inventory vectors in the inv message. 104 | + 105 | +We introduce a new inventory vector type called `utreexoproofhash`, which makes up the extra information that a Utreexo node will receive.
This section feels ambiguous to me.
With the graphic labeling the first box that contains "type:transaction, hash: tx hash (a)" as invvect, I am now wondering whether Utreexo nodes use the inv message to announce messages to each other extended by invvect data, or whether they send invvect messages instead of inv messages.
110 | +Since the hash in an inventory vector is always 32 bytes, any unused space will be padded with the max uint64 value of 18446744073709551615. 111 | + 112 | +With these merkle tree positions for the UTXOs referenced in the inputs, we can calculate the needed positions of the merkle hashes to them. 113 | +These positions are then sent over in the `getdata` message as an another inventory vector. 114 | + 115 | +
Scrolling up and down through this document, it’s sometimes difficult to tell whether a paragraph belongs to the image before or after the paragraph. Since Markdown does not allow captions on images, it could for example help if either the images included the caption, or if the text were structured in some way that makes it clearer.
126 | + 127 | +### Block Propagation 128 | + 129 | + 130 | + 131 | +Legacy block propagation without Compact Blocks comprises of three steps:
Consistency: Previously you were referring to non-Utreexo nodes as "current nodes", now it’s "legacy". Please use one term to refer to the same concept across the entire document.
197 | +#### Reconstructable Script 198 | + 199 | +For some script types (e.g. `ScriptHash`, `PubkeyHash`, `WitnessScriptHash`, `WitnessPubkeyHash`) the actual locking condition is not in the scriptPubkey, but a hash of it. 200 | +The script which is evaluated is provided as an element of the scriptSig or witness data. 201 | + 202 | +Therefore, we can safely just omit the locking script hash from the UTXO data and reconstruct it from the witness or scriptSig.
Therefore, we can safely omit the locking script hash from the UTXO data and reconstruct it from the witness or scriptSig.
237 | + 238 | +| Field | Type | Description | 239 | +|--------------|---------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| 240 | +| block height | uint32 | The time-to-live value of a leaf in the Utreexo merkle forest. The value is determined by the amount of leaves that were added to the accumulator since its creation | 241 | +| length | varint | The length of the TTLs | 242 | +| TTLs | vector of TTL infos | The TTL Info for the UTXOs that are added to the Utreexo merkle forest in blockchain ordering. See [Utreexo - Validation Layer](./utreexo-validation-bip.md#Excluded UTXOs from the accumulator) for the UTXOs that are not added to the Utreexo merkle forest |
| TTLs | vector of TTL infos | The TTL Info for the UTXOs that are added to the Utreexo merkle forest in blockchain ordering. See [Utreexo - Validation Layer](./utreexo-validation-bip.md#excluded-utxos-from-the-accumulator) for the UTXOs that are not added to the Utreexo merkle forest |
282 | + 283 | +The bitmaps here are formatted as big-endian and padded to the nearest byte, with 1 meaning a request for the proof hash or the leaf data, and 0 meaning omit the proof hash or the leaf data. 284 | + 285 | +Since there's one corresponding leaf data per target location, it's trivial to generate a bitmap for the leafdatas. 286 | + 287 | +Using the [proof_positions](./utreexo-accumulator-bip.md#Utility Functions) function, it's possible to generate the positions of the needed proof hashes for a given set of targets.
Using the [proof_positions](./utreexo-accumulator-bip.md#utility-functions) function, it's possible to generate the positions of the needed proof hashes for a given set of targets.
I read the whole P2P BIP, although I went over the new messages section a bit more quickly. There are some sections that felt a bit confusing to me, perhaps you could try to take a look at whether you can clarify those for the less initiated. Overall, this seems close to complete, although I noticed that it is missing a Rationale section.
After discussion amongst the editors, we've assigned 181-183 for these 3 BIP drafts. @murchandamus suggested 181 Accumulator / 182 Validation / 183 P2P (I agree) while leaving it up to you.
Whenever you get around to it, please add the numbers to the Preambles, set the "Created" header to 2025-08-29 (it holds the date a BIP got numbered), and add the table entries to the README.mediawiki.
After discussion amongst the editors, we've assigned 181-183 for these 3 BIP drafts.
@murchandamus suggested 181 Accumulator / 182 Validation / 183 P2P (I agree) while leaving it up to you.
Whenever you get around to it, please add the numbers to the Preambles, set the "Created" header to 2025-08-29 (it holds the date a BIP got numbered), and add the table entries to the README.mediawiki.
Currently going through all the reviews and writing up the rationale for validation and p2p. Will address these as well.
181 | +### New data structures 182 | + 183 | +#### Compact leaf data 184 | + 185 | +For a CSN to learn the data associated with a UTXO, it must ask for a peer that has it. 186 | +To authenticate this data, it is committed into the accumulator, and therefore cannot be changed by peer.
To authenticate this data, it is committed into the accumulator, and therefore cannot be changed by the peer.
13 | +Requires: <BIP-???? (Utreexo Accumulator Specification), BIP-???? (Utreexo - Validation Layer)> 14 | +``` 15 | + 16 | +## Abstract 17 | + 18 | +Utreexo creates a compact representation of the UTXO set that only takes a couple of kilobytes.
At one extreme of this gradient, nodes minimize storage and memory requirements, keeping only the roots of the hash trees, which never exceed a kilobyte.
The Utreexo paper mentions that the upper limit of the accumulator size is a single KB. What changed?
It's essentially still a kilobyte but since we can support leaves up to the maximum of uint64, we can have 64 roots which is 64*32 = 2048. So 2KB max.
All of the review comments are addressed and the rationale for BIPs 182 and 183 were added.
BIP-0183 was also edited in the following ways:
1: Images updated with caption 2: Images now updated with transparent backgrounds and changed the colors so they can be read in dark mod 3: Changed the layout of the images and the paragraphs to be more legible.
206 | +#### Format of the UTXO proof 207 | + 208 | +The UTXO proof has 2 elements: the accumulator proof and the leaf data. The 209 | +leaf data provides the necessary UTXO data for block validation that would be 210 | +stored locally for non-Utreexo nodes. Non-Utreexo nodes store this data (under "chainstate/" for Bitcoin Core) 211 | +but since utreexo nodes don't this data, it must be provided.
Missing a word.
but since utreexo nodes don't <missing word> this data, it must be provided.
but since Utreexo nodes don't this data, it must be provided.
316 | + 317 | +## Rationale 318 | + 319 | +**Why use the Utreexo accumulator to keep track of UTXOs instead of a key-value database like leveldb?** 320 | + 321 | +There's two main advantages to using the Utreexo accumulator instead of a key-value database like leveldb:
There are two main advantages to using the Utreexo accumulator instead of a key-value database like leveldb:
319 | +**Why use the Utreexo accumulator to keep track of UTXOs instead of a key-value database like leveldb?** 320 | + 321 | +There's two main advantages to using the Utreexo accumulator instead of a key-value database like leveldb: 322 | + 323 | + 1. Puts a cap on the UTXO set growth. 324 | + 3. Performance gains with the elimination of random reads/writes.
Renders right of course, but still:
2. Performance gains with the elimination of random reads/writes.
330 | + 331 | +The UTXO set is currently around 10GB in 2025 and with pruning that's all it takes to maintain a full node. 332 | +However, as the UTXO set grows, the disk storage requirement will grow along with it and increase the barrier to running a full node. 333 | + 334 | +Currently, the UTXO set size is $O(log(N))$ where $N$ is the number of UTXOs. 335 | +By utilizing the Utreexo accumulator, we're able to cap the UTXO set growth at $O(log_2(N))$.