Protocol Labs announces first recipients of grant program

Protocol Labs, a research, development, and deployment institution for improving Internet technology, has announced its first grant recipients. Last year, Protocol Labs launched a grant program, through which it would fund cutting-edge research endeavors relevant to its mission.

The first few Requests for Proposals (RFPs) focused on problems the team discovered and formulated while designing and building Filecoin and IPFS. In two months, the Protocol Labs team received 11 proposals in response to their five RFPs, as well as additional proposals addressing other exciting research problems.

The Protocol Labs team said, “Although there were many ambitious and promising directions proposed, we had to prioritize the works most strongly aligned with our project objectives and applied rigorous evaluation criteria. We chose to award five grants to proposals addressing our RFPs in mid-2018 with a total amount in excess of $300,000.”

Grant Recipients: 

• Claudio Orlandi, Dr. Chaya Ganesh, and Prof. Ivan Damgard
  For their prior and continuing work on Proofs-of-Replication.
• Giuseppe Ateniese, Dr. Mohammad Etemad, and Prof. Qiang Tang
  A Proof-of-Spacetime requires a prover P to convince a verifier V that certain outsourced data are not only properly stored/replicated but also stored for a given number of time slots. Trivial solutions that require P and V to periodically execute a proof-of-storage protocol cause large communication overhead, whereas sequentially producing all the verifier challenges from a seed (to reduce the number of proof-of-storage protocol invocations) may be vulnerable to prover pre-computation and/or prover outsourcing attacks. To address the above challenges, the plan is to leverage recently proposed proof-of-delay functions, probabilistic proof checking, and algebraic properties to aggregate the proofs such that the verifier can be convinced that the data is indeed properly stored at the end of each time slot and the total proof size will still be sublinear in the number of time slots.
• Dario Fiore and Dr. Matteo Campanelli
  Proofs-of-Spacetime (PoSt) allows a user to show she has been storing a file for a certain amount of time. They are an important building block of the FileCoin protocol. Current constructions for PoST are based on the following paradigm: iterate a Proof-of-Replication (PoRep) and prove that all the repetitions are correct through a SNARK system. Unfortunately, applying even a state-of-the-art general-purpose SNARK would result in PoST with impractical performances on the prover’s side. Our project aims to obtain fast PoSTs by developing new SNARKs that are specially tailored to Proofs-of-Replication and their iteration. This methodology is part of a larger project that aims to build a framework for “composable proofs” where SNARKs tailored to specific computations can be linked efficiently through a Commit & Prove methodology.
• Ethan Cecchetti, Dr. Ian Miers, and Prof. Ari Juels, in collaboration with Ben Fisch
  The team proposes to construct efficient, provably secure PoReps by combining Depth-Robust Graphs (DRGs) with Butterfly Hourglass Functions (BHFs) (and other graphs in a more general class). DRGs are DAGs that contain a long path even when a fraction of nodes is removed. BHFs are DAG-based file transformations that achieve a goal similar to PoReps: They ensure that an economically rational adversary will store only an encoded file (e.g., one encrypted using a key managed by the adversary) rather than an unencoded version. BHFs have two important properties: every output depends upon every input and recomputation of outputs cannot be significantly accelerated by storing distinguished points. They do not provide security, however, against an adversary with arbitrary parallelism in block retrievals. Our key observation is that, by combining the two types of graphs in a multilayered construction, it is possible to obtain a file encoding that has zero file expansion and that requires an adversarial file holder to perform long sequential computations to reconstruct encoded file blocks it has failed to store. By generalizing the described construction, our intention is to provide the community with a family of practical, easy-to-implement cryptographic primitives that can be used in PoRePs and other applications.
• Victor Grishchenko, Oleg Lebedev, Yuri Syrovetskiy and Nikita Prokopov
  CRDT is a data replication/synchronization technology that needs no central “master” replica. As such, it is often considered an essential building block for distributed/decentralized systems. While the core principles of CRDT are clear, there is certainly a gap between theory and practice. Our research addresses the gap by focusing on the following topics: 1. log-structured (aka operational) CRDTs that can “switch gears” between op-based, patch-based, and state-based modes of operation (corresponding to real-time sync, periodic sync and full reconciliation); 2. minimizing metadata overhead by employing chain structures, achieving an effect similar to the block-based approach but retaining a simple core model; 3. a formal ACID 2.0 (associative, commutative, idempotent, distributed) framework to mix different RDTs in the same environment; 4. unifying Causal and Merkle structures (CRDTs and a common blockchain primitive). That work is divided into three layers: an op-based formal data model and protocol (Replicated Object Notation), replicated data types (RDTs) based on the RON model, and, on top of that, the (database) replication part. For each of the layers, we provide a formal specification, algorithms with pragmatic complexity bounds, and a reference implementation. Overall, the aim of our work is to make CRDTs a simple universal instrument within the reach of every developer.

Current RFPs can be found at https://github.com/protocol/research-RFPs.