Safe Preallocation for (most) Vec<T>

[preston-evans98]

Overview - Safe Preallocation

Currently, Zebra doesn't preallocate Vectors when deserializing, since blind preallocations present a DOS vector. Instead, it relies on maximum block and transaction size to limit allocations. This is inefficient.

We can mitigate the DOS potential and allow for preallocation as follows:

1. Define a new trait SafeAllocate, defining the maximum length a Vec<T: SafeAllocate> can sensibly reach for each implementing type
2. Create a specialized ZcashDeserialize implementation for SafeAllocaters.

pub trait SafeAllocate {
    const fn max_allocation() -> usize;
}

impl<T: ZcashDeserialize + SafeAllocate> ZcashDeserialize for Vec<T> {
    fn zcash_deserialize<R: io::Read>(mut reader: R) -> Result<Self, SerializationError> {
        let len = reader.read_compactsize()?;
        if len > T::max_allocation() {
            return Err(SerializationError::Parse(("Vector longer than max_allocation")));
        }
        let mut vec = Vec::with_capacity(len);
        for _ in 0..len {
            vec.push(T::zcash_deserialize(&mut reader)?);
        }
        Ok(vec)
    }
}

This allows us to pre-allocate for certain types without presenting a DOS vector, while retaining the flexibilty to use the current (lazy) allocation strategy for types that defy safe blind allocation.

Note that deserialization using this method is guaranteed to fail during the deserialization of the first malicious vector. However, Block messages contain nested Vec<T> types, and it is possible for a Byzantine message to cause improper allocations at each level of nesting before being discovered. This is why the potential spike for a Block message is much higher than for other message types.

Potential SafeAllocation Implementors

• Arc<Transaction> - Suggested allocation limit: 49_000. A Zcash block is capped at 2MB. Since transparent Txs are the smallest allowable transactions, and each transparent Tx requires at least one Input with a minimum serialized size of 41 bytes, an upper bound the length of a Vec<Arc<Transaction>> is 2MB / 41 Bytes < 49_000. Note that std::mem::size_of::<Arc<T>>() is 8, so the maximum memory wasted by a Byzantine Vec<Arc<Transaction>> is 49_000 * 8 Bytes < 400KB.

• transparent::Input - Suggested allocation limit: 49_000. A Zcash block is capped at 2MB. Each Input has a minimum serialized size of 41 bytes, so an upper bound the length of a Vec<transparent::Input> is 2MB / 41 Bytes < 49_000. With Inputs taking less than 80 bytes on the stack (36 for the Outpoint, 26 for the Script, and 4 for the sequence), the maximum memory wasted by a Byzantine Vec<transparent::Input> is 49_000 * 80 Bytes < 4MB.

• transparent::Output - Suggested allocation limit: 225_000. A Zcash block is capped at 2MB. Outputs have a minimum serialized size of 9 bytes, so an upper bound the length of a Vec<Arc<transparent::Output>> is 2MB / 9 Bytes < 225_000. With Outputs taking less than 40 bytes on the stack (call it 10 for the value, 26 for the Script, for a total of 36 ), the maximum memory wasted by a Byzantine Vec<Arc<transparent::Output>> is 225_000 * 40 Bytes = 9MB.

• MetaAddr - Suggested allocation limit: 1000. No fancy math required, since this limit is in the Addr message specification. Estimate a MetaAddr at a generous 100 bytes of stack space and you get max memory waste = 1000 * 100B = 100KB.

• block::Hash - Suggested allocation limit: 65536. We derive this limit as MAX_MESSAGE_SIZE / 32 = 2 * 1024 _ 1024 / 32. Since a block hash takes 32 bytes on the stack, the max waste here is MAX_MESSAGE_SIZE.

• InventoryHash - Suggested allocation limit: 50,000. This limit is the listed in the Inv message spec. Maximum waste: 50,000 * 32 B = 1.6 MB.

• block::CountedHeader - Suggested allocation limit: 2000. This limit is in the Headers message spec. Per the most recent spec, each Zcash header is less than 2kb. Maximum waste: 2000 * 2000 Bytes < 4MB

• u8 - Suggested allocation limit: MAX_MESSAGE_SIZE. Since a u8 takes 1 byte on the stack, the maximum waste here is MAX_MESSAGE_SIZE = 2MB.

Example attacks

Using all of these numbers, we calculate the total improper allocation caused by the worst-case instance of each Zcash Message as follows:

• Version: N.A.
• Verack: N.A.
• Ping: N.A.
• Pong: N.A.
• Reject: N.A.
• GetAddr: N.A.
• Addr: contains 1 Vec<MetaAddr> => 100KB (see above)
• Get locks: contains 1 Vec<block::Hash> => MAX_MESSAGE_SIZE (2MB)
• Inv: contains 1 Vec<InventoryHash> => 1.6 MB (see above)
• GetHeaders: contains 1 Vec<block::Hash> => MAX_MESSAGE_SIZE (2MB)
• Headers: contains 1 Vec<block::CountedHeader> => 4MB
• GetData: contains 1 Vec<InventoryHash> => 1.6 MB (see above)
• Block: The worst case block contains 1 Vec<Arc<Transaction>, 1 Vec<transparent::Output>, and 1 malicious Script(Vec<u8>) => 400KB + 9MB + 2MB = 11.4 MB.
• • Note that a dishonest vector is discovered during its own deserialization, so a malicious Vec<transparent::Input> would be discovered before the malicious Vec<transparent::Output> was allocated for. Since Outputs can waste more memory than Inputs, a smart attacker will choose to make only his Vec<transparent::Output> malicious.
• Tx: N.A.
• NotFound: contains 1 Vec<InventoryHash> => 1.6 MB (see above)
• Mempool: N.A.
• FilterLoad: contains 1 Filter(Vec<u8>) => 2MB
• FilterAdd: contains 1 Vec<u8> => 2MB
• FilterClear: N.A.

Alternatives

Do nothing. This is a fine option, since Zebra's networking stack is already fast!

Summary and Recommendations

With the SafeAllocate trait, we can allow preallocation for many Vector types without risking DOS attacks.

In the worst case, a malicious message can cause a short-lived spike in memory usage. The size of this spike depends on the max_allocation defined in SafeAllocate and the depth of nested Vec<T: SafeAllocate> types. Calculations of the maximum spike caused by each message type are included above. Based on these calculations, I recommend implementing SafeAllocate for all types listed in the "Potential SafeAllocate Implementors" section, with the possible exception of transparent::Input and transparent::Output.

If this recommendation is adopted , the worst case memory spike that a malicious peer can cause will be roughly 4MB, or roughly double that peer connection's usual memory consumption.

If transparent::Inputs and transparent::Outputs are included, the worst case spike rises to 11.5MB, or about six times a peer connection's usual memory consumption.

[teor2345]

Hi @preston-evans98, thanks for this suggestion, and working through these calculations.

In general, we've been working on the assumption that parsed data structures are slightly larger than their serialized equivalents. But I don't think we realised that malicious blocks could take up 6 times as much memory when deserialized.

Here's some further analysis of this issue:

Rust Vec over-allocation

Currently, Vec allocations can be up to 2x larger than their current length. That yields an overall 12x memory usage, or 24MB per 2MB malicious block.

https://github.com/rust-lang/rust/blob/ff6ee2a70218543f410e557f390e246131847572/library/alloc/src/raw_vec.rs#L415

Although:

Vec does not guarantee any particular growth strategy when reallocating when full

https://doc.rust-lang.org/std/vec/struct.Vec.html#guarantees

Preallocation would limit the maximum memory usage to 12MB per block.

Validation Pipeline Memory Usage

One of the reasons that Zebra is fast is that it processes many blocks in parallel. So memory usage issues can be quite serious. Zebra achieves this parallelism using a block validation pipeline: it deserialises blocks, then passes them through a number of validation stages. The underlying Arc<Block> data isn't dropped until after the block fails validation.

Inbound Block Gossip Service

The limit on this service is 600 blocks, which is far too high. We'll reduce that to 10 in #1881.

Sync Service

In general, a malicious node can place 500/50 = 10 malicious blocks in the sync pipeline due to request fanout. See #1881 for details.

Checkpoint Validation

The checkpoint verifier stores a queue of blocks, while awaiting the blocks at previous heights. To increase the cost of filling this queue, we check block difficulty in #1882.

Full Block Validation

It's hard to exploit full block validation, because it checks block difficulty before doing any other checks.

[teor2345]

Overall, I think this is a good change, but we should think about our test strategy.

If any of these new limits are too low, they might end up rejecting large blocks that other nodes accept. (Rejecting other large messages isn't as much of an issue, because most large messages aren't consensus-critical.)

So let's think about a test strategy that:

• constructs the smallest possible value of each type
• runs a proptest to confirm it's the smallest
• make sure the limit is correct for the smallest possible value

We can't really run proptests to find the largest possible blocks, because large proptests are very slow.