# Private shared state on Aztec, with Taceo's co-SNARKs

> Thanks to Roman, Franco, Florin @ Taceo, and Sean @Aztec for chatting about this with me this week, and for building a PoC.

Taceo enables a network of MPC nodes M1, M2, M3 (currently 3) to collaboratively generate a zk-snark (aptly termed "co-SNARKs"). This unlocks two cool features, with the 2nd feature being the most exciting:

1. **Outsourcing proving**. Generation of a zk-SNARK over a user's own private data can be _outsourced_ to the MPC network without leaking the user's data. I.e. None of the MPC nodes learn anything about the user's underlying data (under anti-collusion assumptions). This is a potentially-faster alternative to client-side proving, depending on the user's hardware and their trust model.
2. **Private shared state**. The MPC network can _generate_ data that _no one on earth knows_ (again, under anti-collusion assumptions). Furthermore, the MPC network can perform complex computations _over_ that data (data that no one knows) and generate a zk-SNARK of having done so.

This post won't go into the details of how co-SNARKs work; there are already good resources for that. This post talks about how co-SNARKs can enable private shared state on Aztec.

Ok fine, a very brief ELI5 of co-SNARKs is: All data -- be it data that's been generated _within_ the MPC network's circuits, or a user's private data that's been given to the MPC network -- is "secret-shared". Each MPC node gets a secret share of the data, meaning they don't have enough information to meaningfully interpret the underlying values being computed over. The MPC nodes can then generate a zk-SNARK over their secret-shared witnesses. They can then combine the results into a single "co-SNARK". The public inputs of this co-SNARK are useful, intelligible data that a co-SNARK verifier can interpret.

We can elaborate on the case of generating private shared state -- I.e. secret data being generated _within_ the MPC network, as hinted-to in bullet 2 above. Each MPC node generates randomness and secret-shares that randomness with the other MPC nodes. The nodes combine these randomness contributions in such a way that an underlying random value _exists_, but none of the MPC nodes knows it (a "private shared value"). A "private shared value" can become "private shared state" by committing to the value through a co-SNARK and persisting that commitment onchain.

## Using Taceo with Aztec

The cool thing about Taceo's co-SNARKs is that you can write a _normal Noir program_, and prove it via an MPC network.

Hey, Aztec's smart contracts and protocol circuits are written in Noir... can we co-SNARKify an entire Aztec tx?

An Aztec tx looks something like the following pic. The boxes are circuits. Boxes on the left are user-defined smart contract functions (circuits). Boxes on the right are protocol-defined kernel circuits.


There are two obvious areas here that we might want to co-SNARKify: a single function (B) or the entire private component of the Aztec tx (A).


### Proving System Incompatibility

But there's a snag... Taceo have done unbelievable work enabling co-SNARKs to be generated with an "UltraHonk" backend. But Aztec have squeezed out further proving optimisations, and all circuits in area A are actually generated with a "MegaHonk" (aka "Client-IVC") backend.

MegaHonk is like UltraHonk, but with some extra stuff: a DataBus (for efficiently ferrying data between two circuits), Goblinisation (for efficiently deferring non-native ellitic curve operations). In Aztec, both user-defined functions and protocol-defined functions make use of these extra MegaHonk features.

An UH-compatible circuit could technically be proven with MH [this claim needs validating], since UH-compatible circuit functionality is a subset of MH-compatible circuit functionality. UH-compatible circuits just don't try to use a databus or goblin transcript.

But Aztec's MH-compatible circuits do use the databus and goblin transcript, so the UH proving system would just break from these unfamiliar concepts.

This means Taceo's current co-SNARK stack cannot prove Aztec's private-land circuits.

So what can we do?

There are 3 obvious potential solutions. The first two would require more work, and whether they're worthwhile is a strategic question for the respective companies that I wouldn't presume to comment on here:
1. Taceo's stack gets updated to support MH.
2. Aztec's stack gets updated to provide the option of proving private-land circuits with an UH backend.
3. We leave Aztec and Taceo as they are, and feed Taceo's MPC network co-SNARK proofs (UltraHonk proofs) into Aztec smart contract functions.

Re Option 1, this would unlock cleaner private shared state coding patterns, as developers could write ordinary Aztec smart contracts. Entire Aztec txs (or individual smart contract functions) could be proven via MPC, which would be very nice indeed.

To elaborate on Option 2, Aztec would need to create another collection of Aztec kernel circuits which can be proven with UH. There are _tens_ of permutations of Aztec kernel circuit already, and they're all quite complex.

