Sequence Events RFC

[jasongitmail]

No description provided.

[mitschabaude]

Sequence Events RFC

Part 1: Motivation

Like events, sequence events represent arbitrary information that can be passed along with a zkApp transaction. However, they have one additional feature: they are committed to on chain. We call that commitment the "sequence state"; it is a field on every zkApp account. Roughly, the sequence state is a hash (Merkle list) of the entire history of sequence events that have been posted to the account so far. Like with other account fields, you can set a precondition on the sequence state.

Being able to set this precondition means that you can use previously emitted sequence events inside your smart contract method. To do this, you pass in a list of sequence events and an old sequence state hash, and recompute the new (current) sequence state hash inside the circuit. Then, you set this new sequence state hash as a precondition. Thus, you prove that the sequence event list you have is actually the same list of sequence events that were posted on-chain -- in the same order -- since the old sequence state hash.

@mrmr1993 designed this as a clever mechanism to circumvent the problems with concurrent state updates in zkApps.

Let's state the problem first: Say we have a zkApp that wants to update its state in each user interaction, such that the new state depends on the old state plus the interaction inputs. (This probably applies to most zkApps!) The naive way is to directly update on-chain state in every interaction. To compute the new state, however, we have to use the current state. To prove that we're really using the current state that's on-chain, we have to set a precondition on the current state. The problem: If multiple users send their transactions to the same block, without knowing from each other, they will set the same precondition on the current state, and both will also update that state. Thus, every transaction after the first one has an outdated precondition on it, and is rejected.

Let's picture this with a simple example, where the state is just a number and the user interactions are trying to increment that number by 1:

transaction                             zkapp account after transaction
{ state: 0, newState: 1 }  ---------->  { state: 1 }
{ state: 0, newState: 1 }  -----X---->  { state: 1 }  // transaction fails, wrong state precondition

Two users sent an "increment" transaction, but the on-chain state was only incremented once!

Here's how we can solve this: Assume that we can represent our state updates as sequence events, such that the order in which those updates are applied doesn't matter (this is typically possible; more on that later). Then, we could write our smart contract so that normal users do not update on-chain state. They just emit a sequence event instead. No precondition, and no conflicts with other transactions!
Then, after a couple of transactions, we would have the following: An untouched on-chain state, and some emitted sequence events. Those sequence events are like "pending updates".

transaction                   zkapp account after transaction
{ event: INCR }  ---------->  { state: 0, events: [INCR] }
{ event: INCR }  ---------->  { state: 0, events: [INCR, INCR] }

The two user transactions are not conflicting -- both get applied, and they end up creating an account with two "increment" events.

(Note: To simplify the explanation, here I am just picturing sequence events as "events that are stored on chain". This is not precisely what happens, but is a reasonable abstraction, since we can prove that certain events were stored on chain.)

The idea here is that the on-chain state is slightly lagging behind the state implied by the current list of events. To bring the on-chain state up to date with the list of events, we have another smart contract method, which we could call the "rollup method".
What it does is:

• Prove that we have a list of sequence events that was sent to the chain (since some specific index)
• Prove that we have the current on-chain state (i.e., use a state precondition)
• Inside the circuit, apply those sequence events one after another to the old state, to produce the new state
• Set the new state to what you computed

Let's add that rollup transaction to the picture above:

transaction                            zkapp account after transaction
{ event: INCR }           ---------->  { state: 0, events: [INCR] }
{ event: INCR }           ---------->  { state: 0, events: [INCR, INCR] }
{ state: 0, newState: 2 } ---------->  { state: 2, events: [INCR, INCR] }

Now the on-chain state reflects all the updates that happened so far! 🎉

The rough idea is that anyone would be able to send rollup transactions, so it's censorship-resistant; but probably the zkApp developer would want to set up some service that monitors the chain and makes sure to update state from time to time.

Note: If two people would send rollup transactions at the same time, one of them would fail. But this doesn't matter, since no data is lost -- all the data about actual state updates is in the list of events, which can always be added without conflicts.

