feat: native world state

[alexghr]

This PR adds a new CPP module for managing the merkle trees that make up the world state. A new implementetion of MerkleTreeDb is provided to interact with the native code.

msgpack is used to pass messages across the js<->cpp boundary. Tests have been added to assert that the two world state implementations work in the same way (more tests would be better).

This PR builds on top of #7037.

PS: I'm not as experienced with C++

[alexghr]

Need to investigate why this does not work as expected. The only mismatch is the nullifier tree root. I think the the world state cpp code might be wrong so I've disabled this while I investigate further.

Update: inserting nullifier batches > 128 leads to different results. Anything <= 128 at a time is ok.

Update 2: I've enabled the test with smaller blocks

[fcarreiro]

Variants are not considered kosher/idiomatic in C++. This doesn't feel like a typescript type Tree = A | B | C. In C++ it feels more like a casting to any and then casting to some type and hoping.

What's usually done is to set up a common interface and use that.

I'm not saying you change it because it might be quite difficult. I'm only mentioning that coming from a C++ bg it doesn't feel right unless there's no other option.

[alexghr]

Indeed, it's difficult to have a common interface in this case (actually the IndexedTree does already extend AppenyOnlyTree). The other thing I had in mind was to just not use a map/array and instead have each tree be a member variable which mean having a switch or if/else chain in each function.

I haven't touched C++ in a long time (but modern C++ looks awesome!), my understanding of variant is it just takes away the switch statement and has the compiler "write" it?

[fcarreiro]

You can create this in the initializer list just like _workers above.

[fcarreiro]

The ownership model here is very very error prone.

• lmdb_store has a reference to lmdb_env of unknown lifetime.
• store holds a reference to lmdb_store which in principle will only live inside this block. However, then the lifetime gets "extended" by moving it into _trees (which hopefully lives longer than everything else).
• Same with the tree.

Some alternatives:

• Let's assume we are ok with LMDBStore having a reference to a long lived environment. This is not too strange and you know it lives as long as the instance of this class.
• AFAICT from the blocks here, you can actually transfer ownership of most of the ptrs to the next thing you are constructing:

auto lmdb_store = std::make_unique<LMDBStore>(*_lmdb_env, name, false, false, IntegerKeyCmp);
auto store = std::make_unique<NullifierStore>(name, NULLIFIER_TREE_HEIGHT, std::move(lmdb_store));
auto tree = std::make_unique<NullifierTree>(std::move(store), _workers, 128);

Then you JUST insert the tree in _trees. Of course you'd have to change the stores to take and store an std::unique_ptr instead of a reference. This is the right thing to do in this case. Ownership idioms are quite important in C++ and are usually reflected by whether you use a ptr, reference, or unique_ptr. Taking a unique_ptr usually means ownership transfer. Taking a ref/ptr usually means not.

I think this suggestion would work better and be less error prone (you cannot forget to extend the lifetimes). But of course, if you do need somehow raw access to store and lmdb_store in this class (like you have now in _trees) then you might need to change a few things.

PS: I do like that you are using unique_ptr vs shared_ptr ;)

[PhilWindle]

Thanks @fcarreiro. I'll re-work all of the object relationships over the course of the next few PRs that we will be creating for this native world state.

[alexghr]

❗ had to turn this on so that we could build a shared lib (the nodejs module)

[fcarreiro]

A question for @ludamad maybe. Should this all be in barretenberg/cpp/src/{world_state, etc} instead of barretenberg/cpp/src/barretenberg/{world_state, etc}. Seems like we'd want to have some separation between what't the core proving system and things around it (even if it means doing some work on the cmake side).

PS: on that note, it might also make sense to move the AVM one level up from here.

[alexghr]

duplicate 🙈

[alexghr]

This will change depending on the result of AztecProtocol/engineering-designs#9

[alexghr]

Serialize all writes and reads to the cpp code. Ideally this would only lock for uncomitted state.

[alexghr]

This should go in WorldState's constructor in C++

[alexghr]

I'll enable some of the orchestrator tests to use the new world state implementation

[alexghr]

These functions should go in a separate file.

