EIP2390 - Geo-ENS

# Simple Summary

GeoENS brings geographic split horizon capabilities to ENS. It's GeoDNS for ENS!

# Abstract

This EIP specifies an ENS resolver interface for geographically split horizon DNS. Geographic split horizon DNS returns resource records that are specific to an end user's location. This technique is commonly used by CDNs to direct traffic to content caches nearest users. Geographic split horizon resolution is primarily geared towards ENS resolvers storing DNS resource records EIP-1185, although the technique could be used on other interfaces like IPFS content hash storage EIP-1062.

# Motivation

There are many use cases for traditional GeoDNS systems, like Amazon's Route53, in the centralized web. These use cases include proximity-based load balancing and serving content specific to the geographic location of the query. Unfortunately the ENS specification does not provide a mechanism for geo-specific resolution. ENS can respond to queries with IP addresses (as described in EIP-1185) however there is no way to respond to geo-specific queries. This EIP proposes a standard to give the ENS system geo-proximal awareness to serve a similar purpose as GeoDNS.

GeoENS can do more than DNS-based solutions. In addition to geographic split horizon DNS, GeoENS can be used for the following:

Locating digital resources (like smart contracts) that represent physical objects in the real world.
Smart contract managing access to a physical object associated with a specific location.
ENS + IPFS web hosting (as described in EIP-1062) with content translated to the native language of the query source.
Tokenizing objects with a physical location.

Because of the decentralized nature of ENS, geo-specific resolution is different than traditional GeoDNS. GeoDNS works as follows. DNS queries are identified by their source IP address. This IP is looked up in a database like GeoIP2 (opens new window) from MaxMind which maps the IP address to a location. This method of locating the source of a query is error prone and unreliable. If the GeoIP database is out of date, queried locations can be vastly different than their true location. GeoENS does not rely on a database because the user includes a location in their query.

It follows that queries can be made by users for any location, not just their location. Traditional DNS will only return the resource assigned to a query's provenance. GeoENS does not correlate a query's provinance with a location, allowing the entire globe to be queried from a single location.

An additional shortcoming of traditional DNS is the fact that there is no way to return a list of servers in a certain proximity. This is paramount for uses cases that require discovering the resource with the lowest latency. GeoENS allows a list of resources, like IP addresses, to be gathered within a specific location. Then a client to determine themselves which resource has the lowest latency.

Lastly, publicly facing GeoDNS services do not give fine granularity control over geographic regions for GeoDNS queries. Cloud based DNS services like Amazon's Route 53 (opens new window) only allow specifying geographic regions at the granularity of a State in the United States. GeoENS on the other hand gives 8 characters of geohash resolution which corresponds to +-20 meter accuracy.

# Specification

This EIP proposes a new interface to ENS resolvers such that geo-spacial information can be recorded and retrieved from the blockchain. The interface changes are described below for "address resolvers" described in EIP137 however the idea applies to any record described in EIP1185 and EIP1062, namely DNS Resolvers, Text Resolvers, ABI Resolvers, etc.

# What is a geohash?

A Geohash (opens new window) is an interleaving of latitude and longitude bits, whose length determines it's precision. Geohashes are typically encoded in base 32 characters.

# function setGeoAddr(bytes32 node, string calldata geohash, address addr) external authorised(node)

Sets a resource (contract address, IP, ABI, TEXT, etc.) by node and geohash. Geohashes must be unique per address and are exactly 8 characters long. This leads to an accuracy of +-20 meters. Write default initialized resource value, address(0), to remove a resource from the resolver.

# function geoAddr(bytes32 node, string calldata geohash) external view returns (address[] memory ret)

Query the resolver contract for a specific node and location. All resources (contract addresses, IP addresses, ABIs, TEXT records, etc.) matching the node and prefix geohash provided are returned. This permits querying by exact geohash of 8 characters to return the content at that location, or querying by geographic bounding box described by a geohash of less than 8 character precision.

Any type of geohash can be used including Z-order (opens new window) Hilbert (opens new window) or the more accurate S2 Geometry (opens new window) library from Google. There are also ways to search the geographic data using geohashes without always ending up with a rectangular query region. Searching circular shaped regions (opens new window) is slightly more complex as it requires multiple queries.

# Rationale

The proposed implementation uses a sparse Quadtree (opens new window) trie as an index for resource records as it has low storage overhead and good search performance. The leaf nodes of the tree store resource records while non-leaves represent one geohash character. Each node in the tree at depth d corresponds to a geohash of precision d. The tree has depth 8 because the maximum precision of a geohash is 8 characters. The tree has fanout 32 because the radix of a geohash character is 32. The path to get to a leaf node always has depth 8 and the leaf contains the content (like IP address) of the geohash represented by the path to the leaf. The tree is sparse as 71% of the Earth's surface is covered by water. The tree facilitates common traversal algorithms (DFS, BFS) to return lists of resource records within a geographic bounding box.

# Backwards Compatibility

This EIP does not introduce issues with backwards compatibility.

# Test Cases

See https://github.com/james-choncholas/resolvers/blob/master/test/TestPublicResolver.js

# Implementation

This address resolver, written in Solidity, implements the specifications outlined above. The same idea presented here can be applied to other resolver interfaces as specified in EIP137. Note that geohashes are passed and stored using 64 bit unsigned integers. Using integers instead of strings for geohashes is more performant, especially in the geomap mapping. For comparison purposes, see https://github.com/james-choncholas/geoens/tree/master/contracts/StringOwnedGeoENSResolver.sol for the inefficient string implementation.

pragma solidity ^0.5.0;

import "../ResolverBase.sol";

