Data repository and method for promoting network storage of data

CROSS-REFERENCE TO RELATED APPLICATIONS

0001This application is a continuation application of and claims priority to U.S. application Ser. No. 09/785,535, filed on Feb. 16, 2001, which also claims priority to U.S. Provisional Application Ser. No. 60/183,466, filed Feb. 18, 2000 (incorporated by reference herein).

BACKGROUND OF THE INVENTION

0002For almost as long as there have been computer networks, there have been schemes which allow computers to access each other's file systems over the network in much the same manner as they access their own local file system. The first widely used remote file access protocol was Sun Microsystems' network file system (NFS), which became very popular with the rise of Unix in the mid <b>1980</b>'s (see B. Nowicki, “NFS: Network File System Protocol Specification,” Network Working Group RFC1094, March 1989). At about the same time, the SMB network file sharing protocol was developed by IBM for use with their PC's. Subsequent versions of SMB have become widely used on networked PC's running Microsoft Windows, and on their fileservers.

0003Keeping data in networked file systems allows users to access the same data environment from different workstations on the network, and greatly simplifies system administration and the sharing of public data. For these and other reasons, it is expected that network data repositories will become widely popular among PC users as soon as typical PC network connections become fast enough to make substantial remote storage of data practical. Indeed, some Web-based services which make specific types of user data accessible from any Web browser are already popular—for example, email services and appointment calendars. Servers for individuals' Web pages also follow the network-data model.

0004Many companies are offering additional Web-based services which store their data remotely, seeking new applications that will become popular. Some of these companies also offer substantial amounts of free network-based file storage. The greatest obstacle to the acceptance of these new network-based services has been slow network connections. Most computer users currently connect to the network through a telephone modem, which provides them with a connection that is about 1000 times slower than the I/O bandwidth to their local hard disk. This makes it relatively inconvenient to use remote network-based storage for most of the applications that these users now run on their local file system.

0005Some companies currently sell network-based backup services to PC users. For a fee, these companies provide a combination of PC software and networked storage space that allows users to keep a copy of their most important data remotely. For privacy, the PC software encrypts user data before sending it to be stored, using the user's individual public key. Some of these companies also offer Web-based access to backed-up data. Thus far, these companies have not achieved an appreciable penetration into the PC user market. Slow network connections, the cost and effort involved in obtaining and using such services, and a low perceived benefit attached to maintaining backups of file data, have been major obstacles. For the moment, most of the Gigabytes of programs and data that users accumulate remain exclusively on their local hard disks.

0006Use of network storage is also encouraged by techniques which speed up network file transfers. One such technique involves the concept of a “digital fingerprint” of a file, also called a “hash function”, a “content signature” or a “message digest” (see R. L. Rivest, “MD4 Message Digest Algorithm,” Network Working Group RFC1186, October 1990). A fingerprint is a fixed-length value obtained by mixing all of the bits of the file together in some prescribed deterministic manner—the same data always produces the same fingerprint. The fingerprint is used as a compact representative of the whole file: if two file fingerprints don't match, then the files are different. For a well designed fingerprint, the chance that any two actual files will ever have the same fingerprint can be made arbitrarily small. Such a fingerprint serves as a unique name for the file data.

