Add base fee that covers nullifier, account and output note hashes

[PhilippGackstatter]

The initial fee implementation contains only the verification_base_fee, but we need additional ones to cover the cost of inserting nullifiers and accounts into their respective tree and notes in the block note tree and potentially data storage. I'll ignore data storage in this issue since we have discussed it the least.

There are at least two approaches we've previously discussed:

• Two separate tree_base_fee and output_note_base_fee.
• A single hash_base_fee that covers any kind of hashing operation.

As explained here and here nullifiers + accounts and output notes are independent resources and so they shouldn't be covered by the same base fee. This suggests separate base fees.

The argument for having a single fee is that, essentially, the expensive part of inserting nullifiers, account updates or notes into the block note tree are hash operations. And so a single base fee would be sufficient, at least, conceptually. Moreover, an important resource we care about is the number of cycles a transaction adds to the batch and block kernels and input/output notes contribute to this metric (see also #1217 (reply in thread)), and so these would already be partially captured by the cycle-based verification_base_fee.

I'm honestly not sure what the better approach is, so I would default to implementing the simpler option first and if we find it is insufficient, split the hash_base_fee into two later.

Broken out of #1673.

[bobbinth]

The argument for having a single fee is that, essentially, the expensive part of inserting nullifiers, account updates or notes into the block note tree are hash operations. And so a single base fee would be sufficient, at least, conceptually. Moreover, an important resource we care about is the number of cycles a transaction adds to the batch and block kernels and input/output notes contribute to this metric (see also #1217 (reply in thread)), and so these would already be partially captured by the cycle-based verification_base_fee.

I think using a single hash_fee may be tricky. There are a couple of reasons for this:

• Note and Account/Nullifier trees have different structures and it may not be easy to establish cost equivalence between updating them. For example, note trees are of depth 16 while our current implementation of account/nullifier trees is of depth 64. We could say that a cost of a nullifier is 4x of a note, but I'm not sure this is right.
• Related to the above point, there are other costs associated with notes and nullifiers not fully captured by hashing. Specifically, every note needs to be stored by the network (even for private notes we store its hash + metadata). And so in some ways cost of a created note is the same or even greater than a cost of a nullifier.

Basically, we end up in a situation where it is not clear how to compare costs of created notes and nullifiers. And so, my thinking is that we should have these as independent resource.

If we do want to use a single resource, I'd probably make created notes and nullifiers cost the same. In that case, we could make things even more abstract and go with something like "compute unit".

For example, we could say that account update, new nullifier, and new note are all the same and cost 1 compute unit. Then, if we set a compute unit target at 1000 units, and the maximum at 2000 units, an average block would contain either 1K updated account, 1K created nullifiers, or 1K created notes - or more likely a mix of these such they total number ends up around 1000.

---

Another thing I'm not sure how to think about yet is short term vs. long term cost. For example, while updating an account tree has the same cost as updating a nullifier tree in the short term, the costs in the long term are very different. Specifically, long-term cost of updating an account is much lower than of creating a note or a nullifier - e.g., 1000 updates to the same account have the same long-term cost as creating a single nullifier.

Maybe it is indeed simpler to have two resource buckets:

• Compute units - these capture short-term costs.
• Storage units - these capture long-term costs.

And then things could look like so:

• A private note would have the same storage cost as a nullifier, but would be 4x cheaper in terms of compute costs.
• Updating an existing private account would have the same compute cost as the nullifier, but almost zero storage cost.
• Creating a new account would have same compute cost as creating a nullifier, and maybe the same (or higher) storage cost.

I think the tricky part here would be coming up with relative resource costs for each item. Treating them as "independent resources" allows us to let the market decide their relative costs, but it also comes with its own complexities.