O mundo das criptomoedas pode parecer mágico quando comparado aos sistemas arcaicos de bancos. Mas sob esse verniz mágico, há algo ainda mais misterioso. Toneladas de matemática, software e infraestrutura se combinam graças aos esforços incansáveis (e em alguns casos praticamente mágicos) de pessoas motivadas e inteligentes trabalhando em direção a algo melhor para todos nós.
Vamos ampliar uma parte específica dessa combinação - uma na qual recentemente fizemos grandes desenvolvimentos. Mamy, um de nossos engenheiros, fez uma das implementações de assinatura BLS mais rápidas do mundo. Estamos trabalhando nisso desde 2018 e temos alguns grandes resultados para mostrar.
Então o que isso quer dizer?
Os protocolos criptográficos normalmente fornecem pelo menos um dos seguintes benefícios: confidencialidade, integridade, não repúdio ou autenticação. Confidencialidade significa que apenas as partes desejadas podem ler uma mensagem e geralmente é obtida por meio de criptografia. A integridade prova que uma mensagem não foi adulterada e geralmente é obtida por meio de funções de hash. O não repúdio garante a validade da autoria – ou seja, que alguém realmente fez algo. A autenticação prova que alguém é quem diz. Tanto o não repúdio quanto a autenticação são geralmente obtidos por meio de assinaturas digitais.
Vamos falar sobre um tipo específico de assinatura digital: assinaturas BLS (Boneh-Lynn-Shacham, os três autores do algoritmo). Assim como as assinaturas ECDSA, usadas pelo Bitcoin e Ethereum 1, as assinaturas BLS fornecem integridade, autenticação e não repúdio. Eles são particularmente importantes para o Status, pois são usados no Ethereum 2 (assim como Algorand, Chia, Dfinity, Filecoin, Tezos, Zcash e muitos mais).
As assinaturas BLS fornecem uma vantagem notável sobre o ECDSA: ou seja, as assinaturas BLS podem ser agregadas e, mais ainda, em espaço constante. Uma assinatura agregada é uma combinação de assinaturas que fornece as mesmas garantias que as assinaturas originais, mas ocupa menos espaço e geralmente é mais eficiente para trabalhar. Espaço constante significa que um voto de um validador ocupa a mesma quantidade de espaço de armazenamento que 10.000 votos de 10.000 validadores (ou qualquer outro número). Verificar 10.000 votos também é tão caro quanto verificar um único voto. As assinaturas BLS não vencem em todas as métricas - é significativamente mais lento verificar uma assinatura BLS em comparação com uma assinatura ECDSA, por exemplo. Assim, otimizar as assinaturas BLS é extremamente importante.
Benefícios mais diretos
A proliferação de protocolos de blockchain escaláveis de “próxima geração” premiou a geração de assinaturas digitais curtas que podem ser agregadas com eficiência ou facilmente limitadas.
- Ben Edgington, BLS12-381 For The Rest Of Us
A criptografia BLS é o gargalo mais caro no Nimbus – e em todos os clientes de consenso. A implementação do BLS da Mamy (chamada Constantine) é 1,14x mais rápida que o BLST para assinatura e 1,18x mais rápida que o BLST para verificação. Essas otimizações estão relacionadas a uma teoria brutal dos números e a detalhes de implementação/engenharia. Alguns exemplos estão usando uma representação compactada de números que satisfazem um relacionamento polinomial especial e usando o conjunto de maneiras mais otimizadas para reduzir o uso de memória.
Os detalhes (e número) das otimizações estão além do escopo deste artigo, mas uma lista completa está disponível aqui.
Qual é o próximo passo?
Criptógrafos que trabalham na otimização de algoritmos como esse planejam trabalhar juntos para criar um repositório para emparelhar benchmarks, ajudar a medir o desempenho de tais algoritmos e tornar o Ethereum 2 (assim como outros ecossistemas de criptomoedas que dependem do BLS) ser o mais rápido possível!
Constantine não aparecerá no Nimbus por um tempo ainda, pois há mais otimizações a serem feitas, e a biblioteca não é auditada atualmente (mas será auditada em breve).
O que é BLS? [técnico]
(Se você não estiver interessado na matemática do BLS, pode parar aqui.)
Abordaremos brevemente alguns detalhes do esquema de assinatura BLS, mas há uma matemática relativamente complexa e uma explicação completa exigiria vários artigos. Para matemáticos (ou masoquistas), o BLS12-381 For The Rest Of Us de Ben Edginton tem uma explicação mais abrangente (e também serviu como uma referência crucial para este post). As variáveis que usamos recebem os mesmos nomes que em seu artigo.
Observe que esta seção destina-se a fornecer alguma medida de compreensão do BLS, mas não deve ser usada como mais do que uma introdução muito básica ao material, pois alguns detalhes importantes, mas mais técnicos, são omitidos. Os tópicos que abordaremos, como álgebra abstrata, teoria de grupos, teoria de campos, corpos finitos e curvas elípticas são complexos o suficiente para garantir seus próprios posts, mas tememos por nossos leitores se nos tornarmos muito parecidos com um livro de matemática.
O esquema de assinatura BLS foi criado pelo trio Dan Boneh, Ben Lynn e Hovav Shacham em 2001.
Relógios também conhecidos como Aritmética Modular
Quando você faz “matemática do tempo” (considere um relógio de 12 horas para este exemplo), você adiciona números de uma maneira que não corresponde ao nosso entendimento usual de adição. “3 horas depois de 11” não é igual a 14, é 2. Estamos realizando um tipo especial de adição, onde somamos os números e depois reduzimos por 12. Não é por acaso que 2 = 14 - 12.
Curvas Elípticas
Uma curva elíptica (sobre os números reais) é uma curva que é descrita pela equação:
y^2 = x^3 + ax + b,
onde a e b são o tipo “usual” de números (números reais, por exemplo, 10, sqrt(2), pi).
As curvas elípticas são cruciais para muitos tipos de aplicativos de criptografia e criptomoeda. Elas também são um pouco como relógios. Os pontos em uma curva elíptica são pontos (x, y) que satisfazem a equação da curva. Esses pontos podem ser somados, notadamente, de uma maneira que não corresponde ao nosso entendimento usual de adição.
Adição de Curva Elíptica
P + Q = R
As curvas elípticas são simétricas em torno do eixo horizontal. Para adicionar dois pontos em uma curva elíptica, desenhe uma linha através dos dois pontos e encontre o terceiro ponto na curva que cruza a linha. Em seguida, reflita esse ponto sobre o eixo horizontal: esta é a soma de dois pontos em uma curva elíptica. (Adicionar um ponto P ao seu reflexo, ou seja, P + (-P), é um caso especial e resulta em “o ponto no infinito”, mas para nossos propósitos podemos apenas pensar nele como “zero”.)
Para obter mais detalhes sobre a adição de curvas elípticas, consulte A (relativamente fácil de entender) Primer on Elliptic Curve Cryptography, particularmente as seções “Curvas elípticas: blocos de construção de um alçapão” e “Estranha simetria”.
Para piorar a situação, nem todas as curvas elípticas são definidas “sobre os números reais”, o que significa que a e b podem ser menos familiares. Eles podem ser números complexos, por exemplo, ou elementos de qualquer campo sobre o qual a curva elíptica é definida (como na “curva elíptica E definida sobre o campo F”) – um campo é um conjunto de coisas semelhantes a números que se comportam geralmente como números (podem ser somados, subtraídos, multiplicados e divididos, exceto por zero).
Campos Finitos, também conhecidos como Relógios Estranhos
Campos finitos são um tipo de campo comum e útil. Considere um relógio que só vai até 5. Cada vez que você adiciona números neste relógio, você reduz em 5.
1 + 3 = 4
2 + 4 = 6 → 1
2 + 3 = 5 → 0
Também podemos multiplicar esses números e aplicar um processo semelhante de redução:
2*2 = 4
2*4 = 8 → 3
0*2 = 0
(A divisão é um pouco mais estranha e convenientemente desnecessária para nossos propósitos.)
Grupos
Grupos são como campos, mas com menos regras. Um grupo é uma coleção de coisas semelhantes a números que podem ser adicionadas (não necessariamente da maneira que normalmente pensamos em adição), e adicionar quaisquer dois elementos de um grupo sempre produzirá um terceiro elemento do grupo. Todo campo é um grupo, mas nem todo grupo é um campo.
Os grupos com os quais estamos preocupados serão cíclicos, o que significa que algum elemento específico do grupo pode ser adicionado a si mesmo para obter qualquer outro elemento do grupo. Este elemento é chamado de gerador.
Prelúdio BLS
Estamos preocupados com duas curvas elípticas que são referidas como BLS12-381 (Barreto-Lynn-Scott, mesmo Lynn). A primeira curva é definida sobre um corpo finito primo, ou seja, um corpo finito com q elementos, onde q é primo. A segunda curva é um pouco mais complexa e é definida sobre um corpo finito com elementos q^2. A relação entre o primeiro e o segundo campo é muito parecida com a dos números reais e complexos, o segundo campo é essencialmente o primeiro campo combinado com i.
Dissemos que as curvas elípticas são descritas pela equação y^2 = x^3 + ax + b.
Nossa primeira curva parece:
y^2 = x^3 + 0x + 4, ou seja, a = 0 e b = 4. Os pontos desta curva são representados como pares de inteiros.
Nossa segunda curva parece:
y^2 = x^3 + 4(1 + i), onde i é a raiz quadrada de -1. Os pontos desta curva são representados como pares de números complexos.
Encontramos um grupo de pontos em cada curva (a adição de tais pontos é realizada conforme descrito em “Adição de curva elíptica”), que chamaremos de G1 para a primeira curva e G2 para a segunda. Cada grupo tem o mesmo número de elementos, r. Para nossos propósitos, é importante que r seja primo.
Emparelhamentos/Funções Bilineares
Falaremos sobre pares e funções bilineares em apenas um segundo, mas primeiro, o que é uma função linear? Uma função f é linear se f(x+y) = f(x) + f(y) ef(a * x) = a * f(x).
Uma função bilinear é uma função de duas variáveis que é linear em relação a cada uma. Considere este exemplo simples: f(x,y) = xy. Se escolhermos algum valor constante diferente de zero para y, por exemplo. y=2, então f(x,2) = 2x, que sabemos ser linear; e se escolhermos algum valor constante diferente de zero para x, e.g. x=3, então f(3,y) = 3y, que sabemos ser linear. Então f(x,y) = xy é bilinear.
Vamos precisar de um emparelhamento para BLS. Para simplificar, podemos considerar um emparelhamento como uma função bilinear que recebe dois parâmetros de dois grupos (G1 e G2) do mesmo tamanho como entradas e produz uma saída de um terceiro grupo. Os pares são geralmente escritos como:
e(x,y), onde x é um elemento de G1, ey é um elemento de G2.
Esquema BLS (finalmente)
Então, aqui estão todas as peças.
r = número de elementos dos grupos G1 e G2, primo, <= 255 bits
sk = chave privada/secreta, número escolhido aleatoriamente entre 1 e r – 1, inclusive
g1 = gerador escolhido de G1, (ou seja, podemos adicionar g1 a si mesmo algumas vezes para obter qualquer ponto em G1). Como G1 tem um número primo de elementos, qualquer ponto pode funcionar como o gerador escolhido (embora na prática haja certas razões de eficiência para preferir um gerador a outro, e decidir qual gerador usar é feito de maneira reproduzível, de modo que as pessoas finais do esquema de assinatura podem escolher o mesmo).
pk = chave pública; pk = [sk]g1, ou seja, g1 + g1 + … + g1, sk vezes
O problema do logaritmo discreto torna inviável descobrir sk se você estiver começando com pk.
m = a mensagem a ser assinada.
Assumimos que existe alguma maneira de mapear m para um ponto de G2, feito por meio de alguma função de hash que chamamos de H. Praticamente todo esquema criptográfico envolvendo curvas elípticas inclui algum método de tradução de mensagens para um grupo na curva, então vamos passar por cima do detalhes.
H(m) = o ponto correspondente em G2 para a mensagem m
σ = assinatura, σ = [sk]H(m), ou seja, H(m) + H(m) + … + H(m), sk vezes
Então, um breve interlúdio: g1 é um elemento de G1, o que significa que é um ponto na primeira curva elíptica. Isso significa que a adição de g1 é uma adição de curva elíptica, que é um pouco estranha (como descrito em “Adição de curva elíptica”). H(m) é um elemento de G2, o que significa que é um ponto na segunda curva elíptica complexa. A adição de H(m) a si mesmo é igualmente estranha.
Para verificar uma assinatura, tomamos a mensagem m, a assinatura σ e a chave pública pk. Estamos verificando se a mensagem foi assinada com a chave secreta (sk) que corresponde a pk.
A assinatura é válida se e somente se e(g1, σ) = e(pk, H(m)), o que pode ser facilmente verificado (de preferência por um computador) dado o gerador (que é escolhido de forma específica e reproduzível) , a assinatura, a chave pública e o hash da mensagem.
Podemos usar um exemplo mais simples para entender como os emparelhamentos são úteis no BLS. Usaremos a função bilinear de exemplo simples f(x,y) = xy.
Então,
pk = chave pública = chave secreta * gerador = sk * g1
σ = assinatura = chave secreta * H(mensagem) = sk * H(m)
Se a mensagem foi assinada pela chave pública correspondente, as duas entradas de função a seguir produzirão a mesma saída (sem revelar a chave secreta):
f(g1, σ) = g1 * σ = g1 * sk * H(m)
f(pk, H(m)) = pk * H(m) = sk * g1 * H(m) = g1 * sk * H(m)
(Negrito é apenas para dar ênfase.)