Fistbump: A Memory-Hard Decentralized Naming Protocol

A public blockchain that registers human-readable top-level domains and on-chain subdomains, with native DNS record storage, memory-hard proof of work, and on-chain Vickrey auctions.

Abstract

Fistbump is a decentralized naming protocol that registers human-readable top-level domains and on-chain subdomains on a public blockchain with native DNS record storage. It uses Balloon Hashing, a provably memory-hard proof-of-work function requiring 512 MB of RAM per proof attempt, designed to reduce the economic advantage of ASICs and GPUs. Names are allocated through Vickrey (sealed-bid, second-price) auctions with minimum bids tied to the block reward. Registration fees are split between a burn and a development fund; annual renewal fees prevent costless squatting and sustain protocol funding without pre-mines, airdrops, or token treasuries. The reference node, fbd, is written in Swift and includes a built-in authoritative DNS server that responds to standard DNS queries using on-chain records.

1. Background

1.1 The DNS Root Zone

The Domain Name System maps human-readable names to machine-readable addresses and is the entry point for nearly all internet communication. The root zone is managed by IANA (a function of ICANN) and delegates authority to thirteen root server operators, hundreds of accredited registrars, and dozens of certificate authorities. This hierarchy creates known vulnerabilities:

• Domain seizure. The US Department of Justice has seized thousands of domains through civil forfeiture.
• Infrastructure fragility. The 2016 Dyn DDoS attack disrupted Twitter, Reddit, GitHub, and other major services by targeting a single DNS provider.
• Barriers to entry. Applying for a new gTLD costs $185,000, limiting participation to well-funded organizations.
• Certificate authority compromise. The DigiNotar breach and Symantec mis-issuance incidents demonstrated weaknesses in the web PKI built on DNS. DANE/TLSA records, which Fistbump supports natively, offer certificate validation without trusted third parties.

1.2 Prior Work

Several projects have attempted decentralized naming:

• Namecoin (2011). A merge-mined Bitcoin fork with a .bit namespace outside the DNS hierarchy. Required special resolver software.
• ENS (2017). A naming layer for Ethereum that stores resolver records, not DNS records. Runs on Ethereum where gas fees make operations expensive. See Fistbump vs. ENS.
• Handshake (2020). The most architecturally serious attempt, with native covenants, on-chain DNS records, and root zone replacement. Its BLAKE2b+SHA3 PoW was dominated by ASICs. Free renewals enabled costless squatting. See Fistbump vs. Handshake.
• Unstoppable Domains. NFT-based domains on Polygon with no DNS records. Names require browser extensions to resolve.

2. Protocol Overview

Fistbump is a UTXO-based blockchain where every transaction output carries a covenant: a typed data structure that encodes the output's role in the naming protocol. Covenants enforce the state machine of name auctions (open, bid, reveal, register, update, renew, transfer) without complex scripting. Name state is stored in an Urkel tree, a Merkleized trie whose root is committed in every block header, enabling light clients to verify name ownership and DNS records with compact proofs. The proof-of-work function, Balloon Hashing, requires 512 MB of RAM per attempt.

The fbd node includes a built-in authoritative DNS server. When a name is registered and its owner attaches DNS resource records, those records are stored on-chain and served in response to standard DNS queries. TLD owners can enable on-chain subdomain auctions, creating independent names (e.g., example.fistbump) with their own ownership, records, and lifecycle. All existing ICANN TLDs are reserved at genesis to avoid namespace collisions.

Key parameters: total supply of 1,051,200,000 FBC, initial block reward of 500 FBC, halving every four years, two-minute block time. No pre-mine, ICO, airdrop, or founder reward. Registration fees are split 50/50 between a burn and a development fund. Renewal fees are 1% of the registration price annually, floored at the minimum bid for that name's tier. The development fund is sent to a multisig address controlled by the core contributors — a governance parameter published by the project, not consensus-critical.

2.1 Example: Registering and Using a Name

A walkthrough of the full lifecycle:

1. Mine or acquire FBC. Run fbd's built-in CPU miner. Each proof attempt allocates a 512 MB scratchpad. A valid block earns the coinbase reward (500 FBC at genesis), spendable after 100 confirmations.
2. Open an auction. Register "fbd" (3 bytes — premium). Provide a DNSSEC proof of ownership of fbd.dev and broadcast an OPEN covenant.
3. Bid. During the 3-day bidding window, publish a blinded commitment: blind = BLAKE2b-256(value || nonce). On-chain lockup: 80,000 FBC; actual bid: 60,000 FBC (minimum is 50,000).
4. Reveal. During the 1-day reveal window, broadcast the nonce. A second bidder reveals 55,000 FBC.
5. Register. Winner pays the second-highest bid (55,000 FBC). Excess (5,000 + 20,000 lockup surplus) is refunded. Of the 55,000 paid, 27,500 is burned and 27,500 goes to the dev fund. Attach DNS records at registration (A, AAAA, TLSA, etc.).
6. Resolve. dig @<fbd-node> fbd A returns the on-chain record.
7. Renew. Before ~1 year elapses, broadcast a RENEW covenant and pay 1% of 55,000 = 550 FBC.

