Mina Action & Reducers Guide: Let’s take a closer look

ZkNoid
ZkNoid
Published in
8 min readOct 9, 2024

--

In our previous article, we described the challenges of concurrent state updates in Mina zkApps. Mina addresses these issues with actions and reducers, tools that allow processing multiple transactions at once, finalizing the state change later. Today, we’ll dive deeper into actions and reducers, exploring how actions are stored and updated, as well as the role and functionality of reducers.

Actions Merkle list

A Merkle list can be seen as a simple list of elements with an additional property, the root, which helps to prove the existence of every list entry. Merkle lists are useful when you need to store an array and then process it sequentially, which is the case with actions. Let’s explore how we can operate on a Merkle list.

Creating merkle list

To create a Merkle list, you need to call the create function and provide it with a nextHash function and an initial root value. These parameters are optional; if omitted, the nextHash defaults to hash of prev root and new value without a prefix and an initial value of 0.

import { Field, MerkleList, Poseidon, CircuitString } from 'o1js';

const emptyHash = Poseidon.hash([Field(12345)]);

class MyList extends MerkleList.create(
Field,
(hash, x) => Poseidon.hashWithPrefix('my-own-prefix', [hash, x]),
emptyHash
) {}

const instance = MyList.empty();

console.log(`${instance.hash.toString()} = ${emptyHash.toString()}`);
// true

When updated, the Merkle list root mutates according to the nextHash function provided during creation. In our example, it is the hash of the previous root and the new value with some prefix.

instance.push(Field(1));
instance.push(Field(2))

const instanceIterator = instance.startIterating();
while (!instanceIterator.isAtEnd().toBoolean()) {
console.log(instanceIterator.next().toString());
}
// 1
// 2

Merkle list of structs

To store a Merkle list of structs, you need to update the nextHash function to accept a struct as input. Then, convert the struct to fields using the Struct.toFields method. And use previous root and obtained values as inputs for hashing function.

class MyStruct extends Struct({
v1: Field,
v2: Field,
}) {}

const nextStructHash = (hash: Field, x: MyStruct): Field =>
Poseidon.hashWithPrefix('my-own-struct-prefix', [
hash,
...MyStruct.toFields(x),
]);

class MyStructList extends MerkleList.create(
MyStruct,
nextStructHash,
emptyHash
) {}

let s = new MyStruct({
v1: Field(1),
v2: Field(2),
});

const structListInstance = MyStructList.empty();

structListInstance.push(s);

const structIterator = structListInstance.startIterating();
while (!structIterator.isAtEnd().toBoolean()) {
const value = structIterator.next();
console.log(`{v1: ${value.v1.toString()}, v2: ${value.v2.toString()}}`);
}
// {v1: 1, v2: 2}

Multidimensional Merkle List

It’s also possible to store a multidimensional Merkle list, where the elements of one Merkle list are the roots of other Merkle lists.

class MyInnerList extends MerkleList.create(Field) {}

const nextOuterHash = (hash: Field, x: MyInnerList): Field =>
Poseidon.hashWithPrefix('my-own-struct-prefix', [hash, x.hash]);

class MyOuterList extends MerkleList.create(MyInnerList, nextOuterHash) {}

let outer = MyOuterList.empty();
let inner1 = MyInnerList.empty();

inner1.push(Field(1));
inner1.push(Field(2));

outer.push(inner1);

let inner2 = MyInnerList.empty();

inner2.push(Field(3));
inner2.push(Field(4));

outer.push(inner2);

const outerIterator = outer.startIterating();

while (!outerIterator.isAtEnd().toBoolean()) {
const inner = outerIterator.next();
const innerIterator = inner.startIterating();
let values = [];
while (!innerIterator.isAtEnd().toBoolean()) {
values.push(innerIterator.next().toString());
}
console.log(values);
}
// [ '1', '2' ]
// [ '3', '4' ]

This is especially important fo because Mina uses a two-dimensional Merkle list to store actions. The inner dimension stores actions for a single account update, while the outer dimension stores the Merkle list roots for each account update.

Iterating Over a Merkle List

To iterate over a Merkle list, you can use an iterator as shown earlier.

const instanceIterator = instance.startIterating();
while (!instanceIterator.isAtEnd().toBoolean()) {
console.log(instanceIterator.next().toString());
}

However, this can only be done off-chain because only the root is stored on-chain. To prove the existence of a value in the list, you must provide a path from the root to the value. The path length grows linearly with the number of elements, which makes it unsuitable for general-purpose storage. For general-purpose storage, a Merkle tree is preferable because the path length is constant and equals the tree height.

