Ferramentas para desenvolvedores · Gerador UUID
Quantos bits aleatórios um v4 UUID possui? 122, não 128
· Como funciona
uuid criptografia APIs do navegador
Seis dos 128 bits em um UUID aleatório são corrigidos pelo padrão, deixando 122 para a aleatoriedade. Esta postagem mostra como estimar honestamente as probabilidades de colisão e por que as colisões reais vêm de geradores quebrados, e não da matemática.
A pergunta do arquiteto: algum dia conseguiremos uma duplicata? — de onde vem a preocupação e por que a resposta depende do gerador
O arquiteto pergunta: se gerarmos 10 milhões de UUIDs por dia durante dez anos, algum dia conseguiremos uma duplicata? A resposta honesta é: quase certamente não, se o gerador for criptograficamente seguro; quase certamente sim, se o gerador estiver quebrado. A matemática RFC 9562 é correta: um UUID v4 com 122 bits aleatórios tem probabilidade de colisão de aproximadamente n² / 2 elevado à 123ª potência, onde n é o número de identificadores gerados. Para a maioria dos sistemas reais, esta probabilidade é insignificante. O problema é que esta fórmula assume que cada bit é verdadeiramente aleatório. Se o gerador vazar, se repetir ou tiver sido propagado de forma previsível, a fórmula está errada e as duplicatas tornam-se inevitáveis. O layout 128 bits inclui quatro bits de versão (0100 para v4) e dois bits variantes (10 para RFC 9562), que são fixos e definidos pelo padrão.
Quais são os seis bits falados - os quatro bits de versão e dois bits variantes, e por que eles são definidos em vez de aleatórios
Isso deixa 122 bits para aleatoriedade. A formulação às vezes é chamada de 2 para os bits aleatórios 122, produzindo valores únicos. Usando a aproximação do paradoxo do aniversário, a probabilidade de pelo menos uma colisão entre n valores gerados aleatoriamente é aproximadamente n² / 2 elevado a 123. Para n = 1 milhões, isso é (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36, que é cerca de 10^-25. Para n = 10 bilhões, ainda é cerca de 10^-16. Estes não são “efetivamente zero”; eles são "você nunca observará isso". A aproximação do aniversário fornece uma maneira concreta de calcular o risco: conte os UUIDs que você planeja gerar, eleve esse número ao quadrado, divida por 2 elevado à 123ª potência. Se o gerador for o crypto.getRandomValues do navegador, cada bit será apoiado pela entropia do sistema operacional. Se for uma matemática.
A aproximação do aniversário em termos simples - a probabilidade de pelo menos uma colisão entre n identificadores é aproximadamente n ao quadrado dividido por 2 elevado a 123
Para um UUID produzido por um gerador de estado inadequado ou repetido, o modelo matemático falha porque sua suposição de independência é falsa. Uma semente de teste fixa, um acessório copiado ou um instantâneo de processo pode reproduzir valores mesmo que o texto ainda carregue o nibble version-4. Esses são defeitos de implementação, não evidências de que o cálculo do campo 122 estava errado. Outra fonte mundana é copiar o mesmo identificador literal em vários equipamentos e posteriormente mesclar seus dados. Ao investigar uma duplicata, preserve o gerador, a política de seed, o ciclo de vida do processo e o histórico de importação. Não pule de um valor repetido para uma afirmação de que a saída CSPRNG independente esgotou o espaço UUID.
Exemplo resolvido - inserindo uma taxa de geração declarada e um intervalo de tempo na aproximação, com cada etapa mostrada para que você possa substituir seus próprios números
Bifurcação de processo sem ressincronização de estado aleatório. Um bug onde Math.random foi usado em vez de crypto.getRandomValues. Um acessório de teste que foi feito à mão com o mesmo UUID em várias linhas e foi usado acidentalmente na produção. Uma versão antiga de um UUID biblioteca que tinha uma limitação de intervalo ou bug de estado. Nenhum desses cenários envolve a matemática da aproximação do aniversário; envolvem falhas de implementação ou erros operacionais. Calcule honestamente o risco de colisão para o seu sistema: conte a taxa de UUID geração (por segundo, por dia, por ano), projete-o ao longo do tempo em que o sistema funcionará e insira o total na fórmula de aniversário. Se o seu sistema gerar 100,000 UUIDs por dia durante cinco anos (182 milhões no total), a probabilidade de colisão é (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, o que é insignificante.
De onde realmente vêm as duplicatas - sementes Math.random, máquinas virtuais clonadas, processos bifurcados com estado copiado e copiar e colar em fixtures
Se você gerar 10 milhões por segundo durante um ano (315 trilhão no total), a probabilidade é (3. 15 × 10^14)² / 2^123 ≈ 10^-10, que ainda é extremamente pequeno. Estas estimativas assumem que cada bit é independente e aleatório. O gerador ToolAcre usa crypto.getRandomValues, o que fornece aleatoriedade apoiada por CSPRNG; a operação é a única parte em que você precisa confiar. Nunca confie na probabilidade de colisão como desculpa para ignorar as verificações de autorização adequadas. Um UUID não é uma senha, nem um token de acesso, nem um segredo, mesmo que seja 122 bits aleatórios. A singularidade é o benefício; a imprevisibilidade é uma propriedade separada (e mais importante) que evita adivinhações. A matemática do aniversário lida com a singularidade; ele não aborda a vida útil (deve este UUID expirar?), sigilo (precisa ser hash antes do armazenamento?) ou autorização (possuir este UUID prova alguma coisa sobre o chamador?). O gerador ToolAcre fornece UUIDs apoiados por CSPRNG com 122 bits aleatórios, o que significa que a matemática da exclusividade é mantida e a imprevisibilidade é sólida. Todo o resto – validação do token, expiração, controle de acesso – é de responsabilidade do seu aplicativo. A fórmula de probabilidade assume a independência de cada UUID gerado das gerações anteriores. Se o seu sistema gerar identificadores de uma única instância CSPRNG e cada chamada extrair uma nova aleatoriedade do sistema operacional, a suposição de independência será válida. Se o seu sistema usa um estado CSPRNG em cache ou um gerador propagado sem nova propagação do sistema operacional, a suposição é interrompida. O risco de colisão aumenta drasticamente se a fonte de entropia estiver esgotada (ocorre em alguns sistemas embarcados ou máquinas virtuais sob carga) ou se o estado aleatório nunca for redefinido entre os processos (bifurcação do processo sem propagar novamente o CSPRNG).
O que isso não cobre - exclusividade de v1 e v7, que se baseia em carimbos de data e hora e sequências de relógio, em vez de apenas na aleatoriedade
O substituto ToolAcre chama crypto.getRandomValues para cada matriz de bytes e não mantém nenhum estado PRNG no nível do aplicativo. Os componentes internos da plataforma continuam sendo de responsabilidade do navegador e do sistema operacional. A simulação de colisões com geradores reais mostra a diferença entre a teoria e a prática falida. Um gerador construído com Math.random partindo da mesma semente produzirá sequências idênticas; você verá a primeira colisão UUID dentro de algumas centenas a alguns milhares de valores gerados, não depois dos valores 2^60 (a raiz quadrada de 2^122) como a aproximação do aniversário prevê. Um gerador usando crypto.getRandomValues da entropia sólida do sistema operacional produzirá colisões somente quando a probabilidade teórica se tornar inevitável (em torno de 2^60 UUIDs), um número tão grande que você nunca o alcançará. Um gerador que usa uma fonte de entropia fraca ou reutilizada (comum em bibliotecas UUID ou estruturas de teste mal implementadas) produzirá colisões em algum ponto intermediário.
Conclusão: confie na matemática, audite o gerador — o gerador ToolAcre usa o CSPRNG do navegador, que é a parte que não deve ser falsificada
Um teste em lote pode capturar uma implementação que retorna uma constante ou reproduz uma sequência óbvia, mas uma amostra aprovada não pode provar a exclusividade futura. Os sistemas de produção ainda devem impor uma restrição única sempre que identificadores duplicados possam corromper os dados. As importações merecem atenção especial porque dois sistemas de origem válidos já podem conter o mesmo identificador literal e os fixtures podem ser copiados entre ambientes. Os testes de ToolAcre verificam se um lote de 500 contém valores distintos de 500; isso é uma verificação de regressão para esta implementação, não uma garantia estatística. Se aparecer uma duplicata, preserve as evidências e inspecione os caminhos de geração, importação, fixação e armazenamento antes de atribuir uma causa.