3. Consensus

3.1 Proof of Work: Balloon Hashing

Fistbump uses Balloon Hashing, a memory-hard algorithm proposed by Boneh, Corrigan-Gibbs, and Schechter (ASIACRYPT 2016). Unlike earlier memory-hard functions (Scrypt, Ethash) whose security relies on heuristic arguments, Balloon Hashing has a formal proof of memory hardness.

The algorithm operates in two phases:

• Expand. A pseudorandom scratchpad is filled sequentially. Each 32-byte slot is derived from the previous slot and the input via BLAKE2b-256. The entire scratchpad must be allocated and populated before proceeding.
• Mix. The scratchpad is traversed again. Each slot is updated by hashing it with pseudorandomly selected neighbor slots, creating data dependencies across the entire scratchpad. These dependencies prevent time-memory trade-offs.

Parameters:

Scratchpad slots:    16,777,216  (2^24 slots × 32 bytes = 512 MB)
Mixing rounds:       1
Neighbors per round: 1
Inner hash:          BLAKE2b-256

A block is valid when the PoW hash is numerically less than or equal to the target derived from the compact difficulty bits in the header.

3.2 Why Memory Hardness Raises the Cost of Specialized Hardware

Bitcoin's SHA-256 moved from CPUs to ASICs within three years. Litecoin's Scrypt was defeated by Scrypt ASICs within two. Handshake's BLAKE2b+SHA3 was dominated by Bitmain within months. In every case, a compute-bound hash function was efficiently implemented in custom silicon.

Memory-hard functions shift the bottleneck from computation to memory bandwidth:

• ASIC resistance. A 512 MB DRAM requirement per mining core is commodity — cost is similar on an ASIC package or a desktop DIMM.
• GPU resistance. GPUs parallelize through thousands of threads with small local memory (48-128 KB per SM). A 512 MB scratchpad per thread far exceeds this.
• FPGA resistance. FPGAs have less on-chip memory than GPUs and require external DRAM, limiting their advantage.

3.3 Difficulty Adjustment

Difficulty retargets every block using a 72-block sliding window. The algorithm selects the median-of-three blocks at window boundaries to resist timestamp manipulation, computes actual elapsed time, clamps it to between one quarter and four times the expected time, and adjusts the target proportionally. Per-block adjustment suits a memory-hard chain where hash rate is elastic.

3.4 Block Structure

Each block header is 236 bytes:

Preheader (76 bytes):
  nonce            4 bytes    Miner-iterated counter
  time             8 bytes    Unix timestamp
  prevBlock       32 bytes    Hash of previous block
  treeRoot        32 bytes    Urkel trie root

Subheader (128 bytes):
  extraNonce      24 bytes    Additional miner-malleable space
  reservedRoot    32 bytes    Reserved for future use
  witnessRoot     32 bytes    Witness commitment Merkle root
  merkleRoot      32 bytes    Transaction Merkle root
  version          4 bytes    Protocol version
  bits             4 bytes    Compact difficulty target

Mask (32 bytes):
  mask            32 bytes    Reserved (zero-filled)

Block weight = (header size × 4) + transaction size. Maximum block weight: 4,000,000. Maximum non-witness block size: 1,000,000 bytes.

4. Naming System

4.2 Name Rules

Label length:       1-63 bytes per label
Total length:       1-253 bytes (DNS maximum)
Valid characters:   lowercase a-z, digits 0-9, hyphens
Label separators:   dots (subdomains only)
Case:               lowercase only (no Unicode)
Blacklisted:        example, invalid, local, localhost, onion, test
ICANN reserved:     All ICANN TLDs at genesis

If ICANN later assigns a TLD matching an existing Fistbump name, the Fistbump registration is honored.

4.3 Premium Names

Names of 6 bytes or fewer are premium. Opening an auction for a premium name requires a DNSSEC proof of ownership under a qualifying ICANN TLD: com, net, org, gov, io, app, dev, or xyz. DNSSEC proofs are validated on-chain with a 3,600-second grace period for RRSIG validity. Premium names are available at genesis and not subject to rollout.

4.4 Name Rollout

Non-premium names are released over 60 days to prevent a land rush:

day = SHA3-256(name) mod 60

