DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2025.16

Nakamoto Consensus from Multiple Resources

Authors: Mirza Ahad Baig, Christoph U. Günther, and Krzysztof Pietrzak

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

The blocks in the Bitcoin blockchain "record" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF). In this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks. We completely classify such functions in an idealized "continuous" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the "timed" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia). Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.

Cite as

Mirza Ahad Baig, Christoph U. Günther, and Krzysztof Pietrzak. Nakamoto Consensus from Multiple Resources. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baig_et_al:LIPIcs.AFT.2025.16,
  author =	{Baig, Mirza Ahad and G\"{u}nther, Christoph U. and Pietrzak, Krzysztof},
  title =	{{Nakamoto Consensus from Multiple Resources}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.16},
  URN =		{urn:nbn:de:0030-drops-247353},
  doi =		{10.4230/LIPIcs.AFT.2025.16},
  annote =	{Keywords: Nakamoto Consensus, Heaviest-chain Rule, Resource Theory}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2025.85

Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation

Authors: Dorian Rudolph, Sevag Gharibian, and Daniel Nagaj

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the complexity of QSAT transition from "easy" to "hard"? Here, we study QSAT with each constraint acting on a d_A-dimensional and d_B-dimensional qudit pair, denoted (d_A×d_B)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA_1-hard, in that (2×5)-QSAT is QMA_1-complete. (QMA_1 is a quantum analogue of MA with perfect completeness.) In contrast, (2×2)-QSAT (i.e. Quantum 2-SAT on qubits) is well-known to be poly-time solvable [Bravyi, 2006]. Our second main result proves that (3×d)-QSAT on the 1D line with d ∈ O(1) is also QMA_1-hard. Finally, we initiate the study of (2×d)-QSAT on the 1D line by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. As implied by our title, our first result uses a direct embedding: We combine a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset and Nagaj, 2013]. Of note is a new simplified and analytic proof for the latter (as opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection Lemma", allowing us to break low energy analyses into small patches of projectors, and to improve the soundness analysis of [GN13] from Ω(1/T⁶) to Ω(1/T²), for T the number of gates. Our second result goes via black-box reduction: Given an arbitrary 1D Hamiltonian H on d'-dimensional qudits, we show how to embed it into an effective 1D (3×d)-QSAT instance, for d ∈ O(1). Our approach may be viewed as a weaker notion of "analog simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA_1-hardness result.

Cite as

Dorian Rudolph, Sevag Gharibian, and Daniel Nagaj. Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 85:1-85:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rudolph_et_al:LIPIcs.ITCS.2025.85,
  author =	{Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel},
  title =	{{Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript\{1\}-Complete: Direct Embeddings and Black-Box Simulation}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{85:1--85:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.85},
  URN =		{urn:nbn:de:0030-drops-227139},
  doi =		{10.4230/LIPIcs.ITCS.2025.85},
  annote =	{Keywords: quantum complexity theory, Quantum Merlin Arthur (QMA), Quantum Satisfiability Problem (QSAT), Hamiltonian simulation}
}

Document

DOI: 10.4230/LIPIcs.ITP.2023.7

A Proof-Producing Compiler for Blockchain Applications

Authors: Jeremy Avigad, Lior Goldberg, David Levit, Yoav Seginer, and Alon Titelman

Published in: LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023)

Abstract

Cairo is a programming language for running decentralized applications (dapps) at scale. Programs written in the Cairo language are compiled to machine code for the Cairo CPU architecture, and cryptographic protocols are used to verify the results of the execution traces efficiently on blockchain. We explain how we have extended the Cairo compiler with tooling that enables users to prove, in the Lean 3 proof assistant, that compiled code satisfies high-level functional specifications. We demonstrate the success of our approach by verifying primitives for computations with an elliptic curve over a large finite field, as well as their use in the validation of cryptographic signatures.

Cite as

Jeremy Avigad, Lior Goldberg, David Levit, Yoav Seginer, and Alon Titelman. A Proof-Producing Compiler for Blockchain Applications. In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{avigad_et_al:LIPIcs.ITP.2023.7,
  author =	{Avigad, Jeremy and Goldberg, Lior and Levit, David and Seginer, Yoav and Titelman, Alon},
  title =	{{A Proof-Producing Compiler for Blockchain Applications}},
  booktitle =	{14th International Conference on Interactive Theorem Proving (ITP 2023)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-284-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{268},
  editor =	{Naumowicz, Adam and Thiemann, Ren\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.7},
  URN =		{urn:nbn:de:0030-drops-183820},
  doi =		{10.4230/LIPIcs.ITP.2023.7},
  annote =	{Keywords: formal verification, smart contracts, interactive proof systems}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2020.5

DEEP-FRI: Sampling Outside the Box Improves Soundness

Authors: Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space U is δ-far in relative Hamming distance from a linear code V - this is the worst-case assumption - then most elements of U are almost-δ-far from V - this is the average case. However, this result was known to hold only below the "double Johnson" function of the relative distance δ_V of the code V, i.e., only when δ < 1-(1-δ_V)^(1/4). First, we increase the soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point z outside the box D on which codewords are evaluated, and asks the prover for the value at z of the interpolating polynomial of a random element of U. Intuitively, the answer provided by the prover "forces" it to choose one codeword from a list of "pretenders" that are close to U. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V is approximately δ for all δ. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: - An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. The soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. - An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant < 1/8 to a constant arbitrarily close to 1.

Cite as

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf. DEEP-FRI: Sampling Outside the Box Improves Soundness. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 5:1-5:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bensasson_et_al:LIPIcs.ITCS.2020.5,
  author =	{Ben-Sasson, Eli and Goldberg, Lior and Kopparty, Swastik and Saraf, Shubhangi},
  title =	{{DEEP-FRI: Sampling Outside the Box Improves Soundness}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{5:1--5:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.5},
  URN =		{urn:nbn:de:0030-drops-116901},
  doi =		{10.4230/LIPIcs.ITCS.2020.5},
  annote =	{Keywords: Interactive Oracle Proofs of Proximity, STARK, Low Degree Testing}
}

4 Search Results for "Goldberg, Lior"

Nakamoto Consensus from Multiple Resources

Abstract

Cite as

Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation

Abstract

Cite as

A Proof-Producing Compiler for Blockchain Applications

Abstract

Cite as

DEEP-FRI: Sampling Outside the Box Improves Soundness

Abstract

Cite as

Thanks for your feedback!

Could not send message