Blockchain Architecture and Cryptographic Data Structures

Introduction

A blockchain is not merely a database replicated across computers. It is a coordinated system of data structures, cryptographic commitments, consensus rules, and validation procedures. Its security depends on how transactions are represented, how blocks reference earlier blocks, how membership in a set is proven, and how authority is distributed among participants.

This chapter analyses the principal architectural models used in blockchain systems: the unspent transaction output (UTXO) model, the account-based model, and permissioned ledger models. It also explains hash pointers, Merkle trees, Patricia tries, addresses, scripts, and the concept of an immutable ledger. The emphasis is on understanding what each structure guarantees, what it does not guarantee, and why implementation choices affect scalability, privacy, governance, and security.

Learning Objectives

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

1. Explain how transactions and blocks are structured.
2. Describe the security role of cryptographic hash functions and hash pointers.
3. Construct and verify a simple Merkle tree.
4. Compare UTXO, account-based, and permissioned ledger architectures.
5. Explain blockchain addresses, scripts, and state-transition validation.
6. Distinguish tamper evidence from absolute immutability.
7. Analyse practical security, governance, and operational implications.

1. Blockchain as a State-Transition System

A blockchain records a sequence of valid state transitions. Let S_t denote the ledger state at time or height t, and let T_t denote a proposed transaction or transaction set. A valid transition can be expressed as:

Here, F is the protocol-defined state-transition function. The equation is conceptual rather than a universal implementation formula. It applies only when the transaction satisfies the protocol’s signature, balance, format, permission, and consensus rules. Invalid transactions do not produce an accepted next state.

A block normally contains a header and a body. The header commits to metadata such as the previous block, transaction summary, timestamp or logical time, and consensus-related information. The body contains transactions or other state updates. Nodes independently validate the block rather than trusting the producer’s assertion.

A simplified block relationship is:

B_i is block i, H_i is its header, and D_i is its data. The notation H_i.prev means that the current header stores a cryptographic digest of the preceding header. The function hash is assumed to be collision-resistant and deterministic.

2. Cryptographic Hashes and Hash Pointers

A cryptographic hash function maps an input of arbitrary length to a fixed-length output. Important security properties include:

• 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 should produce an apparently unrelated digest.

A hash pointer is a reference that contains both the location of data and a cryptographic digest of that data. A conventional database pointer identifies where data is stored; a hash pointer also permits integrity verification. If the referenced object changes, recomputation produces a different digest.

In a chain of blocks, altering an old transaction changes its transaction commitment, which changes the block header, which changes the next block’s previous-hash field. Every subsequent link must therefore be recomputed. This creates tamper evidence, not mathematical impossibility. A sufficiently powerful adversary might rewrite history if it can satisfy the relevant consensus and network conditions.

Block Headers and Consensus

In proof-of-work systems, a block header may include a nonce. A miner searches for a header hash below a target. If h is the numerical value of the hash and T is the target, the acceptance condition is:

The hash is interpreted as an integer and the target is protocol-defined. This condition demonstrates proof of computational work; it does not by itself prove that transactions are valid. Nodes must separately validate the block’s transactions and consensus rules.

In proof-of-stake and permissioned systems, block acceptance is established through different mechanisms, such as validator signatures, voting, or a trusted ordering protocol. Hash pointers remain useful even when proof-of-work is absent.

3. Transactions and Validation

A transaction is a signed instruction to change ledger state. Common fields include:

A validator typically checks syntax, authorization, conservation of value, replay protection, and compliance with application rules. A digital signature provides authenticity and integrity of a message under the assumptions of the signature scheme and key management system. It does not prove that the signer is morally entitled to act, nor does it recover lost private keys.

A transaction identifier is often a hash of serialized transaction data. Serialization is security-critical: two nodes must hash exactly the same byte sequence. Ambiguous encodings can produce inconsistent identifiers or permit signature-malleability problems.

