The idea of consensus is that the distributed systems will agree on taking the decision needed for the task. In a client server architecture its quite simple because the server is always taking the decision. In case of say a federated system with multiple servers it becomes critical that there is a consensus among the servers involved. There are many consensus algorithms for distributed systems and it all depends on the type of network you want to build and the fault tolerance levels you plan for the network. Broadly speaking there are two types of fault assumption, Byzantine and non-Byzantine. We have talked about this previously. The table below summarizes the consensus types

So the simplest is round-robin and Paxos or RAFT are the types of consensus that are used in a distributed system but with limited number of servers. In this case the number of nodes are fixed and are trusted. These can be used in a trusted distributed system.

The Byzantine fault tolerance can tolerate only 33% of dishonest actors. Blockchains posed two main challenges for distributed consensus 1) Parties can be dishonest 2) Parties can join/Leave the network Hence we needed a more robust consensus algorithm which would be BFT but also support with atleast 51% honest actors. This 51% consensus is also known as nakamoto consensus because the PoW algorithm introduced by bitcoin supported this.

Proof of Work

So the whole idea in a distributed consensus is that the leader is elected and all honest nodes agree with this election. Think about this like a timer. Say each node has a timer and when the timer expires they declare themselves as leaders and then publish that to the peers. Now the challenge here is that its very easy to hack the hw/sw to count the timer fast enough and keep declaring themselves as leaders and many peers could contest that. Hence there needed a mechanism where a node has to do some work which takes significant resource and then publishes the result which other nodes can verify. The good thing with this approach is that all computations are node specific and there is no other exchange of information during the consensus. This is where the concept of hashing comes handy. We will discuss this in detail when we talk about cryptography in the next chapter. Hashing means using some function or algorithm to map object data to some representative integer value. In case of blockchain we use a set of transactions. Now if only a set of transaction is used then its very easy to crack it. Hence in proof of work and also in proof of stake a "nonce" ( number used once) is added to set of transactions. This helps because hash is a one-way function: it cannot be used to obtain the original data, only to check that the data that generated the hash matches the original data. Also since the number of nodes in the network is dynamic and remember that a block needs to be produced at regular interval, a difficulty policy is added. If number of nodes are high then difficulty level is high and if nodes decrease then difficulty is lowered so that the interval is maintained. For bitcoin its 10mins

Proof of stake

Another popular blockchain consensus protocol is proof of stake. Instead of using the computing power the proof of stake uses the concept of staking. In this case the amount of stake that node has will determine its chances of creating a block. In proof of stake there is additional challenge, there can be multiple nodes with similar stake and also nodes should have a saturation limit so that they don’t control maximum stake such that for every block interval the chances of them getting chosen is high. In case of say Cardano which uses ouroboros PoS, the protocol sets ideal number of nodes to be 500 and max stake to be 62M ada. This ensures fair distribution of block creation. Now again among these nodes how do you select the leader? Ouroboros processes transaction blocks by dividing chains into epochs, which are further divided into time slots. A slot leader is elected for each time slot and is responsible for adding a block to the chain. This leader selection uses again the cryptographic technique called VRF verifiable random function. Each of the node registered in the network. At every slot the node verifies a lottery happens and the node checks if its value is below the lottery value and then mints the block if it is elected leader. Even though the slot lottery numbers are randomly generated they are also deterministic when combined with epoch nonce and VRF key. We will cover this in detail when we talk about Cardano

There are many variations of Proof of stake and also other proof of history etc. In general the PoS uses far less compute resource and hence energy efficient.

So using these consensus protocol ensures that leader election is fair and secure in the dynamic environment of blockchain. Next chapter we will cover cryptography details used in blockchains for consensus as well as wallets.

you can find history of PoW here https://armada-alliance.com/blogs/history-of-pow

So to recap the main challenges in distributed system are 1) Network architecture 2) Node data liveliness 3) Timing One specific problem for blockchain is leader selection.

When we consider any blockchain we need to analyze how the blockchain tackles these challenges and the assumptions that are made.

Network Architecture: The architecture itself is usually peer to peer. As shown in previous page the centralized servers are not suitable for Blockchains as we dont want any central node to control the network. However some blockchains choose a federated approach so that until the blockchain grows the pioneers can protect the network. In this Federated approach there are several servers that are maintained by trusted entities and later these servers are removed from the network and make the network more and more peer to peer. Cardano was an example of this approach. By the time I started studying bitcoin and Eth, they were all peer to peer. Ofcourse you have something like a "mining pool" which can collate their compute power. We will look at this when we come to leader selection. Now the next challenge is to look at the behavior of the network. So in the peer to peer we need to understand the assumptions blockchain makes for network behavior. Network behavior is describing what is the expectation from the network. Do we assume that the network is fully reliable like a proprietary network or do we assume fully secure network. In general blockchains will work over internet and this generally means that blockchains have to assume that the network is unreliable and maybe unsecured also.