[AztecBot]

Benchmark results

Metrics with a significant change:

• avm_simulation_time_ms (FeeJuice:set_portal): 13.9 (+42%)
• l2_block_processing_time_in_ms (4): 260 (-18%)
• l2_block_processing_time_in_ms (16): 815 (-23%)

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.

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_ms	5,744	1,546	708	754 (-2%)	774
proof_construction_time_sha256_30_ms	11,807 (-1%)	3,139	1,395	1,423	1,471 (+1%)
proof_construction_time_sha256_100_ms	44,215	11,785 (+1%)	5,397 (-5%)	6,033 (+11%)	5,369
proof_construction_time_poseidon_hash_ms	78.0	34.0	34.0	58.0 (+2%)	87.0
proof_construction_time_poseidon_hash_30_ms	1,529	418	200	228 (+5%)	270 (+2%)
proof_construction_time_poseidon_hash_100_ms	5,643	1,516	672	745 (+2%)	748

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	4,420	7,940	14,948
l1_rollup_calldata_gas	50,560	93,238	177,848
l1_rollup_execution_gas	815,705	1,548,902	3,332,679
l2_block_processing_time_in_ms	⚠️ 260 (-18%)	454 (-4%)	⚠️ 815 (-23%)
l2_block_building_time_in_ms	9,320 (-1%)	18,379	36,720
l2_block_rollup_simulation_time_in_ms	9,319 (-1%)	18,379	36,719
l2_block_public_tx_process_time_in_ms	7,925 (-1%)	16,970	35,274

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	3,131 (+1%)	4,069 (+2%)
node_database_size_in_bytes	14,237,936	18,243,824
pxe_database_size_in_bytes	16,258	26,818

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	input_size_in_bytes	output_size_in_bytes	proving_time_in_ms
private-kernel-init	70.9 (-4%)	376 (-4%)	20,975	44,933	N/A
private-kernel-inner	140 (-1%)	688 (-3%)	71,787	45,067	N/A
private-kernel-reset-tiny	332 (+1%)	715 (-1%)	64,273	44,922	N/A
private-kernel-tail	152 (-5%)	132 (-3%)	50,551	57,178	N/A
base-parity	5.56 (-2%)	N/A	160	96.0	N/A
root-parity	35.5 (+1%)	N/A	73,964	96.0	N/A
base-rollup	2,123 (-1%)	N/A	189,128	664	N/A
block-root-rollup	41.2 (-1%)	N/A	58,217	2,448	N/A
public-kernel-setup	86.1 (-2%)	N/A	114,433	79,670	N/A
public-kernel-app-logic	99.7	N/A	114,251	79,670	N/A
public-kernel-tail	580 (-1%)	N/A	487,098	16,414	N/A
private-kernel-reset-small	306 (-1%)	N/A	66,345	45,629	N/A
private-kernel-tail-to-public	797 (+15%)	592 (-5%)	448,120	1,825	N/A
public-kernel-teardown	85.4 (-1%)	N/A	114,697	79,670	N/A
merge-rollup	19.9 (-1%)	N/A	38,182	664	N/A
undefined	N/A	N/A	N/A	N/A	104,324 (+2%)

Stats on running time collected for app circuits

Function	input_size_in_bytes	output_size_in_bytes	witness_generation_time_in_ms
ContractClassRegisterer:register	1,344	11,731	348
ContractInstanceDeployer:deploy	1,408	11,731	18.2 (-3%)
MultiCallEntrypoint:entrypoint	1,920	11,731	424
FeeJuice:deploy	1,376	11,731	393 (-1%)
SchnorrAccount:constructor	1,312	11,731	60.8 (-1%)
SchnorrAccount:entrypoint	2,336	11,731	368 (-2%)
FeeJuice:claim	1,344	11,731	36.0 (-7%)
Token:privately_mint_private_note	1,280	11,731	66.1 (-9%)
FPC:fee_entrypoint_public	1,344	11,731	24.6
Token:transfer	1,312	11,731	209 (-1%)
Benchmarking:create_note	1,344	11,731	75.1 (+1%)
SchnorrAccount:verify_private_authwit	1,280	11,731	26.5 (-11%)
Token:unshield	1,376	11,731	488
FPC:fee_entrypoint_private	1,376	11,731	645 (-1%)

