Pith. sign in

REVIEW 3 major objections 4 minor 106 references

Proof of All: Verifiable Computation in a Nutshell

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read One seven-property model attempts to unify all cryptographic proof systems.

desk verdict A clear, mostly reliable survey of VC proof systems whose 'unifying model' is a property checklist, not a comparison framework, and whose central claim overstates what is delivered. read the letter →

arxiv 1908.02327 v2 pith:4PH5KTD2 submitted 2019-08-06 cs.CR

Mario Alessandro Barbara This is my paper · ORCID
classification cs.CR
keywords verifiablecomputationzero-knowledgeproofszk-STARKhomomorphicauthenticatorsdelayfunctionsuniversalproofcompilersystemcomparison
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The thesis argues that the many proof systems developed in recent decades—zero-knowledge protocols, homomorphic authenticators, verifiable delay functions, and zk-STARKs—can be read as instances of one subject, Verifiable Computation, described by a single checklist of seven properties: completeness, soundness, zero-knowledge, scalability, transparency, universality, and post-quantum safety. The payoff, if the model holds, is a common vocabulary that lets newcomers compare designs currently living in separate research communities with separate terminologies. The thesis then uses the checklist to analyse two non-universal families (HAUTHs and VDFs) and to present a simplified, design-level walkthrough of zk-STARKs as a "universal proof compiler". The work is a systematic presentation rather than a new theorem: the claim is that synthesis is possible and useful, not that a new cryptographic construction is being proved secure.

What carries the argument

The load-bearing mechanism is the VC Model: a named, standardised property checklist (completeness, soundness, zero-knowledge, scalability, transparency, universality, post-quantum safety) used as a lens for any proof system. The argument also depends on a second mechanism, the zk-STARK reduction pipeline: a computational integrity statement is arithmetised into an execution trace, the trace is encoded as low-degree polynomials, and the statement is finally checked by a polynomial comparison (2POLY) whose degree bound is verified by FRI, a fast proximity test for low-degree polynomials. The model does the work of the thesis's stated unification; the pipeline does the work of the simplified explanation.

What would settle it

Take two proof systems that tick the same seven property boxes but show a documented orders-of-magnitude gap in concrete cost (for example, proof size linear versus logarithmic, or one requiring a trusted setup and the other not): if the model has no way to rank or even describe that gap, then its claim to enable efficient comparison fails.

Watch

Extended reading notes

Core claim

The central claim is that every cryptographic proof system can be described and compared through a fixed set of qualitative properties, and that doing so reveals structural unity: arithmetisation plus interactivity underlies all of them. On this view, Homomorphic Authenticators are non-universal VC protocols that outsource small-degree computation through polynomial interpolation; Verifiable Delay Functions compress sequential time by replacing a long modular-exponentiation proof with a randomized cut-and-choose check; and zk-STARKs are "universal compilers" that reduce any program's correctness to a polynomial comparison problem, solved by low-degree polynomial encoding, hash-based commitments, and the FRI proximity test. The author's contribution is the unification and the accessible derivation of the zk-STARK design, not a claim that the underlying constructions change.

Load-bearing premise

The model assumes a fixed set of qualitative properties is enough to compare any two proof systems efficiently, but no metric, ordering, or formal criterion for "comparison" is ever defined.

Editorial extensions

If this is right

  • If the model is adopted, new proof systems can be introduced by ticking the same seven properties, making cross-family comparisons such as a VDF against a zk-STARK direct.
  • If the zk-STARK walkthrough is correct, a newcomer can trace exactly why the system is scalable (quasilinear prover, logarithmic verifier) and transparent (no trusted setup, only hash functions and public randomness).
  • If the re-analysis of HAUTHs and VDFs as instances of one VC domain is accepted, techniques such as execution traces and cut-and-choose transfer between families.
  • If the checklist becomes standard, conflicting terminology across proof-system papers can be mapped to a common set of properties, easing the entry into a fragmented field.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension would turn the seven qualitative properties into quantitative metrics (proof size, prover time, verifier time, setup trust) so that the model can rank systems, not just classify them; the paper itself leaves this unformalised.
  • The same reduction pipeline suggests that any future universal proof compiler relying on arithmetisation and low-degree testing can be described in the same language, making the model a useful teaching device even if it does not settle research questions.
  • The paper's own comparisons hint that a fuller unification would need to account for concrete performance trade-offs—proof length, setup assumptions, post-quantum resistance—that a purely qualitative checklist cannot express.
  • A promising next experiment would be to apply the seven-property model to a new proof system not analysed in the thesis, such as a pairing-based argument, to see whether the vocabulary remains exact or starts to blur.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. This MSc thesis, posted on arXiv, proposes a 'Verifiable Computation model' intended to simplify and enable efficient comparison of cryptographic proof systems. After a tutorial introduction to interactive proofs, zero-knowledge, Fiat-Shamir, scalability, and other properties, the thesis applies the model to Homomorphic Authenticators and Verifiable Delay Functions, and then offers an informal, design-oriented explanation of zk-STARKs, including arithmetisation, polynomial comparison, and FRI. The paper's stated contributions are a unifying model, technical analyses of HAUTHs and VDFs, and a simplified guide to zk-STARKs. Because it is a thesis, the presentation is deliberately informal and cites external sources for formal statements.