The blockchains need to take these assumptions and convert that to secure reliable communication by using concepts of secure protocol (for example https) and for reliability have mechanisms that can support re-connection and re-transmission. We should also know the expectations of the network for these parameters. We will look at this in detail when we deep dive into Cardano.

Node data Liveliness: This deals with the challenge that the Node is always synced to the latest blocks in the ledger. This directly depends on the ability of the node to stay alive. As you know computers can fail, so in such a scenario how does the blockchain handle? What happens if one node fails? Does it affect the other nodes and reduce blockchain's capability? In most cases the blockchain protocol is capable of handling node failures because of peer to peer networking. The biggest challenge in blockchain is a node turning into an adversary. Now the node maybe working as honest in some scenarios and dishonest in other. So can the blockchain handle such a situation. This is usually referred to as Byzantine problem. Byzantine thought experiment: In this classic problem, the Byzantine army is separated into divisions, each commanded by a general. The generals communicate by messenger in order to devise a joint plan of action. Some generals may be traitors and may intentionally try to subvert the process so that the loyal generals cannot arrive at a unified plan. The goal of this problem is for all of the loyal generals to arrive at the same plan without the traitorous generals being able to cause them to adopt a bad plan.

So as you can see above the blockchain nodes can suffer with this problem. Unfortunately we cannot trust any node. The practical solution to this was that if there are N dishonest nodes then we need total 3N+1 nodes in blockchain. So this means we cannot have more than 1/3 dishonest nodes. This was very limiting set. This can be achieved only in a federated architecture. However a blockchain should be able to tolerate upto 49% dishonest players. This was one of the reasons that held back blockchain development. The main thing that blockchain like bitcoin suggested was the Nakamoto consensus. The interesting thing in blockchain is that unlike distributed databases, in blockchain we can assume that the longest chain is selected as the main chain. However the leader who get selected for extending the chain has to perform a honesty check by using the Proof of Work or Proof of stake. In bitcoin PoW the node should have high compute capability to solve a cryptographic puzzle. So as long as the 51% of compute is not owned by a single entity the blockchain is guaranteed to have nakamoto consensus. The other interesting thing with blockchain is that good behavior can be rewarded with the cryptocurrency. This encourages honest participation. Blockchains are prone to the Sybal attack which 51% attack. So if a single entity controls say the compute power in PoW or stake in PoS then they can cause this attack. So in Sybal attack the adversory has enough power to create new blocks faster than honest node and will always have his blocks extended as longest chain. In Nakamoto consensus we dont know who is honest and who is adversary and hence we go by the rule that longest chain is main chain.

In next section we will consider the Timing aspects in distributed computer system and how this relates to blockchain and its solutions.

We had talked about wallets during the introductory video on Blockchain. Wallets mainly provide the interfaces that is needed to interact with the Blockchain. The underlying asset of the blockchain for example Ada in Cardano or BTC in Bitcoin will be in the blockchain. Wallets only provide an interface to send/receive. So the coins are not really in the Wallet and Wallet mainly have the keys. We talked about the cryptographic principles in the previous section. We mainly talked about public and private key based cryptography. We saw that with this mechanism we can verify the ownership and tamper proof.

As we saw the keys are mainly generated from a seed. So wallets can be divided as deterministic wallet and nondeterministic wallet. In nondeterministic wallet the keys are newly generated every time and people have to maintain all the key pairs. This is great for privacy but painful to maintain. In case of deterministic wallet there is one seed and from this the wallet keys are generated. The advantage is that in case the wallet got corrupted or you wanted to change the wallet then using this seed you can create a new wallet.

However even maintaining this seed as backup is a challenge as it will be a long string containing a series of 1 and 0. The Bitcoin improvement proposal BIP39 introduced mnemonic based deterministic wallets. Also most wallets are hierarchical i.e. there are a bunch of keys that are generated from a master key.

First lets look at how the mnemonic is generated. Remember mnemonic words are generated automatically by the wallet using the standardized process defined in BIP-39. So the steps involved to generate this is as follows

1) Generate 128 or 256 bit random number called entropy

2) Take SHA256 hash. Get the checksum of length of entropy/32 from this hash

3) Add this Checksum to the entropy

