Cryptographic and Data-Structure Foundations

Introduction and Context

Blockchain systems are built from established areas of computer science rather than from a single new invention. Cryptographic primitives protect information and authorize actions; data structures organize transactions and states; distributed protocols determine which records are accepted. A sound understanding of these foundations is essential for designing, using, and auditing blockchain applications.

A blockchain does not make information automatically true, private, permanent, or legally valid. Instead, it provides mechanisms for detecting alteration, proving control of credentials, ordering records, and reaching agreement among participants. The security achieved depends on correct algorithms, sound implementation, secure key custody, appropriate assumptions, and honest interpretation of what the system proves.

Learning Objectives

After studying this chapter, you should be able to:

• explain cryptographic hash functions and their security properties;
• distinguish symmetric cryptography, public-key cryptography, and digital signatures;
• describe key generation, addresses, wallets, and custody risks;
• construct and verify a Merkle tree and explain authenticated data structures;
• compare commitment schemes and explain their applications;
• analyze practical, governance, privacy, and quantum-related limitations.

1. Cryptography as a Security Foundation

Cryptography transforms information using mathematical algorithms and secret or public parameters. Its principal goals are confidentiality, integrity, authentication, and non-repudiation. These goals are related but not identical.

Confidentiality prevents unauthorized disclosure. Integrity allows a recipient to detect modification. Authentication provides evidence about the identity or control associated with a message. Non-repudiation is a broader legal and operational claim that a signer cannot reasonably deny an action; a digital signature alone does not guarantee it, because key theft, coercion, poor custody, and legal rules remain relevant.

Blockchain systems most commonly use cryptography for integrity, authorization, and compact data verification. Public blockchains often expose transaction data, so cryptography should not be confused with privacy.

Cryptographic assumptions

Security claims are conditional. They may assume that an adversary cannot efficiently reverse a hash, cannot guess a secret key, cannot forge a signature, or controls less than a specified portion of a consensus resource. “Computationally infeasible” means that the required work is beyond practical resources for the relevant time period; it does not mean mathematically impossible.

Security also depends on randomness. If a private key or nonce is generated using predictable randomness, a theoretically strong algorithm can become insecure. Implementations must therefore use a vetted cryptographic library and an operating-system or hardware-backed source of cryptographically secure randomness.

2. Hash Functions

A cryptographic hash function maps an input of arbitrary length to a fixed-length output, often called a digest:

Here, m is the message, H is the hash function, and h is the digest. A hash is not encryption: there is normally no secret key and no decryption operation.

Important properties include:

• Determinism: the same input produces the same digest.
• Fixed output size: inputs of different lengths produce outputs of the algorithm’s specified length.
• Preimage resistance: given h, finding a message m such that H(m) = h should be infeasible.
• Second-preimage resistance: given m₁, finding a different m₂ with the same digest should be infeasible.
• Collision resistance: finding any two distinct messages with the same digest should be infeasible.
• Avalanche behavior: a small input change should produce an apparently unrelated digest.

For an ideal n-bit hash, generic collision search requires approximately 2^n/2 evaluations because of the birthday effect, while generic preimage search requires approximately 2ⁿ evaluations. These are security estimates under idealized assumptions, not guarantees for every algorithm or implementation.

A hash provides integrity only when the reference digest is itself protected. If an attacker can replace both a file and its published hash, comparison proves nothing. Blockchains strengthen this arrangement by placing hashes into signed transactions, block headers, and consensus-protected histories.

Hashes in blockchain systems

Hashes can identify transactions, link a block to its predecessor, summarize a set of transactions, derive identifiers, and support proof-of-work. A block commonly contains a previous-block hash, a transaction-root hash, metadata, and a consensus-related value. Changing an earlier transaction changes its transaction hash, which changes the root and therefore invalidates later references.

Hashing does not prove that a transaction is economically valid. A digest cannot determine whether a sender had sufficient balance, whether an input was previously spent, or whether a smart contract’s rules were followed. Those questions require state validation and consensus rules.

