← Learn · crossing a wall

Hop versus sidestep

A wall can be crossed two ways, and both do work over the same leaves. A hop pairs them into a Cantor root, which grows with every level and is the same for everyone. A sidestep hashes them into a Merkle root, which stays 32 bytes at every level and is different for every traveler. In the scene the leaves sit on one row, the hop's tree grows up from them, and the sidestep's tree hangs down.

A sidestep only crosses

A sidestep moves exactly one Gibson, from the leaf touching the wall on one side to the leaf touching it on the other (section 6.3). From 7 to 8 is a valid sidestep across the height-4 wall, and so is 8 to 7. From 5 to 8 is not: the source must be 7, so the traveler hops from 5 to 7 first. From 7 to 11 is not either: the traveler sidesteps to 8 and hops on to 11. Pinning the source to the wall keeps every other Gibson of travel inside hops, which are the only moves that produce a region root. The scene checks this before it draws a verdict, as a verifier does before it looks at any hash.

The Merkle tree

Each leaf is hashed with SHA-256 behind a 64-byte prefix: the 22-byte domain CYBERSPACE_SIDESTEP_V2, the 32-byte id of the traveler's previous chain event, one axis byte, and nine zero bytes (section 6.4). Here that is 22 + 32 + 1 + 9 = 64 bytes, exactly one SHA-256 block, so an implementation hashes the prefix once and each leaf costs one more compression. Pairs of hashes are hashed upward until one 32-byte root remains. Because each node is fixed-size, the tree streams in h × 32 bytes of memory (section 6.5).

Why the seed: a toll, not a road

Switch the traveler in the scene and the Cantor root above the leaves stays put while every hash below changes. That is the design. Without the seed, the first identity to cross a wall would publish a root and openings that every later traveler could copy, and the wall would be priced for the pioneer and free for everyone after. With it, each traveler's tree is unique to their chain position, so everyone pays in full, every time. The hop is deliberately different: its root is canonical, because that is what lets two people at one place derive the same key (section 6.12).

Openings

A sidestep event publishes the destination leaf's path to the root plus eight more paths at pseudorandomly sampled positions, and a re-roll nonce which, with the roots, decides where those positions fall (section 6.10). The magenta path and the ringed leaves in the scene are those openings. A verifier checks the nonce with one hash, recomputes the eight sampled leaves from the public seed and checks their paths, which costs seconds at any height (section 6.11).

The re-roll price

The sample positions are not derived from the root. They are drawn from a 32-byte value G that costs work to obtain: the SHA-256 of the 28-byte domain CYBERSPACE_SIDESTEP_GRIND_V1, the nonce as 8 big-endian bytes, the 32-byte previous event id, and the three 32-byte axis roots Mx, My and Mz, where an axis without movement contributes its single seeded leaf. Let L be the total number of leaves over the axes where movement occurs, and A = max(1, ceil(L / 8)). The prover must publish, in the event's mn tag, a nonce for which G, read as a 256-bit big-endian integer, satisfies G × A < 2256. Each candidate nonce succeeds with probability 1/A, so finding one takes A attempts on average. The preimage is 28 + 8 + 32 + 3 × 32 = 164 bytes, three SHA-256 blocks with the nonce in the first, so no intermediate state survives from one attempt to the next and every attempt costs three compressions. A leaf costs one compression and its share of the internal nodes two more, so one attempt costs exactly one leaf's share of the tree, and A attempts cost one eighth of it (section 6.10). Each sampled position is then the SHA-256 of CYBERSPACE_SIDESTEP_SAMPLE_V2, G, the axis byte and the sample's number as 4 big-endian bytes, read as an integer modulo 2h. The scene's Nonce search lists the attempts, and its Re-roll button searches on for the next nonce that meets the price.

Why a price

A prover can skip work without touching any leaf it will be asked about. It builds only part of the tree honestly, puts 32 fabricated bytes where each missing subtree's root belongs, and publishes the root that results. No sample landing inside a fabricated subtree can produce a valid path, because the verifier recomputes the sampled leaf from the public seed, so a prover that honestly built a fraction f of the leaves passes one set of samples with probability f8. What decides whether cheating pays is the price of trying again (section 6.11).

Version 2 of the sidestep drew the samples from the root alone, so a retry cost about h + 8 hashes: change one fabricated value, rehash the path above it, and derive new samples. A retry did not require rebuilding the tree. Building only the half of the tree that holds the destination and retrying about 256 times passed Level 1 for half the honest work at h20, and fabricating more subtrees brought the cost down to 3.1 percent of the honest work at h55. Version 3 closes this: each fresh set of samples costs A attempts, one eighth of the tree, and at that price no fraction of skipped work lowers the expected cost of an accepted proof. The honest prover pays the price once, so a crossing costs one eighth more than its tree. Verifiers reject version 2 sidesteps, which carry no mn tag, except the ones listed by event id in grandfathered-v2-sidesteps.txt (section 6.16).

Where each one wins

The hop's cost is its root: 85 × 2h bits per axis, held while it is built. The sidestep's cost is time: 2h+1 - 1 hashes for the tree, which is 3 × 2h - 2 SHA-256 compressions, then A re-roll attempts of three compressions each, which add one eighth to that work, and almost no memory. The "project to height" slider computes all of them at any height; a few rows:

HeightHop root per axisSidestep tree hashesRe-roll attempts (A)Sidestep memory
h2011.1 MB2,097,151131,072640 bytes
h34182.5 GB34,359,738,3672,147,483,6481,088 bytes
h4011.7 TB2,199,023,255,551137,438,953,4721,280 bytes
h5012.0 PB2,251,799,813,685,247140,737,488,355,3281,600 bytes
h6012.2 EB2,305,843,009,213,693,951144,115,188,075,855,8721,920 bytes

Measured in the reference implementation, the two cross near h16; above that the sidestep is faster at every height, and far above it the hop is impossible because no one can store the root. Those sidestep figures are the tree alone, and the re-roll price adds one eighth to each (section 6.14). A traveler hops when they want the region's root and sidesteps when they want to move.

Entering is not holding

The Merkle root says nothing about the Cantor root over the same leaves. A traveler who sidesteps into a region has proven the crossing, and holds none of the region's keys: every location key inside still needs the Cantor computation. You can walk into a building without having the keys. The region key scene shows what those keys open.