[Dev]: Deterministic tournament operations

[TylerBloom]

Unmet Need:

The Squire model for communication between clients and the backend requires that tournament operations be entirely deterministic. While there has been a good deal of effort put into ensuring this, we are still operating under several assumptions. These assumptions need to be tested.

Id Generation

One of the biggest sources of non-determinism is UUID generation. Currently, there are two methods in squire_lib/src/identifiers.rs that are used throughout the project to generate IDs. This ensures a uniform process for generating IDs. These methods take some salt (a timestamp) and some hashable data. The timestamp is hashed and is used to create the top 64 bits of the ID, and the other data is hashed and forms the lower 64 bits. The timestamps are passed as arguments from the tournament's apply_op method, which is passed from the SquireSDK's TournamentManager, so this salt is the same for all clients as it is shared as part of the tournament syncing process defined in the SDK.

However, hashing functions will not necessarily generate the same output on all platforms. This will cause the lower bits to potentially differ. To account and test for this, a suite of timestamp-data pairs should be generated (and stored statically) as well as the resulting UUID. These will form regression tests. Tests need to be added that will compute the UUID from the data and ensure the resulting UUID equals the known ID. These tests will run in CI, which will ensure platform independence. If the current method of ID creation fails this test, we need to look for a platform-independent hasher. Something like this hasher.

[zbrachinara]

One issue which might cause non-determinism with hashing -- I can't find any evidence that #[derive(Hash)] hashes the fields of a struct in any particular order. This might be kind of overkill, but we may need to manually impl Hash for the types that we want to convert to UUID, or, even better, make a trait (for example, IntoId) which has a separate derive macro that guarantees the hash order to be the same as the field declaration order (or some other order)

[TylerBloom]

These are good points, but I feel that they are overkill. Not because that could be a problem in general but because of the types that are being hashed. We are mostly hashing string slices and other UUIDs. Both of these are effectively fields of bits, so there isn't too much concern there.

This could be a problem for the timestamp. I don't know how chrono stores timestamps internally. We might consider converting that timestamp into something that we believe won't change its hash (like a string) implementation. But again, I feel like this is unlikely.

Lastly, I would like to point out that these tests are warning flags. If what you describe does happen, we can freeze our toolchain and perform some kind of migration of the data.

[TylerBloom]

I did a bit more digging on this, and this generally seems to be a non-issue. String slices are hashed by a method in the Hasher trait, which str calls in its Hash implementation. Technically, there is a chance that the hasher that is used changes its implementation of hash_str; however, we have discussed using a hasher like AHash. If that occurs, we can freeze the dependency.

UUIDs are also not problematic. UUIDs are just [u8; 16], and, according to the docs in the uuid crate, the ABI for a Uuid will always be the same as an array of bytes. So, we only need be to concerned with how those bytes are hashed, but this has the same solution as the string slice case.

I noticed that we are using the id_from_item method in the SDK to generate IDs for operations. That use case can be ignored as they don't need to be deterministic (and should probably be ULIDs instead).

[zbrachinara]

Hashing determinism is currently being worked on in #102