3. Symmetric and Public-Key Cryptography

Symmetric encryption uses the same secret key for encryption and decryption. It is efficient for bulk data but creates a key-distribution problem: communicating parties must obtain the shared secret securely. Authenticated encryption, such as a modern authenticated-encryption mode, combines confidentiality with detection of unauthorized modification. Reusing a nonce where an algorithm forbids reuse can expose plaintext or destroy integrity.

Public-key cryptography uses a mathematically related key pair: a public key that may be distributed and a private key that must remain secret. Different systems use different mathematical problems, including factoring, discrete logarithms, and elliptic-curve discrete logarithms.

A public-key encryption system typically uses the recipient’s public key for encryption and the private key for decryption. A digital-signature system uses the private key to create a signature and the public key to verify it. These operations should not be conceptually conflated.

Digital signatures

For a message m, a signature scheme can be represented abstractly as:

and verification as:

sk is the private key, pk is the public key, and σ is the signature. In practice, the message is usually hashed before signing, and the signature algorithm applies a precisely specified encoding and domain separation procedure.

A valid signature normally demonstrates that the holder of the private key authorized the exact message or transaction under the scheme’s verification rules. It does not prove that the person understood the transaction, that the key was not stolen, or that the transaction is accepted by a blockchain. Nodes still check syntax, signatures, balances, replay protections, and consensus validity.

A signature scheme should provide existential unforgeability under chosen-message attack, commonly abbreviated EUF-CMA. Informally, even after obtaining signatures on messages selected by an attacker, the attacker should not be able to produce a valid signature on a new message. This is a security model, not a guarantee against implementation mistakes.

4. Key Generation, Addresses, Wallets, and Custody

A private key is secret cryptographic material, not an account balance. A balance or asset record is maintained by the relevant ledger rules. The private key authorizes operations that the system associates with a public key or address.

A simplified key-generation sequence is:

1. obtain high-quality random entropy;
2. sample a private key from the algorithm’s valid range;
3. derive the public key using the specified public-key operation;
4. encode or derive an address according to the protocol;
5. protect backup material and test recovery before holding value.

An address is generally an encoded identifier derived from a public key, script, or account rule. It is not necessarily the public key itself. Address formats often include version information and error-detecting checksums, but a checksum detects accidental errors; it does not authenticate the sender or make an address secret.

Wallet software manages keys and constructs transactions. A wallet may be custodial, where another organization controls the private keys, or non-custodial, where the user controls them. Hardware wallets isolate signing operations, while multisignature or threshold systems distribute authorization across several keys or devices.

A professional custody policy should define key generation, access roles, geographic separation, backups, recovery, rotation, incident response, and transaction approval limits. Seed phrases and private keys must never be entered into untrusted websites or transmitted through ordinary messaging channels.

5. Merkle Trees and Authenticated Data Structures

A Merkle tree is a hash-based commitment to a collection of leaves. In a binary tree, leaf values are hashed and adjacent child hashes are combined recursively until one root remains:

Here, h_2i and h_2i+1 are child hashes, || denotes concatenation under the protocol’s encoding rules, and p_i is the parent hash. The exact treatment of an odd number of leaves is protocol-specific: a system may duplicate the last leaf, use a special rule, or construct an unbalanced tree. This rule must be unambiguous.

A Merkle proof contains the target leaf and the sibling hashes along its path to the root. If the tree has N leaves and is balanced, the proof normally contains about log₂ N sibling hashes. Verification recomputes the path and compares the result with the trusted root. The verifier does not need every leaf.

Worked example

Suppose four leaf digests are a, b, c, and d. Define:

The Merkle root is r. To prove that c is included, the claimant supplies c, sibling d, and sibling x. The verifier computes y = H(c || d) and then r' = H(x || y). Inclusion is accepted only if r' = r, assuming the root is authentic and the encoding is canonical.

