The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

2 The block tree and the most-work rule

Zcash transactions are grouped into blocks, and every block other than the genesis block names its parent by including the parent header’s hash (Crypto Guide, §“Hash functions and the random oracle model”). Blocks therefore form a tree rooted at the genesis block, and each root-to-leaf path, a branch, is one internally consistent history. A branch may contain a transaction that conflicts with a transaction in a sibling branch; the attack that this volume quantifies exploits such conflicts. This section defines the work of a block, the best valid block chain, and confirmations, then states the attack.

2.1 Work, and the best chain

Nodes select one history by a rule that each applies locally, and they converge once the rule strictly prefers one valid branch. The rule weighs each block by the computational effort that its header target represents, rather than counting blocks as a “longest” rule would.

Definition 2.1 (Work of a block).

Let 𝖳𝗈𝖳𝖺𝗋𝗀𝖾𝗍 be the conversion from the header’s nBits field to its 256-bit target threshold (specification §7.7.4). The work of a block is

𝗐𝗈𝗋𝗄=⌊2256𝖳𝗈𝖳𝖺𝗋𝗀𝖾𝗍⁢(nBits)+1⌋

(specification §7.7.5, “Definition of Work”). A lower target admits fewer valid headers, so a block meeting it certifies proportionally more expected hashing; work is the additive measure of that expected hashing.

The deployed Zebra validator computes this quantity without leaving 256-bit arithmetic, as one plus the integer quotient of the bitwise complement of the target by one more than the target; the retired zcashd computed the identical expression. This computation agrees with Definition 2.1 exactly: writing t for the target and A=2256, the complement is ¬t=A−1−t, and

⌊A−1−tt+1⌋+1=⌊A−(t+1)t+1⌋+1=⌊At+1⌋,

an identity also checked by script over random targets.

Definition 2.2 (Best valid block chain).

Specification §3.3 (“The Block Chain”): a node “sums the work, as defined in §7.7.5, of all blocks in each valid block chain, and considers the valid block chain with greatest total work to be best. To break ties between leaf blocks, a node will prefer the block that it received first.”

Rosenfeld’s paper states the same rule for Bitcoin, “the branch representing the most proof of work”, with first-seen tie-breaking, and the model adopts it. The shorthand “longest chain” is exact only while difficulty is constant, which is the paper’s Assumption 4.2 and not a property of the deployed chain (Section 8.2). The rule marks no chain as permanently chosen: a node that learns of a heavier valid branch switches to it however deep the fork point, subject only to the node-local rollback limits of Section 8.4.

Definition 2.3 (Confirmations).

A transaction has n confirmations if it is included in a block of the best chain and there are n blocks on the path from that block to the chain’s leaf, inclusive. The block containing the transaction is its first confirmation.

Different nodes may briefly disagree on the best chain when two blocks of equal cumulative work arrive in different orders. Absent a concurrent extension of the other branch, a later block makes one branch strictly heavier, and nodes converge on it once that block propagates (Figure 1). Such ties arise without an attacker. In the attack of Section 5, the attacker instead builds a fork in private and releases it only once it carries more work than the public branch.

Refer to caption
Figure 1: Branch selection. Arrows point from child to parent. In panel (a) two blocks extend the same parent and the branches carry equal work; each node keeps the one it saw first. In panel (b) a new block lands on the upper branch, which now has strictly more cumulative work; during propagation, every node that knows this state selects the upper branch, unless the lower branch has meanwhile been extended. At constant difficulty “more work” and “longer” coincide, which is how the paper, and this volume’s figures, may draw block counts.

2.2 The attack

The paper (§3) describes the double-spend attack as follows. The attacker:

  1. 1.

    broadcasts a transaction paying the merchant;

  2. 2.

    mines in secret a branch from the last block before that transaction, containing instead a conflicting transaction paying the attacker;

  3. 3.

    waits until the merchant’s transaction has n confirmations and the merchant hands over the goods;

  4. 4.

    in the paper’s first-seen tie model, extends the private branch until it carries more work than the public one, then broadcasts it. Every node that receives it switches to it, the payment to the merchant leaves the best chain, and the attacker holds both the goods and the coins.

Step 4 violates no validity rule: the released branch is a valid chain, distinct from the public one. The success of the attack is therefore a question of probability alone. Sections 4 and 5 compute exactly, in the first-seen model, the probability that the private branch ever carries more work than the public one.