Denial of Service via Quadratic-Time Signer Verification in verifySigningOperatorsWhitelisted

gistfile1.txt

Denial of Service via Quadratic-Time Signer Verification in verifySigningOperatorsWhitelisted

Executive Summary

The verifySigningOperatorsWhitelisted function in OperatorVerifierLib.sol contains algorithmic complexity issues that can cause out-of-gas reverts when processing task responses on source chains. The function performs quadratic-time operations and numerous external calls that scale poorly with operator set size, enabling semi-trusted operators to induce denial-of-service conditions by manipulating the signer/non-signer ratio.

Vulnerability Details

Location

File: OperatorVerifierLib.sol
Function: verifySigningOperatorsWhitelisted (lines 34-114)
Severity: Medium

Root Cause Analysis

The vulnerable function reconstructs the set of signers for each quorum through a series of inefficient operations:

1. Per-Quorum External Call Overhead (O(Q × R))

For each quorum in task.quorumNumbers, the function iterates through all non-signer pubkeys and makes an external call:

solidity


for (uint256 j = 0; j < nonSignerStakesAndSignature.nonSignerPubkeys.length; ++j) {
    bytes32 pubkeyHash =
        BN254.hashG1Point(nonSignerStakesAndSignature.nonSignerPubkeys[j]);
    uint256 quorumBitmap = registryCoordinator.getQuorumBitmapAtBlockNumberByIndex(
        pubkeyHash,
        task.taskCreatedBlock,
        nonSignerStakesAndSignature.nonSignerQuorumBitmapIndices[j]
    );
    // ...
}
This results in Q × R external calls where:

Q = number of quorums
R = number of non-signer pubkeys
Each external call to getQuorumBitmapAtBlockNumberByIndex incurs base gas costs (~2600 for cold storage access) plus execution overhead.

2. Quadratic Membership Check (O(N × M))

For each operator in the quorum, the code performs a linear scan of the non-signer array:

solidity


for (uint256 k = 0; k < operatorIds.length; ++k) {
    bytes32 operatorId = operatorIds[k];

    bool isNonSigner = false;
    for (uint256 m = 0; m < nonSignerCount; ++m) {
        if (nonSignerIds[m] == operatorId) {
            isNonSigner = true;
            break;
        }
    }
    // ...
}
This nested loop yields O(N × M) comparisons per quorum where:

N = total operators in the quorum
M = non-signers in that quorum
3. Additional External Calls Per Signer

For each identified signer, two more external calls occur:

solidity


address operator = blsApkRegistry.getOperatorFromPubkeyHash(operatorId);
// ...
if (!registry.isOperatorWhitelisted(operator)) {
    revert OperatorNotWhitelisted();
}
Gas Cost Model

The total gas consumption can be approximated as:

code


Total Gas ≈ Q × [
    R × (gas_per_bitmap_call) +           // External calls for bitmap
    N × M × (gas_per_comparison) +         // Membership checks
    S × (gas_per_address_lookup +          // getOperatorFromPubkeyHash
         gas_per_whitelist_check)          // isOperatorWhitelisted
]
Where:

Q = number of quorums
R = total non-signers provided
N = operators per quorum
M = non-signers per quorum
S = signers per quorum (N - M)
Why Destination Chains Are Unaffected

The function exits early on destination chains:

solidity


if (address(blsApkRegistry) == address(0) || address(indexRegistry) == address(0)) {
    return;
}
Since EigenLayer registries are not deployed on destination chains, the expensive verification is skipped entirely.

Exploitation Scenarios

Scenario 1: Direct Liveness DoS on Task Response

Context: A source chain deployment with a large operator set (e.g., 1000+ operators per quorum).

Attack Execution:

Semi-trusted operators observe a pending task requiring attestation.
They coordinate to ensure only the minimum number of signers (just above quorumThresholdPercentage) produce valid BLS signatures.
The remaining operators abstain, becoming non-signers.
When the trusted task generator calls respondToTask, the NonSignerStakesAndSignature contains a large non-signer set.
verifySigningOperatorsWhitelisted attempts to process:
Multiple external calls per non-signer per quorum
Quadratic membership checks across all operators
Additional lookups for each signer
Gas consumption exceeds the block limit, causing revert.
Result: The task cannot be finalized within the response window. Attestations are blocked.

