Soundness for bus interaction id

[qwang98]

          So if my math is right, 16 bit means that after 100 samples, we have a ~7% chance of a collision, which would break soundness. 100 machine pairs does not seem so far fetched, especially with auto pre-compiles. Would it be much harder to ensure uniqueness? If yes, we could at least go to 24 or 30 bits, no? That would reduce the chance a lot.

(The chance of a collision after x samples should be 1 - math.prod(2**16 - i for i in range(x)) / 2**(16*x).)

Originally posted by @georgwiese in #2446 (comment)

[qwang98]

Not sure if we are still concerned by this @Schaeff.

Currently, we pass the 16 bit interaction id to finger print with the payloads. Depending on which field extension is used, if in the case of BB, the interaction id gets converted from an expression to a field extension (an array of expressions) by padding zeros. For example, interaction id 123 becomes Fp4(123, 0, 0, 0).

Therefore, in practice, at least at the level after PIL function is called, bus interaction id field extension can always hold 64 bits in 1, 2, or 4 columns (depending on the field extension). If we want to map the hashed interaction id to 2^64 instead of 2^16, this in theory shouldn't create any additional witness columns.

However, a key challenge remains in how to pass a 64 bit number to an array of columns in PIL when the count of columns isn't known. Besides, all our current APIs treat interaction ID as a single column, so would need to change up things a lot.

[Schaeff]

Yes good point, to be honest the hash idea was mostly to simplify implementation, so that we don't need to store a map of each operation to their id. It was introduced in the context of a PR which was already quite large.

So I suspect either we could

• increase the number of bits to 24 or 30 bits as suggested by @georgwiese
• move back to the original idea and precompute a map of IDs starting from 1 etc

[leonardoalt]

Was this done in #2474?