From signed payments to blocks

Alice wants to pay Bob 20 Ð for a book. In an ordinary banking interface, she types 20 and presses Send. Behind that small action, the system must answer several questions: where is the money coming from, who may spend it, what happens to the remainder, and which record prevents Alice from spending it again?

In the previous part, we gave DCoin public validation rules, peer-to-peer communication, hashes and digital signatures. Now we need objects those rules can operate on. We will use a model inspired by Bitcoin: transactions consume existing outputs and create new ones.

This choice is not inevitable. An account-based ledger could update balances instead. The output-based model is useful here because it makes conservation and conflicting spends explicit, and it prepares us for reading actual Bitcoin transactions later.

2.1 #Spend outputs, not a balance field

An unspent transaction output, usually shortened to UTXO, records an amount and the condition required to spend it. An output is identified by the transaction that created it and its position within that transaction. That pair is an outpoint.

For our simplified DCoin rules, the spending condition can be a public key: provide a valid signature under that key. Real Bitcoin outputs use scripts and witness programs, so the public-key picture is an introductory case rather than the whole system.

A wallet's displayed balance is derived from the outputs it can spend. If Alice controls outputs worth 200 Ð and 300 Ð, her balance is 500 Ð, but there is no universal row called Alice.balance that all nodes update. There are two spendable records, each of which can be consumed once.

Suppose instead that Alice controls a single output worth 500 Ð. Spending 20 Ð does not partially consume that output. The transaction consumes all 500 Ð and creates a new output returning the change to Alice.

The conservation rule for a non-issuance transaction is

Here, an input's value comes from the referenced output in the existing ledger. A sender cannot make an input worth 500 merely by writing amount: 500 in a message. Validators look up the referenced record themselves.

Use integer units for these calculations. Floating-point arithmetic is a poor foundation for a rule that every validator must reproduce exactly. Bitcoin expresses values in satoshis; DCoin can choose its own smallest indivisible unit and enforce a maximum range to avoid overflow or nonsensical amounts.

Change is also a real output with a spending condition. It should not be an informal instruction to “keep the rest.” If Alice forgets to create a change output, the input-output difference grows; a valid transaction may then pay an unexpectedly large fee.

2.2 #What a validator actually checks

A DCoin transaction contains a list of input references, a list of new outputs, and the authorization material required by those inputs. Its byte encoding must be deterministic: field order, integer sizes, lengths and signature commitments all belong in the specification.

Given an agreed ledger state, a validator can check a candidate transaction mechanically. It parses the structure, rejects duplicate input references, finds each referenced output, checks that it remains unspent, verifies the spending conditions, and accounts for values. It also enforces any size and timing rules that DCoin defines.

The order of these checks matters operationally. A node should not spend unlimited CPU verifying signatures for an object whose length fields are already impossible. A parser should reject truncation and unreasonable counts rather than allocating memory blindly. Consensus rules describe validity; robust software also needs a careful boundary between untrusted bytes and those rules.

The toy state transition might look like this:

def apply_payment(tx, unspent):
    # Pseudocode: parsing and signature rules are specified elsewhere.
    inputs = [item.outpoint for item in tx.inputs]
    assert inputs and len(inputs) == len(set(inputs))
    previous = [unspent[outpoint] for outpoint in inputs]
    assert all(authorizes(tx, i, old) for i, old in enumerate(previous))
    assert all(0 <= output.value <= MAX_MONEY for output in tx.outputs)
    fee = sum(old.value for old in previous) - sum(o.value for o in tx.outputs)
    assert fee >= 0
    updated = dict(unspent)
    for outpoint in inputs:
        del updated[outpoint]
    for index, output in enumerate(tx.outputs):
        updated[(tx.id, index)] = output
    return updated, fee

This is deliberately not a wallet or a complete consensus implementation. It omits issuance, transaction-ID uniqueness rules, monetary range checks on sums and many other details. Its purpose is to show the state change: delete consumed outputs, then insert the new ones. The original state is left untouched until every check succeeds.

Notice the phrase given an agreed ledger state. If two nodes disagree about which payment happened first, one may still have an output that the other has consumed. Validation is deterministic relative to a state; it does not itself choose that state.

2.3 #Pending is different from confirmed

After Alice broadcasts her payment, peers may keep it in a pool of pending transactions—a mempool. There is no single global mempool. Different nodes may learn about the transaction at different times, retain different candidates or apply different relay policies.

Suppose Alice signs a second transaction spending the same 500 Ð output to Carol. Either payment can be valid against the state before the spend. Together, they cannot both be applied. Rejecting a conflict in one node's mempool does not prove that another node never saw the conflicting version first.

A block packages an ordered batch of transactions. When the block becomes part of the selected history, its transactions are confirmed relative to that history. A block can include a transaction that spends an output created earlier in the same block, so ordering inside the batch can matter too.

For Bitcoin's concrete output and spending model, the transaction guide provides the next layer of detail. The DCoin example keeps only the mechanics we need to understand the ledger.

2.4 #Link blocks through their headers

Each block has a header and a body. The body contains transactions. The header contains metadata, a commitment to the transactions and the hash of the previous block's header. For DCoin, we can specify this structure without yet deciding who may propose the next block.

If someone changes a transaction, its commitment changes. That changes the containing header's hash, so the next block's previous-hash field no longer matches. Repairing the mismatch changes the next header too, and the effect continues through its descendants.

This is a dependency chain, not a magical prohibition on editing. Anyone can build an alternative sequence with internally consistent hashes. We still need a rule that makes replacing the accepted history difficult and tells peers which valid sequence to prefer. That is the consensus problem in the next part.

The first block, the genesis block, has no ordinary predecessor. Its identity and initial rules must be fixed by the protocol or another explicit agreement. A chain cannot explain its own starting conditions merely by pointing backward forever.

2.5 #Commit to the transactions with a Merkle tree

Putting every transaction directly in a header would make headers as large as blocks. Instead, a Merkle tree compresses the commitment into one hash.

Start with transaction identifiers $t_0,t_1,t_2,t_3$. Hash pairs of identifiers, then hash the resulting pair. The final digest is the Merkle root. Here $H$ denotes the tree's chosen hash construction and $\Vert$ means concatenation of raw bytes, not concatenation of their printed hexadecimal strings.

Someone who knows the root can verify this inclusion proof without receiving the other two transactions. With a balanced tree of $n$ leaves, a branch needs roughly $\log_2 n$ sibling hashes rather than $n$ transaction identifiers. The verifier reconstructs the hashes on the path and compares the final result to the committed root.

Inclusion is a limited claim. It does not show that the included transaction has a valid signature, that its inputs were unspent, or that the containing block belongs to the accepted history. Those require other evidence and checks.

Bitcoin's tree uses double SHA-256 and duplicates the final entry at an odd-sized level before forming pairs. Its exact rules matter when reproducing a root from bytes; an abstract binary-tree sketch alone is not a wire-format specification. We will use the block reference when we reach that implementation boundary.

There are now two kinds of hash relationship in our design. The Merkle tree commits to transactions within one block. The previous-header hash connects one block to its predecessor. Keeping these separate helps explain both what a header proves and what it cannot prove.

2.6 #A complete structure, an unresolved choice

We can parse a payment, verify its authorization, update an output set and commit a batch of payments to a header. We can also detect whether a proposed block fits a particular parent. None of that stops two valid blocks from extending the same parent at almost the same time.

The result is a tree of possible histories. A node needs both a validity rule for its branches and a selection rule for the branch it treats as active. Next we will give DCoin a proof-of-work mechanism and examine what its security and incentives actually buy.