1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

//! Sequencing information exposed by snapp smart contract execution.
//!
//! The format of this data is opaque to the Mina protocol, and is defined by each individual smart
//! contract. A smart contract may emit zero or more 'sequence events', which are communicated with
//! the transaction when it is broadcast over the Mina network.
//!
//! These 'sequence events' are collapsed into a single hash for the purposes of the zero-knowledge proofs and cryptographic commitments in [`SequenceState`].
//!
//! Sequence events are stored in the [`SequenceState`] in the order that they are encountered by
//! block producers, storing snapshots of the latest commitment at the end of each block for the
//! most recent 5 blocks with updates.
//!
//! For example, a snapp may be executed zero or more times in a block using sequence events:
//! ```text
//! block1:
//! [ {sequence_events: [A, B, C], ...}
//! , {sequence_events: [D], ...}
//! , {sequence_events: [], ...} ]
//! block2:
//! [ {sequence_events: [E, F], ...} ]
//! block3:
//! []
//! block4:
//! [ {sequence_events: [G], ...} ]
//! ```
//! At the end of each block, the latest sequence state would look like:
//! ```text
//! block1:
//! [[D], [A, B, C], ... /* Any historical events */]
//! block2:
//! [[E, F], [D], [A, B, C]], ... /* Any historical events */]
//! block3:
//! [[E, F], [D], [A, B, C]], ... /* Any historical events */]
//! block4:
//! [[G], [E, F], [D], [A, B, C]], ... /* Any historical events */]
//! ```
//!
//! In order to reduce the amount of data stored by nodes, this information is stored in the
//! snapp's account as a cryptographic commitment instead of a constantly growing list. This update
//! is computed by [`SequenceState::push_sequence_events`].

use crate::primitives::*;

/// A single sequence event emitted by a snapp. See [`crate::sequence_event`] for more.
pub struct SequenceEvent<'a>(pub &'a [Fp]);

impl<'a> SequenceEvent<'a> {
    /// Compute the hash input of a single sequence event by calling [`HashInput::add_field`] for
    /// each field element in the event.
    /// ```rust
    /// let mut hash_input = HashInput::empty();
    /// for event_part in event.0.iter() {
    ///     HashInput::add_field(&mut hash_input, *event_part)
    /// }
    /// hash_input
    /// ```
    pub fn hash_input(event: &SequenceEvent<'a>) -> HashInput {
        let mut hash_input = HashInput::empty();
        for event_part in event.0.iter() {
            HashInput::add_field(&mut hash_input, *event_part)
        }
        hash_input
    }

    /// Compute the hash of a single sequence event, using [`SequenceEvent::hash_input`] and
    /// [`HashPrefixState::sequence_event`].
    /// ```rust
    /// Hash::compute_hash(
    ///     HashPrefixState::sequence_event(),
    ///     SequenceEvent::hash_input(event),
    /// )
    /// ```
    pub fn hash(event: &SequenceEvent<'a>) -> Hash {
        Hash::compute_hash(
            HashPrefixState::sequence_event(),
            SequenceEvent::hash_input(event),
        )
    }
}

/// A list of zero or more events, which may be emitted by a snapp. See [`crate::event`] for more.
pub type SequenceEvents<'a> = [SequenceEvent<'a>];

/// A hash representing a list of sequence events.
#[derive(Copy, Clone)]
pub struct SequenceEventsHash(pub Fp);

impl SequenceEventsHash {
    /// The hash representing an empty list of sequence events. Equivalent to
    /// [`Hash::empty_sequence_events`] wrapped by [`SequenceEventsHash`].
    pub fn empty() -> SequenceEventsHash {
        SequenceEventsHash(Hash::empty_sequence_events())
    }