Significance. The expository portions have real value: the walkthrough of Wesolowski's VDF, the HAUTH construction chain from Gennaro–Wichs through Fiore et al., and the STARK arithmetisation chain (CIP to AP to execution trace to 2POLY to FRI) are generally faithful to the cited literature and could help newcomers. The paper also correctly notes which parts of STARK soundness are omitted. However, the central contribution is not established: the model is a property checklist, and the promised 'efficient comparison' framework is never defined or exercised. If the model were made operational, the paper could serve as a useful survey, but as it stands the strongest claim is a promise. No machine-checked proofs, benchmarks, or formal comparison criteria are provided in support of the claimed unifying model.

major comments (3)
  1. [Abstract; §1.6–1.7] The central claim of the abstract—that the proposed Verifiable Computation model enables 'efficient comparison of all cryptographic proof systems'—is not supported by the definitions given. Section 1.6 formalizes scalability through asymptotic complexity classes, and Section 1.7 lists transparency, universality, and post-quantum safety as qualitative properties, but no ordering, aggregation, weighting, or trade-off rule is defined, and no theorem or algorithm explains how two protocols are to be compared. The model as presented is a property checklist rather than a comparison framework; the paper should either develop the missing comparison methodology or explicitly narrow the claim to that of a common vocabulary.
  2. [§2.1–2.3] The model is never used comparatively. Chapter 2 analyzes Homomorphic Authenticators and Verifiable Delay Functions in separate subsections, but it does not compare the two families with each other or with a baseline using the properties of Sections 1.6–1.7. Section 2.3 concludes only that 'we should try to converge them' under the VC domain and leaves the analysis of remaining protocols as an open question. Because Objective 2 promises a 'Technical Analysis ... using the unifying model,' the absence of any worked comparative application is a gap in the manuscript's central claim; add a comparative case study, or revise the objective to describe the chapter as separate case studies.
  3. [§3.1.5; §3.2] The one concrete comparison in the thesis, zk-STARK versus zk-SNARK, is stated in ad hoc engineering terms—'approximately 1/10th proving time, half verification time, and 100 to 1000 times the proof length'—rather than derived from the model's definitions. Section 3.2 describes competing systems qualitatively (e.g., 'most successful field,' 'innovative solution'), again without mapping them into the VC-model property space. If the model is to support 'efficient comparison,' the comparison should follow from its definitions or be clearly labeled as informal; as written, the strongest advertised contribution is a promise rather than a demonstrated result.
minor comments (4)
  1. [§3.1.7] The text explicitly says the soundness analysis of FRI 'is the toughest part ... and something that we will not get into detail,' then asserts that FRI 'works very well' at large distance. For an informal survey this is acceptable, but the qualitative guarantee should be explicitly attributed to Ben-Sasson et al. [64] and [65], and the sentences should not read as new claims of the thesis.
  2. [§1.2] The IP definition places PUNBOUNDED and VPOLY in ITM, while the extractor-based soundness variant quantifies over P′ POLY; make the bounded/unbounded distinction for the prover explicit, since the text otherwise conflates proof systems with argument systems.
  3. [§2.2.4] The SPoW soundness display contains several under-specified symbols (α, rp, μλ, and the use of Ω) and the dependency between the assumptions and the conclusion is hard to follow; rewriting as numbered assumptions with a short prose proof would improve readability.
  4. [§1.2.1] The PCP theorem is attributed to 'Aurora et al.'; the references [5]–[8] list Arora et al., so the name should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the thesis is an expository survey that maps external constructions onto a property-based VC model; no fitted parameter is renamed as a prediction and no load-bearing self-citation is present.

full rationale

The paper does not derive predictions from fitted parameters, and its central "unifying VC model" is a descriptive checklist of standard cryptographic properties (completeness, soundness, zero-knowledge, scalability, transparency, universality, post-quantum safety) rather than a fitted or self-referential construct. The HAUTH and VDF analyses in Chapter 2 are presentations of externally published constructions mapped onto the model's vocabulary; the mapping is asserted descriptively, not derived from the model in a way that makes the conclusion identical to the input. The zk-STARK treatment in Chapter 3 is likewise an expository reduction to standard algebraic tools (vanishing polynomials, polynomial comparison, Schwartz–Zippel, Reed–Solomon proximity testing), citing the original STARK papers and other external works. The skeptical concern that "efficient comparison" is unsupported is a completeness or correctness issue, not circularity: the thesis never fits an equation to one subset of data and then presents a mathematically forced consequence as a prediction. There are also no load-bearing self-citations: the author does not rely on prior work of his own for the central premises. Accordingly, no specific circular step can be quoted, and the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The thesis contributes no new parameters or entities; it is a synthesis of existing concepts. Its 'unifying model' is a set of vocabulary choices, not a fitted or derived quantity.

