Cryptographic Foundations for Blockchain
Interested in Cryptography
Hash Functions
A hash function is a keyless algorithm that transforms an input, which can be of varying lengths and representations, into a fixed-size binary string of a specific length, known as the hash message digest.
Given a hash function, suppose its output is always a binary string of length k. Then the size of the output space is 2^k.
A good hash function has two properties:
It should be very fast to compute.
It must reduce the chance of ‘collisions’ over the expected input space.
To minimize collisions, a hash function must distribute its output uniformly over the output space. (looks like random)
A potential drawback of such hashes is that there could be many collisions (md4, md5, SHA1)
Ex: Hash tables
Cryptographic Hash Functions
It is wanted for a hash function to behave like a random function.
In order for a hash function to be called a cryptographic hash function, it has to satisfy the following properties for security:
Resistance
- Preimage Resistance
Given an output y, it should be hard to find any input x such that: H(x) = y (One-way)
A generic attack would require around 2^n operations
- Second Preimage Resistance
Given an output y and input x such that H(x) = y, It should be hard to find another input x' such that H(x') = y
Theoretically, finding x and x' for the same output is always possible. Because the output size of y is FIXED, but input can be ANYTHING.
A generic attack would require around 2^n operations
- Collision Resistance
It should be hard to find two inputs x and x' such that H(x) = H(x')
A generic attack would require around 2^(n/2) operations due to Birthday Paradox.
NOTE: Birthday Paradox
How many people need to be in a room before it is more likely than not at least two people share a birthday?
p >= 1/2 when t >= 23
We have a collision with p > 1/2
Understanding Birthday Paradox
NOTE: A hash function’s security is determined by how easy it is to find hash collisions.
Regular hash functions are effective at reducing collisions when inputs are random, but they can be weak against intentional collision attacks. Cryptographic hash functions, the choice for blockchains, excel in resisting collisions even against determined attackers.
Every cryptographic hash function is a hash function. However, not every hash function is a cryptographic hash function.
Symmetric Encryption aka Secret Key Encryption
Only one secret key for encoding and decoding
Oldest and best-known way within cryptographic algorithms
Fast
Not scalable
Easy to execute and manage (one secret key)
Someone can steal/reach the key
Blowfish, AES, RC5, DES (Data Encryption Standard)
DES → broken because of the short key → Triple DES (multi-layered version of DES)
AES (Advance Encryption Standard)
Uses block cipher
Faster and safer according to DES
Supports 128, 192, 256-bit keys
Longer length and block size according to DES
Resist -> brute force attacks
Key Distribution Problem
The secret keys must be transported securely.
Reason for the birth of asymmetric encryption.
Asymmetric Encryption aka Public Key Encryption
Founded in 1976
Uses different keys for encryption and decryption
Diffie-Hellman → First asymmetric encryption algorithm
Elliptic Curve Systems, RSA, Code-based Cryptosystems
As a simple example
Postman, Cargo package, Receiver, Postbox
Receiver’s Address: Public key
Postbox’s Key owned by the receiver: Private key
RSA (Rivest–Shamir–Adleman)
A public-key algorithm that is used for key establishment and the generation and verification of digital signatures.
Comparison between AES, DES, RSA and Blowfish
Hash Puzzles
Hash puzzles are a game in which one tries to find a nonce (an integer) such that:
H (nonce, data) < T (target difficulty level).
Consensus Algorithms
Algorithms that provide data to be negotiated across distributed systems or operations.
Used to provide the “not to require trust structure” of the blockchain.
POW (Proof Of Work)
A nonce that solves the hash puzzle serves as a proof-of-work.
Used by Bitcoin
Hard to solve & easy to confirm
Miners need to solve problems to add blocks
The first miner to solve the problem
the block to the chain.
Almost 100% protection against DDoS
Problem: The system consumes a lot of energy
Mining
Which party solves the puzzle the first?
The process of searching for a nonce that solves the hash puzzle is called mining.
The parties competing to solve the hash puzzle are called miners.
Forks
“Note that the mining rate is different from the rate at which the ledger grows. Ideally, each new block should lead to the growth of the ledger. However, this is not always the case. For example, it is possible that a miner mines a valid block but does not publish it; in this case, the ledger does not grow (this is dishonest behavior, but we must account for it nevertheless). It is also possible that two valid blocks are mined with the same parent block, in which case the ledger grows only by one block.
This can happen if the second hash puzzle is solved before the pertinent miner hears of the previous block. After all, it takes a non-zero amount of time for a block to be communicated across the network, especially if the block has a lot of data.
In general, the set of blocks mined at any given point in time form a directed tree, rather than a single chain. We say that the blockchain has forked when a single block has two or more children blocks. As such, there could be many forks over time.
What then should the users consider as “the ledger”?
The longest chain rule states that the longest chain among all published blocks should be treated as the ledger. Thus, users should build a new block and append it to the longest chain that they currently know of.”
The Longest Chain Rule
A chain selection rule is used to decide which chain is the "correct" chain. Bitcoin uses the "longest chain" rule, which means that whichever blockchain is the longest will be the one the rest of the nodes accept as valid and work with.
POS (Proof Of Stake)
Instead of the computational power required to verify transactions, validators must stake their coins in 32 slots.
PoS systems do not award block rewards, and only transaction costs are given as the minter validates a block.
There are two primary roles for a validator:
checking new blocks and “attesting” to them if they are valid,
proposing new blocks when selected at random from the total validator pool.
Attacking the system is too costly doesn't mean it can't be attacked.
%51 Attack
Capturing 51% of the processing power in the system
Costs too much (processing power, electricity)
Hard to do on large networks like Bitcoin
Digital Signature Algorithm/Standard (DSA/DSS)
Digital signatures are cryptographic equivalents of handwritten signatures, verifying the sender of a message.
Due to the sizes of signatures, the hash of the message is signed instead of the message itself.
Signatures must be verifiable.
Provides data integrity, data origin authentication and non-repudiation.
Each message's signature must be unique. Reusing signatures would compromise the system's integrity.
Signatures need to be sufficiently long for unforgeability and security.
Fingerprint, signing a document or file, email or e-state uses digital signatures.
“A short string of data a user produces for a document using a private key such that anyone with the corresponding public key, the signature, and the document can verify that (1) the document was "signed" by the owner of that particular private key, and (2) the document was not changed after it was signed.“
Digital signature algorithms are NOT encryption algorithms.
Elliptic Curve
Used to generate the keys.
The security of elliptic curve cryptosystems relies on mathematical problems.
Elliptic curves are NOT ellipses but are named as such due to the similarity of their equations to those used in calculating ellipse circumferences.
Shorter key sizes in elliptic curve cryptosystems provide similar security to larger keys in traditional systems, offering better memory usage and performance.
Public keys and signatures are just points on an elliptic curve. If both of these points are created from the same private key, there will be a geometric connection between them that proves that the person who created the signatures also created the public key.
ECDSA (Elliptic Curve Digital Signature Algorithm)
- ECDSA uses an elliptic curve as the basis for a digital signature system.
Key Generation
dG = Q
Private key (d): A large randomly generated number
Public key (Q): The generator point G multiplied by this random number
G is the generator point
Sign
Random number (k): This introduces an element of randomness in to our signatures, which is important for security. It means that every signature we generate will be different, even if we sign the same message twice.
Message hash (z): This is the hash of the message we want to sign. Hashing the message gives us a small and unique fingerprint for it, and it’s more efficient to sign this fingerprint than it is to sign a large blob of data.
Private key (d): The source of a public key
The random point on the curve (r): Take the random number k and multiply it by the generator point to get a random point
A number to accompany the random point (s): This is a unique number created from a combination of the message hash z and d, which is also bound to the random point using r.
Digital Signature = [r, s]
Verify
Public key (Q): This is the public key for the person claiming to have created the signature.
Message: The data that was signed. We can hash it ourselves to get the message hash z.
Signature [r, s]: This is the signature created for the above message, allegedly created by the person who has the private key for the public key.
Use these three pieces of data to calculate two points on the curve:
Point 1. Start with the generator point G, and multiply it by
inverse(s) * z.Point 2. Start with the public key point Q, and multiply it by
inverse(s) * r.
Add these points together to give Point 3:
If this third point matches up with the random point given, the signature is valid.