SHA-256

1. Introduction

The emergence of cryptocurrencies has underscored the need for advanced security mechanisms to protect digital assets and transactions. At the heart of Bitcoin’s security framework lies SHA-256, a member of the SHA-2 family of cryptographic hash functions. This powerful algorithm plays a pivotal role in ensuring the integrity and security of Bitcoin's decentralized network. In this chapter, we explore the inner workings of SHA-256, its fundamental operations, and how it safeguards Bitcoin transactions, making it indispensable to the cryptocurrency's architecture.

SHA-256 (Secure Hash Algorithm 256-bit) Overview

SHA-256 is part of the SHA-2 (Secure Hash Algorithm 2) family, designed by the NSA and standardized by NIST (National Institute of Standards and Technology) in 2001. SHA-256 is a cryptographic hash function, which means it takes an input (or "message") and returns a fixed-length string of 256 bits (32 bytes), regardless of the input size. The result is known as a hash or digest. It's crucial for ensuring data integrity, authenticity, and security in various cryptographic operations.

1.1 How SHA-256 Works:

SHA-256 (Secure Hash Algorithm 256-bit) is a cryptographic hash function that generates a fixed-length output (256 bits) from an input of arbitrary length. Here’s a detailed explanation of how it works:

• Input Handling

Input Length: SHA-256 can process inputs of any size—whether it's a small string, large file, or an entire blockchain.

Padding: The input data is first padded to ensure its length is a multiple of 512 bits. Padding works as follows:

A single bit 1 is appended to the message

Several 0 bits are added until the message length is 64 bits shy of being a multiple of 512.

A 64-bit block representing the original length of the input is added to the end. If the original length exceeds 64 bits, only the last 64 bits are considered.

• Processing in 512-bit Blocks

Once the message is padded, it is divided into blocks of 512 bits each. If the input length is already a multiple of 512, it is processed as-is after padding

• Message Schedule

For each 512-bit block, SHA-256 expands it into 64 32-bit words (a process known as message scheduling).

The first 16 words are simply the 32-bit chunks of the 512-bit block.

The remaining 48 words are generated by applying bitwise rotations and shifts to earlier words using the following formulas:

W[t]=σ1(W[t?2])+W[t?7]+σ0(W[t?15])+W[t?16]

σ0(x)=(x?right?rotate?7)⊕(x?right?rotate?18)⊕(x?shift?right?3)

σ1(x)=(x?right?rotate?17)⊕(x?right?rotate?19)⊕(x?shift?right?10)

• Initial Hash Values

SHA-256 starts with 8 predefined 32-bit initial hash values. These values are constants derived from the square roots of the first 8 prime numbers:

makefile



H0 = 0x6a09e667
H1 = 0xbb67ae85
H2 = 0x3c6ef372
H3 = 0xa54ff53a
H4 = 0x510e527f
H5 = 0x9b05688c
H6 = 0x1f83d9ab
H7 = 0x5be0cd19
        

• Main Compression Loop

SHA-256 processes each 512-bit block through 64 rounds of transformations. For each round:

Select 32-bit Round Constants: These are predetermined constants derived from the fractional part of the cube roots of the first 64 prime numbers.

Bitwise Operations: Several bitwise operations and modular additions are performed on the current block, hash values, and the round constants.

Functions:

Ch (choice): Ch(x,y,z)=(x∧y)⊕(?x∧z)Ch(x, y, z) = (x \land y) \oplus (\neg x \land z)Ch(x,y,z)=(x∧y)⊕(?x∧z)

Maj (majority): Maj(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)Maj(x, y, z) = (x \land y) \oplus (x \land z) \oplus (y \land z)Maj(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)

Σ0 and Σ1

Σ0(x)=(x?right?rotate?2)⊕(x?right?rotate?13)⊕(x?right?rotate?22)

Σ1(x)=(x?right?rotate?6)⊕(x?right?rotate?11)⊕(x?right?rotate?25)

Temporary Variables: Intermediate values are stored in variables a through h. The main computation for each round looks like:

T1=h+Σ1(e)+Ch(e,f,g)+K[t]+W[t]

T2=Σ0(a)+Maj(a,b,c)

h=g,g=f,f=e,e=d+T1,d=c,c=b,b=a,a=T1+T2

After each round, the values in the registers (a through h) are updated.

Now, Final Hash Value

After all the blocks are processed, the final hash is computed by adding the results of the last block to the current intermediate hash values:

H0=H0+a,H1=H1+b,...,H7=H7+hH0 = H0 + a, H1 = H1 + b, ..., H7 = H7 + hH0=H0+a,H1=H1+b,...,H7=H7+h

