o1-labs / o1js

TypeScript framework for zk-SNARKs and zkApps
https://docs.minaprotocol.com/en/zkapps/how-to-write-a-zkapp
Apache License 2.0
500 stars 110 forks source link

IndexedMerkleMap: Support 0 and -1 keys #1671

Closed mitschabaude closed 3 months ago

mitschabaude commented 3 months ago

Stacked after https://github.com/o1-labs/o1js/pull/1666

Why

This refactors how IndexedMerkleMap represents the maximum possible key. Previously, there was a hard-coded entry of nextKey: -1, i.e. the largest possible value, that was present from the beginning.

This had two limitations:

The first point is minor (we probably don't need -1 as a key) but the second point is very annoying, because 0 is the natural value for a dummy key. Setting key=0 to value=0 (the initial value) is a very convenient way to represent a dummy update, because it doesn't affect the tree at all. So with this PR, dummy updates of the Merkle map are supported out of the box without any additional logic.

How

The changes here make both 0 and -1 usable like any other keys. (As before, the Merkle map is initially populated with (0, 0) as the only key-value pair.)

The issue is solved by doing the same as the Aztec implementation and making 0 act as both the smallest and the largest key simultaneously. So, we always have nextKey: 0 in the node with the largest currently stored key, and that node acts as a valid low node for the 0 key.

Implementation-wise, it just means adding a couple of special cases to the key comparison functions. The constraints increase but not significantly:

indexed merkle map (get) 461
indexed merkle map (get option) 990
sparse merkle map (get) 4208

indexed merkle map (insert) 1706
indexed merkle map (update) 905
indexed merkle map (set) 1893
sparse merkle map (set) 8160

indexed merkle map (assert included) 460
indexed merkle map (assert not included) 517
indexed merkle map (is included) 523
mitschabaude commented 3 months ago

I cherry-picked a fix here so that IndexedMerkleTree is fully functional when merged