Ling Ren: Proof of Space from Stacked Expanders

Speaker: Ling Ren, MIT

Date: Friday, October 21, 2016

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: Hewlett, G882, Gates Tower

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Goodwin, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Ling Ren: Proof of Space from Stacked Expanders

Abstract: Recently, proof of space (PoS) has been suggested as a more egalitarian alternative to the traditional hash-based proof of work. In PoS, a prover proves to a verifier that it has dedicated some specified amount of space. A closely related notion is memory-hard functions (MHF), functions that require a lot of memory/space to compute. While making promising progress, existing PoS and MHF have several problems. First, there are large gaps between the desired space-hardness and what can be proven. Second, it has been pointed out that PoS and MHF should require a lot of space not just at some point, but throughout the entire computation/protocol; few proposals considered this issue. Third, the two existing PoS constructions are both based on a class of graphs called superconcentrators, which are either hard to construct or add a logarithmic factor overhead to efficiency. In this paper, we construct PoS from stacked expander graphs. Our constructions are simpler, more efficient and have tighter provable space-hardness than prior works. Our results also apply to a recent MHF called Balloon hash. We show Balloon hash has tighter space-hardness than previously believed and consistent space-hardness throughout its computation.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2016.

Created by Deborah Goodwin Email at Monday, September 12, 2016 at 7:10 AM.