My kneejerk reaction is that Option 2 would effectively double the number of circuits to build, maintain, and audit. It's a potential doubling of the attack surface (bug surface) and so wouldn't be a popular approach.

On the other hand, in terms of MH-specific syntax used in the Aztec kernel circuits, it's probably only the special databus `call_data` keywords that prevent the code from being compilable to an UH circuit. With that in mind, maybe it's fairly easy to create a set of UH-compatible kernel circuits...

> _An example of the private kernel inner circuit. Notice the `call_data` keyword, which specifies to the compiler our desire to use the MH databus. I suppose this keyword could be programmatically toggled in/out of the code, as a way to generate two sets of Aztec circuits: an UH-compatible set and a MH-compatible set. We can certainly entertain the idea, but I'm not sure it'll be accepted._

### An approach that works today

Option 3 is doable today, and the Taceo guys (Roman, Franco, Florin) actually built a proof of concept this week (with design help from Sean and me).

Here's a pretty pic of what Option 3 looks like:


The MPC Network generates a co-SNARK π_mpc using the UltraHonk proving system. π_mpc is then fed into an Aztec smart contract function and recursively verified there. This is possible because Aztec smart contract functions have access to a Noir stdlib function called `verify_proof_with_type`, which can accept UltraHonk proofs.

Lovely, so we've circumvented our "proving system incompatibility" problem, by doing an extra "hop" of recursive proving.

### A general pattern

We've observed a general pattern that can be followed to persist and mutate this new concept of a "private _shared_ state" on Aztec using Taceo.

See this diagram.


Private _shared_ data is _only_ handled and "seen" by co-Noir programs (which actually means the underlying private _shared_ data is never actually _seen_ by anyone, because each node in the MPC network operates over random-looking secret-shares).

Within those co-Noir programs:
- New private shared data can be generated.
- Old Commitments to private shared state can be opened.
- Nullifiers to Old Commitments can be computed using the nullifier secret key of whomever the "owner" of the Old Commitment is deduced to be. (More on this in a sec).
- Private shared state can be modified.
- New Commitments to private shared state can be computed.

We can persist this data to Aztec through an Aztec smart contract function:
- Verify the co-SNARK and its public inputs.
- Push read requests of the Old Commitments to the kernels, to check their existence in the "note hashes tree".
- Push New Nullifiers to the kernels, for insertion, and to ensure the nullifiers don't already exist.
- Push New Commitments to the kernels, for insertion.

#### "Pushing" to kernels

Viewed at a low level, Aztec smart contracts are suprisingly dumb. The public inputs of _every_ Aztec smart contract function **must** conform to a very rigid layout. Here is a screenshot of that layout:


If a Noir program adheres to this public inputs layout, it _is_ effectively an Aztec smart contract function.

> Now, I'm over-simplifying a little bit, because a function can't just spit-out any old data to this `PrivateCircuitPublicInputs` struct: the data has to be _valid_ according to the rules of the Aztec network. This is where the higher-level "aztec_nr" language shines, because it provides rails for users, to ensure their functions will execute successfully on Aztec.

Those highlighted items are the ones we care about here. Above, when I described a smart contract function "pushing read requests / new nullifiers / new commitments", I meant pushing new elements to these arrays, so that the Aztec protocol circuits can deal with them for us automatically. (That is, perform old commitment merkle membership checks, nullifier non-inclusion checks, and nullifier/new commitment insertions).

#### Who executes?

In the "general pattern" described and pictured above, which individual should execute the "Aztec smart contract function" part of the flow? (Recall: Aztec smart contract circuits are proven by one entity -- at least until MegaHonk has co-SNARK support!). It depends on the use case. It might be some user who is interacting with the MPC Network, or it might be a _representative_ of the MPC Network itself. In our PoC, a representative of the MPC Network called an **Orchestration Server** (**OS**) executes such functions.

Crucially, the OS is **not** trusted to know the underlying private shared data, so the circuits that are to be executed by the OS must be designed to _only_ operate on the _commitments_ to the data (and their nullifiers, if applicable) and not the underlying data.

#### High-level abstractions

> This subsection is probably relevant only to the Aztecnr developers. It discusses high-level abstractions.

Currently, Aztec.nr doesn't have any high-level state variables that can operate solely on commitments. It assumes the executor of the function will also have access to the underlying data in the form of "notes" (custom structs of information), so the high-level state variable abstractions of Aztec.nr are designed accordingly. As we just said, the OS isn't allowed to see the underlying data, so we need to write contracts differently.