4) Split this result into 11 bits each. For example if the entropy was 128bits then adding checksum, it will become 132bits. If we divide by 11 we will get 12 11bit numbers.

5) The BIP39 English word list maps words to 11 digit numbers. For example 00000000000 maps to word abandon

6) For 128bit entropy get 12 mnemonic codes. For 256 it will be 24 words.

7) We then can use Password-Based Key Derivation Function PBKDF2. PBKDF2 applies a pseudorandom function, such as hash-based message authentication code (HMAC), to the input password or passphrase along with a salt value and repeats the process many times to produce a derived key, which can then be used as a cryptographic key in subsequent operations. So in our case the Mnemonic code words and a constant Salt is passed to PBKDF2 with 2048 rounds

8) The output of the PBKDF2 will be the 512 bit seed. So as long as you remember the mnemonic words and the order, you can always generate this same key. Any slight change will not generate same key because of the cryptographic principles applied here

From this seed, the first 256 bits can be taken to create a Master private key and generate Master public key using the same elliptic curve math.

From these keys the address are generated. Remember Cardano uses BIP32-Ed25519. Ed25519 is an elliptic curve standard for digital signatures. This is different from bitcoin which uses secp256k1

How do we get the address from this seed?

In Cardano from the seed, the wallet Public and Private Keys are generated. This key is then combined with

1) Purpose Pvt key: This is a value that is enoded as 1852H for shelly era

2) Coin Type Pvt Key: This identifies the coin type and for Ada its 1815

3) Account Private Key and Public key. Multiple accounts can be generated and the index of the account that is being used is added to get the address

4) Role Pvt Key and Public Key. Right now there are mainly 3 roles, 0-> external chain, 1->internal chain and 2 is staking address.

5) Address Pvt key and Public key. By default a wallet like Daedalus generates 20 address with indices from 0 to 19.

Once we get this address public key we can get the payment address. This can be used for sending and receiving transactions. In cardano you can stake and earn rewards. This staking keys are generated by setting the role as 2

This all can be done on commandline with cardano-wallet

cardano-wallet recovery-phrase generate > primary

cat primary | cardano-wallet key from-recovery-phrase Shelley > root.prv

cat root.prv | cardano-wallet key child 1852H/1815H/0H | tee account.prv | cardano-wallet key public --with-chain-code > account.pub

cat root.prv | cardano-wallet key child 1852H/1815H/0H/0/0 | tee address.prv | cardano-wallet key public --with-chain-code > address.pub

To get Payment address

cat address.pub | cardano-address address payment --network-tag 1 > address.pay

For stake keys

cat root.prv | cardano-wallet key child 1852H/1815H/0H/2/0 | tee staking.prv | cardano-wallet key public --with-chain-code > staking.pub

Types of Wallets

Until now we looked at the inner working of the wallet and interact with it using commandline. However this is not suitable for people who are not familiar with this infrastructure. Hence a wallet with a nice User interface is needed. In cardano you have mainly Daedalus and Yoroi. These help generate the required address for payment and staking without the need for any commadline

Another important aspect is to understand where the keys are stored when you use the wallet App. We have two options, hot wallet and cold wallet. Hot wallet is a wallet on mobile phone or desktop. The keys are on this device. Hence care should be taken that the device is not hacked or compromised. Cold wallets use specialized Hardware which only connects using USB and the keys are stored in this device. This provides enhanced security

As you can the Mnemonic words are very critical and so they should be written down and should not be stored on a device connected to internet. Anyone can get access to the wallet with these words.

In the next section we will talk about transaction and how wallets help in creating those transactions

The video series is planned to help participants understand Blockchain and Machine Learning. The course first starts with basics of Blockchain.

So now the question is what is blockchain and how is this related to cryptocurrency. Blockchain is a distributed ledger maintaining records. Compare this with a traditional mechanism. These records can be financial transactions or medical record related or even some logistic related usage. In financial use case you can think of existing bank transfer. So if A wants to transfer money to B then we need a trusted party and this case the trusted party is bank. So A uses Bank as an intermediatary to transfer the money. However if a Bank becomes untrustworthy then it becomes difficult for A and B to transact. This is where blockchain can help. The blockchain is a distributed record. Multiple Nodes in the blockchain maintain this ledger in a chronological order. If you look at the below figure then you will see that the record of A transferring to B is maintained in all the nodes of the blockchain and once it has been verified in the blockchain it remains there permanently. This cannot be altered later.

So blockchain mainly has multiple nodes connected to each other. These nodes are computer systems that can process the transactions and they need to be connected by a network like Internet.

