CSE 434, SLN 11381 Socket Programming Project

1           Introduction
Bitcoin was unleashed on the world in 2009 as the first decentralized digital currency. The technology behind it is the blockchain, which has since been found to be a useful idea for much more than just currency.

A blockchain is a single universally accessible digital ledger. It’s called a chain because changes can be made only by adding new information to the end. Each new addition, or block, contains a set of new transactions that reference previous transactions in the chain. So if Abby pays Barbara a bitcoin, that transaction appears at the end of the chain, and it points to the transaction in which Barbara was previously paid that coin by Carol, which in turn points to the time before that when Carol was paid by coin by Damla, and so on.

Bitcoin’s blockchain, unlike the ledgers maintained by traditional banks, is represented on networked computers around the world and is accessible by anyone. A class of participants on this network, called miners is responsible for detecting transaction requests from users, aggregating them, validating them, and adding them to the blockchain as new blocks.

Validation entails both verifying that Abby actually owns the bitcoins in her transaction and that she has not spent them elsewhere. Bitcoin is a cryptocurrency because it relies on the use of private and public keys to validate transactions, and ensure they’re irreversible. Because Bitcoin has no central authority to enforce the rules it uses a mechanism called proof-of-work to hold the anonymous miners operating around the world accountable.

This project description is organized as follows. First we discuss time in distributed systems in §2 and distributed agreement in §3. The objective of this project is to develop a simplified variant of Bitcoin using a peer-to-peer (P2P) approach, with a centralized server to maintain the active miners; the requirements of the project are described in §4. Finally, submission instructions are provided in §5.

2           Time in Distributed Systems
In real life, clocks are used to represent time, and a timer is used to describe occurrences of events in three different ways: When an event occurs, how long it takes, and which event occurs first.

For computer applications we also need the notions of time and timer. As long as the clock representing time is increased uniformly and monotonically, there is no ambiguity in answering these questions for events that occur within the same process. However, interacting processes on separate machines may have a different perception of the time. Without a global time consensus, it is difficult to coordinate distributed activities. Here we describe the notion of a logical clock that preserves only the ordering of events.

2.1         Logical Clocks
For many applications, events need not be synchronized with respect to the real-time clock. It is only the ordering of event execution that is of concern. In such cases, logical clocks can be used to indicate the ordering information for events, particularly in distributed systems where it is difficult to maintain a common physical clock among all coordinating processes. Lamport’s logical clock is a fundamental concept for ordering processes and events in distributed systems.

Each process Pi in the system maintains a logical clock Ci. Lamport defines → as the happens-before relation to synchronize logical clocks between two events. a → b means that event a precedes event b. Within a process, if event a occurs before b, logical clocks C(a) and C(b) are assigned such that C(a) < C(b). The logical clock in a process is always incremented when events in the process progress (i.e., time never goes back and is only a relative measure for logical clock). Processes interact with each other through a pair of send and receive operations. Sends and receives are considered to be events. A corresponding send and receive pair from process Pi to process Pj must have the property that Ci(send) < Cj(receive) since a receive event cannot be completed until a corresponding send is done. This logical clock based on the happens-before relation is summarized in the following two rules:

1.    If a → b within the same process then C(a) < C(b).

2.    If a is the sending event of Pi and b is the corresponding receiving event of Pj, then Ci(a) < Cj(b).

Rule 1 can be easily implemented since events occur in the same process. Rule 2 can be enforced if the sending process timestamps its logical clock time in the message and the receiving process updates its logical clock by using the large of its own clock time and the incremented timestamp. That is, C(b) = C(a) + 1 and Cj(b) = max(TSa + 1,Cj(b)), where TSa is the timestamp of the sending event. The happens-before relation describes the causality between two events. It is transitive, i.e., if a → b and b → c, then a → c. Two events, a and b are said to be disjoint and can run concurrently if neither a → b nor b → a is true. The time-space diagram on the left in Figure 1 shows examples of causally related events (e.g., a and d, b and f) and concurrent events (e.g., b and e, d and e). Logical clocks for concurrent events do not relate to each other.

                1         2                                                                                          (1,0,0) (2,0,0)



                    e                                                                f                                        e                                                                f

Figure 1: The happens-before relation and assignments of logical clock time using Lamport’s logical clocks (left), and vector logical clocks for the same events (right).

