Escher Update Chains for decentralized subdomains

HIP-0016: Escher Update Chains for decentralized subdomains

Drawing Hands

Abstract

This document specifies a new protocol that enables a Handshake TLD to sell subdomains in an unrevocable manner, eliminating the “parent domain risk” inherent in domains below the blockchain-secured HNS root zone. The protocol does not require any significant changes to the HNS blockchain consensus system. However, a modest soft-fork will significantly improve the performance, security, and accessibility of the system by light clients.

Escher deploys a new Urkel Tree for each TLD that opts-in to the protocol. In this document we will refer to these as “Escher Trees” but they are just Urkel trees with specific parameters. The roots of these Escher Trees are committed to the HNS root zone Urkel Tree and are therefore verifiable by light clients.

Escher Trees are updated by inserting special transaction messages in the data field of standard UPDATE covenants. These messages include proofs that can be verified against the Escher Tree root currently committed in the TLD namestate.

A soft fork will require miners to enforce validity of these proofs, without the miners needing to store the complete Escher Tree. Escher uses the Urkel structure like an accumulator and is similar to utreexo.

Motivation

Handshake offers users censorship-resistant, proof-of-work-secured top-level-domains in an alternate root zone generated by the HNS blockchain. Since it’s mainnet launch the community has been desperate to develop a mechanism that can extend the same minimal trust and security to subdomains of these TLDs, including bridging HNS domains to external consensus systems like Ethereum.

Escher is a decentralized subdomain proposal designed with these goals in mind:

SLDs can not be revoked, transferred or updated by the TLD owner
Scalable (millions of TLDs with thousands or millions of subdomains)
Verifiable by light clients like the HNS root zone itself
HNS is the currency required for SLD purchase
No other consensus system or other blockchain is required
Minimal impact on HNS full nodes and miners

In addition, Escher offers a number of other potential features which may or not be implemented:

TLD owner receives payment when SLDs are transferred (sold by original owner)
SLDs are owned forever and never expire or require renewal

Limitations

The most oppressive limit of Escher Update Chains is the 512 byte limit for UPDATE covenant data (i.e. namestate data written to the Urkel Tree). This limits the maximum Urkel proof size in the Escher messages and therefore limits the maximum possible size of the Escher Tree itself.

This is an area of active research. The parameters currently specified by this proposal will restrict the Escher tree to a maximum of around 4,000 dSLDs. Once this limit is reached, the Escher tree will effectively freeze, since ANY proofs required to update it will be too large to fit in an UPDATE covenant. Because Urkel trees are sparse and proofs are optimized for space using collision prefix bits, the exact maximum size of a proof depends on random bit collisions between namehashes in the tree itself.

The 512-byte limit can be worked-around by at least these two methods:

Deploy a hard fork that increases the maximum size for UPDATE covenant data.
Use witness data for the Urkel proofs, and use covenant data for tree roots only
- That gives us an extra 8,000 bytes but requires a new address type and witness version.
- Increases code complexity quite a bit, since the UTXO script / witness system is entirely separate from the covenant system.
- However, this does make sense in that Escher Urkel proofs are essentially witness data and can be pruned, that data does not need to live in the UTXO set.

Mechanism

What we need is a way to efficiently prove to a light client what the valid DNS records are for an SLD. We accomplish that in the same way we prove root zone records to a light client: Urkel proofs.

Escher dSLD data is limited to a single public key only, essentially a DS record. This key is anchored to the Escher tree, which is anchored to the HNS root Urkel tree:

┌──────────────────────┐
│   HNS block header   │
│  ┌────────────────┐  │
│  │    treeRoot    │  │
│  └───────╱╲───────┘  │
└─────────╱──╲─────────┘
         ╱    ╲
        ▼      ▼
      hash   (node)
               ╱╲
              ╱  ╲
             ╱    ╲
            ▼      ▼
          hash  TLD data─────┐
                │ Escher root│   △ HNS full node △
                └─────╱╲─────┘  ===================
                     ╱  ╲         ▽ Escher data ▽
                    ╱    ╲
                   ▼      ▼
                (node)  hash
                  ╱╲
                 ╱  ╲
                ╱    ╲
               ▼      ▼
             hash  SLD data─────┐
                   │ public key │
                   └────────────┘

