Skip to content

Conversation

@roberto-bayardo
Copy link
Collaborator

@roberto-bayardo roberto-bayardo commented Oct 3, 2025

  • creates a variant of adb::current called adb::ordered::Current that supports key exclusion proofs.
  • current_init benchmark is merged with anydb's init benchmarks all under "fixed_init", since they all now share the same trait.
  • added fuzz test for ordered based on the unordered one, adding testing of get_span
  • fixed bug in the implementation of Db trait for unordered::current turned up by the benchmark (it was passing calls through directly to any, bypassing the bitmap maintenance.)

Resolves #1409

@roberto-bayardo roberto-bayardo changed the base branch from main to ordered-any October 3, 2025 20:53
@roberto-bayardo roberto-bayardo changed the title [storage/adb/current] Exclusion proof db [storage/adb/current] [WiP] Exclusion proof db Oct 3, 2025
@cloudflare-workers-and-pages
Copy link

cloudflare-workers-and-pages bot commented Oct 3, 2025

Deploying monorepo with  Cloudflare Pages  Cloudflare Pages

Latest commit: fbd27e0
Status: ✅  Deploy successful!
Preview URL: https://fbf1fce3.monorepo-eu0.pages.dev
Branch Preview URL: https://exclusion-proof-db.monorepo-eu0.pages.dev

View logs

@roberto-bayardo roberto-bayardo force-pushed the ordered-any branch 7 times, most recently from daced5e to 5ba7fc9 Compare October 9, 2025 18:47
@roberto-bayardo roberto-bayardo force-pushed the exclusion-proof-db branch 3 times, most recently from c05e8b7 to 0f4496f Compare October 9, 2025 22:08
@roberto-bayardo roberto-bayardo force-pushed the ordered-any branch 2 times, most recently from 264d8d8 to 475173b Compare October 10, 2025 22:05
@roberto-bayardo roberto-bayardo force-pushed the exclusion-proof-db branch 2 times, most recently from 51d13da to c2aff73 Compare October 13, 2025 23:28
@roberto-bayardo roberto-bayardo changed the base branch from ordered-any to main October 13, 2025 23:30
@roberto-bayardo roberto-bayardo force-pushed the exclusion-proof-db branch 3 times, most recently from 2f0cbcb to 49a8525 Compare October 13, 2025 23:56
Copy link
Contributor

Copilot AI left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull Request Overview

This PR introduces an ordered variant of the current authenticated database (ADB) that supports key exclusion proofs. The main purpose is to extend the existing unordered current ADB implementation with ordered key capabilities, allowing users to prove that specific keys do not exist in the database.

Key changes include:

  • Creation of a new adb::current::ordered module with exclusion proof functionality
  • Refactoring of the existing current ADB to separate ordered and unordered variants
  • Addition of helper methods for empty MMR root computation and ordered key operations

Reviewed Changes

Copilot reviewed 11 out of 11 changed files in this pull request and generated 2 comments.

Show a summary per file
File Description
storage/src/mmr/mem.rs Added empty_mmr_root helper method and corresponding test
storage/src/mmr/hasher.rs Updated test to use new empty MMR root helper
storage/src/mmr/grafting.rs Fixed documentation reference from specific type to module
storage/src/adb/mod.rs Added KeyExists error variant for exclusion proof failures
storage/src/adb/current/unordered.rs Updated to use new shared verification function and added next_key field
storage/src/adb/current/ordered.rs New implementation of ordered current ADB with exclusion proof support
storage/src/adb/current/mod.rs Refactored to support both ordered and unordered variants, added shared verification functions
storage/src/adb/benches/current_init.rs Updated import to use unordered variant
storage/src/adb/any/fixed/unordered.rs Added is_empty helper method
storage/src/adb/any/fixed/ordered.rs Made fields and methods public for use by current ordered implementation
storage/fuzz/fuzz_targets/adb_current_operations.rs Updated import to use unordered variant

Tip: Customize your code reviews with copilot-instructions.md. Create the file or learn how to get started.

@roberto-bayardo roberto-bayardo changed the title [storage/adb/current] [WiP] Exclusion proof db [storage/adb/current] adb::ordered::current (provides exclusion proof support) Oct 13, 2025
@commonwarexyz commonwarexyz deleted a comment from Copilot AI Oct 14, 2025
@roberto-bayardo roberto-bayardo marked this pull request as ready for review October 14, 2025 02:14
@roberto-bayardo roberto-bayardo force-pushed the exclusion-proof-db branch 2 times, most recently from 044c9c7 to 289033a Compare October 14, 2025 18:34
danlaine
danlaine previously approved these changes Oct 23, 2025
Copy link
Contributor

@patrick-ogrady patrick-ogrady left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

very very small nits

}

