## HIP-0016: Escher Update Chains for decentralized subdomains

## 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- 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. - If the name is not in or entering Escher mode, no additional rules apply.

- If
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:`proposedRoot`

(20 bytes)`opcode`

(1 byte)`namehash`

(20 bytes)- parameters (at least 1 byte)

If

`opcode === 0x00`

the operation is a`REGISTER`

and parameter validation follows:- read
`newKey`

(32 bytes) - read
`proof`

(all remaining bytes) `proof`

MUST be a valid Urkel non-existence proof for`namehash`

in the tree committed by`currentRoot`

.`proof`

is mutated into an existence proof for the`key:value`

pair`namehash:newKey`

and a new root hash is computed.- This new root hash MUST be exactly equal to
`proposedRoot`

.

- read
If

`opcode === 0x01`

the operation is an`UPDATE`

and parameter validation follows:- read
`newKey`

(32 bytes) - read
`signature`

(64 bytes) - read
`proof`

(all remaining bytes) `proof`

MUST be a valid Urkel proof for key`namehash`

in the tree committed by`currentRoot`

. The value of`proof`

is`oldKey`

.`proof`

is mutated to change the value from`oldKey`

to`newKey`

and a new root hash is computed.- This new root hash MUST be exactly equal to
`proposedRoot`

. - Finally,
`signature`

MUST be a valid`ed25519`

signature over the message defined above (committing to`newKey`

).

- read

## 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.

## Implementation

Extra methods are required in the Urkel library for proof mutation:

https://github.com/handshake-org/urkel/pull/24

Soft fork and validation rules:

https://github.com/handshake-org/hsd/pull/761

**HIP:**

**Status:**

**Type:**

**Created:**

**Last commit:**

**Author:**

Edit on GitHub