Removal of identities

[cichaczem]

No description provided.

[kustosz]

Here's a list of required steps:

1. Changes in tree versioning. In the sequencer, we currently assume consecutive inserts and therefore leaf index becomes a natural proxy for an ordered version tag. With arbitrary updates, this is no longer enough to reconstruct the tree, so we need to impose additional ordering.
2. A new circuit for semaphore-mtb, that will support removal. Conceptually it is almost identical to the one we have for insertions, the algorithm is still correct, except indices and previous leaf values need to become parametrized, rather than computed in circuit / assumed zero. Since this is already assumed to exist in the contract, the circuit needs to follow the contract's input format, see here. This also needs to be accompanied by a second API endpoint in MTB.
3. A deeper discussion of SLA on this. Allowing member removals has potential consequences for protocol security – these removals will, by necessity, propagate with a significant delay (no shorter than root validity period). We need to make sure this is properly handled by the clients.
4. Following 3, we need to figure out an algorithm of batching these member updates interspersed with insertions. The batch insertion path is much cheaper gas-wise, so it may be preferable to apply updates lazily. Alternatively, since insertion is also an update, we could give up and include insertions in update-type batches (and hope updates are rare). This decision must be made based on cost vs. finality time grounds.

[cichaczem]

Related prover task