What we don’t want to do is expect all full nodes to store Escher Trees for millions and millions of TLDs, that will not scale. Fortunately, Urkel Trees can be used like a utreexo “accumulator”. This means users can prove (to miners and verifiers) that they are indeed updating the Escher Trees correctly according to the dSLD rules without those verifiers needing complete copies of every tree.

Complete trees can always be reassembled from historical blockchain data by anyone. Entities that need to create Escher proofs will need those complete trees to do so. These entities include dSLD buyers and dSLD name servers (provers). A TLD owner would probably be incentivized to host this data in order to more efficiently sell SLDs, and serve their customers better.

What we can do in 512 bytes is provide compressed Escher Tree operations, that include at least:

A proof of the current state of a key:value pair
The new key:value pair
The NEW root hash that commits the updated Escher Tree

This is all the data needed for verifiers to enforce rules, and for light clients to verify dSLD proofs. This is possible because values are positioned in the Urkel Tree according to their key, therefore a proof of non-existence is exactly the same as a proof of existence with the exception of the final leaf. Modifying a proof of course changes the root hash that proof anchors to. We can use this principle in reverse, to prove what the new tree root hash is AFTER the desired operation.

    (1) Tree:                   (2) Non-existence proof for `111`:

       Root A
       /    \                       /    \
      0      1                     0              hash(0)
     / \    / \                          / \
   00  010 10 110                       10 110    hash(10), leaf(110)
   /\      /\
000 001 100  101                                  Valid if == Root A


                                (3) Insertion data for `111`:
                                    Root B
                                    /    \
                                   0               hash(0)
                                         / \
                                        10         hash(10)
                                            /\
                                         110  111  hash(110), leaf(111)

                                                   New tree root = Root B

    (4) New Tree:      
                       
        Root B         
       /      \        
      0        1       
     / \     /   \     
   00  010 10     11   
   /\      /\     / \  
000 001 100 101 110 111

This diagram illustrates an example Urkel tree with 3 bits. 1- and 2- digit numbers in the diagram indicate internal nodes of tree.

(1) There are 6 leaves in the tree (000, 001, 010, 100, 101, and 110).

(2) To prove that the key 111 does NOT exist in this tree, we need to provide two hashes and the full leaf node at the collision point. The verifier combines that data together to compute a root hash. If that root hash matches the expected root hash (i.e. the root hash committed to a specific block header) then the proof is valid.

(3) We can convert this proof of non-existence into a proof of existence by creating a new internal node (11), and hashing the final leaf node (110). This makes the proof one level deeper, where 110 and 111 are now positioned.

(4) The mutated proof will result in an entirely different root hash, which is exactly the same hash produced by actually inserting the new node into the complete tree!

Specification

The specification currently uses 20 byte hashes in order to fit deeper Urkel proofs into the UPDATE data. 32 byte hashes would be preferable, but would result in significantly lower capacity for dSLDs (an Escher tree using 32 byte hashes will only have capacity for about 100 dSLDs in most proofs under 374 bytes).

We currently choose ed25519 for dSLD ownership because of smaller key size (32 bytes) and compatibility with other blockchain systems like Sia.

P-256 is also a good option because ECDSA allows for public key recovery, which could save us 32 bytes in the update proofs, but P-256 uses bigger public keys (64 bytes)

Since these dSLD keys will eventually be used to sign DNS zone files, it makes sense to choose a standard DNSSEC algorithm (this is why secp256k1, the HNS native signing algorithm, was not selected).

Definitions

ESCHER_VERSION: 0x80

A HNS TLD is said to be “in Escher mode” if the first byte of its data resource is equal to ESCHER_VERSION.

Escher Tree:

hash function: Blake2b160
bits: 160

dSLD algorithm: ed25519

namehash: The blake2b160 digest of the DNS wire-formatted domain name.

Example:
Domain name: campaign.chaos.
DNS name serialization: 0863616d706169676e056368616f7300
Escher namehash: 3199fb4d363f59a8836769be02d201e3bfbc0366

signature: The signature over the a message committing to the NEW public key, the current Escher root hash, and the magic string "EscherMessage" encoded in ASCII.