The result is concatenated to form a 256-bit output, often represented as a 64-character hexadecimal string.

Key Properties of SHA-256

• Fixed Output Size: The output is always a 256-bit (32-byte) hash, regardless of the input size.
• Deterministic: The same input always produces the same output.
• Avalanche Effect: A small change in the input (even a single bit) results in a dramatically different hash.
• Collision-Resistance: It’s computationally infeasible to find two different inputs that produce the same hash.
• Pre-image Resistance: Given a hash, it’s computationally infeasible to reverse it to find the original input.

Example:

For example, hashing the string "hello" using SHA-256 will produce the following 256-bit hash (in hexadecimal):

2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
        

This process, though complex, is designed for efficiency and security, making SHA-256 widely used in various security protocols like SSL, TLS, and blockchain technologies such as Bitcoin.

1.2 Detailed Breakdown of Bitcoin Transactions

1. Transaction Lifecycle:

• Creation: A user creates a transaction using their wallet software. This process typically involves specifying the recipient's address, the amount to send, and any optional fees.
• Signing: The transaction is then signed with the user's private key, creating a unique digital signature that can be verified using the corresponding public key.
• Broadcasting: After signing, the transaction is sent to the Bitcoin network where it is propagated through nodes (computers that maintain a copy of the blockchain).
• Mining: Miners collect these transactions and bundle them into blocks. They compete to solve a complex mathematical problem (proof of work) that allows them to add the block to the blockchain.
• Confirmation: Once a miner successfully adds the block, the transactions within it are confirmed. Additional confirmations occur as more blocks are added on top of this block.

2. Transaction Structure:

Each Bitcoin transaction contains several key elements:

• Version: Indicates the version of the transaction.
• Input Count: The number of inputs being used in the transaction.
• Inputs:Each input references a previous transaction’s output (specifying the transaction ID and output index).The digital signature created by the sender.
• Output Count: The number of outputs created by the transaction.
• Outputs:Each output specifies a recipient's address and the amount of Bitcoin sent.
• Locktime: (optional) Specifies the earliest time a transaction can be added to the blockchain.

3. Transaction Fees:

• Dynamic Fees: Transaction fees are not fixed; they vary based on network congestion. When more users are trying to make transactions, fees increase to incentivize miners to prioritize their transactions.
• Fee Estimation: Wallets often provide fee estimators to help users decide how much to pay, balancing speed with cost.

4. Security Measures:

• Double Spending: Bitcoin's consensus mechanism prevents double spending, where a user tries to spend the same Bitcoin in multiple transactions. This is achieved through the confirmation process and the use of a decentralized ledger.
• Replay Protection: In forks (splits in the blockchain), replay protection mechanisms help prevent transactions from being executed on both chains inadvertently.

Current Developments and Trends

1. Layer 2 Solutions:

• Lightning Network: This is a second-layer solution that allows for faster, off-chain transactions, reducing congestion on the main Bitcoin blockchain. It enables users to open payment channels and transact instantly with minimal fees. It’s especially useful for microtransactions.

2. Segregated Witness (SegWit):

• SegWit is a protocol upgrade that separates transaction signatures (witness data) from the main transaction data. This reduces the size of transactions, allowing more transactions to fit into a single block and improving overall scalability.

3. Taproot:

• Taproot is another upgrade that enhances privacy and efficiency. It allows for more complex transactions to appear as standard transactions on the blockchain, improving privacy for multi-signature transactions and enabling smart contracts.

4. Institutional Adoption:

• Increasingly, institutional investors are entering the Bitcoin market, leading to greater acceptance and integration into financial systems. Companies like MicroStrategy, Tesla, and others have added Bitcoin to their balance sheets, influencing price and adoption.

5. Regulatory Landscape:

• The regulatory environment surrounding Bitcoin is evolving. Governments worldwide are working on frameworks to regulate cryptocurrencies, which can impact transactions, exchanges, and overall market dynamics.

6. Environmental Concerns:

• The energy consumption of Bitcoin mining has drawn scrutiny due to its environmental impact. This has led to discussions about sustainable mining practices and alternative consensus mechanisms (e.g., proof of stake in other cryptocurrencies).

?? Bitcoin Transaction Creation Process

1. Creating the Transaction

• Inputs: Reference previous unspent transaction outputs (UTXOs).
• Outputs: Specify the recipient's Bitcoin address and the amount to send.

Example:

python

