database) set to all block headers, SPV clients can get a way to verify
that a untrusted node or server answers truthfully to queries for names.
This is a very useful thing to have for building "one-click install"
like resolvers and other tools on top of Namecoin. I've investigated
a bit how those commitments could be done based on a trie
data structure.
What is a trie?
See also Wikipedia. Basically, a trie is a special kind of search tree that
is especially suited when the index set is a set of "strings". A simple
example for such a trie, containing the strings "d/a", "d/x" and "d/ab":
Code: Select all
d: null
/: null
a: {...}
b: {...}
x: {...}a tree in ASCII and fail doing so.) Here, {...} stands for some data
associated to a name (as per name_show, for instance) and null means that a
particular name has no data.
As you can see, one can relatively efficiently locate, insert and remove data
from a trie (like with other search trees). Furthermore, each node in the
trie corresponds to an entire "sub-trie" of names starting all with the same
prefix. This is, IMHO, a very useful property (see also below).
How does the commitment work?
We can now define a root hash of such a trie: Compute a hash over
the data as well as all children, but replace the individual child sub-tries
first by their hashes. This construction is similar to a Merkle tree.
The top hash is then committed somehow (e. g., in the coinbase input) in
the blockchain, which could be done by a softfork and should be mandatory
(and verified by full nodes).
A node can now query an untrusted server for a name, and the server
can return the "reduced nodes" (with children replaced by their hashes)
for all trie nodes upward from the requested name.
(One for each character in the string.) It can then use these
to independently compute the root hash and compare it with the blockchain.
Since the returned data for the requested name is part of the hash, the
SPV node can determine that the answer is correct if the root hashes match.
It is also possible to prove that a name does not exist: Just return
the reduced nodes for all prefixes of the requested name that do
exist. Then either the full string is represented by them but the final
node has no data, or only a prefix can be found which does not contain
a child for the next character of the name anymore. In both cases can
the hash be verified and the node be sure that it got a truthful negative
answer.
Why not use Merkle trees?
Of course, one can also construct a Merkle tree of all names and use that
as commitment. However, I believe that a trie has the following advantages:
- It can be kept from one block to the next, then only updated names
need to be updated in the trie. With a Merkle tree, it is necessary to
reconstruct the tree when the set of names changes. (At least I think so.) - With the trie, a node can request a full sub-trie corresponding
to a prefix and verify that as well. This allows to query, for instance,
for an offline database corresponding to a full namespace. Or, the node can
query for a prefix subtree in order to hide the actual name it is interested
in for privacy reasons.
I've implemented building of such tries in the "uno-trie" branch
of my Github for Namecore. A quick result for mainnet on my laptop:
Building the trie and serialising it to compute the size takes around
19 seconds. Just building the trie for the hash should require a little less,
although I don't think the difference will be too much. Memory usage of the
process increases from 110 MiB to 400 MiB, but the serialised size of the trie
(corresponding to the full name database including all values,
name addresses and outpoints) is only around 50 MB in size.
I believe that this is not a prohibitive performance cost for this feature.
Note that a miner and full node only needs to either keep the trie in
memory all the time (then updates should be very fast) or rebuild the
trie for each block (then the memory can be freed immediately again, and
probably one can even build the hash without keeping the full trie in memory
all at once).
It may be beneficial to require that each block should contain the hash of the
previous block's UNO set. That way, the computation of the root hash
can be done once and need not be updated when more transactions are added to
the block. (Only when the previous block it builds upon is changed.)