A simple, low-level workaround would be to write these OS-executed smart contract functions by handling the low-level commitments and nullifiers directly. The Taceo guys took it a step further and began designing some _new_, additional, high-level private state variable abstractions for when the executor _will not_ have access to the underlying data.

They dubbed these `PrivateSharedImmutable` and `PrivateSharedMutable`.

For `PrivateSharedImmutable`, it has a method to initialise a new commitment (aka a new note hash) by pushing it to the public inputs, with the presumption that the underlying data is not allowed to be known to the executor. So there is no functionality to actually _compute_ the commitment; it's just passed-in as an input, and its correctness is expected to have been checked within the earlier co-SNARK. It also has a method to `get` the existing commitment for an already-initialised `PrivateSharedImmutable` -- again, without trying to prove anything about the preimage data. To make this `get` function work, the PXE DB would need to have stored the commitment already, and so there would need to be a way to inject such a commitment into the PXE DB without any accompanying, underlying note data. This could be done manually via a dedicated PXE endpoint, or it could be done through Aztec's automated message discovery process. The former would be easier.

For `PrivateSharedMutable`, the methods are similar, with extra functionality to mutate private shared state. It can emit the nullifier of an old commitment, and emit a read request of the old commitment. Again, the presumption is that the correctness of the nullifier and old commitment have been validated within the co-SNARK, and the executor of the smart contract function is not allowed access to the underlying data.

#### On nullification within a co-SNARK

