A Dream Direct Product Theorem for a Moderately Hard Function

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Statement

View PDF · LaTeX source · Formal statement — not yet formalized

The source builds permissionless consensus without a random oracle or a beacon by having parties generate their own challenges via a distributed sampler, at the cost of a hardness-preservation loss exponential in how many times a sampler message is reused. That loss must be absorbed by the underlying proof of work’s multi-instance security, and the source’s Corollary 3 pins down exactly what is needed: a \((d_0,d_1,\beta,\epsilon)\)-moderately hard proof of work over challenges in \(\{0,1\}^{n(\lambda)}\) with \(\epsilon(t,\lambda) = 2^{-t \cdot n(\lambda)^\gamma}\) for a constant \(\gamma > 0\) — an adversary given \(t\) challenges and roughly \(t\) times the honest solving budget should still succeed with probability at most \(2^{-t \cdot n^\gamma}\), the exact \(t\)-th power of the single-instance bound, with no loss in the exponent.

The source further shows that efficient verifiability is not the obstacle: any function that is moderately hard with these parameters — even if nobody can check a proposed solution quickly — becomes a full proof of work once compiled with a subexponentially sound SNARG for \(\mathsf{P}\), itself available from subexponentially secure LWE. That reduces the entire remaining gap to a statement about a plain function family.

Conjecture (dream direct product theorem). There exist a constant \(\gamma > 0\) and a function family \(f = \{f_{s,\lambda}\}\), with an associated PPT challenge sampler, that is \((d_0,d_1,\beta,\epsilon)\)-moderately hard in the above sense assuming NSETH: for every adversary given \(t \le d_0(\lambda)\) challenges and a budget of \(t \cdot \beta(s,\lambda) \cdot r(s,\lambda)\) steps (where \(r\) is the honest evaluation cost), the probability of solving all \(t\) challenges is at most \(2^{-t \cdot n(\lambda)^\gamma}\).

The source names NSETH only as an example — “assuming, say, NSETH” — rather than committing to it, so a proof from any standard fine-grained hardness hypothesis with a comparable flavor would answer the same question.

Sources

• Abram, Ball, Garay, and Kiayias. Permissionless Consensus from a Common Random String. Cryptology ePrint Archive, Report 2026/1179; abridged version to appear in Proc. CRYPTO 2026. The open question is posed in Section 5 (“Extensions and Open Questions”), pp. 22–23; Corollary 3 and the SNARG-compilation remark are on p. 16; the definition of moderate hardness for a proof of work (Definition 14, adapted here to a plain function) is on p. 27. NSETH is named once, on p. 23, without a definition or citation in the source. InputOutput

Proof

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Open. The source supplies no candidate function or partial construction anywhere — its remaining sections and appendices are proofs of its own theorems (background definitions and the security proofs of Theorems 1, 2 and 6), not attempts at this statement. Its only remark toward feasibility is that the ad hoc puzzles already deployed in practice are “likely to satisfy” the requirement, offered without argument.

Why the easy fixes don’t work. Complexity leveraging — raising the puzzle’s security parameter in proportion to the number of reused instances \(t\) — fails because it raises the honest solving cost by the same factor, defeating the purpose of a puzzle whose whole point is to be cheap to generate once and reused. The source states plainly that existing proofs of work from fine-grained hardness assumptions do not reach the subexponential soundness this needs.

What the source’s own SNARG argument buys. It is worth being precise about what is and is not established: the compilation from a moderately hard function to a full proof of work is proved, conditional on subexponentially secure LWE. Nothing about finding the moderately hard function is touched by that argument — it only says that once found, checkability comes for free.

Discussion

This is a hardness-amplification question dressed as a consensus-protocol requirement, and the source is candid that the dressing has been fully removed by the time it reaches this page: solving it needs no distributed sampler, no consensus protocol and no signature scheme, only a function family and a fine-grained hypothesis. That is what makes it a clean statement rather than an artifact of the surrounding construction — and also why a resolution would travel beyond this one paper’s application, since “dream” (lossless) direct product theorems for fine-grained, nondeterministic-hardness-style problems are a recognized sticking point that standard amplification techniques (XOR lemmas, Yao’s theorem and its relatives) do not generally deliver in this lossless form.

Open obligations

• Construct a function family and challenge sampler that is \((d_0,d_1,\beta,\epsilon)\)-moderately hard with \(\epsilon(t,\lambda) = 2^{-t\cdot n(\lambda)^\gamma}\), under NSETH or another standard fine-grained hardness hypothesis.
• Determine whether any of the ad hoc puzzles already deployed in practice (as the source suggests) can be proved to satisfy this property under a stated hypothesis, rather than merely conjectured to.
• Settle whether a tight version — the per-instance bound \(2^{-n(\lambda)^\gamma}\) itself achievable, not just an upper bound on multi-instance success — is also obtainable.
• Determine whether the two side conditions considered but not imposed here (a polynomial relation between evaluation cost and the time parameter; a polynomial bound on \(1/\beta\)) are necessary for a meaningful instantiation, or artifacts of one way of stating the question.
• Formalize the statement in Lean, including the definition of moderate hardness and a statement of NSETH; neither exists in Mathlib.