BIP 181, 182, 183: BIPs for Utreexo #1923
Conversation
kcalvinalvin
force-pushed
the
2025-08-10-utreexo-bips
branch
2 times, most recently
from
9b3eafb to
a94f643
Compare
jonatack
left a comment
jonatack
left a comment
There was a problem hiding this comment.
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.
kcalvinalvin
force-pushed
the
2025-08-10-utreexo-bips
branch
2 times, most recently
from
cb2993c to
d1d0342
Compare
|
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: 1. Security Advantages
2. Comparative Analysis: SHA-256 vs SHAKE256
3. Functional ExampleInput: SHAKE256 (512-bit output): SHAKE256 (256-bit output): 4. Implementation Benefits
5. Technical ReferenceFor detailed cryptographic differences: |
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? |
SHAKE256 is not used in Bitcoin and introduces a new hash which increases the trust-assumption. We do not want to do this. |
This comment was marked as off-topic.
This comment was marked as off-topic.
|
Some friendly moderation to keep the discussion focused on technical review -- thanks. |
SHA256 and SHA512 are quantum resistent.
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.
|
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. |
This comment was marked as abuse.
This comment was marked as abuse.
This comment was marked as off-topic.
This comment was marked as off-topic.
This comment was marked as off-topic.
This comment was marked as off-topic.
utreexo-validation-bip.md
Outdated
| | Name | Type | Description | | ||
| | ----------------- | ------------------------ | ----------------------------------------- | | ||
| | Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | | ||
| | Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | |
There was a problem hiding this comment.
For clarification, is the Utreexo_Tag_V1 really used twice in preimage to the hash?
There was a problem hiding this comment.
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. | | |
| | Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | | |
| | Name | Type | Description | | |
| | ----------------- | ------------------------ | ----------------------------------------- | | |
| | Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | |
There was a problem hiding this comment.
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.
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. |
kcalvinalvin
force-pushed
the
2025-08-10-utreexo-bips
branch
from
d67f429 to
253c739
Compare
kcalvinalvin
force-pushed
the
2025-08-10-utreexo-bips
branch
from
253c739 to
091afe1
Compare
kcalvinalvin
force-pushed
the
2025-08-10-utreexo-bips
branch
from
091afe1 to
260f2c9
Compare
kcalvinalvin
force-pushed
the
2025-08-10-utreexo-bips
branch
from
260f2c9 to
bd1e242
Compare
kcalvinalvin
changed the title
kcalvinalvin
left a comment
kcalvinalvin
left a comment
There was a problem hiding this comment.
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.
| To accommodate this, Utreexo changes the storage requirement from the accumulator design in [^1] to $O(log_2(N))$, | ||
| where N is the number of elements ever added to the set, while still keeping proof sizes small and verification efficient. |
There was a problem hiding this comment.
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.
utreexo-validation-bip.md
Outdated
| | Name | Type | Description | | ||
| | ----------------- | ------------------------ | ----------------------------------------- | | ||
| | Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | | ||
| | Utreexo_Tag_V1 | 64 byte array | The version tag to be prepended to the leafhash. | |
There was a problem hiding this comment.
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.
|
|
||
| The following utility functions are required for performing accumulator operations: | ||
|
|
||
| **parent_hash(left, right):** Returns the hash of the concatenation of two child hashes (`left` and `right`). |
There was a problem hiding this comment.
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
| return sha512_256(left + right) | ||
| ``` | ||
|
|
||
| **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`. |
There was a problem hiding this comment.
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.
| proofs. Each of the positions in (1) refer to the UTXO hash preimage in the same | ||
| index. |
There was a problem hiding this comment.
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.
| CSNs have the goal of minimizing data storage and download while performing block validation. | ||
| Archive and bridge nodes store more data and provide this data to CSNs. | ||
|
|
||
| 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. |
There was a problem hiding this comment.
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
utreexo-p2p-bip.md
Outdated
| 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. | ||
|
|
||
| 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. | ||
| 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. |
There was a problem hiding this comment.
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.
|
|
||
| ## Abstract | ||
|
|
||
| Utreexo creates a compact representation of the UTXO set that only takes a couple of kilobytes. |
There was a problem hiding this comment.
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.
| The UTXO proof has 2 elements: the accumulator proof and the leaf data. The | ||
| leaf data provides the necessary UTXO data for block validation that would be | ||
| stored locally for non-Utreexo nodes. Non-Utreexo nodes store this data (under "chainstate/" for Bitcoin Core) | ||
| but since utreexo nodes don't this data, it must be provided. |
There was a problem hiding this comment.
Missing a word.
| but since utreexo nodes don't this data, it must be provided. | |
| but since utreexo nodes don't <missing word> this data, it must be provided. |
|
|
||
| **Why use the Utreexo accumulator to keep track of UTXOs instead of a key-value database like leveldb?** | ||
|
|
||
| There's two main advantages to using the Utreexo accumulator instead of a key-value database like leveldb: |
There was a problem hiding this comment.
| 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: |
| There's two main advantages to using the Utreexo accumulator instead of a key-value database like leveldb: | ||
|
|
||
| 1. Puts a cap on the UTXO set growth. | ||
| 3. Performance gains with the elimination of random reads/writes. |
There was a problem hiding this comment.
Renders right of course, but still:
| 3. Performance gains with the elimination of random reads/writes. | |
| 2. Performance gains with the elimination of random reads/writes. |
| Currently, the UTXO set size is $O(log(N))$ where $N$ is the number of UTXOs. | ||
| By utilizing the Utreexo accumulator, we're able to cap the UTXO set growth at $O(log_2(N))$. |
There was a problem hiding this comment.
Given that you don’t store the UTXO set, but an accumulator that commits to the UTXO set, perhaps these two sentences should be amended?
|
It would perhaps be good if one or two other people gave it also a read, but either way, it seems pretty complete to me. What’s the status on your end? Do you still have planned work, or are waiting for people to finish reviews? |
vostrnad
left a comment
vostrnad
left a comment
There was a problem hiding this comment.
It would perhaps be good if one or two other people gave it also a read
Here's my read. I've suggested mainly formatting and capitalization changes, but at least two suggestions are quite important: the distinction between "varint" and "compact size", and the broken cross-BIP links.
| The Utreexo accumulator is based on an append-only Merkle tree design introduced in [^1], | ||
| which provides logarithmic-sized inclusion proofs. Utreexo extends this design to support dynamic updates, | ||
| specifically enabling deletions from the set—a requirement for tracking UTXO spends in Bitcoin. | ||
| To accommodate this, Utreexo changes the storage requirement from the accumulator design in [^1] to $O(log_2(N))$, |
There was a problem hiding this comment.
Specifying the logarithm base is redundant in big O notation, as changing the base is equivalent to multiplying by a constant factor.
| To accommodate this, Utreexo changes the storage requirement from the accumulator design in [^1] to $O(log_2(N))$, | |
| To accommodate this, Utreexo changes the storage requirement from the accumulator design in [^1] to $O(log(N))$, |
| a 16-element tree ($2^4$), a 4-element tree ($2^2$), and a 1-element tree ($2^0$), with gaps at the 8-element ($2^3$) | ||
| and 2-element ($2^1$) positions. | ||
|
|
||
| Each of the hashes in the forest can be referred by an integer label. This labeling is a convention we find easiest |
There was a problem hiding this comment.
| Each of the hashes in the forest can be referred by an integer label. This labeling is a convention we find easiest | |
| Each of the hashes in the forest can be referred to by an integer label. This labeling is a convention we find easiest |
|
|
||
| **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 reason for taking the minimum number of bits required for `numleaves-1` and not `numleaves` is because when `numleaves` is a power of two, we'd get an off-by-one error. |
There was a problem hiding this comment.
It would be nice to have consistent spacing around the minus sign, there's both numleaves - 1 and numleaves-1. Same goes for the equals sign below.
| The calculate roots algorithm is defined as `CalculateRoots(numleaves, []hash, proof) -> calculated_roots`: | ||
|
|
||
| - Check if length of `proof.targets` is equal to the length of `[]hash`. Return early if they're not equal. | ||
| - map `proof.targets` to their hash. |
There was a problem hiding this comment.
| - map `proof.targets` to their hash. | |
| - Map `proof.targets` to their hash. |
| - Map parent hash to the parent position. | ||
| - Return calculated_roots | ||
|
|
||
| The algorithm implemented in python: |
There was a problem hiding this comment.
| The algorithm implemented in python: | |
| The algorithm implemented in Python: |
| | length of the proof hashes | varint | The length of the proof hashes | | ||
| | proof hashes | vector of 32 byte hashes | The vector of the requested Utreexo summaries | | ||
| | length of the leafdatas | varint | The length of the leafdatas | | ||
| | leafdatas | vector of compact leafdatas | The preimage of the leafdatas referenced in the bitcoin transaction. MUST be in the order of the referenced inputs. Unconfirmed inputs do not have a corresponding leaf data. See compact leaf data for details | |
There was a problem hiding this comment.
| | leafdatas | vector of compact leafdatas | The preimage of the leafdatas referenced in the bitcoin transaction. MUST be in the order of the referenced inputs. Unconfirmed inputs do not have a corresponding leaf data. See compact leaf data for details | | |
| | leafdatas | vector of compact leafdatas | The preimage of the leafdatas referenced in the Bitcoin transaction. MUST be in the order of the referenced inputs. Unconfirmed inputs do not have a corresponding leaf data. See compact leaf data for details | |
|
|
||
| #### MSG_UTREEXO_ROOT | ||
|
|
||
| `MSG_UTREEXO_ROOT` is the utreexo accumulator state at a given height with a proof to a utreexo accumulator of the utreexo roots. |
There was a problem hiding this comment.
| `MSG_UTREEXO_ROOT` is the utreexo accumulator state at a given height with a proof to a utreexo accumulator of the utreexo roots. | |
| `MSG_UTREEXO_ROOT` is the Utreexo accumulator state at a given height with a proof to a Utreexo accumulator of the Utreexo roots. |
There are also several instances of lowercase "utreexo" in the table below.
| For example, a computer could divide the task of validating 800,000 blocks into 100 tasks of 8,000 blocks each: blocks 1 through 800, 800 through 1600, 1600 through 2400, and so on. | ||
|
|
||
| In order start the 1600 through 2400 IBD task, however, the node should know what the state of the utxo set is at block 1600, so that it can validate and modify the accumulator. |
There was a problem hiding this comment.
| For example, a computer could divide the task of validating 800,000 blocks into 100 tasks of 8,000 blocks each: blocks 1 through 800, 800 through 1600, 1600 through 2400, and so on. | |
| In order start the 1600 through 2400 IBD task, however, the node should know what the state of the utxo set is at block 1600, so that it can validate and modify the accumulator. | |
| For example, a computer could divide the task of validating 800,000 blocks into 100 tasks of 8,000 blocks each: blocks 1 through 800, 801 through 1600, 1601 through 2400, and so on. | |
| In order start the 1601 through 2400 IBD task, however, the node should know what the state of the UTXO set is at block 1600, so that it can validate and modify the accumulator. |
|
|
||
| These hints are statements of fact that are hard-coded into the program itself, and if they are false all bets are off about the program. | ||
|
|
||
| Archive nodes create a forest of Linkup hints, so that they can prove, with respect to the Linkup forest roots in a node performing IBD, what their binary has claimed the utxo accumulator state to be at any block height. |
There was a problem hiding this comment.
| Archive nodes create a forest of Linkup hints, so that they can prove, with respect to the Linkup forest roots in a node performing IBD, what their binary has claimed the utxo accumulator state to be at any block height. | |
| Archive nodes create a forest of Linkup hints, so that they can prove, with respect to the Linkup forest roots in a node performing IBD, what their binary has claimed the UTXO accumulator state to be at any block height. |
|
|
||
| #### MSG_GET_UTREEXO_ROOT | ||
|
|
||
| `MSG_GET_UTREEXO_ROOT` is used to request a utreexo accumulator state at a given height. |
There was a problem hiding this comment.
| `MSG_GET_UTREEXO_ROOT` is used to request a utreexo accumulator state at a given height. | |
| `MSG_GET_UTREEXO_ROOT` is used to request a Utreexo accumulator state at a given height. |
|
Some test vectors are in order as well. |
|
|
||
|  | ||
|
|
||
| It's possible to have an inv message with multiple txs as well. |
There was a problem hiding this comment.
| It's possible to have an inv message with multiple txs as well. | |
| It's possible to have an `inv` message with multiple transactions as well. |
|
|
||
| ### Block Propagation | ||
|
|
||
| Legacy block propagation without Compact Blocks comprises of three steps: |
There was a problem hiding this comment.
| Legacy block propagation without Compact Blocks comprises of three steps: | |
| Legacy block propagation without Compact Blocks is comprised of three steps: |
| 1. Node A sends an inv message or a block header to Node B. | ||
| 2. Node B makes a getdata request for the block. |
There was a problem hiding this comment.
| 1. Node A sends an inv message or a block header to Node B. | |
| 2. Node B makes a getdata request for the block. | |
| 1. Node A sends an `inv` message or a block header to Node B. | |
| 2. Node B makes a `getdata` request for the block. |
| 2. Node B makes a getdata request for the block. | ||
| 3. Node A sends the block data to Node B. | ||
|
|
||
| Below image illustrates how a non-Utreexo node would relay blocks without using Compact Blocks. |
There was a problem hiding this comment.
| Below image illustrates how a non-Utreexo node would relay blocks without using Compact Blocks. | |
| The image below illustrates how a non-Utreexo node would relay blocks without using Compact Blocks. |
| 1. Node A sends an inv message or a block header to Node B. | ||
| 2. Node B makes a getdata request for the block. | ||
| 3. Node B makes a getutreexoproof request for the block. |
There was a problem hiding this comment.
| 1. Node A sends an inv message or a block header to Node B. | |
| 2. Node B makes a getdata request for the block. | |
| 3. Node B makes a getutreexoproof request for the block. | |
| 1. Node A sends an `inv` message or a block header to Node B. | |
| 2. Node B makes a `getdata` request for the block. | |
| 3. Node B makes a `getutreexoproof` request for the block. |
|
|
||
| ### Commitment scheme for TTL messages | ||
|
|
||
| We choose an arbitrary height `X` and go through each of `TTL info` in all the the `Utreexo TTL` values up until that height. |
There was a problem hiding this comment.
| We choose an arbitrary height `X` and go through each of `TTL info` in all the the `Utreexo TTL` values up until that height. | |
| We choose an arbitrary height `X` and go through each of `TTL Info`s in all of the `Utreexo TTL` values up until that height. |
|
|
||
| We choose an arbitrary height `X` and go through each of `TTL info` in all the the `Utreexo TTL` values up until that height. | ||
|
|
||
| If the TTL in the `TTL info` is greater than the [numleaves](bip-0181.md#Definitions) value of the Utreexo accumulator at the chosen height `X`, we reset the `death position` and the `TTL` values to their default of 0. |
There was a problem hiding this comment.
| If the TTL in the `TTL info` is greater than the [numleaves](bip-0181.md#Definitions) value of the Utreexo accumulator at the chosen height `X`, we reset the `death position` and the `TTL` values to their default of 0. | |
| If the TTL in the `TTL Info` is greater than the [numleaves](bip-0181.md#Definitions) value of the Utreexo accumulator at the chosen height `X`, we reset the `death position` and the `TTL` values to their default of 0. |
|
|
||
| **Why is there a separate NODE_UTREEXO_ARCHIVE service bit from the NODE_UTREEXO service bit?** | ||
|
|
||
| For archive nodes, we wanted the ability for a node to keep just the historical Utreexo proofs since the historical blocks can be served by any archival nodes. |
There was a problem hiding this comment.
| For archive nodes, we wanted the ability for a node to keep just the historical Utreexo proofs since the historical blocks can be served by any archival nodes. | |
| For archival nodes, we wanted the ability for a node to keep just the historical Utreexo proofs since the historical blocks can be served by any archival node. |
|
|
||
| We decided to communicate the positions in the Utreexo merkle forest by inventory vectors instead of a separate message to avoid an extra round trip during the transaction propagation. | ||
|
|
||
| As mentioned above in [Transaction Relay](#transaction-relay), non-Utreexo nodes propagate a transaction in these 3 steps: |
There was a problem hiding this comment.
| As mentioned above in [Transaction Relay](#transaction-relay), non-Utreexo nodes propagate a transaction in these 3 steps: | |
| As mentioned above in [Transaction Relay](#transaction-relay), non-Utreexo nodes propagate a transaction in 3 steps: |
| 2. Send a message to get the positions in the Utreexo merkle forest for the transaction. | ||
| 3. Receive the positions in the Utreexo merkle forest. |
There was a problem hiding this comment.
| 2. Send a message to get the positions in the Utreexo merkle forest for the transaction. | |
| 3. Receive the positions in the Utreexo merkle forest. | |
| 2. Send a message to get the positions in the Utreexo Merkle forest for the transaction. | |
| 3. Receive the positions in the Utreexo Merkle forest. |
| |----------------------------|-------------------------|------------------------------------------------------------------------------------------------------------------| | ||
| | blockhash | 32 byte vector | The hash of the block that the requested utreexo root message is for | | ||
|
|
||
| ### New Inventory Types |
There was a problem hiding this comment.
For all inventory types: be explicit about what needs to be provided and in what format (eg: blockhash, leaf positions, etc..).
| of the UTXO set. Since it can grow indefinitely, bounded only by block size, it represents a | ||
| long-term scalability concern. | ||
|
|
||
| Utreexo is a dynamic accumulator that enables the UTXO set to be represented in just a few kilobytes, |
There was a problem hiding this comment.
The defined accumulator in BIP 181 is positive because it supports membership proofs.
| Utreexo is a dynamic accumulator that enables the UTXO set to be represented in just a few kilobytes, | |
| Utreexo is a dynamic positive accumulator that enables the UTXO set to be represented in just a few kilobytes |
| The Utreexo accumulator is based on an append-only Merkle tree design introduced in [^1], | ||
| which provides logarithmic-sized inclusion proofs. Utreexo extends this design to support dynamic updates, | ||
| specifically enabling deletions from the set—a requirement for tracking UTXO spends in Bitcoin. |
There was a problem hiding this comment.
Parsing through the linked paper it claimed that the accumulator defined there is sound and strong.
With the extension here to make that accumulator dynamic, I suppose it is still correct, sound and strong?
Perhaps link to some resource on where that was explicitly studied
This point should also be added in the rationale along with the benchmarks when available |
murchandamus
added
the
PR Author action required
murchandamus
left a comment
murchandamus
left a comment
There was a problem hiding this comment.
It looks like there is still work in progress here. Please let me know when the review feedback has been resolved.
|
@kcalvinalvin there doesn't seem to be any response since late August -- do you plan to address the review and update here? |
Yes. There have been multiple protocol changes to BIP183 since then and I've been busy with the implementations for those changes. I'll get to the reviews and update the BIP. |
| `MSG_UTREEXO_PROOF` is all the data required for a CSN or archive node using the Utreexo accumulators to validate a Bitcoin block. | ||
|
|
||
| Its `cmdString` for P2PV1 is `uproof`. | ||
| Its [BIP324 P2PV2](https://github.com/bitcoin/bips/blob/master/bip-0324.mediawiki#user-content-v2_Bitcoin_P2P_message_structure) message type is `29`. |
There was a problem hiding this comment.
I think these values should be reserved in bip 324 before being added to other bips, to help avoid conflicts. (At worst, perhaps bip-324 could be updated in this PR)
There was a problem hiding this comment.
That's a good point! I was also told ages ago that we should make a PR to Core reserving the service bits we are using. @kcalvinalvin I think we should also do that?
| To save that bandwidth, we only send a Compact Leaf Data, that contains all missing information for the receiving peer to reconstruct the full leaf data. | ||
| A compact leaf data is defined as: | ||
|
|
||
| | Field | type | Description | |
There was a problem hiding this comment.
The leaf data is quite similar to CTxUndo in Bitcoin Core (de-serialized as a Coin) . I suggest this data be sent as a separate message, as non-Utreexo clients could also make use of this data, and verify its integrity to varying degrees:
- The SwiftSync protocol requires this data to perform full validation and enable parallel block downloads. The integrity of the data is verified at a pre-determined block height. A client cannot be mislead into accepting an invalid state.
BIP-157 clients may audit the construction of a compact block filter when two peers disagree on the hash of a filter for a particular block. This assumes the client is not eclipsed.I realized after the fact this is not accurate. One could change the block undo data for trivially spendable scripts and still produce a valid block and undo data combination.- BIP-157 clients do not have a way to reasonably estimate fee rates without a third party oracle. This data would allow for block-level fee rate analysis by light clients, given the client audits the undo data indeed corresponds to the block filter they have received.
- There is no protocol-native way for clients to scan for silent payments. This would allow a "light" client to download both the block undo data and compact block filter to check for potential payments by computing partial secrets locally.
If the current serialization format from Bitcoin Core is used, nodes serving this data can simply read the bytes from disk and send them directly over the wire without a de-serialization step. The trade-off here is of course the TTLs. To compensate, along with the length of the message, a header section may be included that specifies a height filter for coins that are assumed to already be in the client's cache. So a client requests "I would like all coins spent in this block, but I have the coins that were created in the last N blocks already," however this would required interpreting the undo-data from disk.
When I checked in October, undo data was approximately 90GB on disk. Is this even significant compared to the proofs?
13 participants
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