Proof of storage scheme
The paper "Proofs of Space: When Space is of the Essence" proposes a scheme that allows a client to prove that it has read/write access to at least $B$ bytes of memory.  Basically, the server gives the client a function $f$ that requires at least $B$ bytes to compute, and the client proves it can compute $f$.  The method is complicated and I haven't absorbed all of the machinery.

One of the lead developers of Bitcoin has proposed a different scheme, which allows the client to prove that it is "tieing up" a certain amount of space over time.  The server can periodically send the client a challenge; if the client can always respond correctly, this proves that the client must have set aside that much space.

The idea behind the latter scheme is not too complex.  Basically, we form a GGM hash tree: for a complete binary tree of depth $d$, with a random 160-bit seed at the root, and then recursively label all of the nodes of the tree as follows: if a node has label $x$, then its left child has label $H(x||0)$ and its right child has label $H(x||1)$, where $H$ is a cryptographic hash function.  There are $2^d$ leaves.  Each leaf can be thought of as a pair $(i,x)$, where $i \in \{0,1\}^d$ is the index of the leaf (a binary string indicating the path taken from the root to that leaf) and $x$ is the label on that leaf.  Now sort these pairs on their $x$-values.

At any point, the server can challenge the client by picking a random index $i$, computing the label $x$ on that leaf (this takes just $d$ evaluations of $H$, and can be done by the server, since $H$ is publicly known), sending $x$ to the client, and asking the client to send back the corresponding index.  If the client has been tying up enough space to store all $2^d$ records, it can quickly find the corresponding $(i,x)$ pair and send back the correct value of $i$; if it hasn't, it will find it difficult to respond correctly.