Merkle trees reduce proof size and verification work, but they do not by themselves establish that the root is current, honest, or associated with the correct dataset. The root must be authenticated through a signed message, consensus-confirmed block, trusted checkpoint, or another secure channel.

Authenticated data structures generalize this idea. They allow a prover to answer queries together with evidence that the answer is consistent with a committed structure. Examples include Merkleized key-value maps, sparse Merkle trees, and authenticated sets. They are useful for light clients, verifiable databases, rollups, and transparency logs.

6. Commitment Schemes

A commitment scheme lets one party commit to a value while keeping it hidden until a later reveal. It has two core properties:

• Hiding: the commitment should not reveal the value before opening.
• Binding: after committing, the committer should not be able to open the commitment to two different values.

A simple hash commitment is:

m is the message and s is a randomly generated secret nonce or salt. To open the commitment, the committer reveals m and s. The verifier recomputes the hash. The nonce is important when m comes from a small or guessable set; without it, an observer could try every possible value.

Hash commitments are computationally binding and, under suitable conditions, computationally hiding. The precise strength depends on the hash function, nonce size, message distribution, and protocol encoding. A commitment is not automatically encryption: it is normally not intended to be recoverable by anyone lacking the opening information.

Commitments support sealed-bid auctions, commit-reveal randomness, confidential voting designs, state channels, and zero-knowledge protocols. A commit-reveal protocol must also address aborts: a participant may commit and then refuse to reveal. Time limits, deposits, penalties, or alternative fallback rules may be necessary.

7. Privacy and Zero-Knowledge Perspectives

Pseudonymous addresses do not guarantee anonymity. Transaction graphs, timing, amounts, network metadata, exchange records, and repeated address use can permit attribution. Address reuse also makes activity correlation easier. Privacy engineering should therefore consider data minimization, selective disclosure, encryption, access control, and legal obligations.

Zero-knowledge proofs allow a prover to demonstrate that a statement is true without revealing all underlying data. In a blockchain application, a proof might show that a transaction satisfies a balance or computation constraint while revealing limited information. Such systems require careful circuit design, soundness analysis, trusted-setup or transparent-setup choices, and operational key management. Zero knowledge does not mean “no information leaks”; proof size, timing, public inputs, metadata, and implementation behavior may still reveal information.

8. Limitations and Quantum-Related Risks

Cryptography has operational limitations. Hashes do not repair weak authentication; signatures do not prevent phishing; encryption does not protect data after decryption; and immutability can make incorrect or unlawful data difficult to remove. Smart-contract code may contain logic errors even when its cryptographic primitives are sound.

Large-scale quantum computers could threaten widely deployed public-key systems based on factoring or discrete logarithms through Shor’s algorithm. Hash functions are affected differently: Grover’s algorithm can provide an idealized quadratic speedup for brute-force search. Consequently, a hash with n-bit output is often discussed as offering roughly n/2 bits of generic quantum preimage security, subject to models and implementation constraints. Increasing hash output length can mitigate this risk, whereas migrating public-key signatures requires protocol and key-management changes.

Post-quantum cryptography seeks algorithms believed resistant to known quantum attacks. Migration is difficult because blockchains must coordinate new address formats, signature verification rules, transaction sizes, fees, hardware support, and treatment of old exposed public keys. “Harvest now, decrypt later” is especially relevant to long-lived encrypted data. Organizations should inventory cryptographic dependencies, avoid unnecessary exposure of public keys, support algorithm agility, and monitor standards-based migration plans.

9. Applied Case: Verifiable Academic Credentials

Background. A university wants employers to verify certificates without repeatedly contacting a central office. Certificates contain student identifiers, program information, award dates, and signatures.

Problem. Publishing complete certificates on a public blockchain would expose personal data and make correction or revocation difficult. A simple database lookup also creates dependence on the university’s availability.

