Proposal: Efficient entity ownership transfer

[bedeho]

Background

In the existing content directory, the only way of reassigning ownership is to transfer ownership of channels. There is no way to transfer ownership of entities in the version store, and the only way channels can be transferred is precisely because they live (incorrectly) in the content directory working group.

Problem

Reassigning entity ownership is going very likely going to be needed functionality, however, implementing it is not trivial due to the new same owner on references constraint which is going to be introduced in 2.0.

#175

This is done using field ClassPermissions::referenced_entity_must_have_same_controller. A naive change of the EntityPermission::controller, e.g. in update_entity_controller, for an entity, will break all inbound references from other entities.

While introducing an index from can allow us to at least detect whether a naive ownership change is OK or not, this is not sufficiently practical, as we would just be blocked from making the transfer we want.

Another alternative would be to do some sort of tree search to using the index, going from entity to entity, to find the full set of entities impacted, and then update the controller value for all of them in concert. So for example, changing ownership of a channel could involve an initial search that enumerates some hundreds or thousands of entities, and then updating the controller value by iterating through and mutating. To prevent DoS attack one could cap the size of such a search upfront.

This second solution highlights an obvious property of the entity relationships that are not explicitly modeled but could be, namely that entities are organized into trees, based on their referencing properties, where all entities have the same owner. If we just embrace this, the constant time ownership transfer is possible.

Solution

We allow entities to have their controller be defined not only as a specific EntityController, but also be simply pointing at another Entity and having the same controller as this entity. Notice that this entity may itself have the same policy. This indirect ownership specification should obviously be cycle free, something that must be ensured when changing ownership of an entity.
We should also limit how deep this can go, and this must be ensured both when creating entities, and changing ownership of entities. At an implementation level, we can do

/// Owner of an entity.
enum EntityController<T: Trait> {
  Group(T::GroupId),
  ActorInGroup(ActorInGroupId<T>),
  SameAsEntity(EntityId<T>)
}

Notice that an entity can have controller = EntityController::SameAsEntity(x), where x is the id of an entity from another class. We also have to update the way controllers are assigned to entities, currently via InitialControllerPolicy, to be something like

/// Who will be set as the controller for any newly created entity in a given class.
enum InitialControllerPolicy {
  ActorInGroup,
  Group,
  /// SomeAsEntity for some entity of the given class
  SameAsEntity(ClassId<T>)
}

Create entity

We must also update create_entity to allow for the specification of a possible InitialControllerPolicy::SameAsEntity value, but this is only valid when the class is in this policy mode, so it must be optional. Moreover, we must check that adding the entity does not exceed the max depth of the indirect ownership specification. Obviously, there is no way to introduce a cycle when introducing a new entity, so this problem needs not to be kept in mind.

Authentication

Whenever one authenticates, which typically requires providing as: ActorInGroupId<T>, the authentication logic must climb the tree of SameAsEntity values, until it gets to an entity which has a direct ``EntityController` value. We can trust that this process concludes in a timely manner, by virtue of constraints that are enforced on there being no cycles and max depth.

Change ownership

The primary constraint one must respect in this transition is to not grow the indirect ownership tree any deeper than a given constant value in the runtime. Computing this requires some iteration, but it is all bound by 2*the old depth constraint.

Question

This change is non-trivial, its needs a proper sanity check.

[bedeho]

V2

Problem

This proposal ended up being broken, as observed by @iorveth, because it does not deal with inbound same owner references to the entity. Instead, we are doing this simple approach below.

Solution

I was thinking about this yesterday, and the only solution I could see which was constant time + simple + would always work was as follows:
- for each entity, count the number of references that are same owner separate, not just the total number.
- only allow ownership transfer when the entity 0 such inbound same owner references.
- for any property value the entity has which are same owner references, the caller must provide a new value which respects the new owner.

To use this in practice, it will require doing some setup work, for example: Lets say you want to move a video from one channel A to another B.
However, you have the problem that the video is also in a playlist under channel A, and this playlist has same owner reference to the video.
This means that you must first manually remove the video from the palylist in channel A, then transfer ownership.
This could be done as a batch transaction, which is more practical. Also the lead (who is doing the work) would not need to undersand this
in detail, the user application could do this directly as needed.

[iorveth]

Closed by #396