This post asks the question of whether app circuits should contain the logic to “prove the note’s existence in the tree”, or whether that logic should be ‘punted’ to the private kernel circuit.
Thanks to Zac, Joe, Charlie for chatting about this from time to time.
Pros (of deferring the membership proof to the kernel circuit)
It doesn’t add any extra constraints for the user: they generate both the app proof and the private kernel proof.
It would allow the decentralised community to ‘hard-fork’ more easily, without breaking app circuits.
Examples of such breaking hard-forks:
A change in the depth of the private data tree
A change in the hash type used in the private data tree (e.g. to increase security of the hash)
Unforeseen bug fixes relating to the private data tree
If membership proofs were done in app circuits, they would be broken by such hard forks (the app wouldn’t be usable anymore). But the community will be able to ‘swap out’ the verification keys of kernel circuits for newer kernel circuits (via a hard fork), and so the kernel circuit logic can be updated to use a different hash type or tree depth.
It makes Noir Contract logic marginally simpler (although it’s actually quite easy to perform a membership check with Noir, so this point is moot; all we need for A3 compatibility is the ability to specify the Pedersen domain separator, which is in the works).
Cons (of deferring the membership proof to the kernel circuit)
It imposes an upper bound on the number of note ‘reads’ which can be performed by an app circuit.
Currently (with membership checks being done within the app circuit), an app circuit can perform practically unlimited** reads, because all we need to validate those reads is a single field in the app circuit Public Inputs ABI: the old_private_data_tree_root field.
If reads are deferred to the kernel circuit, the app circuit needs to now communicate a list of all of the note commitments which have been ‘opened’ within the app circuit, so that the kernel circuit can ensure to prove existence of each of these note commitments in the tree. Let’s call such a list read_requests (a list of reads that the app circuit is requesting be performed).
Given that the kernel circuit must have a static number of inputs, which can accommodate many/most app circuits, we’ll need to fix the size of the read_requests array to some READ_REQUESTS_LENGTH constant. This is why the number of reads is restricted under this approach.
Having said that, it will be possible to generate many permutations of kernel circuits, with varying lengths of input arrays. So we could have a kernel circuit for 8, 16, 32, 64, 128, 256, etc read_requests. We need to do more thinking on this subject though. Given the number of arrays the kernel circuit handles, if we wanted to permute all of them, the number of kernel circuit permutations would be huge, and quite a tricky engineering feat to generate such permutations and ensure they’re secure.
We might be inadvertently eliminating interesting applications which need to perform a huge number of reads within a function. [Help wanted, to identify such applications!]
Hybrid?
There is a “best of both worlds” hybrid solution, where an app developer can choose whether to perform membership checks in their app circuit (against the old_private_data_tree_root) or to communicate a list of read_requests to the kernel circuit. This would mean an app developer would need to make a choice about how ‘future proof’ they want their app to be. I can’t imagine many devs would want to opt for an app which only works until the next hard fork!!!
Thoughts?
Thoughts?
* Also, for non-const notes, a read will often be accompanied by emitting the note’s nullifier, as a way of proving it’s not-yet been nullified… but Noir Contract syntax currently separates the syntax for nullifying (with a remove() method), to give devs more control.
** the number of reads an app circuit can do is currently restricted by the size of the SRS, and by the RAM limits of typical user hardware, and RAM limits imposed by wasm (when proving in the browser).
I’m definitely not the best person to chime in here, but hey, posting is free!
A friend of mine used to say that all problems in software engineering are solved by introducing another level of indirection. Would it make sense to have another circuit that handles the “glue” between the app and the world state? This circuit could receive a large number of read requests from the app and expose them as a single old_private_data_tree_root to the kernel circuit. And it would be easy to swap out in the event of a fork that changes the internal state representation, while exposing the same “API” to the app circuits.
I can’t imagine many devs would want to opt for an app which only works until the next hard fork!!!
Jokes aside, I understand that hard forks would be designed to be backwards compatible with app circuits, right? Unless the internal state representation needs to change in ways like the ones you mentioned (eg removing a hash function that was shown to be insecure).
Ah, yes, I forgot to add this as an option, thanks! And it’s a very good option.
We could indeed have a “read circuit” as you suggest.
The cost (in terms of number of constraints) of verifying such a ‘read circuit’ proof within the kernel circuit will need to weighed against the cost of doing the hashing for lots of reads.
With Honk’s various optimisations (including Goblin Plonk ideas), the cost of recursion might make this approach the best approach!
Ideally, yes, we’d want to keep hard forks backwards-compatible. There are a few examples in Ethereum’s history where it’s removed a feature and broken apps (e.g. removing ‘gas rebates’ for setting nonzero storage to zero breaking gastoken).
From my standpoint I think the protocol is simpler to understand if the Kernel circuit does membership checks. In the fixed READ_REQUESTS_LENGTH model, could you recurse to get around this limit, or would the limit apply still to the final proof?
I do agree it’s an engineering challenge to support multiple sizes of Kernel proofs, but for now I can’t think of applications that would require more than say 1024 reads, also any large read can be represented as a single merkle root, to compress it down to one read. The app proof can unpack this to work around the limit.
It would also be safer as the developer could “forget” to do checks otherwise. Imagine if the SLOAD’s in the EVM had to be marked as “check this value is accurate”, it would be audit hell.
Further rational
We already delegate checks to the execution context and the developer doesn’t have to “remember” to do these to write a secure context.
Delegating to the Kernel circuit or execution context means you can also write a Noir Contract that targets a different execution context e.g not Aztec 3. The Noir community may find a use for that and it would allow shared tooling to be made. Solidity is used in more places than Ethereum main-net.
The execution context would just need to correctly handles all the checks required by the ACVM op-codes, e.g READ_NOTE.
Even if we have a separate ‘special’ circuit to perform the merkle membership proofs, we would still need a way for the app to communicate the number of read requests to be performed by that special circuit. So we’d still need multiple permutations of the special circuit (for 8, 16, 32, 64, etc. reads).
It might still be a nice separation of concerns eventually, but we could probably proceed with shifting the ‘read’ logic into the private kernel circuit initially, and then at some point later separate it out.
Good question! Yeah I think we could use recursion. A dev could write a read_8() function (for example), which could read 8 notes at a time, and accumulate the notes into a single value (e.g. summation or whatever fits the use case). Then the main function could call read_8() in a loop.
This would work if read_8 isn’t automatically inlined by Noir - I.e. Noir would need to be told that read_8 must be called as though it’s a separate private function. So we’d need some keyword like noinline (i.e. do not inline).
Can you explain how hard fork is related to reading a note here?
So we are deferring reads to be after the app circuit ie after the execution? Does that not change the flow of the circuit? Like in case of a transfer(), you want to first read the user balance. Will this now be deferred to after the transfer?
We might be inadvertently eliminating interesting applications which need to perform a huge number of reads within a function. [Help wanted, to identify such applications!]
Would identity solutions be such an example. Infrequent writes (ie updating or creating a new identity) but mostly just reads (people verifying your identity/looking at your “passport”) (edited)
In reality we wouldn’t be deferring reads, only “read verification”. The circuit would notify that it read data with commitment X and we defer the verification of the inclusion of X in the private state tree.
If membership proofs happen in the app circuit, then if Aztec hard forks (examples above are: change is made to the depth of the private data tree or the merkle hash type), app circuits which have already been compiled to a circuit and deployed (stored in the contracts tree) on the previous version of Aztec will no longer work on this fork. This is because the old app circuits will contain logic that is specific to a stale Aztec (e.g. an old tree depth or hash type). If we instead defer membership proofs for reads to the kernel circuit, that Aztec-version-specific logic will be in the kernel and not in the already-deployed app circuits.
As @alvaro said, we wouldn’t be deferring reads entirely. We would just be putting of membership proofs until the kernel circuit.
I know there was conversation previously about requiring that you must nullify a private note in order to read it. Is that something being considered? IIRC we decided it wasn’t necessary, but I wanted to bring it up here as I believe it would affect the pros and cons.
I know there was conversation previously about requiring that you must nullify a private note in order to read it
That’s no-longer a requirement. It’s up to the app developer. They have to call get and call remove on the state variable to read, then nullify. So we’ve decoupled those operations, to allow as much flexibility as possible.
One usecase that we desire is to have “const notes”, for example, a note that a user can create but only once. Such a contract would expose a function to create the note, and that function would also emit a nullifier related only to the user nullfier private key (so he cannot create more notes with his identity).
Then that note can be read as many times as necessary without generating any nullifiers, but wouldn’t be “updatable”.