Another note: The pictures above may make it seem like someone could now run the rollup transaction again, using the two existing events as inputs again to update the state to the corrupted value of 4. However, it's not hard to prevent this in the real implementation.

[mrmr1993]

However, it's not hard to prevent this in the real implementation.

Explicitly: by burning an appState entry to keep track of the most-recently-applied sequence event state, and adding that into the precondition.

Great write up, thanks so much @mitschabaude!

[mitschabaude]

Sequence Events RFC

Part 2: API

A bare-bones sequence events API could look like this:

// property that has to be set on `SmartContract`
sequenceEvent: AsFieldElements<T>; 

// emit a sequence event
this.emitSequenceEvent(event: T): void;

// compute the new sequence state (i.e., a hash) from a previous state and an array of events
this.updateSequenceState(stateHash: Field, events: T[]): Field;

// fetch array of arrays of sequence events (inside the circuit, so pre-fetched and not async)
// each of the arrays are the sequence events emitted by one party.
// they have to be fed to `updateSequenceState` one by one
this.getSequenceEvents({ fromStateHash: Field, toStateHash?: Field }): T[][];

Disclaimer: I didn't implement that API, and will explain why in a minute.
Still, here are some notable considerations which will turn up in any API:

• There are no different types of sequence events (as with events), there's just one type. This is because in the typical use case sketched above, users have to apply those events to a state one by one to compute a new state. This is hard to do in a circuit, in a static way, if the type can have any of a number of meanings. I think it's much better to just remove that headache for users by just giving them one possible event type. If they need multiple "kinds" of events, they will naturally build some kind of enum into that single type themselves, but in a way which is probably easier to deal with in a static circuit.
• The natural data structure to store sequence events is not an array of events T[], but an array of arrays T[][]. Each of the arrays are the events emitted by one party. Those need to be fed to updateSequenceState in one chunk to get the next sequence state hash. Thus, we can't store them as a flat array, we need to preserve the chunk structure to be able to compute the correct sequence state hashes later.

In the current implementation (#274), I decided to skip exposing this low-level API, and instead reached for a slightly higher level of abstraction. The reason is that when I implemented the "rollup transaction" described above, it was much harder than anticipated. The complication is that the number of sequence events you want to roll up in one transaction should be dynamic, so you can be flexible with how frequently that method is called. Also, you might have several smart contract methods which emit different numbers of events. So you end up with a computation that's dynamic-size in two dimensions, which has to be fit into a static circuit.

I think most users just wouldn't have an idea on how to do this -- which means we need to give them a function which abstracts it away: which takes the dynamic-size events list and handles rolling them up. However, part of the rolling up logic is user-defined. E.g., in the example with the "increment" events above, rolling up meant to count the increment events. But that's application-specific, so users need a general-purpose framework for defining this kind of update logic themselves.

Here's what I came up with (already implemented):

On a SmartContract, you can set a property called stateUpdate, which takes three parameters:

• A type for a state (not necessarily related to your on-chain state, but in many cases would resemble it)
• A type for an update to that state (i.e., the sequence event)
• An user-defined apply method with the signature (state: S, update: U) => S, i.e., taking an old state plus an update, and producing a new state.

Here's the code for our "counter" / "increment" example:

class CounterZkapp extends SmartContract {

  stateUpdate = SmartContract.StateUpdate({
    state: Field,
    update: Field,
    apply(state: Field, _update: Field) {
      return state.add(1);
    },
  });

  // ...
}

In this particular case, the value of the update isn't even needed in the apply logic, but I think you get an idea how to use this in general. As usual, the types for state and update can be general circuit values, instead of Field.

The stateUpdate field now has the methods on it to interact with sequence events. There are currently two of them. They have two generic type parameters -- S (the state type) and U (the update type).

this.stateUpdate.emit(update: U): void;

this.stateUpdate.applyUpdates({ state: S, stateHash: Field, updates: U[][] }): { state: S, stateHash: Field });