/// Whether the span defined by `span_start` and `span_end` contains `key`.
pub fn span_contains(span_start: &K, span_end: &K, key: &K) -> bool {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Very nice standalone function ❤️

c.bench_function(
&format!(
"{}/elements={} operations={}, keyspace={}",
"{}/elements={} operations={}, variant={}",
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We should put variant first in this list

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

done, though I didn't reorder the loop vars. lmk if you need that changed too. I kind of like variant last in the loop vars since you see the performance impact of each variation across the same params.

/// # Panics
///
/// Panics if there is not at least one active operation above the inactivity floor.
async fn raise_floor(&mut self) -> Result<(), Error> {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looking forward to seeing this ported to the other DBs ❤️

}

async fn update(&mut self, key: K, value: V) -> Result<(), crate::store::Error> {
self.any.update(key, value).await.map_err(Into::into)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for clarifying!

@patrick-ogrady
Copy link
Contributor

from the LLMs:

• - [P0] storage/src/adb/current/ordered.rs:201 – last_commit_loc is initialized to status.len() - 1, i.e. the tip of the log, regardless of whether that element is actually a commit. After a clean restart with pending (uncommitted) updates at the end of the log, this field will point at the most recent update. The next time commit_ops runs it will call
    self.status.set_bit(*last_commit_loc, false), treating that update as the old commit and switching it to “inactive”. That silently drops the freshest update from the status bitmap, so subsequent proofs/root calculations will claim the key is inactive even though we just wrote it. Please compute the real last-commit location during replay (e.g. track the last
    Operation::CommitFloor you encounter and store its index, or have build_snapshot_from_log return it) and leave last_commit_loc as None when the log currently ends in non-commit operations.
    ```

@roberto-bayardo
Copy link
Collaborator Author

roberto-bayardo commented Oct 23, 2025

from the LLMs:

• - [P0] storage/src/adb/current/ordered.rs:201 – last_commit_loc is initialized to status.len() - 1, i.e. the tip of the log, regardless of whether that element is actually a commit. After a clean restart with pending (uncommitted) updates at the end of the log, this field will point at the most recent update. The next time commit_ops runs it will call
    self.status.set_bit(*last_commit_loc, false), treating that update as the old commit and switching it to “inactive”. That silently drops the freshest update from the status bitmap, so subsequent proofs/root calculations will claim the key is inactive even though we just wrote it. Please compute the real last-commit location during replay (e.g. track the last
    Operation::CommitFloor you encounter and store its index, or have build_snapshot_from_log return it) and leave last_commit_loc as None when the log currently ends in non-commit operations.
    ```

Not an issue. Recovery ensures the last operation (if any exists) is always a commit 👍

Went ahead and added an assertion check to confirm that.

@patrick-ogrady patrick-ogrady added this pull request to the merge queue Oct 23, 2025
Merged via the queue into main with commit 1dd4fd4 Oct 23, 2025
71 checks passed
@patrick-ogrady patrick-ogrady deleted the exclusion-proof-db branch October 23, 2025 16:50
@codecov
Copy link

codecov bot commented Oct 23, 2025

Codecov Report

❌ Patch coverage is 94.12766% with 69 lines in your changes missing coverage. Please review.
✅ Project coverage is 92.44%. Comparing base (05c90c9) to head (fbd27e0).
⚠️ Report is 7 commits behind head on main.

Files with missing lines Patch % Lines
storage/src/adb/current/ordered.rs 95.59% 47 Missing ⚠️
storage/src/adb/current/mod.rs 74.50% 13 Missing ⚠️
storage/src/adb/current/unordered.rs 62.50% 9 Missing ⚠️
@@            Coverage Diff             @@
##             main    #1799      +/-   ##
==========================================
+ Coverage   92.39%   92.44%   +0.04%     
==========================================
  Files         303      304       +1     
  Lines       79937    81445    +1508     
==========================================
+ Hits        73861    75294    +1433     
- Misses       6076     6151      +75     
Files with missing lines Coverage Δ
storage/src/adb/any/fixed/ordered.rs 96.84% <100.00%> (+0.25%) ⬆️
storage/src/adb/any/fixed/unordered.rs 96.10% <100.00%> (+0.98%) ⬆️
storage/src/adb/any/variable/mod.rs 97.15% <100.00%> (ø)
storage/src/adb/mod.rs 95.45% <ø> (ø)
storage/src/mmr/grafting.rs 86.32% <ø> (ø)
storage/src/mmr/hasher.rs 93.70% <100.00%> (+0.04%) ⬆️
storage/src/mmr/mem.rs 93.13% <100.00%> (+0.03%) ⬆️
storage/src/adb/current/unordered.rs 93.99% <62.50%> (+1.41%) ⬆️
storage/src/adb/current/mod.rs 80.64% <74.50%> (-6.32%) ⬇️
storage/src/adb/current/ordered.rs 95.59% <95.59%> (ø)

... and 19 files with indirect coverage changes


Continue to review full report in Codecov by Sentry.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 05c90c9...fbd27e0. Read the comment docs.

🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

[storage/adb] authenticated db with exclusion proofs

3 participants