alloy_eips/eip4844/
builder.rs

1use crate::eip4844::{
2    utils::WholeFe, Blob, BYTES_PER_BLOB, FIELD_ELEMENTS_PER_BLOB, FIELD_ELEMENT_BYTES_USIZE,
3};
4use alloc::vec::Vec;
5
6#[cfg(feature = "kzg")]
7use crate::eip4844::env_settings::EnvKzgSettings;
8#[cfg(any(feature = "kzg", feature = "arbitrary"))]
9use crate::eip4844::BlobTransactionSidecar;
10#[cfg(feature = "kzg")]
11use crate::eip4844::Bytes48;
12use core::cmp;
13
14/// A builder for creating a [`BlobTransactionSidecar`].
15///
16/// [`BlobTransactionSidecar`]: crate::eip4844::BlobTransactionSidecar
17#[derive(Clone, Debug)]
18pub struct PartialSidecar {
19    /// The blobs in the sidecar.
20    blobs: Vec<Blob>,
21    /// The number of field elements that we have ingested, total.
22    fe: usize,
23}
24
25impl Default for PartialSidecar {
26    fn default() -> Self {
27        Self::new()
28    }
29}
30
31impl PartialSidecar {
32    /// Create a new builder, and push an empty blob to it. This is the default
33    /// constructor, and allocates space for 2 blobs (256 KiB). If you want to
34    /// preallocate a specific number of blobs, use
35    /// [`PartialSidecar::with_capacity`].
36    pub fn new() -> Self {
37        Self::with_capacity(2)
38    }
39
40    /// Create a new builder, preallocating room for `capacity` blobs, and push
41    /// an empty blob to it.
42    pub fn with_capacity(capacity: usize) -> Self {
43        let mut blobs = Vec::with_capacity(capacity);
44        blobs.push(Blob::new([0u8; BYTES_PER_BLOB]));
45        Self { blobs, fe: 0 }
46    }
47
48    /// Get a reference to the blobs currently in the builder.
49    pub fn blobs(&self) -> &[Blob] {
50        &self.blobs
51    }
52
53    /// Get the number of unused field elements that have been allocated
54    fn free_fe(&self) -> usize {
55        self.blobs.len() * FIELD_ELEMENTS_PER_BLOB as usize - self.fe
56    }
57
58    /// Calculate the length of used field elements IN BYTES in the builder.
59    ///
60    /// This is always strictly greater than the number of bytes that have been
61    /// ingested.
62    pub const fn len(&self) -> usize {
63        self.fe * 32
64    }
65
66    /// Check if the builder is empty.
67    pub const fn is_empty(&self) -> bool {
68        self.fe == 0
69    }
70
71    /// Push an empty blob to the builder.
72    fn push_empty_blob(&mut self) {
73        self.blobs.push(Blob::new([0u8; BYTES_PER_BLOB]));
74    }
75
76    /// Allocate enough space for the required number of new field elements.
77    pub fn alloc_fes(&mut self, required_fe: usize) {
78        while self.free_fe() < required_fe {
79            self.push_empty_blob()
80        }
81    }
82
83    /// Get the number of used field elements in the current blob.
84    const fn fe_in_current_blob(&self) -> usize {
85        self.fe % FIELD_ELEMENTS_PER_BLOB as usize
86    }
87
88    /// Get the index of the first unused field element in the current blob.
89    const fn first_unused_fe_index_in_current_blob(&self) -> usize {
90        self.fe_in_current_blob()
91    }
92
93    /// Get a mutable reference to the current blob.
94    fn current_blob_mut(&mut self) -> &mut Blob {
95        let last_unused_blob_index = self.fe / FIELD_ELEMENTS_PER_BLOB as usize;
96        self.blobs.get_mut(last_unused_blob_index).expect("never empty")
97    }
98
99    /// Get a mutable reference to the field element at the given index, in
100    /// the current blob.
101    fn fe_at_mut(&mut self, index: usize) -> &mut [u8] {
102        &mut self.current_blob_mut()[index * 32..(index + 1) * 32]
103    }
104
105    /// Get a mutable reference to the next unused field element.
106    fn next_unused_fe_mut(&mut self) -> &mut [u8] {
107        self.fe_at_mut(self.first_unused_fe_index_in_current_blob())
108    }
109
110    /// Ingest a field element into the current blobs.
111    pub fn ingest_valid_fe(&mut self, data: WholeFe<'_>) {
112        self.alloc_fes(1);
113        self.next_unused_fe_mut().copy_from_slice(data.as_ref());
114        self.fe += 1;
115    }
116
117    /// Ingest a partial FE into the current blobs.
118    ///
119    /// # Panics
120    ///
121    /// If the data is >=32 bytes. Or if there are not enough free FEs to
122    /// encode the data.
123    pub fn ingest_partial_fe(&mut self, data: &[u8]) {
124        self.alloc_fes(1);
125        let fe = self.next_unused_fe_mut();
126        fe[1..1 + data.len()].copy_from_slice(data);
127        self.fe += 1;
128    }
129}
130
131/// A strategy for coding and decoding data into sidecars.
132///
133/// Coder instances are responsible for encoding and decoding data into and from the sidecar. They
134/// are called by the [`SidecarBuilder`] during the [`ingest`], [`take`], and (if `c_kzg` feature
135/// enabled) `build` methods.
136///
137/// This trait allows different downstream users to use different bit-packing
138/// strategies. For example, a simple coder might only use the last 31 bytes of
139/// each blob, while a more complex coder might use a more sophisticated
140/// strategy to pack data into the low 6 bits of the top byte.
141///
142/// [`ingest`]: SidecarBuilder::ingest
143/// [`take`]: SidecarBuilder::take
144pub trait SidecarCoder {
145    /// Calculate the number of field elements required to store the given
146    /// data.
147    fn required_fe(&self, data: &[u8]) -> usize;
148
149    /// Code a slice of data into the builder.
150    fn code(&mut self, builder: &mut PartialSidecar, data: &[u8]);
151
152    /// Finish the sidecar, and commit to the data. This method should empty
153    /// any buffer or scratch space in the coder, and is called by
154    /// [`SidecarBuilder`]'s `take` and `build` methods.
155    fn finish(self, builder: &mut PartialSidecar);
156
157    /// Decode all slices of data from the blobs.
158    fn decode_all(&mut self, blobs: &[Blob]) -> Option<Vec<Vec<u8>>>;
159}
160
161/// Simple coder that only uses the last 31 bytes of each blob. This is the
162/// default coder for the [`SidecarBuilder`].
163///
164/// # Note
165///
166/// Because this coder sacrifices around 3% of total sidecar space, we do not
167/// recommend its use in production. It is provided for convenience and
168/// non-prod environments.
169///
170/// # Behavior
171///
172/// This coder encodes data as follows:
173/// - The first byte of every 32-byte word is empty.
174/// - Data is pre-pended with a 64-bit big-endian length prefix, which is right padded with zeros to
175///   form a complete word.
176/// - The rest of the data is packed into the remaining 31 bytes of each word.
177/// - If the data is not a multiple of 31 bytes, the last word is right-padded with zeros.
178///
179/// This means that the following regions cannot be used to store data, and are
180/// considered "wasted":
181///
182/// - The first byte of every 32-byte word.
183/// - The right padding on the header word containing the data length.
184/// - Any right padding on the last word for each piece of data.
185#[derive(Clone, Copy, Debug, Default)]
186#[non_exhaustive]
187pub struct SimpleCoder;
188
189impl SimpleCoder {
190    /// Decode an some bytes from an iterator of valid FEs.
191    ///
192    /// Returns `Ok(Some(data))` if there is some data.
193    /// Returns `Ok(None)` if there is no data (empty iterator, length prefix is 0).
194    /// Returns `Err(())` if there is an error.
195    fn decode_one<'a>(mut fes: impl Iterator<Item = WholeFe<'a>>) -> Result<Option<Vec<u8>>, ()> {
196        let Some(first) = fes.next() else {
197            return Ok(None);
198        };
199        let mut num_bytes = u64::from_be_bytes(first.as_ref()[1..9].try_into().unwrap()) as usize;
200
201        // if no more bytes is 0, we're done
202        if num_bytes == 0 {
203            return Ok(None);
204        }
205
206        // if there are too many bytes
207        const MAX_ALLOCATION_SIZE: usize = 2_097_152; //2 MiB
208        if num_bytes > MAX_ALLOCATION_SIZE {
209            return Err(());
210        }
211
212        let mut res = Vec::with_capacity(num_bytes);
213        while num_bytes > 0 {
214            let to_copy = cmp::min(31, num_bytes);
215            let fe = fes.next().ok_or(())?;
216            res.extend_from_slice(&fe.as_ref()[1..1 + to_copy]);
217            num_bytes -= to_copy;
218        }
219        Ok(Some(res))
220    }
221}
222
223impl SidecarCoder for SimpleCoder {
224    fn required_fe(&self, data: &[u8]) -> usize {
225        data.len().div_ceil(31) + 1
226    }
227
228    fn code(&mut self, builder: &mut PartialSidecar, mut data: &[u8]) {
229        if data.is_empty() {
230            return;
231        }
232
233        // first FE is the number of following bytes
234        builder.ingest_partial_fe(&(data.len() as u64).to_be_bytes());
235
236        // ingest the rest of the data
237        while !data.is_empty() {
238            let (left, right) = data.split_at(cmp::min(31, data.len()));
239            builder.ingest_partial_fe(left);
240            data = right
241        }
242    }
243
244    /// No-op
245    fn finish(self, _builder: &mut PartialSidecar) {}
246
247    fn decode_all(&mut self, blobs: &[Blob]) -> Option<Vec<Vec<u8>>> {
248        if blobs.is_empty() {
249            return None;
250        }
251
252        if blobs
253            .iter()
254            .flat_map(|blob| blob.chunks(FIELD_ELEMENT_BYTES_USIZE).map(WholeFe::new))
255            .any(|fe| fe.is_none())
256        {
257            return None;
258        }
259
260        let mut fes = blobs
261            .iter()
262            .flat_map(|blob| blob.chunks(FIELD_ELEMENT_BYTES_USIZE).map(WholeFe::new_unchecked));
263
264        let mut res = Vec::new();
265        loop {
266            match Self::decode_one(&mut fes) {
267                Ok(Some(data)) => res.push(data),
268                Ok(None) => break,
269                Err(()) => return None,
270            }
271        }
272        Some(res)
273    }
274}
275
276/// Build a [`BlobTransactionSidecar`] from an arbitrary amount of data.
277///
278/// This is useful for creating a sidecar from a large amount of data,
279/// which is then split into blobs. It delays KZG commitments and proofs
280/// until all data is ready.
281///
282/// [`BlobTransactionSidecar`]: crate::eip4844::BlobTransactionSidecar
283#[derive(Clone, Debug)]
284pub struct SidecarBuilder<T = SimpleCoder> {
285    /// The blob array we will code data into
286    inner: PartialSidecar,
287    /// The coder to use for ingesting and decoding data.
288    coder: T,
289}
290
291impl<T> Default for SidecarBuilder<T>
292where
293    T: Default + SidecarCoder,
294{
295    fn default() -> Self {
296        Self::new()
297    }
298}
299
300#[cfg(feature = "arbitrary")]
301impl<'a, T: arbitrary::Arbitrary<'a> + Clone> SidecarBuilder<T> {
302    /// Builds an arbitrary realization for BlobTransactionSidecar.
303    pub fn build_arbitrary(&self) -> BlobTransactionSidecar {
304        <BlobTransactionSidecar as arbitrary::Arbitrary>::arbitrary(
305            &mut arbitrary::Unstructured::new(&[]),
306        )
307        .unwrap()
308    }
309}
310
311impl<T: SidecarCoder + Default> SidecarBuilder<T> {
312    /// Instantiate a new builder and new coder instance.
313    ///
314    /// By default, this allocates space for 2 blobs (256 KiB). If you want to
315    /// preallocate a specific number of blobs, use
316    /// [`SidecarBuilder::with_capacity`].
317    pub fn new() -> Self {
318        T::default().into()
319    }
320
321    /// Create a new builder from a slice of data by calling
322    /// [`SidecarBuilder::from_coder_and_data`]
323    pub fn from_slice(data: &[u8]) -> Self {
324        Self::from_coder_and_data(T::default(), data)
325    }
326
327    /// Create a new builder with a pre-allocated capacity. This capacity is
328    /// measured in blobs, each of which is 128 KiB.
329    pub fn with_capacity(capacity: usize) -> Self {
330        Self::from_coder_and_capacity(T::default(), capacity)
331    }
332}
333
334impl<T: SidecarCoder> SidecarBuilder<T> {
335    /// Instantiate a new builder with the provided coder and capacity. This
336    /// capacity is measured in blobs, each of which is 128 KiB.
337    pub fn from_coder_and_capacity(coder: T, capacity: usize) -> Self {
338        Self { inner: PartialSidecar::with_capacity(capacity), coder }
339    }
340
341    /// Calculate the length of bytes used by field elements in the builder.
342    ///
343    /// This is always strictly greater than the number of bytes that have been
344    /// ingested.
345    pub const fn len(&self) -> usize {
346        self.inner.len()
347    }
348
349    /// Check if the builder is empty.
350    pub const fn is_empty(&self) -> bool {
351        self.inner.is_empty()
352    }
353
354    /// Create a new builder from a slice of data.
355    pub fn from_coder_and_data(coder: T, data: &[u8]) -> Self {
356        let required_fe = coder.required_fe(data);
357        let mut this = Self::from_coder_and_capacity(
358            coder,
359            required_fe.div_ceil(FIELD_ELEMENTS_PER_BLOB as usize),
360        );
361        this.ingest(data);
362        this
363    }
364
365    /// Ingest a slice of data into the builder.
366    pub fn ingest(&mut self, data: &[u8]) {
367        self.inner.alloc_fes(self.coder.required_fe(data));
368        self.coder.code(&mut self.inner, data);
369    }
370
371    /// Build the sidecar from the data with the provided settings.
372    #[cfg(feature = "kzg")]
373    pub fn build_with_settings(
374        self,
375        settings: &c_kzg::KzgSettings,
376    ) -> Result<BlobTransactionSidecar, c_kzg::Error> {
377        let mut commitments = Vec::with_capacity(self.inner.blobs.len());
378        let mut proofs = Vec::with_capacity(self.inner.blobs.len());
379        for blob in &self.inner.blobs {
380            // SAFETY: same size
381            let blob = unsafe { core::mem::transmute::<&Blob, &c_kzg::Blob>(blob) };
382            let commitment = settings.blob_to_kzg_commitment(blob)?;
383            let proof = settings.compute_blob_kzg_proof(blob, &commitment.to_bytes())?;
384
385            // SAFETY: same size
386            unsafe {
387                commitments
388                    .push(core::mem::transmute::<c_kzg::Bytes48, Bytes48>(commitment.to_bytes()));
389                proofs.push(core::mem::transmute::<c_kzg::Bytes48, Bytes48>(proof.to_bytes()));
390            }
391        }
392
393        Ok(BlobTransactionSidecar::new(self.inner.blobs, commitments, proofs))
394    }
395
396    /// Build the sidecar from the data, with default (Ethereum Mainnet)
397    /// settings.
398    #[cfg(feature = "kzg")]
399    pub fn build(self) -> Result<BlobTransactionSidecar, c_kzg::Error> {
400        self.build_with_settings(EnvKzgSettings::Default.get())
401    }
402
403    /// Take the blobs from the builder, without committing them to a KZG proof.
404    pub fn take(self) -> Vec<Blob> {
405        self.inner.blobs
406    }
407}
408
409impl<T: SidecarCoder> From<T> for SidecarBuilder<T> {
410    /// Instantiate a new builder with the provided coder.
411    ///
412    /// This is equivalent to calling
413    /// [`SidecarBuilder::from_coder_and_capacity`] with a capacity of 1.
414    /// If you want to preallocate a specific number of blobs, use
415    /// [`SidecarBuilder::from_coder_and_capacity`].
416    fn from(coder: T) -> Self {
417        Self::from_coder_and_capacity(coder, 1)
418    }
419}
420
421impl<T, R> FromIterator<R> for SidecarBuilder<T>
422where
423    T: SidecarCoder + Default,
424    R: AsRef<[u8]>,
425{
426    fn from_iter<I: IntoIterator<Item = R>>(iter: I) -> Self {
427        let mut this = Self::new();
428        for data in iter {
429            this.ingest(data.as_ref());
430        }
431        this
432    }
433}
434
435#[cfg(test)]
436mod tests {
437    use super::*;
438    use crate::eip4844::USABLE_BYTES_PER_BLOB;
439
440    #[test]
441    fn ingestion_strategy() {
442        let mut builder = PartialSidecar::new();
443        let data = &[
444            vec![1u8; 32],
445            vec![2u8; 372],
446            vec![3u8; 17],
447            vec![4u8; 5],
448            vec![5u8; 126_945],
449            vec![6u8; 2 * 126_945],
450        ];
451
452        data.iter().for_each(|data| SimpleCoder.code(&mut builder, data.as_slice()));
453
454        let decoded = SimpleCoder.decode_all(builder.blobs()).unwrap();
455        assert_eq!(decoded, data);
456    }
457
458    #[test]
459    fn big_ingestion_strategy() {
460        let data = vec![1u8; 126_945];
461        let builder = SidecarBuilder::<SimpleCoder>::from_slice(&data);
462
463        let blobs = builder.take();
464        let decoded = SimpleCoder.decode_all(&blobs).unwrap().concat();
465
466        assert_eq!(decoded, data);
467    }
468
469    #[test]
470    fn decode_all_rejects_invalid_data() {
471        assert_eq!(SimpleCoder.decode_all(&[]), None);
472        assert_eq!(SimpleCoder.decode_all(&[Blob::new([0xffu8; BYTES_PER_BLOB])]), None);
473    }
474
475    #[test]
476    fn it_ingests() {
477        // test ingesting a lot of data.
478        let data = [
479            vec![1u8; 32],
480            vec![2u8; 372],
481            vec![3u8; 17],
482            vec![4u8; 5],
483            vec![5u8; USABLE_BYTES_PER_BLOB + 2],
484        ];
485
486        let mut builder = data.iter().collect::<SidecarBuilder<SimpleCoder>>();
487
488        let expected_fe = data.iter().map(|d| SimpleCoder.required_fe(d)).sum::<usize>();
489        assert_eq!(builder.len(), expected_fe * 32);
490
491        // consume 2 more
492        builder.ingest(b"hello");
493        assert_eq!(builder.len(), expected_fe * 32 + 64);
494    }
495}
alloy_eips/eip4844/builder.rs

alloy_eips/eip4844/
builder.rs
