¿Aceptable confiar en que las entradas aleatorias sean únicas?

He estado implementando un protocolo de red y requiero que los paquetes tengan identificadores únicos. Hasta ahora, he estado generando enteros aleatorios de 32 bits, y suponiendo que es astronómicamente improbable que haya una colisión durante la vida útil de un programa / conexión. ¿Se considera esto generalmente una práctica aceptable en el código de producción, o se debería idear un sistema más complejo para evitar colisiones?

Cuidado con la paradoja del cumpleaños .

Suponga que está generando una secuencia de valores aleatorios (uniformemente, independientemente) a partir de un conjunto de tamaño N (N = 2 ^ 32 en su caso).

Luego, la regla general para la paradoja del cumpleaños establece que una vez que haya generado aproximadamente valores de sqrt (N), hay al menos un 50% de posibilidades de que se haya producido una colisión, es decir, que haya al menos dos valores idénticos en el secuencia generada

Para N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Entonces, después de haber generado unos 65k identificadores, ¡es más probable que dos de ellos choquen! Si genera un identificador por segundo, esto sucedería en menos de un día; No hace falta decir que muchos protocolos de red funcionan mucho más rápido que eso.

En general, se considera aceptable confiar en que los números aleatorios sean únicos si esos números tienen suficientes bits. Hay protocolos criptográficos donde la repetición de un número aleatorio romperá toda la seguridad. Y siempre que no haya vulnerabilidades graves en el generador de números aleatorios que se está utilizando, eso no ha sido un problema.

Uno de los algoritmos para generar UUID generará efectivamente una ID que consta de 122 bits aleatorios y supondrá que será único. Y dos de los otros algoritmos se basan en un valor hash truncado a 122 bits que es único, lo que tiene aproximadamente el mismo riesgo de colisiones.

Por lo tanto, hay estándares que dependen de que 122 bits sean suficientes para hacer que una identificación aleatoria sea única, pero 32 bits definitivamente no es suficiente. Con ID de 32 bits, solo se necesitan aproximadamente 2¹⁶ ID antes de que el riesgo de colisión alcance el 50% porque con 2¹⁶ ID habrá cerca de 2³¹ pares, cada uno de los cuales podría ser una colisión.

Incluso 122 bits es menos de lo que recomendaría en cualquier diseño nuevo. Si seguir alguna estandarización es importante para usted, use UUID. De lo contrario, use algo más grande que 122 bits.

La función hash SHA1 con una salida de 160 bits ya no se considera segura, lo que se debe en parte a que 160 bits no es suficiente para garantizar la unicidad de las salidas. Las funciones hash modernas tienen salidas de 224 a 512 bits. Las ID generadas aleatoriamente deben apuntar a los mismos tamaños para garantizar la unicidad con un buen margen de seguridad.

Yo llamaría a esto una mala práctica. El número aleatorio genera simplemente no crea números únicos, solo crea números aleatorios. Es probable que una distribución aleatoria incluya algunos duplicados. Puede hacer que esta circunstancia sea aceptablemente improbable agregando un elemento de tiempo. Si obtiene la hora actual del reloj del sistema en milisegundos. Algo como esto:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Recorreremos un largo camino. Obviamente, para garantizar realmente la unicidad, necesita usar UUID / GUID. Pero pueden ser costosos de generar, lo anterior es probablemente suficiente, ya que la única posibilidad de superposición es si la generación aleatoria tuvo un duplicado en el mismo milisegundo.

Depende tanto de la probabilidad de falla como de las consecuencias de la falla.

Recuerdo un debate entre personas de software y hardware donde las personas de hardware consideraron que un algoritmo con una pequeña probabilidad de resultados incorrectos (algo así como 1 falla en 100 años) era aceptable, y las personas de software pensaron que esto era un anatema. Resultó que la gente del hardware calculaba rutinariamente las tasas de falla esperadas, y estaban muy acostumbrados a la idea de que todo daría respuestas incorrectas ocasionalmente, por ejemplo, debido a las perturbaciones causadas por los rayos cósmicos; les pareció extraño que la gente de software esperara una fiabilidad del 100%.

Claro, tienes probabilidades bastante bajas de que dos enteros aleatorios de 32 bits sean secuenciales, pero no es completamente imposible. La decisión de ingeniería apropiada se basa en cuáles serían las consecuencias de las colisiones, una estimación del volumen de números que está generando, la vida útil durante la cual se requiere unicidad y qué sucede si un usuario malintencionado comienza a intentar causar colisiones.

Puede ser aceptable suponer que los números aleatorios serán únicos, pero hay que tener cuidado.