This is a classic case of distributed systems in computer science field. We will look at this in detail later.

Lets first answer the second question on what is cryptocurrency? In the above example if the distributed ledger holds a digital asset and can guarantee ownership of the asset using cryptography then this underlying digital asset is cryptocurrency. It holds value based on its usage and is not decided by any centralized authority. Blockchain wallets are needed to own and transfer these crypto and main point to for users to interact with blockchain. We will look at wallets later chapter.

Blockchain Generations and Levels:

The blockchains are categorized into generations. However there are multiple levels of blockchain. The generations mainly apply to the Level1 generation of blockchain.

Level1 blockchains are slower because of rigorous ledger maintenance rules. Level2 are mainly meant for scalability of the blockchain. Sidechains help in getting another blockchain working with main blockchain. For example Milkomeda side chain supporting the Ethereum Solidity Smart contracts is under development to work with Cardano as main chain. The digital asset is still Ada. Lets look at generations of blockchain. The first generation blockchain helped in transfer of digital asset viz. cryptocurrency. Now this is very rudimentary like A transfers to B. However we cannot associate any conditions with this transfer. For example the crypto should be transferred only if B has completed some job. This cannot be encoded in the first generation blockchain. So the second generation blockchain provides these mechanisms which can be triggered based on some events. These second generation blockchains are plagued with slowness. They just cannot scale as the usage increases. Hence came the third generation blockchains that tackled the transaction speed issue and also interoperability with other sidechain. Sidechain is also a blockchain that works in conjunction with the main blockchain. We will again look at this in detail later. The focus of third generation blockchain is to solve the trilema of Level1 blockchains which is decentralization,scalability and security.

So Bitcoin is the first generation blockchain, Ethereum is second generation blockchain and Cardano is an example of third generation blockchain. Before we get into the details about the various blockchains we will look into the basics of these blockchains and why these pose as challenges.

Following points are very critical while choosing blockchain

As we discussed before, the base of a blockchain is a set of computers (nodes) and network. This is nothing but a classic distributed systems. Distributed systems have been around for many decades then why was blockchain not implemented earlier? The answer is the challenges in distributed system which made things more complicated for blockchains where untrusted parties had to communicate.

Before getting into these lets look at different distributed architecture 1) Server Client Architecture 2) Federated server architecture 3) Distributed peer to peer architecture

Figure 1 shows Server client architecture. There is one central server and all clients talk to this. This is very much used in many applications today. However this is not suitable in blockchain as we don't want one central server.

Figure 2 shows the Federated server architecture. In this case instead of one single server, there are multiple servers and they talk to each other. The other clients connect to one of the Federated server. These federated servers connect to one main server. This is not an ideal architecture for blockchain. If one server fails then all the clients connected to that server will get disconnected.

Figure 3 is the peer to peer architecture. In this there is no central server and each node is independent and failure of one node does not cause any cascade effect.

The three main challenges in any distributed systems are 1) Network architecture 2) Node data liveliness 3) Timing

The below table shows the difficulty levels in each of the architecture for the above mentioned challenges

In the next section we will look into details of each of these challenges and why they are high for peer to peer.

Every computer system will have a notion of clock. This is needed for the Operating System can schedule various processes. This is also used to synchronize with time of day etc. In a single computer there is one master clock and all other clocks are derived from this. Let us look at how computer gets its time. The computer has a quartz oscillator and this drives the counter circuitry. This counter starts with an initial value and decrements by 1 for each oscillation and generates an interrupt when it reaches 0. The initial value is reloaded. The interrupt is caught by the OS and maintains a clock for example 60 interrupts per second etc

However in a distributed System each computer has its own clock and hence there is a need for synchronization. Now the question is why is a synchronization needed? This is mainly because clocks can drift. The drift is because in the computer systems the clocks are generated using crystal quartz resonators. This is a whole topic on its own and we will not get into too much details here. These provide a base clock and the operating system can schedule various events using these clocks. So in a distributed system if the clocks drift by few microseconds it creates a major problem. Say for example ordering of transactions can matter in split seconds. So for example look at the below diagram. Alice needs to transfer to Bob and then only Bob can transfer to charlie. If the order of transaction changes the Bob does not have sufficient balance to transfer to charlie.

Hence the order in which the messages arrive matter in distributed systems and network latencies can help compound the problem.

In distributed systems the clocks can be synchronized using Physical clock or Logical clock.

Physical Clock In this case the computers circuitry is used to derive the clock. When multiple computers are participating in distributed system then following needs to be taken care 1) Clock Drift: Computers see a widening gap in perceived time 2) Clock Skew : The difference between two clocks at a given point in time.

