Blockchain as a cryptographic primitive

Abstract

We consider blockchain as a new cryptographic primitive. This primitive is defined as an ordered database that allows only the following two types of queries: (a) read the data (by any user) and (b) add a new record to the
end of the database (by a user who complied with certain requirements). A blockchain must satisfy the liveness and persistency conditions. The former condition guarantees that after a query to add a correct record, this record will eventually appear in the database. The latter one means that a record once
added cannot be removed or modified. One of the main problems concerning blockchain is whether this primitive exists. The paper discusses this problem in various models. Known positive results do not provide a satisfactory answer to this problem. In particular, they are all proved in the random oracle model.
In this paper, we focus on Proof-of-Work (PoW) blockchains that are based on cryptographic hash functions. Our main result is that if collision-resistant hash function families exist, then there exists such a family that cannot be used in a PoWblockchain. Therefore there is no black box construction of a PoW-blockchain from a collision-resistant hash function family.