POST relies on Pastry, a structured overlay network, as well as two basic services built upon Pastry: PAST, a storage system and Scribe, a group communication system. POST could easily be layered on similar systems like Chord/CFS, or Tapestry/OceanStore [14,6,9,16].
Pastry [12] is a structured p2p overlay network designed to be self-organizing, highly scalable, and fault tolerant. In Pastry, every node and every object is assigned a unique identifier chosen from a large id space, referred to as a nodeId and key, respectively. Given a message and a key, Pastry can efficiently route the message to the node whose nodeId is numerically closest to the key.
PAST [13] is a storage system built on top of Pastry and can be viewed as a distributed hash table. Each stored item in PAST is given a 160 bit key (hereafter referred to as the handle), and replicas of an object are stored at the k nodes whose nodeIds are the numerically closest to the object's handle. PAST maintains this invariant regardless of node arrivals or failures. Since nodeId assignment is random, these k nodes are unlikely to suffer correlated failures. PAST relies on Pastry's secure routing [2] to ensure that k replicas are stored on the correct nodes, despite the presence of malicious nodes. Throughout this paper, we assume that at most k-1 nodes are faulty or unreachable in any replica set.
POST stores three types of data in PAST: content-hash blocks, public-key blocks, and certificate blocks. Content-hash blocks are stored using the cryptographic hash of the block's contents as the handle. Public-key blocks contain monotonically increasing timestamps, are signed with a private key, and are stored using the cryptographic hash of the corresponding public key as the handle. Certificate blocks are signed by a trusted third party and bind a public key to a name (e.g., an email address). The block is stored using the cryptographic hash of the name as the handle.
Content-hash blocks can be authenticated by obtaining a single replica and verifying that its contents match the handle. Unlike content-hash blocks, public key blocks are mutable. To prevent rollback attacks by malicious storage nodes, clients attempt to obtain all k replicas and choose the authentic block with the most recent timestamp. Certificate blocks require a signature verification using the public key of a trusted third party.
Scribe [3] is a scalable multicast system built on top of Pastry. Each Scribe group has a 160 bit groupId, which serves as the address of the group. The nodes subscribed to each group form a multicast tree, consisting of the union of Pastry routes from all group members to the node with nodeId numerically closest to the groupId.