Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for referenced access control lists. In one aspect, a method includes accessing an object hierarchy for a plurality of objects, each object being representative of one of a storage location or a file. The object hierarchy includes for each object, a respective node, for each object that is a parent object having a child object, a directed edge connecting the node representing the parent object. In addition, for each object, including metadata that includes an access control list identifier that identifies an access control list for the object and that is owned by an access control list root object. The method including receiving updates to an access control list for particular objects, generating a new access control list, and storing the new access control list identifier in metadata for each object that descends from the particular object.