4. The UTXO Model

The UTXO model represents value as discrete unspent transaction outputs. An output contains an amount and a spending condition, commonly a script. An output is either unspent and available for a future transaction, or spent and permanently unavailable.

A UTXO transaction consumes one or more existing outputs and creates new outputs. A simplified conservation relationship is:

The summations refer to the values of all consumed inputs and created outputs. The equality assumes no protocol-specific issuance, destruction, or special subsidy within the transaction. In systems that permit issuance, the more general relation must include the permitted issuance or burn term.

Example

Suppose a wallet controls UTXOs worth 4 units and 3 units. It pays 5 units to a recipient and assigns a fee of 0.2 units. The change output is:

The transaction has two inputs, a recipient output of 5 units, a change output of 1.8 units, and a fee of 0.2 units. The input values are not altered; they are consumed and replaced by new outputs.

Strengths and Limitations

UTXO systems make double-spending checks conceptually direct: a particular output must not be consumed twice. Independent inputs can often be validated in parallel. They also support useful privacy practices because a transaction can use fresh change addresses. However, UTXO selection can be complex, transactions may become large when many small outputs are collected, and application developers must reason about ownership conditions rather than simply updating a balance.

5. The Account-Based Model

Account-based ledgers maintain a state record for each account. An account may contain a balance, a sequence number or nonce, executable code, and persistent storage. A transaction identifies a sender, recipient or contract, value, fee parameters, and authorization data.

A simple balance transition is:

These equations describe an ordinary transfer under the assumptions that the sender has sufficient spendable balance, the transaction is authorized, and the fee is paid from the sender. A nonce normally ensures that an old transaction cannot be replayed indefinitely and that two conflicting transactions from the same account are ordered.

Account systems are often intuitive for users and well suited to smart contracts with persistent state. Their challenges include managing concurrent transactions, preventing nonce errors, and calculating the effect of complex contract execution. A ledger may also need a mechanism for proving that an account’s current balance and storage are included in the committed state.

UTXO and Account Comparison

Neither model is universally superior. The appropriate choice depends on privacy goals, execution requirements, throughput design, and application semantics.

6. Merkle Trees

A Merkle tree is a hash-based commitment structure that allows a root digest to represent a set or ordered list of records. At the leaves, each transaction is hashed. Parent nodes are hashes of their child digests. The root is placed in a block header or another authenticated structure.

For two child hashes, a parent may be computed as:

L and R are the left and right child hashes, and || denotes unambiguous concatenation. Domain separation or length-preserving encoding is important in secure designs so that leaf and internal-node interpretations cannot be confused.

For n leaves in a balanced binary tree, a membership proof normally contains approximately log₂ n sibling hashes, rather than all n transactions. If the tree is not a power of two, the protocol must specify how unpaired nodes are handled; possibilities include promotion, duplication, or a defined padding rule. These choices affect the root and must not be assumed interchangeably.

Worked Merkle Example

Assume four transaction digests A, B, C, and D. The tree is:

To prove that C is included, a verifier needs D and P_AB, together with left/right position information. It recomputes P_CD and then the root. If the result equals the block’s committed root, the transaction is included in that committed set, assuming the root itself is authentic and the tree construction rules are known.

A Merkle proof proves inclusion, not validity, ownership, or finality. A dishonest party could present a valid proof for a transaction in an unfinalized or invalid branch unless the block and consensus evidence are also authenticated.

7. Patricia Tries and Authenticated State

A Patricia trie is a compressed prefix tree. Keys are divided according to their bits or hexadecimal nibbles, while paths with unnecessary single-child nodes are compressed. An authenticated Patricia trie hashes nodes so that its root commits to key-value associations.

An account address may be used as a key, with the value containing balance, nonce, code reference, or storage root. A state root in a block header then commits to the complete logical state. A proof of presence or absence provides the relevant branch nodes needed to reconstruct the root.

