For the AggLayer bridge-out contract, we need a keccak-based Merkle accumulator which recomputes the root on each withdrawal request (i.e. when a B2AGG note is processed by the AggLayerBridgeOut contract).

The contract doesn't need to store the individual leaves: it only provides the latest "withdrawals root" of this Local Exit Tree. This means that the contract should only store the MMR frontier (up to depth-many elements, where depth = 32 for AggLayer) and the latest root.

These requirements are slightly different than the current std::collections::mmr interface. Particularly, for AggLayer integration we only need add and get_root procedures. Maybe the module name can be a bit different to indicate the adapted functionality, e.g., agglayer::collections::mmr_frontier_keccak:

• add would have the similar interface as the current std::collections::mmr::add, although it would accept down double words as input,
• get_root is a bit more involved and AFAICS we don't have an equivalent in the mmr collection (pack is a sequential hash?). (Q: should this be called compute_root instead, as it will perform a bunch of hashing?)

# ----------------------------------------------------------------------------
# Compute the **full Merkle root** for a target height H,
# treating all not-yet-appended leaves as zeros. This is different
# than folding peaks (std::collections::mmr::pack); here we return the root of the complete
# 2^H tree with the leftmost n leaves set and the remaining right
# leaves filled by canonical zero subtrees.
#
# Inputs:   [mmr_ptr, ...]
#   mmr_ptr  : pointer to MMR structure (similar to the current std::collections::mmr)
# Outputs:  [ROOT, ...]
#   ROOT     : Word (RPO digest) = Merkle root of the 2^H tree
#
# Notes:
#   - This result equals the root of a fixed-height, left-filled, zero-padded
#     binary Merkle tree.
# ----------------------------------------------------------------------------
pub proc get_root
    ...
end

Memory layout at mmr_ptr:

• mmr_ptr[0] : contains the number of leaves in the MMR
• mmr_ptr[1..4]: are padding and are ignored
• mmr_ptr[4..12], mmr_ptr[12..20] : contain the 1st MMR peak, 2nd MMR peak, etc. (double-words)

Internal details

For the implementation details: we need a list of zero-subtree hashes:

# const.Z_0 = zero hash at leaf level 0
# const.Z_1 = zero hash at leaf level
# ...

Not sure if constants are best, ideally we'd have a constants list we could index into.
But this can be mimicked by first loading all the constants into memory and then indexing appropriately when needed.

Usage

Then when appropriate, the AggLayerBridgeOut contract would call into this functionality like so:

const MMR_PTR = 42

pub proc bridge_asset_out
   ...
    push.MMR_PTR
    # => [mmr_ptr]

    <load the frontier from contract storage, save to memory at mmr_ptr>
    # => [mmr_ptr]
   
    <compute the leaf from B2AGG data>
    # => [INPUT_L_U32[8], INPUT_R_U32[8], mmr_ptr]
    
    # add the leaf to the MMR
    mmr_frontier_keccak::add
    # => [ ]

    <update the frontier in contract storage with the freshly re-computed frontier>
    
    # finally compute the root
    push.MMR_PTR
    # => [mmr_ptr]
    mmr_frontier_keccak::get_root
    # => [ROOT]
    
    <save the root to the appropriate storage slot>
end