Cryptography and Blockchain Data Structures

Introduction

Blockchain systems combine cryptography with replicated data structures to provide integrity, ownership, and verifiability without relying entirely on a central record keeper. Cryptography does not make a blockchain automatically truthful: it helps participants detect alteration, authenticate messages, and prove control of digital assets. Data structures such as blocks, transaction trees, authenticated dictionaries, and hash-linked histories organize those proofs so that they can be checked efficiently.

A useful distinction is between confidentiality, integrity, and authenticity. Confidentiality prevents unauthorized reading; integrity detects unauthorized modification; authenticity provides evidence about the origin or authority of a message. Most public blockchains emphasize integrity and authenticity rather than confidentiality, because transactions are commonly visible to network participants.

Learning Objectives

By the end of this chapter, a learner should be able to:

• explain cryptographic hash functions and their role in blockchains;
• distinguish symmetric encryption, public-key cryptography, digital signatures, and certificates;
• describe keys, addresses, wallets, and practical key-management controls;
• construct and verify a Merkle tree;
• explain how blocks, transactions, and authenticated data structures support verification;
• analyze a blockchain ownership scenario and identify security and governance risks.

1. Cryptographic Foundations

1.1 Cryptographic hash functions

A cryptographic hash function maps an input of arbitrary length to a fixed-length output. If H is the hash function and m is the message, the digest is:

Here, m is a bit string of any length and h is a fixed-length bit string. For a 256-bit hash, the output space contains 2²⁵⁶ possible values. The function is deterministic: the same input produces the same digest.

A secure hash function is expected to provide:

• Preimage resistance: given h, it should be computationally infeasible to find m such that H(m) = h.
• Second-preimage resistance: given m₁, it should be infeasible to find a different m₂ with H(m₁) = H(m₂).
• Collision resistance: it should be infeasible to find any distinct pair m₁ and m₂ with the same hash.
• Avalanche behavior: a small input change should produce an apparently unrelated output change.

These are computational properties, not mathematical impossibilities. A collision must exist in any fixed-length hash function because infinitely many inputs map into a finite output space. Security depends on the infeasibility of finding one with available resources.

For an ideal n-bit hash, generic collision search requires approximately 2ⁿᐟ² work because of the birthday effect, while generic preimage search requires approximately 2ⁿ work. Thus, a 256-bit hash is commonly described as offering about 128-bit collision security and 256-bit preimage security, subject to the quality of the algorithm and implementation.

Hashes are used for transaction identifiers, block identifiers, Merkle-tree nodes, commitment schemes, and proof-of-work puzzles. A hash is not encryption: it is not designed to be reversed with a decryption key.

1.2 Hashing in a blockchain

A block header normally commits to information such as the previous block hash, a Merkle root, a timestamp, consensus-related fields, and a consensus parameter such as a nonce. Abstractly:

The header includes a reference to the preceding block, commonly represented as H(Bᵢ₋₁) or a hash of the preceding header. Consequently, changing an old transaction changes its transaction hash, its Merkle root, the block header hash, and every later block that refers to it. This creates tamper evidence, not absolute tamper prevention. A sufficiently powerful adversary might attempt to recompute later blocks, while a consensus protocol determines whether the altered history will be accepted.

1.3 Symmetric and asymmetric cryptography

Symmetric cryptography uses the same secret key for encryption and decryption. It is efficient for large data volumes, but securely distributing the shared key is difficult. Examples include AES and authenticated-encryption modes such as AES-GCM or ChaCha20-Poly1305.

Public-key, or asymmetric, cryptography uses a mathematically related private key and public key. The private key must remain secret; the public key may be distributed. Public-key operations are generally slower than symmetric operations, so practical systems often use asymmetric cryptography to establish or protect a symmetric session key.

Blockchain transaction authorization generally uses digital signatures rather than encryption. A simplified signing relationship is:

and verification is:

where sk is the private key, pk is the corresponding public key, m is the message or transaction digest, and σ is the signature. A valid signature demonstrates control of sk at signing time, assuming the cryptographic algorithm and implementation are secure. It does not prove a person’s legal identity unless a separate identity framework connects the key to that person.

