Page MenuHomePhabricator

[chronik] Add a struct to compute a block merkle tree
ClosedPublic

Authored by PiRK on Aug 1 2024, 16:09.

Details

Reviewers
tobias_ruck
Group Reviewers
Restricted Project
Commits
rABC2e8e8b9f174b: [chronik] Add a struct to compute a block merkle tree
Summary

Block merkle trees are used by Electrum ABC and fulcrum for computing checkpoint data and the data needed to verify that an earlier block is part of the same chain as the checkpointed block.

The merkle root is computed the same way as the merkle root for transactions in a block, except that we use the ordered block hashes in the blockchain instead of the ordered transaction hashes in a block.
As a result, it is possible to reuse intermediate hashes from the merkle tree for a block to compute the merkle tree for other blocks, which improves the performance at the cost of some reasonable amount of memory (approximately 60 MB for a 1,000,000 blocks long chain).

This checkpoint data will optionally be returned by the block-header and block-headers endpoints. See:

Test Plan

ninja check-crates

Event Timeline

Tail of the build log:

    Checking chronik-plugin-impl v0.1.0 (/work/chronik/chronik-plugin-impl)
    Checking rocksdb v0.21.0
    Checking chronik-db v0.1.0 (/work/chronik/chronik-db)
    Checking chronik-indexer v0.1.0 (/work/chronik/chronik-indexer)
error: unused variable: `cp_height`
   --> chronik/chronik-indexer/src/query/blocks.rs:313:9
    |
313 |         cp_height: i32,
    |         ^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_cp_height`
    |
    = note: `-D unused-variables` implied by `-D warnings`
    = help: to override `-D warnings` add `#[allow(unused_variables)]`

error: function `is_odd` is never used
  --> chronik/chronik-indexer/src/merkle.rs:11:4
   |
