foundationdb icon indicating copy to clipboard operation
foundationdb copied to clipboard

Automatic idempotency ids have insufficient entropy

Open atn34 opened this issue 1 year ago • 0 comments

The automatically generated ids are 128-bit, but the PRNG's seed is only 32-bits. If clients only commit one transaction per process/network thread, then each transaction's id should be fully determined by the 32-bit seed. According to the birthday problem we only need about 82137 transactions in the unexpired window of idempotency ids until we expect to see a collision.

I haven't tried to reproduce this yet, but I expect an effective mitigation to be setting the hidden idempotency_id option with sufficient entropy prior to setting the automatic_idempotency option.

There may be other places we can run into UID collisions because of 32-bit seeds. I don't know if using 128-bit seeds is sufficient to mitigate all this, but it would definitely be better.

atn34 avatar Jun 09 '24 06:06 atn34