It's Actors All The Way Down

[It is my pleasure to welcome my colleague and collaborator, Tristan Slominski, as a guest-blogger -Dale]
2017-02-07 EDIT: A previous version of this article used the term Domain instead of Realm.

In the popular implementations of the Actor Model, actor addresses are usually globally available to any other actor desiring to discover them. However, in the original Actor Model formulation[1], the actors can only know about acquaintances explicitly provided to them. One consequence of this requirement is that actor addresses need to be unique and unforgeable. The benefit that this brings to the Actor Model is Object Capability security (OCap)[2]. Object Capability enables an arguably simpler approach to guaranteeing security of the system. The desirability of Object Capability is assumed here and will not be further addressed in this post.

Our pursuit of an implementation of the Actor Model makes an assumption that the implementation should be efficient. That is, if an implementation can be made simpler and faster given certain conditions, then the implementation should be made simpler and faster. This perspective results in a tiered approach to ensuring actor address unforgeability that ends up breaking up into three related but separate strategies. I call these strategies “realms” and they are the Memory Realm, the Trusted Realm, and the Public Realm. These realms span from a single machine and single memory address space, to a trusted cluster of machines, to the Internet.

For each realm I will present an approach to actor address implementation within that realm that satisfies uniqueness and unforgeability requirements.

Memory Realm

The idea of the Memory Realm stems from the observation that when an actor system is executed on a physical machine, each actor can be represented in a unique place in memory. Since no two actors can occupy the same space in memory, the uniqueness requirement can be satisfied in this way.

In order to support the unforgeability requirement a simplifying assumption is made that the execution of the actor system enforces the unforgeability restriction. If actor addresses are represented as memory addresses, this requires that the actor system cannot arbitrarily select a memory address to send a message to. Multiple methods exist that can enforce this guarantee. One method is the usage of Memory Management Unit (MMU) to separate executing actor configurations from each other. Another method is a trusted compiler that enforces memory access policies during compilation.

The combination of unique memory addressing with control over the local machine execution environment enables an efficient realization of unforgeable actor addresses within the Memory Realm.

Trusted Realm

Once the scale of the actor system spans beyond a single machine, the mapping from an actor to a unique memory address is lost. Now, the same memory address on one machine could map to a completely different actor (or nothing at all) on another machine.

The simplifying assumption of the Trusted Realm is trust. The machines that are involved in the actor system are trusted and the communication between the machines is trusted. With these assumptions in place, we need to address only the loss of actor address uniqueness because unforgeability is guaranteed by well behaved execution environment trusted to be implemented correctly as in the Memory Realm.

There are multiple methods that can provide distributed global uniqueness of addresses in a trusted execution environment.

One approach is to randomly select an address within a space large enough where it is unlikely the same address will be selected twice during the relevant lifetime of the actor system. SHA-1 of a random digest is a popular choice with a 160 bit address space. For reference, it is estimated that 328 bits are enough to provide a unique address for every atom in the observable universe. Whatever the size of the address space, the reader should be convinced that an address can be uniquely generated via a random selection process that will guarantee the uniqueness property needed to satisfy Trusted Realm actor address requirements. Paired with this approach would be a proxy mechanism for mapping between Memory Realm address and a Trusted Realm address implemented within the Memory Realm itself.

Another approach, which avoids the mapping step and simultaneously provides routing information, would be to pair a host identifier (where uniqueness is enforced within the Trust Realm) with memory addresses from the Memory Realm into a single address.

Whatever the approach, if we have a method (one presented here or otherwise) to select unique addresses in a Trusted Realm, which encompasses multiple Memory Realms, it is possible to enforce unique and unforgeable actor addresses.

Public Realm

Lastly, we are faced with an untrusted network and untrusted machines between Trusted Realms. The known solution to communication over an untrusted medium is point-to-point encryption, in our case the public key variant of point-to-point encryption[3].

An actor address in the Public Realm becomes a public and private key pair. The public key is the address of the actor that is made known to trusted actors and is unforgeable in the sense that only the intended recipient can decode the message meant for it. The name “public” is a misnomer in this context. The “public” address should not be broadcast or announced to the world. Anyone with the “public” key has the capability to send messages to that actor, therefore, it is important that the “public” key be treated as a secret to maintain the basis for OCap security analysis.

This secrecy of “public” keys implies that there is some initial out-of-band exchange of keys between Trusted Realms prior to attempting communication across the Public Realm. Once the initial out-of-band key exchange is complete, any new actor address in form of a public key can be securely transmitted to an already known actor as part of an introduction protocol because it will be contained in an encrypted message sealed with the recipient’s key[4]. Thus, no address leakage occurs and unforgeability is guaranteed by strength of the encryption protocol chosen.

The Public Realm approach encompasses communication between a Trusted Realm and any external system, not necessarily another Trusted Realm. With cryptographic actor addresses, the other party need not be an actor system at all. Because a Trusted Realm should only communicate capabilities it is willing to share with the other party, as long as the other party can send messages back, the cryptographic actor addresses within the Public Realm are sufficient to guarantee unforgeability for the use of those particular addresses. They become public gateways (“receptionists”) of the Trusted Realm and should be treated as such.

Conclusion

The realm approach to solving the problem of unforgeable actor addresses strikes a balance between an efficient implementation and the guarantees required for OCap. A sort of benchmark for OCap introduction protocols that touch on the finer issues of unforgeability and trust is the Grant Matcher Puzzle[5]. The realm approach to solving the problem with its recognition of the existence of Public Realm and point-to-point encryption seems to be sufficient to correctly navigate the Puzzle without sacrificing transparency of man-in-the-middle proxies (another useful Actor Model feature) by using cryptographically implemented Sealer/Unsealer pairs.

References

[1]

C. Hewitt. Viewing Control Structures as Patterns of Passing Messages (http://dspace.mit.edu/bitstream/handle/1721.1/6272/AIM-410.pdf). Journal of Artificial Intelligence, 8(3):323-364, 1977. Accessed on 2 Oct 2013.

[2]

(http://www.erights.org/elib/capability/overview.html) Accessed on 2 Oct 2013.

[3]

C. Hewitt. Letter to the editor: For Privacy and Security, Use Public Keys Everywhere (http://cacm.acm.org/magazines/2013/9/167144-for-privacy-and-security-use-public-keys-everywhere/fulltext). Communications of the ACM, Vol. 56 No. 9, Pages 8-9. Accessed on 3 Oct 2013.

[4]

(http://www.erights.org/elib/capability/horton/mailkeys.html) Accessed on 3 Oct 2013.

[5]

(http://www.erights.org/elib/equality/grant-matcher/index.html) Accessed on 2 Oct 2013.