Matching

1. Units#

PRICE_SCALE = 1e18. A product amount * price of two uint128 values fits in uint256. Sums of amounts (tier totals, demand, supply, Vmax) can exceed 2^128, so the pro-rata product remaining * baseAmount and the band product oraclePrice * (BPS ± d) can exceed 2^256: implementations must use arbitrary precision or at least 512-bit intermediates there. No step may wrap or saturate silently.

Example: an 18-decimal Stock Token quoted in 6-decimal USDG at $211.40 per whole token has price 211.40 * 1e6 * 1e18 / 1e18 = 211_400_000.

Robinhood Chain Stock Tokens keep raw balances fixed across corporate actions and scale the displayed amount through uiMultiplier. Chainlink's Stock Token feeds price one raw token (equity price times multiplier). Kasumi prices are therefore per raw token and need no multiplier handling. Orders live for one epoch, so a multiplier change cannot stale a resting order; the oracle is paused during the change and the market does not trade (§3).

2. Input#

MatchInput {
  epochId: uint64
  markets: [{ marketId: bytes32, oraclePrice: uint256, maxOracleDeviationBps: uint16 }]
  orders:  [{ commitment: bytes32, marketId: bytes32, side: 0|1,
              baseAmount, minFillBase, limitPrice: uint128,
              allowPartialFill: bool, maxOracleDeviationBps: uint16 }]
}

side 0 is BUY (buy base, pay quote), 1 is SELL (sell base, receive quote).

Orders reaching the matcher have already passed validation (docs/PROTOCOL.md §6): decrypted, commitment matches, signature valid, right epoch, validity window covers the settlement window, market allowlisted, nonce unused, funds and allowance sufficient, not cancelled. baseAmount > 0, limitPrice > 0, minFillBase <= baseAmount.

Preconditions. Violating any of them is an input error; the matcher refuses the whole input rather than guessing:

• commitments are unique across all orders of the epoch
• market ids are unique within markets
• every order (including one for an unknown market) has side in {0, 1}, baseAmount > 0, limitPrice > 0 and minFillBase <= baseAmount
• every maxOracleDeviationBps is below BPS

Orders are validated first. Orders whose marketId is not in markets are then ignored.

Each market is matched independently.

3. Oracle bounds#

If oraclePrice == 0 the market does not trade this epoch.

For each order let D = market.maxOracleDeviationBps and

d = D                                   if order.maxOracleDeviationBps == 0
d = min(order.maxOracleDeviationBps, D) otherwise

The order's effective limit is its signed limit clamped to the band it accepts:

BUY : eff = min(limitPrice, floor(oraclePrice * (BPS + d) / BPS))
SELL: eff = max(limitPrice,  ceil(oraclePrice * (BPS - d) / BPS))

Effective limits decide eligibility. A buy never pays more than eff; a sell never receives less than eff. A consequence (proved in §8) is that the clearing price always lies inside the market band, which is what the settlement contract checks.

4. Clearing price#

Repeat the following over the set of active orders (initially all orders of the market).

1. If there is no active buy or no active sell, the market does not trade.
2. Candidates are the distinct effective limits of active orders.
3. For a price p:
   • demand Dm(p) = sum of baseAmount over active buys with eff >= p
   • supply Sp(p) = sum of baseAmount over active sells with eff <= p
   • volume V(p) = min(Dm(p), Sp(p))
4. Vmax = maximum of V over the candidates. If Vmax == 0 the market does not trade.
5. lo = smallest candidate with V == Vmax, hi = largest candidate with V == Vmax.
6. Clearing price P = clamp(oraclePrice, lo, hi): the oracle price if it lies in [lo, hi], otherwise the nearer end.

V is a step function that only changes at candidates, demand is non-increasing and supply non-decreasing, so the set of volume-maximising prices is exactly the interval [lo, hi] and V(P) == Vmax for the chosen P even when P is not itself a candidate. The clamp is the unique price in that interval closest to the oracle, so no further tie-break exists.

5. Allocation#

At price P the eligible buys are active buys with eff >= P; eligible sells are active sells with eff <= P. Each side receives exactly Vmax base in total, allocated as follows.

Sort the side by signed limitPrice, most aggressive first (buys: highest first; sells: lowest first). Orders with equal limitPrice form a tier. Walk tiers in order with remaining = Vmax:

• If the tier's total T <= remaining: every order in the tier is filled in full; remaining -= T.
• Otherwise, if remaining > 0, the tier is filled pro-rata:
  • alloc_i = floor(remaining * baseAmount_i / T)
  • rem_i = (remaining * baseAmount_i) mod T
  • the remaining - sum(alloc_i) leftover units go one each to the orders with the largest rem_i; ties are broken by ascending commitment (compared as a 256-bit unsigned integer)
  • remaining = 0
• Later tiers get nothing.

There is no time priority anywhere. The commitment is a salted hash, so the leftover tie-break (worth at most one raw unit per order) cannot be raced.

6. Minimum-fill constraints#

After allocating, an order is violated if it received a non-zero allocation below its own minimum:

required = baseAmount   if !allowPartialFill   (fill-or-kill)
required = minFillBase  otherwise
violated = 0 < alloc < required

An order with zero allocation is never violated; it is simply unfilled.

If any order is violated, remove the single violated order with the largest commitment from the active set and restart from §4. The active set strictly shrinks, so this terminates. If no order is violated the allocation is final.

This is a deterministic heuristic, not a global optimum: finding the volume-maximising subset under all-or-nothing constraints is a knapsack problem. The rule is fixed so every implementation drops the same orders.

7. Amounts, rounding and dust#

For each order with alloc > 0 the fill is:

baseFilled  = alloc
quoteAmount = ceil(alloc * P / 1e18)    for a BUY  (what the buyer pays)
quoteAmount = floor(alloc * P / 1e18)   for a SELL (what the seller receives)

Base is conserved exactly: buyers receive in total what sellers deliver. Quote paid by buyers is at least quote received by sellers; the difference is at most one raw quote unit per fill pair and is recorded in KasumiSettlement.dust. It is rounding residue, published onchain, and sweepable only by the owner. It is the only value the contract ever retains in v1.

Limits are enforced on the price, not on rounded amounts: a buy fills only if P <= limitPrice, a sell only if P >= limitPrice. A buyer can therefore pay up to one raw quote unit more than alloc * P / 1e18 exactly, and never more than ceil(baseAmount * limitPrice / 1e18) in total.

8. Why the price is always inside the market band#

Every buy has eff <= floor(oracle * (BPS + D) / BPS) and every sell has eff >= ceil(oracle * (BPS - D) / BPS). lo is the effective limit of some sell (volume can only rise at a sell limit when moving up) and hi is the effective limit of some buy (volume can only fall after a buy limit). So lowerBand <= lo <= P <= hi <= upperBand.

9. Output and hashes#

MarketResult { marketId, clearingPrice, matchedBase (= Vmax, up to 256 bits), fills[] , marketHash }
MatchResult  { epochId, markets[], resultHash }

• fills are ordered by ascending commitment.
• markets contains only markets with at least one fill, ordered by ascending marketId.

Hashes are keccak256 over the concatenation of 32-byte big-endian words (u256(x)), no length prefixes:

fillHash   = keccak256( commitment ‖ u256(baseFilled) ‖ u256(quoteAmount) )
marketHash = keccak256( marketId ‖ u256(clearingPrice) ‖ u256(matchedBase) ‖ u256(fills.length)
                        ‖ fillHash_0 ‖ … ‖ fillHash_{n-1} )
resultHash = keccak256( u256(epochId) ‖ u256(markets.length) ‖ marketHash_0 ‖ … )

An epoch with no fills has resultHash = keccak256(u256(epochId) ‖ u256(0)).

The matcher publishes every marketHash with KasumiEpochManager.postMatch(epochId, marketIds, marketHashes) before settling; the contract derives and stores resultHash from them. KasumiSettlement.settleMarket recomputes the marketHash from the transfers it actually performed and reverts unless it equals the published hash for that market. The epoch is SETTLED once every published market has settled. The matcher can replace or withdraw the published hash of an unsettled market with amendMarket, which is logged; resultHash keeps the original publication.

10. Fixture format#

fixtures/matching.json is an array of { name, input, expected }. All integers are decimal strings; bytes32 values are 0x-prefixed lowercase hex. input is §2, expected is §9. Regenerate with pnpm fixtures (TypeScript reference); the Rust test suite must then pass unchanged.