Computers use Coordinated Universal Time (UTC). UTC uses International atomic time and its introduced from 1 Jan 1972. This can be used to measure drift in distributed systems. The below figures show clock with respect to UTC

To compensate for these drifts we need should not move the time back. This can cause lot of confusions for future messages as ordering of messages becomes a mess. So instead we should look at adjusting the clock itself. If the clock is faster then we should slow it down and if its slower then we should make it fast. This can be adjusted using the computer circuitry.

Now the question is who will provide the reference UTC clocks? One practical option is use a time server. Basically each computer in the system can query this time server and get the time. However this needs to account for network delays and also if the server fails then there is no way for computers to synchronize. This can be improved by using multiple time sources and then take an average from that. A Network Time protocol (NTP) provides hierarchical servers and this system can provide better results for clock drift. NTP uses a hierarchical, semi-layered system of time sources. Each level of this hierarchy is termed a stratum and is assigned a number starting with zero for the reference clock at the top

Stratum 0: These are high-precision timekeeping devices such as atomic clocks, GPS or other radio clocks. They generate a very accurate pulse per second signal that triggers an interrupt and timestamp on a connected computer. Stratum 0 devices are also known as reference clocks. NTP servers cannot advertise themselves as stratum 0. A stratum field set to 0 in NTP packet indicates an unspecified stratum [wikipedia Network Time Protocol].

Stratum 1 These are computers whose system time is synchronized to within a few microseconds of their attached stratum 0 devices. Stratum 1 servers may peer with other stratum 1 servers for sanity check and backup.They are also referred to as primary time servers.

Stratum 2 These are computers that are synchronized over a network to stratum 1 servers. Often a stratum 2 computer queries several stratum 1 servers. Stratum 2 computers may also peer with other stratum 2 computers to provide more stable and robust time for all devices in the peer group.

Stratum 3 These are computers that are synchronized to stratum 2 servers. They employ the same algorithms for peering and data sampling as stratum 2, and can themselves act as servers for stratum 4 computers, and so on.

Logical Clocks In logical clocks instead of time of day the distributed systems agree on the events. So lets take 3 computers and if A sends a message m1 and B responds to that with m2 then A will understand the second message m2 but computer C would not make any sense because it received m1 after m2.

So Leslie Lamport introduced the concept of Happens Before. The paper introduced abstract point of view in which a clock is just a way of assigning a number to an event, where the number is thought of as the time at which the event occurred. Lamport introduced an algorithm that forces re-sequencing of timestamps to ensure that the "happened before" relationship is maintained. Lamport's algorithm requires a monotonically increasing counter that has to be incremented when events take place. These events will have the clock value which is called Lamport timestamp. This is good for single event. However if we want to understand if two or more events are concurrent then using a vector clock will help solve the problem for a system where all nodes are trusted. However in a blockchain kind of scenario there is no guarantee that all nodes have seen all messages with timestamp < T. Need to use FIFO links and wait for message with timestamp ≥T from every node.

How blockchains solve this problem? For a proof of work blockchain like bitcoin it is difficult to synchronize the respective physical clocks while the nodes are scattered around the world, and it is also possible that there are nodes that camouflage the clock. Resynchronizing the correct time between nodes by introducing Network Time Protocol (NTP) is a difficult technique. Incorporating the time stamp in the block, a mechanism very similar to the Lamport’s logic clock is prepared. As described in [Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto], each node that performs a write operation to a block as a miner itself has a role as a time stamp server. However in bitcoin only the longest chain is legitimate, incorrect transactions are discarded after miner verification. Therefore, the order of blocks is uniquely determined with the lapse of time. As each time stamp increases, the previous time stamp is reinforced.

For Proof of stake protocol like Cardano, the same technicques as in bitcoin cannot be used. The Cardano blockchain is semi-synchronous and divided into epcohs. Each epoch is 5 days and inside each epoch the time is divided into slots. The nodes synchronize their physical clocks to NTP and use the logical epoch/slot to add blocks in blockchain. Since this is semi-synchronous, the nodes can determine which slot and epoch they are currently synced to. Also the slot leaders are decided at the beginning of the epoch but is confidential.

Next Steps This completes the basics needed for understanding blockchain as distributed systems. In the next chapter we will look at the leader election challenge and how this is very peculiar problem for blockchains.

In this chapter we will look at the cryptography basics and its use in blockchain. From the previous chapters you are aware that the blockchain is a trustless distributed system. There is no single party that ensures security. In such an environment it becomes critical that the communication between the nodes ensures the right identity. Two important concepts that are used in blockchain are