class MyList2 extends MerkleList.create(Field, nextHash, emptyHash) {}
const list = MyList2.empty();
const target = Field(777);
list.push(Field(123));
list.push(Field(456));
const rootBeforeTarget = list.hash;
list.push(target);
list.push(Field(789));

const checkExistance = (
nextHash: (hash: Field, x: Field) => Field,
rootBeforeElement: Field,
element: Field,
path: Field[],
onchainRoot: Field
): Bool => {
const calculatedRoot = [element, ...path].reduce(
(acc, val) => nextHash(acc, val),
rootBeforeElement
);

return calculatedRoot.equals(onchainRoot);
};

let res = checkExistance(
nextHash,
rootBeforeTarget,
target,
[Field(789)],
list.hash
);

if (res.toBoolean()) {
console.log('Success');
}
// Success

Actions Merkle list

Let’s take a closer look at how a Merkle list is created when getActions is called. You can find the code here. and Action struct here.

const Actions = {
// same as events but w/ different hash prefixes
empty(): Events {
let hash = emptyHashWithPrefix('MinaZkappActionsEmpty');
return { hash, data: [] };
},
pushEvent(actions: Events, event: Event): Events {
let eventHash = hashWithPrefix(prefixes.event, event);
let hash = hashWithPrefix(prefixes.sequenceEvents, [
actions.hash,
eventHash,
]);
return { hash, data: [event, ...actions.data] };
},
fromList(events: Event[]): Events {
return [...events].reverse().reduce(Actions.pushEvent, Actions.empty());
},
hash(events: Event[]) {
return this.fromList(events).hash;
},
// different than events
emptyActionState() {
return emptyHashWithPrefix('MinaZkappActionStateEmptyElt');
},
updateSequenceState(state: Field, sequenceEventsHash: Field) {
return hashWithPrefix(prefixes.sequenceEvents, [
state,
sequenceEventsHash,
]);
},
};

const Action = reducer.actionType;
const emptyHash = Actions.empty().hash;
const nextHash = (hash: Field, action: A) =>
Actions.pushEvent({ hash, data: [] }, Action.toFields(action)).hash;

class ActionList extends MerkleList.create(
Action as unknown as ProvableHashable<A>,
nextHash,
emptyHash
) {}

class MerkleActions extends MerkleList.create(
ActionList,
(hash: Field, actions: ActionList) =>
Actions.updateSequenceState(hash, actions.hash),
// if no "start" action hash was specified, this means we are fetching the entire history of actions, which started from the empty action state hash
// otherwise we are only fetching a part of the history, which starts at `fromActionState`
// TODO does this show that `emptyHash` should be part of the instance, not the class? that would make the provable representation bigger though
config?.fromActionState ?? Actions.emptyActionState()
) {}

Here, we have an ActionList that contains actions from one account update, have initial value of emptyHashWithPrefix('MinaZkappActionsEmpty') (its just hashed string), and nextHash is some hash of previous root and event hash.

MerkleActions is a 2 dimensional list of ActionLists, with initial value emptyHashWithPrefix('MinaZkappActionStateEmptyElt') , and with nextHash equals to function that hash prevRoot of list with root of ActionList.

Action state

Ordinary nodes do not store actions directly. Instead, they store the hash of the Merkle list of actions to prove transactions. This value can be received on-chain using:

this.account.actionState.getAndRequireEquals()

Each zkApp has this value, which is updated once at the end of block processing rather than after every transaction in a block. This is because the action state is a hash of a Merkle list of Merkle lists. Hence, two transactions in a single zkApp in same block will have the same actionState, even if they dispatch some actions.

Only archive nodes store all actions themselves. Therefore, to interact with actions in a zkApp, you must:

  1. Get actions from archive node
const Network = Mina.Network({
mina: 'https://api.minascan.io/node/devnet/v1/graphql',
archive: 'https://api.minascan.io/archive/devnet/v1/graphql',
});
Mina.setActiveInstance(Network);

const zkApp = new MyZkapp(zkAppAddress);

const actionLists = await zkApp.reducer.fetchActions({
fromActionState,
endActionState
});

2. Somehow prove that these actions are valid to use it in transaction.

One feature of actions is that nodes store not a single hash but five of them. This can be observed on Minascan:

These are not hashes for a single action state, but one actual action state and four archived ones for previous action states. So in a block where actions are dispatched, the action state changes as follows:

actionState[4] = actionState[3];
actionState[3] = actionState[2];
actionState[2] = actionState[1];
actionState[1] = actionState[0];
actionState[0] = newActionState;

Why Five States?

When you use the actionState value of a contract, it creates a precondition based on that value. If the actionState changes while you are generating and sending your transaction, it could fail due to an unsatisfied precondition.

The design of actions within the Mina protocol considers two key factors:

  1. Frequent Dispatch of Actions: Actions are designed to be used with functions that are called frequently, to solve their concurrency issues.
  2. Challenging Proofs for Action-Related Transactions: Transactions involving actions are harder to prove because they require action proofs. As a result, these transactions take longer to prove, increasing the likelihood that the on-chain actionState might change during the proving process.

To address these challenges, the Mina protocol stores five versions of the actionState. The precondition for a transaction includes not just the most recent value but also the four archived states. This ensures that the precondition is satisfied as long as the actionState used is at least within five blocks of the current state. This gives you approximately 15 minutes to compute and submit the proof, which is generally sufficient.

Caution: Due to this mechanism, you cannot make any assumptions about which specific actionState you are working with. For instance, you cannot guarantee that all actions have been processed, as the last four blocks of actions might be skipped. To ensure all actions are processed, you would need to implement a marker action that indicates that all preceding actions have been processed.

Reducers

Reducers are functions that take an array and convert it into a single value. In the context of zkApps, reducers process a list of actions and perform a computation based on them. It’s important to note that a reducer does not alter the actionState in any way.

There are two ways to implement reducers in zkApps:

  1. Using the Reducer API: The official Mina protocol documentation provides a Reducer API that allows you to reduce actions to a single value according to specific rules. An example of its usage can be found in the reducer-composite.ts file on GitHub. However, this approach has two significant drawbacks:
  • Limited Customization: The Reducer API is not very customizable, making it challenging to implement complex logic.
  • Known Issue with Large Action Sets: Currently, the Reducer API is not reliable when reducing more than 32 actions, as it fails to handle them. This is a known issue, and the Mina team is working on a fix.
  let counter = this.counter.getAndRequireEquals();
let actionState = this.actionState.getAndRequireEquals();

// compute the new counter and hash from pending actions
let pendingActions = this.reducer.getActions({
fromActionState: actionState,
});

let newCounter = this.reducer.reduce(
pendingActions,
// state type
Field,
// function that says how to apply an action
(state: Field, action: MaybeIncrement) => {
return Provable.if(action.isIncrement, state.add(1), state);
},
counter,
{ maxUpdatesWithActions: 10 }
);

// update on-chain state
this.counter.set(newCounter);
this.actionState.set(pendingActions.hash);

2. Writing a Custom Reducer:
You can write a custom reducer, which is more flexible and can handle more complex logic. Essentially, a custom reducer reconstructs the Merkle list root and performs computations based on it. This approach allows you to implement logic of any complexity and can mitigate issues with too many actions by using recursive proofs or top-down execution.

   @method async reduceTickets(reduceProof: ReduceProof) {
// Check proof validity
reduceProof.verify();

let lastProcessedState = this.lastProcessedState.getAndRequireEquals();

// Check that initial state on contract is equal to state on proof
lastProcessedState.assertEquals(
reduceProof.publicOutput.initialState,
'Initial state is not match contract last processed state'
);

// Check that actionState is equal to actionState on proof
this.account.actionState.requireEquals(
reduceProof.publicOutput.finalState
);

// Update onchain values
this.lastProcessedState.set(reduceProof.publicOutput.finalState);
}

Conclusion

Today, we explored how actions and reducers work in zkApps. Understanding these concepts will be crucial as we implement actions and reducers in future zkApps.

In the upcoming articles, we will dive into more practical topics, including:

  • Writing contracts with reducers and implementing two versions of custom reducers.
  • Using batch reducer.
  • Using off-chain storage.

Website | Docs | Twitter | Discord | Telegram | Medium

--

--

ZkNoid
ZkNoid

Published in ZkNoid

ZkNoid is the home for provable gaming. On the platform you can try yourself the cutting edge games utilizing Zero-Knowledge proofs or build one using the provided infrastructure. https://www.zknoid.io/

ZkNoid
ZkNoid

Written by ZkNoid

Platform for games with provable game process based on Mina protocol and o1js. Docs – docs.zknoid.io. Github – github.com/ZkNoid. Twitter – https://x.com/ZkNoid

No responses yet