Analysis. The university can issue a digitally signed credential to the graduate and publish only a commitment or Merkle root representing a revocation and status registry. The credential remains off-chain, while the public record provides evidence that a particular status entry was included at a stated time. The verifier checks the university’s public-key signature, validates the certificate fields, checks a Merkle inclusion proof where applicable, and consults the revocation policy.

Approach. Use canonical serialization, a vetted signature scheme, key rotation, an offline or hardware-protected issuing key, explicit consent, and a documented recovery process. Store only the minimum public information. Provide a status mechanism capable of handling expiration and revocation without pretending that historical publication can be erased.

Outcome. Employers gain independently verifiable evidence, while sensitive certificate contents remain with the holder. The design still depends on the university’s governance: the cryptography proves issuance by a key, not the truth of every institutional claim.

Learning points. Data minimization is preferable to placing personal data directly on-chain. Verification requires both cryptographic checks and interpretation of issuer policy. Key compromise, revocation, privacy law, and long-term algorithm migration must be planned from the beginning.

10. Best Practices for Blockchain Developers

1. Use standardized, reviewed cryptographic libraries; do not design new primitives casually.
2. Use cryptographically secure randomness and follow protocol-specific nonce requirements.
3. Define canonical serialization and domain separation to prevent ambiguity and cross-protocol attacks.
4. Separate signing, encryption, hashing, address derivation, and identity claims conceptually and technically.
5. Protect private keys with hardware, least privilege, multisignature controls, and tested recovery procedures.
6. Treat Merkle roots and commitments as authenticated only when their provenance is secure.
7. Avoid placing personal or easily linkable data on public ledgers unless a lawful, justified design exists.
8. Test malformed inputs, replay attempts, signature edge cases, tree-boundary cases, and key-rotation procedures.
9. Record algorithm identifiers and plan cryptographic agility for future migration.
10. Communicate limitations honestly: cryptographic validity is not the same as factual, legal, or economic validity.

Chapter Summary

Blockchain security relies on cryptographic and data-structural foundations. Hash functions provide fixed-length integrity digests and support transaction identifiers, block links, and Merkle roots. Public-key cryptography enables signatures, while private keys authorize actions and therefore require rigorous custody. Addresses are protocol-level identifiers rather than secrets or balances.

Merkle trees and authenticated data structures allow compact proofs of inclusion or consistency, provided that the root is trusted and encoding rules are unambiguous. Commitment schemes provide delayed disclosure through hiding and binding properties. None of these mechanisms automatically provides privacy, truth, legal validity, or recovery from key loss. Quantum computing may weaken current public-key systems and reduce the effective security of hash search, making inventory, agility, and migration planning essential.

Key Terms

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

Digest: The output produced by a hash function.

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

Preimage resistance: Difficulty of recovering an input from a given hash.

Private key: Secret value used for cryptographic authorization or decryption.

Public key: Public value mathematically associated with a private key.

Digital signature: Verifiable evidence generated with a private key over specified data.

Address: Protocol-specific identifier derived from a key, script, or account rule.

Wallet: Software or hardware that manages keys and creates or authorizes transactions.

Custody: Operational control and protection of cryptographic keys.

Multisignature: Authorization requiring signatures from multiple designated keys.

Merkle tree: A hash tree whose root commits to a collection of leaves.

Merkle proof: Sibling-hash evidence used to verify a leaf’s relation to a root.

Authenticated data structure: A structure supporting queries with cryptographic consistency evidence.

Commitment scheme: A method for binding a party to a value while initially concealing it.

Hiding: The property that a commitment does not reveal its value before opening.

Binding: The property that a commitment cannot feasibly be opened to different values.

Domain separation: Using distinct encodings or prefixes to prevent cross-context interpretation.

Post-quantum cryptography: Cryptography designed to resist known classical and quantum attacks.

Review Questions

5 Short Answer Questions

