In particular, a very big issue with this and also possibly adapted proposals based on the same idea is this: As soon as someone is able to control the coinbase of a Bitcoin pool, it is game over. This, on the other hand, is not too difficult - at least if there are miners who'd rather sell their coinbase space than behave "honestly" (from a Namecoin point-of-view, which may not interest Bitcoin miners). Of course, this is still much more effort to do than just manipulate an old-school DNS query ... so something like the proposal could be useful nevertheless, if the users are aware of the trade-off between security and usability they are taking.
Apart from this issue, I think that one can, indeed, change the validation such that, logically speaking, "existence of a fraudulent proof implies that the attacker had control over a Bitcoin miner's coinbase". I can work this out (have the ideas all together already), but before I do that, I'd like to know whether there's actually interest in that.
Proof-of-Work Secured Namecoin API Queries
==========================================
Abstract
--------
Unlike Bitcoin, in Namecoin also significant value lies in "read-only"
clients. They can be used, for instance, to resolve .bit domains, access
id/-data and use them in other, not-yet-developed ways. Currently, even
clients that are only meant to be read-only have to run a full node and
download as well as store the blockchain. This incurs significant burden.
In this document, we propose a way to use a central, untrusted API server to
access Namecoin data. Our specific proposal includes a way for the server to
add a "proof" that the data is likely authentic and not manipulated. This
gives the client a reasonable trade-off between security and usability.
As opposed to SPV, our method does not require the client to keep a list of
all block headers in the chain (and thus have some up-to-date connection to
the Namecoin network).
Basic Overview
--------------
Changes to the name database in Namecoin are represented by special
transactions. Those transactions, in turn, are included in a Merkle tree of
all transactions in a block. The blocks, finally, include a proof-of-work
(either directly or in the form of auxpow) created by miners. With the
current mining power employed by the Bitcoin network, it is very hard and
expensive to construct such a proof-of-work.
Thus, if an untrusted API server returns a hash chain that links its answer
for a name query to a proof-of-work, this gives the requesting client much
more confidence that the provided answer is not manipulated. (As an attacker
trying to do that would have to expend significant resources.)
Such a proof can be constructed by taking the last name-update operation
performed on the requested name, its Merkle branch, and possibly the Namecoin
block header's auxpow. To return an even stronger proof, the server can also
return a chain of multiple Bitcoin block headers building on the one that
contains the Namecoin header's auxpow.
Format of an Answer with Proof
------------------------------
The proof should contain the full, serialised Namecoin transaction updating
the name. It is not enough to return just the name's value: Even if proof is
given that this value occurs in the blockchain (by adding a proof-of-work), it
could be part of a specifically crafted (but valid and easily mined)
transaction that does not actually update the name. For instance, the desired
value could be part of an output script (even using, e. g., OP_RETURN)
or could be the value of a transaction updating a different name.
For the proof-of-work itself, we propose to give it in form of a "script"
which the client evaluates to check the proof. The script can be serialised,
for instance, as a JSON array where every entry corresponds to an "operation"
to be performed. The client has to keep a current "state", which is
initialised by a double SHA-256 hash of the serialised transaction. The state
is updated during the script evaluation. The following operations will be
necessary:
{
"op": "hash",
"prefix": HEX-STRING,
"postfix": HEX-STRING
}
"prefix" and "postfix" are optional and assumed to be an empty string if
missing. Concatenate prefix, state and postfix and set the new state to the
double SHA-256 hash of the resulting byte array.
{
"op": "reverse"
}
Reverse the bytes in the current state. This operation appears during auxpow
validation and is thus necessary.
{
"op": "block",
"prefix": HEX-STRING,
"postfix": HEX-STRING
}
Perform an operation as with "hash" above. Additionally, before hashing
the concatenated byte array, interpret it as block header and extract the
stated difficulty. If the resulting state (i. e., the block hash) does not
fulfil this difficulty (or if the byte array is not a valid block header),
abort the proof as invalid. If it does, increment the verified amount of work
for the answer by the work corresponding to the stated difficulty.
Verifying an Answer
-------------------
As a first step, the client has to parse the serialised transaction sent by
the server, and look for outputs that have name-script prefixes. The simplest
logic possible for it to implement could work like this:
1) Check that the transaction has a Namecoin-tx version.
2) Ignore all inputs (but parse enough data to know what to skip).
3) Parse all output scripts until one is found that performs an
OP_NAME_UPDATE or OP_NAME_FIRSTUPDATE.
4) If no such output is found or if the updated name does not match the
requested name, ignore the answer as invalid.
5) Otherwise, use the value in the update to resolve the name.
Either before or after this sequence, the proof script has to be checked
according to the previous section. If the total verified work at the end of
the script exceeds some treshold, accept the answer as valid and "proven".
Alternatively, the client can present the amount of work in some suitable form
to the user and let the user decide whether to accept or reject the answer.
Security Guarantees and Possible Weaknesses
-------------------------------------------
We assume that an attacker does not have the resources to create a
proof-of-work matching the client's treshold value. If the treshold is chosen
on the order of magnitude of the Namecoin or Bitcoin difficulty, an attacker
capable of constructing such a proof-of-work probably also has enough
resources to compromise the victim's system in another way. Thus, we believe
that this assumption is reasonable.
Checking the serialised transaction according to the description in the
previous section implies that it is only valid for the Namecoin network if it
really represents a name update of the requested name by its rightful owner.
Furthermore, since no transaction with Namecoin version is allowed to have
more than one name output, it is fine to abort parsing after the first name
output found. (Transactions before the block 212,500 do not necessarily
fulfil this criterion, but there is only a small and well-known number of them
in the blockchain.)
Possible attacks and weaknesses:
1) While the proof may guarantee (absent the other weaknesses mentioned
below) that the returned value *was* the name's correct value at one
point in the past, it can not guarantee that it *is* the current value.
If this guarantee is required, a system based on committing a Merkle tree
of all names to each block seems like the correct solution.
2) Building on 1), if a name is expired and re-registered or transferred to
a new owner, proofs can be constructed that return all of the values the
previous owner may have set the name to. Thus, a proof does not
guarantee that the returned value was ever endorsed by the current name
owner. To partially resolve this issue, the client could also extract
timing information of the block headers in the script and warn the user
if the time is very far in the past. (Or display the time in some
suitable way and let the user decide.)
3) With the system described above, it is still possible to build a
serialised name-update transaction that parses but is not valid (because
the attacker does not have the necessary signing key). This transaction
could be put as a whole into the value of some name owned by the
attacker, and then a valid proof based on the "hash" operation as
described can be constructed. It is probably possible to avoid this to
some degree by imposing more stringent checks in the script operations.
Verifying Merkle branches only ever sets *either* prefix *or* postfix,
and the set value is precisely 32 bytes in length. However, *both* prefix
*and* postfix are still necessary to build a block hash and to verify
auxpow. So care must be taken when working out the stricter rules.
(But it is probably possible to define rules that can securely
differentiate a transaction from a block header and auxpow. Since an
auxpow must be a coinbase transaction, if one verifies the index
in the Merkle tree to be zero, one knows at least that a miner was
directly involved in creation of the proof. Unless miners sell space
in their coinbase cheaply.)
4) If an attacker is a miner, they have a strong economic incentive to use
their hash power to mine valid blocks and not expend it on creating a
false proof. However, the miner could construct a malicious alternative
block header and merge-mine it together with the correct Namecoin chain.
If this situation is considered to be a threat, the checks can be
expanded to verify the auxpow chain ID. However, a miner could still
decide to merge-mine the attack block instead of Namecoin, which would
incur "only" an opportunity cost of the Namecoin block reward instead of
losing also the Bitcoin block reward (as would be the case if the hash
power would be expended solely on creating the attack proof-of-work).
Conclusion
----------
We believe that our proposal could greatly improve the availability of "light"
Namecoin resolvers, while still providing them with reasonable security
against manipulations by the API server. However, at least some of the
weaknesses mentioned need further discussion and should be resolved before
the system becomes useful in practice. But it should be possible to find
solutions that still allow a client to relatively easily verify the proof. In
particular, the client should not need a connection to the Namecoin network
(no internet access at all, in fact) and also no need to store large amounts
of data.
It may be necessary, though, to remove the flexible "scripting" in the proof
and instead make it consist of more strictly-defined data. (The Merkle
branch, Namecoin block header, auxpow and possibly a chain of Bitcoin block
headers.) This reduces the possibilities that an attacker has at constructing
a malicious proof that can be included in a valid transaction (and thus mined
by the network without cost to the attacker).
The possibly most serious issue is that a miner can always merge-mine a
fraudulent Namecoin block and still be paid the Bitcoin block reward. This
means that for a cost of just a *Namecoin* block reward (which is not too
significant), it can construct a malicious proof of, for instance, a very
valuable domain. While this means that an entity that possesses significant
hashing power is required, a "rational" but not "honest" miner could sell the
creation of such an invalid proof for an amount that is larger than the
Namecoin block reward it could reap by behaving honestly. The cost incurred
on an attacker in buying such a proof is not big. There seems to be no way to
avoid this issue, except for the client having a list of valid Namecoin block
headers. In this case, though, it is back at being an SPV client.