11 | fn is_odd(n: usize) -> bool {
   |    ^^^^^^
   |
   = note: `-D dead-code` implied by `-D warnings`
   = help: to override `-D warnings` add `#[allow(dead_code)]`

error: function `branch_length` is never used
  --> chronik/chronik-indexer/src/merkle.rs:15:4
   |
15 | fn branch_length(num_blocks: usize) -> usize {
   |    ^^^^^^^^^^^^^

error: function `hash_concatenated_bytes` is never used
  --> chronik/chronik-indexer/src/merkle.rs:19:4
   |
19 | fn hash_concatenated_bytes(h1: &[u8; 32], h2: &[u8; 32]) -> [u8; 32] {
   |    ^^^^^^^^^^^^^^^^^^^^^^^

error: struct `BlockMerkleTree` is never constructed
  --> chronik/chronik-indexer/src/merkle.rs:26:8
   |
26 | struct BlockMerkleTree {
   |        ^^^^^^^^^^^^^^^

error: associated items `new`, `hash_one_level`, `merkle_root_and_branch`, and `invalidate_block` are never used
   --> chronik/chronik-indexer/src/merkle.rs:31:8
    |
30  | impl BlockMerkleTree {
    | -------------------- associated items in this implementation
31  |     fn new() -> Self {
    |        ^^^
...
35  |     fn hash_one_level(
    |        ^^^^^^^^^^^^^^
...
58  |     fn merkle_root_and_branch(
    |        ^^^^^^^^^^^^^^^^^^^^^^
...
101 |     fn invalidate_block(&mut self, height: usize) {
    |        ^^^^^^^^^^^^^^^^

error: could not compile `chronik-indexer` (lib) due to 6 previous errors
ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik failed with exit code 1

Tail of the build log:

test io::token::tests::test_batch_disconnect_block::test_batch_disconnect ... ok
test plugins::io::tests::test_plugin_writer ... ok
test io::token::tests::test_batch_genesis::test_batch_genesis_alp ... ok
test plugins::io::tests::test_plugin_metas ... ok
test ser::tests::test_deserialize_err ... ok
test ser::tests::test_deserialize_leftover_err ... ok
test ser::tests::test_err_display_deserialize ... ok
test ser::tests::test_err_display_deserialize_leftover ... ok
test ser::tests::test_err_display_serialize ... ok
test ser::tests::test_roundtrip ... ok
test ser::tests::test_roundtrip_vec ... ok
test ser::tests::test_serialize_err ... ok
test io::spent_by::tests::test_spent_by ... ok
test io::token::tests::test_batch_genesis::test_batch_genesis_slp_fungible ... ok
test reverse_lookup::tests::test_reverse_lookup ... ok
test io::token::tests::test_batch_unknown::test_batch_unknown ... ok
test io::token::tests::test_batch_vault::test_batch_vault ... ok
test io::token::tests::test_batch_nft::test_batch_slp_nft1 ... ok
test mem::tokens::tests::test_mempool_tokens ... ok
test io::blocks::tests::test_blocks ... ok
test index_tx::tests::test_prepare_indexed_txs ... ok
test io::txs::tests::test_insert_txs ... ok
test reverse_lookup::tests::test_reverse_lookup_rng ... ok

test result: ok. 37 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 2.09s

     Running unittests src/lib.rs (abc-ci-builds/build-chronik-plugins/cargo/build/debug/deps/chronik_http-479bdf71fe02e1ff)

running 2 tests
test error::tests::test_report_error ... ok
test protobuf::tests::test_protobuf ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

     Running unittests src/lib.rs (abc-ci-builds/build-chronik-plugins/cargo/build/debug/deps/chronik_indexer-49736bf92fe6acc5)

running 4 tests
test merkle::tests::test_roots ... FAILED
test indexer::tests::test_plugin_versions ... ok
test indexer::tests::test_indexer ... ok
test indexer::tests::test_schema_version ... ok

failures:

---- merkle::tests::test_roots stdout ----
thread 'merkle::tests::test_roots' panicked at chronik/chronik-indexer/src/merkle.rs:193:13:
assertion `left == right` failed
  left: "b8c02be1675dc8b30aacf903a1a752927057125c0815be774b112dd02722dcab"
 right: "abdc2227d02d114b77be15085c1257709252a7a103f9ac0ab3c85d67e12bc0b8"
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    merkle::tests::test_roots

test result: FAILED. 3 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 1.82s

error: test failed, to rerun pass `-p chronik-indexer --lib`
ninja: build stopped: cannot make progress due to previous errors.
Build build-chronik-plugins failed with exit code 1
PiRK retitled this revision from [chronik] Compute a block merkle tree as used for checkpoints in the electrumx protocol. to [chronik] Add a struct to compute a block merkle tree.
PiRK edited the summary of this revision. (Show Details)
PiRK edited the test plan for this revision. (Show Details)

add tests, fix the endianness returned by hash_concatenated_bytes, fix a bunch of compilation warnings/errors

PiRK published this revision for review.Aug 2 2024, 10:28
tobias_ruck added a subscriber: tobias_ruck.
tobias_ruck added inline comments.
chronik/chronik-indexer/src/merkle.rs
11 ↗(On Diff #49009)

you can actually use the is-odd crate to simplify this

(I'm joking ofc)

16 ↗(On Diff #49009)

is this how it's implemented in Electrum/Fulcrum too? It seems like a bad idea to rely on floating point numbers for consensus code

Instead, you can use leading_zeros (should cast num_blocks to u64 or u32 first!), like here: https://stackoverflow.com/a/72253642

So this *should* just be what I suggested (but please double-check)

19 ↗(On Diff #49009)

why not consistently use the Sha256d struct here? Makes it clear what these arrays actually are and doesn't have the magic 32 numbers

21 ↗(On Diff #49009)
31 ↗(On Diff #49009)

same here, as an idea

46 ↗(On Diff #49009)

You can actually simplify this with the is-even crate

(joking ofc, ok I need to stop)

70 ↗(On Diff #49009)

I think it might make it more readable to introduce a struct for this result

125 ↗(On Diff #49009)

You can use the from_be_hex functions on Hashed here (and change the return value to Sha256d):

use crate::hash::Hashed;
138 ↗(On Diff #49009)

You can also use the Hashed::hex_be function here, we don't need to reinvent the wheel 🙃

172 ↗(On Diff #49009)

looks like this should be a const? or it seems like it should return Vec<Sha256d>

This revision now requires changes to proceed.Aug 2 2024, 11:36
Fabien added inline comments.
chronik/chronik-indexer/src/merkle.rs
11 ↗(On Diff #49009)

Macro zero_day_since_new_dependency:  npm style

use Sha256d instead of [u8; 32] everywhere and use integer arithmetic in branch_length

The build failed due to an unexpected infrastructure outage. The administrators have been notified to investigate. Sorry for the inconvenience.
The build failed due to an unexpected infrastructure outage. The administrators have been notified to investigate. Sorry for the inconvenience.
The build failed due to an unexpected infrastructure outage. The administrators have been notified to investigate. Sorry for the inconvenience.
The build failed due to an unexpected infrastructure outage. The administrators have been notified to investigate. Sorry for the inconvenience.
The build failed due to an unexpected infrastructure outage. The administrators have been notified to investigate. Sorry for the inconvenience.

rebase on latest master

chronik/chronik-indexer/src/merkle.rs
17 ↗(On Diff #49284)

The results match the previous floating-point arithmetic implementation: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=5961ea0699dc3c4f03cee9cc89b27849

tobias_ruck added inline comments.
chronik/chronik-indexer/src/merkle.rs
17 ↗(On Diff #49284)

might be an idea to add a few tests for this, you can access this function in the tests module below (despite being private)

80 ↗(On Diff #49284)

Seems better to just inline this (not too happy with the name bl tbh); it will only be computed once when entering the loop, and is not used elsewhere.

154 ↗(On Diff #49284)

any reason not to use hex_to_sha256d here? can also remove that function, or inline it to the test_branches test.

160 ↗(On Diff #49284)

I think we need to specify the actual height and cp_h here in the comment, otherwise people have to figure out what to put there to verify

304–305 ↗(On Diff #49284)

this is probably more readable; we're not targeting 16-bit architectures

This revision now requires changes to proceed.Aug 19 2024, 21:34
PiRK marked an inline comment as done.

I missed one

PiRK marked 2 inline comments as done.Aug 21 2024, 18:12
PiRK added inline comments.
chronik/chronik-indexer/src/merkle.rs
80 ↗(On Diff #49284)

It is used once above (line 75). I can rename it, just need to find a name that does not shadow the function name.

160 ↗(On Diff #49284)

I think my change should clarify the comment.

tobias_ruck added inline comments.
chronik/chronik-indexer/src/merkle.rs
15 ↗(On Diff #49303)

You can also call the function calc_branch_length (or _len) and then the branch_length name (or branch_len) is free

This revision is now accepted and ready to land.Aug 21 2024, 18:32

use a verb in the function name, as per suggestion