Aggregation: make the MAX_KEYS exclusive bound explicit in the public contract

[alexanderlhicks]

The internal constant documentation correctly says that MAX_KEYS is an exclusive bound. The public contract is inconsistent with that:

• AggregateSignature.public_keys says "at most MAX_KEYS long".
• AggregateError::TooLarge says "more than MAX_KEYS signers".
• Both host checks reject when the relevant count is >= MAX_KEYS.

Exactly 65,536 slots are therefore rejected even though the public wording says they are allowed. The guest is compiled around the same strict range, so this is an API-contract and availability issue rather than a guest/host soundness disagreement.

The smallest and safest fix is documentation: consistently say "fewer than MAX_KEYS" and "at least MAX_KEYS," or rename the constant to make its exclusivity unambiguous. Accepting exactly 65,536 would instead require increasing the guest and minimum-memory range, not merely changing the host comparisons.

Please add helper-level boundary tests showing that MAX_KEYS - 1 satisfies the capacity check and MAX_KEYS returns the documented error, without constructing an enormous proof.

AI assistance disclosure: this issue was prepared with help from an OpenAI Codex agent during a fresh adversarial review of PR 10. The agent was instructed to reproduce or otherwise evidence each finding, try to falsify it, distinguish PR changes from pre-existing and later mainline changes, and make the proposed resolution pedagogical and actionable. The evidence in this issue was rechecked against merged commit f5d6e5040d666981005371742a6f21640ce865a1.

[alexanderlhicks]

Proposed fix

This is the issue-specific portion of the combined local diff based on f5d6e5040d666981005371742a6f21640ce865a1. It has not been committed or pushed.

The intended invariant is n_keys + n_dup < MAX_KEYS everywhere. The guest already enforces that strict inequality. The proposed Rust change makes the public contract say the same thing, checks the total before allocating coverage tables, and pins both sides of the boundary in a small unit test.

Exact diff

diff --git a/crates/rec_aggregation/src/aggregation.rs b/crates/rec_aggregation/src/aggregation.rs
--- a/crates/rec_aggregation/src/aggregation.rs
+++ b/crates/rec_aggregation/src/aggregation.rs
@@ -345,4 +345,4 @@ pub struct AggregateSignature {
     pub message: xmss::Message,
     pub epoch: u32,
-    /// Strictly sorted, deduplicated, non-empty, at most [`MAX_KEYS`] long.
+    /// Strictly sorted, deduplicated, non-empty, and fewer than [`MAX_KEYS`] long.
     pub public_keys: Vec<XmssPublicKey>,
@@ -374,5 +374,5 @@ pub enum AggregateError {
     /// Nothing to aggregate: no raw signatures and no children.
     Empty,
-    /// More than [`MAX_CHILDREN`] children, or more than [`MAX_KEYS`] signers
-    /// once the duplicate slots are counted.
+    /// More than [`MAX_CHILDREN`] children, or at least [`MAX_KEYS`] signer
+    /// slots once duplicates are counted.
     TooLarge,
@@ -402,4 +402,12 @@ fn check_signer_set(keys: &[XmssPublicKey]) -> Result<(), VerifyError> {
     Ok(())
 }
 
+fn check_key_slot_count(n_slots: usize) -> Result<(), AggregateError> {
+    if n_slots >= MAX_KEYS {
+        Err(AggregateError::TooLarge)
+    } else {
+        Ok(())
+    }
+}
+
 impl AggregateSignature {
@@ -1486,4 +1494,9 @@ fn take_slot(
 }
 
 fn plan_coverage(raw: &[XmssPublicKey], children: &[&[XmssPublicKey]]) -> Result<Coverage, AggregateError> {
+    let n_slots = children
+        .iter()
+        .try_fold(raw.len(), |total, child| total.checked_add(child.len()))
+        .ok_or(AggregateError::TooLarge)?;
+    check_key_slot_count(n_slots)?;
     let mut keys: Vec<XmssPublicKey> = raw.to_vec();
@@ -1509,7 +1522,5 @@ fn plan_coverage(raw: &[XmssPublicKey], children: &[&[XmssPublicKey]]) -> Result
                 .collect()
         })
         .collect();
-    if keys.len() + duplicates.len() >= MAX_KEYS {
-        return Err(AggregateError::TooLarge);
-    }
+    debug_assert_eq!(keys.len() + duplicates.len(), n_slots);
     Ok(Coverage {
@@ -2432,5 +2443,12 @@ mod tests {
         aggregate(&[], signers.to_vec(), message(), EPOCH, LOG_INV_RATE).expect("leaf aggregates")
     }
 
+    #[test]
+    fn key_slot_limit_is_exclusive() {
+        assert_eq!(check_key_slot_count(MAX_KEYS - 1), Ok(()));
+        assert_eq!(check_key_slot_count(MAX_KEYS), Err(AggregateError::TooLarge));
+        assert_eq!(check_key_slot_count(usize::MAX), Err(AggregateError::TooLarge));
+    }
+
     #[test]
     fn aggregate_one_signer() {

Design justification

• This keeps MAX_KEYS and the guest unchanged. Accepting exactly 65,536 would require a protocol and memory-range change; this proposal only corrects and centralizes the Rust contract.
• try_fold with checked_add makes overflow a normal TooLarge result and obtains the exact slot count before cloning keys or allocating claimed and duplicate tables.
• The coverage walk still constructs the signer union and duplicate slots exactly as before. The debug assertion checks the internal partition against the already validated total without duplicating a release-path branch.
• The helper is private and local to the one capacity rule, matching the repository's preference for simple code over a new public abstraction.
• The wire format, public input, guest bytecode, and valid capacity remain unchanged.

Validation

Exact boundary test:

$ cargo test --release -p rec_aggregation key_slot_limit_is_exclusive
test aggregation::tests::key_slot_limit_is_exclusive ... ok
1 passed; 0 failed

Combined regression coverage:

$ cargo test --release -p rec_aggregation -p xmss
rec_aggregation: 10 passed; 0 failed; 3 ignored
arena_prove:     1 passed; 0 failed
xmss_tests:      7 passed; 0 failed; 1 ignored

$ cargo testall
all active workspace tests and doctests passed

$ cargo clippyall
exit 0

$ cargo docall
exit 0

$ rustfmt --edition 2024 --check crates/rec_aggregation/src/aggregation.rs
# no output, exit 0

$ git diff --check
# no output, exit 0

The whole-workspace formatter currently reports pre-existing ordering drift in ten files untouched by this proposal; the changed Rust file itself is clean, and that unrelated churn is intentionally excluded.

The fenced issue-specific diff was extracted verbatim and git apply --check accepted it against f5d6e5040d666981005371742a6f21640ce865a1.

AI assistance disclosure: this proposed patch and validation report were prepared with help from an OpenAI Codex agent. The agent was asked to review the exact diff as if it were a focused PR, verify the host and guest inequalities, check overflow and allocation ordering, exercise both boundary values and honest aggregation, and separate pre-existing formatting drift from this change.