A public ledger, especially one without a trusted party, requires computational techniques in order to ensure that the record is valid and cannot be controlled by malicious parties. We need to ensure that transactions can't be swapped, reversed, cloned, removed, and that new coins are generated on solid grounds.
Transaction consistency
All these features can be stated in terms of logical properties (e.g. consistency) on a chain of transactions. However, several consistent chains may still be inconsistent with each other, so we need in addition to ensure that a majority of parties can agree on a single valid chain.
Spawn it if you can
If we have a chain recording transactions in a payment system, the problem is that several of the parties that are supposed to make the system work (aka miners) can collude and spawn a chain that records an alternative reality. Moreover, they may be able to convince other parties that this is actually the real chain, forming a new consensus that invalidates previous transactions.
To deal with this problem, Bitcoin makes it computationally hard for miners to add blocks of transactions to the chain, i.e. they have to provide a proof of work. Moreover, the challenge for the proof of work is derived from the block chain, this way gluing the new transactions into the chain. After a few such chain extensions a time T, it is getting harder and harder for miners to spawn a chain that shows alternative transactions at time T or earlier.
From time to space
A proof of work takes time and energy, so, are there any other options available to authenticate the transaction chain? I'll summarize the papers [1] and [2], where they show how to do it with proofs of space, which look like this:
Setting: a prover P has to convince a verifier V that it allocated space of size N
- P stores a structure S of size N
- V obtains from P a space commitment comm(S)
- V challenges P for a proof that it indeed stored S of size N
- V can accept or reject
- Completeness: V always accepts the proof of a P that is honest, i.e. if it stored the required O(N) space ;
- Soundness: a dishonest P has to spend at least O(N) time during execution in order for its proof to be accepted by V ;
- Efficiency: V has to run in time at most O(log(N)) and polynomial in the security parameter (in both phases), while for P we allow O(N) time during initialization.
Consider the following simple protocols for proving space:
- V sends a random file of size N to P at initialization and at execution queries for some of its random bits. This protocol does not satisfy efficiency, since the verifier runs in time O(N).
- For a difficult to invert function F, P stores (1, F(1)), ... (N, F(N)) at initialization and V queries for the inverse of a random F(r) at execution. This protocol does not satisfy soundness, since it is known that a prover can answer such a challenge in time O(N^(2/3)) by using only O(N^(2/3)) space [3].
- At initialization, P constructs a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree) storing values w_1,...,w_N and V gets the root of this tree. At execution, V requests P to open some random branches of the tree. Is this a proof of space? Probably not. In fact, the main construction of [1] adds an additional constraint on the values w_1,...,w_N that are to be stored in the Merkle tree.
The values w_1,...,w_N in the Merkle tree will be labels of nodes in a direct acyclic graph G, computed using the following equation
w=h(v,w_1,...,w_n)
where h is a hash function, w is the label for the node v, and w_1,...,w_n are the labels for the parents of v. Moreover, G is not just any graph, but a graph with a small number of edges (e.g. in-degree of O(log N) or less) that should be hard to pebble: if the prover P stores only a few labels of the graph, it should be computationally hard for P to get the label of a challenge node.
The hard to pebble requirement for the graph amounts to having enough precedents for a random node in the graph, even if some of its nodes are removed. The main construction of such a graph proposed in [1] is based on a chain of bipartite graphs that are robust expanders [4], superposed with a sparse graph with dense long paths [5], and connected to a superconcentrator [6]. It has in-degree of O( log log N).
On the blockchain, time binds stronger than space
Goin back to our chain of transactions, interesting things are revealed when we replace a proof of work with a proof of space. The blocks in Bitcoin are chained as follows:
[ trans , hash , key , pw ] -----> [ trans', hash', key', pw' ]
where hash' = h(trans', hash, key', pw')
and pw' is such that hash' < L
For a random hash function h, it is difficult to find a value pw' satisfying the constraints above, when L is chosen to be small enough - therefore pw' is a proof of work connecting a block to its predecessor.
In a proof of space, let us denote by proof( chal, comm(S) ) the proof that P supplies to the verifier after having commited comm(S) in the initialisation phase and being challenged with chal in the execution phase. We could then have the blocks chained as follows:
[ trans, hash, key, ps ] -----> [ trans', hash', key', ps' ]
where hash' = h(trans', hash, key', ps')
and ps' = [ comm(S') , proof( hash, comm(S') ) ]
and S' is some allocated space for the mined block
and S' is some allocated space for the mined block
For some reason, [2] requires miners to publish the space commitment comm(S') in an earlier transaction that is already on the block chain (they have special transactions for this). More seriously, because proofs of space are computationally easy to produce, we have the problem of grinding, where a miner can try out different values hash' (by trying different sets of transactions trans' as inputs) and choose one that will make it easier to have his blocks accepted on the chain in future - a malicious miner can hijack the chain this way. To address this, [2] proposes to remove the transactions from the input of the hash, and instead add two signatures to the block:
s_1' = sign(trans', sk(key') )
s_2' = sign( (s_1,s_2), sk(key'))
one on transactions in the new block, and one on signatures in the previous block.The challenge of more
There is also a problem with using the hash of the previous block as a challenge for the proof. This means that, if there are several competing chains, the challenges for the newly added block will be different in each chain. Again, because proofs of space are easy to compute, self-interested miners can estimate the value of adding their blocks to various chains (for different challenges, the value of blocks will be different - according to definitions in [2]), and this leads to problems in reaching consensus on a single chain. The paper proposes several ideas for finding a good single challenge (from further in the past, from an unpredictable beacon, from other miners), but none of them is ideal. Another problem to reaching consensus is that the miners can extend multiple chains, and not, as they're supposed to, concentrate only on the best one. To address this, [2] introduces a new type of transactions that allows a miner to penalize another who worked on multiple chains, and collect some of its coins.
References
[1] Proofs of space
Stefan Dziembowski and Sebastian Faust and Vladimir Kolmogorov and Krzysztof Pietrzak [CRYPTO 2015]
https://eprint.iacr.org/2013/796
[2] Spacemint: a cryptocurrency based on proofs of space
Sunoo Park and Krzysztof Pietrzak and Albert Kwon and Joël Alwen and Georg Fuchsbauer and Peter Gaži
https://eprint.iacr.org/2015/528
[3] A cryptanalytic time-memory trade-off
Martin Hellman
Information Theory, IEEE Transactions on 26.4 (1980): 401-406.
[4] Pseudorandomness
Salil P. Vadhan
Foundations and Trends in Theoretical Computer Science, Vol. 7, pp 1-336
[5] On sparse graphs with dense long paths.
Erdoes, Paul, Ronald L. Graham, and Endre Szemeredi.
Computers & Mathematics with Applications 1.3 (1975): 365-369.
[6] Graph-theoretic properties in computational complexity.
Valiant, L. G. (1976).
Journal of Computer and System Sciences, 13(3), 278-285.
