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.
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
Yes. And it is totally possible that a "common" and default use case with GNS looks just like DNS.
The spec just does not mandate the governance. In fact, it mandates implementations to honor user-chosen configurations for petname overrides.
(See my other comments)
It is important to distinguish the technical procedure of resolving a name with the namespace governance.
You could imagine a system where you manage your DNS root zone locally ("hyperlocal") and there is NO consensus on what it contains.
The DNS resolution mechanism could support such a concept.
It is only the de-facto rule of ICANN over the root zone what makes DNS names globally unique.
And IETF/Standards do not allow to diverge from this.
The GNS specification explicitly allows it. That is it.
It does not mandate that users must bootstrap their root using fancy hand-picked petnames.
In practice, a common set of root zone entries will very likely exists.
The specification does not mandate the governance.
There could be a world in which DNS names as we know them today are resolved using the GNS resolution mechanism with no tangible difference to the user.
There are a lot of stakeholders involved and a lot of applications relying on DNS may have problems (browsers).
So the migration path is long and winded I guess.
Other than that, no.
GNS itself could also be realised on top of other DHTs, such as libp2p/IPFS (before anyone mentioned the, eh, maturity issues of the reference implementation in GNUnet.)
Theoretically, you could combine a blockchain-based root zone governance (e.g. Handshake) with GNS. This would give you globally unique names and efficient and private delegated names.
In general, not a fan of BNS beyond that, through, as upkeep is too resource intensive. It is just not a sustainable and efficient thing to do for names.
Well compelling the TLD owner (in this case .com) through the courts to change the delegation to your zone also works in GNS. (You would not force some kind of "hand over" of the example.com domain. Because that is not how it works).
Similarly "buying the domain" simply means having this party yield the registration at the domain registrar to you.
Anyway, both also works in GNS.
My example addresses the case where the legal claim is not possible and the other party uncooperative while "consensus" is that it is a squatter with no claim. (Or, by extension, a censorious circumstance, think TPB)
Yes, and you could apply the DNS governance model to GNS.
For example:
Let's say GNS gets traction. Users and implementation could provide a list of start zone mappings which are managed by ICANN and use this as a default.
Effectively, this will give users global names. Just like now.
.de will be managed by DENIC, .fr will be managed by AFNIC etc.
BUT: GNS is designed to allow to override such a setting.
The ICANN root zone may be delegated by the user into the .icann namespace.
So, locally, example.com in DNS would become example.com.icann in GNS.
Alternatively, the user may also override ANY TLD mapping provided by the ICANN configuration - or individual domains - if needed.
For example, if a domain is seized or otherwise censored in DNS.