Auxpow Security

[globaltoken]

Hello @domob1812,

I have a question regarding to the security of auxpow.
Auxpow is not part of the CPureBlockHeader, so it will not be hashed.

Is there a security mechanism, that protects it against forgery?
What I think now is: Is it possible to manipulate a block and insert different auxpow?
I mean there would be no sence to do it, but there is no hash mechanism which validates, if this auxpow was the one, that was included in this block?

So if you would modify block X with a new auxpow, it is still valid, because the blockhash will not change.
Then you have a different auxpow for block X then all other nodes, and if someone syncs from you, you distribute the "wrong" auxpow. The requirement must be, that the auxpow is valid. But its a completly different auxpow, than it was at the beginning.

I hope you can understand what I mean, it would be nice to discuss.

Thank you.

[domob1812]

Yes, it is true that you can replace the auxpow by a different one if you like - but as you say, why would someone do that? And more importantly, why do you think that would be a problem?

[JeremyRand]

@domob1812 can you please transfer this issue to the Namecoin repo rather than your personal repo, so that we have proper transparency about threat model discussions? (Not sure why it was reported here.)

I have a question regarding to the security of auxpow.
Auxpow is not part of the CPureBlockHeader, so it will not be hashed.

Is there a security mechanism, that protects it against forgery?
What I think now is: Is it possible to manipulate a block and insert different auxpow?
I mean there would be no sence to do it, but there is no hash mechanism which validates, if this auxpow was the one, that was included in this block?

So if you would modify block X with a new auxpow, it is still valid, because the blockhash will not change.
Then you have a different auxpow for block X then all other nodes, and if someone syncs from you, you distribute the "wrong" auxpow. The requirement must be, that the auxpow is valid. But its a completly different auxpow, than it was at the beginning.

@globaltoken While I can't think of any significant security issues with the current design as deployed, I can think of 2 interesting effects of the current design:

1. The AuxPoW headers provide useful information about the parent blocks, such as the timestamps. This can be used for forensic analysis of miner behavior, e.g. analyzing reorg attacks on the sidechain. Forging historical parent blocks with original timestamps is extremely expensive because such a parent block won't be valid anymore in the parent chain. However, I don't see anything that prevents a miner from committing to a historical sidechain block in a current parent chain block, and in that case the miner is only throwing away the sidechain reward. (Maybe I'm missing something that invalidates this analysis; curious what Daniel thinks.)
2. The AuxPoW headers' non-contribution to the sidechain block hash allows AuxPoW data to be truncated for users who already have a reason to believe that a given block has valid PoW (e.g. because the block is committed to by a checkpoint). This produces a roughly 90% bandwidth savings in Electrum-NMC for block heights that are covered by a checkpoint. The degree to which this actually matters is somewhat debatable, since it's not totally obvious that Electrum-NMC can't be modified to achieve sufficiently small bandwidth usage without this trick. (Note that ElectrumX protocol version 1.4.1 added this feature, and 1.4.1 isn't yet added to Electrum-NMC master branch because I haven't yet gotten confirmation that the public servers have upgraded, so using this feature requires applying an extra PR to Electrum-NMC and selecting a known-upgraded ElectrumX server.)

In practice I tend to think that the benefit of (2) outweighs the drawback of (1), at least until a more scalable AuxPoW spec such as the one by Luke Dashjr is deployed. (Luke's spec has much smaller AuxPoW headers and also uses a single timestamp across all chains, so it's clearly a winner in this department, but it also requires Bitcoin to hardfork, so the political implications of that make it unlikely to happen soon. But I hope it eventually happens.)

[globaltoken]

@domob1812 As we see in the bitcoin blockchain, people are doing lot of crazy stuff.
Do you remember about the DOS-Virus header in one block?

I thought about a new NetMsgType, where we have an extra "auxpow.dat" file, that will hash all auxdata and makes a chain of it. So in this case, you know what auxpow data was first in the block, and which is manipulated.

As described, this is not a big problem, but a blockchain should be forgery safe or?

[JeremyRand]

I thought about a new NetMsgType, where we have an extra "auxpow.dat" file, that will hash all auxdata and makes a chain of it. So in this case, you know what auxpow data was first in the block, and which is manipulated.

@globaltoken How would this chain be authenticated? By a DMMS? If so, how? If not, what is it useful for? (Remember that the P2P network is trivially easy to Sybil and that most nodes are not online 24/7 and that new nodes come online all the time.)

[JeremyRand]

Also why exactly are we supposed to care if someone embeds a malware sample in an AuxPoW coinbase transaction...?

[JeremyRand]

As an aside, it would be possible to softfork Namecoin to impose a limit on the distance between the sidechain timestamps and the parent timestamps. This would greatly increase the cost of forging AuxPoW headers. It's not clear to me exactly what the claimed benefit would be though, seeing as the forensic analysis use case I described wouldn't matter AFAICT.

[JeremyRand]

To elaborate on my point, it's not really feasible to stop miners from forward-dating timestamps in a reorg attack, since the timestamp enforcement in Bitcoin and Namecoin only requires that the median timestamp not decrease. If we required parent and sidechain timestamps to be near each other, then someone doing a reorg attack on the sidechain would just forward-date the sidechain blocks they're mining so that they matched the parent chain, and the attack would still work fine. Which is exactly what they'd do anyway since it's cheaper due to not losing the parent block reward. If someone wanted to confuse forensic analysis after the fact, they might want to backdate parent blocks in a re-org, but that's already highly expensive regardless of the existence of that softfork.

[globaltoken]

It's not about a malware in the Coinbase transaction. That was just an example.
Let's say 3 nodes manipulate one block, lets say height 100 000.
Height 100 000 has now 3 different auxpow data.

If this nodes will be online and have a listen function, they can distribute the blocks to freshly syncing nodes.

If 3 different blocks were distributed at height 100 000 a lot of users have different auxpow at block height 100 000. How can we be sure, which is the correct one? There is no consens in the blockchain, since all nodes will have then different auxpow.

This will not affect any blocks, but having for example 3000 nodes online and 1000 of them have auxpow A, 100 000 have auxpow B, and 100 000 have auxpow C.

In theory like you said, you can write some stuff into the coinbase.
I heard last year about child porns in the blockchain, even if this are just links to related sites.
Whatever you like can now be part of the blockchain, since you can edit the auxpow blocks, if you have enough proof of work. And I think the beginning of auxpow will have not a high diff like it is now.
So you can generate a fake auxpow with ease, and leave your data in the auxpow block.

My idea was, like the normal blockchain, a second sidechain database.
For example:

To add one entry to the database, we will hash the height of this block and the auxpow data of this block.
Now we add the height and the hash of auxpow into the database.

The database will follow a own chain.
Maybe we can do it like Block Checkpoints? Introduce the first auxpow block that has ever been mined, and the database will start with this data.

SHA256(height, auxpowhash, size, previous auxpow hash)
To verify the database now its easy:

Before we sync the blocks, we will sync the sidechain auxpow.dat.
With this, we have already the known and valid auxpow.

Now while syncing, in CheckBlockHeader we can add the auxpow validation, that will check, if the synchronized data of auxpow matchs the expected from auxpow.dat

So there is no chance later to fake the auxdata.

[globaltoken]

@JeremyRand I think we talk about 2 different attacks. You are talking about a security related attack, I talk about a data manipulation attack in auxpow, that has no security consequences, but it could be a problem for the blockchain if this data is found in the blockchain.

Maybe you should get me an external link about your described timestamp attack, because I can't imagine exactly how it should work.
Similar like an 51% attack, with the difference, using valid high proof of work data from the auxpow parent blocks?

[JeremyRand]

Okay, so the attack here is that someone who's mining today wants to replace an AuxPoW header from the distant past which has much lower difficulty, and therefore is trivially easy to mine with modern mining equipment (to the point that the attacker doesn't mind burning some small amount of parent chain hashrate to do it)? Okay, so I guess someone could do this. What do they replace the AuxPoW header with? I suppose they could embed Hidden Wiki text like someone did with Bitcoin, but what does that achieve? Last I checked no one is being held liable for storing the Bitcoin chain despite that text being there. In fact, I'd suggest that there's a more straightforward "white hat attack" that can be done here: just mine a bunch of AuxPoW headers with empty coinbase transactions, and specifically replace the AuxPoW headers that have massive coinbase transactions (I seem to recall Eligius is well-known for having large coinbases). This would basically be a way to expend PoW to compress the Namecoin blockchain retroactively.