transaction = {
    "inputs": [{"txid": "previous_txid", "vout": 0}],
    "outputs": [{"address": "recipient_address", "amount": 0.01}]
}
        

2. Signing the Transaction

• Use the sender's private key to sign the transaction, ensuring ownership.

Example:

python

import hashlib
import ecdsa

def sign_transaction(transaction, private_key):
    tx_hash = hashlib.sha256(transaction.encode()).hexdigest()
    private_key_bytes = bytes.fromhex(private_key)
    signing_key = ecdsa.SigningKey.from_string(private_key_bytes, curve=ecdsa.SECP256k1)
    signature = signing_key.sign(tx_hash.encode())
    return signature.hex()

signature = sign_transaction(str(transaction), "your_private_key")

        

"Signing ensures that only the owner of the Bitcoin can initiate the transaction."

Broadcasting the Transaction

Example:

pyhton

import requests

def broadcast_transaction(signed_tx):
    response = requests.post("https://api.blockchain.com/v3/push_tx", json={"tx": signed_tx})
    return response.json()

broadcast_response = broadcast_transaction(signature)
        

Broadcasting allows miners to pick up the transaction and include it in a block."

Verification by Miners

• Miners validate the transaction to ensure inputs are correct and sufficient funds are available.

"Verification is crucial to maintain the integrity of the Bitcoin network."

Inclusion in a Block

Valid transactions are compiled into a new block by miners.

Mathematical Calculation: If a miner successfully mines a block every 10 minutes, they can mine approximately:

Blocks?per?day=24?hours×60?minutes10?minutes=144?blocks\text{Blocks per day} = \frac{24 \text{ hours} \times 60 \text{ minutes}}{10 \text{ minutes}} = 144 \text{ blocks}Blocks?per?day=10?minutes24?hours×60?minutes=144?blocks

?? Block Confirmation Process

Example:

python

block = {
    "previous_hash": "hash_of_previous_block",
    "transactions": [transaction],
    "timestamp": time.time()
}
        

Each block contains a list of transactions, a timestamp, and a reference to the previous block.

Proof of Work

• Miners solve a cryptographic puzzle to add the block.

Mathematical Calculation:

Let’s assume a miner has a hash rate of 100 TH/s (terahashes per second) and the current difficulty level requires 2242^{24}224 hashes for a valid block:

Expected?time?to?mine=224?hashes100×1012?hashes/second≈16777216?seconds≈194days\text{Expected time to mine} = \frac{2^{24} \text{ hashes}}{100 \times 10^{12} \text{ hashes/second}} \approx 16777216 \text{ seconds} \approx 194 daysExpected?time?to?mine=100×1012?hashes/second224?hashes≈16777216?seconds≈194days

Proof of Work ensures that adding a block requires significant computational effort.

Difficulty Adjustment

• The network adjusts mining difficulty every 2,016 blocks.

Difficulty adjustment helps stabilize the rate of block creation over time.

Finalization

• Once a block has enough confirmations, its transactions are considered permanent

Confirmation Count:A transaction with 6 confirmations is generally considered secure

Finalization means that the transactions are now part of the permanent Bitcoin ledger.

1.3 Key Generation in Bitcoin

ey generation in Bitcoin is a critical process that underpins the security and functionality of the network. It involves creating pairs of cryptographic keys: a public key and a private key. Here’s a detailed explanation of the key generation process, including steps, concepts, and relevant mathematical foundations.

Overview of Keys

1. Private Key: A secret number, known only to the owner, that allows them to access and control their Bitcoin. It’s typically a 256-bit number.
2. Public Key: A derived key from the private key, which can be shared with others to receive Bitcoin. It’s generated through an elliptic curve multiplication.

Steps in Key Generation

Step 1: Generate a Private Key

The first step is generating a random private key. This key should be generated securely using a cryptographic random number generator to ensure it is unpredictable.

• Format: A Bitcoin private key can be represented in hexadecimal form, usually 64 characters long (256 bits).
• Example: Kx8sV9n4AyL6Qr8G4c1Rn2kDqfT7gJdZpV5h8L2wC9QY3X2R2W7f3Q4Y8sQ7gTzD

Step 2: Generate the Public Key

The public key is derived from the private key using elliptic curve cryptography (ECC). Specifically, Bitcoin uses the secp256k1 curve.

• Elliptic Curve Multiplication: The public key PPP is computed as:

P=k×G

where:

k is the private key (a scalar),

G is a predefined point on the elliptic curve (the generator point).

Public Key Formats: The public key can be in two formats:

• Uncompressed: Begins with 04, followed by the x and y coordinates of the elliptic curve point.
• Compressed: Begins with 02 or 03, depending on whether the y-coordinate is even or odd.

Step 3: Create the Bitcoin Address

To create a Bitcoin address, the public key undergoes several transformations:

1. Hashing: The public key is hashed using the SHA-256 algorithm, followed by RIPEMD-160 to create a 160-bit hash. H=RIPEMD-160(SHA-256(P))
2. Add Network Byte: A network byte (0x00 for the main Bitcoin network) is prepended to the hash.
3. Checksum: A checksum is created by taking the first four bytes of the SHA-256 hash of the extended public key (the one with the network byte).
4. Base58Check Encoding: Finally, the result is encoded in Base58Check format, which is the address format used in Bitcoin.

Example Bitcoin Address: 156UGALjatSQnY7wy4LruP6CEE5VoczdZE

Summary of Key Generation Process

• Generate Private Key: A 256-bit random number.
• Derive Public Key: Using elliptic curve multiplication.
• Create Bitcoin Address: Hash the public key, add a network byte, compute a checksum, and encode it in Base58.

Security Considerations

• Randomness: The private key must be generated using a strong, cryptographically secure random number generator.
• Storage: Never share your private key. If someone has access to it, they can control your Bitcoin.
• Backup: It’s essential to back up the private key or the seed phrase (if using a hierarchical deterministic wallet) securely.

1.4 SHA-256: A Deep Dive into Security Features

SHA-256 (Secure Hash Algorithm 256-bit) is part of the SHA-2 family of cryptographic hash functions designed by the National Security Agency (NSA) in the United States. It plays a crucial role in ensuring data integrity and security across various applications, particularly in the realms of blockchain technology, digital signatures, and secure communications.

Key Security Features of SHA-256

1. Deterministic Output

• Definition: For any given input, SHA-256 always produces the same 256-bit (32-byte) hash output.
• Implication: This ensures consistency in data verification. When you hash the same input multiple times, the result will never change.

2. Pre-image Resistance

• Definition: It is computationally infeasible to reverse-engineer the original input from its hash output.
• Implication: This property guarantees that even if an attacker knows the hash, they cannot easily retrieve the original data.

3. Second Pre-image Resistance

• Definition: Given an input and its hash, it should be challenging to find a different input that produces the same hash.
• Implication: This prevents the substitution of a legitimate input with a malicious one that has the same hash, thereby ensuring data authenticity.

4. Collision Resistance

• Definition: Finding two distinct inputs that produce the same hash output should be extremely difficult.
• Implication: This characteristic protects against attacks that exploit hash collisions, ensuring that each input corresponds to a unique hash output.

5. Avalanche Effect

• Definition: A small change in the input (even a single bit) results in a significantly different hash output.
• Implication: This feature enhances security by making it hard to predict how minor changes will affect the hash, thus ensuring that even similar inputs yield different outputs.

6. Bit Security

• Definition: SHA-256 is considered to have 128 bits of security strength.
• Implication: An attacker would need approximately 21282^{128}2128 operations to find a collision, making brute-force attacks practically impossible with current technology.

7. Length Extension Resistance