applyUpdates is what the "rollup method" uses to apply state updates. It handles all the complicated things -- hashing, adding the sequence state precondition, computing the new state using your custom apply method, all for dynamically-sized updates. The stateHash in the applyUpdates method is of course just the "sequence state" that's stored on the zkApp account. The reason that it is exposed to users in this way is that you need it to refer to a particular point in the history of updates (you can't use the state itself for that, because different points in the history can have the same state). To use applyUpdates the first time, you'll also need the initial state hash. It's always the same value, and available via SmartContract.StateUpdate.initialStateHash.

A fully-fledged example is here: https://github.com/o1-labs/snarkyjs/blob/fc4dcf7ad5293e6f89ec5f8f4560e5d2a09bf48e/src/examples/state_update_rollup.ts

Further remarks:

• This API doesn't use the term "sequence events" at all. I just found no place to introduce that word, and thought it would be confusing, so I went with the more familiar terminology of "states" and "updates". As usual, comments are welcome on the naming!
• We will also need a fetch method of course, it's not implemented but could be

this.stateUpdate.getUpdates({ fromStateHash: Field, toStateHash?: Field }): U[][];

• Different than for normal events, this time I use a function call to declare the state update structure: stateUpdate = SmartContract.StateUpdate( ... ). This makes typing much, much better -- in fact, normal events are essentially untyped, while this is typed precisely. I think that's easily worth adding the bloat in API.
• This API makes absolutely no assumptions about what you do with the state. You can store it on chain directly, but I didn't want to prescribe that, to retain the full flexibility that sequence events give you. In many cases, for example, on-chain state could be derived from the rolled-up state instead of equal to it; or only a part of on-chain state could be computed from it; etc etc.

[jasongitmail]

Thanks Gregor!

Some questions on pt 1 CC @mrmr1993

transaction zkapp account after transaction
{ event: INCR } ----------> { state: 0, events: [INCR] }
{ event: INCR } ----------> { state: 0, events: [INCR, INCR] }
{ state: 0, newState: 2 } ----------> { state: 2, events: [INCR, INCR] }

• What happens to the first two tx's if a rollup tx does not arrive by the time the next block is created? How long will they remain in the mem pool until rolled up & under what conditions would they be evicted?
• What is max # of sequence events per zkApp that the Mina node will retain in the mem pool? How does the node handle a situation where the "queue" is full, if that can occur, and another tx containing a sequence event arrives?
• Are sequence events available via Mina GraphQL API on Berkeley?
• What happens if a rollup tx is received and then subsequent tx's containing sequence events are received? Will their precondition be invalid and subsequent tx's will have their precondition fail until the next block & they'd need to generate a new tx based off the new state? I suppose that depends on what precondition they choose. Or do zkApps have a way to know about this intermediate state after the rollup via the GraphQL API, implying that subsequent tx's containing sequence events and rollup tx's could be accepted into the same block?

There are no different types of sequence events (as with events), there's just one type. This is because in the typical use case sketched above, users have to apply those events to a state one by one to compute a new state. This is hard to do in a circuit, in a static way, if the type can have any of a number of meanings. I think it's much better to just remove that headache for users by just giving them one possible event type. If they need multiple "kinds" of events, they will naturally build some kind of enum into that single type themselves, but in a way which is probably easier to deal with in a static circuit.

Makes sense.

[mimoo]

very well written! some questions/thoughts on part 1:

• my way of thinking about this: the "sequencer" (the agent that orders transactions to be rolled up) is on-chain, built as part of the zkapp. The downside, if it is one, is that the sequencer is not cleanly separated from the rollup/protocol.
• this translates into an overhead for every application: you need to wait twice. Once for the event to be emitted, then for the rollup to happen
• I guess no sequence events can be lost when you apply them in a rollup?

[bkase]

Thanks @mitschabaude ! This is a great write-up and I really like your StateUpdate abstraction. But I think we should take it even further!

What we have here is really close to the Elm Architecture-style state management. This is a really nice way to deal with state machines in an application and have really nice properties, so it makes sense that it comes up when we're trying to model our state machine here!

