Cryptography and Blockchain Data Structures

Introduction

Blockchain networks are built from two complementary ideas: cryptographic protection and structured, replicated data. Cryptography makes it difficult to forge records, impersonate participants, or alter previously published information without detection. Data structures—especially transactions, Merkle trees, blocks, and chains of block headers—organize that information so that many independent computers can verify it efficiently.

A blockchain does not make data magically true or confidential. Rather, it provides mechanisms for establishing integrity, authorship, ordering, and agreement about a shared history. Understanding these mechanisms is essential for developers, administrators, auditors, and analysts working with blockchain systems.

Learning Objectives

After completing this chapter, you should be able to:

1. Explain the roles of hashing, public-key cryptography, and digital signatures.
2. Distinguish private keys, public keys, addresses, and signatures.
3. Describe how transactions are represented and verified.
4. Construct and interpret a Merkle tree and Merkle proof.
5. Explain the structure of a block, including timestamps and block references.
6. Analyse how tamper-evident data structures support blockchain security.
7. Identify practical limitations, operational risks, and governance responsibilities.

1. Cryptography as a Foundation of Blockchain

Cryptography is the study and practice of protecting information and communications using mathematical techniques. In blockchain networks it primarily supports four goals:

Most public blockchains emphasize integrity and authentication rather than confidentiality. Transactions are commonly visible to network participants, although some systems use privacy technologies such as zero-knowledge proofs, confidential transactions, or permissioned access controls.

Cryptographic security depends on assumptions. Algorithms must be correctly implemented, keys must remain secret, and attackers must not possess computational resources sufficient to defeat the chosen primitive. Cryptography reduces risk; it does not remove the need for secure software, governance, backups, and access control.

2. Cryptographic Hash Functions

A cryptographic hash function maps an input of arbitrary length to a fixed-length output called a digest or hash. A simplified notation is:

Here, m is the message, H is the hash function, and h is the resulting digest. The digest length is fixed for a particular algorithm—for example, SHA-256 produces 256 bits, or 32 bytes, for every input length.

A suitable cryptographic hash function has the following properties:

• Determinism: the same input always produces the same digest.
• Preimage resistance: given a digest, finding an input that produces it should be computationally infeasible.
• Second-preimage resistance: given one input, finding a different input with the same digest should be infeasible.
• Collision resistance: finding any two different inputs with the same digest should be infeasible.
• Avalanche effect: a small input change produces an apparently unrelated digest.
• Efficient computation: legitimate users can calculate digests quickly.

A hash is not encryption. Encryption is designed to be reversible with a key; a cryptographic hash is normally one-way and does not provide secrecy. Hashes are therefore suitable for integrity checks, commitments, identifiers, and linking records.

Hashes in blockchain systems

A transaction may be serialized into bytes and hashed. A block header may contain the hash of the previous block. These uses create a dependency: changing an earlier record changes its digest and consequently invalidates data that refers to it.

Hash output should be treated as a byte string, not as a number in ordinary application logic. Displayed hexadecimal text is an encoding of those bytes. Different systems must agree on serialization, byte order, character encoding, and treatment of optional fields; otherwise identical logical data can produce different hashes.

Collision probability

For an ideal hash with an n-bit output, there are 2ⁿ possible digests. If an attacker evaluates approximately q independent inputs and seeks any collision, the birthday approximation is:

Here, P(collision) is the probability of at least one collision under the idealized model. This approximation is most useful when q is not close to or greater than the square root of 2ⁿ. The birthday bound is approximately 2^(n/2), not 2ⁿ. For SHA-256, this is approximately 2¹28 evaluations, far beyond ordinary capability, assuming no cryptanalytic weakness.

3. Public-Private Key Cryptography

Public-key cryptography uses a mathematically related key pair:

• The private key is secret and is used to create signatures or, in some systems, derive other secret values.
• The public key may be distributed and is used to verify signatures or establish encrypted communication.

