0xMiden / 0xMiden/miden-vm

`SimpleSmt` insertion optimization

Ouverte
#3,488 3 commentaires 1 réaction 0 personnes assignées Voir sur GitHub
merkle
Langage dominant
Rust
Étoiles
772
Forks
352
Merge moyen
1 j 12 h
PR mergées (30 j)
93

Description

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.

Guide de contribution

Ouvrir le guide de contribution

Évaluation

Cette issue n'a pas encore été évaluée.

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.