By the way, what we really have is a scan over an implicit infinite stream of actions that are aggregated in chunks -- this is exactly the same problem that came up when processing transactions in the Mina Protocol with Snark Workers: https://minaprotocol.com/blog/fast-accumulation-on-streams except in the transaction processing case it was important that the "actions" themselves were monoidal (so we could combine them in a tree) and there wasn't a commutativity requirement (see below).

This should be familiar to TypeScript/JavaScript web developers through its instantiation via the Redux library or more "recently" (does this age me?) via the useReducer hook in React.

Not only is it important to call this out in documentation because it will help people reason about how to model their state-update logic, but I think we should try to push the API to feel more like Elm/useReducer/Redux/etc. This actually doesn't meaningfully change what you've proposed too much.

Naming

Something that immediately falls out is the nomenclature:

• sequence events or updates become actions
• emit becomes dispatch or send
• applyUpdates becomes reduce (or just update if we take from Elm)

We're missing a nice way to define the initial state or init or z

Commutativity Property

What's unique here and slightly different than a typical Elm Architecture implementation is that actions are deferred from being reduced immediately against the state and that you typically want your state machine to allow actions to commute ie (given a left-associative update $\circ$):

$$\begin{eqnarray} \forall a,a' &\in& \texttt{action} \nonumber \\ \forall s &\in& \texttt{state} \nonumber \\ s \circ a \circ a' &=& s \circ a' \circ a \nonumber \\ \end{eqnarray}$$

With a quick google, I haven't found any prior art for any "Commutative Elm Architecture" or "Reducers with Commutative Actions", but I think this doesn't actually impact the way the API is defined -- it's just something developers need to think about when they're designing their state and reduce logic.

Instantiation and dispatch

Rough proposal:

reducer = SmartContract.Reducer({
  stateType: Field,
  actionType: Field,
  initialState: new Field(0), // see below, this assumes we do state management
  reduce: (state: Field, _update: Field) {
      return state.add(1);
  }
})

//...

this.reducer.dispatch(action: Action): void ;

Fetching and reducing

As far as managing fetching and reducing the actions (ie "settling the rollup"): In some ways, I really like the "rollup" nomenclature because it truly is performing a similar settling operation as any rollup, but in other ways there will be a lot of different rollups floating around given that a lot of the time the smart contract will be a zk-rollup on another dimension simultaneously.

Alternatively, we can just stick with the Elm Architecture / Redux / useReducer world and say something like this.reducer.reduce; I'm partial to scan since we're not really doing a proper reduce, but I guess the world has decided to use reduce in this case.

The other question that comes to my mind is: To what extent should we manage the state for people? What you've proposed above is explicitly not managing it at all. The developer needs to decide where to store the state if anywhere and remember which actions they have processed so far. Alternatively, we could manage the state for the developer -- potentially via some mechanism where you can say if you want it in on-chain state, off-chain via a merkle root, or somewhere else. I haven't fully thought this through, but I think this would make it a lot easier to use this tool in their zkApps.

[mitschabaude]

