0xPolygonMiden / crypto

Cryptographic primitives used in Polygon Miden rollup
MIT License
101 stars 35 forks source link

`SimpleSmt` insertion optimization #300

Open polydez opened 7 months ago

polydez commented 7 months ago

Currently SimpleSmt recomputes inner node hashes on each insert. It computes and writes hashes starting from inserted node and up to the root. It might lead to unnecessary computations during bulk inserts (for example, SimpleSmt::with_leaves and SimpleSmt::with_contiguous_leaves use insert under the hood).

We can use different approaches for such optimization. For example:

  1. Simply disable hashes calculations during bulk inserts and then create all needed inner nodes with hashes computation after operation. This approach should work fine for populating constructors (with_leaves, and similar).
  2. Mark hashes, affected during insertion, as invalid. Recalculate lazily only invalid hashes on access to root hash. This is little more complex approach, but should work fine for random inserts.
polydez commented 7 months ago

I'd personally use both approaches, at least the first one (not sure, that we need to insert values randomly).

bobbinth commented 7 months ago

I would start with the first one - I think it should get us most of the benefit. The second one can be implemented much later (and only if we discover that we need it).