guide:history@en

Guides

From Multics to Zanzibar

Sixty years of access control, from capability lists and Multics ACLs through RBAC and ABAC to Zanzibar and the open-source systems that followed it, each step with its primary source.

Facts checked on Paper sections §2.1, §3.2.4, §4, §5

The Zanzibar paper describes its own ancestry in §5 Related Work. It cites Multics, UNIX, POSIX ACLs, VMS and Taos for the data model; RBAC for roles; the IAM systems of Amazon, Google and Microsoft for the idea of one ACL store behind an RPC API; Facebook’s TAO as a system of similar scale; and Lamport clocks, Spanner, Chubby and ZooKeeper for the consistency question. This page follows the same threads in time order.

How the ideas lead to Zanzibar

The first multi-user systems had to decide who could touch what. In 1966 Dennis and Van Horn gave each computation a list of capabilities, unforgeable tokens that name an object and grant rights to it (Dennis and Van Horn). Lampson’s 1971 access matrix showed that capabilities and access control lists are two ways of storing the same table, by row or by column (Lampson). Multics took the column view: every segment and directory carried an ACL (Saltzer). Zanzibar is on the ACL side too: it answers “who can touch this object?”.

Operating systems then made the lists cheaper and coarser, and later richer again. The paper traces this itself: in the first edition of UNIX, file flags say “whether owner and non-owner can read or write the file”; by the fourth edition there are read, write and execute bits “for owner, group, and others”; POSIX ACLs add “an arbitrary list of users and groups”; VMS “supports ACL inheritance for files created within a directory tree” (§5). Those four words, permissions, users, groups and inheritance, are what Zanzibar’s data model sets out to support.

From the 1970s, models moved away from per-object lists. Bell–LaPadula and Biba let the system, not the owner, decide by labels; Zanzibar is discretionary, so they are contrast rather than ancestry. Role-based access control (1992) put roles between users and permissions; the paper says roles “are similar to Zanzibar relations” (§5). Attribute-based control, defined in NIST’s 2014 guide SP 800-162, computes decisions from attributes at request time. Relationship-based control, named by Gates in 2007 and formalised by Fong in 2011, decides from relationships such as “member of” or “parent folder of”, which compose (Fong). The paper never uses the word ReBAC, but its relation tuples are such a graph.

What was new at Google was scale and consistency. The paper says Zanzibar “has been in production use for more than 5 years” (§4) as of the July 2019 paper, so it was running by 2014 at the latest; no public source gives a start year. It serves Calendar, Cloud, Drive, Maps, Photos and YouTube (§1). TAO, which the paper compares it with, offers “eventual global consistency”, while Zanzibar provides “external consistency and snapshot reads with bounded staleness” so that it protects against the “new enemy” problem (§5). Lamport clocks were ruled out because they “require explicit participation of all “processes””, and some of Zanzibar’s are “external clients or even human users”. Chubby does not support “high volumes of data, efficient range reads, or reads at a client-specified snapshot with bounded staleness”, and ZooKeeper offers neither external consistency across nodes nor bounded-staleness snapshot reads (§5). Spanner and its TrueTime clock supplied the guarantee (Spanner, OSDI ’12).

After the paper, others rebuilt the design in the open. Ory Keto was rewritten around it in 2021, and SpiceDB, OpenFGA, Permify and Topaz followed within about eighteen months. At the same time policy engines in the ABAC line, OPA and Cedar, matured, and the OpenID Foundation’s AuthZEN working group, formed in 2023, standardised how an application asks an authorization engine for a decision: its Authorization API 1.0 became an OpenID Final Specification in January 2026. The details of each system are on the ecosystem pages.

Timeline

Operating systems

  1. 1966

    Capability lists

    Dennis and Van Horn describe a computation's "sphere of protection" as its list of capabilities, the C-list. Capabilities answer "what can this subject touch?".

    Source
  2. 1971

    UNIX First Edition: owner and non-owner bits

    chmod has six mode bits: read and write for owner and for non-owner, executable, set-user-ID. No group class. (Date from an archive copy; the original manual was not checked.)

    Source
  3. 1973

    UNIX Fourth Edition: group bits

    The chmod page dated 8/5/73 adds set-group-ID and read, write, execute bits for owner, group and others.

    Source
  4. 1973–1974

    Multics ACLs, described by Saltzer

    An ACL on every segment and directory. Presented at SOSP in October 1973, published in CACM in July 1974; Multics itself ran earlier. Zanzibar reference [23].

    Source
  5. 1997–1998

    POSIX.1e ACLs: draft 17, then withdrawn

    Draft 17 (October 1997) became the basis of Linux ACLs; sponsorship for 1003.1e was withdrawn in January 1998.

    Source

