One of the DNS issues I tried to fix with NIS+ was the 'maintaining a list of trusted servers' problem by distributing the management of the authoritative servers. Trust was built bottom up, and authority came top down.
The way it worked was that clients used a 'coldstart' file which was the (small number) of servers you trusted to provide your namespace lookups. You to their public key and you put it into your coldstart file. Similarly, a server put the key(s) of the servers it trusted above it in the name space in its coldstart file. And at company 'root' level was a set of servers run by a trusted authority.
Locating the authoritative name server for x.y.z from p.q.z (same as DNS root is rightmost) client in x.y.z asks its server for a trusted y.z server, gets it, and asks that server for a trusted z. server, then asks that server for a q.z. server and finally for a p.q.z. server. Once this has happened once you know trusted servers can can jump to the nearest one to start resolving a new path in the namespace.
It was slower on initial lookup and then just as fast as DNS on later ones.
It had the downside that compromised (or borked) high level servers could send you on a different path to different root if the server above them was incorrect.
It is one of the more fun problems in the whole name/directory service space.
DNS SEC doesn't seem any closer to solving this problem, unfortunately.
Do you know of any designs that require a quorum at each level prior to trust? BitCoin seems to be having success with this model, but I'm wondering if anyone's built something like that with the primary intent of creating a directory service.
I don't think they have, much of the work on directory services died when people gave up. DNS was "too hard" to change and Microsoft wasn't going to let anything make into a standard that killed off the need for Active Directory. The LDAP guys, being formerly X.500 guys, went off solving a different problem and ended up somewhat stuck between AD and DNS. Sad really.
That said, your idea about poaching the Bitcoin quorum ideas is a good one. Essentially a data structure, equivalent to the block chain, where it only gets authenticated if enough people ack that its the most valid version of reality. Probably a publishable paper in exploring that question.
I love the fact that AD, and this newer posixy clone FreeIPA essentially operate as independent but interdependent directory services: LDAP, Kerberos, and DNS, and they still need X.500 in the form of SSL CA trusts to finish gluing it all together.
You may see an email from me in the next few weeks asking for feedback on such a paper.