MaxEncodedLen tracking issue

[coriolinus]

Rationale

For PoV benchmarking, we need some way to estimate what the maximum encoded size of an arbitrary storage item can be. We've settled on a new trait, MaxEncodedLen.

While Encode::size_hint already exists, we can't rely on it. One fatal flaw: it's an optional, "if possible" method which for many structs simply returns the default size of 0. Another: Encode is implemented for certain types such as VecDeque<T>, which we'd want to intentionally exclude from storage, as they aren't bounded. We need a trait which we can use to exclude types.

Design

pub trait MaxEncodedLen: Encode {
  fn max_encoded_len() -> usize;
}

Roadmap

• implement BoundedEncodedLen #8720 Introduce the BoundedEncodedLen trait
• implement BoundedEncodedLen #8720 Implement for primitive types, fixed size arrays, tuples, etc. Non-containers for which Encode is implemented. Mostly defers to sp_std::mem::size_of::<T>().
• impl BoundedEncodedLen for BoundedVec #8727 Implement for BoundedVec<T>
• implement BoundedEncodedLen #8720 Implement for certain containers:
  • Option<T>
  • Result<T, E>
  • PhantomData<T>
  • Compact<T>
• Optional: Implement Bounded variants for other container types for which Encode is implemented. Implement BoundedEncodedLen for these bounded variants.
  • Add BoundedBTreeMap to frame_support::storage #8745 BTreeMap<K, V>
  • Add BoundedBTreeSet #8750 BTreeSet<T>
  • BinaryHeap<T>
  • LinkedList<T>
  • VecDeque<T>
• #[derive(MaxEncodedLen)] #8737 Derive macro: #[derive(Encode, BoundedEncodedLen)] for non-container structs, enums. Requires all fields to implement Encode and BoundedEncodedLen.
• Extend FRAME storage macros such that all StorageMap and friends are actually implemented as newtypes which implement the full API of the parent type, plus BoundedEncodedLen
  • Backwards-compatibility: existing macro declarations should use a fixed bound of 300,000
  • Allow to specify some max number of values for storages in pallet macro. #8735 A new optional attribute (pending bikeshedding) allows per-map customization of bound. #[storage::map_bound(300_000)]. The value specified in this attribute is used to determine the bounded length of the map.
• New requirement on frame::storage: all storage items must implement BoundedEncodedLen.
• Patch all the holes to make everything work.

Notes

This always explicitly computes an upper bound. While a u128 can potentially be compact-encoded in only one byte, Compact<u128>::max_encoded_len() will always return 17.

While implementations of BoundedVec<T> and friends impose a hard cap on their length, we do not use BoundedEncodedLen to impose a hard cap on the size of StorageMap and friends. While potentially a parachain author could misrepresent the bounds on its maps to attempt to pack a parachain block with more transactions, that behavior is self-defeating. Eventually they will try to pack too many transactions into a block, causing that block to become invalid because its actual size is too large. User documentation for the storage::map_bound attribute should emphasize that it is in the chain author's best interest to use a reasonable value here.

We'd like to offer logging warnings that could be noted by Prometheus etc when the size of StorageMap exceeds certain thresholds (eg. info at 80%, warn at 100%), but that feature is out of scope of this tracking issue. It requires additional design work because currently the only way to determine a map's size is to iterate over its members, which is not performant.

max_encoded_len is a function instead of an associated constant for pragmatic rather than theoretical reasons. Currently, BoundedVec's limit is not a constant, so we can't use its value in a constant context.

[bkchr]

* Introduce the `BoundedEncodedLen` trait to SCALE

Why? Why should this exist in scale-codec?

What I still don't understand, how should this help to calculate the proof size? The proof size is not only composed of the size of the individual elements. The size also comes from the trie structure itself that is encoded in the proof. Than there are also values included which are may not being accessed by an extrinsic and still would increase the proof size.

[shawntabrizi]

After our chat in Element, I agree this probably can go in Substrate instead of SCALE.

@coriolinus you can transfer the issue.

[kianenigma]

I can help with

• Extend Frame macros to..

• Implement Derive macro for...

---

Backwards-compatibility: existing macro declarations should use a fixed bound of 300,000

Where is this number coming from?

---

New requirement on frame::storage: all storage items must implement BoundedEncodedLen.

Given all of this, in the context of a parachain, we pretty much want to ban storing anything unbounded like Vec<_> in storage, right? be it a map or simple value, it shall never be unbounded.

[coriolinus]

I'm working on the derive macro right now, but assistance on the Frame side would be much appreciated.

Where is this number coming from?

Just a SWAG; it's high enough that it'll probably suffice for most cases without being high enough to make the weight predictions unreasonably high.

be it a map or simple value, it shall never be unbounded.

Yes, we're specifically excluding Vec<T> with that requirement, in favor of BoundedVec. Bounded maps etc which can fit inside other arbitrary storage items will follow.