Multisig::execute weight annotation is O(depth × bytes), evaluated before fee/weight rejection

[n13]

Multisig::execute's weight annotation walks the whole call subtree at every nesting level, so a chain of nested execute calls costs O(depth × bytes) of encode-walking during transaction validation — before any weight or fee check can reject it.

The code

pallets/multisig/src/lib.rs:1092-1095:

<T as Config>::WeightInfo::execute(
    T::MaxCallSize::get().max(call.encoded_size() as u32),
)
.saturating_add(call.get_dispatch_info().call_weight)

Two things compound here:

• call.encoded_size() is O(bytes of the whole remaining subtree) — Encode::encoded_size runs a full encode_to into a size tracker.
• call.get_dispatch_info() recurses into the inner call, and if that inner call is another Multisig::execute, this same expression is evaluated again over its subtree.

So for k nested execute wrappers around a payload of B bytes, the annotation performs roughly k × B bytes of walking.

Why it is reachable before any rejection

frame_executive's validate_transaction computes the dispatch info immediately after the signature check and before the transaction extensions run:

let uxt = <Block::Extrinsic as codec::DecodeLimit>::decode_all_with_depth_limit(
    MAX_EXTRINSIC_DEPTH,
    &mut &encoded[..],
)?;
let xt = uxt.check(&Default::default())?;
let dispatch_info = xt.get_dispatch_info();

CheckWeight and ChargeTransactionPayment both run after that point, so the walk happens even when the transaction is ultimately rejected for exhausting resources or for insufficient balance — in which case no fee is charged at all.

Worst case

Each execute wrapper costs 38 encoded bytes (pallet index + call index + AccountId32 + u32 + Box) and exactly one codec depth level, since WrapperTypeDecode for Box calls descend_ref while derived enums do not. So ~255 wrappers fit under MAX_EXTRINSIC_DEPTH = 256 in under 10 KB, leaving essentially the whole RuntimeBlockLength normal budget (3.75 MB with the current 5 MB / 75% config) for the innermost payload, e.g. one large System::remark.

That is on the order of 255 × 3.75 MB of encode_to per validation, for a ~3.75 MB upload, repeatable, with no fee charged. The magnitude is derived from the constants rather than measured, but the code path is straightforward to confirm.

The transaction fails validation, so it is not gossiped onward — the attacker has to hit each node directly, which bounds this to a per-peer cost rather than a network-wide amplification. It still bypasses fee charging entirely.

Not equivalent to Utility::batch_all

batch_all's annotation calls weight_and_dispatch_class(&calls), which is O(number of children) per level and never O(bytes). Nesting batch_all gives O(depth) total work, not O(depth × bytes).

Suggested fix

Drop .max(call.encoded_size() as u32) from the annotation and declare WeightInfo::execute(T::MaxCallSize::get()). The recursion through get_dispatch_info() is inherent and fine — it is the per-level encoded_size() that makes this quadratic.

The .max(...) is there so that the post-dispatch bookkeeping_weight (sized by max(proposal.call.len(), call.encoded_size()) at :1135) can never exceed the declared weight. That can be preserved by clamping the body's call_size to MaxCallSize as well: a submitted call larger than MaxCallSize can never be byte-equal to a stored proposal (which is bounded by MaxCallSize), so it can only ever end in CallMismatch, and charging it execute(MaxCallSize) is correct.

Context

Found while reviewing a downstream merge of public main (through 308ba838). The pre-#661 annotation was two constants (WeightInfo::execute(MaxCallSize) + MaxInnerCallWeight), so this came in with the call-carrying execute interface.