Venti (software)

Last updated

Venti is a network storage system that permanently stores data blocks. A 160-bit SHA-1 hash of the data (called score by Venti) acts as the address of the data. This enforces a write-once policy since no other data block can be found with the same address: the addresses of multiple writes of the same data are identical, so it is highly likely that duplicate data is easily identified and the data block is stored only once. Data blocks cannot be removed, making it ideal for permanent or backup storage. Venti is typically used with Fossil to provide a file system with permanent snapshots.

Contents

History

Venti was designed and implemented by Sean Quinlan and Sean Dorward at Bell Labs. It appeared in the Plan 9 distribution in 2002. Development has been continued by Russ Cox who has reimplemented most of the server, written a library for creating datastructures (files, directories and meta-data) to store in Venti and implemented optimizations. Venti is available both in the Plan 9 distribution and for many Unix-like operating systems [1] as part of Plan 9 from User Space. Venti is included as part of Inferno with accompanying modules for access. There is a Go set of programs to build your own Venti servers. Included are examples using different kinds of backend storage.

Details

Venti is a user space daemon. [2] Clients connect to Venti over TCP [2] and communicate using a simple RPC-protocol. The most important messages of the protocol are listed below. Note that there is no message to delete an address or modify data at a given address.

The data block stored by Venti must be greater than 512 bytes in length and smaller than 56 kilobytes. So, if a Venti user/client wants to store larger data blocks, it has to make a datastructure (which can be stored in Venti). For example, Fossil uses hash trees to store large files. Venti itself is not concerned with the contents of a data block; it does however store the type of a data block.

The design of Venti has the following consequences:

The data blocks are stored on hard drives. The disks making up the available storage, typically a RAID, is called the data log. This data log is split up in smaller pieces called arenas, which are sized so they can be written to other media such as CD/DVD or magnetic tape. Another set of hard drives is used for the index, which maps scores to addresses in the data log. The data structure used for the index is a hash table with fixed-sized buckets. Venti relies on the scores to be randomly distributed so buckets do not fill up. Since each lookup costs one disk seek time, an index usually consists of multiple hard drives with low access time.

Usage

The Venti server may be used by clients in several ways. The Plan 9 operating system makes use of Venti for daily archival snapshots of the file system. These copies of the main filesystem can be mounted as a filetree of full copies organized by date. The utility programs 'vac' and 'unvac' can be used to store and retrieve data from a Venti server in the form of individual files or as a directory and its contents. 'Vacfs' allows browsing of the data associated with a vac score without full retrieval of all remotely stored data. Data and index scores can be duplicated between Venti servers using 'rdarena' and 'wrarena'. Plan 9 from Bell Labs, Plan 9 from User Space, Inferno and any other clients that implement the Venti protocol can all be used interchangeably to store and retrieve data. [3]

Hash collisions

A basic principle of information theory is the pigeonhole principle, which states that if set A contains more values than set B, then for any function that maps A to B there will be members of B that are associated with more than one member of set A. In the case of Venti, the set of possible SHA-1 hashes is obviously smaller than the set of all possible blocks that could be stored in the filesystem, and thus a hash collision is possible.

The risk of accidental hash collision in a 160-bit hash is very small, even for exabytes of data. Historically, however, many hash functions become increasingly vulnerable to malicious hash collisions due to both cryptographic and computational advances. [4] Venti does not address the issue of hash collisions; as of this time,[ when? ] it is still computationally infeasible to find collisions in SHA-1, but it may become necessary for Venti to switch to a different hash function at some point in the future. On 23 February 2017, Google announced the SHAttered attack, in which they generated two different PDF files with the same SHA-1 hash in roughly 263.1 SHA-1 evaluations.

See also

Related Research Articles

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

passwd Tool to change passwords on Unix-like OSes

passwd is a command on Unix, Plan 9, Inferno, and most Unix-like operating systems used to change a user's password. The password entered by the user is run through a key derivation function to create a hashed version of the new password, which is saved. Only the hashed version is stored; the entered password is not saved for security reasons.

Hashcash is a proof-of-work system used to limit email spam and denial-of-service attacks. Hashcash was proposed in 1997 by Adam Back and described more formally in Back's 2002 paper "Hashcash – A Denial of Service Counter-Measure". In Hashcash the client has to concatenate a random number with a string several times and hash this new string. It then has to do so over and over until a hash beginning with a certain number of zeros is found.

The Encrypting File System (EFS) on Microsoft Windows is a feature introduced in version 3.0 of NTFS that provides filesystem-level encryption. The technology enables files to be transparently encrypted to protect confidential data from attackers with physical access to the computer.

<span class="mw-page-title-main">/dev/random</span> Pseudorandom number generator file in Unix-like operating systems

In Unix-like operating systems, /dev/random and /dev/urandom are special files that serve as cryptographically secure pseudorandom number generators (CSPRNGs). They allow access to a CSPRNG that is seeded with entropy from environmental noise, collected from device drivers and other sources. /dev/random typically blocked if there was less entropy available than requested; more recently it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for /dev/random and /dev/urandom.

Filesystem in Userspace (FUSE) is a software interface for Unix and Unix-like computer operating systems that lets non-privileged users create their own file systems without editing kernel code. This is achieved by running file system code in user space while the FUSE module provides only a bridge to the actual kernel interfaces.

