A Proof of Work (PoW) is an important construction for spam-mitigation and distributed consensus protocols. Intuitively, a PoW is a short proof that is easy for the verifier to check but moderately expensive for a prover to generate. However, existing proofs of work are not egalitarian in the sense that the amortized cost to generate a PoW proof using customized hardware is often several orders of magnitude lower than the cost for an honest party to generate a proof on a personal computer. Because Memory-Hard Functions (MHFs) appear to be egalitarian, there have been multiple attempts to construct Memory-Hard Proofs of Work (MHPoW) which require memory-hard computation to generate, but are efficient to verify. Biryukov and Khovratovich (Usenix, 2016) developed a MHPoW candidate called Merkle Tree Proofs (MTP) using the Argon2d MHF. However, they did not provide a formal security proof and Dinur and Nadler (Crypto, 2017) found an attack which exploited the data-dependencies of the underlying Argon2d graph. We revisit the security of the MTP framework and formally prove, in the parallel random oracle model, that the MTP framework is sound when instantiated with a suitable data-independent Memory-Hard Function (iMHF). We generically lower bound the cumulative memory cost ( \({\textsf{cmc}} \) ) of any prover for the protocol by the pebbling cost of the ex-post facto graph. We also prove that, as long as the underlying graph of the original iMHF is sufficiently depth-robust, the ex-post facto graph will have high cumulative memory cost—except with negligible probability. In particular, if we instantiate the iMHF with DRSample then we obtain a MHPoW with the following properties: (1) An honest prover for the protocol can run in sequential time O(N), (2) The proofs have size \(\texttt{polylog}(N)\) and can be verified in time \(\texttt{polylog}(N)\) (3) Any malicious prover who produces a valid proof must incur high \({\textsf{cmc}} \) at least \(\varOmega \left( \frac{N^2}{\log N}\right) \) . We also develop general pebbling attacks which we use to show that (1) any iMHF based MHPoW using the MTP framework has proof size at least \(\varOmega \left( \log ^2 N/\log \log N \right) \) , and (2) at least \(\tilde{\varOmega }(N^{0.32})\) when the iMHF is instantiated with Argon2i, the data-independent version of Argon2.

Provably Memory-Hard Proofs of Work with Memory-Easy Verification

会议论文
发表日期：

2026年

查看全文

Jeremiah Blocki,
Nathan Smearsoll

摘要

A Proof of Work (PoW) is an important construction for spam-mitigation and distributed consensus protocols. Intuitively, a PoW is a short proof that is easy for the verifier to check but moderately expensive for a prover to generate. However, existing proofs of work are not egalitarian in the sense that the amortized cost to generate a PoW proof using customized hardware is often several orders of magnitude lower than the cost for an honest party to generate a proof on a personal computer. Because Memory-Hard Functions (MHFs) appear to be egalitarian, there have been multiple attempts to construct Memory-Hard Proofs of Work (MHPoW) which require memory-hard computation to generate, but are efficient to verify. Biryukov and Khovratovich (Usenix, 2016) developed a MHPoW candidate called Merkle Tree Proofs (MTP) using the Argon2d MHF. However, they did not provide a formal security proof and Dinur and Nadler (Crypto, 2017) found an attack which exploited the data-dependencies of the underlying Argon2d graph. We revisit the security of the MTP framework and formally prove, in the parallel random oracle model, that the MTP framework is sound when instantiated with a suitable data-independent Memory-Hard Function (iMHF). We generically lower bound the cumulative memory cost ( \({\textsf{cmc}} \) ) of any prover for the protocol by the pebbling cost of the ex-post facto graph. We also prove that, as long as the underlying graph of the original iMHF is sufficiently depth-robust, the ex-post facto graph will have high cumulative memory cost—except with negligible probability. In particular, if we instantiate the iMHF with DRSample then we obtain a MHPoW with the following properties: (1) An honest prover for the protocol can run in sequential time O(N), (2) The proofs have size \(\texttt{polylog}(N)\) and can be verified in time \(\texttt{polylog}(N)\) (3) Any malicious prover who produces a valid proof must incur high \({\textsf{cmc}} \) at least \(\varOmega \left( \frac{N^2}{\log N}\right) \) . We also develop general pebbling attacks which we use to show that (1) any iMHF based MHPoW using the MTP framework has proof size at least \(\varOmega \left( \log ^2 N/\log \log N \right) \) , and (2) at least \(\tilde{\varOmega }(N^{0.32})\) when the iMHF is instantiated with Argon2i, the data-independent version of Argon2.