Preconditions:

Source-chain deployment with active registryCoordinator, blsApkRegistry, and indexRegistry
Large operator set per quorum
Moderate quorumThresholdPercentage (allowing minimal signer sets)
Semi-trusted operators willing to abstain
Valid aggregate BLS signature from the minimal signer set
Scenario 2: Multi-Quorum Amplification

Context: A task spans multiple quorums (e.g., 3-5 quorums with 500+ operators each).

Attack Execution:

The attacker follows the same approach as Scenario 1 but targets a task with multiple quorums.
The outer loop in verifySigningOperatorsWhitelisted repeats the entire verification process for each quorum:
solidity


for (uint256 i = 0; i < task.quorumNumbers.length; ++i) {
    uint8 quorumNumber = uint8(task.quorumNumbers[i]);
    // All expensive operations repeated
}
Gas costs multiply by the number of quorums.
Result: Even moderately-sized operator sets become prohibitive when multiple quorums are involved.

Preconditions:

All preconditions from Scenario 1
Task includes multiple quorums in task.quorumNumbers
Impact Assessment

Availability Impact

Task responses cannot be submitted when operator sets are large and non-signer ratios are high.
Attestation creation is blocked within response windows.
Core protocol functionality becomes unavailable under specific conditions.
Financial Impact

No direct loss of principal funds.
No permanent freezing of assets.
Potential indirect costs from failed task responses and delayed attestations.
Attack Cost

Requires coordination among semi-trusted operators.
No direct financial cost to attackers (they simply abstain from signing).
Semi-trusted operators may face reputation or slashing risks depending on protocol rules (not evident in provided code).
Suggested Remediation Approaches

Approach 1: Precompute Non-Signer Bitmaps Outside Per-Quorum Loop

Problem Addressed: Redundant external calls for the same non-signer across multiple quorums.

Implementation:

solidity


// Compute quorum bitmaps once, outside the per-quorum loop
bytes32[] memory nonSignerPubkeyHashes = 
    new bytes32[](nonSignerStakesAndSignature.nonSignerPubkeys.length);
uint256[] memory nonSignerQuorumBitmaps = 
    new uint256[](nonSignerStakesAndSignature.nonSignerPubkeys.length);

for (uint256 j = 0; j < nonSignerStakesAndSignature.nonSignerPubkeys.length; ++j) {
    nonSignerPubkeyHashes[j] = 
        BN254.hashG1Point(nonSignerStakesAndSignature.nonSignerPubkeys[j]);
    nonSignerQuorumBitmaps[j] = registryCoordinator.getQuorumBitmapAtBlockNumberByIndex(
        nonSignerPubkeyHashes[j],
        task.taskCreatedBlock,
        nonSignerStakesAndSignature.nonSignerQuorumBitmapIndices[j]
    );
}

// Then use cached bitmaps in per-quorum loop
for (uint256 i = 0; i < task.quorumNumbers.length; ++i) {
    uint8 quorumNumber = uint8(task.quorumNumbers[i]);
    // Filter using cached nonSignerQuorumBitmaps[j] and BitmapUtils.isSet
}
Complexity Reduction: O(Q × R) → O(R) external calls.

Approach 2: Sort and Binary Search for Membership

Problem Addressed: Quadratic membership checks.

Implementation:

solidity


// Sort nonSignerIds after population
// Use a sorting algorithm or assume sorted input
sortBytes32Array(nonSignerIds, nonSignerCount);

// Replace linear search with binary search
for (uint256 k = 0; k < operatorIds.length; ++k) {
    bytes32 operatorId = operatorIds[k];
    bool isNonSigner = binarySearch(nonSignerIds, nonSignerCount, operatorId);
    // ...
}
Complexity Reduction: O(N × M) → O(N log M).

Approach 3: Two-Pointer Merge (If Both Arrays Are Sorted)

Problem Addressed: Membership checks when both operator lists and non-signer lists can be sorted.

Implementation:

solidity


