Commit Graph

428 Commits

Author SHA1 Message Date
Kris Nuttycombe 07a88c34ac Adds a `Retention` enum to the `incrementalmerkletree` crate.
This will be necessary in order to make the testing infrastructure
reusable for shardtree.
2023-02-16 15:01:53 -07:00
Kris Nuttycombe aa1d59f47a `witness` now witnesses at a checkpoint, rather than a root.
This change exposed an inconsistency in how `BridgeTree` and
`CompleteTree` were tracking `Mark` operations, which has now also been
fixed.

The behavior of the "unmark" operation has been simplified, such that it
now ensures that a marked node will be made eligible for garbage
collection when the checkpoint for the tree state in which the mark was
forgotten rolls off the back of the checkpoint queue.
2023-02-16 15:01:53 -07:00
Kris Nuttycombe 92121642b0
Merge pull request #54 from nuttycom/improve_addrs
Add `Address` methods to facilitate tree traversal.
2023-02-16 15:01:29 -07:00
Kris Nuttycombe 2e9043ef82 Add `Address` methods to facilitate tree traversal. 2023-02-16 14:32:54 -07:00
str4d 3c19b5320f
Merge pull request #55 from nuttycom/update_msrv_1.60
Update MSRV to 1.60
2023-02-16 18:22:49 +00:00
Kris Nuttycombe 39fe209e21
Apply suggestions from code review
Co-authored-by: str4d <thestr4d@gmail.com>
2023-02-16 11:02:47 -07:00
Kris Nuttycombe dff6be7221 Update MSRV to 1.60
The transitive dependency we have on `unarray` is forcing this update.
Also, update CI actions to eliminate dependencies on the unmaintained
`actions-rs` Rust CI tools.
2023-02-16 10:51:41 -07:00
str4d da9ab5a71d
Merge pull request #49 from nuttycom/workspace_refactor
Move common utilities to the incrementalmerkletree crate & turn into a workspace.
2023-01-06 09:22:30 +00:00
Kris Nuttycombe 8998f839ce Change `append` to take ownership of the value being appended.
It is now up to the caller to clone the value if necessary.
2023-01-04 14:08:11 -07:00
Kris Nuttycombe 0dde92c699 Move `testing::lazy_root` to `testing::complete_tree::root` & make crate-private
The former name didnt make sense anyway, because there's nothing lazy
about the result.
2022-12-21 14:48:53 -07:00
Kris Nuttycombe 50779d2bd5 Consolidate bridgetree tests. 2022-12-21 12:53:17 -07:00
Kris Nuttycombe 4e2883c707 Move CombinedTree to incrementalmerkletree::testing 2022-12-21 12:53:17 -07:00
Kris Nuttycombe 3f88ac3af2 Move complete_tree testing module to incrementalmerkletree 2022-12-21 12:53:17 -07:00
Kris Nuttycombe a8c5ce1c98 Move `check_operations` to `incrementalmerkletree::testing` 2022-12-21 12:53:17 -07:00
Kris Nuttycombe 02a33c5c32 Refactor check_operations to generalize usage. 2022-12-21 12:53:17 -07:00
Kris Nuttycombe 6b4bcda423 Move shared example tests to incrementalmerkletree::testing 2022-12-21 12:53:17 -07:00
Kris Nuttycombe 6b6d108de6 Move randomized test generators to incrementalmerkletree 2022-12-21 12:53:17 -07:00
Kris Nuttycombe eb3413837e Move `Tree` and `Frontier` traits to `incementalmerkletree::testing` 2022-12-21 12:53:17 -07:00
Kris Nuttycombe c5c6c65799 Move position & hashable types to incrementalmerkletree root. 2022-12-21 12:52:57 -07:00
Kris Nuttycombe b2a68215a0 Move the `bridgetree` crate to a workspace. 2022-12-21 11:59:43 -07:00
Kris Nuttycombe 8f6056c73e
Merge pull request #51 from nuttycom/master
Release bridgetree v0.2.0.
2022-12-20 17:30:23 -07:00
Kris Nuttycombe 61a34e5ec5 Clarify the witnees->mark renaming in the `Tree` interface. 2022-12-20 17:05:01 -07:00
Kris Nuttycombe e78fb14a43 Update changelogs for bridgetree v0.2.0. 2022-12-20 16:53:14 -07:00
Kris Nuttycombe ae75af55b3 Release bridgetree v0.2.0. 2022-12-19 17:03:16 -07:00
Kris Nuttycombe 49eca24a11
Merge pull request #46 from zingolabs/doc_update
Doc update
2022-08-16 12:05:29 -06:00
zancas 0eb0cc527d
typo 2022-08-08 17:36:24 -06:00
zancas 99f21fc543
Make general statement about merkle trees more conservative 2022-08-08 17:34:11 -06:00
Kris Nuttycombe ab23aafe5a
Merge pull request #44 from nuttycom/improve_naming
Rework the API for move to the `bridgetree` crate.
2022-08-04 16:50:34 -06:00
Kris Nuttycombe a98875d196 Improve `BridgeTree` and `MerkleBridge` documentation.
Co-authored-by: ebfull <ewillbefull@gmail.com>
2022-08-04 13:00:58 -06:00
Kris Nuttycombe 95d95f46db Export position & hashing types from the top-level module. 2022-08-04 13:00:58 -06:00
Kris Nuttycombe ad2c751633 Improve reporting for errors that can be generated in witness creation. 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 7556c04472 Update bridgetree root module documentation. 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 1581ce6864 Update README 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 4d35824257 Minimize scope of allowed deprecations in testing.rs 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 693961be3f Remove codecov task (never worked) 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 5e04301a4b Move documentation to top-level methods + minor cleanup. 2022-08-04 13:00:58 -06:00
Kris Nuttycombe adf9ba26e4 Move the BridgeTree type to the root module. 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 6e97389d1b Move `Frontier` and `Tree` traits to testing module.
These traits are only used for comparison testing between
the CompleteTree and BridgeTree types; they don't represent
useful independent abstractions.
2022-08-04 13:00:58 -06:00
Kris Nuttycombe 55731de321 Move Hashable trait to hashing module 2022-08-04 13:00:58 -06:00
Kris Nuttycombe 2a19b40fc1 Move position types to position module. 2022-08-04 13:00:56 -06:00
Kris Nuttycombe d631b8278a Move common test code into the testing module. 2022-08-04 13:00:05 -06:00
Kris Nuttycombe e19446f8fd Make test utilities available under a test-dependencies feature. 2022-08-04 13:00:05 -06:00
Kris Nuttycombe 7331a8f458 Rename fragments -> ommers 2022-08-04 13:00:05 -06:00
Kris Nuttycombe 6b6548f02e Rename authentication_path -> witness 2022-08-04 13:00:05 -06:00
Kris Nuttycombe ee93cb8598 Rename witness->mark 2022-08-04 13:00:04 -06:00
Kris Nuttycombe 7bd1907451
Merge pull request #43 from nuttycom/fix_frontiers
Remove the `bridgetree::Leaf` type & make ommer levels start at 0
2022-07-22 16:14:02 -06:00
Kris Nuttycombe 40e31f340c
Merge pull request #42 from nuttycom/sharing_tree
Alter MerkleBridge to avoid storing duplicate ommers.
2022-07-22 12:46:07 -06:00
Kris Nuttycombe 3b08071125 Remove the `bridgetree::Leaf` type & make ommer levels start at 0
This is a major refactoring that gets rid of a significant wart
in the design of the `bridgetree::Frontier` type that has existed
since the the project's inception.

The `Leaf` type incorrectly treated the siblings of leaves at
odd positions as special, whereas they should have been simply
treated as ordinary entries in the frontier's ommers list. Correcting
this allows for the code to be significantly simplified in a number
of places.
2022-07-21 18:32:58 -06:00
Kris Nuttycombe 4973b6682f Alter MerkleBridge to avoid storing duplicate ommers.
Prior to this change, each position being tracked would
require an entry in the `auth_fragments` map for each
bridge in a BridgeTree. However, very frequently, these
entries would duplicate storage of nodes higher up in the
tree, wherever a single node in the was an ancestor of
a leaf being tracked.

This commit restructures the tracking of auth data to
avoid this duplication of data, as well as the redundant
work that was required to produce each copy of the duplicated
nodes.
2022-07-21 18:27:09 -06:00
Kris Nuttycombe f081cfc81e Factor out bridge-level auth path construction. 2022-07-14 14:22:59 -06:00