Recursive reduce()

[mitschabaude]

We should make it easier to roll up updates to a Merkle tree with actions /.reducer.
Ideal (IMO) architecture is laid out here: #659 (comment)

EDIT: This issue is now specifically about breaking the relationship between number of processed actions and circuit size, to allow reducers to process an arbitrary amount of actions by default

[Trivo25]

Proof Requests and Recursive Reducer

Context

Actions and reducers influence the circuit size of a smart contract significantly. The reducer is designed to process a fixed-size list of actions, with the default capacity set to 32 actions. This size can be user-defined. For each action in the list, a user-defined callback function is applied individually. This design imposes certain limitations, as actions must be processed in small batches, and the reducer's current architecture does not allow for runtime adjustments to accommodate a varying number of outstanding actions. Such a limitation could lead to potential issues for users. For instance, if the number of actions exceeds the pre-set limit, it could result in an "overflow" scenario. This overflow can trigger a deadlock in the reducer, rendering it unable to process any actions. This deadlock occurs because the precondition on the action state might not be met, preventing further processing and potentially causing operational disruptions in the smart contract's functionality.

Proposed solution

Leveraging recursion allows the development of a reducer capable of handling lists of actions of any length, circumventing the constraints imposed by circuit size. Through the use of ZkProgram, actions can be grouped into distinct proofs. These individual proofs can then be recursively verified, enabling a more efficient and seamless reducer function. This approach ensures that the reducer can manage an extensive number of outstanding actions efficiently, without the limitations associated. By implementing this recursive strategy, we significantly enhance the reducers flexibility and scalability,.

Hurdles

To streamline the process, o1js is designed to automatically create a proof for the recursive reduce function without the user needing to manage it themselves. It does this by requesting proofs in advance, before the smart contract gets proven. These proofs are then generated in advance and provided to the smart contract when needed. However, o1js can't handle proofs in an "on-the-fly" manner without asynchronous circuits and witness blocks, this means all proofs must be arranged beforehand. This setup ensures the user doesn't have to deal with the complexities of proof generation, making the whole process smoother and more user friendly.

Workaround and proposed API

Requesting proofs is beneficial not just for internal operations but also significantly enhances the developer experience when it comes to integrating ZkProgram into smart contracts.

Proof requesting

// ..
class RequestProof extends SmartContract {
  @method doSmth() {
    let proof = this.requestProof(MyProgram, 'baseCase', privateInputs, publicInputs);
    proof.verify();
    // ..
  }
}

Behind the scenes, o1js handles two key operations: it issues a lazy compile request and a lazy proof request. When users invoke SmartContract.compile(), o1js automatically compiles all ZkProgram dependencies required for proof generation. This ensures that all necessary components are prepared and available for use when needed.

Similarly, when a user is ready execute a smart contract interaction through tx.prove(), o1js follows a parallel process for the proof generation. It takes care of proving the ZkProgram method specified by the user and automatically provides the proof for verification. This change streamlines the process, removing the need for manual compilation and proof generation.

With the introduction of this feature, there will be no need for any further abstractions, and the current API will remain unchanged. This simplifies the integration process between smart contracts and ZkPrograms. Before this feature, users were required to supply both private and public inputs and generate the proof themselves prior to executing the smart contract. This approach could cause confusion and result in invalid ZkProgram proofs due to discrepancies in the state between when the smart contract was executed and when the ZkProgram was proved.

Impact on reducers

The reducer function get a new optional parameter, useRecursion, which defaults to false. When this feature is activated by enabling useRecursion, o1js automatically takes care of generating recursive reducer proofs. This enables the generation of a sufficient number of recursive proofs to process all outstanding actions, regardless of their size. o1js iwill also calculate the necessary number of recursive proofs needed and to verify them recursively.

For users, the introduction of this useRecursion argument is the only change they will notice. There might be an impact on the compile and proving times, which will vary based on the amount of recursive proofs required. This new feature aims to simplify the processing of actions without compromising on simplicity.

Unlocks

This feature opens the door to a set of new use cases, while simultaneously simplifying existing ones. Specifically, it proves to be advantageous for the development of off-chain storage solutions that leverage actions and reducers. By enabling recursion through the useRecursion argument, o1js facilitates the processing of an extensive number of actions without being constrained by the circuit size or batch limits. This capability is crucial for off-chain storage solutions, where the need to handle a large volume of actions efficiently and securely is key.

Prior art

A similar approach is already being utilised in OCaml.

[mitschabaude]

This is so slick, love it @Trivo25

Nit: I would probably pass the public and private inputs in the same way you would pass them in a function call, i.e. [publicInput?, ...privateInputs]