Models and standards

  1. 1971

    Lampson, "Protection": the access matrix

    Rows are domains (subjects), columns are objects, cells are access attributes. An ACL is one column, attached to the object; capabilities are a domain's entries.

    Source
  2. 1973

    Bell–LaPadula

    Mandatory confidentiality: no read up, no write down. MITRE MTR-2547 Vol. I (March 1973); the *-property (no write down) arrives in Vol. II (May 1973). Cited from Bell's own retrospective.

    Source
  3. 1975–1977

    Biba integrity model

    The integrity dual of Bell–LaPadula. MITRE MTR-3153 (June 1975); the revised report, MTR-3153 Rev. 1, was issued as ESD-TR-76-372 in April 1977 (DTIC AD-A039324).

    Source
  4. 1992

    Role-based access control

    Ferraiolo and Kuhn, 15th National Computer Security Conference. Zanzibar reference [17].

    Source
  5. 1996

    RBAC96

    Sandhu et al. formalise a family of RBAC models in IEEE Computer, February 1996.

    Source
  6. 2003

    XACML 1.0, OASIS Standard

    An XML policy language that separates the enforcement point from the decision point. The exact approval day in February 2003 varies by source.

    Source
  7. 2004

    ANSI INCITS 359-2004 (RBAC)

    The unified NIST RBAC model becomes an ANSI standard on 11 February 2004; revised as INCITS 359-2012.

    Source
  8. 2007

    "Relationship-Based Access Control" coined

    Carrie Gates, W2SP 2007, as credited in Fong's 2011 paper (abstract and reference [18]). Gates's paper itself was not checked.

    Source
  9. 2011

    Fong: a ReBAC protection model

    Decisions based on the relationship between owner and accessor in a social network; relations compose, unlike roles.

    Source
  10. 2013

    XACML 3.0, OASIS Standard

    The core specification is dated 22 January 2013.

    Source
  11. 2014

    NIST SP 800-162 (ABAC)

    Attribute-based access control defined; published January 2014, updated 2 August 2019.

    Source

Planet scale

  1. 2012

    Spanner

    Google's globally distributed database, with TrueTime and external consistency. Zanzibar stores its tuples in it (reference [15]).

    Source
  2. by 2014

    Zanzibar in production

    The paper says it "has been in production use for more than 5 years" (§4). That puts the start before mid-2014; no public source gives the year.

    Source
  3. 2019

    The Zanzibar paper, USENIX ATC '19

    Pang et al., presented in Renton, WA, in July 2019. The paper this site translates.

    Source

Open source and standards

  1. 2016

    Open Policy Agent v0.1.0

    A general-purpose policy engine with the Rego language; first GitHub release on 14 July 2016.

    Source
  2. 2021

    OPA graduates in the CNCF

    Announced 4 February 2021.

    Source
  3. 2021

    Ory Keto's Zanzibar rewrite

    v0.6.0-alpha.1, 7 April 2021. Keto itself dates from 2018.

    Source
  4. 2021

    SpiceDB first release

    30 September 2021, from AuthZed.

    Source
  5. 2022

    OpenFGA first release

    10 June 2022. Developed by Okta employees; a CNCF Incubating project since 28 October 2025, announced in the CNCF blog on 11 November 2025.

    Source
  6. 2022

    Permify first release

    3 August 2022.

    Source
  7. 2022

    Topaz first release

    25 October 2022, from Aserto.

    Source
  8. 2023

    Cedar open-sourced

    AWS releases the Cedar policy language under Apache-2.0 on 10 May 2023.

    Source
  9. 2023

    Amazon Verified Permissions GA

    A managed service that evaluates Cedar policies, generally available on 13 June 2023.

    Source
  10. 2023

    OpenID AuthZEN working group

    Announced 20 October 2023, to define "standard mechanisms, protocols and formats for communication between authorization components".

    Source
  11. 2026

    AuthZEN Authorization API 1.0 Final

    Approved as an OpenID Final Specification, announced 12 January 2026 (81 approve, 1 object, 25 abstain). The API lets policy enforcement points (PEPs) ask policy decision points (PDPs) for decisions.

    Source

What Zanzibar took from where

The paper is careful about the difference between building on something and resembling it. It runs on Spanner and Leopard; it supports the features of earlier ACL systems; and it calls RBAC roles similar to its relations and the “blessings” of Abadi et al. similar to its tuples (§5).

Which earlier work shows up in which part of Zanzibar?

What Zanzibar took from whereLeft column, earlier work and the systems Zanzibar runs on: Multics, UNIX, POSIX ACLs, VMS (ACLs, groups, inheritance); Abadi et al., 2015 (blessings); RBAC, 1992 (roles); Spanner, 2012 (TrueTime, snapshot reads), green; the Leopard index, a Zanzibar component, green. Right column, parts of Zanzibar: relation tuples and usersets (§2.1); relations and userset rewrites (§2.3.1); external consistency and zookies (§2.2); nested-group checks (§3.2.4). Dashed arrows labelled supports features of, and similar to, run from the ACL systems and from Abadi et al. to tuples and usersets, and from RBAC to relations. Solid arrows labelled built on run from Spanner to external consistency and from Leopard to nested-group checks.Multics, UNIX, POSIX ACLs, VMSACLs, groups, inheritanceAbadi et al. (2015)"blessings"RBAC (1992)rolesSpanner (2012)TrueTime, snapshot readsLeopard index(part of Zanzibar)relation tuplesand usersets (§2.1)relations and usersetrewrites (§2.3.1)external consistency,zookies (§2.2)nested-groupchecks (§3.2.4)supports features ofsimilar tosimilar tobuilt onbuilt on
Solid arrows: Zanzibar runs on it. Dashed arrows: the paper names it as a precedent or a similar idea (§5, §3.2.4).

Notice the split. The data model on the top half is a recombination of old ideas; the paper’s own claim is the unification, modelling with tuples “allows us to unify the concepts of ACLs and groups” (§2.1), where Abadi et al. kept them separate (§5). The bottom half is what made it work at Google’s scale: Spanner for “external consistency and snapshot reads with bounded staleness” (§5), and Leopard, “an indexing system used to optimize operations on large and deeply nested sets” (§3), for groups that pointer chasing cannot serve fast enough (§3.2.4).

Sources