compute_split's O(n²) largest-remainder dust distribution should be O(n log n) — compounds with #8's unbounded recipients

[chonilius]

Overview

compute_split's largest-remainder dust-distribution loop (contracts/escrow/src/lib.rs:295-317, byte-identical in contracts/milestones/src/lib.rs:279-301) is algorithmically O(n²) in the number of recipients, not O(n log n) as a largest-remainder allocation can be implemented:

let mut dust = distributable - allocated;
while dust > 0 {
    let mut best_index: u32 = 0;
    let mut best_remainder: i128 = -1;
    for (i, remainder) in remainders.iter().enumerate() {
        // ...linear scan to find the current largest remainder...
    }
    // ...award one unit to best_index, mark it consumed (-1)...
    dust -= 1;
}

Each iteration of the outer while dust > 0 loop performs a full linear scan of remainders (an inner for loop over all n recipients) to find the single largest remaining value, then "consumes" it and repeats. Since dust can be as large as recipients.len() - 1 in the worst case (the maximum possible leftover under integer division with basis points summing to exactly 10000), the total work is O(dust × n), which is O(n²) in the worst case — e.g. a 100-recipient split with maximal dust does on the order of 10,000 comparison operations just for remainder distribution, on top of the O(n) work already done to compute each share/remainder pair.

A largest-remainder allocation can be computed in O(n log n) instead: sort (index, remainder) pairs once by remainder descending (with the existing address-based tie-break as a secondary sort key), then award one unit to each of the first dust entries in that sorted order — no repeated re-scanning needed. This directly compounds with #8 ("Unbounded recipients: Vec<(Address, u32)> in release/release_issue risks resource-limit transaction failure"): the larger a team split is allowed to grow (the exact axis #8 is about bounding), the worse this algorithm's quadratic cost gets, meaning the two issues' severities are multiplicative, not independent — a fix for #8 that raises or removes the practical recipient-count ceiling makes this issue's cost curve correspondingly steeper, and a fix for this issue increases the recipient count #8's eventual bound can safely allow before hitting Soroban's CPU-instruction budget.

This is distinct from #17 ("property-based fuzz harness for compute_split") and #23 ("Soroban instruction/resource-budget regression benchmark suite") — both of those are about testing/measuring behavior and cost; this issue is a specific, concrete algorithmic fix for an inefficiency identified by reading the code directly, independent of whether either testing effort has landed yet.

Requirements

• Reimplement the dust-distribution step in both escrow::compute_split and milestones::compute_split (kept in sync manually today, or via Extract compute_split into a shared crate with proof of behavioral equivalence #16's shared-crate extraction if that lands first) using a single sort by (remainder desc, address asc) followed by a linear pass awarding dust to the first dust entries, replacing the current repeated-linear-scan approach.
• Confirm the change is behavior-preserving — the same recipients should receive the same dust units as before for every existing test case (the largest-remainder-with-address-tiebreak rule isn't changing, only how it's computed), so all of Correctness audit of compute_split under zero-recipient-adjacent, duplicate-address, and self-referential edge cases #28/Build a property-based fuzz harness for compute_split covering adversarial recipient vectors #17's existing and eventual edge-case tests should pass unmodified against the new implementation.
• If Build a Soroban instruction/resource-budget regression benchmark suite for all entrypoints #23's benchmark suite exists by the time this lands, add a before/after resource-cost comparison for a large (e.g. 50-100 recipient) split to quantify the improvement concretely.

Acceptance Criteria

• Dust distribution reimplemented as O(n log n) in both escrow and milestones
• All existing tests in both escrow::test and milestones::test (particularly test_release_distributes_rounding_dust_by_largest_remainder and test_adversarial_ordering_resistance) pass unmodified, proving behavior preservation
• New test with a larger recipient count (e.g. 50+) exercising multiple dust units distributed correctly under the new algorithm
• cargo test --workspace passes

Additional Notes

• Precise references: contracts/escrow/src/lib.rs:295-317 (the O(n²) loop), identical at contracts/milestones/src/lib.rs:279-301.
• Soroban's soroban_sdk::Vec<T> doesn't expose a built-in sort_by the way std::vec::Vec does (no-std, host-object-backed collection) — implementation will likely need either a manual sort (e.g. insertion sort is fine for reasonably small n and would still be an improvement, though a proper comparison sort is preferable) or collecting into a local array/fixed-size structure if no_std constraints make alloc-based sorting awkward; this is worth scoping carefully given the #![no_std] constraint (contracts/escrow/src/lib.rs:8) shared by all three contracts.
• Cross-references: Unbounded recipients: Vec<(Address, u32)> in release/release_issue risks resource-limit transaction failure #8 (unbounded recipients — directly compounding, as explained above); Build a property-based fuzz harness for compute_split covering adversarial recipient vectors #17 (compute_split fuzz harness — this issue's fix must remain behaviorally identical under whatever adversarial vectors that harness eventually generates); Build a Soroban instruction/resource-budget regression benchmark suite for all entrypoints #23 (resource-budget benchmarking — the natural place to quantify this issue's improvement once both exist); Extract compute_split into a shared crate with proof of behavioral equivalence #16 (shared-crate extraction — if it lands first, this issue's fix only needs to be implemented once instead of twice).

[aristotle224]

I have experience working with Rust/Soroban smart contracts and blockchain systems where correctness, resource usage, and deterministic behaviour are important. I’m comfortable working with contract-level algorithms, test suites, and changes that need to preserve existing financial allocation semantics.

I would approach this by first examining the current compute_split implementations in both escrow and milestones, particularly the existing largest-remainder and address-based tie-breaking behaviour. I’d replace the repeated linear scan with a single ordering of (index, remainder) pairs by descending remainder and ascending address, then distribute the dust through one linear pass.

Because these contracts are no_std and use soroban_sdk::Vec, I’d first verify the available collection/sorting options rather than assuming standard Rust Vec APIs are available. The implementation needs to improve the complexity without introducing unnecessary allocations or violating Soroban resource constraints.

I’d preserve the existing allocation rule exactly and add a larger-recipient test with multiple dust units, while ensuring the existing largest-remainder and adversarial-ordering tests remain unchanged. I’d also run the full workspace test suite and, if the resource benchmark from #23 is available, use it to quantify the improvement for larger recipient sets.

[annieolivia61-ux]

I will love to solve this issue

[grantfox-oss]

🦊 GrantFox — @aristotle224 has been assigned to this issue as part of the Third Campaign campaign!

Next steps:

1. Open a Pull Request referencing this issue (e.g., Closes #55)
2. Your PR will be reviewed by the MergeFi maintainers

Good luck! Track your progress on GrantFox.

[grantfox-oss]

🎉 This issue has been marked as completed on GrantFox as part of the Third Campaign campaign!

@aristotle224's PR #61 was approved and merged by @chonilius.

🏆 @aristotle224: You earned 35 FoxPoints for this contribution! Your current tier: Explorer (414 total points). Track your full progress on GrantFox.

👏 Great work, @aristotle224! Keep contributing to MergeFi.