feat: Private refunds

[just-mitch]

This PR creates a new token contract and fee payment contract that support private refunds.

I.e. Alice pays Bob in private notes, and receives refunds in private notes within the same transaction.

This is a massive improvement over the existing PrivateFeePaymentMethod which uses an un/shield flow, which puts Alice in a never-ending loop of refunding refunds.

Note I suspect we will want to:

1. consolidate this token/fpc, and the other token/fpc
2. and/or create a more general pattern for this type of homomorphic operation

but the exact way forward there is not clear to me yet.

This PR also shows off some of the ugly things we need to do to get this working, like:

• storing notes as a set to avoid mixing in the owner's address when computing the note hash
• storing raw npk hashes in the contracts
• needing to use to_unconstrained to get private balances

This PR also fixes two bugs:

• supporting transactions that only have public teardown
• validation of complete addresses that did not have public keys associated with their deployment

This PR also has the TXE charge nominal TX fees, and basic support for a teardown function.

Side note, see https://hackmd.io/NUfIc2LJRlqL0-myhij3KQ for a cost analysis (in terms of TXEffects byte size) for different fee payment methods.

In conclusion

I vote to merge the PR roughly as is and start the discussion on how to clean the stuff up that we hate, but if someone has strong negative reactions, I'm definitely open to hearing which parts we want to tease out into individual PRs.

[AztecBot]

Benchmark results

Metrics with a significant change:

• protocol_circuit_simulation_time_in_ms (public-kernel-setup): 740 (+18%)
• app_circuit_proving_time_in_ms (AuthRegistry:set_authorized (avm)): 1,619 (+22%)
• app_circuit_proving_time_in_ms (FPC:pay_refund (avm)): 16,644 (-30%)
• protocol_circuit_proving_time_in_ms (root-parity): 33,822 (-21%)

Detailed results

