Delete appointments from the tower

[sr-gi]

We come from here: talaia-labs/python-teos#158

To state the problem:

We'd like to allow the user to delete some data from the tower. This serves two purposes: first, it allows irrelevant data to be wiped (like data from already closed channels), and second, it allows the user to reuse part of the slots from its subscription, so it's kind of a win-win situation. Except this are not that easy (at least not in accountable mode).

In accountable mode, the tower hands agreement receipts to the user for every bit of data it watches, allowing deletion means that the tower needs to keep proof of the deletion request for each deleted item, otherwise, the user could:

• Request some data to be watched
• Ask for a deletion of the data
• Trigger the data

Given the tower won't have the data anymore the user could claim the tower misbehaved.

Keeping proof of the deletion, however, implies that if the tower is giving back slots so the user is incentivized to request data deletion of irrelevant data, a malicious user could simply:

• Request some data to be watched
• Ask for the data deletion
• Rinse and repeat

And the tower would need to store data for free until the end of the subscription.

I think there may be multiple ways of solving this issue, for instance not giving slots back straightaway but giving a discount on subscription renewal (this could even be implemented with bearer tokens so the discount can even be given to someone else). But approaches like these are certainly not trade-off free and would need some proper analysis to make sure they are not exploitable (apart from this meaning the tower is reducing the data storage but not completely whipping the data related to the relevant appointments, modulo the data being actually smaller than the proof, which should be the case).

Back in the day discussing this with @ZmnSCPxj, he proposed that this may be solvable with accumulators (rolling set commitments I think was the exact term), so I'm starting to consider this option.

[sr-gi]

Given the user is not expected to store any data regarding all appointments that have been sent to the tower, but the accumulated state instead I'm wondering how the rolling commitment may work, especially with respect to how would the tower reconstruct a proof if required.

My first thought was going for something like:

// This is just rust pseudo-code
[...]

let state = if request.is_insertion() {
    if state.is_none() {
        request.data
    } else {
        sha256(state, add, request.data)
    }	
} else {
    if !appointments.contains(request.data) {
        // Error, cannot remove something we don't have
    } else {
        sha256(state, del, request.data)
    }
};

// Verify user sig
[...]
let user_sig = request.sig();
let sig = sign(user_sig, tower_sk);

So, in a nutshell, the state starts empty and is assigned to the first addition. For every new addition/deletion, the state is the previous state hashed with the operation (add/remove) plus the data to be added/removed. We conditionally bound the deletion of data to have the datum, this covers both the base case (no data in the accumulator) and trying to remove something twice. Also, given the user knows the latest state and the new piece of data to be added/removed, it can construct the newest state and sign it, meaning that the tower signature can simply be the signature of the user's (modulo it being verified).

I see one issue with this thought: The tower needs to store an ordered list of operations so it can reconstruct the last state.

---

I think it would be way better to have another kind of accumulator for this where insertion/deletion can be easily proven. For the tower, the best would be something like a binary tree where leaves are the ordered appointment locators. In this way, the tower could rebuild the state by simply creating the merkle root of all appointments without the need of storing anything else.

I guess the requirements for this are:

• The verifier only has the latest state of the accumulator and the data to be added/removed
• The verifier needs to be able to verify that the accumulated state n equals n-1 plus performing the addition/deletion of the provided data
• The prober has all pieces of data, but no additional information about them wants to be stored (such as the order in which the operation where made, or intermediate signatures of the state)

Does something like this exist?

[sr-gi]

Also tagging @bigspider, I know you love accumulators and Merkle trees :P

[bigspider]

If what you need is maintaining a set S where you might remove/add elements, and prove both membership and non-membership, I don't think a Merkle tree can work (only works well on additive).

If I'm not missing anything, though, it sounds like a sparse Merkle tree should work: imagine the complete, giant Merkle tree with 2^256 leaves, corresponding to all the 256-bit strings. Any set S can be represented by the set S' = {H(x) such that x is in S}. Now if you consider the subset of leaves of the giant Merkle tree corresponding to the elements of S'. That is, for an element x you consider the leaf of the giant Merkle tree with index H(x), and you put a 1 there; for any other leaf, there's implicitly a 0.

The next step is to compress this tree further: if at some point you're at an internal node that contains just one leaf... just store the leaf there instead of going down 256 levels.

(Not sure this is the best approach, but the general idea should be correct)

On this structure, you can prove both membership an non-membership, and also prove correctness of updates. Because almost all the leaves are 0, you can keep the structure implicit, so the intractable size is not an issue; proofs still require O(log(n)) hashes.

Not sure how well it does in practice, and probably not as easy to implement as a normal Merkle tree − but looks like there's a rust crate if you want to look into it: https://crates.io/crates/sparse-merkle-tree.

[sr-gi]

I've written some thoughts on this so it can be easily shared and discussed. Just for reference:

https://gist.github.com/sr-gi/f91f007fc8d871ea96ead9b27feec3d5