Mining out of Delphi: bitcoin proofs of work without random oracles
OA Version
Citation
Abstract
The Random Oracle (RO) model has proven to be very powerful for building cryptographic tools, but is known to be unrealistic. As such, finding security proofs for various crypto primitives that do not involve the random oracle model is of utmost importance. One property of the RO – Correlation Intractability (CI) – has proven to be an extremely useful property in this regard. A series of publications (Canetti et al., 2018) (Canetti et al., 2019) have constructed succinct publicly verifiable non- interactive argument systems using hash functions that are CI. Another application of RO is the Proof of Work(PoW) in Bitcoin where it serves many functions. In this thesis, we investigate these functions and attempt to eliminate the RO assumption for at least some of the functions that it serves.
For the puzzle itself in Bitcoin mining, we attempt to construct a candidate hash function that is moderately hard CI – a function for which, it is hard, but not impossible, to find, an input-output pair that satisfies a particular moderately sparse relation. The motivation for this is mainly the fact that such a function should be able capture the properties of the work that a successful bitcoin miner needs to do.