Distributed Trust (CS 6858, Jul – Nov 2022)

Administrivia

Intructor: John Augustine. Contact Details
Teaching Assistants:

Slot: “K”. Wed 3.30 - 4.45 PM; Fri 2.00 - 3.15 PM; one more 50 mins slot will be announced in the first week. First Day of Class is on July 27, 2022.

Location: CS 34 (in person).

Please see my note on academic honesty. You are required to read it carefully and abide by it both in letter and spirit.

We will be recording classroom activities in this Miro Board. The password will be announced in class.

About the course

In a nutshell …

Distributed trust deals with how mutually distrusting parties can collaboratively solve problems of common interest. Distributed ledgers based on Blockchain technology are widely used nowadays for distributed trust. Though invented around 2008 by Satoshi Nakamoto in the context of bitcoin (a cryptocurrency system), blockchains are widely used for implementing smart contracts between parties that don't necessarily trust each other. The foundations of blockchains trace their roots back to the Byzantine agreement problem and rich theory that has been developed over the years.

This course will introduce you to the foundations and the practical aspects of distributed trust.

The fun problem that started it all.

Distributed Trust deals with distributed settings where participants must collaborate with each other but cannot blindly trust each other. This notion traces its roots back to the Byzantine Generals Problem (aka the Byzantine Agreement Problem) introduced by Lamport, Pease, and Shostak back in the early 80's. In this problem, we are concerned with the following conundrum faced by a fictitious Byzantine army camped around a city. The army has several battalions each lead by a general and each general has an opinion of whether to attack or retreat. The generals must collectively decide to either attack in unison or retreat in unison. (Any half-hearted attack will be the ruin of the Byzantine army.) The problem is that there is no central command and the only option for the generals is to pass messages to each other through messengers in order to make that decision. Let us assume all messages are delivered promptly. Then, one may expect a simple voting mechanism to work. The problem is that some of the generals are traitors (though they may not appear so). Such traitors can maliciously send inconsistent messages to confuse the good generals. Here are a few questions for you to mull over.

Amazingly, this “toy problem” has had a profound impact both in theory as well as in practice. Let us now fast forward to more recent times.

Today's Byzantine Generals: bitcoin, cryptocurrencies, blockchains, smart contracts …

In 2008, an unknown person (or persons) by the name of Satoshi Nakamoto released a white paper that started a fully decentralized currency system called bitcoin. This was the first functional and scalable distributed trust system. Anyone can join the bitcoin system and transact reliably even when many members of the bitcoin system may be malicious. At its core, the main issue is the Byzantine Agreement problem whereby all good participants in the bitcoin system must have a consistent understanding of which transactions took place and which didn't. This consistent understanding of transactions that is agreed by everyone is encoded in a distributed ledger called a blockchain. While bitcoin uses these blockchains for maintaining a currency system, other blockchain systems like Ethereum, Algorand, and Hedera have recognized that these digital ledgers can be used to record state transitions and can be used for writing programs that can encode so-called “smart contracts” between different participants that do not trust each other, but nevertheless wish to work with each other. A few salient points about these blockchain systems need to be mentioned.

So are blockchains really useful for anything other than cryptocurrencies? You bet. Smart contracts are useful in setting up contractual agreements between two or more participants that may not mutually trust each other. As contractual obligations are fulfilled, they can be recorded on the blockchain and payments for such fulfillment can be automated. Amazingly, they are fully secure despite having no central authority exercising oversight. Take a gander here to see several domains in which blockchains can be applied.

In this course…

We will start with the theory of Byzantine fault tolerance in the context of Byzantine agreement and state machine replication. We will then cover blockchain systems, their designs, consensus mechanisms, and their applications. We will also deep dive into writing smart contracts using Solidity, a prominent programming language used for implementing smart contracts.

Course Structure

The course will comprise three modules.

Prerequisites

There are no formal prerequisites. The course is intended to be useful for a wide range of students. However, the following basics will be assumed.

Please feel free to discuss this with the course instructor.

Also…

I plan to give out a prerequisites test in the first week of the course. It will not be evaluated for the course, but it will serve as a way for us to figure out if this course is right for you.

Tentative Course Evaluation

Textbook & References

This course will NOT require any textbook to be purchased. All required material will be made available to the students.