    /// The hash formed by hash-consing `sequence_event_hash` with `sequence_events_hash`.
    ///
    /// Creates a [`HashInput`] formed by adding the `sequence_events_hash` and
    /// `sequence_events_hash` field elements in order, then [computing](`Hash::compute_hash`) the
    /// resulting hash with [`HashPrefixState::sequence_events_list`].
    /// ```rust
    /// let mut hash_input = HashInput::empty();
    /// HashInput::add_field(&mut hash_input, sequence_event_hash);
    /// HashInput::add_field(&mut hash_input, sequence_events_hash.0);
    ///
    /// SequenceEventsHash(Hash::compute_hash(
    ///     HashPrefixState::sequence_events_list(),
    ///     hash_input,
    /// ))
    /// ```
    pub fn push_sequence_event_hash(
        sequence_event_hash: Hash,
        sequence_events_hash: SequenceEventsHash,
    ) -> SequenceEventsHash {
        let mut hash_input = HashInput::empty();
        HashInput::add_field(&mut hash_input, sequence_event_hash);
        HashInput::add_field(&mut hash_input, sequence_events_hash.0);
        SequenceEventsHash(Hash::compute_hash(
            HashPrefixState::sequence_events_list(),
            hash_input,
        ))
    }

    /// The hash formed by hash-consing `sequence_event`'s hash with `sequence_events_hash`.
    ///
    /// Equivalent to calling [`SequenceEventsHash::push_sequence_event`] on the result of
    /// [`SequenceEvent::hash`]:
    /// ```rust
    /// SequenceEventsHash::push_sequence_event_hash(
    ///     SequenceEvent::hash(sequence_event),
    ///     sequence_events_hash,
    /// )
    /// ```
    pub fn push_sequence_event(
        sequence_event: &SequenceEvent,
        sequence_events_hash: SequenceEventsHash,
    ) -> SequenceEventsHash {
        SequenceEventsHash::push_sequence_event_hash(
            SequenceEvent::hash(sequence_event),
            sequence_events_hash,
        )
    }

    /// Compute the hash of `sequence_events` by starting with
    /// [`empty`](`SequenceEventsHash::empty`) and calling
    /// [`push_sequence_event`](`SequenceEventsHash::push_sequence_event`) on each event in turn.
    /// ```rust
    /// let mut sequence_events_hash = SequenceEventsHash::empty();
    /// for sequence_event in sequence_events.iter() {
    ///     sequence_events_hash =
    ///         SequenceEventsHash::push_sequence_event(sequence_event, sequence_events_hash)
    /// }
    /// sequence_events_hash
    /// ```
    pub fn of_sequence_events(sequence_events: &SequenceEvents) -> SequenceEventsHash {
        let mut sequence_events_hash = SequenceEventsHash::empty();
        for sequence_event in sequence_events.iter() {
            sequence_events_hash =
                SequenceEventsHash::push_sequence_event(sequence_event, sequence_events_hash)
        }
        sequence_events_hash
    }
}

/// A hash representing the current sequence state.
#[derive(Copy, Clone)]
pub struct SequenceStateHash(pub Fp);

impl SequenceStateHash {
    /// The hash representing an empty list of sequence events. Equivalent to
    /// [`Hash::empty_sequence_state`] wrapped by [`SequenceStateHash`].
    pub fn empty() -> SequenceStateHash {
        SequenceStateHash(Hash::empty_sequence_state())
    }

    /// The hash formed by hash-consing `sequence_events_hash` with `sequence_state_hash`.
    ///
    /// Creates a [`HashInput`] formed by adding the `sequence_state_hash` and
    /// `sequence_state_hash` field elements in order, then [computing](`Hash::compute_hash`) the
    /// resulting hash with [`HashPrefixState::sequence_state`].
    /// ```rust
    /// let mut hash_input = HashInput::empty();
    /// HashInput::add_field(&mut hash_input, sequence_events_hash.0);
    /// HashInput::add_field(&mut hash_input, sequence_state_hash.0);
    /// SequenceStateHash(Hash::compute_hash(
    ///     HashPrefixState::sequence_state(),
    ///     hash_input,
    /// ))
    /// ```
    pub fn push_sequence_events_hash(
        sequence_events_hash: SequenceEventsHash,
        sequence_state_hash: SequenceStateHash,
    ) -> SequenceStateHash {
        let mut hash_input = HashInput::empty();
        HashInput::add_field(&mut hash_input, sequence_events_hash.0);
        HashInput::add_field(&mut hash_input, sequence_state_hash.0);
        SequenceStateHash(Hash::compute_hash(
            HashPrefixState::sequence_state(),
            hash_input,
        ))
    }