A blockchain account is not simply a username. In many systems, control is demonstrated by producing a valid signature under a private key recognized by the protocol. An address is usually an encoded representation derived from a public key or a script describing spending conditions. An address is not necessarily the public key itself.

Common blockchain signature families include elliptic-curve schemes such as ECDSA and EdDSA variants. Exact algorithms, curves, signature encoding, and verification rules are protocol-specific. A signature scheme is commonly represented as:

and verified by:

where sk is the private key, pk is the public key, m is the message, and σ is the signature. Verification should succeed only when the signature corresponds to the message and the public key, subject to the scheme's security assumptions.

A signature authenticates possession of a private key at signing time. It does not prove that the signed statement is factually correct, that the key owner understood the transaction, or that the key was legally controlled by a particular person. Legal attribution requires additional evidence and applicable law.

Digital-signature workflow

1. The wallet constructs a transaction according to protocol rules.
2. The transaction, or a defined transaction digest, is presented to the signing device.
3. The private key generates a signature.
4. The transaction and signature are broadcast.
5. Nodes reconstruct the signed message and verify the signature using the public key.
6. Nodes also check authorization rules, balances, nonces, scripts, or other state constraints.

A valid signature alone does not make a transaction valid. It must also satisfy consensus and state-transition rules.

Key management

Private-key compromise can allow unauthorized transactions, while private-key loss can permanently prevent access to assets. Professional practice includes hardware wallets or hardware security modules where appropriate, encrypted backups, recovery procedures, role separation, multisignature authorization, transaction limits, and secure user interfaces. Seed phrases should never be entered into untrusted websites or stored in ordinary cloud notes.

Multisignature arrangements require several keys or approvals. For example, a 2-of-3 policy requires at least two of three designated signatures. This reduces dependence on one device or employee, although it introduces coordination, recovery, and policy complexity.

4. Transactions and Serialization

A transaction is a structured instruction that changes blockchain state. Depending on the platform, it may contain an account identifier, recipient, amount, fee, nonce, smart-contract call, public key, signature, and metadata. The exact fields are defined by the protocol.

Before signing, the wallet serializes the relevant fields into a canonical byte sequence. Canonical serialization is critical: if two nodes interpret the same visible transaction differently, they may calculate different hashes or verify different signatures. Robust protocols specify field order, integer representation, length prefixes, allowable ranges, and handling of omitted or duplicated fields.

A transaction typically passes through these stages:

Figure: Simplified transaction authorization and inclusion flow.

5. Merkle Trees

A Merkle tree is a binary hash tree that summarizes a collection of transactions. Each leaf represents a transaction hash. Parent nodes are calculated by hashing the concatenation of two child hashes:

where L and R are the left and right child byte strings, ∥ means concatenation, and P is the parent hash. The top value is the Merkle root.

For four transactions, the structure is:

Merkle root
                 H(P1 ∥ P2)
                /           \
          P1=H(T1∥T2)    P2=H(T3∥T4)
             /   \           /   \
           H(T1) H(T2)     H(T3) H(T4)

Some protocols define special handling when a level has an odd number of nodes, such as duplicating the final hash; others use a different tree construction. This rule must be specified and followed exactly.

Merkle proofs

A Merkle proof demonstrates that a transaction belongs to a committed tree without transmitting every transaction. For a balanced tree with N leaves, the proof generally contains approximately log₂N sibling hashes, plus ordering information. The verifier hashes the transaction and combines it with the supplied siblings until obtaining a root. If the computed root equals the trusted block-header root, inclusion is established relative to that root.

A Merkle proof does not prove that the transaction is valid, finalized, or honest. It proves membership in a particular committed set. The verifier still needs a trusted block header and, where relevant, evidence that the block is sufficiently confirmed.

6. Blocks and Blockchain Linking

A block normally contains a header and a body. The body contains transactions or other protocol records. A header may contain:

