Maybe someone already thought of this, but in case not:
GoalProvide a decentralized system to convert memorable short names like "bitcointalk.bit" into a small amount of data (512 B, say), while making it impossible for anyone by any means to take down or block names so registered.
Naïve solutionYou can just put the name data into a block chain like Namecoin does, but this isn't ideal for (at least) these two reasons:
- Miners and network participants can blacklist certain names, preventing them from operating. In the case of miners, only a majority of mining power is necessary to ban a name network-wide.
- Network participants could perhaps be legally forced not to provide-for-download transactions/data related to certain domains. For example, a node operator could receive a DMCA takedown. (The exact legal details are debatable, but it's within the realm of possibility.)
(BTW, decentralized database systems usually have the same problem. Participants in the Tor hidden service DHT could refuse to provide service to certain hidden services which they blacklist, and if this happened on a wide scale it'd bring down the hidden service. I sketched out a possible solution for that problem in
this post.)
Enhancement 1: time-delay encryptionAssume name data is being mined into blocks. Instead of having the blocks be immediately readable, the name data portion can be temporarily encrypted in this way:
1. Hash together the concatenated hashes of the blocks with depth 20 through 120 or so to get a seed.
2. Using the seed, choose a random pubkey point on a secp256k1-like curve. You get the point directly, not by producing a private key.
3. Once you solve the block, you will asymmetrically encrypt the namedata portion to that pubkey.
4. In order to solve the block, you need to brute-force the last not-yet-decrypted block from eg. ~24 hours ago, and include the private key in your new block. This is unsuitable as a timestamping proof-of-work, so after you do this and encrypt the namedata, you also have to timestamp your block hash using OpenTimestamps or similar.
Unlike eg. RSA, AFAIK all valid-looking secp256k1 pubkeys have a private key. Difficulty should be auto-adjusted to maintain the ~24-hour delay by producing modified versions of secp256k1 with smaller integer sizes.
You could also use symmetric crypto with a random instead of seeded key, but then the miner knows the key, so you can't use it for PoW. Also, although I don't use it in this post, it might be useful in some cases to allow people to encrypt transactions/data to one of these pubkeys.
This prevents miners from soft-forking out blocks which contain banned names. By the time they can test whether the block contains a banned name, it'll be deep in the chain and therefore difficult to undo.
Enhancement 2: mixing together namedataEach block needs to contain a function which takes a name and produces the output data for that name. Typically this is done as just a list, but this makes it easy to modify the list. If a name is banned, nodes could republish block data with that name's data redacted. My solution to this is to construct the function so that all of the name data is jumbled together, it's not immediately obvious which names are contained in it (though you can test individual names), and you can't remove one name without affecting everything else. The best thing I've come up with for constructing such a function is:
1. Let hash(name) = encHash and hash(encHash) = idxHash. The name's data is encrypted with the key encHash before being published to the network.
2. Each miner generates a random key and encrypts idxHash and the name data before dealing with them, purely to ensure that they are uniformly random. This key is published in the block's unencrypted segment.
3. Looking at all idxHash values in his candidate block, the miner attempts to find a most-minimal subset of their bits such that each idxHash is uniquely identified by as few bits as possible. (Note that duplicate idxHash values are not allowed.) The chosen bits can be in any order, and need not be contiguous. For example, a miner might find that bits 2,3,10,15,22,1,40,32,100,125 results in unique IDs for 500 entries. This is published in the final block.
4. Using the smaller index value for each name, the miner constructs a truth table with the index as input bits and the double-encrypted name data as the output bits. When the block is nearly complete, the miner converts this truth table into an as-minimal-as-possible set of boolean formulas.
Example:
Say that you have these keys (name hashes) and values:
KEY VALUE
6A80AE9 A1
CDE2E9D 22
14DB3CF B3
1F43947 24
2CA8297 45
(In reality the keys would be 256 bits long, the values would be perhaps 4096 bits long, and there would be many more pairs.)
First, I choose a small subset of bits from the input such that each pair has a unique value. I choose bits 11-8, giving a binary truth table like this:
IN OUT
1010 10100001
1110 00100010
0011 10110011
1001 00100100
0010 01000101
And then I create boolean formulas from that, dictating the output of each bit 7-0:
e1 = i3&!i2&!i0;
e2 = i1&i0;
e3 = !i3&!i0;
o7 = e1 | e2;
o6 = e3;
o5 = !i1 | e1 | e2 | i2;
o4 = e2;
o3 = 0;
o2 = !i1 | e3;
o1 = e2 | i2;
o0 = e1 | e2 | e3;
That's the function. When given the a key, it produces the correct output. Eg. for input 0011 you get:
i3 = 0
i2 = 0
i1 = 1
i0 = 1
e1 = i3&!i2&!i0 = 0;
e2 = i1&i0 = 1;
e3 = !i3&!i0 = 0;
o7 = e1 | e2 = 1;
o6 = e3 = 0;
o5 = !i1 | e1 | e2 | i2 = 1;
o4 = e2 = 1;
o3 = 0;
o2 = !i1 | e3 = 0;
o1 = e2 | i2 = 1;
o0 = e1 | e2 | e3 = 1;
But you can't tell by looking at the function which keys were used to create it. You can test that it contains a name by trying to resolve the name using the function's data and seeing if it works, but if you want to remove it from the function, there's no way to do so without possibly ruining other keys, since you don't know what other keys are represented in the function, and everything is tangled together.
Sketch of the rest of a DNSEvery block should have a bloom filter matching the idxHash values within it, in the encrypted segment. To resolve a name, you'd go through every block in the past and check the name's idxHash against the bloom filter. If it passes the bloom filter, you reconstruct the data using the function explained above and try to decrypt it using its encHash. If it decrypts with a good MAC, then it's OK. You get the current name data by replaying its entire history of valid namedata updates, the first-ever of which will have a pubkey with which the rest are signed. Names might expire if not updated for a few years, to allow lost ones to return to the pool.
For payment, this is the best I could come up with: To register/update a name, you'd pay a "registrar" and give them the encrypted namedata update & idxHash. The registrar would send the namedata update to all miners along with a willing-to-pay price, signed with the registrar's own key. When a miner includes it (which the registrar & other miners can check by trying to find the idxHash in every future block once it's decrypted), the registrar pays a miner-address listed in the block the promised amount. Miners keep track of which registrars are actually paying them the promised amounts, and will blacklist any who stiff them. To start a new registrar, you might pay a miner an initial fee to get them to start listening to your transactions.
Miners would be constantly trying to brute-force the last unbroken encryption key from about a day ago. Unlike with normal cryptocurrencies, they wouldn't actually construct their final block until they found the solution. When they find it, they'd use OpenTimestamps to timestamp their block, wait for a timestamp-on-Bitcoin confirmation, and then broadcast it. To prevent withholding attacks, nodes would refuse to ever reorg unless the two candidate blocks are actually seen within minutes of each other. The brute-force difficulty might adjust only if the block interval goes outside of a pretty large range, which would allow for block generation to be more responsive to demand.
FlawsWhen you first register a name, nobody has any idea what it is since registrars and miners only get the hash and the encrypted data. But once the name becomes publicly-known, registrars and miners could refuse to process matching idxHash updates. This may be somewhat annoying, but since a softfork banning the name network-wide isn't possible, enough darknet registrars/miners should exist to make this not too much of a problem.
To resolve a name, you have to download and scan through every past block. I think that blocks should be pretty small (perhaps about 25-50kB per 10k domain updates?), and the max block size could be set very restrictively. Scanning a single block should be extremely fast, and it's also parallelizable. But after many years, the history could accumulate to the point of being problematic, and I can't see a perfect way of resolving this. One optimization would be to require that every domain send at least one update a year, and require that every update contain a pointer to the first-ever update which created the name; then, if there are no conflicts in a year, you can just trust that one, and if there are conflicts, you can check through a subset of the whole history to figure out which claim is correct.
To prevent miners from filling up every block with domain-squatted domains, maybe there should be some additional cost for every registration. One way to do this would be to require a hashcash proof-of-work in the data for every new domain -- if it's not there, then the registration is ignored at resolve-time as if it didn't exist.
I wonder if it's theoretically possible to create a homomorphic encryption scheme where an encrypted registry database is maintained which nobody has the decryption keys for, but it's still possible to do lookups. That'd be ideal.
