Certified, scalable map.

[matthewhammer]

(Moved from Jira, SDK-284.)

This ticket is tracking a certified scalable map for base, which is still missing, at least in full.

What exists today in Rust and Motoko

There is a Rust implementation of a certified RB-Tree and comparing it with the existing motoko merkle tree it seems like the missing gap is that the former uses a RBTree structure to enforce balance, whereas the later has no rebalancing logic or policy in place.

As we discussed in the Languages team meeting on certain occasions, a few points to consider:

• Rebalancing is needed to ensure that an adversary that controls insertions does not control the shape of all of the certificates (making them too large and too expensive)

• It seems reasonable for us to close this gap in the base library, or somewhere.

• But even if we do, other custom DBs in the wild may only hope to follow this certified map code as a pattern, rather than reuse it as a library, since they have their own data structure compositions.

• But perhaps there is still some hope to create a modular library, as we also discussed; but such a library would be something in addition to what exists today in the Rust CDK, where no such independent library exists (AFAIK).

• This certified map would be a first step towards a more general solution, which should subsume it.

Additional partial solution

@di-wu authored another partial solution: GitHub - aviate-labs/certified-map.mo: [WIP] Certified Map in Motoko

I say it’s “partial” because it seems like

• the delete operation is missing for the RBTree (so insert only, until that operation is added),
• and the HashTree structure does not rebalance (so the certificates could become too long to be practical, especially if an adversary has write access).