• a reference to the previous block hash;
• a Merkle root or equivalent transaction commitment;
• a timestamp or time-related field;
• a consensus-specific value such as a nonce, validator signature, or proposer identity;
• a protocol version and other commitments.

A simplified block relationship is:

Block i−1 hash → Block i header → Block i hash → Block i+1 header

The previous-block hash creates a chain of commitments. If an attacker changes a transaction in block i, the transaction commitment changes; the block header changes; the block hash changes; and the reference stored in block i+1 no longer matches. Rewriting the history therefore requires altering subsequent blocks and overcoming the network's consensus and economic or governance protections.

This is tamper evidence, not absolute tamper prevention. A sufficiently powerful attacker, a compromised majority, a vulnerable consensus mechanism, or a flawed implementation may be able to rewrite history. The security claim must always be stated relative to the protocol's threat model.

Timestamps

A block timestamp records a time-related claim made under protocol rules. It may support ordering, time locks, difficulty adjustment, expiry, or audit interpretation. It is not necessarily an atomic, trusted measurement from a universal clock. Distributed networks have clock differences, network delays, and protocol-specific bounds on acceptable timestamps.

Applications should avoid treating a blockchain timestamp as precise proof of the physical time at which an event occurred. For high-assurance evidence, combine it with trusted external time sources, signed records, device attestations, or legal and organizational controls.

7. Worked Example: A Four-Transaction Merkle Root

Assume four already-computed transaction digests are T₁, T₂, T₃, and T₄. The tree is calculated as follows:

1. P₁ = H(T₁ ∥ T₂)
2. P₂ = H(T₃ ∥ T₄)
3. R = H(P₁ ∥ P₂)

The root R is placed in the block header. Suppose an auditor receives transaction T₃, sibling T₄, the sibling parent P₁, and the left/right ordering rules. The auditor computes P₂ = H(T₃ ∥ T₄), then R = H(P₁ ∥ P₂). Equality with the trusted header root confirms inclusion.

This example demonstrates verification, not generation of actual cryptographic values. In practice, exact byte serialization, hash algorithm, and odd-leaf rules must be obtained from the relevant blockchain specification.

8. Applied Case: Pharmaceutical Cold-Chain Records

This is an illustrative case.

Background

A pharmaceutical distributor needs to document temperature conditions as vaccines move from a manufacturer to clinics. Several organizations participate, and no single organization should be able to rewrite the shared audit history unnoticed.

Problem

Sensors generate frequent readings. Storing every reading in every block would increase cost and reduce throughput. In addition, a blockchain record alone cannot guarantee that a sensor was calibrated or that a technician did not manipulate the device.

Approach

The distributor stores signed sensor batches in an external repository. Each batch is canonicalized and hashed. A daily set of batch hashes is committed to a Merkle tree, and the Merkle root is recorded on a permissioned blockchain with the relevant shipment identifier and timestamp. Authorized participants retain access to the original data and calibration certificates. Periodic audits use Merkle proofs to verify that a selected batch belongs to the committed daily set.

The network uses role-based access and multiple organizational approvals for exceptional corrections. Corrections do not delete the original record; they append a new, linked record explaining the reason, author, and approval.

Outcome

The design reduces on-chain storage while making later alteration detectable. It also separates three questions that are often confused: whether data was included in a commitment, whether the sensor produced accurate data, and whether the shipment complied with regulation.

Learning points

• Hashes protect integrity, not sensor truth.
• Merkle roots support scalable commitments and proofs.
• Timestamps require careful interpretation.
• Governance, calibration, identity management, and audit procedures remain essential.
• External data availability must be maintained; a hash is not a substitute for the underlying evidence.

9. Limitations, Risks, and Governance

Cryptographic and technical limitations

