[Part-4] Blockchain Simplified Notes NPTEL
Consensus.
Consensus is a procedure to reach in a common agreement in a distributed or decentralized multi-agent platform.
For example, there are 4 people who could make two decisions, A or B. Three people are in the favour of A and one person in the favour of B. Then, decision A will be considered as majority of people are in its favour.
Need for Consensus:
Reliability and Fault tolerance in a distributed system. Even if there are certain faulty nodes present in the network, correct operations can take place using consensus.
Uses of Consensus:
- Commit transaction in a database: If you wish to transfer money from your bank branch to some other bank branch, then all the bank branches need to reach consensus to decide the validity of transaction and then allow the transaction.
- State Machine Replication.
- Clock Synchronisation.
Types of Fault:
- Crash Fault: A node suddenly crashes or becomes unavailable in the
middle of a communication due to software or hardware failure. - Network or Partitioned Fault: A network fault occurs (say the link
failure) and the network gets partitioned. - Byzantine Fault:A node starts behaving maliciously.
Properties of Distributed Consensus:
- Termination: Every correct node(non-faulty) decides some value at the end of the protocol.
- Validity: If all the individuals proposes the same value, then all correct individuals decide on that value.
- Integrity: Every correct individual decides at most one value, and the decided value must be proposed by some individuals.
- Agreement: Every correct individual must agree on the same value.
Message Passing System.
Message passing is a technique for invoking behaviour (i.e., running a program) on a computer. The invoking program sends a message to a process (which may be an actor or object) and relies on the process and the supporting infrastructure to select and invoke the actual code to run.(Source: Wikipedia)
Synchronous Message Passing System:
The message is received within a fixed predefined interval of time. The delay time is also guaranteed. Paxos, Raft, Byzantine fault tolerance (BFT) are some synchronous consensus algorithms explored by distributed system community.
Asynchronous Message Passing System:
The message can be delayed for arbitrary period of time. No fixed message reception time.
Impossibility Result(FLP[85]): No consensus can be guaranteed in a purely asynchronous communication system in the presence of any failures. In such a system, Consensus may occur recognisably, rarely or often. FLP stands for Fischer-Lynch-Patterson who were awarded a Dijkstra Prize for this significant work of impossibility result.
Consensus in Open System.
Problems in open system:
- Message passing requires a closed environment. Everyone need to
know the identity of others. Since in Bitcoin anyone can join the network anytime, this clearly is not possible in an open environment. - Shared memory is not suitable for Internet grade computing. Where will we keep the shared memory?
Consensus in Bitcoin:
All the nodes in this network need to agree on the correctness of a
transaction. Some nodes can also initiate malicious transactions.
Whenever the multiple miners mine new blocks simultaneously, the objective of consensus is to decide which block is to be added next.
Here the miners don’t know each other. If we broadcast the transactions (flooding), then the impossibility result might occur because we don’t have a global clock. So, it is not feasible to wait for infinite time.
Every miner solves a challenge independently. The miner who completes the challenge first will add the block mined by him to blockchain. This is his Proof of Work(PoW).
Now the miner sends the solution to all the other miners and this block is included in the blockchain. In case any transactions are not logged in the block, they will be included in the next round.
Different Attacks & their Solutions.
Tampering Blockchain:
Each block is mined after doing some work. Thus, the blockchain together contains a large amount of work. If an attacker wants to change any block, he needs to compute all the hashes in the blockchain. This will need a large amount of work which is difficult with current hardware.
Double Spending Problem:
We have already seen this problem in the previous article. This problem arises when the attacker tries to send the same amount of bitcoins to two different persons.
The solution to the problem in blockchain is that the transactions are irreversible and every transaction is validated against the existing blockchain before accepting it.
A known case of double spending: In November 2013,it was discovered that the GHash.io mining pool appeared to be engaging in repeated payment fraud against BetCoin Dice, a gambling site.
Sybil Attack:
In this attack, the attacker attempts to fill the network with the clients under its control so that he can refuse to relay valid blocks and can perform double spending.
Bitcoin makes these attacks more difficult by only making an outbound connection to one IP address per /16 (x.y.0.0).
Denial of Service(DoS) Attack:
The attacker sends a lot of data in the network to make it busy so that the actual transactions are not able to take place.
Solutions:
- No forwarding of orphaned blocks
- No forwarding of double-spend transactions
- No forwarding of same block or transactions
- Disconnect a peer that sends too many messages
- Restrict the block size to 1 MB
- Limit the size of each script up to 10000 bytes
Other Attacks can be read here: https://en.bitcoin.it/wiki/Weaknesses
Proof of Work(Pow).
- This idea was first proposed by Dwork and Naor (1992) to combat junk emails. To discourage the attacker from sending junk emails, the sender had to do some work for the validation of email.
- The work is given by Service provider to the Service requester. This work is moderately hard but feasible for the requester and is easy for the provider to validate.
- The puzzle friendliness property of cryptographic hash functions make them useful to be used as PoW.
- Most implementations of Bitcoin PoW use double SHA256 hash function.
- The probability of getting a PoW is low. It is difficult to say which miner
will be able to generate the block. Hence, no single miner will be able to control the network.
Hashcash PoW:
Hashcash is a proof-of-work system used to limit email spam and denial-of-service attacks, and more recently has become known for its use in bitcoin (and other cryptocurrencies) as part of the mining algorithm. Hashcash was proposed in 1997 by Adam Back.(Source: Wikipedia)
In this a textual encoding of a hashcash stamp is included in an email header to check that the sender has expended a modest amount of CPU time calculating the stamp before sending the email. The header looks like this:
X-Hashcash: 1:20:1303030600:hey@jaindivya.com::McMybZIhxKXu57jd:ckviVersion: number of zero bits in the hashed code: date: resource:
optional extension: string of random characters: counter
The header contains:
- ver: Hashcash format version, 1 (which supersedes version 0).
- bits: Number of “partial pre-image” (zero) bits in the hashed code.
- date: The time that the message was sent, in the format
YYMMDD[hhmm[ss]]. - resource: Resource data string being transmitted, e.g., an IP address or email address.
- ext: Extension (optional; ignored in version 1).
- rand: String of random characters, encoded in base-64 format.
- counter: Binary counter (up to 220), encoded in base-64 format.
Sender Side Computation:
- Initialise counter to a random number.
- Compute 160-bit SHA-1 hash of the header.
- Accept header if first 20 bits of the header are all 0.
- If not, repeat the above steps with a different counter.
Recipient Side Computation:
- Check if date is within two days.
- Check the email of the sender.
- Check the random string for repetition.
- Compute the 160 bit SHA-1 hash of the entire received string.
- Check if the first 20 bits are zero or not.
On average, the sender will have to try 220 hash values to find a valid
header and the receiver required 2 microseconds to validate.
Applications of Hashcash PoW:
- Bitcoin mining.
- Spam filters.
- Comment Spamming prevention.
Monopoly Problem.
During bitcoin’s early days, anyone could “mine” it using their home computer. But as the price of digital currency climbed towards $100 in 2013 (it’s now over $4,000), professional mining groups with specialised computer chips emerged. Today, these groups, or pools — nearly all based in China — have become concentrated and now dominate the production of new bitcoins.
Why monopoly problem existed?
- Miners are getting less rewards over the time. So, they are discouraged to join as a miner.
- The difficulty of puzzle is increasing which is not possible to be solved by normal hardware.
Solution of Monopoly Problem:
Proof of Stake(PoS) emerged as a solution to this problem. Let’s study about it in detail.
Proof of Stake(PoS):
A person can mine or validate block transactions according to how many coins he or she holds. This means that the more Bitcoin or altcoin owned by a miner, the more mining power he or she has.(Source: Investopedia)
The first cryptocurrency to adopt the PoS method was Peercoin.In Peercoin, the coinage is used as a variation of stake. Coinage is calculated by multiplying number of coins by the number of days the coins
have been held.
- If an attacker wants to attack, he/she should have more number of bitcoins.
- If the attacker holds majority of bitcoins, then the majority affect will be on attacker only.
Proof of Burn(PoB):
PoB works on the principle of allowing the miners to “burn” or “destroy” the virtual currency tokens, which grants them the right to write blocks in proportion to the coins burnt.
To burn the coins, miners send them to a verifiably un-spendable address. This process does not consume many resources other than the burned coins.
PoB works by burning PoW mined cryptocurrencies. It is power efficient unlike PoW.
Proof of Elapsed Time(PoET):
- PoET is proposed by Intel as a part of hyperledger sawtooth.
- In this each participant in the blockchain network waits a random amount of time. The first participant to finish waiting gets to be leader for the new block.
- To verify that the proposer has really waited for the random amount of time, it relies on a special CPU instruction set called Intel Software Guard Extensions (SGX). SGX allows applications to run trusted code in a protected environment.
Further Reading: https://www.hyperledger.org/projects/sawtooth
Miners.
Responsibilities of a miner:
- Validate transactions and construct a block.
- Use hash power to vote on consensus and commit transactions with a new
block. - Store and broadcast the blockchain to the peers.
How a miner mines a bitcoin?
- A miner joins the network and listens for the transactions.
- Listens for new blocks, then validate and re-broadcast a new block when it is proposed.
- Collects transactions for a predefined time and construct a new block.
- Finds a nonce to make the new block valid.
- Broadcasts the new block. Everybody accepts it if it is a part of the main
chain. - Earns the reward for participating in the mining procedure.
Mining Difficulty:
- Mining difficulty is a measure of the amount of difficulty in finding the hash below a given target.
- Bitcoin has a global block difficulty while mining pools have a pool-specific share difficulty.
Difficulty Calculation in Bitcoin:
In Bitcoin, the difficulty changes for every 2016 blocks. The desired rate is that it should take two weeks to mine 2016 blocks provided one block is mined in 10 minutes.
If it takes less than two weeks to mine 2016 blocks, then the difficulty is increased. If it takes more than two weeks to mine 2016 blocks, the difficulty is decreased.
current_difficulty = previous_difficulty *(2 weeks in milliseconds)/(milliseconds to mine last 2016 blocks)The expected number of hashes we need to calculate to find a block with
difficulty D is :
(D * 2256) / (0xffff * 2208)To know the current difficulty, refer this link: https://blockexplorer.com/api/status?q=getDifficulty
Mining Hardware:
- Anyone with access to the internet and suitable hardware can participate in mining.
- In the earliest days of Bitcoin, mining was done with CPUs from normal desktop computers.
- Graphics cards, or graphics processing units (GPUs), are more effective at mining than CPUs and as Bitcoin gained popularity, GPUs became dominant.
- Eventually, hardware known as an ASIC (which stands for Application-Specific Integrated Circuit) was designed specifically for mining Bitcoin. The first ones were released in 2013 and have been improved upon since, with more efficient designs coming to market.(Source: Steemkr)
Mining Pool.
- When the resources are pooled by miners, they create a mining pool.
- The processing power is shared by miners over a network to mine a new block.
- The reward is split proportionally to the amount of work each miner has contributed.
- Slush Pool is the oldest currently active mining pool. AntPool is the largest currently active mining pool.
- Although mining pool allows small miners to participate in the mining process, it also discourages miners for running complete mining procedure.
- Mining centralisation in China is one of Bitcoin’s biggest issues at the moment.
Mining Pool Methods.
Terminology:
- Block Reward: The new bitcoins distributed by the network to miners for each successfully solved block.
- Mining Pool Fee: The fees taken for mining in a pool.
Notations used:
B: Block Reward minus Pool Fee.
p: Probability of finding a block in a share attempt (p = 1/D), D is the
block difficulty.
Pay Per Share(PPS):
- It offers an instant, guaranteed payout to a miner for his contribution to the probability that the pool finds a block.
- Each share costs exactly the expected value of each hash attempt:
R = B*p. - This model allows for the least possible variance in payment for miners while also transferring much of the risk to the pool’s operator.
Proportional:
- Miners earn shares until the pool finds a block (the end of the mining round).
- After that each user gets reward as per their share:
R = B * (n/N)
n = Amount of share of the miner.
N = amount of all shares in the round.Pay-per-last-N-shares(PPLNS):
- This is similar to proportional with a difference that the miner’s reward is calculated on a basis of N last shares, instead of all shares for the last round.
- If the round was short enough all miners get more profit, and vice versa.
About this Series.
This is a series of notes based on the Blockchain Course by NPTEL, which serves as a primer for understanding the blockchain fundamentals. You can find previous articles here:
I am always open to discussions so shoot your thoughts about this topic in the comment section below.
About MoatFund.
We are continuously assisting people get educated about how rapidly this technology is advancing and revolutionising our world. Our mission is to create a decentralised fund managing protocol operated on smart contracts, which is publicly accessible and can control the entire network of fund managing capabilities on blockchain. Here’s Everything You Need to Know About MoatFund, All In One Place.
