Oversized epoch-approval bitmask passes verification and triggers quadratic Bitmask.Len CPU exhaustion

## Details
NextEpochApprovals.NodeIDs is a byte slice decoded from remote block proposals (blockDeserializer.DeserializeBlock -> RawBlock.UnmarshalCanoto -> SimplexEpochInfo -> NextEpochApprovals). It is interpreted as a bitmask of approving validator indices, but no code bounds its length to ceil(len(validators)/8):

1. The canoto decoder accepts NodeIDs up to the network message limit (~2 MiB => ~16.7 million bits).
2. verifyNextEpochApprovalsSignature/aggregatePubKeysForBitmask only iterate over i < len(validators), so bits set at higher indices are ignored by signature verification. A malicious round leader during an epoch transition (collecting-approvals state) can therefore publish a block whose bitmask contains its own valid approval bit (and any bits inherited from the parent) plus megabytes of junk high bits; the aggregate BLS signature still verifies, the superset and quorum checks pass, and the digest comparison uses the proposed NodeIDs verbatim, so the block is accepted, notarized and propagated.
3. avalanchego.Bitmask.Len() is quadratic: it right-shifts the whole big.Int one bit per iteration. computeNewApproverSignaturesAndSigners calls oldApprovingNodes.Len() eagerly (as a zap.Int argument, evaluated even when debug logging is disabled) on the parent block's bitmask every time a node builds the next collecting-approvals block. With an 8-16 million bit bitmask this is roughly n^2/128 ~= 5*10^11 - 2*10^12 word operations, i.e. minutes to tens of minutes of CPU per block-build attempt.

Because honest builders clone the parent bitmask and carry the junk bits forward (the superset rule forbids dropping bits), every subsequent block build during the epoch transition re-triggers the quadratic scan, effectively stalling block production and preventing the epoch transition from completing. Additionally, the attacker can propose a later block that drops one junk bit, forcing every verifier to execute the quadratic Len() in areNextEpochApprovalsSignersSupersetOfApprovalsOfPrevBlock before the proposal is rejected, burning CPU on all honest nodes repeatedly.

The root cause is the missing canonicality/size validation on the decoded bitmask (bits beyond the validator range should make verification fail, and the byte length should be capped), combined with a super-linear popcount implementation on attacker-sized input.