• Definition: Given a hash h=SHA?256(m)h = SHA-256(m)h=SHA?256(m), it is infeasible to compute SHA?256(m∣∣m′)SHA-256(m||m')SHA?256(m∣∣m′) without knowing the original message mmm.
• Implication: This is crucial for applications like Message Authentication Codes (MACs), where the integrity of the original message must be maintained.

8. Efficient Computation

• Definition: Designed to be efficient on modern hardware.
• Implication: SHA-256 strikes a balance between security and performance, making it suitable for a wide range of applications while being computationally intensive enough to deter brute-force attacks.

9. Widespread Application in Security Protocols

SHA-256 is integrated into many security protocols, including:

• TLS/SSL: Protecting web communications.
• Digital Signatures: Ensuring message authenticity and integrity.
• Blockchain Technology: Validating transactions and securing cryptocurrency networks like Bitcoin.

Example: Computing SHA-256 Hash in Python

To illustrate the practicality of SHA-256, here’s a simple Python snippet that computes the SHA-256 hash of a string:

python 

import hashlib

def compute_sha256(input_string):
    sha256_hash = hashlib.sha256()
    sha256_hash.update(input_string.encode('utf-8'))
    return sha256_hash.hexdigest()

# Example usage
input_data = "Hello, World!"
hash_result = compute_sha256(input_data)
print(f"SHA-256 Hash: {hash_result}")

        

SHA-256 stands as a pillar of modern cryptographic practices, offering a robust suite of security features essential for maintaining the integrity and authenticity of data. Its deterministic nature, resistance to various attacks, and efficiency make it indispensable in secure digital communications and beyond.

1.4 Complexity of SHA-256

SHA-256 is renowned for its robustness and efficiency. Here’s a detailed look at its computational complexity, security features, and the underlying algorithms.

1. Algorithm Overview

SHA-256 is a member of the SHA-2 family of cryptographic hash functions. It employs a series of logical operations, bitwise shifts, and modular additions to transform an input message into a fixed-length hash of 256 bits. The core of the algorithm consists of several rounds of processing.

Basic Steps of SHA-256:

1. Padding the Input: The input message is padded so that its length is congruent to 448 modulo 512. This means the message length, when expressed in bits, must be n≡448mod??512n \equiv 448 \mod 512n≡448mod512. Padding adds a single '1' bit followed by enough '0' bits, and then the original message length is appended as a 64-bit integer.
2. Setting Initial Hash Values: The algorithm begins with predefined initial hash values, which are constants derived from the square roots of the first 64 prime numbers.
3. Processing in Blocks: The message is divided into 512-bit blocks. Each block is processed in 64 rounds using the SHA-256 functions and constants.
4. Final Hash Calculation: The output of each block's processing is combined with the hash values from the previous block, culminating in the final 256-bit hash.

2. Time Complexity

The computational complexity of SHA-256 can be expressed in terms of its time complexity, which primarily depends on the number of operations required to process the input message.

Key Points:

• Block Processing: SHA-256 processes data in 512-bit blocks. Each block undergoes 64 rounds of transformation.
• Operations Per Block: For each block, the algorithm involves a series of logical operations, modular additions, and bitwise shifts. Each of the 64 rounds requires approximately 64 operations.
• Overall Complexity:For a message of length mmm bits, the number of 512-bit blocks NNN is given by N=?m+64512?N = \lceil \frac{m + 64}{512} \rceilN=?512m+64?.The total number of operations is approximately 64N64N64N, leading to a time complexity of O(N), or more specifically, O(m) in terms of the input size.

Space Complexity

The space complexity of SHA-256 is relatively low, primarily because the algorithm uses a fixed amount of memory regardless of the input size.

Key Points:

• Constants and State Variables: The algorithm maintains a fixed set of 8 hash values (each 32 bits) and uses a few additional variables for processing (also 32 bits each).
• Working Memory: SHA-256 requires memory for 64 words of 32 bits each for message scheduling and a small amount for intermediate processing.
• Overall Space Complexity: The space complexity is O(1), meaning it uses a constant amount of space.

4. Security Complexity

1. Collision Resistance

• SHA-256 is designed to withstand collision attacks, where two distinct inputs produce the same hash.
• The security strength against collision attacks is approximately 21282^{128}2128 operations, making it infeasible to find collisions with current technology.

2. Pre-image Resistance

• For a given hash value, finding any input that hashes to it (the pre-image) requires approximately 22562^{256}2256 operations.

3. Second Pre-image Resistance

• Given an input and its hash, finding a different input that produces the same hash is also estimated at around 22562^{256}2256 operations.

4. Bit Security

• The effective security level of SHA-256 is considered to be 128 bits, meaning that an attacker would need 21282^{128}2128 operations to find a collision, which is prohibitively large for brute-force attacks.

5. Summary of Complexity

• Time Complexity: O(m), where mmm is the length of the input message in bits.
• Space Complexity: O(1), constant space usage regardless of the input size.
• Collision Resistance: Approximately 21282^{128}2128 operations.
• Pre-image Resistance: Approximately 22562^{256}2256 operations.

1.5 Conclusion

SHA-256 is a cornerstone of Bitcoin's security framework, providing the necessary cryptographic foundation to ensure the integrity and reliability of transactions within the network. Its sophisticated design, characterized by its intricate operations and robust security features, is crucial for safeguarding the decentralized ledger against potential threats.

Understanding the inner workings and complexities of SHA-256 is essential for anyone seeking to comprehend the mechanisms that secure and validate Bitcoin transactions. As the Bitcoin network continues to evolve and expand, the role of SHA-256 in preserving the integrity and security of each transaction will become increasingly vital.

In an era where digital currencies are gaining traction, the steadfastness of SHA-256 ensures that Bitcoin remains a secure and trustworthy medium of exchange. Thus, the importance of this hash function cannot be overstated; it stands as a testament to the resilience and innovation that underpin the world of cryptocurrency.