Using the happens-before relation and the two rules, all causally related events are ordered by the logical clocks. This results in a partially ordered event graph. For two disjoint events a and b, Ci(a) < Cj(b) does not imply a → b. Furthermore, it is possible that Ci(a) = Cj(b). Total ordering of events may be achieved by assuming the following additional rule for disjoint events:

3.    For all events a and b, C(a) 6= C(b).

2.1.1         Vector Logical Clocks
Even with the total ordering of events using logical clocks, it is not possible to tell whether event a actually happened before event b if Ci(a) < Cj(b), i.e., they might be concurrent. This is where a vector logical clock is used.

In the vector logical clock method, each process Pi maintains a vector of logical clocks for each event. We denote the vector logical clock for event a at processor i as V Ci(a) = [TS1,TS2,...,Ci(a),...,TSn], where n is the number of cooperating processes. Ci(a) (also represented as TSi) is the logical clock time of event a in Pi, and TSk, for k = 1,...,n except i, is the logical clock time for process Pk obtained through the timestamp information carried by messages in the system.

The vector clocks are initialized to zero at the beginning of process execution. The logical clock within a process is incremented as in Rule 1 for the basic logical clock approach. Rule 2 is modified as follows: When sending a message m from Pi (event a) to Pj, the logical timestamp of m, V Ci(m) is sent along with m to Pj. Let b be the event of receiving m at Pj. That is, Pj takes the pairwise maximum of the entries for every k = 1,...,n and also increments is logical clock. Thus the most recent logical clock information is propagated to every process by sending timestamps TSk in the messages.

It is obvious that if event a in Pi happened before event b in Pj, then V Ci(a) < V Cj(b), meaning that TSk(a) ≤ TSk(b) for every k and also TSj(a) < TSj(b). This is because there is a causal path from event a to event b, and event b should have a more up-to-date logical time information than event a since the timestamps are passed along the path and the update rule is based on the larger of the two timestamps. Furthermore, the logical clock of the successor event b has been incremented since event a; therefore TSj(b) must be greater than TSj(a).

For disjoint events, it is not possible to have V Ci(a) < V Cj(b) unless a → b, since process Pi, which contains event a, should have a better update of its own time than any other process’ estimate of the current clock time of Pi; that is, Ci(a) is greater or equal to the TSi in other vectors. Similarly, V Cj(b) < V Ci(a) is true only if b → a. We can conclude that it is possible to tell whether two events are causally related or not by comparing the vector logical clocks of the two events. If V Ci(a) < V Cj(b) then a → b; otherwise a and b are concurrent. The time-space diagram on the right in Figure 1 gives the vector logical clocks for the same events on the left.

3           Distributed Consensus
A fundamental problem in distributed computing is the distributed agreement or the distributed consensus problem – how to get a set of processors to agree on a value.

The formal setting for a distributed consensus protocol is the following: There are M processors P = p1,...,pM that are trying to reach agreement. A subset F of the processors are faulty, and the remaining are non-faulty. Each processor pi ∈ P stores a value Vi. During the consensus protocol, the processors calculate an agreement value Ai. After the protocol ends, the following two conditions should hold:

1.    For every pair pi and pj of non-faulty processors Ai = Aj. This value is the agreement value.

2.    The agreement value is a function of the initial values {Vi} of the non-faulty processors (P − F).

The distributed consensus problem has been studied under a number of failure models, to understand when the problem can be solved. Most of the results use adversary arguments.

Byzantine agreement generally refers to distributed consensus algorithms in which a faulty processor can send arbitrary messages into the network. In particular, a faulty processor can try to prevent the non-faulty processors from reaching an agreement. Indeed, in this setting, if there are t traitors (faulty processors), and M 3t, we can solve the Byzantine generals problem. But if there are too many traitors, then it can be shown that agreement cannot be reached.

To simplify this project, we’ll assume all processors are non-faulty. In addition, we assume the communication is reliable, i.e., uses TCP. Then, distributed consensus can be solved trivially through a simple broadcast, here implemented as repeated unicast.

4           Socket Programming Project
The architecture of the Bitcoin system consists of a centralized server to manage miners. It also consists of n peers where each peer, is identified by name, IP address, port number, and an initial number of coins. Each peer combines the functionality of a peer-to-peer (P2P) client and a transient P2P server. As a P2P client, a peer interacts with the server to join or leave the set of active miners, query the active miner set.

As a transient P2P server, a peer participates in processing Bitcoin transactions. You are to write two programs for this socket programming project:

1.    A miner server that takes (optionally) a command line parameter that is the name of a text file containing miner information; see §4.1 for the commands the server must be able to process.

2.    A P2P miner client and transient miner server; see §4.2 for specifications.

4.1         Miner Management Server
A miner server maintains a “database” of the active miners, i.e., the participants in the network that detect transaction requests, validate them, and add them to the blockchain as new blocks. The miner server must process messages containing the following commands:

1.    query, returns n, the number of miners, and for each miner four attributes are stored: user name, IP address, port number, and the initial number of coins owned.

2.    register username IP-address port coins, when a new miner client process is started, the first thing it does is register itself with the miner server. The server adds the miner attributes to the database or verifies an exact match to an existing records. The server returns an (integer) identifier for the user, and a return code of SUCCESS indicates the information is successfully added to, or verified in, the database. Otherwise, it returns FAILURE.

3.    deregister user-name, removes the named miner and its associated information from the database. A return code of SUCCESS is returned if the miner is successfully removed from the database. Otherwise, it returns FAILURE.

4.    save file-name, saves in the text file named file-name.txt:

•    A line containing the number n of miners.

•    For each of the n miners, a line containing the username followed by its IP address and port number, the initial number of coins owned, and its integer identifier.

A return code of SUCCESS indicates the miners were saved successfully to the file, or FAILURE otherwise.

When the miner server is started, it may be provided a file in this format to initialize the active miners to speed testing of your application. This file may also be generated manually. Of course, the miner processes started should correspond to the attributes in the file.

4.2         Peer-to-Peer Miner Operation
Recall that the miners are the participants in the network that detect transaction requests, aggregate them, validate them, and add them to the blockchain as new blocks. In this project, a miner corresponds to user with a user name (given by a string) running on a host. For simplicity, we will not aggregate transactions, only handle them one at a time.

When a new miner process is started on a host it registers with the miner server. It then queries the miner server in order to know the size, n, and details of the active miner set, which are then output. The ledger (blockchain) at the miner is initialized with a block containing the initial number of coins ci for each active miner, i = 1,...,n, and a null purchase request. The new miner then broadcasts that it has joined the active set of miners, providing its attributes. When an active miner receives the attributes of a new miner joining the active set, it responds with its blockchain. The new miner should replace its blockchain with the longest blockchain received with the latest timestamp.

In this project, a transaction corresponds to a purchase request. A miner Mi forms a transaction by indicating the miner Mj from which it intends to make a purchase, along with the amount in coins cij. In a valid transaction, the amount cij is less than or equal to the number of coins Mi owns, i.e., cij ≤ ci. If the amount cij ci then the transaction is considered invalid and is rejected because Mi can’t afford to make the purchase. The resulting effect of processing a valid transaction is to decrease the coins owned by Mi by the purchase amount, ci = ci−cij, and to increase the coins owned by Mj by the same amount, cj = cj +cij.

All events at a miner must be timestamped using vector logical clocks. A message that is broadcast is to be implemented using repeated unicast; each unicast in the broadcast has the same timestamp.

The steps to follow in processing transactions in our Bitcoin network are:

1.    Mi broadcasts a new transaction to all active miners.

2.    Each miner receives a new transaction and stores it in a block; for simplicity we do not aggregate transactions.

3.    Each miner works on finding a difficult proof-of-work for the block received.

4.    When a miner finds a proof-of-work, it broadcasts the block to all active miners.

5.    Miners accept the block only if the transaction in it is valid.

6.    Miners express their acceptance of the block by appending it to the blockchain if it is unique.

In a real Bitcoin network, proof-of-work involves a time-consuming computation based on hash functions. In our version of Bitcoin, we start with the first block in blockchain and verify that each successive block is both valid and the timestamps must be either concurrent, or follow the happens-before relation. That is, for each successive pair of blocks bi and bi+1, i = 1,...,`−1, where ` is the length (i.e., number of blocks in) of the blockchain, then the transaction in bi must happen-before or be concurrent with the transaction in block bi+1. In order to make the proof-of-work computation more time consuming, we fake the hash computation by taking a very large integer at random and testing if it is a prime number; repeat a small random number of times (≤ 50 times).