1. What is the difference between collision resistance and preimage resistance?
2. Why is a digital signature not equivalent to encryption?
3. What information does a Merkle proof allow a verifier to establish?
4. Why should a hash commitment include a random nonce?
5. Identify two risks associated with private-key custody.

5 Long Answer Questions

1. Explain how hashes, digital signatures, and consensus work together to protect a blockchain transaction.
2. Describe the complete lifecycle of a key, from generation through backup, use, rotation, and revocation.
3. Construct and explain a four-leaf Merkle tree, including the proof needed for one leaf.
4. Compare custodial, single-key, hardware-backed, and multisignature custody models.
5. Discuss why public blockchains provide pseudonymity rather than guaranteed anonymity.

3 Analytical / Application Questions

1. Design a commitment-based sealed-bid auction and analyze how you would prevent participants from refusing to reveal their bids.
2. A university proposes storing complete student certificates on a public blockchain. Evaluate the proposal and recommend a privacy-preserving alternative.
3. A blockchain team plans to continue using an elliptic-curve signature scheme indefinitely. Prepare a migration analysis addressing quantum risk, key exposure, transaction size, backward compatibility, and governance.

Multiple Choice Questions with Answers

Question 1

Which property makes it difficult to find two distinct messages with the same hash?

A. Collision resistance

B. Confidentiality

C. Key escrow

D. Forward secrecy

Correct Answer: A. Collision resistance

Question 2

What does a digital signature primarily demonstrate when verification succeeds?

A. The message is encrypted

B. The holder of the private key authorized the specified data

C. The transaction is economically valid

D. The signer is legally liable in every jurisdiction

Correct Answer: B. The holder of the private key authorized the specified data

Question 3

In a Merkle tree, what does the root commit to?

A. Only the first leaf

B. A collection of leaves under the tree’s construction rules

C. The private keys of all users

D. The consensus algorithm’s source code

Correct Answer: B. A collection of leaves under the tree’s construction rules

Question 4

What is the main purpose of the random value in C = H(m || s)?

A. To make the message longer for storage

B. To prevent guessing a low-entropy message from the commitment

C. To encrypt the hash with a public key

D. To replace the need for verification

Correct Answer: B. To prevent guessing a low-entropy message from the commitment

Question 5

Which statement about an address is most accurate?

A. It is always identical to the private key

B. It is generally an encoded identifier derived from a key or spending rule

C. It is a guarantee that the holder is known

D. It contains the entire blockchain balance

Correct Answer: B. It is generally an encoded identifier derived from a key or spending rule

Question 6

For an ideal 256-bit hash, generic collision search is approximately associated with which work factor?

A. 2³2 evaluations

B. 2⁶4 evaluations

C. 2¹28 evaluations

D. 2²56 evaluations

Correct Answer: C. 2¹28 evaluations

Question 7

Which custody arrangement prevents one individual key from authorizing a transaction alone?

A. Plaintext backup

B. Multisignature authorization

C. Address reuse

D. Hash truncation

Correct Answer: B. Multisignature authorization

Question 8

What is a central limitation of publishing personal data directly on a public blockchain?

A. The data cannot be hashed

B. Historical publication may be difficult to remove and may expose privacy-sensitive information

C. Digital signatures cannot be verified publicly

D. Merkle trees require plaintext private keys

Correct Answer: B. Historical publication may be difficult to remove and may expose privacy-sensitive information

Question 9

Which cryptographic primitive is most directly threatened by Shor’s algorithm in commonly deployed systems?

A. Public-key systems based on factoring or discrete logarithms

B. All hash functions equally

C. Checksums only

D. Random file names only

Correct Answer: A. Public-key systems based on factoring or discrete logarithms

Question 10

What must be trusted for a Merkle inclusion proof to be meaningful?

A. The claimant’s screen resolution

B. The provenance and authenticity of the Merkle root

C. The number of wallet applications installed

D. The length of the transaction description

Correct Answer: B. The provenance and authenticity of the Merkle root