Intructor: John Augustine. Contact Details
Teaching Assistants:
Pappu Kumar
Jaya Vardhan
Bhargavi Sriram
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.
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.
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.
Will the simple voting procedures fail even if there is just one traitor general? Why?
How can the good generals still decide in unison when there is just one traitor? In other words, how can we modify the procedure to make it resilient to one traitor.
Are there mechanisms by which we can tolerate more traitors?
Is there a limit to the number of traitors that we can tolerate?
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.
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.
There is no need for a central authority to interfere in the operation of a blockchain system.
Entries recorded on the blockchain can be suitably encrypted to maintain privacy. (Of course, this is not a foolproof system, as we shall see in the course, and needs careful implementation to ensure privacy).
Non-repudiation is a key feature by which no participant can unilaterally backtrack on a transaction.
In the context of cryptocurrencies like bitcoin, we are guaranteed that the same participant cannot spend a particular bitcoin twice.
and many more that we will see in detail in the course.
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.
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.
The course will comprise three modules.
Module 1: The Foundations of Byzantine Fault Tolerance. Byzantine Agreement and Broadcast, with and without authentication, synchronous/asynchronous/partially synchronous, state machine replication protocols, sparse networks, dynamic networks. A brief primer for required concepts in cryptography will be provided. (~ 5 weeks)
Module 2: Blockchains. Classical bitcoin and blockchain design, permissionless systems vs permissioned systems, consensus mechanisms (proof-of-work, proof-of-stake, etc.), deep dives into design aspects of bitcoin/ethereum/algorand/hedera, and prominent attacks on blockchains. (~ 5 weeks)
Module 3: Smart Contracts Applications & Programming using Solidity. Introduction to Solidity, setting up a test environment, writing smart contracts, Non-Fungible Tokens (NFTs), and application case studies. (~ 4 weeks)
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.
Basics of object oriented programming (required)
Design and Analysis of Algorithms (recommended)
Probabilistic Reasoning (recommended)
Please feel free to discuss this with the course instructor.
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.
Three assignments (two theory and one programming): 3*12
Two quizzes (Modules 1 & 2): 2*20
Mini Project (Module 3): 20
Class Participation: 4
This course will NOT require any textbook to be purchased. All required material will be made available to the students.