Digital signatures provide:

• authentication of key control;
• message integrity, because a changed message normally fails verification;
• non-repudiation-like evidence, although the legal meaning of non-repudiation depends on jurisdiction, evidence, key custody, and governance.

They do not provide confidentiality. Anyone with the public key can generally verify the signature and read the signed transaction if the transaction is public.

1.4 Randomness and key generation

A private key must be generated using a cryptographically secure random-number generator. Predictable randomness can make an apparently strong algorithm worthless. Reusing a nonce in some signature systems can also reveal the private key. Implementations should therefore use reviewed libraries, secure operating-system randomness, deterministic signing methods where appropriate, and algorithm-specific safeguards.

2. Public-Key Infrastructure, Addresses, and Ownership

2.1 Public-key infrastructure

Public-key infrastructure (PKI) is a framework for binding public keys to identities or roles using certificates, certificate authorities, revocation mechanisms, policies, and validation procedures. In a conventional PKI, a certificate authority signs a certificate stating that a public key belongs to a named subject.

Many permissionless blockchains do not require X.509 certificates or a central certificate authority for ordinary transactions. Instead, users control pseudonymous key pairs, and the protocol validates signatures and spending conditions. Permissioned networks may use PKI to identify organizations, nodes, or employees and to manage access to consensus and transaction services.

PKI and blockchain identity should not be treated as interchangeable. A blockchain address can demonstrate control of a key, while a certificate or verified registry may provide evidence about who or what the key represents.

2.2 Addresses

An address is usually an encoded representation of a public key, a hash of a public key, or a programmable spending condition. It is not necessarily the public key itself. Address formats often include version information and error-detection checksums. Different blockchain networks may use different address schemes, so an address valid on one network may be invalid or dangerous on another.

An address is best understood as a destination or identifier for a locking condition. Possession of an address does not itself prove ownership. Ownership, in the operational blockchain sense, means the ability to satisfy the condition required to spend or transfer the associated asset.

2.3 Wallets

A wallet does not usually contain coins as physical objects. It manages keys and constructs, signs, stores, or displays transactions. Depending on the protocol, a wallet may maintain:

• private keys or seed material;
• public keys and addresses;
• transaction history;
• account or unspent-output state;
• network and fee information;
• backup and recovery metadata.

Wallet categories include:

A seed phrase is commonly a human-readable encoding of high-entropy wallet-generation material. It is not a password and should never be entered into an untrusted website. Anyone obtaining it may be able to derive the wallet’s private keys.

2.4 Key-management lifecycle

Professional key management covers the entire lifecycle:

1. Generation: use audited software and secure entropy.
2. Activation: verify addresses and transaction details before use.
3. Storage: apply encryption, hardware isolation, access control, or multisignature policies.
4. Use: limit signing authority and inspect transaction destinations.
5. Backup: create tested, geographically sensible backups without exposing them.
6. Rotation or migration: move assets when keys, devices, personnel, or policies change.
7. Revocation or retirement: disable compromised or obsolete keys where the protocol supports it.
8. Recovery: rehearse restoration procedures and document authorization.

A backup that has never been restored is only an assumption. Organizations should use separation of duties, dual control, transaction limits, allowlists, tamper-evident procedures, and incident-response plans. Multisignature arrangements reduce dependence on one key but do not eliminate collusion, poor recovery design, or smart-contract errors.

3. Merkle Trees and Authenticated Data Structures

3.1 Merkle-tree construction

A Merkle tree is a hash-based authenticated data structure. Its leaves represent records, commonly transaction hashes. Internal nodes commit to their child nodes. For two child hashes L and R:

where ∥ denotes unambiguous concatenation. The root hash commits to the entire ordered dataset. A verifier can check whether a transaction belongs to the committed set without downloading every transaction, provided the verifier receives the transaction, its authentication path, and the relevant root.

For n leaves in a balanced binary tree, an authentication path normally contains approximately log₂(n) sibling hashes. The proof size is therefore logarithmic in the number of records, although the verifier must also know the leaf position and the tree’s precise construction rules.