contract GeoENSResolver is ResolverBase {
    bytes4 constant ERC2390 = 0x8fbcc5ce;
    uint constant MAX_ADDR_RETURNS = 64;
    uint constant TREE_VISITATION_QUEUESZ = 64;
    uint8 constant ASCII_0 = 48;
    uint8 constant ASCII_9 = 57;
    uint8 constant ASCII_a = 97;
    uint8 constant ASCII_b = 98;
    uint8 constant ASCII_i = 105;
    uint8 constant ASCII_l = 108;
    uint8 constant ASCII_o = 111;
    uint8 constant ASCII_z = 122;

    struct Node {
        address data; // 0 if not leaf
        uint256 parent;
        uint256[] children; // always length 32
    }

    // A geohash is 8, base-32 characters.
    // A geomap is stored as tree of fan-out 32 (because
    // geohash is base 32) and height 8 (because geohash
    // length is 8 characters)
    mapping(bytes32=>Node[]) private geomap;

    event GeoENSRecordChanged(bytes32 indexed node, bytes8 geohash, address addr);

    // only 5 bits of ret value are used
    function chartobase32(byte c) pure internal returns (uint8 b) {
        uint8 ascii = uint8(c);
        require( (ascii >= ASCII_0 && ascii <= ASCII_9) ||
                (ascii > ASCII_a && ascii <= ASCII_z));
        require(ascii != ASCII_a);
        require(ascii != ASCII_i);
        require(ascii != ASCII_l);
        require(ascii != ASCII_o);

        if (ascii <= (ASCII_0 + 9)) {
            b = ascii - ASCII_0;

        } else {
            // base32 b = 10
            // ascii 'b' = 0x60
            // note base32 skips the letter 'a'
            b = ascii - ASCII_b + 10;

            // base32 also skips the following letters
            if (ascii > ASCII_i)
                b --;
            if (ascii > ASCII_l)
                b --;
            if (ascii > ASCII_o)
                b --;
        }
        require(b < 32); // base 32 can't be larger than 32
        return b;
    }

    function geoAddr(bytes32 node, bytes8 geohash, uint8 precision) external view returns (address[] memory ret) {
        bytes32(node); // single node georesolver ignores node
        assert(precision <= geohash.length);

        ret = new address[](MAX_ADDR_RETURNS);
        if (geomap[node].length == 0) { return ret; }
        uint ret_i = 0;

        // walk into the geomap data structure
        uint pointer = 0; // not actual pointer but index into geomap
        for(uint8 i=0; i < precision; i++) {

            uint8 c = chartobase32(geohash[i]);
            uint next = geomap[node][pointer].children[c];
            if (next == 0) {
                // nothing found for this geohash.
                // return early.
                return ret;
            } else {
                pointer = next;
            }
        }

        // pointer is now node representing the resolution of the query geohash.
        // DFS until all addresses found or ret[] is full.
        // Do not use recursion because blockchain...
        uint[] memory indexes_to_visit = new uint[](TREE_VISITATION_QUEUESZ);
        indexes_to_visit[0] = pointer;
        uint front_i = 0;
        uint back_i = 1;

        while(front_i != back_i) {
            Node memory cur_node = geomap[node][indexes_to_visit[front_i]];
            front_i ++;

            // if not a leaf node...
            if (cur_node.data == address(0)) {
                // visit all the chilins
                for(uint i=0; i<cur_node.children.length; i++) {
                    // only visit valid children
                    if (cur_node.children[i] != 0) {
                        assert(back_i < TREE_VISITATION_QUEUESZ);
                        indexes_to_visit[back_i] = cur_node.children[i];
                        back_i ++;

                    }
                }
            } else {
                ret[ret_i] = cur_node.data;
                ret_i ++;
                if (ret_i > MAX_ADDR_RETURNS) break;
            }
        }

        return ret;
    }

    // when setting, geohash must be precise to 8 digits.
    function setGeoAddr(bytes32 node, bytes8 geohash, address addr) external authorised(node) {
        bytes32(node); // single node georesolver ignores node

        // create root node if not yet created
        if (geomap[node].length == 0) {
            geomap[node].push( Node({
                data: address(0),
                parent: 0,
                children: new uint256[](32)
            }));
        }

        // walk into the geomap data structure
        uint pointer = 0; // not actual pointer but index into geomap
        for(uint i=0; i < geohash.length; i++) {

            uint8 c = chartobase32(geohash[i]);

            if (geomap[node][pointer].children[c] == 0) {
                // nothing found for this geohash.
                // we need to create a path to the leaf
                geomap[node].push( Node({
                    data: address(0),
                    parent: pointer,
                    children: new uint256[](32)
                }));
                geomap[node][pointer].children[c] = geomap[node].length - 1;
            }
            pointer = geomap[node][pointer].children[c];
        }

        Node storage cur_node = geomap[node][pointer]; // storage = get reference
        cur_node.data = addr;

        emit GeoENSRecordChanged(node, geohash, addr);
    }

    function supportsInterface(bytes4 interfaceID) public pure returns (bool) {
        return interfaceID == ERC2390 || super.supportsInterface(interfaceID);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

# Security Considerations

This contract has similar functionality to ENS Resolvers - refer there for security considerations. Additionally, this contract has a dimension of data privacy. Users query via the geoAddr function specifying a geohash of less than 8 characters which defines the query region. Users who run light clients leak the query region to their connected full-nodes. Users who rely on nodes run by third parties (like Infura) will also leak the query region. Users who run their own full node or have access to a trusted full node do not leak any location data.

Given the way most location services work, the query region is likely to contain the user's actual location. The difference between API access, light, and full nodes has always had an impact on privacy but now the impact is underscored by the involvement of coarse granularity user location.