Basic Concepts

Ad-hoc Networks

In wireless networks, an ad-hoc connection is a direct connection between nodes. This type of connection doesn't rely on any infrastructures (e.g. base stations). Consequently, the nodes are only able to connect to others that are within its range. An ad-hoc network is a scalable network composed of nodes connected by ad-hoc connections. In such network, a node can communicate with others that are not within its range with the help of nodes between them. Those intermediate nodes can help pass along packets until they reach the destination. So with the cooperation of its participants, the network can achieve full connectivity, while retaining its independence from centralized infrastructures.

This independence means that the network can emerge without the need of any third party installed and maintained infrastructures. The nodes in the network combine their resources together to build a functional, fully connected network. Furthermore, having all nodes act both as clients and routers eliminates central points of failure in the network, and maximizes potential route redundancies.

Password Capabilities

Imagine a token with a text inscribed on it. The text describes what the possessor of the token is allowed to do. For example, it might say "you're allowed to run process A". This token can be passed around, and the ones who possess this token are allowed to do what the inscribed text says. This token is analogous to what a capability is.

A capability system is a very fine-grained access control system. It grants the capabilities to processes that need them. It works with the Principle of Least Privilege. That is, a process should only be given as much access right as it needs to perform its task. For example, an e-mail client should only have the right to access the mailbox, and to open a socket. It doesn't need, and shouldn't be granted the right to delete or read files on a user's home directory.

The question is how do we represent or implement a capability? Any implementation of capabilities need to provide protection againt forgeries, and malicious or accidental alterations. The Password-Capability system provides protection by sparsity. It represents capabilities with random passwords. So only those who know the password are authorised to exercise the right inferred by the capability.

The advantage of representing capabilities with passwords is that they're only numbers. They can be passed around on the wire across computers easily. Password-capability systems also allows derivation. When an object is first created, the master capability is returned to the object creator. It grants the permission to do anything to the object. The possessor of the master capability can then derive a new capability from that master capability. The new capability has to be more restrictive than the parent one. Processes that posses that new capability can again further derive that capability.

Password-Capability systems has many other features, like revocation, confinement and resource charging. They're not explain here, since they're outside the scope of this web page.

Distributed Hash Tables

A Distributed Hash Table (DHT) is similar to traditional hash tables in that it associates a value with a key. Like hash tables, when presented with a key, it returns the corresponding value. But unlike traditional hash tables, the data is stored some nodes in a network, not in a table. So DHT is an overlay network method that provides a routing algorithm that forwards information lookup requests to the right set of nodes in a network. Those set of nodes then answer the query redundantly. Some examples of DHT systems include Tapestry, Chord and Kademlia.

DHTs achieve high information lookup scalability in a fully decentralized network. Rather than flooding the network with requests to find nodes that host the desired data, DHTs use a routing algorithm, which eliminates half of the search space after every query. The way this is done differs according to the routing algorithm employed. The central idea behind it is that each node in the network stores information about all nodes in an area in the topology that it's responsible for. So after every query, the source node would have better information about which nodes are likely to know about the location of the information.

Threshold Signatures

A threshold signature system allows a group of actors to sign a message collectively. Like traditional digital signature schemes, it uses a pair of public and private key. Unlike traditional schemes, the private key is distributed among the actors in a group. A (n, t+1) threshold signature scheme allows t+1 actors in a group to sign a message, signifying that the majority of the group has acknowledged the message. On the other hand, t or less actors won't be able to do it, even if they collude.

---

References