Compared with a simple Merkle tree, a trie naturally supports key-based lookup and can represent sparse namespaces. Its costs include more complex node encoding, updates, proof formats, and database management. Security depends on canonical serialization, correct path handling, collision-resistant hashing, and unambiguous treatment of absent keys.

8. Addresses, Keys, and Scripts

An address is a representation used to identify a destination or spending condition. It is not necessarily a public key. Some addresses encode a hash of a public key; others identify a script, contract, or account. Address formats commonly include version information and error-detection checksums.

A private key authorizes operations through a digital signature. A public key enables verification, while an address provides a user-facing or protocol-facing identifier. Good systems separate these concepts because exposing a public key, reusing an address, or mishandling a private key can create privacy and security risks.

Scripts are programs or predicates that determine whether a transaction may spend an output or alter state. A restrictive script may require a valid signature corresponding to a specified public key. More advanced scripts can require multiple signatures, time conditions, hash preimages, or threshold approvals.

Scripts should be analysed in terms of:

• Authorization: who or what may act?
• Conditions: what evidence is required?
• Resource limits: how much computation or data is permitted?
• Failure behaviour: what happens when execution fails?
• Upgrade policy: can the rules change, and who controls that change?

Turing-complete smart contracts increase expressive power but also introduce risks such as re-entrancy, arithmetic errors, denial of service, unsafe access control, and dependency vulnerabilities. Formal review, testing, constrained interfaces, and carefully designed upgrade mechanisms are therefore essential.

9. Permissioned Blockchain Architecture

Permissioned blockchains restrict participation in validation, transaction submission, or data access. Membership may be managed by certificates, organizational identities, or governance-approved roles. Consensus may use crash fault tolerant or Byzantine fault tolerant protocols rather than open mining.

A permissioned ledger commonly separates:

1. Identity and membership: which organizations may participate?
2. Ordering: in what sequence are transactions committed?
3. Endorsement or validation: which parties must approve a transaction?
4. State storage: what data is replicated, private, or confidential?
5. Governance: who changes rules, membership, or software?

Permissioning can improve privacy, accountability, and predictable performance, but it changes the trust model. The ledger is not trustless merely because it uses hashes. Participants must trust the membership authority, consensus operators, certificate infrastructure, and governance process. Collusion, administrative abuse, or coordinated censorship remain possible.

10. Immutability, Finality, and Governance

“Immutable ledger” is best understood as a layered property. Cryptographic commitments make unauthorized changes detectable. Consensus makes some histories more authoritative than competing histories. Operational controls, backups, and governance determine whether corrections, reversals, or forks can occur.

Three concepts should be distinguished:

• Tamper evidence: alteration changes a commitment and can be detected.
• Probabilistic finality: the probability of reversal decreases as additional blocks or confirmations accumulate.
• Deterministic finality: a protocol rule declares a transaction final once specified conditions are met.

Immutability can conflict with legal duties such as correction, deletion, confidentiality, or dispute resolution. Sensitive personal data should generally not be placed directly on a public immutable ledger. Hashing personal data does not automatically make it anonymous: if the original data or a small search space is available, the hash may be linkable or reversible through guessing.

Practical designs often store sensitive content off-chain and place a commitment, pointer, or proof on-chain. This reduces exposure but introduces availability, integrity, retention, and governance dependencies.

11. Applied Case: Trade-Document Verification

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

Background

Several importers, exporters, banks, insurers, and logistics firms exchange bills of lading and inspection certificates. Reconciliation is slow because each organization maintains a separate database.

Problem

A participant could submit an outdated document, and counterparties had difficulty proving which version was authoritative. Full document publication would expose commercially sensitive information.

Analysis

The participants require shared ordering, authenticated identities, document-version commitments, and selective disclosure. A public UTXO ledger would not naturally express organizational permissions or confidential documents. A permissioned ledger with an authenticated state structure is more suitable.

