Proposal: Reduce size of block hashing blobs for PoW validation about monero HOT 10 CLOSED

we can actually reduce the intermediate hash size down from 32 bytes to ~5 bytes

Sounds unrealistic to me, since the hash algorithms' block size is 32 bytes.

from monero.

The hash algorithm would remain unmodified, we would simply only include X bytes of the RandomX hash result in the header hashing blob, where X is the amount of bytes needed to bind the block contents with at least as much as the current difficulty of the block.

In other words, we are downgrading the strength of the bind from industry-standard 128-bit security level to the strength of the block difficulty.

from monero.

I think @hyc was pointing out that with a block of 32-bytes, there isn't going to be much performance improvement in this suggestion.

from monero.

Yes, there would be 0 CPU performance improvement, but if we only save enough bytes from the intermediate hash to bind the contents of the block stronger than its difficulty (~4-5 bytes as of the time of this writing), then we get to save 27 or 28 bytes per header hashing blob while still retaining spam proofness.

from monero.

Sorry, I guess I jumped ahead a bit since it wouldn't create the same hashes as the current RandomX proposal, it would require a Blake2B hash of this reduced hash, replacing the extra step where we hash the hash of the dataset, but the original proposal also required a hard fork, so this requirement shouldn't be a big deal IMO.

from monero.

Proposals like this make me very uneasy in terms of cost benefit: The history of secure hash algorithms demonstrates fairly conclusively that you want a wide safety margin because things can and do often go wrong. Tevador's original proposal expands the safety margin so I don't really see a case for thinking of the two ideas as a single unit; in particular, there's no need to offset the extra header bytes in tevador's proposal (the proposal should stand on its own, and I didn't see much objection to the extra bytes). Linking the proposals creates a lot of downside: What if one has to be undone? I'd rather not condition "reduce DoS vulnerability" on "slightly reduce network traffic".

from monero.

The history of secure hash algorithms demonstrates fairly conclusively that you want a wide safety margin because things can and do often go wrong

I would tend to agree, except that this problem isn't related to secure hash algorithms in a traditional sense, it's related to PoW. We don't need collision resistance within a security factor so large that no computer we can conceive of could reasonably find one (i.e. the current 128-bit industry standard level), we only need difficulty that is greater than the block difficulty, which should be trivially provable under the current assumptions we use for PoW consensus rules.

Tevador's original proposal expands the safety margin

Wrong. It has 0 effect on the "safety margin". If you're talking about resistance to 51% attacks, if the 256-bit intermediate hash would cause any extra difficulty to attackers (i.e. finding a collision with the intermediate hash is harder than remining the RandomX PoW, which it should be), then the attacker would simply just remine the RandomX PoW, since that's easier. In that case, we have exactly the same difficulty to perform 51% attacks as before the changes. What @tevador's proposal protects against is forcing any node on the network to run iterations of RandomX at no cost to the remote attacker.

Now you could have a point that we could multiply the current difficulty by a buffer amount, just to be extra sure our rough intermediate hash has a higher difficulty to fake than the current difficulty of the block. For example, instead of rough_diff_bytes = log256ceil(current_difficulty), we could have rough_diff_bytes = log256ceil(2^7 * current_difficulty).

from monero.

The history of secure hash algorithms demonstrates fairly conclusively that you want a wide safety margin because things can and do often go wrong

I would tend to agree, except that this problem isn't related to secure hash algorithms in a traditional sense, it's related to PoW

Except the problem here does relate to certain properties of hash algorithms (specifically, bit independence, pre-image resistance), which have been difficult to conclusively analyze in past algorithms. If you think the relevant properties are "trivially provable", then by all means, prove them; your work will no doubt very much be appreciated the next time standards bodies solicit drafts for hashing algorithms.

Wrong. It has 0 effect on the "safety margin".

I obviously was not referring to the safety margin of the hashing algorithm (which tevador's proposal didn't impact, as it didn't touch the algorithm), but the network as a whole.

from monero.

rough_diff_bytes = log256ceil(current_difficulty). Then, we get the rough tx tree hash: rough_tx_tree_hash = randomx(<the tx tree>)[:rough_diff_bytes]

It should be noted that this is insecure.

With a 40-bit rough_tx_tree_hash, finding a collision would only take about 2²⁰ RandomX hashes. That's just 1 second for an attacker with 1 MH/s, which is a medium-size miner (or a small pool).

The attack works as follows: The malicious miner will first find two sets of transactions (both including their coinbase reward) that have the same rough_tx_tree_hash. They then continue mining as usual. Once they find a block, they have effectively found 2 different blocks. They submit block A to one part of the network and block B to another part of the network. This will cause a temporary chain split and a subsequent reorg, which can be used for double-spending. The cost of this attack is negligible because both blocks A and B contain the miner's coinbase reward and the initial collision search only needed 1M hashes.

This vulnerability can be fixed by setting rough_tx_tree_hash = randomx(<the tx tree>)[:2*rough_diff_bytes], doubling the rough hash size from 40 to 80 bits, which makes finding a collision take the same amount of work as mining a block.

However, even with this modification, I would recommend against this change. The main idea of reducing the download size to verify the PoW chain doesn't work because without the ability to verify the block_id, you can't actually verify that the list of hashing blobs forms a valid chain (i.e. the prev_id of the next block is correct). This could be abused to insert a fake block in the chain with the effort equal to mining a block with the difficulty of the block following the block you want to replace. The light node would "verify" the PoW chain and then use the fake prev_id in the replaced block to download a fake block that actually doesn't exist in the chain.

from monero.

Yes everything you said @tevador is correct; we would have to double the size of the buffer to prevent collision attacks. Along with @SChernykh's point that since the hashing blobs overlap for block IDs and PoW, such that prev_id can be implied when sent as a compressed chain, I think this issue should be closed. Thanks everyone for the discussion.

from monero.