0007Fingerprints have been used for many years to avoid unnecessary file transfers. One application of this sort has been in Bulletin Board Systems (BBSs), which have used fingerprints since the early 1990's to avoid the communication cost of uploading file data that is already present in the BBS, but associated with a different file name. Fingerprints have also been used in BBSs to conserve storage space by not storing duplicate data (for an example of both uses, see Frederick W. Kantor's Content Signature software, FWKCS, which has been in use by bulletin boards such as Channel 1 since at least 1993). These BBSs maintain a table of fingerprints for all files already present. When a new file is uploaded for storage on the BBS, its fingerprint is taken. If the BBS already contains a file with the same fingerprint (regardless of the file's name) then the duplicate data is not stored. Similarly, a client computer wishing to store data into the BBS can compute the fingerprint of the file that it wishes to send, and send that first. If a file containing this data is already present in the BBS, then the client is informed and need not send anything.

0008D. A. Farber and R. D. Lachman, in U.S. Pat. No. 5,978,791 (Data processing system using substantially unique identifiers to identify data items, whereby identical data items have the same identifiers, filed October 1997) carry the idea of file fingerprints a step further, using them as the primary identifier for all data-items stored in a file system. In their scheme, not only are fingerprints used to avoid unnecessary transmission and duplicate-storage of file data (as in the BBS scheme mentioned above), but they also use fingerprints directly to gain read access to data. In this scheme, access to “licensed” data is controlled by associating explicit lists of licensees with specific data-items. Such a control mechanism doesn't scale well when applied to intellectual property protection in general. Any data-item added to the system which is copyrighted, for example, would have to have attached to it an explicit list of all users who are legally allowed to read it. Otherwise someone can give out access to the data-item to everyone that uses the file system by anonymously publishing the fingerprint of the data-item. Constructing an explicit legal-access list for each data-item is in general cumbersome, difficult and intrusive.

0009Furthermore, existing schemes which use fingerprints to identify redundant data and avoid unnecessary transmission and storage depend upon the storage system being able to examine previously stored data. If users independently encrypt their data for privacy, they can't take advantage of each others data to save on transmission or on storage. If data is unencrypted, then the storage system maintainers have complete access to all user data. They may be tempted or coerced into looking at this data, and in some situations may be legally obliged to provide parts of it to third parties.

SUMMARY OF THE INVENTION

0010In general, the invention features a method for providing naming and access control of data items in a data repository, the method comprising having a first client program deposit a data item in the data repository, the depositing including determining a digital fingerprint from the data item, and storing the data item in the data repository at a location or locations associated with the fingerprint, having the first client program specify an object name for an object that comprises a set of data items, storing in the repository an association between the name and the set of data items, and allowing the client program to retrieve a data item from the set of data items by specifying the object name and without providing the digital fingerprint of any data item or composite of data items.

0011In preferred implementations, one or more of the following features may be incorporated. A second client program may initiate a process for depositing a second data item in the data repository, wherein the second data item may be identical to the data item stored by the first client program, the process including determining a digital fingerprint from the second data item, determining from the digital fingerprint that a data item identical to the second data item is already stored in the data repository, and relying on the data item already stored in the data repository for storage of the second data item rather than storing a separate copy of the second data item. No mechanism may be provided that allows retrieval of a data item based on its fingerprint. The object name or information derived from the object name may become part of an access authorization credential that includes information that identifies a repository user or set of users. The access authorization credential may be supplied by the first client program in order to retrieve a portion of the associated named set of data items. A named object may be deleted from the repository and information associated with its references to its component data items may be modified. The last object which references a data item may be deleted and the data item itself may be deleted from the repository. Deletion of a data item which has been shared as a component of a plurality of named objects may depend only upon whether or not all of the plurality of named objects have been deleted. The set of data items may comprise a single data item.

0012Other features and advantages of the various aspects of the invention will be apparent from the following detailed description and from the drawings.

DESCRIPTION OF THE DRAWINGS

0013<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram depicting a user's query to the repository to determine if data is present, and transmit it if necessary.

0014<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram depicting the creation of a named object to secure future read access to a data-item.

0015<figref idref="DRAWINGS">FIG. 3</figref> is a block diagram depicting a read operation using a named object.

0016<figref idref="DRAWINGS">FIG. 4</figref> depicts how a mirroring client can be downloaded and run on a user's computer with very little effort, time or user supervision.

0017<figref idref="DRAWINGS">FIG. 5</figref> depicts the data-item encryption process, which produces an encrypted data-item that is user-independent.

0018<figref idref="DRAWINGS">FIG. 6</figref> depicts a way to allow a user to prove ownership of a named-object, without requiring the repository to hold information from which it can identify the user.

0019<figref idref="DRAWINGS">FIG. 7</figref> illustrates the steps involved in depositing a composite-item and associating it with a named-object.

0020<figref idref="DRAWINGS">FIG. 8</figref> illustrates the steps involved in reading a portion of a composite-item.

0021<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram depicting a user's request that the repository modify a named object to point to new data in the storage.

0022<figref idref="DRAWINGS">FIG. 10</figref> is a block diagram depicting an embodiment of the repository's timestamping service.

0023<figref idref="DRAWINGS">FIG. 11</figref> is a block diagram depicting an encryption scheme based on a reversible cellular automaton.

DETAILED DESCRIPTION

0024This invention deals with the organization and operation of a network-based data repository and an associated data services business. This organization and method of operation are designed to make it both feasible and attractive for computer users with slow network connections to store a copy of their local file system data in remote network-connected storage. The same repository organization is also designed to provide efficient storage and data transmission for users with high-bandwidth network connections. This organization addresses feasibility and attractiveness not only in technical matters, but also in societal and legal matters, such as privacy and copyright.

0025The envisioned data repository consists of a set of data storage devices connected to the Internet, along with the hardware and software that link them together. These storage devices are arranged in groups at widely separated geographical locations, in order to minimize the impact of localized disasters, and to also minimize network congestion. Erasure-resilient coding techniques operating over the network are used to ensure that data is never lost (see the April 1989 paper by Michael O. Rabin, “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance” in the Journal of the ACM, Volume 36 number 2, pages 335-348).

0026This repository is unusual in that, like the BBS systems cited above, from a logical standpoint it contains only a single copy of each data-item stored in it no matter how many repository clients (i.e., computers running software acting on behalf of human users) store files into it containing the same data-item. Any replication of data is done purely to assure data integrity (i.e., to make sure data is correct) and to improve data availability (i.e., to make sure a copy of the data is available) and accessibility (i.e., to make sure data can be accessed reasonably quickly). A pointer to a data-item already contained within this repository can be constructed directly from a copy of the same data-item present on a client computer, without the aid of the repository data-servers. Such pointers can be communicated to the repository in place of the actual data-items themselves.

0027The unusual organization of the repository is a key element in making significant network storage practicable for computers with slow network connections. Advantage is taken of the fact that most of the data on a typical computer duplicates data that is also present on other machines: operating system files, applications, and data files that have been downloaded over the network or copied from removable media. In order to transfer such files to the repository, client software will typically only have to send a pointer, since the repository will already contain a copy of the data, sent earlier by some other client. An important element in the scheme is arranging to share data in this manner without compromising the privacy of user data—this is accomplished by sharing encrypted data.

0028This is a key difference from prior art. Previous schemes have used digital fingerprints (hashes) to avoid communicating data already present at the destination. In the present scheme, the data that is communicated is first encrypted. The encryption is performed using a key derived from the data itself, and this key is never seen in an unencrypted form by the repository servers. Since independent client programs encrypt the same data-item in the same manner, fingerprints can be used to avoid duplicate communication. Unique data is automatically encrypted in a unique manner. Data-items with a length comparable to the fingerprint may be encrypted conventionally without much affect on bandwidth usage or storage. This alleviates concerns that short data-items may be decrypted by guessing them.

0029To further allay privacy concerns, the repository is careful to avoid storing information that is sufficient to identify who has access to a particular data-item. Additional information provided by user access credentials allows a link to be created transiently at the moment of access. This means that common data-items (such as components of popular programs) can't be traced back to their owners using data present in the repository alone. This also avoids some legal issues associated with subpoenable records.

0030A major concern for a widely used data repository is to avoid becoming entangled in intellectual property disputes. For example, the Farber/Lachman scheme discussed earlier doesn't deal adequately with the issue of copyright. Unless all copyrighted items are individually identified and labeled with all legal accessors, the scheme fails to protect copyright. The fingerprint of an unlabeled data-item can be broadcast anonymously, giving everyone receiving the broadcast read access to the data-item. In this scenario, the repository company would be unable to point to a responsible party other than itself. The present scheme ensures that there is always a responsible party when access is broadcast: it precludes anonymous broadcast of access. For example, assume that a client has a data-item, and wants to secure future access to a copy of this data-item which it determines, using fingerprints, is already present in the repository. That is, the client wishes to deposit the data-item into the repository without retransmitting it. The repository must determine that the depositor has more than just the fingerprint, because that could have been broadcast anonymously. It therefore challenges the depositor, asking for a small amount of information (such as a specified hash) that proves that the depositor has a copy of the full data-item, before giving the depositor access to the repository's copy of the data-item.

0031The initial applications contemplated for this repository are mainly archival: storing the complete contents of file systems, mirrored and available live on the network, with historical versions of files also available. The longer term applications center on the role of the repository company as a responsible party in a storage transaction marketplace. By implementing protocols that assure data integrity, persistence, privacy, accessibility and access control, and by using a scheme that avoids certain kinds of legal liability and copyright difficulties, the repository company is poised to help enable a storage transaction marketplace.

0000Initial Applications

0032In order to attract a significant volume of data from users with slow network connections, it is not only necessary to lower technical barriers, but also necessary to provide significant positive incentives. While these users can deposit much of their data quickly into the repository, they can only retrieve the actual data-items rather slowly—it isn't practical for them to use the repository in place of their local hard disk. There are, however, two practical services that can be provided which justify their depositing substantial amounts of data into the repository: file system mirroring and file system backup.

0033File system mirroring involves maintaining an up-to-date “mirror” copy of a user's file system within the repository. This mirror constitutes a remote network-based backup version of the local file system in a format which allows immediate network-based access to this data. To achieve this, client software is provided that runs on the user's computer and communicates with the repository data-server, automatically sending information to the repository about files that have changed. This program needs little or no configuration, and uses the client computer's processor and network resources only when they are not needed by other programs. It also performs other useful services, such as checking files for viruses. Once a copy of user data has been deposited in the repository, it is guaranteed to be safe from mishap or malicious mischief, and this data is available for use by its owner from anywhere on the network—available at all times and with high bandwidth. Some of the files mirrored in the repository could be deleted from the local file system, to save space. If a user has several PC's, all of their data that is scattered among their various machines becomes commonly available through the repository. Mirroring can also be applied to many non-PC devices (e.g., wireless personal digital assistants), further helping to consolidate user data. The owner of the mirrored data can also make their data accessible to network based applications and services: for example, portions of it can be served as Web pages, or copied directly to other network file systems. Third-party Application Service Providers (ASPs) can be given access by the users to portions of their data: for example, a system-maintenance ASP could check for software version incompatibilities in a user's data. Specific software ASP's could allow network-based versions of their software to operate on users' text and presentation documents.

0034Backup is performed on all repository data, including file system mirror data. The repository data server preserves historical copies of all repository data. These copies also reside in the repository but take up little space, since data-items in the repository are never actually replicated—only the metadata that associates names with data-items is actually copied. As files change, data-items which are no longer associated with any file (or backup copy of a file) may be erased from the repository, and their storage space reclaimed. For low-bandwidth users, there is little reason to ever remove any of their backup files from active storage in the repository—this data is always available. Users are able to retrieve past versions of file data. The repository data-server also periodically time-stamps file system “hash” information using digital timestamp techniques (see S. A. Haber and W. S. Stornetta, Jr., U.S. Pat. USRE034954, “Method for secure time-stamping of digital documents,” May 30, 1995), allowing the repository to provide incontestable legal evidence that a user had a particular file with particular contents in their file system on a given date.

0035For users with low-bandwidth and intermittent connectivity to the network, the repository business can provide many inducements to convince them to deposit their data in the repository, aiming to retain them as customers when their connectivity improves. In addition to lowering technical barriers, providing useful services, and guaranteeing data privacy, the business can also offer most or all services to these users for free. They are expected to soon turn into higher-bandwidth constant-connection users, who's continued patronage will provide revenue. Revenue can also be derived from ASPs providing data services to these users, particularly if the repository evolves from a data-mirror into a primary data-storage vehicle. An attractive feature of the repository in this context is that it provides safe and secure storage under the control of the end-user (unlike current network based applications such as Web-based email, which lock the user data into the ASPs database). The repository business can also expect to earn revenue from the traffic at the Web portal that users use to control their repository services and to subscribe to new services. Another potential revenue stream for both the business and the users would involve selling application usage information. Users would be paid who are willing to allow the client software to report such information. For example, information about cross-correlations between the presence of different application programs and data files in the same user's file system would be of great interest to software vendors, particularly if tied to a user name.

0000The Data Repository

0036The data repository is a distributed aggregate of data storage devices connected to the network, which together maintain a collection of data-items in a single logical address space, indexed by “datanames” (digital fingerprints) generated directly from the data-items themselves. Logically only one copy of each distinct data-item is kept in the repository, which allows for great economy in use of storage space. In practice, some redundancy is needed in order to assure data integrity, and to increase data availability and accessibility. Economical transmission of data-items which reside within the repository can be accomplished by sending the dataname in place of the data-item. This is illustrated in <figref idref="DRAWINGS">FIG. 1</figref>.

0037For each data-item <b>3</b> that a data-client <b>1</b> wishes to deposit into the repository, a cryptographic hash function (digital fingerprint) is calculated from the data-item—this is the repository dataname <b>3</b><i>a </i>for that data-item. Ideally, a cryptographic hash function is a fixed random mapping between arbitrarily long input bit-strings and a fixed-length output. With enough bits in the output value, such a hash is probabilistically “guaranteed” to provide a unique dataname for every distinct data-item that will ever be sent to the repository. In this discussion it will be assumed that the repository uses a well studied public-domain hash function called SHA-1, although other choices would do as well (see National Institute of Standards and Technology, NIST FIPS PUB 180-1, “Secure Hash Standard,”-U.S. Department of Commerce, April 1995.) This function produces a 20-byte value. It is at present computationally infeasible to find two distinct data files that have the same SHA-1 hash value—this prevents users from intentionally confusing the repository. If it ever becomes necessary to change the hash function used to index new data-items, old datanames can still be used to retrieve old data.

0038To deposit a data-item <b>3</b> into the repository, the dataname <b>3</b><i>a </i>is first used to check whether or not the repository already contains a copy of the data-item. The data-client <b>1</b> communicates with the repository data-server <b>2</b>, asking whether a given dataname <b>3</b><i>a </i>corresponds to an existing repository data-item. If not, the data-client sends the data <b>3</b>. The repository data-server <b>2</b> independently recomputes the dataname <b>3</b><i>a </i>by hashing the data-item received, in order to verify correct transmission, and to avoid any danger of associating the wrong dataname with a given repository data-item. Once a data-item is in the repository, it never needs to be sent again by anyone (unless it has been removed).

0000Named Objects

0039Although repository data-items are written directly, in the primary embodiment of this invention they can only be read indirectly, by referring to “named-objects” such as <b>10</b> and <b>12</b> in <figref idref="DRAWINGS">FIG. 2</figref>. This property is not shared by the scheme of Farber and Lachman mentioned in the background section. This restriction is imposed for several reasons. First of all, this provides a mechanism for associating a fixed name with changing data: reading the same named-object, different data-items are retrieved at different times. Secondly, this level of indirection is used to implement an access control mechanism for shared data: it is useful to control access to a named-object (e.g., file), rather than to a particular string of bits (i.e., data-item). By associating access-control information with named-objects, restrictions can be placed on which users are allowed to read particular named-objects in the repository. Finally, if the repository handles the creation and modification of the named-objects, then it can tell if a particular data-item is currently associated with any named-object: this makes it possible to identify unreferenced data-items and reuse their storage space.

0040For these reasons, the repository maintains a named-object database. After ensuring that a data-item <b>3</b> being transmitted resides in the repository, the client <b>1</b> communicates with the data-server <b>2</b> in order to associate the data-item <b>3</b> with a named-object <b>3</b><i>d </i>(<figref idref="DRAWINGS">FIG. 2</figref>). It is possible for the data-server <b>2</b> to require that the claim submit a “dataproof”, i.e., verify that the client actually has a copy of the data-item <b>3</b> being transmitted (and not just a dataname provided by some outside agency) before granting repository read access by associating the data-item <b>3</b> with the named-object <b>3</b><i>d</i>. A read client <b>5</b> (<figref idref="DRAWINGS">FIG. 3</figref>) associated with client <b>1</b> can use the access-authorization credential <b>3</b><i>b </i>that was generated in the deposit transaction to subsequently read data-item <b>3</b> indirectly by reference to named-object <b>3</b><i>d</i>, but no client can directly read data-item <b>3</b>. All clients which read using named objects (such as <b>3</b><i>d </i>and <b>10</b>) that are associated with the same dataname <b>3</b><i>a </i>actually share access to a single repository data-item <b>3</b>.

0041If the client <b>1</b> (<figref idref="DRAWINGS">FIG. 2</figref>) transmits the data-item <b>3</b> to the repository using the dataname <b>3</b><i>a </i>only, the data server <b>2</b> might, for example, randomly select a few data-bytes belonging to the data-item <b>3</b>, and request that the client <b>1</b> send these to it as a dataproof <b>3</b><i>c </i>before associating the named-object <b>3</b><i>d </i>with the data-item <b>3</b>, which will allow future read access. Alternatively, the data-server <b>2</b> might select a hash function, and ask the client <b>1</b> to send it the value of that function applied to the data-item <b>3</b> as the dataproof <b>3</b><i>c</i>. Such verification could be routinely performed, or might only be used in extraordinary circumstances, such as in connection with proprietary data-items for which the datanames have been unlawfully broadcast.

0042When verification of ownership is required, this could also be accomplished in an offline fashion—allowing the individual client to determine what it needs to prove for each data-item without directly communicating with the repository. With offline dataproofs, the dataproof <b>3</b><i>c </i>in <figref idref="DRAWINGS">FIG. 2</figref> could have been precomputed offline long before the “create-access-credential” request is sent—the client would have the dataproof <b>3</b><i>c </i>ready and waiting when it is needed and wouldn't even need to wait for it to be requested.

0043To prevent access to datanames which have been anonymously broadcast, an offline dataproof should depend on both the client and the data-item. One way to arrange this is to have a different “challenge-randomizer” value associated with each client—known to both the client and the repository. The challenge for a given data-item <b>3</b> could then be derived in a deterministic fashion using the challenge-randomizer and the data-item itself. A simple way to do this would be to hash together the challenge-randomizer and the dataname <b>3</b><i>a </i>and use the result as the seed for a random number generator which selects a set of data-item bytes to be returned; or alternatively just compute a hash on the data-item <b>3</b> that depends on the challenge-randomizer. The latter approach has the property that the entire data-item <b>3</b> is needed to compute the result of the challenge <b>3</b><i>c</i>, and so one party being asked to compute a challenge result on behalf of another would have to be given the challenge-randomizer value. Depending on how this value was selected, this might identify the party trying to gain access, or give away some valuable secret of theirs.

0000Transmitting Read Access

0044A client desiring access to a particular named-object <b>3</b><i>d </i>transmits its request to a client <b>5</b> (<figref idref="DRAWINGS">FIG. 3</figref>) that already has access, and the latter client passes along the request (along with the requester's access control information) to the repository data-server <b>2</b>. If the requester is to share an existing named-object <b>3</b><i>d </i>(so that if anyone changes which data-item or data-items are associated with it, the requester will see the change) then the requester is given access to the existing named-object <b>3</b><i>d</i>. This kind of “access” transaction is used, for example, to share files. If, instead, the requester is only being given access to the data-item <b>3</b> currently associated with the named-object <b>3</b><i>d </i>(and will not see any future changes in this named-object) then the data-server <b>2</b> will make a new named-object <b>10</b> for the requester, associated with the same data-item <b>3</b>. This kind of “copy” transaction is used, for example, to pass data “by value” to a network-based compute server. In either case, the data-item <b>3</b> itself is not copied—only control information associated with the named-object <b>3</b><i>d </i>is replicated in order to communicate data access.

0045Access could alternatively be transmitted in an offline fashion, by transmitting the named-object access-authorization credential <b>3</b><i>b </i>that users require to access the data item <b>3</b> themselves (perhaps augmented with other authorization credentials). By including a user-identifying token as a necessary part of the access-authorization credential <b>3</b><i>b</i>, the unauthorized broadcasting of access to proprietary data can be discouraged. Thus to cause the repository to make a copy of a named object, a client would need to provide its own authorization information for creating a named-object, along with the access-authorization credentials needed for reading the named-object.

0046Data-items could also be transmitted directly from one repository user to another using the repository as a kind of data-item compression aid. If the data-source wishes to send a data-item <b>3</b> which has been deposited in the repository and to which it has read access, then it only needs to send enough information to the data-recipient to allow it to deposit the data-item <b>3</b>. This consists of just the dataname <b>3</b><i>a</i>, along with whatever information <b>3</b><i>c </i>is needed to answer the verification challenge that the recipient must meet in order to deposit by dataname. This form of peer-to-peer copying can be discouraged or controlled by making the verification challenge involve the entire data-item (requiring the source to read the entire item before it can transmit access), and by making the information needed to answer the challenge reveal information about the recipient to the source.

0047Repository users can grant access to their data to whomever they please by giving them appropriate access authorization credentials and decryption keys. Third parties connected to the network can be granted the access needed to act on behalf of repository users, providing useful applications that manipulate repository data, and performing useful data management and data transformation functions. File systems, databases and other persistent object storage systems can be built by third parties, or by users themselves, on top of the repository named-object mechanism. For example, for maximum privacy client software can maintain its own file system directory data for files kept in the repository, using ordinary encrypted data-items to hold the directory information. The repository itself is simply a secure data store, which avoids unnecessary redundancy in the transmission and storage of data, provides access control, and promises to keep verifiable copies of old data and never lose data.

0000File system Mirroring

0048The structure of the repository makes it feasible for a computer user with a low-bandwidth connection to the network to maintain a copy of a local file system in remote storage. This copy appears on the network as a “mirror” file system, which reflects the current state of the user's local file system.

0049The principal benefits of file system mirroring are data security and data accessibility. Once data is deposited in the repository, it is protected from accidental or malicious loss, and past versions of files are made accessible, certified and time-stamped. Moreover, repository file systems can be accessed at high bandwidth, and from anywhere on the network. Mirrored file system data can, for example, be processed by high-performance network based compute-servers, served as Web pages, retrieved through a Web-browser interface, or “mounted” and used as if it were on a local disk.

0050The benefits of mirroring a local file system provide justification for low-bandwidth users to keep substantial amounts of data in remote storage. The structure of the repository makes this prospect feasible for such users, by avoiding the need to deposit data which is replicated on more than one local file system. If the complete file system is not mirrored, the repository structure also makes it easier to identify which files should be omitted from the mirror: only unique data-items need to be transmitted to the repository, and so only unique data-items need to be considered for omission.

0051In addition to providing many benefits, file system mirroring also presents a potential threat to privacy. Users may be reluctant to place a copy of their most private files outside of their physical control. Conversely, the repository maintainers may be reluctant to accept the legal liability of having access to valuable secret files, and even to evidence of criminal activity. These kinds of problems are avoided if it is demonstrably impossible for the repository maintainers to understand any of the mirror data that is sent to them. This can be arranged by using encryption techniques, as is discussed in detail in the next section. Since the mirroring client only needs to write data and never needs to read data, as an additional safeguard the mirroring client can be given only the encryption keys needed to write data, but not those needed to read data. This protects users from having everything that was ever on their computer's disk visible to an antagonist who captures their computer. In order for users to be confident that appropriate encryption is being used and that no private information is being reported, the source code of the mirroring client software can be openly published. Open publication of mirroring clients also makes it easier for third parties to write their own clients which make use of the repository in novel ways.

0052Considerations related to setting up mirroring are depicted in <figref idref="DRAWINGS">FIG. 4</figref>. In addition to dealing with privacy issues through encryption, the mirroring software is also confronted with smaller barriers that might cause users to abandon mirroring, or not try it in the first place. This is important, since the perceived benefits of mirroring may not be enormous for the typical user; after all, most personal computer users don't currently perform any sort of backup on their data. The first barrier to running the mirroring software <b>13</b> is downloading it. This process can be made very short: since the client is designed to talk to repository servers (such as <b>16</b>), only a minimal “bootstrap” program needs to be downloaded and installed initially, probably by clicking once on a Web page <b>14</b>. This bootstrap program can download the rest of the client software later on.

0053Complex program configuration would also discourage use. By default, the client software can be configured on installation to simply mirror everything. Once installed, the function of the client program <b>15</b> is to run continuously, checking whether files have changed since they were last mirrored, checking if new file data is already present in the repository, depositing data-items as needed, and maintaining repository directory information. By default, this should all be done in an invisible fashion. While the processor is being heavily used for other tasks, this program should stop running. If other programs are using the network, their outgoing data packets should get priority. Running the mirroring client program should not perceptibly slow down the computer's performance on other tasks.

0054The perceived benefit of running the mirroring client can also be increased if it has system-health-enhancing properties. It can, for example, check for viruses as it examines the local file system. The client's virus information can be kept up-to-date as it communicates with the repository.

0000Privacy Through Encryption

0055To avoid the need to transmit and store common data-items multiple times, all data-items are kept in a single shared data-pool in the repository, indexed by datanames, as discussed above. Without further elaboration, this arrangement has the drawback that sensitive private data is visible to the repository maintainers. To avoid this problem, files are ordinarily transmitted to the repository in encrypted form. For example, all mirrored file data is encrypted, as is indicated in <figref idref="DRAWINGS">FIG. 4</figref>. If the encryption was user-dependent, then each user's encrypted version of the same file would be different, and each user would have to transmit their distinct version of each file. In order to have all users with the same file produce the same encrypted data-item, all files are encrypted in a user-independent fashion: the encryption key for each file is derived from the file data alone. This is depicted in <figref idref="DRAWINGS">FIG. 5</figref>.

0056The procedure for file system mirroring is otherwise the same as discussed above. Each file <b>17</b> is compressed and encrypted before computing its dataname <b>19</b>, which is used to determine whether or not the encrypted data-item <b>22</b> needs to be sent to the repository. The client software encrypts files using a datakey <b>18</b> that is derived by hashing the compressed file data. To maintain privacy, care is taken that the data repository never sees this datakey “in the clear.” For compatibility with media such as audio and video data which are often used in a sequential or streaming fashion, both the compression and the encryption can be performed in a fashion which allows the data-item <b>22</b>, when being read, to begin to be decrypted and decompressed before the entire data-item has been read.

0057When a client wishes to retrieve and decrypt a repository data-item, the datakey that was used to encrypt it is needed. For this reason, it is natural to include an encrypted copy of the datakey <b>20</b> as part of the named-object in the repository that is associated with this data-item. The encrypted datakey <b>20</b> belongs with the named-object rather than with the data-item because the encryption of the datakey will not be the same for all users—the key <b>21</b> used for this will vary from user to user. By making sure that a mirroring client doesn't have (or quickly loses) the ability to decrypt datakeys that it writes, write-only mirroring clients are enabled. This can be accomplished, for example, using public/private key pairs, with the mirroring client only holding the public keys.

0058Groups of users who wish to share a set of named-objects (for example, a file system) will also share an “aggregate-key” that is used to encrypt all the datakeys in that set of objects. Care is taken that the data repository never sees aggregate-keys in the clear. When access is transmitted by copying a named-object (rather than by sharing it), the transmitting user gives the unencrypted datakey directly to the access recipient.

0059Every repository client needs to provide an access-authorization credential in order to read a data-item associated with a named-object. This credential includes a repository-name or “handle” which uniquely identifies the named-object for that client. For the mirroring client, this handle can be derived by hashing the file system path-name on the client's local file system. In this case, it is sufficient for the client to remember all pathnames in it's directory tree in order to be able to reproduce the handles of all of its files. Thus, for example, part of the mirroring process might involve writing data-items which are directory listings for each subdirectory that has changed. Privacy is enhanced if handles are difficult to guess: this can be accomplished by having each mirroring client remember its own randomly chosen “name-randomizer” value which it uses as part of the hashing process that derives handles from file system pathnames. The hashing process might be, for example: start with the name-randomizer and the first component of the pathname, and hash these together; take the result of this hash and hash it with the next component of the pathname, and so on. This kind of hierarchical construction has the advantage that given the handle for some directory along with pathnames starting at that directory, all of the handles for that directory can be constructed. This may make it more convenient to transmit handle information from one client program to another.

0060While user-independent encryption provides privacy for data-items that are used by only one user, any shared data-item has a vulnerability: given access to the unencrypted file data for any client which shares the data-item, it is easy to discover which file contains the unencrypted data-item. The concern here is not that it will become possible to decrypt the data-item; the unencrypted version was assumed to be available. The conflict with privacy is that it becomes possible for the repository maintainers to identify shared programs and data that a user has in their file system. For example, the repository maintainers could compute the dataname of a particular version of the executable of Microsoft Word, and monitor all transactions to construct a list of all users who have deposited a copy of this program.

0000Virtual Private Storage Systems

0061In the scheme described thus far, the datakey used to encrypt the data-items is derived identically by all users from the unencrypted data-item alone. An alternative to this is to have an additional piece of information used to determine the data-item encryption key, which might be called a family key. All users with the same family key use the same method to derive the data-item encryption key from the data; users with different family keys use different methods. For example, a user might use the family key to modify the datakey described above before using it to encrypt the data, as in <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0062"> data-item encryption-key=E(family-key, datakey) <br /> where E is itself an encryption operation. This has the advantage that it makes a family of data-items more private. For example, this would prevent the repository maintainers from monitoring whether users in this family have deposited specific known pieces of data, since without the family key the repository maintainers will be unable to generate the same data-items and datanames to compare against. This has the disadvantage, of course, that instances of data-items which would have been identical are now made different, and hence the storage and transmission of these data-items becomes less efficient. <br /> Privacy Through Anonymity </li></ul></li></ul>

0063If family keys are not used, or if family keys become known, it becomes possible for the repository maintainers to identify shared programs and data that a user has in their file system, which conflicts with user privacy.

0064This conflict can be avoided if all transactions with the repository are anonymous, so that it is impossible to tell who has access to a particular data-item. Of course, for users to be truly anonymous, all data communications would have to be forwarded through a third party “anonymizer” so that identifying information doesn't appear in the network data packets received by the repository. Anonymous transactions that the repository wishes to charge money for can be handled using electronic cash techniques (see D. Chaum, A. Fiat, and M. Naor, “Untraceable Electronic Cash,” Advances in Cryptology CRYPTO '88, Springer-Verlag, pp. 319-327). Alternatively, funds can simply be transferred between non-anonymous and anonymous repository accounts using blind signatures.

0065Anonymity can, however, be a liability. This is the case in connection with named-objects that are shared by many users. These objects can be shared either by separately granting access to each sharer, or by a number of users all sharing the same access information (or even the same identity). In either case, the prospect of users using the repository to illegally share proprietary data (music, videos, programs, etc.) causes a potential problem for the repository maintainers. A completely anonymous repository is much more attractive for these kinds of activities than a more conventional data repository. It may be advisable, for this reason, to limit anonymity in some manner.

0000Limiting Anonymity

0066One approach is to eliminate anonymity altogether. Users simply trust the repository to not accumulate or reveal information about the non-unique data that they have in their file systems. In this case, the less information the repository accumulates, the less it can be coerced into revealing. If the repository avoids storing enough information to link users and data-items, then users have a kind of effective anonymity. Extra information provided only at the moment of access can allow users and data to be linked. At that moment, ownership data associated with a named-object can be generated using a cryptographic hash function in a manner that prevents ownership from being discovered, but allows ownership to be proven.

0067This is illustrated in <figref idref="DRAWINGS">FIG. 6</figref>, which contains some details omitted from <figref idref="DRAWINGS">FIG. 3</figref>. In this example, we're assuming that the access-authorization credential <b>3</b><i>b </i>for a named-object includes a user-identifying token called a “namespace-ID” <b>3</b><i>e</i>. A namespace is simply a group of related credentials belonging to a single user. The access-authorization credential <b>3</b><i>b </i>also includes a repository handle <b>3</b><i>f</i>, which is unguessable by construction. Read access to a named-object may be transmitted from one user to another without the intervention of the repository (i.e., in an offline manner) by transmitting the access-authorization credential <b>3</b><i>b</i>. Control over who has the authority to create or use credentials for a given namespace can be handled separately, or can be encoded in additional credentials.

0068Regardless of the precise composition of the access-authorization credential, anonymous ownership data can be generated from it by hashing the namespace-ID <b>3</b><i>e </i>and the handle <b>3</b><i>f </i>together using a cryptographic hash function <b>30</b>. The resulting access identifier <b>3</b><i>d </i>is used to identify a named object in the named object database <b>6</b>. We equate this identifier with the named object itself (cf. <figref idref="DRAWINGS">FIG. 3</figref>). The existence of a named object in the database <b>6</b> corresponding to the access identifier <b>3</b><i>d </i>proves ownership: this database entry was generated when the data-item <b>3</b> was associated with the named object <b>3</b><i>d </i>(<figref idref="DRAWINGS">FIG. 2</figref>). Because of the one-way nature of the cryptographic hash, and because the unguessable handles are never stored in the repository, it is impossible to invert the hash <b>30</b> and determine the namespace-ID <b>3</b><i>e </i>from the repository's stored access identifier <b>3</b><i>d</i>. Since the repository uses the access identifier <b>3</b><i>d </i>to determine the data-item <b>3</b> that is associated with the named-object, the impossibility of inverting the hash also hides the connection between data-item <b>3</b> and the access-owners (i.e., the users or client programs which have established access-authorization credentials) who are able to read it.

0000Partial Anonymity

0069Another approach is to treat shared named-objects differently than unshared ones. If these two categories can in fact be distinguished, then unshared objects can be made completely anonymous, while shared objects have no anonymity: all transactions involving shared named-objects require user identity verification. This leaves the repository in the same position as more conventional repositories with respect to intellectual property issues associated with shared files, and in a better position with respect to the privacy of unshared files.

0070This approach assumes that it is possible to distinguish between shared named-objects and unshared ones. This will in fact be possible if the sharing of access-information can be prevented, so that all sharing is done through explicit “share” requests to the data-server. In particular, in this approach we wouldn't provide an offline method of transmitting access-information without sharing a user-identity. Sharing access-information can be discouraged by holding those who share such information responsible for whatever use is subsequently made of the shared named-object. It can also be arranged for the sharing of access-information to reveal the true identity of the access owner to all sharers (but not to the repository). To permit access sharers to know who the access owner is—without this information being visible to the repository—access owners can be compelled to store their certified identity information in the repository in an encrypted form which only they and the sharers can read. They can be required to prove that they've done this using a zero-knowledge protocol (for a discussion of zero-knowledge protocols, see U. Feige, A. Fiat and A. Shamir, “Zero-knowledge proofs of identity,” Journal of Cryptography, 1: 66-94, 1988). If user authentication requires knowledge of the key used to encrypt the identity information, then all users sharing access information will have it.

0071By limiting anonymity in other ways, it may be possible to put the repository in a still better position. For example, those who are sharing a set of named-objects could be given access to information about who last modified each object, with this information kept invisible to the repository. The identifying information provided could, for example, be a repository email address, with associated personal information revealed by the repository only under a court order. This organization would allow users to confront each other privately concerning controversial sharing of data before trying to compel the repository to intervene.

0000Poorly Verified Users

0072Finally, it should be noted that it may be desirable to support some users who are effectively anonymous not because the repository forgets information about them, but because the repository cannot confirm their identities. For example, it may be desirable not to require users trying out the mirroring client to provide any sort of verification of their identities. In this case, it would still be necessary to prevent such users from using their unverified repository accounts to broadcast proprietary data. This can be accomplished by not allowing repository-mediated sharing of data-items that come from unverified accounts, and by not allowing offline transmission of read access to data-items in such accounts. The total aggregate bandwidth available using the data-access privileges of such an account could also be limited, so that sharing of access information doesn't enable more than a small number of users to simultaneously read data from this account at a useful rate.

0000Composite Objects

0073There are several reasons to construct named-objects which are composed out of more than one data-item. For example, a mirroring client running over a telephone modem may take hours to deposit a single very large file which is not already in the repository. If this file is broken up into many smaller pieces, then if the telephone connection to the local ISP is lost before completion of the full transfer, all of the pieces which were successfully transferred will not need to be transferred again. If the connection is regained and the transfer attempt is repeated, the normal repository query protocol will discover which pieces have already been deposited, and they will not need to be sent again.

0074Similarly, some structured items can be sent more efficiently if they are broken up appropriately. For example, email messages with multiple attachments can be transmitted (and stored) more efficiently if they are split up into several pieces, with the divisions occurring at appropriate attachment boundaries. In general, files with a limited amount of user-specific information can segregate this user-specific information into designated segments, allowing the file to be broken up in such a manner that most segments are common between multiple users. For example, a user-name could be assigned to a variable at the beginning of a file, and the name would not need to appear explicitly again.

0075Finally, for general use of the repository as a network-attached file system, the division of files into smaller blocks is useful.

0076To support composite structure, it would be expensive in terms of resource usage for the repository to associate with each client a separate copy of the structure information for every file deposited. For a long video file, for example, the repository might store hundreds of thousands of individual data-items corresponding to individual frames of the video, with a corresponding list of datanames repeated for each client which deposits this object. For this reason, it is logical for lists of datanames which describe larger objects (with perhaps other information included) to themselves be deposited as data-items in the repository. These index-items can then be shared, just as any other data-items.

0077The steps involved in depositing a composite object using an index-item are illustrated in <figref idref="DRAWINGS">FIG. 7</figref>. First the individual data-items <b>40</b> are deposited into the repository as described earlier, sending data to the repository data-server <b>47</b> only when the data-item is not already present. Then the ordered list of corresponding datanames <b>42</b> is deposited as a data-item <b>41</b>, called an index-item. Assuming the data-items <b>40</b> are encrypted, a list of unencrypted datakeys <b>46</b> (in the same order as the datanames <b>42</b>) is deposited as a data-item <b>45</b>, called a key-item. Finally, the dataname <b>41</b><i>a </i>of the index-item <b>41</b> and the dataname <b>45</b><i>a </i>of the key-item <b>45</b> are associated with a named object <b>49</b> in the repository. This involves sending an access authorization credential <b>43</b> and (assuming verification is required) a list of dataproofs <b>44</b>, one for each of the data-items <b>40</b>. Alternatively, it may be more efficient for the server <b>47</b> to return a token at deposit time confirming each deposit of the data-items <b>40</b>, and use these tokens for ownership verification instead of the list of dataproofs <b>44</b>: this reduces the amount of work that the server <b>47</b> has to do at the moment when the named-object is created. Both the index-item <b>41</b> and the key-item <b>45</b> are encrypted in a user-independent manner, just as any other data-items. The datakey for the key-item <b>45</b> becomes the datakey for the entire composite data-item, and is encrypted privately before being stored in the repository, as discussed earlier. The repository is given access to the datakey for the index-item <b>41</b> only transiently, when it needs to look at the index-item.

0078The process of reading part of a composite object is illustrated in <figref idref="DRAWINGS">FIG. 8</figref>. In addition to the read-access authorization credential <b>43</b> for the named-object <b>49</b>, a block number <b>50</b> is also supplied. This indicates which dataname (e.g., <b>42</b><i>b</i>) in the index-item <b>41</b> should be referenced. The corresponding data-item <b>40</b><i>b </i>is returned to the user. Note that this scheme preserves the atomic-nature of named-object writes: the current data-item that a named-object accesses is changed in a single operation.

0000Historical Versions of Objects

0079For mirroring of personal computer file systems over low-bandwidth and intermittent network connections, there is little need to ever erase any data-items from the repository. For repository users with faster connections, however, it would be unreasonable to try to keep every version of every file. As an extreme example, if a file is rewritten every time a byte is added, by the time the file reaches a Megabyte a total of about half a Terabyte of data will have been written. Keeping all versions of such a file should be avoided, if possible.

0080In a repository which keeps historical versions of named objects, a choice must be made of which data to keep. This issue can be addressed by using repository snapshots and named-object reference counting. A “snapshot” of a file system which has been implemented within the repository is a complete “backup” copy of all directory data and file data at a particular moment in time. Snapshots are relatively inexpensive to make, since no data-items are ever duplicated in the repository. To copy a set of named-objects, only pointer and property information actually needs to be copied. By periodically taking “snapshots” of all named-objects in the repository, the ability is preserved to retrieve previous versions of the state of all objects at particular times, but not at all times. Data-items which aren't associated with any named-object are not needed in any of these snapshot versions of the files kept in the repository. This is illustrated in <figref idref="DRAWINGS">FIG. 9</figref>. When write client <b>56</b> associates a new data-item <b>62</b> with named object <b>58</b>, the reference count of the previous data-item <b>60</b> associated with named object <b>58</b> may go to zero. This means that data-item <b>60</b> is unreferenced, and it may be deleted and its storage reclaimed. If data-item <b>60</b> was part of any file system snapshot, its reference count would not have gone to zero, and so it would be preserved. Thus keeping count of all references by named-objects to data-items allows an unreferenced data-item such as <b>60</b> to be erased without any danger of losing the ability to retrieve snapshotted earlier versions of all files.

0081Since data-items which are common to more than one snapshot are only stored once, this backup scheme can be classified as “incremental.” Doubling the interval between snapshots only makes it possible to reclaim space associated with files that changed during each of two consecutive original intervals. Beyond some correlation time, it is expected that the set of files that change during each interval will be substantially different for each interval, and so little is saved by further increasing the interval. For this reason, shorter-interval snapshots are kept for a finite period, and longest-interval snapshots forever. When the named-objects associated with a short-interval snapshot are erased, storage space occupied by data-items that become unreferenced can be reclaimed.

0082File system snapshots can be implemented by declaring a moment of time to be the snapshot, and all writes after that moment don't overwrite previous versions of the same file—the incremental backup is accumulated incrementally. Each snapshot declares that all named objects that make up the file system start a new version the next time they are written, and the old version is preserved.

0083As long as the capacity of storage devices continues to grow exponentially, there is (for most users) little need to ever move any old data out of the repository, onto archival media. For example, if the longest interval snapshots are taken every month, and half of the monthly change in a typical user's unique data is the addition of new files, and their unique-data disk usage grows at the same rate as the hardware capacity of disks, then keeping all monthly snapshots in the repository forever only increases the total disk usage by about a factor of two. If unique user data doesn't grow exponentially, then total disk usage also grows more slowly than hardware capacity, although old data becomes a more significant portion of total usage.

0084A limiting case of the snapshot method is to set the time interval between snapshots to zero. This means that every time a named object is rewritten, a new version is created. Every version of every object is kept. If this results in too many versions of some named objects, then a decision is made to declare some of these versions as being unnecessary, and to delete them. Rather than simply prune versions as they are written based on a global time threshold (the snapshot method), versions may be pruned based on many criteria. Decisions on which versions to delete might depend on separate policy information associated with each object, the relative time intervals between different versions of the same object, and even on global time thresholds.

0085The data-pruning mechanisms discussed imply a distinction between short-term memory and long-term memory in the repository. This distinction reflects the fact that objects that have changed recently are the ones most likely to change again. Thus in the short-term, data-items are kept in a form that it is convenient (or at least possible) to erase. In the long-term, it may be inconvenient (or even impossible) to forget any data-items.

0000Forgetting the Meaning

0086The repository is designed to be able to remember historical versions of file data forever. This can be accomplished using standard techniques such as redundancy and archival media. Files which have been removed from the current version of a repository file system can be restored by copying them from an earlier version. Historical versions of files which have changed remain available. Hash information about each file system is digitally timestamped, to allow the repository to provide legal evidence of the existence and contents of files at specific times in the past (see Timestamping discussion below).

0087The indelible character of the repository means that it may be difficult or impossible to destroy all traces of old data even if someone badly wants to. The general use of encryption makes it possible, however, to render selected old data meaningless. The basic idea is that the most essential encryption keys are never stored in the data repository, and so the user is free to forget these keys, making all associated data unintelligible. If data that is to be retained is copied before “forgetting” the rest in this manner, then information can be selectively erased: only a now-meaningless encrypted copy of the forgotten data remains in the repository.

0088If keys have been shared (more than one person knows them), then past data can be forgotten in this manner only if everyone who knows these keys cooperates. One can always, however, stop sharing future versions of files by simply copying them to a new client file system and no longer using the old client file system. This is really all that can be accomplished with certainty, since once data has been shared one is never certain that someone hasn't secretly made a copy of the data.

0000Other Access-Authorization Credentials

0089An access-authorization credential is a credential that may be presented by a client program to a repository server in order to prove that it has authorization to read a data-item. In the embodiment described above, an example of such a credential has been provided (<figref idref="DRAWINGS">FIG. 6</figref>): <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0090"> access-authorization-credential <b>3</b><i>b</i>=(namespace-ID <b>3</b><i>e</i>, handle <b>3</b><i>f</i>) <br /> where the namespace-ID <b>3</b><i>e </i>identifies the access-owner, and the handle <b>3</b><i>f </i>identifies a named-object <b>3</b><i>d </i>belonging to that namespace. A client program attempting to use this credential <b>3</b><i>b </i>must demonstrate that it is one of the authorized users of the namespace-ID <b>3</b><i>e</i>. The existence of a named object <b>3</b><i>d </i>in the repository corresponding to the credential <b>3</b><i>b </i>records the right of an authorized client to access the corresponding data-item <b>3</b>. </li></ul></li></ul>

0091This example illustrates the general character of an access-authorization credential: it constitutes proof that access has been authorized, and it includes information identifying the access credential's owner. The latter property is really only needed in a credential which can be used by third parties—this property then helps prevent anonymous broadcast of access capability. For credentials usable by third parties, control is maintained over who is permitted to create or use credentials for a given namespace-ID.

0092There may be advantages in having access-authorization credentials which allow direct access to a data-item, without reference to a named object in the repository. This is particularly appealing in connection with objects which have stopped changing. For such static objects, information about the association of data-items with names can be conveniently stored in ordinary data-items, thus reducing the size of specialized named-object databases. The metadata for these named objects would be managed by clients, and would not be directly visible to the repository.

0093An example of a direct-access credential might simply be the information needed to create an access-authorization credential for a named-object in the repository. In the above example, this would be (see <figref idref="DRAWINGS">FIGS. 2 and 6</figref>), <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0094"> direct-access-credential=(namespace-ID <b>3</b><i>e</i>, dataname <b>3</b><i>a</i>, dataproof <b>3</b><i>c</i>) <br /> To use this direct-access credential, one could simply create a named-object in the repository at the moment when read access is required (including submission of the dataproof, as shown in <figref idref="DRAWINGS">FIG. 2</figref> and earlier discussed), then read using the associated credential, and then delete the repository named-object. </li></ul>

0095For this mechanism to work, one would need to have a way to ensure that the data-item <b>3</b> is not deleted from the repository. In the discussion of historical versions of objects, we assumed that data-items which are not referenced by any repository named-object can be deleted, and their storage space reused. This deletion mechanism can be easily modified to accommodate direct access credentials. For example, when client <b>1</b> deposits data-item <b>3</b> (<figref idref="DRAWINGS">FIG. 2</figref>), it could specify a minimum expiration period. If data-item <b>3</b> becomes unreferenced by repository named objects, it would not be deleted from the repository until after the latest expiration date specified in any deposit.

0096Rather than require the repository to create and delete a temporary named object, one could simply allow a direct-access credential to be used directly for reading a data-item. As part of the data-item deposit process, the repository could supply some authentication code or signature to augment the direct access credential, allowing it to be used without requiring the dataproof to always be checked. Retaining the dataproof as part of the direct access credential makes it possible to verify credentials if repository signing keys have been compromised, canceled or are otherwise unavailable.

0097It may be desirable to allow the repository to delete a data-item as soon as all access authorization credentials which reference it have been declared deleted. To allow this, one could associate a reference counting scheme with the direct access credential. This could be done, for example, by associating a per-depositor record with each data-item whenever a direct access credential is created. When the credential is later declared deleted, the corresponding per-depositor record would be deleted. Since large reference counts are unlikely to ever go to zero, it may be that once the number of depositor records passes some threshold, the data-item can simply be marked as permanent. This would bound the number of per-depositor records associated with each data-item.

0098Note that even if the challenge set by the repository server as part of the deposit process is nondeterministic, it can still be the case that a dataproof or other deposit-proof information returned by the server in response to the deposit is perfectly deterministic and suitable for use in a direct-access credential.

0099Finally, note that the direct access credential could be the primary access authorization credential—it is not dependent on the existence of a repository based object credential.

0000Timestamping

0100<figref idref="DRAWINGS">FIG. 10</figref> illustrates one possible scheme for timestamping repository named-object data. This scheme has the useful feature that all historical data is automatically timestamped: the repository can prove the ownership and contents of any version of a named object that has not been deleted. Users are not required to save any extra information in order to support this service. Short-lived versions of named objects are not timestamped.

0101Each named object is assumed to exist in multiple historical versions. In this case, the access authorization credential for a named object includes not only the namespace-ID <b>72</b><i>i </i>and handle <b>73</b><i>i</i>, but also a version number <b>74</b><i>i</i>, which we'll assume is chosen randomly. As usual, the hash of the access authorization credential is the access identifier <b>71</b><i>i </i>used to index the named object database <b>75</b>.

0102In this example scheme, the repository timestamps all named-objects which pass a certain transience threshold, allowing proofs to be constructed for any timestamped object of when the named-object existed, what data-item it was associated with at that time, and who had access to it. This scheme also makes it possible to automatically lose the ability to construct proofs for objects which have been deleted from the named-object database <b>75</b>.

0103In this illustrative scheme, we assume that the set of all named objects is divided up among a set of repository servers, each of which has authoritative information about a subset of the named objects (this division can conveniently be based on the access identifier). We will describe the timestamping procedure for a single repository server <b>70</b>—the procedure for multiple servers is simply to timestamp each server separately. When a proof is needed, the server responsible for the required portion of the named-object space is identified, and it's timestamp information is used.

0104The access identifier <b>71</b> indexes the named object version information stored in a named-object database <b>75</b>, which includes the dataname <b>76</b>. We select a subset of the server <b>70</b>'s named object database <b>75</b> to be timestamped: for example, all versions which were created more than one week earlier, but less than two. This selects a subset which is not so recent that many of the versions will be deleted as being unneeded. If, in this example, we only perform timestamps once per week, then it makes sense to only timestamp one week's worth of versions at a time. By timestamping a selected subset of versions at once, it becomes possible to organize the timestamp information in a convenient form.

0105The actual timestamp record <b>78</b> consists of a list of cryptographic hashes <b>80</b>, one per version selected for timestamping. Each hash includes an access identifier <b>71</b><i>i </i>for a version of an object as well as a dataname <b>76</b><i>i </i>associated with the version. This entire list is saved in the repository as a composite data-item <b>78</b>, to be used in the future in constructing named-object existence proofs. The corresponding dataname <b>78</b><i>a </i>is published publicly, or sent to a digital timestamping service.

0106Assume for simplicity that the timestamp list <b>80</b> is sorted by hash value. If a proof of existence is ever required for a particular version of an object which is still in the repository, its timestamp hash can easily be located within the timestamp data-item <b>78</b> for the relevant repository server <b>70</b>. The data-block containing the relevant hash, along with the index-block for the entire data-item <b>78</b> and the published dataname <b>78</b><i>a </i>for the index block, provide all the information needed to prove the time of the relevant hash. (More levels of hierarchical hashing could be used to reduce the size of an existence proof.) The timestamp hash for the particular version of a named object in turn allows proof of the ownership and dataname of the version. The dataname then allows data contents to be proven.

0107If a user deletes an object record such as the one indexed by <b>71</b><i>i </i>from the repository metadata, the corresponding timestamp hash <b>80</b><i>i </i>can no longer be used to prove anything. This is because of the inclusion of the random version number <b>74</b><i>i </i>in constructing the hash, assuming that all record of this number is erased along with the object record <b>71</b><i>i</i>. This is an important privacy feature, since timestamps could potentially be used by an adversary to prove that a particular user had access to a particular data-item, if the dataname <b>76</b><i>i </i>and handle <b>73</b><i>i </i>and version number <b>74</b><i>i </i>could all be reconstructed.

0108Note that if a direct access-authorization credential is supported, separate provisions would have to be made to have its hash included in the timestamping process. For the reasons discussed above, it would be important to include an unguessable component in this hash. It would be the client's responsibility to maintain a copy of any direct access credential that it may want to later prove.

0000Deposit Receipts

0109Deposit receipts play a similar role to time-stamps. Users can ask for and receive immediate proof that a deposit was successful, and that a certain level of persistence has been guaranteed. The repository will not make this guarantee until it has taken steps to actually safeguard the data. The actual receipt could simply be a digitally signed set of access-authorization credentials.

0000A Uniqueness Oracle

0110In addition to avoiding unnecessary data transmission, there are other uses which can be made of the repository's status as an oracle which can determine whether or not a data-item is unique. A prosaic example would be to use the repository as a “spam” filter. If users are encouraged to keep their email messages in the repository, with the header information separate from the body of the message, then the repository allows users to detect whether or not an email message that they receive contains unique data. Users might reject non-unique messages as junk mail.

0111The repository can give information not only on the absolute uniqueness of a data-item, but also on it's relative uniqueness. This ability is based upon the reference counts that are maintained by the repository in order to allow the reclamation of space occupied by unreferenced data-items. These reference counts allow the construction, for example, of better spam filters which don't reject relatively uncommon messages. They also allow the repository to, for example, help find viruses by detecting unexpected levels of uniqueness. If a virus always affects an application in the same manner, then the resulting data-item can be tagged in the repository as virus-infected, and immediately identified when seen. If, on the other hand, a virus has a variable effect, then each virus-infected executable file will tend to be significantly less common than other files associated with the same application.

0112The ability of the repository to tag a shared data-item with information also opens up other possibilities. For example, the first depositor of a data-item might be presumed to hold the copyright (until otherwise demonstrated), and could tag the item with information about who to pay if others want to use this item. Software vendors could tag data-items corresponding to old versions of their software with information about newer versions. All sorts of reviews and annotations could be attached to data-items, both encrypted and unencrypted. Such services could also be operated by third-parties using databases indexed by datanames. Annotations could be hidden from the repository by encrypting them using the datakey from the data-item being tagged.

0113Online-information vendors (software, music, books, etc.) may be interested directly in the reference counts corresponding to their (and competitor's) data. These counts could, for example, be normalized by the reference counts of all versions of a particular operating system in order to give market penetration statistics for a software application. The time development of the reference counts gives information about rate of sales.

0000A Layered Business Structure

0114The repository has a layered structure which lends itself to being implemented as several separate businesses. First there is the physical storage layer, which keeps data in safe and rapidly accessible high-volume storage. Next there is the data-server layer, which manages data-item storage and access using datanames and named-objects, and is responsible for historical versioning and time-stamping. On top of the data-server are built file system and data-services layers, which will in turn have additional application services layers built on top of them. Each of these distinct layers can be implemented as separate businesses, with competition possible at each level.

0115The primary business that is the subject of this invention is the data-server layer. This business provides an interface which allows clients to share storage efficiently, and to avoid redundancy in data transmission. The data-server business can make use of existing network storage companies for physical storage during its startup phase, and such companies provide extra storage capacity that can be rapidly deployed in case of unanticipated demand. The data-server business could also make use of other companies and entities for physical storage in the long run—it is an independent business.

0116Separating the companies that build file systems and advanced data-services from the data-server business has significant advantages. First of all there is a separation of liability issues, since data-services companies may be given unencrypted access to data that they are expected to protect and hold proprietary or confidential. If a data-services company wishes to challenge what is allowed under copyright laws, for example, the data-server business is not responsible for this client's decisions about to whom it gives access to data. Furthermore, separating advanced data-services from the data-server business makes it possible for competing companies to all make use of the same repository. This both lowers the barriers to competition, and makes it more likely that the repository will be associated with successful data-services companies.

0117The file system mirroring service, which is designed to help promote the data-server business among low-bandwidth users, doesn't require any separate network fileservers: this service can be handled directly as part of the data-server business. The mirrored file systems can be maintained directly by the mirroring-client software using client-maintained directory structures that are stored in the repository along with the data. This arrangement provides maximum privacy for user data, since if the directory information is encrypted, not even the structure of the file hierarchy is visible to the repository. The data can be accessed over the network as if it were a local file system by using a device driver which communicates directly with the data-server.

0118In the long-run, a repository data-server business is expected to make money by charging to mediate transactions between data-storers, data-services providers, and (perhaps) data-storage providers. Charges would reflect resource usage. In the near-term, the mirroring client provides valuable services which can be directly charged for. It would also be possible to charge only for very specific value-added services, such as disaster recovery assistance using mirrored data.

0000Other Features

0119Some individuals and organizations may be unwilling to let any of their private data be stored outside of their direct control. Such entities can still make use of the repository to maintain a mirror and backup of their public data, while they manage their private data themselves. The determination of which data is private and which public can be made using the repository query mechanism: a data-item which is already present in the repository can be deemed public. Such an entity will never transmit more than the verification challenge for a data-item to the repository. If such an entity runs its own isolated version of the repository data-server to manage its private data, then it obtains the benefits of communication and storage reduction, while retaining the repository's privacy advantages relative to the data-server maintainers.

0120Since datanames are obtained using a cryptographic hash, they provide a natural source of pseudo-randomness to help divide the data-service work evenly among data-servers. For example, if a local data-server doesn't recognize a dataname, it can use a portion of the dataname to help it decide which other data-servers are responsible for having the definitive answer as to whether the repository holds the corresponding data-item. Similarly, access identifiers are pseudo-random, and this can be used to help split up repository named-object information evenly among data-servers.

0121A rapidly growing trend today is the use of computers and digital media to replace other kinds of media. For example, at current disk prices, a high-quality digital scan of a typical book (compressed) takes about $1 worth of disk space. A music CD takes a similar amount of disk space. An interesting business opportunity built on top of the data repository is to perform these media conversions for people, putting the result directly into the repository. Such a service is already provided by Mp3.com for music CD's, using a specialized CD repository. In the case of the envisioned business, when multiple users perform the same conversion, the repeaters are instantly given access to the data-item. This not only greatly speeds up the conversion for them, but it also avoids filling the repository with many slightly different versions of the same information. The major issue that needs to be resolved in this context is how to avoid infringing upon intellectual property rights. It has not yet been decided in court, for example, whether it is enough that the user demonstrate that they possess a copy of the item and represent that they own it, in order to give them access to a copy. It seems likely that it would be sufficient for a user to mail the physical item to the conversion business, which would destroy the original and give them digital access to an electronic version.

0122Although the file system mirroring discussion only considered copying file system data from a client with a slow connection to the repository, it might be useful to such users to also provide the capability of mirroring in the opposite direction. This would be particularly useful if users with slow connections are also permitted to control the transfer of data between network file systems at high bandwidth, including such services as downloading files, applying compute servers to their network data, and even using an instant media conversion service such as the one outlined above. Results of such operations could be deposited at high-bandwidth in a user's network file system within the repository, which is mirrored within the user's local file system. The downloaded files, computation results, etc., would all eventually appear on the user's local disk automatically, being transferred as a background task by the file system mirroring software. User-initiated background copying of data between local and remote file systems would also be supported.

0123A coalescing repository such as the one described herein is very well suited to capturing broadcast digital data. For example, if a digital video program (digital cable TV, HDTV, satellite, etc.) is broadcast to a large number of repository users, each user only needs to deposit a small fraction of the data (perhaps just one frame each) in order to transmit the entire program to the repository. For example, if users deposit one frame at a time, starting at about the same time, and with some randomization in the order in which they deposit frames, then the task of depositing the program is automatically partitioned between the users by the repository's query-before-transmit protocol. By greatly spreading out the time period over which a broadcast object is deposited, the degree of synchronicity needed between depositors in order to share the deposit burden is greatly reduced. (Some randomization in the order that each client chooses to deposit frames may also help divide up this task). Ideally the broadcast coalesces back into a single compound data-object in the repository. Because of single-frame errors this won't actually be the case, but most of the frames will coalesce. This kind of broadcast deposit is particularly attractive in conjunction with disk-based program time-shifting hardware, which records broadcasts for later viewing. If all programs recorded are subsequently deposited in the repository, then they remain accessible even after the copy on the recorder's disk has been erased to make room for new recordings. Essentially all programs ever recorded could remain accessible to the user.

0124Similarly, the Web can be viewed as a digital broadcast medium. Users could permanently cache all Web pages they have viewed in the repository. This could be done, for example, by configuring the user's Web Browser to request that Web pages pass through a repository proxy server before being passed on to the user. Instead of temporarily caching Web data, as a normal proxy server would, the repository proxy server would deposit a copy of the Web page into the repository. By using a proxy server, rather than having the user deposit the pages directly, we avoid having a new Web page travel both to and from the user. All pages ever viewed would remain available and searchable by the user. This would result in the repository accumulating a copy of all Web pages viewed by its users, which would be useful in constructing Web search engines. Users would have an incentive to use the repository proxy server, since it makes their history permanently available to them. If the repository is arranging for retrieved data to be cached for availability, then having their data in the repository is useful to content providers, since it can save them bandwidth (the repository can use standard techniques to check if it has the latest version of a URL).

0125A novel way of encrypting a data-item, suitable for use in the repository, is to use an encryption key to control a reversible cellular automata (RCA) dynamics. (For a discussion of RCA models, see N. Margolus, “Crystalline Computation,” in the book Feynman and Computation, edited by A. Hey, Perseus Books 1999, pages 267-305). A CA-based scheme has the advantage that it can be run efficiently in software and can easily be accelerated in hardware, since the dynamics is local and uniform (see N. Margolus, “A mechanism for efficient data access and communication in parallel computations on an emulated spatial lattice,” USPTO patent application, filed Aug. 12, 1999). This is illustrated in <figref idref="DRAWINGS">FIG. 11</figref>. In this example, the bit-string <b>90</b> to be encrypted can be taken to be the cell data for an n-dimensional CA space, with a plurality of bits associated with each cell. In the illustration, we divide the bit-string <b>90</b> into four pieces (<b>90</b><i>a</i>, <b>90</b><i>b</i>, <b>90</b><i>c </i>and <b>90</b><i>d</i>) which we will call bit-fields. Each bit-field can be interpreted as an n-dimensional array of bits, with a fixed mapping between position in the bit-string and position in the array. In general, bit-fields will be the same size in corresponding dimensions, and bits from each bit-field constitute a cell (e.g., <b>91</b><i>i</i>). Data is moved within an emulated space by independently spatially shifting each bit-field, interpreted as an n-dimensional array. An example of shifting for 1-dimensional bit-fields is shown in <b>92</b>. In general, this kind of shifting can be performed efficiently for n-dimensional bit-fields using the techniques discussed in the patent application cited above. Bits <b>93</b><i>a </i>that shift past the edge <b>95</b><i>a </i>of one dimension wrap around to the opposite edge <b>95</b><i>b </i>as bits <b>94</b><i>a</i>, and similarly with bits <b>93</b><i>b</i>, <b>93</b><i>c </i>and <b>93</b><i>d</i>. The shift amount and/or direction can be different in each of a sequence of RCA steps, with the amounts and directions controlled by portions (<b>99</b><i>a</i>, <b>99</b><i>b</i>, <b>99</b><i>c</i>, <b>99</b><i>d</i>) of the key <b>99</b>, interpreted as binary numbers. In between data shifting steps, some or all cells (such as <b>91</b><i>i</i>) can be updated individually, with invertibility guaranteed by having the operation performed on each cell be a permutation on the cell's state set. The choice of permutation in each such transformation can be determined by bits of the key (such as <b>99</b><i>e</i>). If more bits than are present in the key are desired to control the sequence of shifts and permutations, the key may be transformed in some iterative fashion to produce additional control bits.

Other Embodiments

0126Although some of this discussion has focused on mirroring of file system data, the methods and protocols described here are of much more general utility. File system mirroring is discussed primarily as an initial application, to help establish the repository. As noted above, the operation of the data-servers and their associated data-transmission and data-storage protocol constitute a separate business which is compatible with a wide variety of clients, and a wide variety of data-storage entities. This business and protocol will evolve with time.

0127It is to be understood that while the invention has been described in conjunction with the detailed description thereof, the foregoing description is intended to illustrate and not limit the scope of the invention, which is defined by the scope of the appended claims.

0128Other embodiments are within the scope of the following claims.