Date & Time:
October 25, 2024 1:30 pm – 2:30 pm
Location:
Crerar 346, 5730 S. Ellis Ave., Chicago, IL,
10/25/2024 01:30 PM 10/25/2024 02:30 PM America/Chicago Leonid Reyzin (Boston University)- Proofs of Space with Maximal Hardness Crerar 346, 5730 S. Ellis Ave., Chicago, IL,

Abstract: In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases even a portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier.

In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (vanishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019) that requires extremely depth-robust graphs, which result in impractically high complexity of the initialization process.

We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space. Our construction is a generalization of an existing construction called SDR (Fisch, Eurocrypt 2019) deployed on the Filecoin blockchain. Our improvements, while general, also demonstrate that the already deployed construction has considerably better security than previously shown.

Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every set of $\pi \cdot n$ nodes contains a subset of $\alpha_\pi \cdot n$ nodes whose induced subgraph has just one sink. We take a predecessor-robust graph with constant parameters $(\pi, \alpha_\pi)$, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small additive constant.

Speakers

Leonid Reyzin

Professor of Computer Science, Boston University

Related News & Events

simulated Roblox chat
UChicago CS News

Helping Elementary School Children Learn About Digital Privacy and Security With Micro-Lessons

Mar 25, 2025
grant ho writing on white board
UChicago CS News

New Study Reveals Gaps in Common Types of Cybersecurity Training

Mar 24, 2025
headshot
UChicago CS News

Jasmine Lu on Sustainable Computing: Rethinking E-Waste and Innovation

Mar 18, 2025
Pedro giving speech
UChicago CS News

Pedro Lopes Honored with 2025 IEEE VGTC Virtual Reality Significant New Researcher Award

Mar 13, 2025
ai generated network traffic
UChicago CS News

University of Chicago Researchers Revolutionize Network Traffic Generation with AI Breakthrough

Mar 12, 2025
UChicago CS News

Federal budget cuts threaten to decimate America’s AI superiority—and other countries are watching

Feb 25, 2025
Netflix logo on phone screen
UChicago CS News

The Hidden Cost of Netflix’s Autoplay: A Study on Viewing Patterns and User Control

Feb 25, 2025
Raul Castro Fernandez
UChicago CS News

Raul Castro Fernandez among six UChicago scientists awarded prestigious Sloan Fellowships in 2025

Feb 18, 2025
UChicago CS News

Quantum Leap: New Research Reveals Secrets of Random Quantum Circuits

Feb 04, 2025
UChicago CS News

Fred Chong from the Department of Computer Science Named ACM Fellow for Contributions to Quantum Computing

Jan 22, 2025
UChicago CS News

Rethinking AI as a Thought Partner: Perspectives on Writing, Programming, and More

Jan 16, 2025
UChicago CS News

UChicago Partners On New National Science Foundation Large-Scale Research Infrastructure For Education

Dec 10, 2024
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube