kona_proof_interop/
pre_state.rs

1//! Types for the pre-state claims used in the interop proof.
2
3use alloc::vec::Vec;
4use alloy_primitives::{B256, Bytes, b256, keccak256};
5use alloy_rlp::{Buf, Decodable, Encodable, Header, RlpDecodable, RlpEncodable};
6use kona_interop::{OutputRootWithChain, SUPER_ROOT_VERSION, SuperRoot};
7use serde::{Deserialize, Serialize};
8
9/// The current [TransitionState] encoding format version.
10pub(crate) const TRANSITION_STATE_VERSION: u8 = 255;
11
12/// The maximum number of steps allowed in a [TransitionState].
13pub const TRANSITION_STATE_MAX_STEPS: u64 = 2u64.pow(7) - 1;
14
15/// The [Bytes] representation of the string "invalid".
16pub const INVALID_TRANSITION: Bytes = Bytes::from_static(b"invalid");
17
18/// `keccak256("invalid")`
19pub const INVALID_TRANSITION_HASH: B256 =
20    b256!("ffd7db0f9d5cdeb49c4c9eba649d4dc6d852d64671e65488e57f58584992ac68");
21
22/// The [PreState] of the interop proof program can be one of two types: a [SuperRoot] or a
23/// [TransitionState]. The [SuperRoot] is the canonical state of the superchain, while the
24/// [TransitionState] is a super-structure of the [SuperRoot] that represents the progress of a
25/// pending superchain state transition from one [SuperRoot] to the next.
26#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
27#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
28pub enum PreState {
29    /// The canonical state of the superchain.
30    SuperRoot(SuperRoot),
31    /// The progress of a pending superchain state transition.
32    TransitionState(TransitionState),
33}
34
35impl PreState {
36    /// Hashes the encoded [PreState] using [keccak256].
37    pub fn hash(&self) -> B256 {
38        let mut rlp_buf = Vec::with_capacity(self.length());
39        self.encode(&mut rlp_buf);
40        keccak256(&rlp_buf)
41    }
42
43    /// Returns the timestamp of the [PreState].
44    pub const fn timestamp(&self) -> u64 {
45        match self {
46            Self::SuperRoot(super_root) => super_root.timestamp,
47            Self::TransitionState(transition_state) => transition_state.pre_state.timestamp,
48        }
49    }
50
51    /// Returns the active L2 output root hash of the [PreState]. This is the output root that
52    /// represents the pre-state of the chain that is to be committed to in the next transition
53    /// step, or [None] if the [PreState] has already been fully saturated.
54    pub fn active_l2_output_root(&self) -> Option<&OutputRootWithChain> {
55        match self {
56            Self::SuperRoot(super_root) => super_root.output_roots.first(),
57            Self::TransitionState(transition_state) => {
58                transition_state.pre_state.output_roots.get(transition_state.step as usize)
59            }
60        }
61    }
62
63    /// Returns the active L2 chain ID of the [PreState]. This is the chain ID of the output root
64    /// that is to be committed to in the next transition step, or [None] if the [PreState]
65    /// has already been fully saturated.
66    pub fn active_l2_chain_id(&self) -> Option<u64> {
67        self.active_l2_output_root().map(|output_root| output_root.chain_id)
68    }
69
70    /// Transitions to the next state, appending the [OptimisticBlock] to the pending progress.
71    pub fn transition(self, optimistic_block: Option<OptimisticBlock>) -> Option<Self> {
72        match self {
73            Self::SuperRoot(super_root) => Some(Self::TransitionState(TransitionState::new(
74                super_root,
75                alloc::vec![optimistic_block?],
76                1,
77            ))),
78            Self::TransitionState(mut transition_state) => {
79                // If the transition state's pending progress contains the same number of states as
80                // the pre-state's output roots already, then we can either no-op
81                // the transition or finalize it.
82                if transition_state.pending_progress.len() ==
83                    transition_state.pre_state.output_roots.len()
84                {
85                    if transition_state.step == TRANSITION_STATE_MAX_STEPS {
86                        let super_root = SuperRoot::new(
87                            transition_state.pre_state.timestamp + 1,
88                            transition_state
89                                .pending_progress
90                                .iter()
91                                .zip(transition_state.pre_state.output_roots.iter())
92                                .map(|(optimistic_block, pre_state_output)| {
93                                    OutputRootWithChain::new(
94                                        pre_state_output.chain_id,
95                                        optimistic_block.output_root,
96                                    )
97                                })
98                                .collect(),
99                        );
100                        return Some(Self::SuperRoot(super_root));
101                    } else {
102                        transition_state.step += 1;
103                        return Some(Self::TransitionState(transition_state));
104                    };
105                }
106
107                transition_state.pending_progress.push(optimistic_block?);
108                transition_state.step += 1;
109                Some(Self::TransitionState(transition_state))
110            }
111        }
112    }
113}
114
115impl Encodable for PreState {
116    fn encode(&self, out: &mut dyn alloy_rlp::BufMut) {
117        match self {
118            Self::SuperRoot(super_root) => {
119                super_root.encode(out);
120            }
121            Self::TransitionState(transition_state) => {
122                transition_state.encode(out);
123            }
124        }
125    }
126}
127
128impl Decodable for PreState {
129    fn decode(buf: &mut &[u8]) -> alloy_rlp::Result<Self> {
130        if buf.is_empty() {
131            return Err(alloy_rlp::Error::UnexpectedLength);
132        }
133
134        match buf[0] {
135            TRANSITION_STATE_VERSION => {
136                let transition_state = TransitionState::decode(buf)?;
137                Ok(Self::TransitionState(transition_state))
138            }
139            SUPER_ROOT_VERSION => {
140                let super_root =
141                    SuperRoot::decode(buf).map_err(|_| alloy_rlp::Error::UnexpectedString)?;
142                Ok(Self::SuperRoot(super_root))
143            }
144            _ => Err(alloy_rlp::Error::Custom("invalid version byte")),
145        }
146    }
147}
148
149/// The [TransitionState] is a super-structure of the [SuperRoot] that represents the progress of a
150/// pending superchain state transition from one [SuperRoot] to the next.
151#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize)]
152#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
153pub struct TransitionState {
154    /// The canonical pre-state super root commitment.
155    pub pre_state: SuperRoot,
156    /// The progress that has been made in the pending superchain state transition.
157    pub pending_progress: Vec<OptimisticBlock>,
158    /// The step number of the pending superchain state transition.
159    pub step: u64,
160}
161
162impl TransitionState {
163    /// Create a new [TransitionState] with the given pre-state, pending progress, and step number.
164    pub const fn new(
165        pre_state: SuperRoot,
166        pending_progress: Vec<OptimisticBlock>,
167        step: u64,
168    ) -> Self {
169        Self { pre_state, pending_progress, step }
170    }
171
172    /// Hashes the encoded [TransitionState] using [keccak256].
173    pub fn hash(&self) -> B256 {
174        let mut rlp_buf = Vec::with_capacity(self.length());
175        self.encode(&mut rlp_buf);
176        keccak256(&rlp_buf)
177    }
178
179    /// Returns the RLP payload length of the [TransitionState].
180    pub fn payload_length(&self) -> usize {
181        Header { list: false, payload_length: self.pre_state.encoded_length() }.length() +
182            self.pre_state.encoded_length() +
183            self.pending_progress.length() +
184            self.step.length()
185    }
186}
187
188impl Encodable for TransitionState {
189    fn encode(&self, out: &mut dyn alloy_rlp::BufMut) {
190        out.put_u8(TRANSITION_STATE_VERSION);
191
192        Header { list: true, payload_length: self.payload_length() }.encode(out);
193
194        // The pre-state has special encoding, since it is not RLP. We encode the structure, and
195        // then encode it as a RLP string.
196        let mut pre_state_buf = Vec::new();
197        self.pre_state.encode(&mut pre_state_buf);
198        Bytes::from(pre_state_buf).encode(out);
199
200        self.pending_progress.encode(out);
201        self.step.encode(out);
202    }
203}
204
205impl Decodable for TransitionState {
206    fn decode(buf: &mut &[u8]) -> alloy_rlp::Result<Self> {
207        if buf.is_empty() {
208            return Err(alloy_rlp::Error::UnexpectedLength);
209        }
210
211        let version = buf[0];
212        if version != TRANSITION_STATE_VERSION {
213            return Err(alloy_rlp::Error::Custom("invalid version byte"));
214        }
215        buf.advance(1);
216
217        // Decode the RLP header.
218        let header = Header::decode(buf)?;
219        if !header.list {
220            return Err(alloy_rlp::Error::UnexpectedString);
221        }
222
223        // The pre-state has special decoding, since it is not RLP. We decode the RLP string, and
224        // then decode the structure.
225        let pre_state_buf = Bytes::decode(buf)?;
226        let pre_state = SuperRoot::decode(&mut pre_state_buf.as_ref())
227            .map_err(|_| alloy_rlp::Error::UnexpectedString)?;
228
229        // The rest of the fields are RLP encoded as normal.
230        let pending_progress = Vec::<OptimisticBlock>::decode(buf)?;
231        let step = u64::decode(buf)?;
232
233        Ok(Self { pre_state, pending_progress, step })
234    }
235}
236
237/// A wrapper around a pending output root hash with the block hash it commits to.
238#[derive(
239    Default, Debug, Clone, Eq, PartialEq, RlpEncodable, RlpDecodable, Serialize, Deserialize,
240)]
241#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
242pub struct OptimisticBlock {
243    /// The block hash of the output root.
244    pub block_hash: B256,
245    /// The output root hash.
246    pub output_root: B256,
247}
248
249impl OptimisticBlock {
250    /// Create a new [OptimisticBlock] with the given block hash and output root hash.
251    pub const fn new(block_hash: B256, output_root: B256) -> Self {
252        Self { block_hash, output_root }
253    }
254}
255
256#[cfg(test)]
257mod test {
258    use super::{OptimisticBlock, SuperRoot, TransitionState};
259    use alloc::{vec, vec::Vec};
260    use alloy_primitives::B256;
261    use alloy_rlp::{Decodable, Encodable};
262    use kona_interop::OutputRootWithChain;
263
264    #[test]
265    fn test_static_transition_state_roundtrip() {
266        let transition_state = TransitionState::new(
267            SuperRoot::new(
268                10,
269                vec![
270                    (OutputRootWithChain::new(1, B256::default())),
271                    (OutputRootWithChain::new(2, B256::default())),
272                ],
273            ),
274            vec![OptimisticBlock::default(), OptimisticBlock::default()],
275            1,
276        );
277
278        let mut rlp_buf = Vec::with_capacity(transition_state.length());
279        transition_state.encode(&mut rlp_buf);
280
281        assert_eq!(transition_state, TransitionState::decode(&mut rlp_buf.as_slice()).unwrap());
282    }
283
284    #[test]
285    #[cfg(feature = "arbitrary")]
286    fn test_arbitrary_pre_state_roundtrip() {
287        use arbitrary::Arbitrary;
288        use rand::Rng;
289        let mut bytes = [0u8; 1024];
290        rand::rng().fill(bytes.as_mut_slice());
291        let pre_state =
292            super::PreState::arbitrary(&mut arbitrary::Unstructured::new(&bytes)).unwrap();
293
294        let mut rlp_buf = Vec::with_capacity(pre_state.length());
295        pre_state.encode(&mut rlp_buf);
296        assert_eq!(pre_state, super::PreState::decode(&mut rlp_buf.as_slice()).unwrap());
297    }
298
299    #[test]
300    #[cfg(feature = "arbitrary")]
301    fn test_arbitrary_transition_state_roundtrip() {
302        use arbitrary::Arbitrary;
303        use rand::Rng;
304        let mut bytes = [0u8; 1024];
305        rand::rng().fill(bytes.as_mut_slice());
306        let transition_state =
307            TransitionState::arbitrary(&mut arbitrary::Unstructured::new(&bytes)).unwrap();
308
309        let mut rlp_buf = Vec::with_capacity(transition_state.length());
310        transition_state.encode(&mut rlp_buf);
311        assert_eq!(transition_state, TransitionState::decode(&mut rlp_buf.as_slice()).unwrap());
312    }
313}
kona_proof_interop/pre_state.rs

kona_proof_interop/
pre_state.rs