Example:
Current public key: f5e5c982f8084efec7964e68b6f61cf529f656fb6d2e343ff42cc8ea9520ed5c
Magic string: 4573636865724d657373616765
Current tree root: 6c3bc60ab45fe53ec7c6e9948fa87e558d2cbf23
New public key: 0bf7920cbd5b4697704952ac5aa7d0d4de92d643368c544da4c5d2706204d4ed
Complete signed message:
4573636865724d6573736167656c3bc60ab45fe53ec7c6e9948fa87e558d2cbf23
0bf7920cbd5b4697704952ac5aa7d0d4de92d643368c544da4c5d2706204d4ed
Signature:
bf1a62fd4f4c234b6e6cdf4d52b7397c1c2db2e9848bdab996003bfcc7cfd29a
c6f911e71c3b0ef329df20cf42d48312940fcc7ef3da5882e890737d1690b901

Message format

This is the data that must fit in the 512 byte UPDATE covenant data item:

size	data
1	`ESCHER_VERSION`
20	proposed new tree root
1	method (REGISTER: `0x00`, UPDATE: `0x01`)
20	`namehash`
…	parameters (see below)

REGISTER: 0x00 parameters

size	data
32	NEW public key
4-438	Urkel proof-of-nonexistence of `namehash`

UPDATE: 0x01 parameters

size	data
32	NEW public key
64	`signature`
4-374	Urkel proof of OLD public key of `namehash`

New consensus rules

The following rules apply to verifyCovenants() which is called by both mempool and chain for every output of every transaction as part of full validation. This function is already responsible for checking name ownership, name auction state and so forth. The current nameState for a name is always retrieved from the current Urkel tree, meaning the validator already has the current nameState data in memory. This data is set by the previous UPDATE or REGISTER and is referred to as current.

The data being checked (in the UPDATE covenant of the transaction being checked) is referred to as proposed.

If any of these rules are violated, verification fails immediately and the entire transaction being considered MUST be rejected from mempool or block:

If current[0] !== ESCHER_VERSION the name is not in Escher mode
1. If proposed[0] === ESCHER_VERSION the name is entering Escher mode and the version byte MUST be followed by 20 bytes of 0x00. This is the root hash of the empty Escher tree.
2. If the name is not in or entering Escher mode, no additional rules apply.
If the name is in Escher mode it MUST remain in Escher mode, i.e. proposed[0] === ESCHER_VERSION is required. (There is no escaping Escher mode!)
Bytes 1-20 of current are read and referred to as currentRoot. This is the root hash of the current Escher tree.
After the version byte, proposed MUST have at least 42 bytes of data remaining:
1. proposedRoot (20 bytes)
2. opcode (1 byte)
3. namehash (20 bytes)
4. parameters (at least 1 byte)
If opcode === 0x00 the operation is a REGISTER and parameter validation follows:
1. read newKey (32 bytes)
2. read proof (all remaining bytes)
3. proof MUST be a valid Urkel non-existence proof for namehash in the tree committed by currentRoot.
4. proof is mutated into an existence proof for the key:value pair namehash:newKey and a new root hash is computed.
5. This new root hash MUST be exactly equal to proposedRoot.
If opcode === 0x01 the operation is an UPDATE and parameter validation follows:
1. read newKey (32 bytes)
2. read signature (64 bytes)
3. read proof (all remaining bytes)
4. proof MUST be a valid Urkel proof for key namehash in the tree committed by currentRoot. The value of proof is oldKey.
5. proof is mutated to change the value from oldKey to newKey and a new root hash is computed.
6. This new root hash MUST be exactly equal to proposedRoot.
7. Finally, signature MUST be a valid ed25519 signature over the message defined above (committing to newKey).

Name servers

Escher is an ownership protocol and is designed only to assign SLDs to public keys (literally namehash:pubkey). Escher does NOT solve the problem of data availability. Zone files for dSLDs SHOULD be made available on a single network extension like a DHT or Kademlia protocol maintained by providers. These providers must also serve current Escher proofs for dSLDs. Providers will likely be incentivized by dSLD owners or TLD owners in order to resolve dSLDs.

A precise protocol for dSLD resolution will be specified in a future HIP. What Escher does is simply authenticate that data. Because zone files are signed with expiration times, the data can be hosted anywhere by anyone. Escher can be used to ensure that only valid data (signed by the dSLD owner) is served.