Protocol Labs Research
A finality calculator for Filecoin’s Expected Consensus
We propose a finality calculator for Filecoin’s Expected consensus that considers what takes place during epochs and can attain, under normal operating conditions, an error probability of 2^(−30) in 30 epochs (15 minutes) - a 30x improvement over the current 900-epoch threshold.
Filecoin Proof of Useful Space
This document provides a simple formal definition of Proof of Space (taken from the academic literature) and an informal definition of persistent and useful space (needed for Filecoin). It describes construction details and a security proof for the Stacked-DRGs proof of space (SDR), and goes into how SDR is used in Filecoin.
SpaceVDF: Verifiable delay functions using cryptographic satellites
In this document we aim to evaluate how VDF algorithms based on physical limits can be implemented in satellites and which physical properties / or roles of physics we can utilize to guarantee the passage of time.
Yonatan Winetraub, Elad Sagi, Yan Michalevsky, Chhi'mèd Künzang , Jonathan Gross
LURK: Lambda, the ultimate recursive knowledge
We introduce Lurk, a new LISP-based programming language for zk-SNARKs. Traditional approaches to programming over zero-knowledge proofs require compiling the desired computation into a flat circuit, imposing serious constraints on the size and complexity of computations that can be achieved in practice.
Nada Amin, John Burnham, François Garillot, Rosario Gennaro , Chhi'mèd Künzang , Daniel Rogozin, Cameron Wong
tlock: Practical timelock encryption from threshold BLS
We present a practical construction and implementation of timelock encryption, in which a ciphertext is guaranteed to be decryptable only after some specified time has passed. We employ an existing threshold network, the League of Entropy, implementing threshold BLS [BLS01, B03] in the context of Boneh and Franklin’s identity-based encryption (IBE).
Nicolas Gailly , Kelsey Melissaris, Yolan Romailler
Structure-preserving compilers from new notions of obfuscations
The dream of software obfuscation is to take programs, as they are, and then compile them into obfuscated versions that hide their secret inner workings. In this work we investigate notions of obfuscations weaker than virtual black-box (VBB) but which still allow obfuscating cryptographic primitives preserving their original functionalities as much as possible.
Matteo Campanelli , Danilo Francati, Claudio Orlandi
Impossibilities in succinct arguments: Black-box extraction and more
The celebrated result by Gentry and Wichs established a theoretical barrier for succinct non-interactive arguments (SNARGs), showing that for (expressive enough) hard-on-average languages we must assume non-falsifiable assumptions. We further investigate those barriers by showing new negative and positive results related to extractability and to the preprocessing model.
Matteo Campanelli , Chaya Ganesh, Hamidreza Khoshakhlagh, Janno Siim
Curve trees: Practical and transparent zero-knowledge accumulators
In this work we propose a new accumulator construction and efficient ways to prove knowledge of some element in a set without leaking anything about the element. This problem arises in several applications including privacy-preserving distributed ledgers (e.
Matteo Campanelli , Mathias Hall-Andersen
2022-07-06 / Report
Caulk: Lookup arguments in sublinear time
We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or m values that comprise commitment cm all belong to the vector of size N committed to in C.
Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu , Mark Simkin
2022-07-06 / Report
Linear-map vector commitments and their practical applications
Vector commitments (VC) are a cryptographic primitive that allow one to commit to a vector and then “open” some of its positions efficiently. Vector commitments are increasingly recognized as a central tool to scale highly decentralized networks of large size and whose content is dynamic.
Matteo Campanelli , Anca Nitulescu , Carla Ràfols, Alexandros Zacharakis, Arantxa Zapico
On the impossibility of algebraic vector commitments in pairing-free groups
Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, algebraic constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes.
Dario Catalano , Dario Fiore, Rosario Gennaro , Emmanuele Giunta
2022-04-08 / Report
Witness-authenticated key exchange revisited: Improved models, simpler constructions, extensions to groups
We revisit the notion of Witness Authenticated Key Exchange (WAKE) where a party can be authenticated through a generic witness to an NP statement. We point out shortcomings of previous definitions, protocols and security proofs in Ngo et al.
Rinocchio: SNARKs for ring arithmetic
Succinct non-interactive arguments of knowledge (SNARKs) enable non-interactive efficient verification of NP computations and admit short proofs. However, all current SNARK constructions assume that the statements to be proven can be efficiently represented as either Boolean or arithmetic circuits over finite fields.
Chaya Ganesh, Anca Nitulescu , Eduardo Soria-Vazquez
Accelerating content routing with Bitswap: A multi-path file transfer protocol in IPFS and Filecoin
Bitswap is a Block Exchange protocol designed for P2P Content Addressable Networks. It leverages merkle-linked graphs in order to parallelize retrieval and verify content integrity. Bitswap is being used in the InterPlanetary File System architecture as the main content exchange protocol, as well as in the Filecoin network as part of the block synchronisation protocol.
2020-12-05 / Conference paper
Incrementally aggregatable vector commitment techniques and applications to verifiable decentralized storage
Vector commitments with subvector openings (SVC) [Lai-Malavolta, Boneh-Bunz-Fisch; CRYPTO’19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector’s length and the number of opened positions.
Advances in Cryptology – ASIACRYPT 2020 / 2020.12.05
Matteo Campanelli , Dario Fiore, Nicola Greco , Dimitris Kolonelos, Luca Nizzardo
Engineering Filecoin’s economy
As a novel data storage and distribution network, the Filecoin Network’s mission is to create a decentralized, efficient, and robust foundation for humanity’s information. This mission will be advanced by incentivizing consistent growth and development of the Filecoin Network’s economy.
Protocol Labs
GossipSub: Attack-resilient message propagation in the Filecoin and ETH2.0 networks
Permissionless blockchain environments necessitate the use of a fast and attack-resilient message propagation protocol for Block and Transaction messages to keep nodes synchronised and avoid forks. We present GossipSub, a gossip-based pubsub protocol, which, in contrast to past pubsub protocols, incorporates resilience against a wide spectrum of attacks.
Dimitris Vyzovitis, Yusef Napora, Dirk McCormick, David Dias , Yiannis Psaras
Gossipsub-v1.1 evaluation report
Permissionless blockchain environments necessitate the use of a fast and attack-resilient message propagation protocol for Block and Transaction messages to keep nodes synchronised and avoid forks. We present GossipSub, a gossip-based pubsub protocol, which, in contrast to past pubsub protocols, incorporates resilience against a wide spectrum of attacks.
Dimitris Vyzovitis, Yusef Napora, Dirk McCormick, David Dias , Yiannis Psaras
Exploring connections between active learning and model extraction
Machine learning is being increasingly used by individuals, research institutions, and corporations. This has resulted in the surge of Machine Learning-as-a-Service (MLaaS) - cloud services that provide (a) tools and resources to learn the model, and (b) a user-friendly query interface to access the model.
Varun Chandrasekaran, Kamalika Chaudhuri, Irene Giacomelli , Somesh Jha, Songbai Yan
U.S. energy policy and market design
The U.S. bulk power system has an enormous number of actors: regulatory agencies (local, state, and federal), utilities (investor-owned, municipal, cooperatives, and power marketing administrations), operators (ISOs and RTOs), and customers.
AuroraLight: Improved prover efficiency and SRS size in a Sonic-like system
Using ideas from the recent Aurora zk-STARK of Ben-Sasson et al. [BCR + 19], we present a zk-SNARK with a universal and updatable SRS similar to the recent construction of Maller et al.
Microgrids are local installations typically connecting one or multiple generation sources with some set of loads. They range in size, from tiny off-grid solar home systems (SHSs) to power infrastructure spanning a university campus or military base.
Scaling proof-of-replication for Filecoin mining
A proof-of-replication (PoRep) is a proof system that a server can use to demonstrate to a network in a publicly verifiable way that it is dedicating unique resources to storing one or more replicas of a data file.
Smart grid pilot projects
There are thousands of smart grid pilot projects all around the world, having begun largely in the early 2000s. With the introduction of blockchain, and with the grid becoming more unpredictable and decentralized, several use cases are becoming apparent for blockchain.
Price signals and demand-side management in the electric distribution and retail system
This report focuses on power distribution and retail — the ‘last few miles’ of electricity delivery — because this portion of the power grid in particular must be transformed if we are to decarbonize our energy system.
Energy pricing
This first report focuses on the mechanisms by which electricity is priced in today’s power markets. Existing energy markets govern the infrastructure that any widely-used trading protocol must interface with in the short and medium terms.
PoReps: Proofs of space on useful data
A proof-of-replication (PoRep) is an interactive proof system in which a prover defends a publicly verifiable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data file.
Power fault tolerance
Byzantine Fault Tolerance (BFT) accounts for faults as the number of faulty nodes and is thus cumbersome to apply to many modern decentralized systems. We introduce the Power Fault Tolerance (PFT) model, which reframes BFT in terms of participants' influence over the outcome of a protocol, instead of the number of nodes.
Protocol Labs
Proof of replication
We introduce Proof-of-Replication (PoRep), a new kind of Proof-of-Storage, that can be used to prove that some data D has been replicated to its own uniquely dedicated physical storage. Enforcing unique physical copies enables a verifier to check that a prover is not deduplicating multiple copies of D into the same storage space.
Filecoin: A decentralized storage network
The internet is in the middle of a revolution: centralized proprietary services are being replaced with decentralized open ones; trusted parties replaced with verifiable computation; brittle location addresses replaced with resilient content addresses; inefficient monolithic services replaced with peer-to-peer algo-rithmic markets.
Protocol Labs
Filecoin: A cryptocurrency operated file storage network
Filecoin is a distributed electronic currency similar to Bitcoin. Unlike Bitcoin’s computation-only proof-of-work, Filecoin’s proof-of-work function includes a proof-of-retrievability component, which requires nodes to prove they store a particular file. The Filecoin network forms an entirely distributed file storage system, whose nodes are incentivized to store as much of the entire network’s data as they can.
Protocol Labs
IPFS - Content addressed, versioned, P2P file system
The InterPlanetary File System (IPFS) is a peer-to-peer distributed file system that seeks to connect all computing devices with the same system of files. In some ways, IPFS is similar to the Web, but IPFS could be seen as a single BitTorrent swarm, exchanging objects within one Git repository.