Rollout begins at block 10,080. A new batch becomes available every 720 blocks (~1 day).

4.5 Auction Mechanism

Names are allocated through Vickrey (sealed-bid, second-price) auctions:

Phase        Duration                 Action
OPEN         30 blocks (~1 hour)      Broadcast OPEN covenant
BID          2,160 blocks (~3 days)   Submit blind bids: BLAKE2b-256(value || nonce)
REVEAL       720 blocks (~1 day)      Reveal nonces; unrevealed bids forfeited
REGISTER     2,130 blocks (~71 hrs)   Winner registers, pays second-highest bid

Total cycle: approximately 7 days. The on-chain lockup must be ≥ the actual bid; the difference is returned after reveal. Minimum bids:

Premium TLDs (≤6 bytes):  100× block reward  (50,000 FBC at genesis)
Regular TLDs:              20× block reward  (10,000 FBC at genesis)
Subdomains:               0.2× block reward  (100 FBC at genesis)

4.6 Post-Registration Operations

UPDATE      Change DNS records or set flags.
RENEW       Extend for one year. Required within 262,800 blocks.
            Fee: 1% of registration price, floored at minimum bid.
TRANSFER    Initiate transfer. 360-block lockup (~12 hours).
FINALIZE    Complete a pending transfer.
REVOKE      Burn a name to prevent stolen-transfer completion.

4.7 On-Chain DNS Records

Registered names store standard DNS resource records on-chain:

DS       DNSSEC delegation signer
NS       Name server delegation
GLUE4    IPv4 glue record (for self-referential NS)
GLUE6    IPv6 glue record
SYNTH4   Synthetic IPv4 record
SYNTH6   Synthetic IPv6 record
TXT      Text record
A        IPv4 address
AAAA     IPv6 address
CNAME    Canonical name alias
MX       Mail exchange
TLSA     TLS certificate association (DANE), with port + protocol
CAA      Certificate Authority Authorization
SUB      Inline subdomain record

Maximum resource data per name: 512 bytes. The fbd node includes a built-in authoritative DNS server that resolves queries against on-chain state.

4.8 On-Chain Subdomains

Fistbump supports fully on-chain subdomains: names like example.fistbump and shop.example.fistbump registered, auctioned, and resolved entirely on-chain. Unlike traditional DNS subdomains, Fistbump subdomains are independent on-chain names with their own ownership, records, auction history, and renewal lifecycle. The parent cannot unilaterally revoke or modify a subdomain once registered.

A TLD owner enables subdomains by setting the auctionSubdomains flag via UPDATE. Once set, the flag is permanent. Subdomain registration fees are split:

Burn:       50% of the registration price
Ancestors:  25%, split evenly among all ancestor owners
Dev fund:   25%

For shop.example.fistbump, the ancestors are example.fistbump and fistbump (12.5% each).

5. Covenants

Every transaction output carries a covenant: a typed data structure encoding the output's role in the naming protocol.

Type        Value   Purpose
NONE          0     Standard value transfer
OPEN          1     Initiate a name auction
BID           2     Place a blind bid
REVEAL        3     Reveal a bid
REDEEM        4     Reclaim a losing bid
REGISTER      5     Register a won name
UPDATE        6     Update DNS records
RENEW         7     Renew ownership
TRANSFER      8     Initiate transfer
FINALIZE      9     Complete a transfer
REVOKE       10     Burn a name

Covenants from REVEAL through REVOKE must reference the previous covenant output in the name's UTXO chain.

6. Currency: FBC

The native currency is FBC (Fistbump Coin). The smallest unit is one bump.

1 FBC = 1,000,000 bumps

Initial block reward:   500 FBC
Halving interval:       1,051,200 blocks (~4 years at 2-min blocks)
Maximum halvings:       52
Total supply:           1,051,200,000 FBC

The genesis block reward is burned. Coinbase outputs require 100 confirmations before spending.

7. Transactions

Fistbump uses an all-witness transaction format with no legacy types. Each transaction contains version, inputs (previous outpoints and sequence numbers), outputs (value, address, covenant per output), locktime, and witnesses (one witness stack per input). Hashing uses BLAKE2b-256. Maximum transaction size: 1,000,000 bytes; maximum block weight: 4,000,000.

8. Addresses

All addresses use Bech32 encoding with a network-specific human-readable part:

Network     HRP     Example prefix
mainnet     fb      fb1q...
testnet     ft      ft1q...
regtest     fr      fr1q...
simnet      fs      fs1q...

Witness programs: version 0 with 20-byte hash (P2WPKH, BLAKE2b-160 of compressed public key) or 32-byte hash (P2WSH, SHA3-256 of witness script). Versions 1–31 are reserved for future soft fork upgrades.