1) Cryptographic Hash function

2) Asymmetric Cryptography

Cryptographic Hash function

A hash function is a mathematical function that converts a numerical input value into another compressed numerical value. The input to the hash function is of arbitrary length but output is always of fixed length.

A hash function has following properties

1) Computationally hard to reverse a hash function

2) Given an input and its hash it should be hard to find different input with same value

3) It should be hard to find two input functions of any length that map to same hash

The basic hash function takes 2 blocks of fixed size and then create a hash. Hashing algorithm takes this basic block and run in multiple rounds to get final value.

Since the first message becomes an input to second one and this continues until block N, this effect is known as avalanche effect

Message Digest (MD) and Secure Hash Functions (SHA) are popular hash functions. The main usage of Hash function in blockchain is data integrity. So along with the message the corresponding hash is also sent. The recipient will take the received message re-hash it and then compare this computed hash with the received hash. If both match then the message can be trusted. This is not only useful for data integrity but also block integrity. If the hash of the block is saved along with the block then the blocks become immutable. This is because if someone tries to change the block then they will not be able to get the same hash as original one because of the properties of hash. The other advantage is that the hash always has fixed length.

The hashing is also used in proof of work. In PoW, miner uses partial hash inversions to prove that work was done. The average work that the miner needs to perform in order to find a valid message is exponential in the number of zero bits required in the hash value, while the other miners can verify the validity by executing a single hash function

Asymmetric Cryptography

Cryptography is needed in distributed systems mainly because of the trustless nature. Cryptography is a method of using advanced mathematical principles in storing and transmitting data in a particular form so that only those for whom it is intended can read and process it. Encryption is a key concept in cryptography — It is a process whereby a message is encoded in a format that cannot be read or understood by an eavesdropper. The technique is old and was first used by Caesar to encrypt his messages using Caesar cipher. A plain text from a user can be encrypted to a cipher text, then send through a communication channel and no eavesdropper can interfere with the plain text. When it reaches the receiver end, the cipher text is decrypted to the original plain text.

In symmetric cryptography a single key is used to encrypt and decrypt the message. The sender and receiver share this key and keep it a secret. However in blockchain there are multiple distributed nodes and hence it becomes impossible to use the symmetric cryptography.

Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys. Each pair consists of a public key (which may be known to others) and a private key (which may not be known by anyone except the owner). The generation of such key pairs depends on cryptographic algorithms which are based on mathematical problems termed one-way functions.

The main idea is to use a large random number and then use a key generation algorithm to get the public and private key. Now lets look at how this is used.

The first scheme of things, message is encrypted using Alice’s public key and this can be decrypted only by Alice with her private key. This is known as public key encryption. Here the main concern is the secrecy of the message itself. Another scheme is Different-Hellman Key exchange.

In this case a shared secret is created using public key of one participant and private key of another. This essentially creates a shared secret which can be decrypted. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel.

The other important concept is digital signatures. So in the first case we encrypted the message but how to know that in fact the message was send by the correct sender? message is signed with the sender's private key and can be verified by anyone who has access to the sender's public key. This verification proves that the sender had access to the private key, and therefore is very likely to be the person associated with the public key. This also ensures that the message has not been tampered with, as a signature is mathematically bound to the message it originally was made from, and verification will fail for practically any other message, no matter how similar to the original message.

We talked about generation of keys using a large random number. But which one is suitable for this? The answer is elliptic curve multiplication.

Elliptic curve multiplication is a type of function that cryptographers call a "one-way" function: it is easy to do in one direction (multiplication) and impossible to do in the reverse direction ("division", or finding the discrete logarithm). The owner of the private key can easily create the public key and then share it with the world knowing that no one can reverse the function and calculate the private key from the public key.

Bitcoin uses a specific elliptic curve and set of mathematical constants, as defined in a standard called secp256k1, established by the National Institute of Standards and Technology (NIST). The first and most important step in generating keys is to find a secure source of entropy, or randomness. Creating a bitcoin key is essentially the same as "Pick a number between 1 and 2256." The exact method you use to pick that number does not matter as long as it is not predictable or repeatable.

Starting with a private key in the form of a randomly generated number k, we multiply it by a predetermined point on the curve called the generator point G to produce another point somewhere else on the curve, which is the corresponding public key K. The generator point is specified as part of the secp256k1 standard

K = k * G

where k is the private key, G is the generator point, and K is the resulting public key, a point on the curve

