Co-author here. If you look into the R5N paper (link in draft), you can find this term. If you assume a routing performance of O(log n) and O(sqrt (n)) number of lookups to find the value, you get O (sqrt (n) * log n) as overall complexity (last section in paper).
For the argument of the sqrt (n) itself, see the paper.
Edit 1: Quote: "Assuming that T [random path length] is chosen large enough to achieve perfect mixing, sqrt (n / (cā1)) replicas would need to be created in order for a GET request to succeed with about 50% probability according
to the birthday paradox."
Edit 2: In a world without local minima the term itself will be 1 (you only need a single lookup and will find the value with 100% probability.
In the restricted route scenario you will have to so O(sqrt(n)) lookups.
Aha, thanks for that, the paper seems to reason better at first glance, I'll read it.
You mention sybil attacks on Kademlia, especially those that arise because nodes may set their ID and "camp around" some known key in the hash table. How is this addressed here? By glancing over the standard draft, I see the identifier is just a SHA-512 of the pubkey. Wouldn't it be feasible to bruteforce the first some bits of the key and "camp around" some keys a malicious sybil actor wants to deny service to?
Our recent webinar shows the state of GNS, and addresses some recurring questions regarding governance, how name registration is supposed to work and the RFC.
This is correct.
I would like to add that the ISE also had us engage with a variety of stakeholders within the IETF (dnsop, for example, as part of discussions on RFC 9476) and also expected some third party reviews.
These are all valid deployment questions, which we tried to address in Appendix A.
In a nutshell, we expect that resolvers would ship with a (large) set of default "suffix-to-zone" mappings, that can be overridden by the user to provide a usable and convenient out-of-the box experience.
Not that "we expect" means that this would be the ideal scenario, not something to expect when installing our reference implementation right now.
Indeed that would work. In theory. Especially since we thought of that use case (delegation into DNS) with the GNS2DNS record type.
There is a BUT: You need an initial label for ICANN zone to resolve the names.
Unless you have a resolver implementation that "hides" the zkey of ICANN in the UI. But technically, under the hood, a name for this ICANN zone would look like:
www.example.com.THEICANNZKEY...
ICANN could also publish the TLDs individually as zones, however, and you could have an "ICANN Start Zone" (see Start Zone in the RFC) consisting of the TLD/zone key mappings.
GNS, in theory, could replace DNS (the technology) and reuse its current root governance model as default.
From the point of view of GNS namespace governance is separate from name resolution protocols.
Of course, from the point of view of a lot of DNS folks, DNS is both: The governance (ICANN) and the technology (RFC 1035 et al) and indivisible.
FWIW we have recently acquired funding to demonstrate that GNS can handle large size zones by migrating TLD zones (available through AXFR for now, the number of zones supporting hat is, eh, marginal [1]) to GNS which delegate back into DNS (using [2]).
This allows GNS users to (partially) circumvent the root and manually manage their local root namespace as envisioned for GNS [3].
We think that shipping default configurations and allowing users to modify/enhance that locally is how governance should look like from the user's perspective.
If you want ICANN as default -> use the ICANN default configuration... if you need to override a censored/censoring registry, you can do that too... etc