Approach

The consortium uses a permissioned network. Each organization receives a certificate from a membership authority. A document is stored in controlled off-chain storage; its canonical byte representation is hashed. The document hash, issuer identity, timestamp, and status are recorded on-chain. A transaction updates the relevant shipment record, and endorsing organizations sign the update. A Merkle or trie-based state root allows replicas to prove that a document commitment belongs to the agreed ledger state.

Outcome

Participants can detect whether a presented document matches the committed version and can identify the issuing organization. Confidential content remains off-chain. The system does not eliminate trust: members must trust the certificate authority, document custodians, and governance rules.

Learning Points

The case illustrates that architecture follows requirements. A hash proves consistency with a commitment, not the truth of the underlying document. Permissioned consensus improves organizational control but creates governance dependencies. Off-chain storage protects confidentiality but creates availability and retention obligations.

12. Security and Professional Best Practices

• Define the threat model before selecting a ledger model.
• Use reviewed cryptographic libraries rather than implementing primitives from scratch.
• Specify canonical serialization and domain separation.
• Protect private keys with hardware-backed or multisignature controls where appropriate.
• Validate signatures, nonces, output status, authorization, and resource limits independently.
• Treat block confirmations and finality according to the actual consensus protocol.
• Audit smart contracts and test failure paths, not only successful paths.
• Minimize personal and confidential data on immutable infrastructure.
• Document governance, upgrade, incident-response, and dispute-resolution procedures.
• Monitor dependencies, certificate expiry, validator behaviour, and state-database integrity.

Contemporary development is moving toward succinct proofs, rollups, verifiable computation, confidential transactions, threshold signatures, and interoperable state proofs. These techniques can improve scalability or privacy, but they add assumptions and implementation complexity. A security claim should therefore identify its cryptographic assumptions, trusted parties, proof system, and failure modes.

Chapter Summary

Blockchain architecture combines cryptographic commitments with state-transition rules and consensus. Hash pointers link blocks and make historical modification evident. Merkle trees commit efficiently to transaction sets and support logarithmic-size inclusion proofs. Patricia tries provide authenticated key-value state commitments suited to accounts and contract storage.

UTXO ledgers represent value as individually spendable outputs, while account-based ledgers update balances, nonces, code, and storage. UTXO systems offer clear double-spend semantics and potential validation parallelism; account systems provide a natural model for persistent application state. Permissioned ledgers restrict participation and can provide organizational privacy and predictable performance, but they rely on membership and governance authorities.

Addresses identify destinations or conditions, whereas keys authorize actions and scripts define spending or execution rules. Finally, immutability should be understood as tamper evidence and consensus-backed finality rather than an absolute guarantee. Sound designs match data structures, trust assumptions, privacy requirements, and governance mechanisms to the application.

Key Terms

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

Hash pointer: A reference containing a location and a cryptographic digest of referenced data.

Block header: Metadata that commits to a block and its relationship to earlier blocks.

Transaction: An authorized instruction to transfer value or modify ledger state.

UTXO: An unspent transaction output available for future consumption.

Account model: A ledger model that stores balances and other state in accounts.

Nonce: A sequence value used to order transactions or prevent replay.

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

Merkle proof: Evidence allowing verification that an item belongs to a committed tree.

Patricia trie: A compressed prefix tree used to represent key-value mappings.

State root: A digest committing to an authenticated representation of ledger state.

Address: A protocol or user-facing representation of a destination or spending condition.

Private key: Secret cryptographic material used to authorize signatures.

Digital signature: Cryptographic evidence of authorization and message integrity.

Script: A rule or program defining conditions for spending or execution.

Consensus: The process by which participants agree on an accepted ledger history.

Finality: The degree or point at which a ledger decision is considered irreversible.

Permissioned blockchain: A ledger whose participation is restricted by membership rules.

Tamper evidence: The property that unauthorized modification changes detectable commitments.