assumptions (3)
  • domain assumption The standard cryptographic definitions of completeness, soundness, and zero-knowledge are taken as given from prior literature.
    Chapter 1 defines the VC model directly from these standard notions and builds the rest of the thesis on them without re-justification.
  • domain assumption The zk-STARK construction and its security are assumed correct as stated in Ben-Sasson et al. [51].
    Chapter 3 presents zk-STARKs as a breakthrough and relies on the original paper's soundness claims; the thesis explicitly declines to reproduce the soundness analysis (Section 3.1.7).
  • domain assumption The Random Oracle Model and existence of one-way hash functions are assumed for non-interactive and transparent variants.
    Section 3.1.5 lists these as the security assumptions for zk-STARKs, adopted from the cited work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Proof of All: Verifiable Computation in a Nutshell." pith.science (2026). https://pith.science/paper/4PH5KTD2

@misc{pith2026190802327,
  author       = {Pith},
  title        = {Pith review of: Proof of All: Verifiable Computation in a Nutshell},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4PH5KTD2}},
  note         = {Machine review of arXiv:1908.02327}
}
read the original abstract

Recent advances in the cryptographic field of "Zero-Knowledge Proofs" have sparked a new wave of research, giving birth to many exciting theoretical approaches in the last few years. Such research has often overlapped with the need for private and scalable solutions of Blockchain-based communities, resulting in the first practical implementations of such systems. Many of these innovative constructions have developed in parallel, using different terminologies and evolving into a fragmented ecosystem, calling for their consolidation into the more stable domain of "Verifiable Computation". In this master thesis I propose a unifying Verifiable Computation model for the simplification and efficient comparison of all cryptographic proof systems. I take advantage of this model to analyse innovative technologies (Homomorphic Authenticators, Verifiable Delay Functions) which developed into their own specialised domains, and I attempt to make them more accessible for newcomers to the field. Furthermore, I expand on the future of Verifiable Computation, Universal proof compilers and "Proofs of All", by approaching the state-of-the-art zk-STARK construction from a more accessible and informal design perspective.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