Delightfully, a _private shared_ nullifier secret key can be generated _by_ the MPC Network, meaning no one in the world actually _knows_ the nullifier secret key. The corresponding nullifier _public_ key can then be used to _represent_ the MPC Network on Aztec. This principle can be extended to having the MPC Network generate a fully-fledged "Aztec Address" (we just didn't have time to do this).

A common nullification pattern in Aztec is "zcash-style" nullification, where a nullifier secret key must enter an app circuit, in order to compute the nullifier from it. We've historically had to do some gymnastics to derive an app-siloed nullifier secret key that can safely be used in an app circuit, because we don't trust apps with master secret keys. We've also spent a lot of time thinking about alternative nullification patterns (see [this big post](https://forum.aztec.network/t/transferfrom-escrow-nullification-patterns/7528) I wrote exploring many many ways to nullify under different scenarios).

Nullifying certain states via an MPC Network adds another lovely nullification pattern for Aztec devs to play with. The MPC Network can hold private shared state, as well as a master nullifier secret key that can be safely used _directly within_ in a co-Noir program. ("Safely", modulo anti-collusion assumptions).

## A Proof of Concept

We wanted to have a proof of concept which demonstrates private shared state being persisted on Aztec, and then later being _mutated_. Roman suggested the famous [Monty Hall](https://en.wikipedia.org/wiki/Monty_Hall_problem) gameshow.

The fastest tl;dr: There are 3 doors. A prize is behind one door. A player picks a door. The host opens a door _which isn't the winning door, and isn't the user's chosen door_. The user is then offered the option of switching their choice to the other unrevealed door. The user chooses whether to stick or switch. The host opens the player's door choice. Did they win?

In our PoC, then:
- The role of "the host" is performed by the MPC network, so that no one on earth actually knows the game state at any time until the end of the game.
- The winning door is a shared private state that is generated within Taceo's MPC network, and then persisted on Aztec.
- The user executes Aztec smart contract functions to commit-to and persist their choice whenever it's their turn to do something.
- Persisting their choices isn't technically needed (they could just send a signature of their choices to the MPC Network), but we wanted to show-off more machinery which might get used in more-complex use cases.
- The host's actions are conditional on the previously-persisted game state and the user's choices. These actions are calculated by the MPC network, within a co-SNARK, so that the private shared game state can be provably read and mutated according to the rules of the game, without anyone in the world seeing (not even the MPC nodes can see).

Here's the game in code: https://github.com/TaceoLabs/monty-hall-aztec/tree/main

The Player and the Orchestration Server exectute certain smart contract functions in `./contract/`.

The MPC Netwotk executes co-Noir programs in `./noir_logic`.

Orchestration code (to pass data between entities and components) is in `./mpc`.

### In pictures

If you're feeling lazy, here are some diagrams of the game.

(Some of the names of functions and variables differ from the PoC codebase, and even some of the logic differs slightly from the codebase for the sake of conveying things more-simply in diagrams. I was also writing some of this at the same time as the PoC developed.):

> Key:
> LHS, blue boxes: co-Noir programs executed by the MPC network.
> RHS, pink boxes: Aztec smart contract functions executed by the Orchestration Server.
> RHS, yellow boxes: Aztec smart contract functions executed by the Player.

The MPC Network generates a random seed (that no one on earth knows), which will seed private shared game state later. The OS then executes an Aztec smart contract function to persist a commitment to this seed to Aztec.

The MPC Network generates the initial game state, include which door the prize is behind. This data is committed-to. The OS then executes an Aztec smart contract function to persist this data to Aztec.

The user chooses a door, via an Aztec smart contract function, and commits their choice to Aztec. The MPC Network then uses this choice and the private shared game state to compute which door to reveal to the user. Here you can see how old state is read and nullified, and how replacement state is computed. The OS then executes an Aztec smart contract function to finalise the state changes on Aztec:

Similarly, the user chooses whether or not to switch their choice of door. The MPC Network then computes whether the user is a winner or not, and the OS executes a function to finalise the game state on Aztec. This final transaction could even be composed with a token contract on Aztec to distribute some prize money to the user, for example:

## Security

If the MPC Nodes collude, they can see all the private shared state and private computations.

## Changes to Aztec

The PoC has been a good exercise for us to identify some potential new features for Aztec. This is just an unopinonated list; their feasibility hasn't been assessed in any detail.

**Proving System:**
- Make the recursive verifier "ZK" for UH proofs that are fed-into Aztec smart contract functions. At the moment, the recursive verifier is not adapted for the "ZK" property.
- Discuss the feasibility of supporting the extension of co-SNARKs to the MegaHonk proving system.
- Collaborative tx generation. Currently, Alice and Bob cannot contribute a function each to a single tx. This is because the witness instances of each "function execution" are folded together. If Alice gives Bob the witness instance of her "function execution", Bob will be able to read all of Alice's secrets from this witness like a book. "Old fashioned" SNARKs like plonk enabled this use case. Anyway, in the PoC, there are lots of individual Aztec txs being created and submitted by the Player and the Orchestration Server. If it were possible for users to collaboratively build a tx, we could combine some of those steps. It's not a dealbreaker. Of course, if we were able to co-SNARKify entire Aztec functions and kernels (see the next item, below), such collaboration might be less important.

**Protocol Circuits:**
- Discuss the feasibility of generating a set of UH-compatible private kernel circuits (and private function circuits). This would enable entire Aztec txs (or individual Aztec functions) to be executed, instead of the extra recursive "hop" we see in the PoC.

**Aztec_nr/PXE:**

> Note: much of this subsection talks about changes that are only needed because we can't co-SNARKify Aztec smart contract functions nor kernels. (Recall, we can't coSNARKify those, because Taceo's coSNARKs work over UltraHonk). If we were able to co-SNARKify Aztec functions & kernels, we might not entertain the suggsetions in this subsection.
- Expose an `add_note_hash()` endpoint to the PXE, so that note hashes can be manually injected directly into the PXE DB.
- For example, the Orchestration Server (in the PoC) is not allowed to know the underlying `note` data, but they need to be able to compute read requests for the notes' commitments (`note_hashes`) when submitting Aztec transactions.
- Ability to secret-share private data from the PXE DB: take some data, break that data into secret-shares, then encrypt those secret-shares to the public keys of the MPC network's nodes.
- Maybe protocol-enshrined oracles to accesss private PXE data and create secret-shares of this data (as per prev bullet).
- Design private state variables (syntactic sugar) that are compatible with the PoC described above. Taceo have already hacked-together a suggestion of `PrivateSharedMutable` and `PrivateSharedImmutable`. `PrivateSharedSet` unexplored, but similar.
- Rename SharedMutable to `PrivatelyReadablePublicMutable`. "Shared" has a much more prominent and important meaning now that "shared private state" is possible, and so our `SharedMutable` is now too-confusing a name.
- `PrivatelyReadablePublicMutableWithLag`? `PrivatelyReadablePublicMutableWithADelayBeforePublicMutationsTakeEffect`?
- Potentially extract low-level Aztec smart contract primitives into libraries, so that they're easier for low-level devs to access.

### Some other take-aways

Poseidon2 encryption in Aztec smart contract functions was favoured by the Taceo guys, because they haven't built the AES blackbox in co-Noir. Roman built a "more recommended" version of Poseidon2 encryption, which was nice of him!

The Noir programs executed by the MPC network apparently took ~1 second to prove. Pretty fast!

### Hacks

Securely sharing data between participants was hand-waved, in places.

The MPC network wasn't represented by an "Aztec Address", but by a simple keypair (whose secret key was not known to anyone). This keypair was then used for nullification of private shared notes. This was in the interest of simplicity, for a PoC.

### Conclusion

Private shared state gud.