Canonical serialization: A unique encoding of logical data into bytes for hashing or signing.

Review Questions

5 Short Answer Questions

1. What is the difference between a conventional pointer and a hash pointer?
2. Why does a UTXO become unavailable after it is spent?
3. What information does a Merkle proof provide?
4. Why are nonces commonly used in account-based systems?
5. Why does a permissioned blockchain still require governance?

5 Long Answer Questions

1. Explain the structure of a blockchain block and analyse how hash pointers provide tamper evidence.
2. Compare UTXO and account-based models with respect to validation, privacy, concurrency, and smart contracts.
3. Describe Merkle trees and Patricia tries, including their different purposes and proof behaviour.
4. Explain the relationships among private keys, public keys, addresses, signatures, and scripts.
5. Discuss why blockchain immutability is not equivalent to absolute irreversibility.

3 Analytical / Application Questions

1. A payment system requires parallel transaction validation and strong control over individual asset units. Recommend a ledger model and justify the choice.
2. A consortium wants to record proof of document integrity without publishing confidential documents. Design an architecture and identify its trust dependencies.
3. Analyse the security consequences of ambiguous transaction serialization in a system that uses transaction hashes and digital signatures.

Multiple Choice Questions with Answers

Question 1

Which property of a cryptographic hash function makes it difficult to find an input corresponding to a known digest?

A. Preimage resistance

B. Key escrow

C. Address reuse

D. Nonce ordering

Correct Answer: A. Preimage resistance

Question 2

In a UTXO transaction, inputs valued at 10 units produce outputs of 9.7 units. Assuming no issuance or burn, what is the fee?

A. 0.03 units

B. 0.3 units

C. 1.03 units

D. 19.7 units

Correct Answer: B. 0.3 units

Question 3

What does a Merkle inclusion proof primarily demonstrate?

A. That the signer owns the private key

B. That a transaction belongs to a committed tree

C. That a transaction is legally valid

D. That a block has deterministic finality

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

Question 4

Which structure is most naturally suited to authenticated key-value state such as account records?

A. Patricia trie

B. Plain text log

C. Random nonce list

D. Digital signature alone

Correct Answer: A. Patricia trie

Question 5

What is the primary role of a nonce in many account-based ledgers?

A. Compressing public keys

B. Preventing replay and ordering transactions

C. Replacing consensus

D. Generating Merkle roots

Correct Answer: B. Preventing replay and ordering transactions

Question 6

Which statement best describes a blockchain address?

A. It is always identical to a private key

B. It is necessarily the full public key

C. It identifies a destination or spending condition

D. It proves that an off-chain document is true

Correct Answer: C. It identifies a destination or spending condition

Question 7

For four Merkle leaves A, B, C, and D, which expression gives the root under a binary tree using concatenation?

A. hash(A || B || C || D) only

B. hash(hash(A || B) || hash(C || D))

C. hash(A + B + C) − D

D. hash(A) + hash(B) + hash(C) + hash(D)

Correct Answer: B. hash(hash(A || B) || hash(C || D))

Question 8

Which statement about permissioned blockchains is most accurate?

A. They eliminate all trust requirements

B. They restrict participation through membership or identity rules

C. They cannot use digital signatures

D. They must use proof-of-work mining

Correct Answer: B. They restrict participation through membership or identity rules

Question 9

If a sender has 7 units, pays 5 units, and pays a fee of 0.1 units, what change is required in a UTXO transaction?

A. 1.9 units

B. 2.0 units

C. 5.1 units

D. 12.1 units

Correct Answer: A. 1.9 units

Question 10

What does tamper evidence mean in a blockchain context?

A. History can never be changed under any circumstances

B. Unauthorized modification changes commitments and can be detected

C. Every transaction is automatically private

D. Consensus is unnecessary after hashing

Correct Answer: B. Unauthorized modification changes commitments and can be detected