<span class="mw-page-title-main">Digest access authentication</span> Method of negotiating credentials between web server and browser

Digest access authentication is one of the agreed-upon methods a web server can use to negotiate credentials, such as username or password, with a user's web browser. This can be used to confirm the identity of a user before sending sensitive information, such as online banking transaction history. It applies a hash function to the username and password before sending them over the network. In contrast, basic access authentication uses the easily reversible Base64 encoding instead of hashing, making it non-secure unless used in conjunction with TLS.

A versioning file system is any computer file system which allows a computer file to exist in several versions at the same time. Thus it is a form of revision control. Most common versioning file systems keep a number of old copies of the file. Some limit the number of changes per minute or per hour to avoid storing large numbers of trivial changes. Others instead take periodic snapshots whose contents can be accessed using methods similar as those for normal file access.

Fossil is the default file system in Plan 9 from Bell Labs. It serves the network protocol 9P and runs as a user space daemon, like most Plan 9 file servers. Fossil is different from most other file systems due to its snapshot/archival feature. It can take snapshots of the entire file system on command or automatically. These snapshots can be kept on the Fossil partition as long as disk space allows; if the partition fills up then old snapshots will be removed to free up disk space. A snapshot can also be saved permanently to Venti. Fossil and Venti are typically installed together.

Content-addressable storage (CAS), also referred to as content-addressed storage or fixed-content storage, is a way to store information so it can be retrieved based on its content, not its name or location. It has been used for high-speed storage and retrieval of fixed content, such as documents stored for compliance with government regulations. Content-addressable storage is similar to content-addressable memory.

In computer science, storage virtualization is "the process of presenting a logical view of the physical storage resources to" a host computer system, "treating all storage media in the enterprise as a single pool of storage."

sha1sum is a computer program that calculates and verifies SHA-1 hashes. It is commonly used to verify the integrity of files. It is installed by default on most Linux distributions. Typically distributed alongside sha1sum are sha224sum, sha256sum, sha384sum and sha512sum, which use a specific SHA-2 hash function and b2sum, which uses the BLAKE2 cryptographic hash function.

In public-key cryptography, a public key fingerprint is a short sequence of bytes used to identify a longer public key. Fingerprints are created by applying a cryptographic hash function to a public key. Since fingerprints are shorter than the keys they refer to, they can be used to simplify certain key management tasks. In Microsoft software, "thumbprint" is used instead of "fingerprint."

<span class="mw-page-title-main">MagmaFS</span>

Magma is a distributed file system based on a distributed hash table, written in C, compatible with Linux and BSD kernels using FUSE.

In computing, data deduplication is a technique for eliminating duplicate copies of repeating data. Successful implementation of the technique can improve storage utilization, which may in turn lower capital expenditure by reducing the overall amount of storage media required to meet storage capacity needs. It can also be applied to network data transfers to reduce the number of bytes that must be sent.

SipHash is an add–rotate–xor (ARX) based family of pseudorandom functions created by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012, in response to a spate of "hash flooding" denial-of-service attacks (HashDoS) in late 2011.

crypt is a POSIX C library function. It is typically used to compute the hash of user account passwords. The function outputs a text string which also encodes the salt, and identifies the hash algorithm used. This output string forms a password record, which is usually stored in a text file.

Synnefo is a complete open-source cloud stack written in Python that provides Compute, Network, Image, Volume and Storage services, similar to the ones offered by AWS. Synnefo manages multiple Google Ganeti clusters at the backend that handle low-level VM operations and uses Archipelago to unify cloud storage. To boost 3rd-party compatibility, Synnefo exposes the OpenStack APIs to users.

ZFS is a file system with volume management capabilities. It began as part of the Sun Microsystems Solaris operating system in 2001. Large parts of Solaris, including ZFS, were published under an open source license as OpenSolaris for around 5 years from 2005 before being placed under a closed source license when Oracle Corporation acquired Sun in 2009–2010. During 2005 to 2010, the open source version of ZFS was ported to Linux, Mac OS X and FreeBSD. In 2010, the illumos project forked a recent version of OpenSolaris, including ZFS, to continue its development as an open source project. In 2013, OpenZFS was founded to coordinate the development of open source ZFS. OpenZFS maintains and manages the core ZFS code, while organizations using ZFS maintain the specific code and validation processes required for ZFS to integrate within their systems. OpenZFS is widely used in Unix-like systems.

References

  1. ↑ Such as Linux, FreeBSD, NetBSD, OpenBSD, SunOS or Mac OS X
  2. 1 2 3 4 Lukkien, Mechiel. Venti Analysis and Memventi Implementation. Thesis. University of Twente, 2007. N.p.: n.p., n.d. University of Twente Theses Repository. Web. 13 Oct. 2014. <http://essay.utwente.nl/694/1/scriptie_Lukkien.pdf>.
  3. ↑ "Venti (6) man page in the Plan 9 4th edition manual". Man.cat-v.org. Retrieved 2013-04-21.
  4. ↑ "HASH COLLISION Q&A." Cryptography Research. Rambus, n.d. Web. 12 Jan. 2010. <https://web.archive.org/web/20100306180648/http://www.cryptography.com/cnews/hash.html>.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.