[Part-2] Blockchain Simplified Notes NPTEL
In this article, we will discuss main cryptotypes used in blockchain and the algorithms used to find them:
Cryptographic Hash Function.
Input: Any string of any length, i.e. the message.
Output: Fixed Size output,i.e. message digest(256 bits for blockchain).
Properties of Hash Function:
- Collision free: For two different messages(inputs), digests(outputs) are always different.
- Hiding: The original message is hidden behind the message digest.
- Puzzle Friendly: The value of k has to be found in
Y=H(X||k)using mining puzzle in Bitcoin PoW where X and Y are known.
1. Collision Free
- One-Way: Message digest can be computed from message using some algorithm but the vice versa is not possible.
- It is difficult to find x and y such that x ≠y but H(x)=H(y).(Not impossible)
- Collision depends on the complexity of hash function. In case of cryptographic hash function, it is difficult to have collision.
Birthday Paradox Problem
Question Statement: What is the probability that in a set of n random people, some of them will have the same birthdays?
Solution: By Pigeon hole Principle, the probability will be 1 if the number of people reaches 366(not leap) or 367(leap) year. This probability decreases with the decrease in number of people. For 23 people, probability will be 0.5 only.
How much time will it take to hack cryptographic hash function?
Suppose a hash function produces N bits of output, then an attacker has to compute 2^(N/2) hashes for a random input to find two matching outputs with probability greater than 0.98.
Thus, for 256-bit hash function, hacker needs to compute 2¹²⁸ hash operations which is time consuming. If every hash takes 1 millisecond, then it would take ~10²⁸ years.
Summary:
- If H(x) = H(y), then it is safe to assume x = y.
- Need to remember only message digest(only 256-bits) rather than the whole original message.
- Comparison of two large messages become easy with their message digest because you will have to compare only 256-bits of hash.
2. Hiding
- If a message(x) is given, it is easier to find message digest H(x) but it is computationally difficult to find message(x) from message digest H(x).
- Hence, the original message is hidden behind the message digest.
3. Puzzle Friendly
In a search puzzle M and Z are known and k is to be computed such that the hash value of M append k is equal to Z. This can be seen by the below formula:
Z = H (M||k)
Puzzle friendly property implies that random searching is the best strategy to solve the above puzzle.
SHA256 Algorithm.
Secure Hash Algorithm (SHA) is used in bitcoin mining to compute 256-bits hash or message digest.
Step 1: Pre-processing of message:
It is done in three steps:
- Padding the message
- Parsing the message
- Setting the initial hash value, H⁰
Padding the message:
In this, padded message is a multiple of 512 bits. Suppose the length of the message is l bits.
Append ‘1’ to the end of the message, followed by k zero bits, where k is the smallest, non-negative solution to the equation l+1+ k ≡ 448 mod 512 .
Then append the 64-bit block that is equal to the number l expressed using a binary representation.
For example, the (8-bit ASCII) message “abc” has length 8× 3 = 24 , so the message is padded with a one bit.
Then 448 − (24 +1) = 423 zero bits, and the message length, to become the 512-bit padded message.
Parsing the message:
The message and its padding must be parsed into N 32-bit blocks.
After padding the output is a multiple of 512-bits. Now, these N blocks of 512-bits each can be expressed as M¹, M²,M³…..
Further, each block of 512-bits can be expressed as 16 sub-blocks of 32-bits such as M¹(0), M¹(1)…..M¹(15) for the first block.
Setting the initial hash value H⁰:
For SHA-256, the initial hash value, H⁰, shall consist of the eight 32-bit words, in hex which were obtained by taking the first 32 bits of the fractional parts of the square roots of the first eight prime numbers. e.g. H⁰(0) = 6a09e667
Step 2: Compression Algorithm
Function that carries out the actual hashing operation of the message-dependent word that comes out of the message scheduler in each round. Compute:
C is the SHA-256 compression algorithm and + means mod 2³² addition.
Hash Pointer.
Hash pointers are just hashes that are used to reference another piece of known information. With hash pointer, we can retrieve the information and check that the information has not been modified.
For example, Bitcoin uses hashes to reference funds supplied in previous transactions. So, if you want to make a transaction giving some bitcoins to someone, you have to reference (with a hash pointer) the transaction where you were given some funds.
Hash Pointer ensures prevention of data tampering because previous block hash is used to compute the new block hash as discussed earlier.
If anyone changes anything in one hash pointer, he will have to change all the previous hash values and hence, pointers which is not possible.
Digital Signature.
A digital signature is a digital code that is transmitted along with the document to the receiver.
The sender uses a signing algorithm to sign the message. The message and the signature are sent to the receiver. The receiver applies verifying algorithm to the combination. If the result is true, the message is accepted otherwise rejected.
Types of keys:
- Public(Asymmetric key): This key is available to everyone and is used in verifying the message by receiver.
- Private(Symmetric key): This key is only known to the sender and is used in signing the document by sender.
Properties of Digital Signature:
- Message Authentication: Ensures the identity of the sender. A message sent by Alice can only be verified using her public key. The message will not be verifiable using Eve’s public key.
- Message Integrity: Ensures that message has not been tampered with or altered. In case an attacker has access to the data and modifies it, the digital signature verification at receiver end fails. The hash of modified data and the output provided by the verification algorithm will not match. Hence, receiver can safely deny the message assuming that data integrity has been breached.
- Non-Repudiation: Sender can’t deny about the sending of the data. If Alice has send some message, she can’t deny later because the message can be verified using her public key.
Public Key Cryptography.
In a public key encryption system, any person can encrypt a message using the receiver’s public key. That encrypted message can only be decrypted with the receiver’s private key.
Terminology of texts:
- Plain text: The original message which is not been encrypted.
- Cipher text: The encrypted text which is obtained by encrypting plain text using some algorithm.
Properties of Public key cryptography:
- It is generated randomly that a attacker is unable to guess it in any way.
- Length of the key must be enough for it not to be guessed. Long key will be difficult to guess.
- The key should contain sufficient entropy such that all the bits in the key are equally random.
RSA (Rivest–Shamir–Adleman) Algorithm
In this algorithm, the encryption key is public and it is different from the decryption key which is kept secret (private). Anyone can encrypt the data but only the intended receiver can decrypt it.
Four phases of RSA:
- Key Generation
- Key Distribution
- Encryption
- Decryption
A basic principle behind RSA is the observation that it is practical to find three very large positive integers e, d and n such that with modular exponentiation for all integer m (with 0 ≤ m < n):
and that even knowing e and n or even m it can be extremely difficult to find d.
In addition, for some operations it is convenient that the order of the two exponentiations can be changed and that this relation also implies:
(e,n) is used as public key, (d,n) is used as private key and m is the message that is to be encrypted.
Key Generation(with example):
- Choose two distinct prime numbers p and q.
Let p=61, q=53. - Compute n = pq.
n=61*53=3233. - Compute λ(n) = lcm(p − 1, q − 1). λ(3233)= LCM(60,52)=
780. - Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; i.e., e and λ(n) are coprime.
Choosing e such that 1<e<780 and GCD(e,780)=1. We gete=17. - Determine d as d ≡ e−1 (mod λ(n)); i.e., d is the modular multiplicative inverse of e (modulo λ(n)).
Forumula obtained: (d*e) mod λ(n) =1
Hence, (d * 17) mod 780 = 1. So,d=413.
Key Distribution:
Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice’s public key to encrypt the message and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key (n, e) to Bob via a reliable, but not necessarily secret, route. Alice’s private key (d) is never distributed.
Encryption:
Public key is (n,e). For a padded plaintext message m, the encryption function is:
For the above example,public key is (3233, 17) and c = m¹⁷ mod 3233.
Decryption:
Private key is (d,n). For an encrypted cipher text, the decryption function is:
For us, private key is (413,3233) and m = c⁴¹³ mod 3233.
Digital Signature in Blockchain.
This is used to validate origin of transaction and prevent non-repudiation. The sender can’t deny the transaction or anyone else can’t claim the transaction by this.
Bitcoin uses Elliptic Curve Digital Signature Algorithm(ECDSA) based on elliptic curve cryptography.
Conclusion.
That’s all about the basics crypto primitives used in blockchain. In the next article, we will study the basics of Bitcoin.
In case you are willing to revise the topic, here is the part 1 of Blockchain Simplified Notes NPTEL. Hope you have completed the assignment-1 of the Blockchain course offered by NPTEL.
In case you wish to discuss anything from this course with me, feel free to comment below.
This is a series of notes based on the Blockchain Course by NPTEL, which serves as a primer for understanding the blockchain fundamentals.
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.
