Reduce constraint count of a function call

[iAmMichaelConnor]

Pasting my comment from slack:

A function call adds 200k constraints to an app circuit? That's surprising.

Edit: ok I've looked at the code and can see it's hashing all fields of a flattened PrivateCircuitPublicInputs. (Links in reverse order)

• aztec-packages/noir-projects/noir-protocol-circuits/crates/types/src/abis/private_circuit_public_inputs.nr

  Line 53 in d4921a0

  struct PrivateCircuitPublicInputs {

• aztec-packages/noir-projects/noir-protocol-circuits/crates/types/src/abis/private_call_stack_item.nr

  Line 59 in d4921a0

  pedersen_hash(self.serialize(), GENERATOR_INDEX__CALL_STACK_ITEM)

• aztec-packages/noir-projects/aztec-nr/aztec/src/context/private_context.nr

  Line 488 in d4921a0

  PrivateCallRequest { hash: item.hash(), caller_context, start_side_effect_counter, end_side_effect_counter }

I can think of some potential optimisations:

• When a call is made, don't hash the entire public inputs. I'm sure that only a subset of this data that can be hashed (and actually I thought we were only hashing a subset, so this is a pleasant surprise), whilst ensuring the call can't do anything malicious. E.g. just hashing the call_context, tx_context, args_hash, returns_hash, and maybe side_effect_counters? Maybe we can get away with just hashing the call_context, args, and returns? It feels to me like the calling app only needs to validate this info, and not any of the side effects created by the called function. The kernel circuit can unpack the rest of the PrivateCircuitPublicInputs to validate the side effects, counters, the consistency of the header.
  • Aside, it doesn't look like the call_context conveys the gas limits that are being forwarded from the calling function to the called function. Where is that info? Hopefully not in the TxContext?
• We can go further, and change the "topology" of how the data is hashed, so that hashes of some fields can be precomputed.
  • E.g. hashes of zeros (e.g. if there are no return values for a function call).
  • If the function call is known at compile time, many of the hashes of data in the PrivateCircuitPublicInputs can be precomputed ahead of time.
    • E.g. the example in this thread, of a token transfer: precompute hashes of the contract address (if that's not circular and impossible), function selector, whether it's a delegate/static call.
    • Also, maybe we can pre-compute hashes of zero args, if we know not all args will be used by a function call. Similar for returns. That might require structuring args hashing and returns hashing as a merkle tree, instead of as a flat list, so that subtree roots of zeros can be precomputed.
• I guess we're not using poseidon yet, because it's still inefficient? That'll speed things up nicely.

cc @LeilaWang @LHerskind - not sure whose remit this falls under :)

[benesjan]

When a call is made, don't hash the entire public inputs. I'm sure that only a subset of this data that can be hashed (and actually I thought we were only hashing a subset, so this is a pleasant surprise), whilst ensuring the call can't do anything malicious. E.g. just hashing the call_context, tx_context, args_hash, returns_hash, and maybe side_effect_counters? Maybe we can get away with just hashing the call_context, args, and returns?

I've been looking into this and I see that we call hash on private call stack item in 2 places:

1. first one is in the app circuit,
2. and second time in the kernel.

And it looks that in the kernel it checks that the hash which traveled all the way from app circuit matches the computed hash. I would need a feedback from someone who knows the kernel's better to check whether we could optimize this.

@iAmMichaelConnor do you have a clue here? If not I would wait for Alvaro to come back and bother him on Monday. I don't know this part of code that well.

[iAmMichaelConnor]

I think it's ok to hash just the call_context, args, and returns in both places.

When A calls B, a call stack item is a way to ensure consistency between the data A sent and consumed, and the data B received and returned. I don't think any of the other public inputs of function B are important to enable that check; just the call_context, args, and returns.

It'd be great if @LeilaWang, you could validate that this optimisation works, and whether this change would conflict badly with the PR you're currently working on.

[LeilaWang]

It's a good idea! We only need to check call_context, args_hash, returns_hash in PrivateCircuitPublicInputs. Actually we don't even need to hash them anymore, as the data will be a lot cheaper after switching to databus. We can update the struct to be:

struct PrivateCallRequest {
  contract_address,
  function_data,
  call_context,
  caller_context,
  args_hash,
  returns_hash,
  start_side_effect_counter,
  end_side_effect_counter,
}

[iAmMichaelConnor]

Good point re the data bus.

Why can't the PrivateCallRequest be:

struct PrivateCallRequest {
  contract_address,
  function_data, // not sure what's in here?
  call_context,
  // caller_context, // not this
  args_hash,
  returns_hash,
  // start_side_effect_counter, // not this
  // end_side_effect_counter, // not this
}

I figured the other data that I've commented-out is available to the kernel circuit through other public inputs?

[LeilaWang]

They need to be in the call request because they are the data the caller expects in each nested call.

function_data: contains function_selector and is_private. It needs to be specified in the request so that the kernel can check that a nested call/function is indeed the request is for.

caller_context: it's already in the current call request. It contains the caller's contract address, is_static, and the storage contract address and msg_sender (both zeroed if it's not a delegate call). It's set by the caller and verified by the kernel. It needs to be in the request so that a kernel can verify a nested call's msg_sender, storage contract address, etc.

start and end counters: they need to be in the request because the caller has to enforce the counter range of a nested call, which affects the order of the side effects from the caller and from the nested call. If they are not checked, then I can basically move a nested call, i.e. I can pretend a child function is called after the caller's 3rd side effect instead of the 1st.

[LHerskind]

@LeilaWang, for public calls, we are currently hashing PublicCircuitPublicInputs in its entirely, similar to the private inputs that does not really seem necessary.

As part of #7285, I use

        pedersen_hash([
            self.contract_address.to_field(),
            self.public_inputs.call_context.hash(),
            self.function_data.hash(),
            self.public_inputs.args_hash,
            self.public_inputs.returns_hash,
            self.public_inputs.start_side_effect_counter as Field,
            self.public_inputs.end_side_effect_counter as Field,
        ], GENERATOR_INDEX__CALL_STACK_ITEM)

for the private call stack item hash. And for public I was thinking that:

std::hash::pedersen_hash_with_separator([
            item.contract_address.to_field(),
            item.public_inputs.call_context.hash(),
            item.function_data.hash(),
            item.public_inputs.args_hash,
            item.public_inputs.returns_hash,
            item.public_inputs.start_side_effect_counter as Field,
            item.public_inputs.end_side_effect_counter as Field,
            item.public_inputs.start_gas_left.da_gas as Field,
            item.public_inputs.start_gas_left.l2_gas as Field,
            item.public_inputs.end_gas_left.da_gas as Field,
            item.public_inputs.end_gas_left.l2_gas as Field,
        ], GENERATOR_INDEX__CALL_STACK_ITEM)

Should do the job. Very similar values, mainly with the gas values as well, but I don't know if they are actually needed like this. I don't really know about something like the hashes etc. But maybe you or @dbanks12 would be able to provide more data on if this is a fair change?

With both changes and the argshash size change the entrypoint goes all the way down to 125K 😎

[LeilaWang]

For public call, we don't need to include:

• end_side_effect_counter: it's always zero. I want to remove it at some point.
• returns_hash: don't see we use a public function's returns_hash anywhere 🤔
• And the following because the function making the public call request doesn't care about these, and the public kernel computes or checks them in a nested call against the previous kernel's public inputs:
  • start_gas_left
  • end_gas_left