A private key can be converted into a public key, but a public key cannot be converted back into a private key because the math only works one way.

To visualize multiplication of a point with an integer, we will use the simpler elliptic curve over real numbers—remember, the math is the same. Our goal is to find the multiple kG of the generator point G, which is the same as adding G to itself, k times in a row. In elliptic curves, adding a point to itself is the equivalent of drawing a tangent line on the point and finding where it intersects the curve again, then reflecting that point on the x-axis.

So this forms the basis of wallets and transactions in blockchains. The public private keys forms the basis for the address used in blockchains. The sender will use digital signature to help nodes to validate that the owner of the wallet. If we take Cardano’s example : if Alice wants to send Ada to Bob

1) Alice creates a transaction with Bob’s public key based address and Ada to be transferred

2) Transaction hash is then created

3) Alice then uses the private key to sign this hash

4) This signature and the original transaction is sent.

5) Bob verifies the received message by first verifying the signature to get the hash and calculates the hash of received message. This way Bob is able to identify the identity and also uncorrupted message from Alice

We will look into more on Wallets and transactions in next chapter. There are other cryptographic functions that we use in DeepchainAda viz, homomorphic encryption and decryption. We will look at this in detail when we talk about privacy based machine learning.

References: Wikipedia and Mastering bitcoin

We have completed the Part1a which focussed on Distributed systems, challenges and how it relates to blockchains. We then focused on Cryptographic principles, wallets and transactions. These are the founding principles of blockchain

In Part1b we will focus mainly on Cardano. We start with

1) Consensus protocols: Ouroboros Classic, Praos, Genesis, Chronos

2) Networking and mini protocols

3) EUTXO in detail

4) Plutus framework : Onchain and offchain

In parallel we will have basic Haskell completed so that after Part1b we can focus on writing Plutus applications

Part2 will focus on Machine Learning fundamentals which will start once we finish Plutus framework.

In the previous chapter we looked at how the wallets help in creating addresses. The wallets now have to support transactions like payment, registration of pool or after the Shelly fork in Cardano even the minting of tokens.

Assets in ledger

The first thing we need to understand is the ledger model. In other words, how are the assets (Ada) stored in the ledger. There are two main models for this. One is Unspent Transaction Outputs (UTxO) and other one is global accounting model.

In UTxO model, the assets are held as unspent transaction outputs. This is similar to cash and coins. For example if you want to make a purchase worth $90 and you have $100 note then you will give that and get back $10. So if we take this as UTxO model then you have one UTxO say worth 100 and after you spend it you get two UTxO, one worth 90 which is added to shopkeeper's wallet and another UTxO worth 10 is returned back to your wallet

In Account based model, transaction updates look similar to say a bank account. If you have $100 in the account then after spending $90 the account is directly updated to $10. This type is suitable for computation but the global state has to be known so that we dont have the double spend problem.

UTxO

Cardano uses Chimeric ledger. This means it can support both Account based and UTXO based transactions. When you stake in cardano stakepool and receive the rewards for staking then the reward amount is stored in Account based model. This helps in saving space and also if the rewards are very small then it prevents the problem of UTXO dust. Hence when you want to spend your rewards you first need to do a withdraw so that these get converted to UTXO.

Now lets understand this UTXO transaction model

Suppose Alice's wallet has 3 UTXO, one worth 2Ada, another 3Ada and one more worth 100Ada. Alice wants to transfer 10Ada to Bob. In this case the wallet needs to select the UTxO worth 100Ada and once the transaction is successful then we will mainly have one UTxO worth 90Ada put back into Alice's wallet and UTxO 10Ada in Bob's wallet. So now Alice again has 3 UTxO one worth 2Ada, another 3Ada and finally the new 90Ada. Note that we cannot split UTxO. They get spent and removed once they are part of successful transaction.

EUTxO

The EUTxO is the new enhanced UTXO to support smart contracts. In this case instead of just using the digital signature, we have a state called Datum and script. The input redeemer will check if the transaction can be redeemed. We will talk about this in detail when we start with smart contracts

In summary, each transaction has a set of UTxO to be spent and create new UTxO to handle the transfer and change. Every transaction has to pay a transaction fee to cover the cost of validating the transaction.

Transactions in Cardano

We now look at how the transactions are constructed. All these are represented using Concise Binary Object Representation (CBOR). CBOR is a data format whose design goals include the possibility of extremely small code size, fairly small message size, and extensibility without the need for version negotiation. Its similar to JSON. Like JSON it allows the transmission of data objects that contain name–value pairs, but in a more concise manner. This increases processing and transfer speeds at the cost of human readability

