Grantees: Danilo Francati, Qiang Tang (U. Sydney), Giuseppe Ateniese (GMU), Dimitris Papadopoulos (HKUST)
Institutions: University of Sydney, GMU, HKUST
Description: Verifiable capacity bound function (VCBF) was recently proposed as a space analog of verifiable delay function. In particular, a VCBF imposes a lower bound on the number of bits read from memory during evaluation (referred to as minimum capacity). No adversary, even unbounded, should produce an output without spending this minimum memory capacity. Moreover, a VCBF allows for an efficient public verification process: Given a proof-of-correctness, checking the validity of the output takes significantly fewer memory resources, sublinear in the target minimum capacity. Finally, it achieves soundness, i.e., no computationally bounded adversary can produce a proof that passes verification for a false output. Despite showing potentials for applications due to the strict enforcement of “energy cost” during function evaluation (and analyzed via the tool of Kolmogorov complexity), VCBF is still at its very beginning, several drawbacks remain, here we list two:
(1) Current VCBF construction is secure in a “restricted model” that the adversary reads only constant blocks. This is only a theoretical cornerstone for a construction eventually in the model that allows the adversary to “adaptively” decide which bits to read.
(2) Directly applying VCBF to proofof-space (PoS), by replacing the hash might not work, as VCBF in its current form does not support proportional capacity growth during parallel evaluations
Status: end date Oct 2022