[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.

[lxfind]

I have a few questions regarding this:

1. Although I could see the concept of implementing a Map using this, I couldn't see how such a Map could ever be useful in practice. First of all, it's not something you could really interact with meaningfully in a smart contract, because the map does not store objects directly. So you cannot retrieve the object from it within Move. Even worse, if we want to do something about the map from outside of Move by making a transaction, say remove an object from it, when making a Move call to the map module, we would end up having to pass all objects in the map to the Move call (unless we know which object will be removed in advance, which is rare because otherwise why would we need a map if we always know which object to operate on).
2. Let's say we support multi-sig address and can be created on-the-fly with a convenient API. Is there anything that cannot be done with such a feature, but can only be done through object owning other objects?

[gdanezis]

@lxfind I think the key to point 1 is:

unless we know which object will be removed in advance, which is rare because otherwise why would we need a map if we always know which object to operate on

When a client is about to execute an order in fastx it knows exactly what the result of the execution is. It does not execute the order to perform the computation. It executes the order to change the global state, and convince others through fastx of the result of the computation.

So you are right that the client would track all objects on the map. Then run the insert or remove, or whatever mutable operation on the map. Then record which specific branches/leaves are mutated, and then create an order that only refer to this small (O(logN) hopefully) subset.

At the end of all this it has managed to convince the world of the correctness of a transition in a collection, with an O(logN) length order and O(logN) writes, rather than O(N) writes (if it re-writes the whole collection in an object).

Now to the point of whether we can implement all this in a different way: I think that by restricting transfer (as we do in move modules) we can still implement maps -- we define a module that makes branches/leaves of a BTree for example, and does not allow them to be transferred. Then their mutation is subject to the module logic, so inserts / removes are correct. Is that right @lxfind / @sblackshear ?

I think the only downside of this is ... you cannot transfer such structure :( . Whereas if the branches / leaves `belong' to a root BTree structure if you transfer this root structure you end up transferring the rest of the tree as well.

[lxfind]

Had an offline chat with Sam. So the name "Map" is not quite accurate here. It's rather called "Bundle", which contains a collection of objects, and its main purpose would be that it's convenient to transfer a bundle simply by transferring the root object.

[gdanezis]

Ok, now objects can own other objects. There are still things to design but this is done. Thanks @lxfind !