This paper points out privacy concern fundamental to the way that Bitcoin operates, namely that the blockchain allows for the creation of transaction graphs that can be used to monitor and potentially de-anonymize individual accounts. The author proceeds to explain several existing attempts to introduce greater privacy by confusing the transaction graph, but notes that they all have their own drawbacks. The author then suggest using modified confidential transactions, one-way aggregate signatures, and merging transactions across blocks to allow for confidential transactions and an obscured transaction graph.

We introduce the first graph-theoretic proof-of-work system, based on finding small cycles or other structures in large random graphs. Such problems are trivially verifiable and arbitrarily scalable, presumably requiring memory linear in graph size to solve efficiently. Our cycle finding algorithm uses one bit per edge, and up to one bit per node. Runtime is linear in graph size and dominated by random access latency, ideal properties for a memory bound proof-of-work. We exhibit two alternative algorithms that allow for a memory-time trade-off (TMTO)—decreased memory usage, by a factor k, coupled with increased runtime, by a factor Ω(k). The constant implied in Ω() gives a notion of memory-hardness, which is shown to be dependent on cycle length, guiding the latter’s choice. Our algorithms are shown to parallelize reasonably well.