All benchmarks are run on txs on the `Benchmarking` contract on the repository. Each tx consists of a batch call to `create_note` and `increment_balance`, which guarantees that each tx has a private call, a nested private call, a public call, and a nested public call, as well as an emitted private note, an unencrypted log, and public storage read and write. This benchmark source data is available in JSON format on S3 [here](https://aztec-ci-artifacts.s3.us-east-2.amazonaws.com/benchmarks-v1/pulls/7226.json). ### Proof generation Each column represents the number of threads used in proof generation. | Metric | 1 threads | 4 threads | 16 threads | 32 threads | 64 threads | | - | - | - | - | - | - | proof_construction_time_sha256_30_ms | 11,389 (+2%) | 3,058 | 1,443 (+3%) | 1,417 (-5%) | 1,566 (+1%) | proof_construction_time_sha256_100_ms | 43,846 (+1%) | 11,740 | 5,422 | 5,394 | 5,374 (+1%) | proof_construction_time_poseidon_hash_ms | 78.0 (+1%) | 34.0 | 34.0 | 57.0 | 89.0 (+1%) | proof_construction_time_poseidon_hash_30_ms | 1,517 | 415 | 200 | 221 (-1%) | 271 (+3%) | proof_construction_time_poseidon_hash_100_ms | 5,755 | 1,564 | 720 (-1%) | 761 (-2%) | 798 (+1%) | ### L2 block published to L1 Each column represents the number of txs on an L2 block published to L1. | Metric | 4 txs | 8 txs | 16 txs | | - | - | - | - | l1_rollup_calldata_size_in_bytes | 1,412 | 1,412 | 1,412 | l1_rollup_calldata_gas | 9,476 | 9,472 | 9,452 | l1_rollup_execution_gas | 610,297 | 610,293 | 610,273 | l2_block_processing_time_in_ms | 744 (-1%) | 1,409 (-2%) | 2,676 (-1%) | l2_block_building_time_in_ms | 25,588 (+2%) | 52,602 (+5%) | 99,981 (+1%) | l2_block_rollup_simulation_time_in_ms | 25,587 (+2%) | 52,601 (+5%) | 99,981 (+1%) | l2_block_public_tx_process_time_in_ms | 22,008 (+3%) | 48,677 (+6%) | 96,247 (+2%) | ### L2 chain processing Each column represents the number of blocks on the L2 chain where each block has 8 txs. | Metric | 3 blocks | 5 blocks | | - | - | - | node_history_sync_time_in_ms | 6,947 (-3%) | 9,797 (-2%) | node_database_size_in_bytes | 12,165,200 | 16,117,840 | pxe_database_size_in_bytes | 16,254 | 26,813 | ### Circuits stats Stats on running time and I/O sizes collected for every kernel circuit run across all benchmarks. | Circuit | simulation_time_in_ms | witness_generation_time_in_ms | proving_time_in_ms | input_size_in_bytes | output_size_in_bytes | proof_size_in_bytes | num_public_inputs | size_in_gates | | - | - | - | - | - | - | - | - | - | private-kernel-init | 123 (+6%) | 494 (+11%) | 12,274 (-7%) | 20,634 | 67,190 | 92,352 | 2,819 | 524,288 | private-kernel-inner | 389 (+7%) | 1,097 (-2%) | 45,289 (-6%) | 94,902 | 67,190 | 92,352 | 2,819 | 2,097,152 | private-kernel-tail | 319 (+5%) | 1,835 (+6%) | 46,369 (-15%) | 99,121 | 71,733 | 14,912 | 399 | 2,097,152 | base-parity | 6.47 (+5%) | 2,053 (+15%) | 2,518 (-8%) | 128 | 64.0 | 2,208 | 2.00 | 131,072 | root-parity | 49.9 (+2%) | 58.1 (-24%) | :warning: 33,822 (**-21%**) | 27,100 | 64.0 | 2,720 | 18.0 | 2,097,152 | base-rollup | 8,117 (+5%) | 5,026 (+4%) | 72,294 (-14%) | 170,330 | 756 | 3,648 | 47.0 | 4,194,304 | root-rollup | 112 (-1%) | 76.0 (-17%) | 19,698 (-11%) | 25,309 | 620 | 3,456 | 41.0 | 1,048,576 | public-kernel-setup | :warning: 740 (**+18%**) | 3,695 (+1%) | 38,849 (-15%) | 116,905 | 93,334 | 125,344 | 3,850 | 2,097,152 | public-kernel-app-logic | 649 (+9%) | 4,828 (+5%) | 39,856 (-12%) | 116,905 | 93,334 | 125,344 | 3,850 | 2,097,152 | public-kernel-tail | 1,440 (+4%) | 36,638 (+2%) | 165,548 (-11%) | 511,910 | 10,014 | 14,912 | 399 | 8,388,608 | private-kernel-reset-small | 577 (+5%) | 2,230 (+14%) | 41,514 (-10%) | 123,313 | 67,190 | 92,352 | 2,819 | 2,097,152 | public-kernel-teardown | 654 (+15%) | 4,892 (+6%) | 39,945 (-15%) | 116,905 | 93,334 | 125,344 | 3,850 | 2,097,152 | merge-rollup | 30.5 (-2%) | N/A | N/A | 16,542 | 756 | N/A | N/A | N/A | private-kernel-tail-to-public | N/A | 7,146 (-1%) | 85,016 (-15%) | N/A | N/A | 125,344 | 3,850 | 4,194,304 | Stats on running time collected for app circuits | Function | input_size_in_bytes | output_size_in_bytes | witness_generation_time_in_ms | proof_size_in_bytes | proving_time_in_ms | size_in_gates | num_public_inputs | | - | - | - | - | - | - | - | - | ContractClassRegisterer:register | 1,344 | 9,944 | 424 (+4%) | N/A | N/A | N/A | N/A | ContractInstanceDeployer:deploy | 1,408 | 9,944 | 40.9 (+4%) | N/A | N/A | N/A | N/A | MultiCallEntrypoint:entrypoint | 1,920 | 9,944 | 1,814 (+3%) | N/A | N/A | N/A | N/A | GasToken:deploy | 1,376 | 9,944 | 1,018 (+7%) | N/A | N/A | N/A | N/A | SchnorrAccount:constructor | 1,312 | 9,944 | 1,439 (+2%) | N/A | N/A | N/A | N/A | SchnorrAccount:entrypoint | 2,304 | 9,944 | 2,865 (-1%) | 16,768 | 50,767 (-6%) | 2,097,152 | 457 | Token:privately_mint_private_note | 1,280 | 9,944 | 1,708 (+7%) | N/A | N/A | N/A | N/A | FPC:fee_entrypoint_public | 1,344 | 9,944 | 388 (+11%) | 16,768 | 10,364 (-8%) | 524,288 | 457 | Token:transfer | 1,312 | 9,944 | 4,622 (+4%) | 16,768 | 40,950 (-13%) | 2,097,152 | 457 | AuthRegistry:set_authorized (avm) | 21,043 | N/A | N/A | 87,200 | :warning: 1,619 (**+22%**) | N/A | N/A | FPC:prepare_fee (avm) | 28,495 | N/A | N/A | 88,032 | 4,783 (-15%) | N/A | N/A | Token:transfer_public (avm) | 44,885 | N/A | N/A | 87,754 | 3,525 (-9%) | N/A | N/A | AuthRegistry:consume (avm) | 34,973 | N/A | N/A | 87,616 | 2,804 (-4%) | N/A | N/A | FPC:pay_refund (avm) | 41,394 (+7%) | N/A | N/A | 88,864 | :warning: 16,644 (**-30%**) | N/A | N/A | Benchmarking:create_note | 1,344 | 9,944 | 1,411 (-2%) | N/A | N/A | N/A | N/A | SchnorrAccount:verify_private_authwit | 1,280 | 9,944 | 73.3 (+1%) | N/A | N/A | N/A | N/A | Token:unshield | 1,376 | 9,944 | 3,732 (+1%) | N/A | N/A | N/A | N/A | FPC:fee_entrypoint_private | 1,376 | 9,944 | 4,682 (-1%) | N/A | N/A | N/A | N/A | ### AVM Simulation Time to simulate various public functions in the AVM. | Function | time_ms | bytecode_size_in_bytes | | - | - | - | GasToken:_increase_public_balance | 67.6 (-2%) | 13,873 (+1%) | GasToken:set_portal | 17.1 (-6%) | 3,495 (+5%) | Token:constructor | 94.6 (+4%) | 24,207 (+2%) | FPC:constructor | 64.1 | 13,893 (+2%) | GasToken:mint_public | 54.4 (+5%) | 10,241 (+1%) | Token:mint_public | 65.6 (+1%) | 19,216 (+1%) | Token:assert_minter_and_mint | 231 (+6%) | 13,034 (+1%) | AuthRegistry:set_authorized | 31.8 (-2%) | 7,869 (+1%) | FPC:prepare_fee | 146 (-4%) | 15,129 | Token:transfer_public | 38.2 (+24%) | 31,425 (+1%) | FPC:pay_refund | 208 (+6%) | 28,061 (+11%) | Benchmarking:increment_balance | 2,823 (+7%) | 15,407 (+1%) | Token:_increase_public_balance | 56.4 (+1%) | 15,089 (+1%) | FPC:pay_refund_with_shielded_rebate | 203 (+12%) | 29,148 (+10%) | ### Public DB Access Time to access various public DBs. | Function | time_ms | | - | - | get-nullifier-index | 0.147 (-6%) | ### Tree insertion stats The duration to insert a fixed batch of leaves into each tree type. | Metric | 1 leaves | 16 leaves | 64 leaves | 128 leaves | 256 leaves | 512 leaves | 1024 leaves | | - | - | - | - | - | - | - | - | batch_insert_into_append_only_tree_16_depth_ms | 10.4 | 16.7 | N/A | N/A | N/A | N/A | N/A | batch_insert_into_append_only_tree_16_depth_hash_count | 16.8 | 31.7 | N/A | N/A | N/A | N/A | N/A | batch_insert_into_append_only_tree_16_depth_hash_ms | 0.604 (+1%) | 0.515 | N/A | N/A | N/A | N/A | N/A | batch_insert_into_append_only_tree_32_depth_ms | N/A | N/A | 48.3 (-1%) | 75.6 (-1%) | 131 | 244 (-2%) | 466 (-2%) | batch_insert_into_append_only_tree_32_depth_hash_count | N/A | N/A | 95.9 | 159 | 287 | 543 | 1,055 | batch_insert_into_append_only_tree_32_depth_hash_ms | N/A | N/A | 0.494 (-1%) | 0.465 (-1%) | 0.449 | 0.442 (-2%) | 0.437 (-1%) | batch_insert_into_indexed_tree_20_depth_ms | N/A | N/A | 61.1 (+2%) | 111 (-1%) | 181 (-1%) | 358 | 690 | batch_insert_into_indexed_tree_20_depth_hash_count | N/A | N/A | 109 | 207 | 355 | 691 | 1,363 | batch_insert_into_indexed_tree_20_depth_hash_ms | N/A | N/A | 0.518 (+3%) | 0.500 (-1%) | 0.480 | 0.485 | 0.474 | batch_insert_into_indexed_tree_40_depth_ms | N/A | N/A | 72.8 | N/A | N/A | N/A | N/A | batch_insert_into_indexed_tree_40_depth_hash_count | N/A | N/A | 133 | N/A | N/A | N/A | N/A | batch_insert_into_indexed_tree_40_depth_hash_ms | N/A | N/A | 0.519 | N/A | N/A | N/A | N/A | ### Miscellaneous Transaction sizes based on how many contract classes are registered in the tx. | Metric | 0 registered classes | 1 registered classes | | - | - | - | tx_size_in_bytes | 85,672 | 670,983 | Transaction size based on fee payment method | Metric | | | - | |