    /// The hash formed by hash-consing `sequence_events`'s hash with `sequence_state_hash`.
    ///
    /// Equivalent to calling [`SequenceStateHash::push_sequence_events`] on the result of
    /// [`SequenceEventsHash::of_sequence_events`]:
    /// ```rust
    /// SequenceStateHash::push_sequence_events_hash(
    ///     SequenceEvents::hash(sequence_events),
    ///     sequence_state_hash,
    /// )
    /// ```
    pub fn push_sequence_events(
        sequence_events: &SequenceEvents,
        sequence_state_hash: SequenceStateHash,
    ) -> SequenceStateHash {
        SequenceStateHash::push_sequence_events_hash(
            SequenceEventsHash::of_sequence_events(sequence_events),
            sequence_state_hash,
        )
    }
}

/// Information about all historical sequence events emmitted by snapp transactions.
///
/// This data is stored in last-in-first-out stack, stored as a cryptographic hash. The order that
/// transactions are stored in this stack is determined by the order in which they are applied
/// within blocks, as determined by block producers.
///
/// This structure stores the updates from the 5 most-recent slots, so that previous updates can be
/// 'rolled-up' into an update of the main snapp state, while still allowing the snapp to accept
/// new updates within the same block.
pub struct SequenceState {
    /// History of sequenced event updates for the most recent 5 slots with updates.
    pub most_recent_states: [SequenceStateHash; 5],
    /// The slot number (since genesis) of the most recent sequenced event update.
    pub last_sequence_slot: u32,
}

impl SequenceState {
    /// The initial value of `SequenceState` in accounts.
    ///
    /// ```rust
    /// empty() =
    /// SequenceState {
    ///     most_recent_states: [SequenceStateHash::empty(); 5],
    ///     last_sequence_slot: 0,
    /// }
    /// ```
    pub fn empty() -> SequenceState {
        SequenceState {
            most_recent_states: [SequenceStateHash::empty(); 5],
            last_sequence_slot: 0,
        }
    }

    /// Update `SequenceState` for the current block's slot, shifting the `most_recent_states`
    /// along by 1 position if the `slot` is greater than `last_sequence_slot`, and copying the
    /// original first state into the first position.
    /// ```rust
    /// if state.last_sequence_slot < slot {
    ///     let [state0, state1, state2, state3, _] = state.most_recent_states;
    ///     SequenceState {
    ///         most_recent_states: [state0, state0, state1, state2, state3],
    ///         last_sequence_slot: slot,
    ///     }
    /// } else {
    ///     state
    /// }
    /// ```
    pub fn update_for_slot(state: SequenceState, slot: u32) -> SequenceState {
        if state.last_sequence_slot < slot {
            let [state0, state1, state2, state3, _] = state.most_recent_states;
            SequenceState {
                most_recent_states: [state0, state0, state1, state2, state3],
                last_sequence_slot: slot,
            }
        } else {
            state
        }
    }

    /// Update the most recent sequence state with the new hash after pushing the sequence event,
    /// using [`SequenceStateHash::push_sequence_events`].
    ///
    /// ```rust
    /// state.most_recent_states[0] =
    ///     SequenceStateHash::push_sequence_events(
    ///         sequence_events,
    ///         state.most_recent_states[0],
    ///     );
    /// ```
    pub fn push_sequence_events_unconditional(
        mut state: SequenceState,
        sequence_events: &SequenceEvents,
    ) -> SequenceState {
        state.most_recent_states[0] =
            SequenceStateHash::push_sequence_events(sequence_events, state.most_recent_states[0]);
        state
    }

    /// Push a sequence event at a given slot.
    ///
    /// If the sequence event is empty, the [`SequenceState`] must be returned unmodified.
    /// Otherwise, this must call [`SequenceState::update_for_slot`] and then
    /// [`SequenceState::push_sequence_events_unconditional`].
    ///
    /// ```rust
    /// if sequence_events.len() == 0 {
    ///     state
    /// } else {
    ///     let state = SequenceState::update_for_slot(state, slot);
    ///     SequenceState::push_sequence_events_unconditional(state, sequence_events)
    /// }
    /// ```
    pub fn push_sequence_events(
        state: SequenceState,
        sequence_events: &SequenceEvents,
        slot: u32,
    ) -> SequenceState {
        if sequence_events.len() == 0 {
            state
        } else {
            let state = SequenceState::update_for_slot(state, slot);
            SequenceState::push_sequence_events_unconditional(state, sequence_events)
        }
    }
}