Exponential complexity of weight calculation functions in multiple imported Substrate 2.0.0 pallets allows for Denial of Service attack, potentially stalling the blockchain

Summary

The weight calculation functions of multiple extrinsics in Substrate had exponential complexity because they perform two calls to the get_dispatch_info() function. An attacker can abuse this exponential complexity of O(2^n) to craft a nested extrinsic (that is still below the MAX_EXTRINSIC_DEPTH of 256) for which the weight computation is not feasible in limited time and thus cause a validator to miss its slot.

The following extrinsics that are used by Joystream are affected:

fn batch and fn as_derivative (in frame/utility/src/lib.rs)
fn sudo and fn sudo_as (in frame/sudo/src/lib.rs)

The currently used Substrate version (2.0.0) is vulnerable to this attack since multiple extrinsics there had exponential-complexity weight-calculation functions. Thus, to mitigate this vulnerability in the extrinsics imported from Substrate, a Substrate update to a version that includes the fix is necessary.

Issue Description

The root cause of the issue is that the batch extrinsic performs multiple nested calls to get_dispatch_info in its weight calculation function. The fn batch extrinsic has the following function that is executed upon dispatch:

        #[weight = (
            calls.iter()
                .map(|call| call.get_dispatch_info().weight)
                .fold(0, |total: Weight, weight: Weight| total.saturating_add(weight))
                .saturating_add(T::WeightInfo::batch(calls.len() as u32)),
            {
                let all_operational = calls.iter()
                    .map(|call| call.get_dispatch_info().class)
                    .all(|class| class == DispatchClass::Operational);
                if all_operational {
                    DispatchClass::Operational
                } else {
                    DispatchClass::Normal
                }
            },
        )]
        fn batch(origin, calls: Vec<::Call>) {

Note that this dispatch function performs two recursive calls to get_dispatch_info. Nesting batch calls thus have an exponential complexity of O(2^n), where n is the nesting depth. As a result, nesting 40 batch calls already result in a call tree with 2^40 = 1099511627776 (>1099 billion) leaves, that is, in more than 2^40 calls to the get_dispatch_function. This can be illustrated by the following call tree for a chain of nested batch calls (batch(..,batch(..,batch,...)))

                                            batch.get_dispatch_info
                                              /                   \
                                             /                     \
                                batch.get_dispatch_info      batch.get_dispatch_info
                                /                  \                 /           \                        
            batch.get_dispatch_info  batch.get_dispatch_info       [...]        [...]

where each layer in the tree doubles the amount of calls to dispatch_info, resulting in 2^n layers.

Risk

An attacker can easily abuse the exponential complexity and craft a nested extrinsic and for which the weight calculation is infeasible. By gossiping this extrinsic, an attacker could cause validators to miss their slots and fail at block production, potentially halting block production.

Mitigation

Instead of perform two calls to get_dispatch_info only perform one call and save the result in a temporary variable. This prevents the exponential complexity of the weight calculation function. An example for this would be the weight calculation function of the fn proxy extrinsic from the Substrate repository:

From substrate/frame/proxy/src/lib.rs:

        #[weight = {
                        
            let di = call.get_dispatch_info();
                        
            (T::WeightInfo::proxy(T::MaxProxies::get().into())
                .saturating_add(di.weight)
                 // AccountData for inner call origin accountdata.
                .saturating_add(T::DbWeight::get().reads_writes(1, 1)),
            di.class)
        }]
        fn proxy(origin,

Joystream / audits