// Assuming both operatorIds and nonSignerIds are sorted
uint256 nonSignerPtr = 0;
for (uint256 k = 0; k < operatorIds.length; ++k) {
    bytes32 operatorId = operatorIds[k];
    
    // Advance non-signer pointer while less than current operator
    while (nonSignerPtr < nonSignerCount && nonSignerIds[nonSignerPtr] < operatorId) {
        ++nonSignerPtr;
    }
    
    bool isNonSigner = (nonSignerPtr < nonSignerCount && nonSignerIds[nonSignerPtr] == operatorId);
    // ...
}
Complexity Reduction: O(N × M) → O(N + M).

Approach 4: Cache Operator Address Lookups

Problem Addressed: Repeated getOperatorFromPubkeyHash calls for the same operator across quorums.

Implementation:

solidity


// Build a mapping of operatorId -> address before per-quorum loops
// (May require refactoring to gather all unique operator IDs first)
mapping(bytes32 => address) memory operatorAddressCache;
// Populate cache, then use cached values in inner loops
Trade-off: Increases memory usage but reduces external calls.

Open Questions for Review

Sorting Guarantees: Does indexRegistry.getOperatorListAtBlockNumber return operator IDs in any deterministic order? If sorted, the two-pointer merge approach becomes viable without additional sorting overhead.
Non-Signer Input Ordering: Are nonSignerPubkeys and nonSignerQuorumBitmapIndices required to be in any specific order by the calling code? If so, this could be leveraged for optimization.
Maximum Operator Set Size: What is the expected maximum number of operators per quorum? This determines whether the current implementation can ever succeed or if it will always exceed gas limits at scale.
Semi-Trusted Operator Penalties: Are there off-chain or on-chain penalties for operators who consistently abstain from signing? The effectiveness of this attack depends on whether abstention has consequences.
Alternative Verification Approaches: Could the whitelist check be performed differently—for example, by verifying only the aggregate signature and deferring individual operator whitelist checks to a fraud-proof mechanism?
Block Gas Limit Considerations: What is the target chain's block gas limit, and what operator set sizes are safe given current implementation?
Conclusion

The verifySigningOperatorsWhitelisted function contains algorithmic inefficiencies that create a denial-of-service vector on source chains. The quadratic-time membership checks and redundant external calls scale poorly with operator set size, allowing semi-trusted operators to block task responses by manipulating the signer/non-signer ratio.

The recommended fixes involve:

Precomputing non-signer bitmaps once (not per quorum)
Replacing linear membership checks with sorted binary search or two-pointer merge
Caching operator address lookups across quorums
These changes reduce complexity from O(Q × R + Q × N × M) to approximately O(R + Q × (N + M)) or O(R + Q × N log M), making the function viable for large operator sets.

★ Insight ─────────────────────────────────────
The key question is whether this is a practical DoS vector or a theoretical algorithmic concern. The answer depends on realistic operator set
sizes, gas costs, and whether the "attack" (operators abstaining from signing) is actually penalized by the protocol.
─────────────────────────────────────────────────

Issue 1: Per-Quorum External Calls — O(Q × R)

Report claims: getQuorumBitmapAtBlockNumberByIndex is called Q × R times (once per non-signer per quorum).

Actual code (lines 55-82): Confirmed. The outer loop iterates quorums (line 55), the inner loop iterates all non-signer pubkeys (line 67), and
each iteration calls registryCoordinator.getQuorumBitmapAtBlockNumberByIndex (line 71). With Q quorums and R non-signers, this is Q × R external
calls.

Verdict: Valid — the pattern exists. But is it practical?

Issue 2: Quadratic Membership Checks — O(N × M)

Report claims: Nested loops at lines 85-95 produce O(N × M) comparisons.

Actual code: Line 85 iterates all operator IDs in the quorum (N), and line 90 does a linear scan of nonSignerIds (M) for each. This is indeed O(N
× M) per quorum.

Verdict: Valid — the pattern exists.

Issue 3: Per-Signer External Calls

Report claims: Two external calls per signer (getOperatorFromPubkeyHash + isOperatorWhitelisted).

Actual code (lines 103, 111): Confirmed. For every operator that's NOT a non-signer, two external calls are made.

