Proof-of-Work Secured Namecoin API Queries

Post Reply
domob
Posts: 1129
Joined: Mon Jun 24, 2013 11:27 am
Contact:

Proof-of-Work Secured Namecoin API Queries

Post by domob »

Below is a proposal for an idea phelix, cassini and I discussed recently. It was written on a train from Munich to Graz, so is not really fully worked out. While I like its "elegance", it won't work as described (see at the end). I'll put it here nevertheless so encourage discussion.

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.
BTC: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS
Use your Namecoin identity as OpenID: https://nameid.org/

biolizard89
Posts: 2001
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Proof-of-Work Secured Namecoin API Queries

Post by biolizard89 »

While this is an improvement over a plain name-->value API, I guess I'm not clear on which use cases make it necessary to not use SPV. My understanding is that you only need SPV headers for the last 36 kiloblocks to verify any name, and these can be provided by an API server rather than the Namecoin network (if, e.g. the Namecoin protocol is blacklisted by a firewall or something). Am I unaware of some use cases here?
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

phelix
Posts: 1634
Joined: Thu Aug 18, 2011 6:59 am

Re: Proof-of-Work Secured Namecoin API Queries

Post by phelix »

biolizard89 wrote:While this is an improvement over a plain name-->value API, I guess I'm not clear on which use cases make it necessary to not use SPV. My understanding is that you only need SPV headers for the last 36 kiloblocks to verify any name, and these can be provided by an API server rather than the Namecoin network (if, e.g. the Namecoin protocol is blacklisted by a firewall or something). Am I unaware of some use cases here?
Well, this is even lighter and simpler than SPV. What is the average size of a Namecoin block header (with auxpow)? 300 bytes? That would make more than 14MB. 50 block headers would only be a little more than 15kb and could be served with every request.

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
Important point. Maybe a look at the timestamps can help a little. If the headers time stamps are far apart they might have been forged. Is there a rule to enforce that auxpow Bitcoin / Namecoin block headers must have a time stamp with a limited difference?
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

biolizard89
Posts: 2001
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Proof-of-Work Secured Namecoin API Queries

Post by biolizard89 »

phelix wrote:
biolizard89 wrote:While this is an improvement over a plain name-->value API, I guess I'm not clear on which use cases make it necessary to not use SPV. My understanding is that you only need SPV headers for the last 36 kiloblocks to verify any name, and these can be provided by an API server rather than the Namecoin network (if, e.g. the Namecoin protocol is blacklisted by a firewall or something). Am I unaware of some use cases here?
Well, this is even lighter and simpler than SPV. What is the average size of a Namecoin block header (with auxpow)? 300 bytes? That would make more than 14MB. 50 block headers would only be a little more than 15kb and could be served with every request.
Right, this is somewhere between SPV and a name-->value API in terms of both complexity and security. What I'm asking is, what use cases exist where this is necessary or even particularly useful? I don't know exactly the size of the average Namecoin block header, but assuming 14 MB as you are, I can't think of any real-world use cases where downloading ~14MB of bootstrap data, plus on average 300 bytes per 10 minutes, is problematic. I can do that on my 3-year-old phone with zero trouble. Maybe I'm missing a use case?
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

phelix
Posts: 1634
Joined: Thu Aug 18, 2011 6:59 am

Re: Proof-of-Work Secured Namecoin API Queries

Post by phelix »

biolizard89 wrote:
phelix wrote:
biolizard89 wrote:While this is an improvement over a plain name-->value API, I guess I'm not clear on which use cases make it necessary to not use SPV. My understanding is that you only need SPV headers for the last 36 kiloblocks to verify any name, and these can be provided by an API server rather than the Namecoin network (if, e.g. the Namecoin protocol is blacklisted by a firewall or something). Am I unaware of some use cases here?
Well, this is even lighter and simpler than SPV. What is the average size of a Namecoin block header (with auxpow)? 300 bytes? That would make more than 14MB. 50 block headers would only be a little more than 15kb and could be served with every request.
Right, this is somewhere between SPV and a name-->value API in terms of both complexity and security. What I'm asking is, what use cases exist where this is necessary or even particularly useful? I don't know exactly the size of the average Namecoin block header, but assuming 14 MB as you are, I can't think of any real-world use cases where downloading ~14MB of bootstrap data, plus on average 300 bytes per 10 minutes, is problematic. I can do that on my 3-year-old phone with zero trouble. Maybe I'm missing a use case?
Who will serve the data? The API server can't do it. The network? Then you will have to write a light client. With this solution you don't need any networking. It is "almost finished" and should still be way more secure than normal DNS requests.
nx.bit - some namecoin stats
nf.bit - shortcut to this forum