@bkase I love the idea of using "reducer" terminology! reducer / reduce / dispatch will immediately get developers in the right mindset and give them something familiar. Much better than "stateUpdates" / "apply"! I prefer reduce over scan since its better-known and clearer IMO (I didn't know scan at least).

Re: should we manage state -- when thinking more about the use cases for sequence events, I discovered what feels like an important use case, that isn't covered well by having a single stateType and a single reduce / "apply" function. So my answer (elaborated below) is that we shouldn't manage state, and make the API even more flexible than proposed before.

Namely, there's the case that

• the potential length of the history of sequence events is reasonable; say in the tens or hundreds
• there is no single neat / small-ish state implied by that history which captures the history well

Example: Let's say a simplified poker zkApp creates events of the form {player: PublicKey, bet: UInt64, round: Field}, i.e., recording the bets that various players make during the game. And the zkApp might want to reason about things like "did player X make a bet in the current round? if yes, how large was that bet?".
If you try and capture that in a single state type, you end up with something huge, e.g. { players: [Alice, Bob, ...], rounds: 3, didBetInRound: [[true, false, ...], [false, ...], ...], betSizeInRound: [[100, 0, ...], [0,...], ...] }, which is annoying and inefficient to process in a circuit. Instead, if you can make your state specific to the current player and the current round, the answer to your reduce query is small: { didMakeBet: true, betSize: 100 }.

So, there are two points here:

• the reduce operation may have parameters that depend on the current run of the smart contract method. This doesn't work if it is specified beforehand at the top level of the smart contract
• instead of storing the state returned by reduce either on-chain of off-chain, it might make sense to just use it within the current smart contract method run, and discard it.

Basically, the list of events themselves is the state in this use case, and it's important to reason over that list of events inside smart contracts, so we have to use sequence events instead of normal events.

As another point, there might be other smart contract methods that run an entirely different query on the list of events, so that the stateType can be mutliple different things in different reduce calls. In the example above, other queries could be

• in which round are we?
• which players' turn is it?

To offer such flexibility, we should only declare the event type, i.e. actionType, as part of the top-level reducer, and pass in the (state, update) => newState callback, as well as the stateType and initial state, as arguments to reducer.reduce.

Here's how that could look in a full example -- the counter example we already discussed.

const INCREMENT = Field.one;

class CounterZkapp extends SmartContract {
  reducer = SmartContract.Reducer({ actionType: Field });

  @state(Field) counter = State<Field>();
  // we also need the stateHash in on-chain state to know where in the action history we are
  @state(Field) stateHash = State<Field>();

  @method incrementCounter() {
    this.reducer.dispatch(INCREMENT);
  }

  @method rollupIncrements() {
    // get on-chain state & state hash, add preconditions for them
    let counter = this.counter.get();
    this.counter.assertEquals(counter);
    let stateHash = this.stateHash.get();
    this.stateHash.assertEquals(stateHash);

    // fetch list of actions
    let actions = this.reducer.getActions({ fromStateHash: stateHash });
    // state type
    let stateType = Field;

    // reduce takes not only the actions and initial state / hash as parameters (as before),
    // but also the stateType and reduce callback
    let { state: newCounter, stateHash: newStateHash } = reducer.reduce(
      actions,
      stateType,
      (state: Field, _action: Field) => {
        return state.add(1);
      },
      { state: counter, stateHash }
    );

    // store the new state / stateHash on chain
    this.counter.set(newCounter);
    this.stateHash.set(newStateHash);
  }
}

Note: In this example, we do have just one stateType and just one (state, update) => newState callback. And we do just store the reduced state on-chain. But I argue that doing this within a more flexible API is still quite straight-forward. It's a pattern for how to use reducer that can be easily copy-&-pasted and adapted to similar use cases. Still, we offer the full list of use cases people might have for sequence events.

For reference, this is the proposed API:

reducer = SmartContract.Reducer({ actionType: AsFieldElements<A> });
  
this.reducer.dispatch(action: A): void;

this.reducer.reduce<S>(
  actions: A[][],
  stateType: AsFieldElements<S>,
  reduce: (state: S, action: A) => S,
  initial: { state: S, stateHash: Field }
): { state: S, stateHash: Field };

// to be implement later
this.reducer.getActions({ fromStateHash?: Field, toStateHash?: Field }): A[][];

The only part I'm not very confident about is the naming of the stateHash parameter and return value in reducer.reduce. That hash actually represents the history of actions, and has no connection to the state; so the naming "stateHash" might be confusing if there's now the potential to use reduce with different types of states.

Maybe it should be actionsHash? reducerHash? actionsCommitment?

[mitschabaude]

@jasongitmail

What happens to the first two tx's if a rollup tx does not arrive by the time the next block is created? How long will they remain in the mem pool until rolled up & under what conditions would they be evicted?
What is max # of sequence events per zkApp that the Mina node will retain in the mem pool? How does the node handle a situation where the "queue" is full, if that can occur, and another tx containing a sequence event arrives?

Just to clarify, the first two txns modify the account state immediately. They update the "sequence state" on the account, which is a hash of all sequence events so far; so the fact that these two events happened will be forever recorded on chain, even if there is no rollup tx at all. Not sure if that answers your questions -- I think we don't really depend on the txns being in the mempool.

We do depend on being able to fetch the list of events from somewhere, to be able to rollup. We could fetch recent events from the Mina node, but they probably will get unavailable after some time (don't know the technical details). Or, we could fetch them from an archive node, where they will be available forever; or keep track of them on our own.

Are sequence events available via Mina GraphQL API on Berkeley?

I don't think they are, currently

What happens if a rollup tx is received and then subsequent tx's containing sequence events are received? Will their precondition be invalid and subsequent tx's will have their precondition fail until the next block & they'd need to generate a new tx based off the new state? I suppose that depends on what precondition they choose. Or do zkApps have a way to know about this intermediate state after the rollup via the GraphQL API, implying that subsequent tx's containing sequence events and rollup tx's could be accepted into the same block?

Excellent question! Event-emitting txns don't have a precondition on them, so they can't become invalid. But the rollup txn has a precondition on the current sequence state, so it's valid to ask: What happens if more event-emitting txns sneak in while the rollup txn is being prepared -- will the rollup txn have an outdated precondition?

The answer is no, but requires digging into the details:

The on-chain sequence state field actually stores sequence state hashes for the 5 most recent slots that contained sequence events, and the sequence state precondition is accepted if it matches any of these 5.

So, say that an account has the following sequence state hashes at the end of a slot: [s1, s2, s3, s4, s5], and we know these were all included in a block already.
Let's say we're now in a subsequent slot, where we want to construct a rollup tx but at the same time people are submitting new events.

The first of the new events will shift the on-chain sequence state to the right, and add a new element, which represents the current slot:
[sNEW, s1, s2, s3, s4]
Notice that the s5 state was thrown out, it's no longer a valid precondition.

Now, if another new event gets submitted within the same slot, it doesn't shift the states to the right again, but also updates the first entry:
[sNEW_modified, s1, s2, s3, s4]

So the state s1, which represents the state at the end of the most recent block, will still remain a valid sequence state precondition for five additional slots after that block. Since a slot is 3 minutes, that are 15 minutes (in the worst case, where all those slots contain blocks with sequence events).

So, what do we do if we want to create a rollup txn?

• We look at the sequence state from the last completed block, s1 in this case. We fetch sequence events up until that state, and rollup those events with s1 as the precondition
• The newly submitted events, which all modify sNEW, don't bother us, since we are easily able to construct the rollup txn and submit it within 15 minutes, so we know s1 will be a valid precondition
• Our transaction gets accepted, independent of how many events were submitted around the same time

It only ever makes sense to refer to the sequence event state at the end of a completed block, because that's when the order of sequence events has been fixed. It doesn't make sense to target the block that's currently being constructed, and guess the order that the events in there will be applied.

@mimoo

I guess no sequence events can be lost when you apply them in a rollup?

Yes, if we do it like in my code example in the last post, no events can be lost -- since the smart contract method forces us to start at the stateHash that's stored on-chain, and which was the result of the last update

this translates into an overhead for every application: you need to wait twice. Once for the event to be emitted, then for the rollup to happen

That's a good point. Maybe we want to encourage a framing where the pending events are also considered part of the current state, and UIs display it as such, because it's basically guaranteed that they will eventually end up in on-chain state. Not sure if that's smart though...
Otherwise it could be just "wait for two blocks instead of one" if the zkApp developer is willing to pay for maximally frequent rollups, or makes users pay for them

[bkase]

I really like the latest version of this 👍 . I like actionsHash or actionsCommitment with some associated doccomments that explain that it's the merkle hash of a list of actions I think?

[bkase]

That's a good point. Maybe we want to encourage a framing where the pending events are also considered part of the current state, and UIs display it as such, because it's basically guaranteed that they will eventually end up in on-chain state. > Not sure if that's smart though...
Otherwise it could be just "wait for two blocks instead of one" if the zkApp developer is willing to pay for maximally frequent rollups, or makes users pay for them

I like this idea and I think it's pretty safe as you said. Depends on the application, but for most the existence of a sequence event is good enough I think.