Suponiendo que sus números aleatorios están distribuidos equitativamente, la probabilidad de una colisión es aproximadamente (n ^2/2 ) / k donde n es el número de números aleatorios que genera yk es el número de valores posibles que puede tomar un número "aleatorio".

No pone un número en astronómicamente improbable, así que tomemos como 1 en 2 ³⁰ (aproximadamente en mil millones). Digamos además que genera 2 ³⁰ paquetes (si cada paquete representa aproximadamente un kilobyte de datos, esto significa aproximadamente un terabyte de datos totales, grandes pero no inimaginablemente). Encontramos que necesitamos un número aleatorio con al menos 2 ⁸⁹ valores posibles.

En primer lugar, tus números aleatorios deben ser lo suficientemente grandes. Un número aleatorio de 32 bits puede tener como máximo 2 ³² valores posibles. Para un servidor ocupado que no está lo suficientemente cerca.

En segundo lugar, su generador de números aleatorios debe tener un estado interno suficientemente grande. Si su generador de números aleatorios solo tiene un estado interno de 32 bits, no importa cuán grande sea el valor que genere, solo obtendrá como máximo 2 ³² valores posibles.

En tercer lugar, si necesita que los números aleatorios sean únicos en todas las conexiones en lugar de solo dentro de una conexión, su generador de números aleatorios debe estar bien sembrado. Esto es especialmente cierto si su programa se reinicia con frecuencia.

En general, los generadores de números aleatorios "regulares" en lenguajes de programación no son adecuados para tal uso. Los generadores de números aleatorios proporcionados por las bibliotecas de criptografía generalmente son.

En algunas de las respuestas anteriores se asume que el generador de números aleatorios es realmente 'plano', que la probabilidad de que dos números sean el próximo generado es la misma.

Eso probablemente no sea cierto para la mayoría de los generadores de números aleatorios. La mayoría de los cuales utilizan algún polinomio de alto orden aplicado repetidamente a una semilla.

Dicho esto, hay muchos sistemas que dependen de este esquema, generalmente con UUID. Por ejemplo, cada objeto y activo en Second Life tiene un UUID de 128 bits, generado aleatoriamente, y rara vez chocan.

Mucha gente ya ha dado respuestas de alta calidad, pero me gustaría agregar algunos puntos menores: primero, el punto de @nomadictype sobre la paradoja del cumpleaños es excelente .

Otro punto: la aleatoriedad no es tan sencilla de generar y definir como la gente podría suponer. (De hecho, en realidad hay pruebas estadísticas de aleatoriedad disponibles).

Dicho esto, es importante tener en cuenta la Falacia del jugador , que es una falacia estadística en la que las personas suponen que los eventos independientes de alguna manera se influyen entre sí. Los eventos aleatorios generalmente son estadísticamente independientes entre sí, es decir, si genera aleatoriamente un "10", no cambia su probabilidad futura de generar más "10" en lo más mínimo. (Tal vez alguien podría presentar una excepción a esa regla, pero esperaría que ese fuera el caso para casi todos los generadores de números aleatorios).

Entonces, mi respuesta es que si pudieras asumir que una secuencia suficientemente larga de números aleatorios es única, en realidad no serían números aleatorios porque sería un patrón estadístico claro. Además, implicaría que cada nuevo número no es un evento independiente porque si genera, por ejemplo, un 10, eso significaría que la probabilidad de generar futuros 10 sería del 0% (posiblemente no podría suceder), más eso significaría que aumentaría las probabilidades de obtener un número distinto de 10 (es decir, cuantos más números genere, mayor será la probabilidad de que cada uno de los números restantes se vuelva).

Una cosa más a considerar: la posibilidad de ganar el Powerball de jugar un solo juego es, según tengo entendido, aproximadamente 1 en 175 millones. Sin embargo, las probabilidades de que alguien gane son considerablemente más altas que eso. Está más interesado en las probabilidades de que alguien "gane" (es decir, que sea un duplicado) que en las probabilidades de que un número particular "gane" / sea un duplicado.

No importa cuántos bits use; NO PUEDE garantizar que dos números "aleatorios" sean diferentes. En cambio, sugiero que use algo como la dirección IP u otra dirección de red de la computadora y un número secuencial, preferiblemente un número secuencial HONKIN 'BIG: 128 bits (obviamente sin signo) suena como un buen comienzo, pero 256 sería mejor.

No claro que no. A menos que el rng esté usando muestras sin reemplazo, existe la posibilidad, por pequeña que sea, de duplicación.