0xMiden / 0xMiden/protocol

AggLayer: further optimize frontier loading

Offen
#2,857 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
agglayer
Vorherrschende Sprache
Rust
Sterne
132
Forks
167
Ø Merge
1 T. 23 Std.
Gemergte PRs (30 T.)
110

Beschreibung

As described in [this commit](https://github.com/0xMiden/protocol/pull/2752/changes/13f0d9068458616c730c5f2f484794a445b53b00#diff-3181b2b0e91167fbd1aafc4c9c2f97deac70118c873e35feac4a849ed27003e4R442-R455), there is potentially further room to improve the `B2AGG` note cycle counts:
```
#! Note, that not all entries that are written to storage will be meaningfully read again.
#! Some frontier heights may be written multiple times before they are read again. For example:
#! for a tree of depth=4, the frontier entry at height=2 will be written with the pattern 0b_X0XX:
#! - num_leaves = 0b_0000 (0),
#! - num_leaves = 0b_0001 (1),
#! - num_leaves = 0b_0010 (2),
#! - num_leaves = 0b_0011 (3),
#! before it's ever read when inserting the 5th leaf (when pre-insert num_leaves = 0b_0100 (4)).
#! Notice that only the last write here is meaningful.
#!
#! This pattern is later repeated for height=2 but when the upper bit is 1:
#! - num_leaves = 0b_1000 (8),
#! - num_leaves = 0b_1001 (9),
#! - num_leaves = 0b_1010 (10),
#! - num_leaves = 0b_1011 (11),
#! before it's read again when inserting the 13th leaf (when pre-insert num_leaves = 0b_1100 (12)).
#!
#! This is a little wasteful, but already better than the previous implementation, which
#! unconditionally saved all frontier entries to storage.
#! TODO: potential room for optimization here? Need to see if this affects root computation
```

If I'm not mistaken, for a tree depth=32, we only have 1/32 meaningful writes.

One thing to note is that they might not be evenly distributed (TODO confirm this?), which might lead to more variance / unpredictability in cycle counts across different `B2AGG` notes, although we already have a small degree of variance to due how many reads vs. writes are performed.

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.