If the number of leaves is not a power of two, protocols must specify how uneven levels are handled. Some duplicate the final hash; others use a different tree rule. The rule is part of the commitment and must not be guessed.

3.2 Worked Merkle example

Consider four transaction hashes A, B, C, and D. The tree is:

R is the Merkle root stored in the block header. To prove that C is included, a verifier needs C, its sibling D, the sibling P₁, and the ordering information. It computes P₂ = H(C ∥ D), then R′ = H(P₁ ∥ P₂). Inclusion is accepted if R′ equals the trusted root R.

The proof establishes inclusion in the committed transaction set. It does not, by itself, establish that the transaction is valid, confirmed by final consensus, or authorized by a particular legal person. Those are separate questions.

3.3 Other authenticated structures

A blockchain may use structures other than a simple Merkle tree:

• Merkle Patricia trees combine hashing with trie-like key paths and are useful for state databases.
• Sparse Merkle trees represent a large key space with predictable paths and efficient absence proofs.
• Verkle trees use vector commitments to reduce proof sizes in some designs.
• Accumulator structures can provide compact membership evidence, depending on their cryptographic assumptions.

These structures commonly support light clients, state synchronization, audit proofs, and scalable query verification. Their security depends on collision-resistant hashing or other commitment assumptions, canonical encoding, correct path interpretation, and a trusted or consensus-backed root.

4. Blocks, Transactions, and Verification

A transaction is a structured message expressing a state transition or a transfer authorization. Its fields may include inputs, outputs, amounts, scripts or conditions, fees, sequence values, signatures, and metadata. Exact formats vary by blockchain.

A block commonly contains:

• a header;
• an ordered list of transactions;
• a transaction Merkle root;
• a reference to a previous block;
• consensus-specific fields.

A simplified verification sequence is:

1. decode the data according to the protocol;
2. check transaction syntax and canonical encoding;
3. verify signatures and spending conditions;
4. check balances, nonces, or unspent-output availability;
5. recompute transaction identifiers and the Merkle root;
6. verify the previous-block reference;
7. validate consensus rules and, where applicable, finality evidence;
8. update the local state.

A block hash alone is not a complete validity proof. A verifier must know the correct serialization, hash function, network rules, consensus context, and state against which the transaction is evaluated.

4.1 UTXO and account models

In a UTXO model, transactions consume identifiable unspent outputs and create new outputs. An output contains an amount and a locking condition; an input provides a reference and evidence, often a signature, that the condition may be satisfied. A UTXO cannot normally be spent twice because valid state-transition rules mark it as consumed.

In an account model, the ledger maintains account state such as balances and nonces. A transaction signed by an account key requests a state transition. The nonce helps prevent replay or ambiguous ordering within the account’s transaction sequence.

Both models use cryptography, but their data structures and verification logic differ. A wallet and auditor must use the rules of the specific protocol rather than assumptions transferred from another chain.

5. Applied Case: Supply-Chain Receipt Verification

The following is an illustrative case, not a report of a specific organization.

Background

A pharmaceutical distributor wants hospitals to verify that a shipment receipt has not been altered after dispatch. The distributor operates a permissioned blockchain with authenticated organization identities.

Problem

A spreadsheet-based system allows records to be edited and makes it difficult for a hospital to verify whether a receipt belongs to the original shipment batch. Storing every document directly on-chain would expose sensitive information and increase storage costs.

Analysis

The system needs integrity, provenance, selective disclosure, and manageable key custody. It does not need public disclosure of patient or commercial data. A cryptographic hash can commit to a document without revealing its contents, while a digital signature can identify the organization that approved the receipt. A Merkle tree can commit to many receipts in one block.

Approach

The distributor canonicalizes each receipt so that inconsequential formatting changes do not create different records. It computes a hash of the canonical document, signs the hash with an organizational signing key, and stores the signed record reference on the permissioned ledger. The block stores a Merkle root for the batch. A hospital receives the document, signature, public-key certificate, and Merkle proof. It:

1. canonicalizes the received document using the agreed procedure;
2. recomputes the document hash;
3. verifies the organizational signature;
4. checks the certificate chain and key status;
5. verifies the Merkle proof against the block root;
6. checks that the block is accepted under the network’s consensus and governance rules.

Outcome

An altered receipt produces a different hash and fails signature or Merkle verification. The design reduces on-chain data exposure while allowing independent verification. It does not prove that the physical shipment was genuine, that the original signer acted honestly, or that the certificate authority made no mistake.

Learning points

Cryptography secures statements about digital data. It cannot independently verify real-world facts. Canonicalization, certificate governance, key recovery, role separation, and audit procedures are as important as the hash algorithm.

6. Limitations, Governance, and Ethical Issues

Technical limitations

• Lost private keys can make assets or permissions inaccessible.
• Stolen keys can authorize transactions that are cryptographically valid but unauthorized in a human sense.
• Hashes do not hide low-entropy data: an attacker can hash guesses and compare results.
• Public ledgers may create permanent privacy risks through transaction-linkage analysis.
• Smart contracts can contain logic errors even when their signatures and hashes are correct.
• A valid Merkle proof is meaningful only when the root is authentic and the tree rules are known.
• Quantum computing may affect some public-key schemes in the future; migration planning is therefore relevant for long-lived assets.

Governance and compliance

Organizations must define who may create keys, approve transactions, recover access, investigate incidents, and change protocol rules. Regulatory obligations may include anti-money-laundering controls, data protection, financial reporting, consumer protection, and electronic-signature requirements. Immutability can conflict with data-minimization or deletion obligations; systems should avoid placing unnecessary personal data on an irreversible public ledger.

Best practices

Use well-reviewed cryptographic primitives and libraries; never design custom cryptography for routine production use. Separate keys by purpose and environment. Protect seed phrases and signing devices. Verify destination addresses through independent channels. Use multisignature or threshold controls for high-value operations. Define canonical serialization. Record algorithm, network, version, and tree-construction assumptions. Monitor for compromised keys, rehearse recovery, and subject smart contracts and wallet software to independent testing.

Chapter Summary

Cryptographic hash functions create compact commitments and make unauthorized changes detectable. Digital signatures demonstrate control of private keys and authenticate transaction authorization, but they do not automatically identify a legal person or guarantee that a real-world statement is true. Public-key infrastructure may bind keys to identities in permissioned settings, whereas many public blockchains rely on pseudonymous key control.

Addresses represent destinations or spending conditions, and wallets manage the keys and transaction information needed to use them. Key management is a lifecycle discipline involving generation, storage, use, backup, recovery, rotation, and retirement. Merkle trees and related authenticated data structures allow efficient proofs that records belong to a committed dataset. Blocks combine hash-linked history, transaction commitments, and consensus validation. In every application, cryptography must be complemented by sound serialization, governance, privacy controls, operational security, and realistic assumptions about the physical world.

Key Terms

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

Digest: The fixed-length output of a hash function.

Collision resistance: The property that finding two different inputs with the same digest is computationally difficult.

Preimage resistance: The difficulty of finding an input that produces a specified digest.

Digital signature: Cryptographic evidence produced with a private key and verified with a public key.

Private key: Secret cryptographic material used to sign or authorize operations.

Public key: The key shared for signature verification or other public-key operations.

PKI: A framework for certificates, authorities, policies, and key-status management.

Address: An encoded public key, key hash, or spending condition used as a destination.

Wallet: Software or hardware that manages keys and transaction operations.

Seed phrase: A human-readable representation of wallet-generation material.

Multisignature: A control scheme requiring signatures from multiple keys.

Merkle tree: A hash-based tree whose root commits to a set or ordered list of records.

Merkle root: The top hash of a Merkle tree.

Authentication path: Sibling hashes and ordering data used to verify Merkle inclusion.

Authenticated data structure: A structure supporting efficient proofs about committed data.

UTXO: An unspent transaction output that can be consumed by a later transaction.

Account model: A ledger model maintaining balances and other state for accounts.

Canonicalization: Converting equivalent data into one agreed representation before hashing or signing.

