Collaborative Research:CNS Core:Medium:Unlinking the (Block)chain:Scalable Byzantine-Tolerant Databases.

This project proposes a new architecture for enabling safe and secure data sharing among mutually distrustful parties. Blockchains are today the platform of choice for such needs. They offer the appealing abstraction of a shared, totally-ordered, tamper-resistant log of operations, implemented via a distributed protocol run by a collection of computing nodes, each replicating the entire state of the log.

While the details of these protocols vary for different blockchain implementations, they all rely on an underlying architecture that suffers from two key limitations. First, it predicates correctness and integrity on an execution model where replicas process operations sequentially, according to the same total order; this quickly becomes a performance bottleneck.

Second, it complicates deployment. The need for all replicas store the full body of data stored in the blockchain is not only resource intensive, but can be legally problematic: GDPR laws, for instance, severely restrict where personally identifiable data (such as banking or medical records) of European citizens can reside. This project overcomes these limitations by implementing the blockchain abstraction on a novel foundation, and, in so doing, demonstrates that efficient data processing and the decentralization of trust can go hand-in-hand.

At its core is a key insight gained from prior research in databases – namely, that is possible to implement the abstraction of a totally ordered sequence of transactions without requiring all of their operations to be actually executed sequentially. To leverage the opportunity for greater parallelism offered by this insight, this project will develop the first geo-distributed database provably resilient to malicious sabotage, whether from some of the computing nodes implementing the database or from clients of the database.

Today, there exists no rigorous specification of what correctness would even mean in such a database; this project will introduce such correctness specification, based on the ethos of bounding the influence that malicious actors (whether among the replicas implementing the database or among its clients) can have on the outcome of transactions submitted by correct clients. It will then develop new algorithmic techniques that, despite adversarial attempts to the contrary, implement the blockchain abstraction while provably enforcing these correctness conditions.

To simplify deployment, this project will focus on drastically reducing the degree of replication necessary to support blockchains. Specifically, it will refine the blockchain’s current threat model to decouple the degree of replication needed to ensure that no data will be lost from what is required to guarantee the integrity of the blockchain execution; this will make it possible to relax the requirement that all replicas store the entire state of the blockchain, and thus lead to easier regulatory compliance.

Tighter integration among mutually untrusted parties can be transformative for a variety of applications, including healthcare, financial services, and supply chain management. Databases are natural candidates for supporting this integration, but currently lack a way to express and efficiently enforce correctness when some actors behave maliciously.

This work builds that conceptual framework, leveraging a novel architecture that makes it easier to comply with data use regulations, and instantiates it in working prototypes that will be rigorously evaluated for performance and robustness. The synergy between theory and engineering critical for the success of this project is also crucial to the education of the next generation of system engineers: they will have to negotiate issues of performance, fault-tolerance, and trust in the ubiquitous large-scale distributed systems that underpin most industries today.

Proposed lecture and project materials will prepare students to apply a principled approach to building trustworthy distributed systems.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.