Hash functions can be weakened by implementation errors, poor serialization, or obsolete algorithms. Signature systems can fail through nonce reuse, weak randomness, key leakage, or incorrect verification. Smart contracts may authorize unintended actions even when their signatures are valid. Quantum computing may eventually threaten some widely used public-key systems, although the timing and practical impact remain uncertain; organizations should monitor post-quantum migration guidance.

Operational limitations

A blockchain cannot recover a lost private key. Wallet interfaces can be deceived by address substitution or malicious transaction details. Backups may create additional theft targets. Custody arrangements should define who can initiate, approve, recover, and audit transactions.

Privacy and regulation

Hashes may still be personal data in some contexts if they can be linked to an identifiable person or used as persistent identifiers. Recording personal information directly on an immutable ledger can conflict with data-minimization, correction, retention, or deletion obligations. A common design principle is to keep sensitive data off-chain and place only a carefully assessed commitment on-chain, but this does not automatically solve legal issues.

Organizations should document data ownership, lawful purpose, access rights, retention, incident response, key recovery, and responsibility for incorrect records. Permissioned systems require explicit governance for membership, validator operation, software upgrades, dispute handling, and emergency procedures.

10. Best Practices

1. Use mature, standardized cryptographic algorithms rather than designing new primitives.
2. Define canonical serialization before implementing hashing or signing.
3. Separate signing keys, encryption keys, administrative keys, and recovery keys.
4. Protect private keys with appropriate hardware, policies, and least privilege.
5. Verify signatures and all protocol state rules, not signatures alone.
6. Specify Merkle-tree ordering, odd-leaf handling, and proof formats explicitly.
7. Treat timestamps as protocol-controlled claims, not perfect physical time.
8. Preserve underlying evidence when using on-chain commitments.
9. Test failure, recovery, upgrade, and key-compromise scenarios.
10. Review privacy, accessibility, regulatory, and governance consequences before deployment.

Chapter Summary

Cryptography provides the mechanisms by which blockchain networks detect alteration and authenticate authorized actions. Cryptographic hash functions produce fixed-length, one-way digests and support integrity checks, identifiers, Merkle trees, and block linking. Public-private key systems allow a private key to create a digital signature that anyone with the corresponding public key can verify. However, a valid signature does not by itself establish that a transaction is legally authorized, factually correct, or valid under all consensus rules.

Transactions are serialized structured messages. Merkle trees summarize transaction sets through parent hashes and provide efficient inclusion proofs. Blocks normally contain a transaction commitment, a previous-block reference, a timestamp-related field, and consensus-specific data. These links produce tamper-evident histories, but protection depends on cryptographic assumptions, implementation quality, consensus, key management, and governance. Practical blockchain applications must therefore combine cryptographic design with reliable data sources, privacy controls, operational security, and accountable institutions.

Key Terms

Hash function: A deterministic function that maps arbitrary input to a fixed-length digest.

Digest: The output produced by a hash function.

Preimage resistance: The difficulty of finding an input corresponding to a specified hash.

Collision resistance: The difficulty of finding two different inputs with the same hash.

Private key: A secret value used to authorize signatures or other cryptographic operations.

Public key: A value distributed for signature verification or related public-key operations.

Digital signature: A cryptographic value that authenticates a message under a private key.

Address: A protocol-defined identifier representing a recipient or spending condition.

Serialization: The conversion of structured data into a defined byte sequence.

Canonical serialization: Serialization that gives one unambiguous byte representation to valid data.

Transaction: A protocol message requesting a state change.

Block: A structured collection of transactions and metadata committed to a blockchain.

Block header: Metadata used to identify and validate a block.

Merkle tree: A tree of hashes that summarizes a collection of records.

Merkle root: The top hash of a Merkle tree.

Merkle proof: Evidence that a leaf belongs to a committed Merkle tree.

Tamper evidence: Detectability of unauthorized alteration, rather than absolute prevention.

Timestamp: A protocol-controlled time-related field associated with a record or block.

Multisignature: An authorization policy requiring signatures from multiple keys.