## Evidence
1. [msm/msm.go:1120–1135](https://github.com/ava-labs/Simplex/blob/main/msm/msm.go#L1120-L1135)
aggregatePubKeysForBitmask converts the attacker-controlled NextEpochApprovals.NodeIDs bytes into a bitmask and only inspects bit indices i < len(validators). Any bits set at indices >= len(validators) are silently ignored, so an aggregate signature that covers only the in-range signers still verifies even when the bitmask carries megabytes of extra set bits. Neither this function nor its callers bound len(nodeIDsBitmask) to ceil(len(validators)/8).
2. [msm/msm.go:1663–1669](https://github.com/ava-labs/Simplex/blob/main/msm/msm.go#L1663-L1669)
computeNewApproverSignaturesAndSigners eagerly evaluates oldApprovingNodes.Len() as a zap.Int argument (evaluated regardless of log level). oldApprovingNodes is built from the parent block's NextEpochApprovals.NodeIDs, so once one poisoned block is notarized, every honest node that builds the next collecting-approvals block executes the quadratic Len() over the full multi-million-bit bitmask.
3. [avalanchego/misc.go:92–105](https://github.com/ava-labs/Simplex/blob/main/avalanchego/misc.go#L92-L105)
Bitmask.Len() counts set bits by repeatedly reading bit 0 and right-shifting the entire big.Int by one. For an n-bit value this is n iterations each costing O(n/64) word operations, i.e. O(n^2/64) total. A 1-2 MiB NodeIDs field (8-16 million bits) costs on the order of 10^11-10^12 word operations, i.e. minutes to tens of minutes of CPU per invocation.
4. [msm/msm.go:1748–1764](https://github.com/ava-labs/Simplex/blob/main/msm/msm.go#L1748-L1764)
areNextEpochApprovalsSignersSupersetOfApprovalsOfPrevBlock computes prevSigners.Difference(nextSigners) and then prevSigners.Len(). Once the parent block carries the poisoned bitmask, an attacker who is leader again can propose a follow-up block whose bitmask drops one junk bit; every verifier then runs the quadratic Len() over the millions of remaining bits before rejecting the block, burning CPU on all honest nodes even though the proposal fails.
5. [msm/msm.go:1050–1080](https://github.com/ava-labs/Simplex/blob/main/msm/msm.go#L1050-L1080)
verifyCollectingApprovalsBlock constructs the expected block using the proposed NodeIDs/Signature verbatim (computeSimplexEpochInfoForCollectingApprovalsBlock with newApprovals.NodeIDs), so the digest comparison in verifyAgainstExpected imposes no constraint on the bitmask contents. The only semantic checks are the aggregate-signature check (which ignores out-of-range bits), the superset check, and the quorum check via SelectSubset (which also caps at len(validators)). A block with arbitrary high junk bits therefore verifies successfully.
6. [msm/encoding.canoto.go:1871–1881](https://github.com/ava-labs/Simplex/blob/main/msm/encoding.canoto.go#L1871-L1881)
The generated decoder for NextEpochApprovals reads the NodeIDs bytes field with no length restriction other than the enclosing message size, so a remote block proposal can carry a NodeIDs bitmask of up to the network message limit (~2 MiB, i.e. ~16.7 million bits).
7. [msm/encoding.go:333–337](https://github.com/ava-labs/Simplex/blob/main/msm/encoding.go#L333-L337)
NextEpochApprovals declares NodeIDs as an unbounded []byte; the msm package provides no wrapper validation that caps the bitmask to the validator-set size before it is interpreted as validator indices.
8. [adapters.go:250–269](https://github.com/ava-labs/Simplex/blob/main/adapters.go#L250-L269)
blockDeserializer.DeserializeBlock is the untrusted network entry point: raw block bytes received from a peer are unmarshaled into RawBlock/StateMachineMetadata (including SimplexEpochInfo.NextEpochApprovals) and handed to the consensus engine for verification, establishing remote reachability of the decode path.

## Impact
Every honest node that attempts to build a collecting-approvals block on top of the poisoned block spends minutes to tens of minutes of CPU in Bitmask.Len() (no context cancellation), and verifiers can be forced into the same quadratic scan via a follow-up proposal that drops a junk bit. Block production during the epoch transition stalls and the transition cannot complete in a timely manner, halting consensus liveness. No confidentiality or integrity impact: the junk bits do not change quorum computation or the accepted signer set.

## Reproduction steps
1. The attacker must be a validator in the current epoch and be the round leader while an epoch transition is in progress (collecting-approvals state). Leadership rotates deterministically, so a validator becomes leader within a few rounds; the transition state occurs whenever the validator set changes on the P-chain (which a staking validator can itself induce). The attacker crafts one block whose NextEpochApprovals.NodeIDs contains valid approval bits plus megabytes of set bits beyond the validator range; it passes all verification and poisons every subsequent build in the transition. Delivery is a normal consensus block message over the network.

## Recommended fix
1. Verification treats NextEpochApprovals.NodeIDs as a bitmask over validator indices but never rejects bitmasks whose byte length exceeds ceil(len(validators)/8) or that have bits set at indices >= len(validators); such bitmasks pass signature, superset, digest, and quorum checks and become part of the notarized chain. Fix criteria: A proposed block whose NextEpochApprovals.NodeIDs is longer than the minimal encoding for the validator-set size, or which has any bit set at an index outside [0, len(validators)), must fail verification in verifyCollectingApprovalsBlock before any expensive processing. Verify that the attack block from the assessment is rejected and that legitimately built blocks (bitmask produced by newApprovingNodes.Bytes()) still verify.
2. avalanchego.Bitmask.Len() counts set bits with a bit-by-bit shift loop, giving O(n^2) cost on the bit-length of its input; it is invoked eagerly (including as a log-field argument in computeNewApproverSignaturesAndSigners) on data whose size is influenced by remote peers. Fix criteria: Population count over a b-byte bitmask must run in O(b) (e.g., word-wise popcount over big.Int.Bits()), and hot paths must not evaluate expensive expressions solely for disabled log statements. Verify that Len() on a 2 MiB all-ones bitmask completes in milliseconds.

---
**Severity:** HIGH
**Status:** Open
**Category:** Algorithmic complexity
**CWE:** [CWE-407](https://cwe.mitre.org/data/definitions/407.html)
**Repository:** ava-labs/Simplex
**Branch:** main
**Date created:** 2026-08-21

---

Start at adapters.go:250-269 to trace block deserialization, then read msm/encoding.go, msm/encoding.canoto.go, and the verification paths in msm/msm.go around the cited ranges. Confirm how oversized NodeIDs reach signature, quorum, and superset checks, and inspect avalanchego/misc.go for Bitmask.Len(). Done means invalid high bits are rejected before expensive work, valid blocks still verify, and Len() handles a 2 MiB mask in linear time.

Written by the indexing model from the issue text.