AVM Simulation

Time to simulate various public functions in the AVM.

Function	time_ms	bytecode_size_in_bytes
FeeJuice:_increase_public_balance	43.0 (-1%)	1,328
FeeJuice:set_portal	⚠️ 13.9 (+42%)	1,274
Token:constructor	257	11,412
FPC:constructor	71.0 (+4%)	8,425
FeeJuice:check_balance	35.8 (-2%)	1,135
Token:mint_public	249 (-2%)	2,413
Token:assert_minter_and_mint	43.3 (+2%)	1,629
AuthRegistry:set_authorized	45.0 (-4%)	567
FPC:prepare_fee	91.6 (+4%)	1,638
Token:transfer_public	14.9 (-9%)	9,301
FPC:pay_refund	40.6 (-7%)	2,170
Benchmarking:increment_balance	1,001	1,584
Token:_increase_public_balance	37.6 (-4%)	1,305
FPC:pay_refund_with_shielded_rebate	51.1 (-1%)	2,170

Public DB Access

Time to access various public DBs.

Function	time_ms
get-nullifier-index	0.164 (+4%)

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	2.20 (+1%)	3.87	N/A	N/A	N/A	N/A	N/A
batch_insert_into_append_only_tree_16_depth_hash_count	16.7	31.8	N/A	N/A	N/A	N/A	N/A
batch_insert_into_append_only_tree_16_depth_hash_ms	0.114 (+1%)	0.108 (-1%)	N/A	N/A	N/A	N/A	N/A
batch_insert_into_append_only_tree_32_depth_ms	N/A	N/A	11.1 (-2%)	17.6 (-1%)	30.5 (-1%)	59.4 (-1%)	113 (-1%)
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.106 (-3%)	0.102 (-1%)	0.0995 (-1%)	0.102	0.101 (-1%)
batch_insert_into_indexed_tree_20_depth_ms	N/A	N/A	14.1 (-3%)	25.8 (-1%)	43.4 (-2%)	83.5 (+1%)	160 (-1%)
batch_insert_into_indexed_tree_20_depth_hash_count	N/A	N/A	109	207	357	691	1,363
batch_insert_into_indexed_tree_20_depth_hash_ms	N/A	N/A	0.108 (-4%)	0.104 (-1%)	0.104 (-2%)	0.104 (+1%)	0.101 (-2%)
batch_insert_into_indexed_tree_40_depth_ms	N/A	N/A	16.1 (-1%)	N/A	N/A	N/A	N/A
batch_insert_into_indexed_tree_40_depth_hash_count	N/A	N/A	129	N/A	N/A	N/A	N/A
batch_insert_into_indexed_tree_40_depth_hash_ms	N/A	N/A	0.105 (-2%)	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	72,417	668,302

Transaction size based on fee payment method

| Metric | |
| - | |

[ludamad]

Re organization, so far e.g. the AVM stuff is all over and we've been okay with it, but I'd sympathize with wanting it in its own module. No strong opinions at this time

[fcarreiro]

Re organization, so far e.g. the AVM stuff is all over and we've been okay with it, but I'd sympathize with wanting it in its own module. No strong opinions at this time

But this is not avm, right? :)
I think recently I made some changes and now all AVM files should at least always be under barretenberg/cpp/vm (also the generated ones and the relations). Of course, there's also the unavoidable things in main.cpp. Maybe it can already be made a module? (not sure how cmake works)

[ludamad]

I was just saying I agree with separation but no strong opinions, as I hadn't had with AVM

[ludamad]

do we need all these presets?

[PhilWindle]

Removed the gcc ones.

[ludamad]

why are we using gcc for this?

[PhilWindle]

Removed

[ludamad]

not a fan of the pic name, this is a low level detail for a high level feature. This preset and this earthly command could likely be preset-aztec-world-state or similar

[PhilWindle]

Renamed

[ludamad]

Cmake changes look otherwise good