Tamper evidence: The ability to detect modification, rather than an absolute guarantee that modification cannot occur.

Review Questions

5 Short Answer Questions

1. What is the difference between a hash function and encryption?
2. What information does a digital signature provide, and what does it not provide?
3. Why is a private key more sensitive than a public key?
4. What is the purpose of a Merkle root?
5. Why must a blockchain address not automatically be treated as proof of legal identity?

5 Long Answer Questions

1. Explain how a change to a transaction can affect a block and subsequent blocks.
2. Compare custodial, software, hardware, and multisignature wallets, including their principal risks.
3. Describe the construction and verification of a Merkle proof for a four-leaf tree.
4. Compare UTXO and account-based models in terms of state representation and transaction verification.
5. Discuss why key management and governance are as important as cryptographic algorithms in an enterprise blockchain.

3 Analytical / Application Questions

1. A hospital receives a digitally signed supply-chain document and a Merkle proof, but the certificate used to identify the signer has expired. Analyze which claims can still be verified and which require additional evidence.
2. Design a key-management policy for a treasury wallet holding high-value assets. Identify controls for generation, daily use, backup, recovery, personnel changes, and compromise.
3. A developer proposes storing patients’ names and medical records directly on a public blockchain because the ledger is immutable. Evaluate the proposal and recommend a cryptographically informed alternative.

Multiple Choice Questions with Answers

Question 1

Which property makes it difficult to find two different inputs with the same hash output?

A. Collision resistance

B. Confidentiality

C. Key escrow

D. Compression

Correct Answer: A. Collision resistance

Question 2

What does a digital signature primarily demonstrate in a blockchain transaction?

A. That the transaction is private

B. Control of the relevant private key and integrity of the signed message

C. That the transaction is legally approved in every jurisdiction

D. That the transaction cannot ever be reversed by consensus

Correct Answer: B. Control of the relevant private key and integrity of the signed message

Question 3

For an ideal 256-bit hash function, generic collision search requires approximately what amount of work?

A. 2²⁵⁶

B. 2¹²⁸

C. 256²

D. 2⁶⁴

Correct Answer: B. 2¹²⁸

Question 4

What does a Merkle proof normally establish?

A. That a private key is valid

B. That a record belongs to a dataset committed by a specified root

C. That the real-world event described by a record occurred

D. That a block producer acted honestly

Correct Answer: B. That a record belongs to a dataset committed by a specified root

Question 5

Which wallet arrangement requires signatures from multiple keys before authorization?

A. Single-key custodial wallet

B. Multisignature wallet

C. Read-only address

D. Hash pointer

Correct Answer: B. Multisignature wallet

Question 6

In the expression P = H(L ∥ R), what do L and R represent?

A. The left and right child hashes

B. The ledger and root balances

C. The local and remote wallets

D. The login and recovery passwords

Correct Answer: A. The left and right child hashes

Question 7

Which statement about a blockchain address is most accurate?

A. It is always the private key in encoded form

B. It necessarily identifies a person by legal name

C. It may encode a public key, key hash, or spending condition

D. It is a substitute for transaction verification

Correct Answer: C. It may encode a public key, key hash, or spending condition

Question 8

Why is canonicalization important before hashing a document?

A. It guarantees that the document is truthful

B. It ensures agreed equivalent representations produce the same hash

C. It encrypts the document contents

D. It eliminates the need for a signature

Correct Answer: B. It ensures agreed equivalent representations produce the same hash

Question 9

In a UTXO model, a valid transaction normally does what to an input UTXO?

A. Consumes it so it cannot normally be spent again

B. Converts it into a certificate authority

C. Uses it only as a public-key password

D. Leaves it permanently unreferenced

Correct Answer: A. Consumes it so it cannot normally be spent again

Question 10

What is a major limitation of cryptographic verification in a supply-chain application?

A. It cannot detect any digital alteration

B. It cannot independently prove that the physical goods were genuine

C. It prevents all authorized users from signing

D. It requires every document to be stored in plaintext on-chain

Correct Answer: B. It cannot independently prove that the physical goods were genuine