[fastx programmability] allowing objects to own other objects

[sblackshear]

Step 1: fleshing out addresses and authenticators

Today, every object has an owner: FastPayAddress field, where a FastPayAddress is just a 32 byte public key. In the future, an address should be the hash of an authenticator, e.g.

enum Authenticator {
  PubKey(PublicKeyBytes), // existing
  Object(ObjectID), // new, purpose of this issue
  // ... K-of-N multisig, whatever else we want
}

pub struct Address(Vec<u8>)

impl Address {
  pub fn new(auth: Authenticator) -> Self {
   // .. hash authenticator to build the address
  }
}

A transaction will also need to include an authenticator for the sender instead of an address.

Step 2: expand tx authentication logic to cover the new authenticator types

Today, that logic lives here. This should be extended to

• Look at the owner address of each input object
• If the address was derived from the PubKey variant, it should match the hash of the pubkey in the tx's authenticator
• If the address was derived from the Object(id) variant, id should also be an input to the transaction

Step 3: expose Move primitive for transferring an object to another object

This (almost) already exists here. The semantics are much the same as Transfer::transfer: switch the object's owner field to the given ObjectID.

Step 4: define collection types and other code that use this new primitive in interesting ways. E.g.

struct Map {
  /// a heterogenous map keyed by object ID's
  struct Map has key { id: ID, children: vector<IDBytes> }

  public fun insert<T: key>(m: &mut Map, child: T) {
    Vector::push_back(&mut m.childen, ID::id(&child));
    Transfer::transfer_to_id(child, ID::id(&m))
  }
  // ... checking membership, removing items, transferring Map itself, etc.
}

struct Gallery {
  // a heterogenous collection of objects
  struct Gallery has key { id : ID, num_items: u64 }

  public fun add<T: key>(g: &mut Gallery, t: T) {
    g.num_items += 1;
    Transfer::transfer_to_id(child, ID::id(&t))
  }
  // ... removing items, transferring Gallery itself, etc.
}

[gdanezis]

If the address was derived from the Object(id) variant, id should also be an input to the transaction

Could we further require that the owner object was earlier in the list of objects? This makes the implementation a little simpler.

[sblackshear]

Yes, I think that is a very sensible restriction.

[gdanezis]

Ok, from the authority.rs perspective this change is not that difficult: We change the ownership check to check that each objects is either owned by the signer, OR another object already checked. So we just need to keep a hashset of checked object-Ids.

[sblackshear]

After thinking about the interaction with immutable objects a bit, I think the story is slightly more complicated (but still workable). To lead with an example involving end-user X, mutable objects A-C, and ownership chain X -> A -> B -> C:

• A transaction signed by X can take [A], [A,B], or [A,B,C] as inputs. And each object can be passed by value, as a mutable reference, or as an immutable reference.
• Now, consider what happens if A gets frozen. B and C remain mutable, but we must now be careful to only allow B and C to be passed by immutable reference. Otherwise, we have a race--since A is immutable, anyone (not just X) can send a tx that takes A as input and mutates B/C.
• Similarly, consider the case where B gets frozen--we need to ensure C can only be passed as a mutable reference.

Moving away to the example and back to the conceptual level, the property we need to ensure is that:

1. Each transaction signed by X accepts a forest of objects
2. Each roots in the forest needs to be either immutable or owned by X
3. Each edge in the forest needs to satisfy child.owner == parent
4. Each path e1, e2, ... e_n in the forest needs to satify e_n.mutability >= e_n+1.mutability (where we define mut >= immut. Said differently: once you hit an immut on a path, all subsequent edges in the path need to be immut.

[sblackshear]

This feature dazzles me with its power, but it also scares me a bit in the complexity that it creates:

• for authorities in the checking logic
• for users (who can accidentally lock objects by creating owership cycles, or by freezing an parent object with children that the user intended to transfer or mutate later)
• for auditors and tooling that want to reason about code (since this goes beyond the simple tree-based memory of Move and allows users to build arbitrary data structures). To give a concrete example, the Prover cannot help us in code that uses transfer_to_id, and extending it to do so would be (I believe) quite challenging.

Thus, my recommendation is that we take our time in designing adding this feature (and more specifically, not try to get it in for the GDC milestone). As part of the GDC prep work, we will work on a number of concrete use-cases and see where the current programming model hits its limits. I think that will help us see more precisely when this feature is needed and (perhaps) introduce a simpler, but equally expressive version of it.

E.g., one idea is that:

• the stdlib exposes collection modules like Map and Gallery that use transfer_to_id under the hood, but don't expose the transfer_to_id primitive to users
• we write these modules in a way that prevents freezing an object with mutable children and creating ownership cycles impossible by construction
• this would let us keep the simple "earlier in the list" authority checking logic and avoid some major footguns for users.

But just a thought--the use-cases should drive the path forward.