Details

Reviewers

sdulfari
deadalnix

Group Reviewers

Restricted Project

Commits

rABC87b4609c7efe: [avalanche] Maintain a radix tree of the proofs

Summary

This will be used to send the short proof ids of our proofs to our peers. The radix tree is copy-on-write, which makes it possible to store a copy of the tree in the remote node data, so even if the proof set keep evolving we can retrieve the missing proofs based on an index snapshoted at the time of the copy, while only duplicating the subset of the tree that has changed.

Test Plan

ninja check-avalanche

Diff Detail

Repository

rABC Bitcoin ABC

Branch

avalanche_radix_tree_proof

Lint

Lint Passed

Unit

No Test Coverage

Build Status

Buildable 19052
Build 37856: Build Diff	lint-circular-dependencies · build-diff · build-without-wallet · build-debug · build-clang-tidy · build-clang
Build 37855: arc lint + arc unit

Event Timeline

Fabien created this revision.May 11 2022, 20:56

Herald added a reviewer: Restricted Project. · View Herald TranscriptMay 11 2022, 20:56

Fabien requested review of this revision.May 11 2022, 20:56

Fabien retitled this revision from [avalanche] Maintain a radix tree of the proof ids to [avalanche] Maintain a radix tree of the proofs.May 11 2022, 20:59

Harbormaster completed remote builds in B19004: Diff 33486.May 11 2022, 21:07

Generally true throughout this diff: the naming is too dependent on the underlying proofs database being a radix tree. A simple example at the peer manager interface is getProofRadixTree(). Does the caller care that the DB is a radix tree? If we change to some other COW DB, we'll end up with a lot of renaming to do.

src/avalanche/peermanager.cpp
319 ↗	(On Diff #33486)	Is synchronize necessary on insertions?
src/avalanche/test/peermanager_tests.cpp
1654 ↗	(On Diff #33486)	In addition to counting the leaves, is it worth keeping a list of proofs you built and ensuring each leaf can be found in that list?
1698 ↗	(On Diff #33486)	The above comment is even more relevant here.

This revision now requires changes to proceed.May 12 2022, 00:34

Rename to shareableProofs and getShareableProofsSnapshot(), because these proofs are intended to be shared with our peers.
Update the test to check against a list of expeced proofs rather than relying on the count.

Harbormaster completed remote builds in B19008: Diff 33493.May 12 2022, 08:58

Fabien added inline comments.May 12 2022, 10:00

src/avalanche/peermanager.cpp
319 ↗	(On Diff #33486)	The insertion might have copied part of the tree and the previous content can be released after readers are done

Make the ProofElement public

Fabien added a child revision: D11453: [avalanche] Introduce a CompactProofs class for managing the short proof ids.May 12 2022, 12:55

Harbormaster completed remote builds in B19009: Diff 33494.May 12 2022, 13:02

Fabien added a child revision: D11454: [avalanche] Move the ProofElement to its own header.May 12 2022, 15:06

deadalnix requested changes to this revision.May 12 2022, 18:52

deadalnix added a subscriber: deadalnix.

deadalnix added inline comments.

src/avalanche/peermanager.cpp
319 ↗	(On Diff #33494)	It is not needed. If it is needed, it is almost certainly a bug. Did ASAN yell at you before you put these barriers in place?
513 ↗	(On Diff #33494)	dito
699 ↗	(On Diff #33494)	You probably want a way to early exit the iteration, no?
src/avalanche/peermanager.h
162 ↗	(On Diff #33494)	Something doesn't make sense. The proof are duplicated between here and the various pools, no? That makes no sense, you want a tree of proofs, not a tree of gizmos that copy the proofs. If the main problem is that you want a `Uint256KeyWrapper` (which is a pretty bad name, what is this wrapper, why would I want to wrap my Uint256? What does this do?), then just pass an adapter to the radix tree to tell it how to get the id.
376 ↗	(On Diff #33494)	You probably don't want to eagerly copy and leave that to the caller, considering there is a synchronize operation involved.