Verdict: Valid — the pattern exists.

Practical Severity Assessment

Now the critical question: is this exploitable in practice?

Newton's operator set size: Newton is an EigenLayer AVS. Current EigenLayer AVS operator sets are typically 10-50 operators, not 1000+. Even
EigenDA, the largest AVS, has ~300 operators.

Gas cost estimation for realistic sizes:

• 30 operators, 1 quorum, 10 non-signers: ~30 × 10 = 300 comparisons + ~10 external calls + ~20 signer lookups. Roughly ~500K gas. Well within
  block limits.
• 100 operators, 1 quorum, 50 non-signers: ~100 × 50 = 5000 comparisons + ~50 external calls + ~50 signer lookups. Roughly ~2M gas. Still within
  Ethereum's 30M block limit.
• 500 operators, 3 quorums, 400 non-signers: ~3 × 500 × 400 = 600K comparisons + 3 × 400 = 1200 external calls. This could approach ~15-20M gas.
  Getting close to block limit.

Attack requires operator coordination: The "attacker" needs enough operators to abstain from signing to create a large non-signer list while still
meeting quorum. This requires significant stake coordination.

My assessment: Low severity — the algorithmic inefficiency is real but not practically exploitable at current or near-future Newton operator set
sizes (10-50 operators). It becomes a concern only at 500+ operators with multi-quorum tasks. This is a scalability improvement, not a security
vulnerability.

Proposed Fixes Evaluation

Fix 1 (precompute bitmaps): Valid optimization. Moves bitmap lookups outside the per-quorum loop. Reduces O(Q × R) to O(R) external calls. No
downside.

Fix 2/3 (binary search / two-pointer): Valid optimization for the O(N × M) inner loop. However, requires sorting arrays, and
indexRegistry.getOperatorListAtBlockNumber does NOT guarantee sorted output. Binary search would need an explicit sort step. The two-pointer
approach is cleaner if we sort first.

Fix 4 (cache operator addresses): Solidity doesn't have mapping in memory. Would need a bytes32[] + address[] pair. Adds complexity for marginal
benefit since each operator is only looked up once per quorum.

Fix 1 is the most impactful and lowest-risk optimization. Fixes 2/3 are nice-to-have but add complexity. Fix 4 is not practical in Solidity.

Phase 7: Report

┌─────────────────────────────────────┬───────────────────────────┬──────────────────────────────────────────────────────────────────────────┐
│ Claimed Vulnerability │ Verdict │ Evidence │
├─────────────────────────────────────┼───────────────────────────┼──────────────────────────────────────────────────────────────────────────┤
│ O(Q × R) external calls per quorum │ Partially valid │ Pattern exists (lines 55-82) but not exploitable at current operator set │
│ │ │ sizes (10-50) │
├─────────────────────────────────────┼───────────────────────────┼──────────────────────────────────────────────────────────────────────────┤
│ O(N × M) quadratic membership │ Partially valid │ Pattern exists (lines 85-95) but manageable at current scale │
│ checks │ │ │
├─────────────────────────────────────┼───────────────────────────┼──────────────────────────────────────────────────────────────────────────┤
│ DoS via operator abstention at │ Invalid at current scale │ Newton has ~10-50 operators per quorum. Attack requires 500+ operators │
│ 1000+ operators │ │ with multi-quorum coordination │
├─────────────────────────────────────┼───────────────────────────┼──────────────────────────────────────────────────────────────────────────┤
│ Medium severity │ Downgrade to │ Scalability concern, not a current security vulnerability │
│ │ Low/Informational │ │
└─────────────────────────────────────┴───────────────────────────┴──────────────────────────────────────────────────────────────────────────┘

No fix implemented. The algorithmic patterns are real but not exploitable at Newton's current or near-future operator set sizes. The report
describes a scalability improvement that would become relevant at 500+ operators.

Recommendation: When Newton approaches 200+ operators, implement Fix 1 (precompute bitmaps outside the per-quorum loop) as the highest-impact,
lowest-risk optimization. File a ticket for future work rather than fixing now.

No ABI-breaking changes. No lessons recorded — this is a scaling concern, not a security pattern to prevent.