The basic steps are

1) Find all the UTxO and choose the ones that will be suitable for the transaction (UTXO IN in fig below)

2) Build the transaction using payment address, destination address and timeout. This timeout is needed incase the transaction does not complete within certain slots. If transactions are not processed before timeout then the transactions become invalid (UTXO OUT , Invalid Slot Num)

3) Based on this calculate the fee. In Cardano fee is calculated with fee = minFee + 44*NumberOfBytesInTransaction

4) Calculate the change output. This is the value left after the transfer amount and fee (UTXO End address)

5) Using these 4 parameters build the transaction as shown in figure below

Now if you see there are additional fields in the transaction. This is because after Shelly, we are able put metadata and create policies for NFT (non fungible tokens). This is one of the reasons why Cardano was able to support NFT even before smart contracts. So along with UTXO we can specify a policy ID to mint along with token name and number of tokens. The script hash is also added and a metadata which can be an IPFS location for the image. If we dont associate image the metadata will be NULL

6) Finally we sign the transaction. This scheme was explained in the cryptography principles chapter.

The signed transaction will include the token public key (while minting tokens) and transaction hash signed with private key. Finally to pay the transaction fees in case of minting token or if making an Ada payment then payment key signature is added as shown in figure.

This was a very quick view on how wallets assist in creating transactions and submitting them to chain.

We talked about UTXO dust. So what is UTXO dust? As we can see if we have multiple UTXOs then how do we choose which UTXO to be used. For example if we have in a wallet say one UTXO worth 2 Ada, another worth 1Ada, a third one worth 6 Ada. If we want to transfer 3 Ada which ones should we choose? Care should be taken that there are not too many small value UTxO as they may cause transaction fees to increase. If we include multiple UTXO then the size in bytes of transaction increases and hence fees. Hence if a wallet has lot of small value UTxO then its called accumulating dust. The wallets handle how to avoid this and we will not look at those details here. However if you are writing a contract that directly creates these transactions then care should be taken about UTxO dust.

As we have studied before, blockchains need to solve the distributed system challenges like

1) Node

2) Network

3) Time

4) Consensus

We will first start with Consensus and time for Cardano. Cardano uses Proof of stake protocol and this is called Ouroboros. This helps in achieving consensus. Ouroboros comes in different flavors and these are

1) Ouroboros Classic

2) Ouroboros Praos

3) Ouroboros Genesis

4) Ouroboros Chronos

5) Ouroboros Hydra

In this part we will focus on Ouroboros Classic and Praos. In the video below we will look at the Proof of stake protocol leader selection and usage of global time. We will look at how Verifiable Random Function (VRF) is used. This is part1 of the video. In part2 we will look at adversary and chain fork in these protocols

The second part of the video talks about leader selection if there is a conflict. It may happen that at a given slot two parties are leaders then using VRF this is solved. This is called slot battle. The other kind of battle that happens if a party has propogation delays then it may mint same block number as another party. Then depending on the propogation time one of them is chosen. This is called block height battle.

Apart from this there is chain selection that needs to happen and this also affects if a leader's block is added or not. This will be covered in next video

Networking in Cardano is being enabled for P2P. As you know blockchain need P2P for a truely decentralized environment. However in Cardano the P2P is being enabled in 1.33.0. I will update this chapter once P2P is enabled on mainnet

So how does Cardano handle node connectivity if its not P2P? It uses mechanism called topology updator. Relays for the first time need to connect to a known relay in network (usually provided by IOG). This is similar to a trusted setup we have during cryptograhic initializations. Once the relays are synced, if you operate a stakepool then you need to register the relay as part of your pool. This will help the relay get registered in the topology files. Once in the topology file the other realys can discover and connect. You need to run a updator script every hour so that topology has the relay entry. This aoids faulty relays to be part of topology

Currently the connections between nodes is unidirectional. This means you have seperate IN connections and OUT connections. P2P will enable bidirectional connections. I provide some more details in the video

Apart from this, there are mini-protocols to help implement the block transmission and connection to wallets. This is beyond the scope of this book. Usually these protocols are implemented by low level API.

This completes the Blockchain part. From next chapter we will look at Deeplearning

Slides are updated here

Video

We will mainly use following reference books

1) d2l.ai

2) http://www.deeplearningbook.org

3) Neural Networks and Learning Machines -Simon H.

Topics covered: Linear algebra, multivariate analysis, probability theory, statistics.

This is good resource for people who want to revise concepts

I will cover relevant parts when we go further in the course

Next Week we will look at Linear Neural Network