Anyway, I don't see how your proposed solution actually authenticates the AuxPoW data. Sure, you can have a checkpoint commitment to all the AuxPoW below a certain height, but authenticating that the checkpoint is correct isn't actually feasible -- blockchain checkpoints work because you can independently verify the correctness of all the blocks they commit to, and you can independently verify that no one has presented a longer chain than the chain they commit to, so it's trivially easy for anyone who wants to audit a checkpoint to do so. Your system doesn't have any way to audit the checkpoints because they are not authenticated by a DMMS. Saying "use a database" is nonsensical -- a database isn't used to authenticate anything in Bitcoin, it's just a storage mechanism for fast lookups of data that's already been authenticated. Similarly, syncing the AuxPoW from the P2P network (regardless of whether it's before you sync the headers) isn't going to help you authenticate it, because there's no DMMS and the P2P network is trivially easy to Sybil.

If we actually wanted to make the DMMS commit to the AuxPoW data (which I don't think is a bad thing, for the record), I think the "right" way to do it is probably to add an extra hash to the block header, which is committed to by the prev_hash field of the following block header. I'm not sure what the most efficient way to encode it would be. In any event this would be a hardfork (though presumably we could roll it into AAA if there were a consensus that it's a good idea).

[globaltoken]

In my suggested solution, there is a way to check if the checkpoint is valid. In the database, that will be created and managed by the nodes, we have the hardcoded first auxpow block. With this: We get the hash

SHA256(height, auxpowhash, size, previous auxpow hash)

Lets assue SHA256(100000, SHA256(auxpow), auxpowserializedsize, NULLHASH), lets assume the hash of this first "auxpow genesis" block is now
9D470C30FEADC659CBF63EBD2F2533EE11B4F972CEAAE3E14259FC089185315E .

Then the nodes will save in the database height 100000, and the hash 9D470C30FEADC659CBF63EBD2F2533EE11B4F972CEAAE3E14259FC089185315E

Now lets say height 100002 is auxpow again, the next entry is:
SHA256(100002, SHA256(auxpow), auxpowserializedsize, 9D470C30FEADC659CBF63EBD2F2533EE11B4F972CEAAE3E14259FC089185315E).
Now the next hash is: 7CC408FB3482A3479BB212959C3D70036E5C2CDB7F336CE7F6A9370A71AC826F

The database will save now 100002, 7CC408FB3482A3479BB212959C3D70036E5C2CDB7F336CE7F6A9370A71AC826F

and this is going on and on ...

If you start the node, it gets the current auxpow db like above through the new implemented netmsgtype. Then it starts syncing. Lets guess auxpow started at block 100,000 and now the node gets from the syncing nodes the block header.

It checks if this is a auxpow block (nVersion & 256), if so search this height in the auxpow.dat
(At this point I noticed right now, that the height is not part of the CBlock. Lets take the full blockhash instead of height like above).
So it reads the auxpow database for hash = hash of height 100,000 and it gets the auxpow expected hash: 9D470C30FEADC659CBF63EBD2F2533EE11B4F972CEAAE3E14259FC089185315E.
Now you can hash the auxpow data that we received through the network:

SHA256(SHA256(block 100000), SHA256(this->auxpow), auxpowserializedsize, (prevauxpowhash, in this case null, because this is the auxpow activation height)). Now we get while validating the block manually the same hash = 9D470C30FEADC659CBF63EBD2F2533EE11B4F972CEAAE3E14259FC089185315E.

This auxpow matchs the expected hash from the db, we will sync it, it's valid.

And while syncing you can also sync from a node, that is on another fork, and use a forked chain.
So, if we sycned the auxpow.dat from network, we could request a second netmsgtype "auxcmp", this will send our last blockhash in the db, and the last auxpow hash through the connected nodes. They will send their hashes back, and if we see that > 90% of the responded nodes has the same hash, then it should be valid.

[JeremyRand]

First off, that's not how checkpoints work. Checkpoints don't commit to the first block in a chain, they commit to the set of all blocks below a given height. Committing to the first block doesn't give you any way to verify that later blocks are correct.

Also I've mentioned Sybil attacks several times in this thread and it doesn't appear that you understand what they are or how easy they are to perform.

[globaltoken]

Well, you can define hardcoded checkpoints for the auxpow.dat as well in the chainparams.
It's not different from the block DB.

But I was thinking more to add this in GLT first, because Masternodes are more trusted then all other normal nodes. So a sybil attack at GLT is probably not the case.

I just wanted to let you know about this issue. However, if you think it's safe how it is, leave it.
It is just an discussion thread here about it.

Feel free to leave solutions instead focussing on the problems.

[JeremyRand]

I just wanted to let you know about this issue.

And we thank you for that.

However, if you think it's safe how it is, leave it.

I don't recall us ever making a claim that we were certain this was the case, we were asking what attack scenario you were describing and trying to analyze the costs/benefits of the various potential fixes. This analysis is made much harder by:

Feel free to leave solutions instead focussing on the problems.

Said every shitcoin developer ever who doesn't want to find out their solutions are broken until they're deployed on mainnet and someone decides to actually do an attack....

If you're the kind of developer who gets offended when people poke holes in proposals, you might want to re-evaluate being in the crypto space. No one is in any way obligated to provide a different proposal just because they criticized someone else's proposal. That's simply not how this space works.

(Also I'm not sure why you're telling me to provide a solution when you haven't commented on the one I already provided 2 posts ago.)

[globaltoken]

I think all other proposals are not possible with a softfork.
The database / checkpoint proposal is similar to the Block Checkpoint solution.

Otherwise I like your idea with hashing the auxpow hash into the Blockheader, but the auxpow is serialized after the block. So the block hash will change.

I am not sure, but I think the auxpow block must include the blockhash or block height of the block or?

[JeremyRand]

Otherwise I like your idea with hashing the auxpow hash into the Blockheader, but the auxpow is serialized after the block. So the block hash will change.

The AuxPoW needs to commit to the block hash, and a block needs to commit to the previous block hash, but there's no fundamental requirement that those two commitments be identical. I'm suggesting that a block can commit to the previous block's AuxPoW as part of the data hashed to yield the prev_hash field. Technically this would allow an AuxPoW to be replaced before the next block is mined, but I'm under the impression this isn't a significant threat. Am I missing something that would prevent this from working?

It should be noted that this design would require checkpoint-using clients that don't currently process AuxPoW to download an extra 32 bytes per block (unless there's some way to compress it that I'm not seeing [1]). I'm not yet sure how big of a problem that is.

[1] I suppose maybe the commitment to the previous block's AuxPoW could be stuffed into the transaction Merkle tree in some way, but I haven't thought about this very carefully and maybe there are other drawbacks to that approach.

[JeremyRand]

As an aside, I tend to think there are other spam vectors besides this that are more important to close for Namecoin, some of which (e.g. decreasing the block weight limit) are already being worked on. That doesn't in any way imply that there's anything wrong with discussing this vector and potential fixes, just that I'd expect this vector to get a less prompt fix.

[Satoshi0x]

@domob1812 can you please transfer this issue to the Namecoin repo rather than your personal repo, so that we have proper transparency about threat model discussions? (Not sure why it was reported here.)

Because there's so much to learn about this project's other leader across the pond. The two of you have very different work, but like a Parent in Merge Mining, who is to say the chain from the project's "namecoin" repositories are the "best and official" master upstream chain. Git is a block chain. GitHub has properties like hashes and parent sometimes more than one to commits. Sometimes even find commits in a repository that is not part of it anymore if you click enough of those hashes. Poor orphans. :)