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:

__a prover__

*Setting:**has to convince a verifier*

**P**

*V**that it allocated space of size*

*N*

*Initialization:*stores a structure*P**S**N*obtains from*V*a space commitment*P**comm(S)*

*Execution*challenges*V*for a proof that it indeed stored*P*of size*S**N*can*V*or**accept***reject*

*Desired properties*always accepts the proof of a**Completeness:****V**that is honest, i.e. if it stored the required**P**space ;*O(N)*: a dishonest**Soundness**has to spend at least*P*time during execution in order for its proof to be accepted by**O(N)**;*V*has to run in time at most*Efficiency: V***O(log(N))**and polynomial in the security parameter (in both phases), while for P we allowtime during initialization*O(N)***.**

**The proofs of space that aren't**

Consider the following simple protocols for proving space:

sends a random file of size**V**to**N**at initialization and at execution queries for some of its random bits. This protocol does not satisfy**P****efficiency,**since the verifier runs in time**O(N).**- For a difficult to invert function
,**F**stores**P**at initialization and*(1, F(1)), ... (N, F(N))***V**at execution. This protocol does not satisfy*F(r)*, since it is known that a prover can answer such a challenge in time**soundness***O(N^(2/3))*space [3].*O(N^(2/3))* - At initialization,
constructs a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree) storing values**P**and*w_1,...,w_N*gets the root of this tree. At execution,**V**requests**V**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**P**that are to be stored in the Merkle tree.**w_1,...,w_N**

**Crypto graphs: robust expanders, superconcentrators, dense long pathers**

The values

**in the Merkle tree will be labels of nodes in a direct acyclic graph**

*w_1,...,w_N**, computed using the following equation*

**G**

*w=h(v,w_1,...,w_n)*where

*is a hash function,***h***is the label for the node***w***, and***v***are the labels for the parents of***w_1,...,w_n***. Moreover,***v***is not just any graph, but a graph with a small number of edges (e.g. in-degree of***G****or less) that should be hard to pebble: if the prover***O(log N)**stores only a few labels of the graph, it should be computationally hard for***P****to get the label of a challenge node.***P*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**

**[**

*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

*, it is difficult to find a value***h***satisfying the constraints above, when***pw'***is chosen to be small enough - therefore***L***is a proof of work connecting a block to its predecessor.***pw'**In a proof of space, let us denote by

*the proof that*

**proof( chal, comm(S) )****supplies to the verifier after having commited**

*P**in the initialisation phase and being challenged with*

**comm(S)****in the execution phase. We could then have the blocks chained as follows:**

*chal*

**[**

*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**

For some reason, [2] requires miners to publish the space commitment

*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***comm(S')****, where a miner can try out different values***grinding***(by trying different sets of transactions***hash'**as inputs)***trans'****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'))***The challenge of more**

There is also a problem with using the

*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*

**hash***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.*

**consensus****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.