Zero Sized Types should not enable DoS

[matklad]

We currently special-case zst's when deserializing vectors:

borsh-rs/borsh/src/de/mod.rs

Lines 282 to 293 in b03a03c

	} else if size_of::<T>() == 0 {
	let mut result = vec![T::deserialize(buf)?];
	let p = result.as_mut_ptr();
	unsafe {
	forget(result);
	let len = len.try_into().map_err(|_| ErrorKind::InvalidInput)?;
	let result = Vec::from_raw_parts(p, len, len);
	Ok(result)
	}
	} else {
	// TODO(16): return capacity allocation when we can safely do that.

I think the reason to do that is to avoid DOS attacks. If we remove this restriction, then it's possible to hand-craft four-byte-len vec![(); !0], which will take a lot of time to deserialize. There are a couple of problems with this approach though:

• it is unsound (BorshDeserialize can cause UB by copying zero sized objects with no safe Copy impl #19)
• it doesn't' fully address the problem (we have the same issue for hash maps)

[preston-evans98]

You may have already considered this, but adding an unsafe marker trait would let us push this decision to the caller and fix the unsoundness in #19

pub mod zst {
    /// A marker trait indicating that a zero-sized type can have its deserialization optimized away
    pub unsafe trait CanSkipDeserialize: Sized + crate::BorshDeserialize {}

    /// A wrapper around Vec<T> for ZSTs that invokes T::deserialize only
    /// once regardless of the length of the vector.
    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
    pub struct SkippableVec<T>(pub Vec<T>);

    impl<T: CanSkipDeserialize> From<SkippableVec<T>> for Vec<T> {
        fn from(value: SkippableVec<T>) -> Self {
            value.0
        }
    }

    /// A marker trait indicating that a type is zero-sized. Panics at compile time
    /// if implemented for a non-ZST.
    trait IsZst: Sized {
        const IS_ZST: () = assert!(core::mem::size_of::<Self>() == 0);
    }

    /// Prevent people from implementing CanSkipDeserialize for non-ZSTs by blanket
    /// implementing the IsZst marker trait.
    impl<T: CanSkipDeserialize> IsZst for T {}
}

Until specialization lands, I think users will have to manually replace Vec<T> with SkippableVec<T> when they want to opt in to the ZST optimization, though we may be able to use some macro magic to help with derived impls.

impl<T: BorshDeserialize> BorshDeserialize for SkippableVec<T> {
    fn deserialize_reader<R: Read>(reader: &mut R) -> Result<Self> {
        let len = u32::deserialize_reader(reader)?;
        let mut result = vec![T::deserialize_reader(reader)?];
        let p = result.as_mut_ptr();
        unsafe {
            forget(result);
            let len = len.try_into().map_err(|_| ErrorKind::InvalidInput)?;
            let result = Vec::from_raw_parts(p, len, len);
            Ok(Self(result))
        }
    }
}

impl<T> BorshDeserialize for Vec<T>
where
    T: BorshDeserialize,
{
    #[inline]
    fn deserialize_reader<R: Read>(reader: &mut R) -> Result<Self> {
        let len = u32::deserialize_reader(reader)?;
        if len == 0 {
            Ok(Vec::new())
        } else if let Some(vec_bytes) = T::vec_from_reader(len, reader)? {
            Ok(vec_bytes)
        } else {
            // TODO(16): return capacity allocation when we can safely do that.
            let mut result = Vec::with_capacity(hint::cautious::<T>(len));
            for _ in 0..len {
                result.push(T::deserialize_reader(reader)?);
            }
            Ok(result)
        }
    }
}

Once specialization does land, we can just use a specialized deserialize impl for types that implement the marker trait.

[frol]

it doesn't' fully address the problem (we have the same issue for hash maps)

I cannot think of hashmap of zero-size keys. Though, a vector of zero-sized types is also pointless in my opinion, so I believe the best thing is to just forbid collections of zero-size elements (#136 (comment)). I am wondering if there is a way to do it through the type system (in the worst case, we will do it at runtime).