biolizard89
Posts: 2001
Joined: Tue Jun 05, 2012 6:25 am
os: linux

Re: Proof-of-Work Secured Namecoin API Queries

Post by biolizard89 »

phelix wrote:
biolizard89 wrote:
phelix wrote:Well, this is even lighter and simpler than SPV. What is the average size of a Namecoin block header (with auxpow)? 300 bytes? That would make more than 14MB. 50 block headers would only be a little more than 15kb and could be served with every request.
Right, this is somewhere between SPV and a name-->value API in terms of both complexity and security. What I'm asking is, what use cases exist where this is necessary or even particularly useful? I don't know exactly the size of the average Namecoin block header, but assuming 14 MB as you are, I can't think of any real-world use cases where downloading ~14MB of bootstrap data, plus on average 300 bytes per 10 minutes, is problematic. I can do that on my 3-year-old phone with zero trouble. Maybe I'm missing a use case?
Who will serve the data? The API server can't do it. The network? Then you will have to write a light client. With this solution you don't need any networking. It is "almost finished" and should still be way more secure than normal DNS requests.
If this is intended to be an inferior system to SPV, for use until SPV (with Namecoin wire protocol support for getname) is coded, then that makes sense. That wasn't clear to me.
Jeremy Rand, Lead Namecoin Application Engineer
NameID: id/jeremy
DyName: Dynamic DNS update client for .bit domains.

Donations: BTC 1EcUWRa9H6ZuWPkF3BDj6k4k1vCgv41ab8 ; NMC NFqbaS7ReiQ9MBmsowwcDSmp4iDznjmEh5

domob
Posts: 1129
Joined: Mon Jun 24, 2013 11:27 am
Contact:

Re: Proof-of-Work Secured Namecoin API Queries

Post by domob »

phelix wrote:
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
Important point. Maybe a look at the timestamps can help a little. If the headers time stamps are far apart they might have been forged. Is there a rule to enforce that auxpow Bitcoin / Namecoin block headers must have a time stamp with a limited difference?
The only rule I'm aware of is that a block's timestamp must be within +- 2 hours of the node's clock to be accepted. I don't think that this is a a-posteriori rule when validating the blockchain, just for networking (but I may be wrong here). What I definitely know is that no timing is enforced in auxpow.

But your point is not bad - one could request a chain of multiple consecutive NMC block headers and verify that they are not too far apart plus that they have a "reasonable" difficulty. In this case, a miner can't construct a malicious proof when it gets lucky finding a Bitcoin block, but it really has to have also a significant hash power. Not sure about the details, though.
biolizard89 wrote:If this is intended to be an inferior system to SPV, for use until SPV (with Namecoin wire protocol support for getname) is coded, then that makes sense. That wasn't clear to me.
I wouldn't say that this is only useful until SPV is implemented. As phelix said, I also think that keeping an up-to-date list of block headers is not as trivial as you make it sound. It requires a connection to the Namecoin network itself besides the API server, including node discovery (to get the extra security, you have to make sure that an attacker can't easily connect you to nodes of their own!), networking commands and a lot of extra stuff. The idea as proposed here means that you really just have to query an API and do some offline processing.
BTC: 1domobKsPZ5cWk2kXssD8p8ES1qffGUCm | NMC: NCdomobcmcmVdxC5yxMitojQ4tvAtv99pY
BM-GtQnWM3vcdorfqpKXsmfHQ4rVYPG5pKS
Use your Namecoin identity as OpenID: https://nameid.org/

Post Reply