You will receive multiple copies of the same transaction that are equivalent (i.e., identical except for the vector timestamp). Only one copy of each transaction should be appended to the blockchain.

Transactions are generated repeatedly until the miner decides to exit the system. It then sends a deregister command to the miner server, and broadcasts its departure. Before a miner terminates, it prints its blockchain clearly labelling each block with its timestamp and associated transaction.

Design your Bitcoin application to read commands from standard input (or from a file redirected to stdin). The sequence of commands has the form:

•    register attributes with the miner server,

•    query the miner server, and then broadcast its attributes to active miners in orderinitialize its blockchain based on responses,

•    repeatedly generate transactions to buy from other miners, process transactions of other miners, and finally,

•    deregister and exit the system.

4.3         Message Format
You must define the format of all the messages exchanged between the active miner server and its clients, and between peers. This is achieved by defining a structure with all the fields you need. For example, for the communication with the miner server, you could define a command field as an integer, e.g., if command is equal to one, then this indicates the query command. It is also useful to define meaningful return codes to indicate success and differentiate failures.

For communication between peers think about what a transaction should contain. It is likely to contain the miner Mi initiating the transaction, the intended recipient Mj, and the current balances of all active miners. To be able to distinguish copies of the same transaction, you may want to include a transaction identifier.

The set of active miners grows and shrinks over time; you may define an upper bound on their number (say, 10). This can bound the size of your vector for implementing vector clocks.

4.4         Port Numbers
Both TCP and UDP use 16-bit integer port numbers to differentiate between processes. Both TCP and UDP define a group of well-known ports to identify well-known services. For example, every TCP/IP implementation that supports FTP assigns well-known port of 21 (decimal) to the FTP server.

Clients on the other hand, use ephemeral, or short-lived, ports. These port numbers are normally assigned to the client. Clients normally do not care about the value of the ephemeral port; the client just needs to be certain that the ephemeral port is unique on the client host.

RFC 1700 contains the list of port number assignments from the Internet Assigned Numbers Authority (IANA). The port numbers are divided into three ranges:

•    Well-known ports: 0 through 1023. These port numbers are controlled and assigned by IANA. When possible the same port is assigned to a given server for both TCP and UDP. For example, port 80 is assigned for a Web server for both protocols, though all implementations currently use only TCP.

•    Registered ports: 1024 through 49151. The upper limit of 49151 for these ports is new; RFC 1700 lists the upper range as 65535. These port numbers are not controlled by the IANA. As with well-known ports, the same port is assigned to a given service for both TCP and UDP.

•    Dynamic or private ports: 49152 through 65535. The IANA dictates nothing about these ports. These are the ephemeral ports.

In this project, each group G is assigned a set of 1000 unique port numbers to use in the following range:

[1000 + (G × 1000),1000 + (G × 1000) + 999]

5           Submission Requirements and Guideline for Deliverables
Using the submission link on Blackboard, submit a zip file[1] named Groupx.zip, where x is your group number, before 11:59pm of Sunday, 02/25/2018. This zip file should contain the following:

1.    Design document (30%). Describe the design of your miner server and P2P Bitcoin application. Include a description your message format and all protocols you have implemented in your system. Include a pseudocode description of the miner server, P2P client, and P2P server. In addition, describe your data structures, design choices, and algorithms used. User documentation describing how to compile and run your program must be provided.

2.    Code, demo, and documentation (70%). Submit all source code implementing your miner server and P2P Bitcoin application. This will be downloaded, compiled, and run during the demo of your project. If you demo on the racks in BYENG 217 a bonus of 10% may be obtained.

5.1         Suggested Timeline
Here is a timeline you may consider following to complete this project on time:

Date
Milestone
02/04/2018
Design message format between miner server and P2P client; test
02/11/2018
Design message format between P2P Bitcoin peers
02/18/2018
Implementation of vector clocks and transaction processing among P2P peers
02/25/2018
Continue to test and debug application
6           For Honours Project Credit
If you are interested in extending this project for honours credit I have some ideas. One is implementing the Bitcoin proof-of-work based on public and private keys. Another could involve using UDP instead of TCP for message transmission and coping with lost messages (using what you can deduce from vector clocks to request retransmission). I will also consider your own ideas. Please think about it and come talk to me.



[1] Do not use any other archiving program except zip.