Consensus: Rules and processes by which a network agrees on valid state and history.

Review Questions

Short Answer Questions

1. What is the difference between a cryptographic hash and encryption?
2. Why must a private key be kept secret?
3. What is the purpose of a Merkle root?
4. Why does a block usually contain the previous block's hash?
5. Why should blockchain timestamps not automatically be treated as exact physical time?

Long Answer Questions

1. Explain the complete lifecycle of a signed blockchain transaction, from serialization to block inclusion.
2. Describe the security properties of a cryptographic hash function and explain their relevance to blockchain systems.
3. Explain how a Merkle proof is constructed and verified.
4. Discuss how private-key management affects the security of blockchain assets and records.
5. Analyse the difference between tamper evidence, data authenticity, and data availability.

Analytical / Application Questions

1. A logistics company wants to store one million sensor readings daily on-chain. Propose a design using hashes and Merkle trees, and identify what evidence must remain off-chain.
2. An auditor verifies a Merkle proof successfully but discovers that the sensor generating the original reading was uncalibrated. What has been proved, and what has not?
3. Design a key-management and approval policy for a treasury account controlled by three departments. Justify the use of single-signature or multisignature authorization and discuss recovery risks.

Multiple Choice Questions with Answers

Question 1

Which property means that a small change in input produces a substantially different hash output?

A. Avalanche effect

B. Confidentiality

C. Key recovery

D. Non-repudiation

Correct Answer: A. Avalanche effect

Question 2

Which key is normally used to create a digital signature?

A. Public key

B. Private key

C. Merkle root

D. Block hash

Correct Answer: B. Private key

Question 3

What does a Merkle proof primarily demonstrate?

A. That a transaction is legally correct

B. That a transaction belongs to a committed tree

C. That a private key was never copied

D. That a timestamp is physically exact

Correct Answer: B. That a transaction belongs to a committed tree

Question 4

In a binary Merkle tree, how is a parent commonly calculated?

A. By adding the child hashes as integers

B. By encrypting one child with the other

C. By hashing the concatenation of the child hashes

D. By selecting the longer child hash

Correct Answer: C. By hashing the concatenation of the child hashes

Question 5

What is the main purpose of including a previous-block hash in a block header?

A. To provide confidentiality for all transactions

B. To link the block to the preceding history

C. To replace digital signatures

D. To guarantee accurate sensor data

Correct Answer: B. To link the block to the preceding history

Question 6

A valid digital signature by itself proves that:

A. The signed message satisfies every consensus rule

B. The underlying real-world event is true

C. The corresponding private-key operation authorized the message, subject to verification assumptions

D. The signer is legally identifiable in every jurisdiction

Correct Answer: C. The corresponding private-key operation authorized the message, subject to verification assumptions

Question 7

For an ideal n-bit hash, the approximate birthday-bound work for finding a collision is on the order of:

A. 2^n

B. 2^(n/2)

C. n^2

D. 2n

Correct Answer: B. 2^(n/2)

Question 8

Which statement about a blockchain timestamp is most accurate?

A. It is always an exact measurement from a universal clock

B. It is a protocol-controlled time-related claim subject to network and rule limitations

C. It is generated only by the transaction sender's device

D. It proves the physical condition of an asset

Correct Answer: B. It is a protocol-controlled time-related claim subject to network and rule limitations

Question 9

What problem does canonical serialization help prevent?

A. Different nodes hashing different byte representations of the same logical transaction

B. Loss of all private keys

C. A shortage of validator hardware

D. Unauthorized physical access to sensors

Correct Answer: A. Different nodes hashing different byte representations of the same logical transaction

Question 10

What does a 2-of-3 multisignature policy require?

A. One signature from each of three keys simultaneously

B. At least two valid signatures from three designated keys

C. Two public keys and three private keys

D. Three signatures generated from one private key

Correct Answer: B. At least two valid signatures from three designated keys