Award Abstract # 1518899
TWC: Large: Collaborative: The Science and Applications of Crypto-Currency

NSF Org: CNS
Division Of Computer and Network Systems
Recipient: REGENTS OF THE UNIVERSITY OF CALIFORNIA, THE
Initial Amendment Date: June 29, 2015
Latest Amendment Date: July 14, 2017
Award Number: 1518899
Award Instrument: Continuing Grant
Program Manager: Nina Amla
namla@nsf.gov
 (703)292-7991
CNS
 Division Of Computer and Network Systems
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: July 1, 2015
End Date: June 30, 2020 (Estimated)
Total Intended Award Amount: $540,000.00
Total Awarded Amount to Date: $540,000.00
Funds Obligated to Date: FY 2015 = $180,000.00
FY 2016 = $180,000.00

FY 2017 = $180,000.00
History of Investigator:
  • Dawn Song (Principal Investigator)
    dawnsong@cs.berkeley.edu
Recipient Sponsored Research Office: University of California-Berkeley
1608 4TH ST STE 201
BERKELEY
CA  US  94710-1749
(510)643-3891
Sponsor Congressional District: 12
Primary Place of Performance: University of California- Berkeley
675 Soda Hall
Berkeley
CA  US  94720-1776
Primary Place of Performance
Congressional District:
12
Unique Entity Identifier (UEI): GS3YEVSS12N6
Parent UEI:
NSF Program(s): Secure &Trustworthy Cyberspace
Primary Program Source: 01001516DB NSF RESEARCH & RELATED ACTIVIT
01001617DB NSF RESEARCH & RELATED ACTIVIT

01001718DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7434, 7925
Program Element Code(s): 806000
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

Crypto-currencies and smart contracts are a new wave of disruptive technology that will shape the future of money and financial transactions. Today, crypto-currencies are a billion-dollar market, and hundreds of companies are entering this space, promising exciting new markets and eco-systems. Unfortunately, usage of crypto-currencies outstrips our understanding. Currently most crypto currencies rely on heuristic designs without a solid appreciation of the necessary security properties, or any formal basis upon which strong assurance of such properties might be achieved.

This work aims to establish a rigorous scientific foundation for crypto-currencies. To achieve this, this work blends cryptography, game theory, programming languages, and systems security techniques. Expected outcomes include new crypto-currency designs with provable security properties, financially enforceable cryptographic protocols whose security properties are backed by enforceable payments in case of a breach, smart contract systems that are easy to program and formally verifiable, as well as high-assurance systems for storing and handling high-value crypto-currencies and transactions. The project will provide solutions to some of the most difficult and important technical questions surrounding the current digital-money revolution. The investigators will organize a crypto-currency speaker series that will bring together technologists, economists, social scientists, and policy-makers to foster collaborations that will shape the future of digital currencies.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gun Sirer, Dawn Song, Roger Wattenhofer "On Scaling Decentralized Blockchains (A Position Paper)" 3rd Workshop on Bitcoin and Blockchain Research , 2016
Mitar Milutinovic, Warren He, Howard Wu, and Maxinder Kanwal "Proof of Luck: an Efficient Blockchain Consensus Protocol" 1st Workshop on System Software for Trusted Execution (SysTEX 2016) , 2016 10.1145/3007788.3007790
Phuc C. Nguyen, Sam Tobin-Hochstadt, David Van Horn "Higher order symbolic execution for contract verification and refutation" J. Funct. Program. , 2017

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

We present 4 main outcomes of the project during the last reporting period.

First, we present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both O(dlogC) for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features a one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 s to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.

Then, we present a new succinct zero knowledge argument scheme for layered arithmetic circuits without trusted setup. The prover time is O (C+ n log n) and the proof size is O (D log C+ log2 n) for a D-depth circuit with n inputs and C gates. The verification time is also succinct, O (D log C+ log2 n), if the circuit is structured. Our scheme only uses lightweight cryptographic primitives such as collision-resistant hash functions and is plausibly post-quantum secure. We implement a zero knowledge argument system, Virgo, based on our new scheme and compare its performance to existing schemes. Experiments show that it only takes 53 seconds to generate a proof for a circuit computing a Merkle tree with 256 leaves, at least an order of magnitude faster than all other succinct zero knowledge argument schemes. The verification time is 50ms, and the proof size is 253KB, both competitive to existing systems. Underlying Virgo is a new transparent zero knowledge verifiable polynomial delegation scheme with logarithmic proof size and verification time. The scheme is in the interactive oracle proof model and may be of independent interest.

After Virgo, We introduce CHURP (CHUrn-Robust Proactive secret sharing). CHURP enables secure secret-sharing in dynamic settings, where the committee of nodes storing a secret changes over time. Designed for blockchains, CHURP has lower communication complexity than previous schemes: $O(n)$ on-chain and $O(n^2)$ off-chain in the optimistic case of no node failures. CHURP includes several technical innovations: An efficient new proactivization scheme of independent interest, a technique (using asymmetric bivariate polynomials) for efficiently changing secret-sharing thresholds, and a hedge against setup failures in an efficient polynomial commitment scheme. We also introduce a general new technique for inexpensive off-chain communication across the peer-to-peer networks of permissionless blockchains. We formally prove the security of CHURP, report on an implementation, and present performance measurements.

Finally we present PRIVGUARD, a new framework for automatic compliance checking of data privacy regulations in heterogeneous data processing infrastructures. Our key insight is to pair up a data subject’s data with a policy governing how the data is processed. Specified in our formal policy language: PRIVPOLICY, the policy is created and provided by the data subject alongside the data, and is associated with the data throughout the life-cycle of data processing (e.g., data transformation by data processing systems, data aggregation of multiple data subjects’ data). We introduce a solution for static enforcement of privacy policies based on the concept of residual policies, and present a novel algorithm based on abstract interpretation for deriving residual policies in PRIVPOLICY.

 

 


Last Modified: 09/14/2020
Modified by: Dawn Song

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page