[Protocol3] Decrease merkle tree depths

[Brechtpd]

Our current tree depth sizes:

Accounts: 24 (16,777,216 unique accounts / exchange)
Tokens: 12 (4096 unique tokens / exchange)
Trade History: 16 (65536 slots / tokenS / account)

Some of these are larger than needed. Updating these trees in the circuits is our main bottleneck next to data availability (which will be optional). By decreasing these we lower the number of constraints which increases our achievable throughput.

I propose the following:

Accounts: 20 (1,048,576 unique accounts / exchange)
Tokens: [8, 10] (256 - 1024 unique tokens / exchange)
TradeHistory: [12, 14] (4096 - 16384 slots / tokenS / account)

The Tokens tree is updated the most frequent so lowering this is the most important, then the Accounts tree and then the TradeHistory tree.

[dong77]

I agree with smaller trees. 20 for accounts, 8 for tokens, and 14 for trading history seems ok for the near term. In the long term, way may even allow DEX to config these numbers on exchange creation.

[dong77]

Will any of these depths "configs" be visible on smart contract level?

[Brechtpd]

The only 'logic' that needs to be changed is in the withdrawFromMerkleTree where the length of the merkle proof changes. The genesis merkle root value will also change.
There are also a few places where tokenID is assumed to need 16bits and we only need 8bits, but I don't think we should change that in the smart contract because savings for this will be insignificant (and it will be easier to switch back to something bigger again if needed).

This shouldn't be a lot of work and should decrease the number of constraints by ~10-15%.

[Brechtpd]

It's also not really possible to make these configurable for every exchange. Every different configuration would need its own set of circuits.

[dong77]

I totally agree. I would only suggest these configs are somehow refected by those constant variables in the smart contract.

[Brechtpd]

Done in #115

Constraints/ring decreased from 650,000 -> 525,000, a nice 20% reduction.
I also got the correct constraint numbers of the circuit without data-availability, which is a bit cheaper than with data-availability: max throughput increased from 350 rings/second to 450 rings/second.

[dong77]

This is great. I'll close this issue then.