9. State Storage: Urkel Tree

Name state is stored in an Urkel tree, a base-2 Merkleized radix trie. Keys are 32-byte SHA3-256 hashes of names. Values are serialized NameState records containing the raw name, height, renewal, owner UTXO, value, data, flags, parentHash, and status fields.

The trie root is committed in the block header. The tree updates every 30 blocks (the tree interval), enabling light client verification without full chain download.

10. Networking

Nodes communicate over TCP using a binary message protocol. Default ports:

Network     P2P      Brontide   RPC      DNS
mainnet     32867    32868      32869    32870
testnet     42867    42868      42869    42870
regtest     52867    52868      52869    52870
simnet      62867    62868      62869    62870

Peer connections support Brontide, an encrypted transport based on the Noise protocol framework: Noise_XK_secp256k1_ChaChaPoly_SHA256+SVDW_Squared. Provides mutual authentication, forward secrecy, and encrypted traffic with key rotation every 1,000 messages.

11. Cryptographic Primitives

BLAKE2b-256         Block hashing, transaction hashing, PoW password, blind bids
BLAKE2b-160         Public key hashing (P2WPKH addresses)
SHA3-256            Name hashing, witness script hashing (P2WSH)
secp256k1           Elliptic curve for signatures (ECDSA) and key agreement (ECDH)
ChaCha20-Poly1305   Brontide peer-to-peer encryption
BalloonHash         Proof-of-work (BLAKE2b-256 inner hash, 512 MB scratchpad)

12. Comparison with Handshake

Fistbump shares Handshake's covenant-based naming model, Urkel tree, and UTXO structure. Key differences are summarized below. For the full analysis, see Fistbump vs. Handshake.

13. Security Considerations

13.1 51% Attacks

A miner controlling majority hash rate could reorganize the chain. Memory-hard PoW raises the capital cost by requiring large amounts of RAM rather than specialized chips. An attacker must acquire and operate many general-purpose computers, which is expected to be more expensive per unit of effective hashpower than an attack on an ASIC-dominated, compute-bound chain.

13.2 Name Squatting

Multiple mechanisms mitigate squatting: the 60-day rollout prevents a land rush at genesis; DNSSEC requirements protect short names; minimum bids prevent costless acquisition; and renewal fees create ongoing holding costs. Names not renewed within 262,800 blocks (~1 year) expire and reopen for auction.

13.3 Subdomain Sovereignty

The auctionSubdomains flag is permanent once set. Both the flag and parentHash are preserved through name expiration, so subdomains function even if the parent expires. Delegation and SUB records are blocked when subdomain auctions are enabled, preventing resolution redirection or shadowing.

14. Implementation

The reference implementation is fbd, a full node written in Swift:

• fbd — Full node with P2P networking, chain validation, mempool, CPU miner, DNS server, and JSON-RPC API.
• fbdctl — Command-line RPC client.

Supports four networks (mainnet, testnet, regtest, simnet) on macOS, Linux, and Windows. Over 60 JSON-RPC methods for blockchain queries, wallet management, name auctions, mining, and network administration.

Source code: github.com/fistbump-org/fbd.

15. Conclusion

Fistbump provides a complete naming hierarchy, from root to subdomain, on a blockchain secured by provably memory-hard proof of work. On-chain DNS records and a built-in authoritative server make names immediately resolvable through standard DNS query interfaces. Market-driven auctions, minimum bids, and renewal fees create sustainable economics without insider allocation. The result is a naming system designed to resist centralized control, secured by a mining design intended to raise the cost of hardware concentration.

References

1. Boneh, D., Corrigan-Gibbs, H., Schechter, S. "Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks." ASIACRYPT 2016.
2. Alwen, J., Serbinenko, V. "High Parallel Complexity Graphs and Memory-Hard Functions." STOC 2015.
3. Kalodner, H., Carlsten, M., Ellenbogen, P., Bonneau, J., Narayanan, A. "An Empirical Study of Namecoin and Lessons for Decentralized Namespace Design." WEIS 2015.
4. US Department of Justice. "Department of Justice Seizes 2,779 Internet Domain Names Engaged in Selling Counterfeit Goods." Press release, November 2020.
5. Hilton, S. "Dyn Analysis Summary Of Friday October 21 Attack." Dyn Blog, October 2016.
6. Fox-IT. "Black Tulip: Report of the Investigation into the DigiNotar Certificate Authority Breach." 2012.
7. O'Brien, D., Sleevi, R., Whalley, A. "Chrome's Plan to Distrust Symantec Certificates." Google Security Blog, September 2017.
8. Unstoppable Domains. US Patent Application 17/465,707, "Resolving Blockchain Domains." Filed 2021.