This paper describes a design for an authentication service for a very large scale, very long lifetime, distributed system. The paper introduces a methodology for describing authentication protocols that makes explicit the trust relationships amongst the participants. The authentication protocol is based on the primitive notion of composition of secure channels. The authentication model offered provides for the authentication of “roles”, where a principal might exercise differing roles at differing times, whilst having only a single “identity”. Roles are suitable for inclusion in access control lists. The naming of a role implies what entities are being trusted to authenticate the role. We provide a UID scheme that gives clients control over the time at which a name gets bound to a principal, thus controlling the effects of mutability of the name space.