106 extracted references · 79 canonical work pages

  1. [1]

    We can think of income tax statements, for example, where a citizen is trying to perform tax evasion by submitting false claims regarding his income

    Integrity In order to trust the output of a specific computation, we need to consider that a Prover may be incentivised to cheat. We can think of income tax statements, for example, where a citizen is trying to perform tax evasion by submitting false claims regarding his income. To prevent this, and to trust the validity of the Prover’s claim, we need to s...

  2. [2]

    To allow a Prover to make such a privacy-friendly claim, we need to somehow “hide” our computation’s inputs (i.e

    Privacy What happens if the output of a specific computation can be revealed, but not its input? Consider a scenario in which I’m buying drinks at a bar and I need to provide identification to the bartender, so that he may check that I am of legal age to drink alcohol, but I do not want to reveal anything else about my age, name, nationality, height, or gen...

  3. [3]

    Capture The Flag

    Efficiency Along with the previous two fundamental properties, Ben-Sasson et al. mention this additional and more practical requirement. We are concerned with the realisation of concrete systems, which can be used under realistic and fair conditions, using hardware that is commonly available to any average Prover or Verifier. Assume you’re tasked with extra...

  4. [4]

    1.5); but keep in mind that it reduces our perfect zero-knowledge scheme to a computational zero-knowledge scheme

    Public Randomness Source (for transparency) 3.1.5.1 The Non-Interactive variant Non-interactive STARKs were proven to exist using the ROM model, which is performed using the traditional Fiat-Shamir heuristic [12] shown in our model ([Section sec. 1.5); but keep in mind that it reduces our perfect zero-knowledge scheme to a computational zero-knowledge sch...

  5. [5]

    This can be useful in very simple scenarios where we just want to check whether each element of a list lies within a given domain

    Domain-based constraints: each of the elements of the trace must satisfy a specific set-membership condition. This can be useful in very simple scenarios where we just want to check whether each element of a list lies within a given domain

  6. [6]

    probabilistic checks

    Polynomial-based constraints: this scenario is more realistic, and it considers the requirements that a normal program would have. They can be represented as polynomials, taking as input one or more execution states. We will elaborate on reducing these two scenarios to a 2POLY problem in the following subsections. 49 3 Universal VC Compilers NOTE: a singl...

  7. [7]

    In the given 2POLY problem this is not possible because the lists are given as is, but within the STARK context the polynomials actually relate to execution traces

    Compress the polynomials: to decrease d, we need to replace our lists with equivalent alternatives of lower degree. In the given 2POLY problem this is not possible because the lists are given as is, but within the STARK context the polynomials actually relate to execution traces. Each element of a trace can be anything, as long as it complies with the giv...

  8. [8]

    To do this, we can simply have the Prover give polynomial evaluations over a domain that is much larger than their degree, and this easily be obtained through interpolation

    Add Redundancy: to increase |D|, we need to increase the space from which we can pick our succinct queries. To do this, we can simply have the Prover give polynomial evaluations over a domain that is much larger than their degree, and this easily be obtained through interpolation. Since the second method can always be applied to our 2POLY problem, we can ...

Show all 106 references
  1. [9]

    hiding” property), which is useful for the Zero-Knowledge extension discussed later. This step is the “cut

    Commit the Prover commits to each possible evaluation of the interpolated polynomial on the required domain. Each evaluated point will be kept hidden by the Commit- ment Scheme (due to its “hiding” property), which is useful for the Zero-Knowledge extension discussed later. Th...

  2. [10]

    This step is the “choose” part of theCut&Choose technique

    Query the Verifier chooses one (or more) point(s) from the polynomial that he would like to query. This step is the “choose” part of theCut&Choose technique

  3. [11]

    argument compiler

    Reveal 56 3.1 zk-STARKs the Verifier opens the commitment for the requested points, revealing the requested evaluation; because a Commitment Scheme is “binding”, he will not be able to change the value of the evaluations that were committed in the first step (as the Verifier woul...

  4. [12]

    Existence and availability of cryptographic one-way Hash Functions

  5. [13]

    Validity of the Random Oracle Model (ROM) (only for the non-interactive variant)

  6. [14]

    Existence of a ZK Argument of Knowledge Statement (Section 3.1.2.2)

  7. [15]

    Babai, ‘Trading group theory for randomness’, inProceedings of the seventeenth annual acm symposium on theory of computing, 1985, pp

    L. Babai, ‘Trading group theory for randomness’, inProceedings of the seventeenth annual acm symposium on theory of computing, 1985, pp. 421–429

    1985

  8. [16]

    the input x)

    Deny Querying the Execution Trace: the Verifier is not allowed to perform queries from the execution trace’s original domain, as any of its values may contain traces of the original witness (i.e. the input x). Likewise, in Shamir’s scheme the first element of the evaluation list...

  9. [17]

    partial interpolation

    Introduce Randomness: the execution trace is extended with uniformly selected noise, equal to as many elements as the number of queries performed by the Verifier. This is performed because preventing the Verifier from querying the original domain of the execution trace is not su...

  10. [18]

    Reduce f to a polynomial f ′ of degree deg (f ′) = deg (f )/2

  11. [19]

    f ← f ′, go back to step 1 and repeat for log (d) steps

  12. [20]

    composition

    Check that f is of degree 0 In order to reduce f to f ′, we take advantage of a decomposition technique that shares similarities with the Berlekamp-Welch algorithm [67] for error correction of Reed-Solomon codes, and is exactly the same one used by the divide-et-impera Cooley-...

  13. [21]

    Backes, D

    M. Backes, D. Fiore, and R. M. Reischuk, ‘Verifiable delegation of computation on outsourced data’, in Proceedings of the 2013 acm sigsac conference on computer & communications security, 2013, pp. 863–874

    2013

  14. [22]

    del Castillo, ‘Big Blockchain: The 50 Largest Public Companies Exploring Block- chain’

    M. del Castillo, ‘Big Blockchain: The 50 Largest Public Companies Exploring Block- chain’. https://www.forbes.com/sites/michaeldelcastillo/2018/07/03/big-blockchain-the-50- largest-public-companies-exploring-blockchain/, 2018

    2018

  15. [23]

    Hackett, ‘Police Nab Alleged Boss Behind Bitcoin Pyramid Scheme Bitconnect’

    R. Hackett, ‘Police Nab Alleged Boss Behind Bitcoin Pyramid Scheme Bitconnect’. http://fortune.com/2018/08/20/bitcoin-scam-bitconnect-arrest/, 2018

    2018

  16. [24]

    https://ethresear.ch

    ‘Ethereum Research’. https://ethresear.ch

  17. [25]

    Goldwasser, S

    S. Goldwasser, S. Micali, and C. Rackoff, ‘The knowledge complexity of interactive proof systems’,SIAM Journal on computing, vol. 18, no. 1, pp. 186–208, 1989

    1989

  18. [26]

    Arora, C

    S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, ‘Proof verification and the hardness of approximation problems’,Journal of the ACM (JACM), vol. 45, no. 3, pp. 501–555, 1998

    1998

  19. [27]

    Arora and S

    S. Arora and S. Safra, ‘Probabilistic checking of proofs: A new characterization of np’, Journal of the ACM (JACM), vol. 45, no. 1, pp. 70–122, 1998

    1998

  20. [28]

    aszl o Babai, L

    L. aszl o Babai, L. Fortnow, L. Levin, and M. Szegedy, ‘Checking computations in polylogarithmic time’, in Proceedings of the 23rd annual acm symposium on theory of computing, 1991, pp. 21–31

    1991

  21. [29]

    in the head

    technique that we mentioned in the Intermediate Arithmetisation section. We will also be doing so efficiently through a succinct querying of each polynomial f (i), called “oracle” in the IOP model that FRI is based upon; this second part of FRI is called the query-phase. The ma...

  22. [30]

    Babai, L

    L. Babai, L. Fortnow, and C. Lund, ‘Non-deterministic exponential time has two- prover interactive protocols’,Computational complexity, vol. 1, no. 1, pp. 3–40, 1991

    1991

  23. [31]

    Ben-Sasson, A

    E. Ben-Sasson, A. Chiesa, and N. Spooner, ‘Interactive oracle proofs’, inTheory of cryptography, 2016, pp. 31–60

    2016

  24. [32]

    Quisquater et al., ‘How to explain zero-knowledge protocols to your children’, in Advances in cryptology — crypto’ 89 proceedings, 1990, pp

    J.-J. Quisquater et al., ‘How to explain zero-knowledge protocols to your children’, in Advances in cryptology — crypto’ 89 proceedings, 1990, pp. 628–631

    1990

  25. [33]

    Blum, ‘How to prove a theorem so no one else can claim it’, inProceedings of the international congress of mathematicians, 1986, vol

    M. Blum, ‘How to prove a theorem so no one else can claim it’, inProceedings of the international congress of mathematicians, 1986, vol. 1, p. 2

    1986

  26. [34]

    Fiat and A

    A. Fiat and A. Shamir, ‘How to prove yourself: Practical solutions to identification and signature problems’, in Conference on the theory and application of cryptographic techniques, 1986, pp. 186–194

    1986

  27. [35]

    Bellare and P

    M. Bellare and P. Rogaway, ‘Random oracles are practical: A paradigm for designing efficient protocols’, inProceedings of the 1st acm conference on computer and communica- tions security, 1993, pp. 62–73

    1993

  28. [36]

    fiat-shamir for proofs

    N. Bitansky et al., ‘Why “fiat-shamir for proofs” lacks a proof’, inTheory of crypto- graphy conference, 2013, pp. 182–201

    2013

  29. [37]

    Babai and S

    L. Babai and S. Moran, ‘Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes’,Journal of Computer and System Sciences, vol. 36, no. 2, pp. 254–276, 1988. 67 4 References & Bibliography

    1988

  30. [38]

    aszl o Babai, L

    L. aszl o Babai, L. Fortnow, L. Levin, and M. Szegedy, ‘Checking computations in polylogarithmic time’, inProceedings of the 23rd annual acm symposium on theory of computing, 1991, pp. 21–31

    1991

  31. [39]

    Johnson, D

    R. Johnson, D. Molnar, D. Song, and D. Wagner, ‘Homomorphic signature schemes’, in Cryptographers’ track at the rsa conference, 2002, pp. 244–262

    2002

  32. [40]

    Gennaro and D

    R. Gennaro and D. Wichs, ‘Fully homomorphic message authenticators’. Cryptology ePrint Archive, Report 2012/290, 2012

    2012

  33. [41]

    Fiore, A

    D. Fiore, A. Mitrokotsa, L. Nizzardo, and E. Pagnin, ‘Multi-key homomorphic authenticators’, inInternational conference on the theory and application of cryptology and information security, 2016, pp. 499–530

    2016

  34. [42]

    Sander, ‘Efficient accumulators without trapdoor extended abstract’, inInterna- tional conference on information and communications security, 1999, pp

    T. Sander, ‘Efficient accumulators without trapdoor extended abstract’, inInterna- tional conference on information and communications security, 1999, pp. 252–262

    1999

  35. [43]

    Schabhüser, D

    L. Schabhüser, D. Butin, and J. Buchmann, ‘Context hiding multi-key linearly homomorphic authenticators’, in Cryptographers’ track at the rsa conference, 2019, pp. 493–513

    2019

  36. [44]

    Bertoni, J

    G. Bertoni, J. Daemen, M. Peeters, and G. Assche, ‘The keccak reference’,Submission to NIST (Round 3), vol. 13, pp. 14–15, 2011

    2011

  37. [45]

    Boneh, J

    D. Boneh, J. Bonneau, B. Bünz, and B. Fisch, ‘Verifiable delay functions’, inAnnual international cryptology conference, 2018, pp. 757–788

    2018

  38. [46]

    Proof of All

    cryptocurrency implements, was actually based upon RSA Accumulators. • Attribute Based Encryption (ABE): such systems take advantage of user identit- ies to establish public key pairs, which offers the big advantage of being able to send a single message to a specific hierarchy...

  39. [47]

    R. L. Rivest, A. Shamir, and D. A. Wagner, ‘Time-lock puzzles and timed-release crypto’, Massachusetts Institute of Technology, Cambridge, MA, USA, 1996

    1996

  40. [48]

    R. C. Merkle, ‘Secure communications over insecure channels’,Commun. ACM, vol. 21, no. 4, pp. 294–299, Apr. 1978

    1978

  41. [49]

    A. K. Lenstra and B. Wesolowski, ‘A random zoo: Sloth, unicorn, and trx.’,IACR Cryptology ePrint Archive, vol. 2015, p. 366, 2015

    2015

  42. [50]

    Wesolowski, ‘Efficient verifiable delay functions.’,IACR Cryptology ePrint Archive, vol

    B. Wesolowski, ‘Efficient verifiable delay functions.’,IACR Cryptology ePrint Archive, vol. 2018, p. 623, 2018

    2018

  43. [51]

    Pietrzak, ‘Simple verifiable delay functions’, in10th innovations in theoretical computer science conference (itcs 2019), 2018

    K. Pietrzak, ‘Simple verifiable delay functions’, in10th innovations in theoretical computer science conference (itcs 2019), 2018

    2019

  44. [52]

    Boneh, B

    D. Boneh, B. Bünz, and B. Fisch, ‘A survey of two verifiable delay functions’. Crypto- logy ePrint Archive, Report 2018/712, 2018

    2018

  45. [53]

    Bellare and S

    M. Bellare and S. Goldwasser, ‘Encapsulated key escrow’. MIT Laboratory for Computer Science Technical Report, 1996

    1996

  46. [54]

    Bellare and S

    M. Bellare and S. Goldwasser, ‘Verifiable partial key escrow.’, inACM conference on computer and communications security, 1997, vol. 1997, pp. 78–91

    1997

  47. [55]

    Boneh and M

    D. Boneh and M. Naor, ‘Timed commitments’, inAnnual international cryptology conference, 2000, pp. 236–254

    2000

  48. [56]

    B. Bünz, S. Goldfeder, and J. Bonneau, ‘Proofs-of-delay and randomness beacons in ethereum’,IEEE Security and Privacy on the blockchain (IEEE S&B), 2017

    2017

  49. [57]

    Bonneau, J

    J. Bonneau, J. Clark, and S. Goldfeder, ‘On bitcoin as a public randomness source’. Cryptology ePrint Archive, Report 2015/1015, 2015

    2015

  50. [58]

    https: //github.com/mabbamOG/traplottery, 2018

    @mabbamOG, ‘TrapLottery 0.2: Automated Lottery on the Blockchain’. https: //github.com/mabbamOG/traplottery, 2018. 68

    2018

  51. [59]

    V. Trón, A. Fischer, D. Nagy, Z. Felföldi, and N. Johnson, ‘Swap, swear, and swindle: Incentive system for swarm’. Technical Report, Ethersphere, 2016. Ethersphere Orange Papers 1., 2016

    2016

  52. [60]

    Percival, ‘Stronger key derivation via sequential memory-hard functions’

    C. Percival, ‘Stronger key derivation via sequential memory-hard functions’. BSD- Can, 2009

    2009

  53. [61]

    Wood and others, ‘Ethereum: A secure decentralised generalised transaction ledger’,Ethereum project yellow paper, vol

    G. Wood and others, ‘Ethereum: A secure decentralised generalised transaction ledger’,Ethereum project yellow paper, vol. 151, pp. 1–32, 2014

    2014

  54. [62]

    Drake, ‘Minimal VDF randomness beacon’

    J. Drake, ‘Minimal VDF randomness beacon’. https://ethresear.ch/t/minimal-vdf- randomness-beacon/, 2018

    2018

  55. [63]

    M. O. Rabin, ‘Digitalized signatures and public-key functions as intractable as factorization’, Jan. 1979

    1979

  56. [64]

    A. C.-C. Yao, ‘How to generate and exchange secrets’, in27th annual symposium on foundations of computer science (sfcs 1986), 1986, pp. 162–167

    1986

  57. [65]

    Damgård, M

    I. Damgård, M. Geisler, M. Krøigaard, and J. B. Nielsen, ‘Asynchronous multi- party computation: Theory and implementation’, inInternational workshop on public key cryptography, 2009, pp. 160–179

    2009

  58. [66]

    Boneh and M

    D. Boneh and M. Franklin, ‘Efficient generation of shared rsa keys’, in Annual international cryptology conference, 1997, pp. 425–439

    1997

  59. [67]

    Hopwood, S

    D. Hopwood, S. Bowe, T. Hornby, and N. Wilcox, ‘Zcash protocol specification’,Tech. rep. 2016–1.10. Zerocoin Electric Coin Company, Tech. Rep., 2016

    2016

  60. [68]

    Buchmann and H

    J. Buchmann and H. C. Williams, ‘A key-exchange system based on imaginary quadratic fields’,Journal of Cryptology, vol. 1, no. 2, pp. 107–118, Jun. 1988

    1988

  61. [69]

    Biehl, J

    I. Biehl, J. Buchmann, S. Hamdy, and A. Meyer, ‘A signature scheme based on the intractability of computing roots’,Designs, Codes and Cryptography, vol. 25, no. 3, pp. 223–236, 2002

    2002

  62. [70]

    Benhamouda, S

    F. Benhamouda, S. Krenn, V. Lyubashevsky, and K. Pietrzak, ‘Efficient zero- knowledge proofs for commitments from learning with errors over rings’, in European symposium on research in computer security, 2015, pp. 305–325

    2015

  63. [71]

    Derler, C

    D. Derler, C. Hanser, and D. Slamanig, ‘Revisiting cryptographic accumulators, additional properties and relations to other primitives’, inCryptographers’ track at the rsa conference, 2015, pp. 127–144

    2015

  64. [72]

    Ben-Sasson, I

    E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, ‘Scalable, transparent, and post-quantum secure computational integrity’. Cryptology ePrint Archive, Report 2018/046, 2018

    2018

  65. [73]

    https://github.com/ elibensasson/libSTARK, 2018

    @elibensasson, ‘libSTARK: a C++ library for zk-STARK systems’. https://github.com/ elibensasson/libSTARK, 2018

    2018

  66. [74]

    Preneel, R

    B. Preneel, R. Govaerts, and J. Vandewalle, ‘Hash functions based on block ciphers: A synthetic approach’, inAnnual international cryptology conference, 1993, pp. 368–378

    1993

  67. [75]

    Ben-Sasson, A

    E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza, ‘TinyRAM architec- ture specification, v0. 991’. 2013

    2013

  68. [76]

    J. T. Schwartz, ‘Probabilistic algorithms for verification of polynomial identities’, in International symposium on symbolic and algebraic manipulation, 1979, pp. 200–215. 69 4 References & Bibliography

    1979

  69. [77]

    Zippel, ‘Probabilistic algorithms for sparse polynomials’, inInternational sym- posium on symbolic and algebraic manipulation, 1979, pp

    R. Zippel, ‘Probabilistic algorithms for sparse polynomials’, inInternational sym- posium on symbolic and algebraic manipulation, 1979, pp. 216–226

    1979

  70. [78]

    R. A. DeMillo and R. J. Lipton, ‘A probabilistic remark on algebraic program testing.’, GEORGIA INST OF TECH ATLANTA SCHOOL OF INFORMATION AND COMPUTER SCIENCE, 1977

    1977

  71. [79]

    Lin, W.-H

    S.-J. Lin, W.-H. Chung, and Y. S. Han, ‘Novel polynomial basis and its application to reed-solomon erasure codes’, in 2014 ieee 55th annual symposium on foundations of computer science, 2014, pp. 316–325

    2014

  72. [80]

    Kilian, ‘A note on efficient zero-knowledge proofs and arguments’, inProceedings of the twenty-fourth annual acm symposium on theory of computing, 1992, pp

    J. Kilian, ‘A note on efficient zero-knowledge proofs and arguments’, inProceedings of the twenty-fourth annual acm symposium on theory of computing, 1992, pp. 723–732

    1992

  73. [81]

    Micali, ‘Computationally sound proofs’,SIAM Journal on Computing, vol

    S. Micali, ‘Computationally sound proofs’,SIAM Journal on Computing, vol. 30, no. 4, pp. 1253–1298, 2000

    2000

  74. [82]

    R. C. Merkle, ‘A digital signature based on a conventional encryption function’, in Conference on the theory and application of cryptographic techniques, 1987, pp. 369–378

    1987

  75. [83]

    I. S. Reed and G. Solomon, ‘Polynomial codes over certain finite fields’,Journal of the society for industrial and applied mathematics, vol. 8, no. 2, pp. 300–304, 1960

    1960

  76. [84]

    Shamir, ‘How to share a secret’,Communications of the ACM, vol

    A. Shamir, ‘How to share a secret’,Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979

    1979

  77. [85]

    Ben-Sasson, I

    E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev, ‘Fast reed-solomon interactive oracle proofs of proximity’, in45th international colloquium on automata, languages, and programming (icalp 2018), 2018

    2018

  78. [86]

    Ben-Sasson, L

    E. Ben-Sasson, L. Goldberg, S. Kopparty, and S. Saraf, ‘DEEP-fri: Sampling outside the box improves soundness’,arXiv preprint arXiv:1903.12243, 2019

    1903 arXiv

  79. [87]

    Rubinfeld and M

    R. Rubinfeld and M. Sudan, ‘Robust characterizations of polynomials with applic- ations to program testing’, SIAM Journal on Computing , vol. 25, no. 2, pp. 252–271, 1996

    1996

  80. [88]

    L. R. Welch and E. R. Berlekamp, ‘Error correction for algebraic block codes’. Google Patents, 1986

    1986

  81. [89]

    J. W. Cooley and J. W. Tukey, ‘An algorithm for the machine calculation of complex fourier series’,Mathematics of computation, vol. 19, no. 90, pp. 297–301, 1965

    1965

  82. [90]

    Giacomelli, J

    I. Giacomelli, J. Madsen, and C. Orlandi, ‘Zkboo: Faster zero-knowledge for boolean circuits’, in25th {usenix} security symposium ({usenix} security 16), 2016, pp. 1069–1083

    2016

  83. [91]

    M. Chase et al., ‘Post-quantum zero-knowledge and signatures from symmetric-key primitives’, inProceedings of the 2017 acm sigsac conference on computer and communica- tions security, 2017, pp. 1825–1842

    2017

  84. [92]

    S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam, ‘Ligero: Lightweight sublinear arguments without a trusted setup’, in Proceedings of the 2017 acm sigsac conference on computer and communications security, 2017, pp. 2087–2104

    2017

  85. [93]

    Bitansky, R

    N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer, ‘From extractable collision resist- ance to succinct non-interactive arguments of knowledge, and back again’, inProceedings of the 3rd innovations in theoretical computer science conference, 2012, pp. 326–349

    2012

  86. [94]

    Gentry and D

    C. Gentry and D. Wichs, ‘Separating succinct non-interactive arguments from all falsifiable assumptions’, inProceedings of the forty-third annual acm symposium on theory of computing, 2011, pp. 99–108. 70

    2011

  87. [95]

    Costelloet al., ‘Geppetto: Versatile verifiable computation’, in2015 ieee symposium on security and privacy, 2015, pp

    C. Costelloet al., ‘Geppetto: Versatile verifiable computation’, in2015 ieee symposium on security and privacy, 2015, pp. 253–270

    2015

  88. [96]

    Parno, J

    B. Parno, J. Howell, C. Gentry, and M. Raykova, ‘Pinocchio: Nearly practical verifiable computation’, in2013 ieee symposium on security and privacy, 2013, pp. 238–252

    2013

  89. [97]

    Groth, ‘On the size of pairing-based non-interactive arguments’, in Annual international conference on the theory and applications of cryptographic techniques, 2016, pp

    J. Groth, ‘On the size of pairing-based non-interactive arguments’, in Annual international conference on the theory and applications of cryptographic techniques, 2016, pp. 305–326

    2016

  90. [98]

    Ben-Sasson, A

    E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, and M. Virza, ‘SNARKs for c: Verifying program executions succinctly and in zero knowledge’, in Annual cryptology conference, 2013, pp. 90–108

    2013

  91. [99]

    Ben-Sasson, A

    E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward, ‘Aurora: Transparent succinct arguments for r1cs’, inAnnual international conference on the theory and applications of cryptographic techniques, 2019, pp. 103–128

    2019

  92. [100]

    Maller, S

    M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn, ‘Sonic: Zero-knowledge snarks from linear-size universal and updateable structured reference strings’. Cryptology ePrint Archive, Report 2019/099, 2019

    2019

  93. [101]

    T. Xie, J. Zhang, Y. Zhang, C. Papamanthou, and D. Song, ‘Libra: Succinct zero- knowledge proofs with optimal prover computation.’,IACR Cryptology ePrint Archive, vol. 2019, p. 317, 2019

    2019

  94. [102]

    Goldwasser, Y

    S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, ‘Delegating computation: Interactive proofs for muggles’,Journal of the ACM (JACM), vol. 62, no. 4, p. 27, 2015

    2015

  95. [103]

    R. S. Wahby, I. Tzialla, abhi shelat, J. Thaler, and M. Walfish, ‘Doubly-efficient zkSNARKs without trusted setup’. Cryptology ePrint Archive, Report 2017/1132, 2017

    2017

  96. [104]

    B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, ‘Bulletproofs: Short proofs for confidential transactions and more’, in2018 ieee symposium on security and privacy (sp), 2018, pp. 315–334

    2018

  97. [105]

    Van Saberhagen, ‘CryptoNote v 2.0’

    N. Van Saberhagen, ‘CryptoNote v 2.0’. 2013

    2013

  98. [106]

    S. Bowe, A. Chiesa, M. Green, I. Miers, P. Mishra, and H. Wu, ‘Zexe: Enabling decentralized private computation’,IACR ePrint, vol. 962, 2018. 71

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.