Factorio Forums

In 0.15.28, on Windows (64-bit), the following two blueprints can't be added to the blueprint library at the same time:
Here's what it looks like if you try: https://www.youtube.com/watch?v=vs3uEIIrllw

perhaps they have the same CRC info as discussed here.

In fact they do

That didn't take long for someone to find a collision!

As useless as the first BP is, it seems as if it was intentionally created for this exact purpose.

Loewchen wrote:As useless as the first BP is, it seems as if it was intentionally created for this exact purpose.

It was https://www.reddit.com/r/factorio/comme ... _same_crc/

ok how bout this for a challenge. show us two blueprints someone would actually use.

impetus maximus wrote:ok how bout this for a challenge. show us two blueprints someone would actually use.

By what metric? There is somebody who would use _every_ valid blueprint, even if only for decoration or a compendium of every single possible blueprint.

---

That said, just matching a CRC to detect duplicate blueprints isn't enough, especially since there isn't a huge amount of entropy present in CRC. Aside from possibly moving to a cryptographic hash, my suggestion (which should probably be implemented either way, as a "just in case" percaution) is to, if the CRCs (other hashes are available) match, run an O(n) comparison on the data. In theory, this wouldn't need to be done too frequently, but if there is some facet I'm missing let me know.

TruePikachu wrote:

impetus maximus wrote:ok how bout this for a challenge. show us two blueprints someone would actually use.

By what metric? There is somebody who would use _every_ valid blueprint, even if only for decoration or a compendium of every single possible blueprint.

---

That said, just matching a CRC to detect duplicate blueprints isn't enough, especially since there isn't a huge amount of entropy present in CRC. Aside from possibly moving to a cryptographic hash, my suggestion (which should probably be implemented either way, as a "just in case" percaution) is to, if the CRCs (other hashes are available) match, run an O(n) comparison on the data. In theory, this wouldn't need to be done too frequently, but if there is some facet I'm missing let me know.

I'm not sure how CRCs work, but would it be possible to simply add a salt to the data then recheck CRC if a collision is detected? If the two data are identical, then the salted data would also produce identical CRCs, but would the salt change the CRC if the original data were different?

adeade45 wrote:

TruePikachu wrote:

impetus maximus wrote:ok how bout this for a challenge. show us two blueprints someone would actually use.

By what metric? There is somebody who would use _every_ valid blueprint, even if only for decoration or a compendium of every single possible blueprint.

---

That said, just matching a CRC to detect duplicate blueprints isn't enough, especially since there isn't a huge amount of entropy present in CRC. Aside from possibly moving to a cryptographic hash, my suggestion (which should probably be implemented either way, as a "just in case" percaution) is to, if the CRCs (other hashes are available) match, run an O(n) comparison on the data. In theory, this wouldn't need to be done too frequently, but if there is some facet I'm missing let me know.

I'm not sure how CRCs work, but would it be possible to simply add a salt to the data then recheck CRC if a collision is detected? If the two data are identical, then the salted data would also produce identical CRCs, but would the salt change the CRC if the original data were different?

You could, but it's the same amount of work as (or more work than), and less secure, than running a stronger cryoptographic hash, which is the original suggestion. (There is some good discussion on WHAT hash to use in viewtopic.php?f=38&t=50663&start=80 )

Whats the problem about making a full comparison of the blueprint if the CRC is identical?

Patashu wrote:You could, but it's the same amount of work as (or more work than), and less secure, than running a stronger cryoptographic hash, which is the original suggestion. (There is some good discussion on WHAT hash to use in viewtopic.php?f=38&t=50663&start=80 )

Strictly speaking, a strong hash will frequently be slower than CRC.

Nexarius wrote:Whats the problem about making a full comparison of the blueprint if the CRC is identical?

The main possible "issue" is that you get a O(n) byte-by-byte comparison, in contrast to the O(1) CRC checking.

Theoretically, however, this shouldn't be much of a problem. The only times that blueprints need to be checked for duplication are when they are being added to the library manually, and the only time the O(n) comparison is needed is if the O(1) comparison matches. This would usually only happen in the case that the blueprints are identical (which results in the maximum runtime from O(n) comparison), but it can happen in the example given here (which would result in less than maximum runtime).

It might be possible to optimize the O(n) comparison quite a bit, though, by first comparing the fields most likely to differ (and length). However, in the case of actual duplicates, it is impossible to get better than O(n) time.

TruePikachu wrote:

Patashu wrote:You could, but it's the same amount of work as (or more work than), and less secure, than running a stronger cryoptographic hash, which is the original suggestion. (There is some good discussion on WHAT hash to use in viewtopic.php?f=38&t=50663&start=80 )

Strictly speaking, a strong hash will frequently be slower than CRC.

Yeah, but it doesn't matter if it's a bit slower, since making a new blueprint happens once per minute or slower, compare that to the UPS savings of making something like belts or inserters run faster (which happens 10000s of times per second)

Fixed in 0.15.29.