Probabilidad remota

Como últimamente me estoy aficionando ligeramente a la estadística (quién me lo iba a decir...), quería destacar unos párrafos que me han encantado del libro Pro Git.

Para aquellos que no conozcáis Git, este es un sistema de control de versiones distribuído, lo que ofrece algunas ventajas sobre otros sistemas centralizados como Subversion ó SourceSafe (del que ya hablé tiempo atrás).

Una peculiaridad de Git es que no designa cada versión (cada snapshot o foto del código) con un número incremental, sino que utiliza una firma generada con función hash de 160 bits, en concreto SHA-1. Una función hash toma una determinada entrada y genera una salida de una longitud determinada (en este caso 160 bits, es decir, un número entre 0 y 2^160 - 1). Idealmente, una buena función hash tiene varias propiedades, entre las que se incluyen:

• Una mínima varianza en la entrada de la función genera cambios grandes en la salida de la función.
• Es muy complicado (por no decir prácticamente imposible) encontrar dos entradas que generen la misma salida (lo que se denomina una colisión).

Y de esta cuestión, la probabilidad de colisión, viene el párrafo que me ha gustado. Ante la preocupación de qué ocurriría si en Git dos versiones distintas generaran la misma firma. El texto original es este:

A lot of people become concerned at some point that they will, by random happenstance, have two objects in their repository that hash to the same SHA-1 value. What then?

(...)

However, you should be aware of how ridiculously unlikely this scenario is. The SHA-1 digest is 20 bytes or 160 bits. The number of randomly hashed objects needed to ensure a 50% probability of a single collision is about 2^80 (the formula for determining collision probability is p = (n(n-1)/2) * (1/2^160)). 2^80 is 1.2 x 10^24 or 1 million billion billion. That’s 1,200 times the number of grains of sand on the earth.

Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (1 million Git objects) and pushing it into one enormous Git repository, it would take 5 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

y la traducción vendría a ser algo como:

A mucha gente le preocupa que en algún momento tengan, por casualidad, dos objetos en su repositorio cuya firma (hash) sea el mismo valor SHA-1. ¿Qué ocurre entonces?

(...)

Sin embargo, deberías tener constancia de lo ridículamente improbable es este escenario. La firma SHA-1 es de 20 bytes de longitud, ó 160 bits. El número de firmas de objetos generadas aleatoriamente que son necesarias para asegurar una probabilidad del 50% de una única colisión es aldededor de 2^80 (la fórmula para determinar la probabilidad de colisión es p = (n(n-1)/2) * (1/2^160)). 2^80 es 1,2 x 10^24 o 1 million de billones de billones (en formato americano, donde 1 billón es 1.000.000.000). Eso es 1.200 veces el número de granos de arena en La Tierra.

Aquí va un ejemplo para darte una idea de qué tomaría conseguir una colisión SHA-1. Si los 6,5 billones de humanos (billones americanos, serían 6.500 millones) estuvieran programando y, cada segundo, cada uno produjera el código equivalente a la historia completa del kernel Linux (1 millón de objetos Git) y enviándolos a un enorme repositorio Git, pasarían 5 años hasta que ese repositorio contuviera suficientes objetos como para tener un 50% de probabilidad de una única colisión de un objeto SHA-1. Existe una mayor probabilidad de que cada miembro de tu equipo de programación sea atacado y asesinado por lobos en incidentes sin relación durante la misma noche.

Conozco gente tan gafe que estoy casi convencido que cuando comencemos a utilizar Git en nuestro trabajo generará una colisión, pero en general me parece una probabilidad razonable.