A matemática por trás do protocolo Bitcoin

Um motivo pelo qual o Bitcoin pode ser confuso para iniciantes é que a Tecnologia por trás dele redefine o conceito de propriedade.

Possuir algo no sentido tradicional, seja uma casa ou uma quantia de dinheiro, significa ter a custódia pessoal da coisa ou conceder a custódia a uma entidade confiável, como um banco.

Protocolo Bitcoin

Com o Bitcoin o caso é diferente. Os próprios bitcoins não são armazenados centralmente ou localmente e, portanto, ONE entidade é sua custodiante. Eles existem como registros em um livro-razão distribuído chamado blockchain, cujas cópias são compartilhadas por uma rede voluntária de computadores conectados. “Possuir” um Bitcoin significa simplesmente ter a capacidade de transferir o controle dele para outra pessoa criando um registro da transferência no blockchain. O que concede essa capacidade? Acesso a um ECDSA par de chaves privada e pública. O que isso significa e como isso protege o Bitcoin?

Vamos dar uma olhada sob o capô.

ECDSAé a abreviação de Elliptic Curve Digital Signature Algorithm. É um processo que usa umcurva elípticae umcampo finito para “assinar” dados de tal forma que terceiros possam verificar a autenticidade da assinatura enquanto o signatário retém a capacidade exclusiva de criar a assinatura. Com Bitcoin, os dados que são assinados são a transação que transfere a propriedade.

O ECDSA tem procedimentos separados para assinatura e verificação. Cada procedimento é um algoritmo composto de algumas operações aritméticas. O algoritmo de assinatura faz uso da chave privada, e o processo de verificação faz uso da chave pública. Mostraremos um exemplo disso mais tarde.

Mas primeiro, um curso intensivo sobre curvas elípticas e corpos finitos.

Curvas elípticas

Uma curva elíptica é representada algebricamente como uma equação da forma:

y2 = x3 + ax + b

Para a = 0 e b = 7 (a versão usada pelo Bitcoin), LOOKS assim:

Curvas elípticas têm propriedades úteis. Por exemplo, uma linha não vertical que intercepta dois pontos não tangentes na curva sempre interceptará um terceiro ponto na curva. Outra propriedade é que uma linha não vertical tangente à curva em um ponto interceptará precisamente um outro ponto na curva.

Podemos usar essas propriedades para definir duas operações: adição de pontos e duplicação de pontos.

Adição de ponto,P + Q = R,é definido como a reflexão através do eixo x do terceiro ponto de intersecçãoR'em uma linha que incluiP e Pq. É mais fácil entender isso usando um diagrama:

De forma similar,ponto de duplicação,P + P = Ré definido encontrando a reta tangente ao ponto a ser duplicado,P, e tomando a reflexão através do eixo x do ponto de intersecçãoR'na curva para chegarR. Aqui está um exemplo de como isso seria:

Juntas, essas duas operações são usadas paramultiplicação escalar,R = um P,definido pela adição do pontoPpara si mesmoumvezes. Por exemplo:

R = 7P

R = P + (P + (P + (P + (P + (P + P)))))

O processo de multiplicação escalar é normalmente simplificado usando uma combinação de operações de adição de pontos e duplicação de pontos. Por exemplo:

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

Aqui, 7Pfoi dividido em duas etapas de duplicação de pontos e duas etapas de adição de pontos.

Campos finitos

Um campo finito, no contexto do ECDSA, pode ser pensado como um intervalo predefinido de números positivos dentro do qual todo cálculo deve cair. Qualquer número fora desse intervalo “envolve” para cair dentro do intervalo.

A maneira mais simples de pensar sobre isso é calculando restos, como representado pelo operador de módulo (mod). Por exemplo, 9/7 dá 1 com resto de 2:

9 módulo 7 = 2

Aqui, nosso corpo finito é módulo 7, e todas as operações de mod sobre esse corpo produzem um resultado dentro de um intervalo de 0 a 6.

Colocando tudo junto

ECDSA usa curvas elípticas no contexto de um campo finito, o que muda muito sua aparência, mas não suas equações subjacentes ou propriedades especiais. A mesma equação plotada acima, em um campo finito de módulo 67, LOOKS com isso:

Agora é um conjunto de pontos, em que todos osx e eos valores são inteiros entre 0 e 66. Observe que a “curva” ainda mantém sua simetria horizontal.

A adição e a duplicação de pontos agora são visualmente ligeiramente diferentes. As linhas desenhadas neste gráfico envolverão as direções horizontal e vertical, assim como em um jogo de Asteroides, mantendo a mesma inclinação. Então, adicionar os pontos (2, 22) e (6, 25) LOOKS assim:

O terceiro ponto de intersecção é (47, 39) e seu ponto de reflexão é (47, 28).

De volta ao ECDSA e Bitcoin

Um protocolo como o Bitcoin seleciona um conjunto de parâmetros para a curva elíptica e sua representação de campo finito que é fixa para todos os usuários do protocolo. Os parâmetros incluem o equaçãousado, omódulo PRIMEdo campo, e umponto baseque cai na curva. Oordem do ponto base, que não é selecionado independentemente, mas é uma função dos outros parâmetros, pode ser pensado graficamente como o número de vezes que o ponto pode ser adicionado a si mesmo até que sua inclinação seja infinita, ou uma linha vertical. O ponto base é selecionado de modo que a ordem seja um grande número PRIME .

O Bitcoin usa números muito grandes para seu ponto base, módulo PRIME e ordem. Na verdade, todas as aplicações práticas do ECDSA usam valores enormes. A segurança do algoritmo depende desses valores serem grandes e, portanto, impraticáveis ​​para força bruta ou engenharia reversa.

No caso do Bitcoin:

Equação da curva elíptica: y2 = x3 + 7

Módulo PRIME = 2256 – 232 – 29 – 28 – 27 – 26 – 24 - 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Ponto base = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Ordem = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Quem escolheu esses números e por quê? Uma grande quantidade depesquisar, e uma boa quantidade deintriga, envolve a seleção de parâmetros apropriados. Afinal, um número grande e aparentemente aleatório pode esconder um método de backdoor para reconstruir a chave privada. Em resumo, essa realização em particular é chamada de secp256k1 e faz parte de uma família de soluções de curvas elípticas sobre campos finitos propostas para uso em criptografia.

Chaves privadas e chaves públicas

Com essas formalidades resolvidas, agora estamos em posição de entender chaves privadas e públicas e como elas estão relacionadas. Aqui está em poucas palavras: No ECDSA, a chave privada é um número imprevisivelmente escolhido entre 1 e a ordem. A chave pública é derivada da chave privada pela multiplicação escalar do ponto base um número de vezes igual ao valor da chave privada. Expresso como uma equação:

chave pública = chave privada * ponto base

Isso mostra que o número máximo possível de chaves privadas (e, portanto, endereços de Bitcoin ) é igual à ordem.

Em um campo contínuo, poderíamos traçar a linha tangente e localizar a chave pública no The Graph, mas existem algumas equaçõesque realizam a mesma coisa no contexto de campos finitos. Adição de ponto dep + qpara encontrarré definido por componente da seguinte forma:

c = (qy - py) / (qx - px)

rx = c2 - px - qx

ry = c (px - rx) - py

E ponto de duplicação para encontrarré o seguinte:

c = (3px2 + a) / 2py

rx = c2 - 2px

ry = c (px - rx) - py

Na prática, o cálculo da chave pública é dividido em várias operações de duplicação e adição de pontos, começando pelo ponto base.

Vamos executar um exemplo de volta do envelope usando números pequenos, para ter uma intuição sobre como as chaves são construídas e usadas na assinatura e verificação. Os parâmetros que usaremos são:

Equação: y2 = x3 + 7 (ou seja, a = 0 e b = 7)

Módulo PRIME : 67

Ponto base: (2, 22)

Ordem: 79

Chave privada: 2

Primeiro, vamos encontrar a chave pública. Como selecionamos a chave privada mais simples possível com valor = 2, ela exigirá apenas uma única operação de duplicação de ponto a partir do ponto base. O cálculo LOOKS com isso:

c = (3 * 22 + 0) / (2 * 22) módulo 67

c = (3 * 4) / (44) mod 67

c = 12 / 44 mod 67

Aqui temos que fazer uma pausa para um BIT de prestidigitação: como realizamos a divisão no contexto de um corpo finito, onde o resultado deve ser sempre um inteiro? Temos que multiplicar pelo inverso, que o espaço não nos permite definir aqui (referimo-nos a aqui e aquise estiver interessado). No caso em questão, você terá que confiar em nós por enquanto que:

44-1 = 32

Seguindo em frente:

c = 12 * 32 módulo 67

c = 384 módulo 67

c = 49

rx = (492 - 2 * 2) mod 67

rx = (2401 - 4) mod 67

rx = 2397 mod 67

rx = 52

ry = (49 * (2 - 52) - 22) mod 67

ry = (49 * (-50) - 22) mod 67

ry = (-2450 - 22) mod 67

ry = -2472 mod 67

ry = 7

Nossa chave pública, portanto, corresponde ao ponto (52, 7). Todo esse trabalho para uma chave privada de 2!

Essa operação — passar da chave privada para a pública — é computacionalmente fácil em comparação a tentar trabalhar de trás para frente para deduzir a chave privada da chave pública, o que, embora teoricamente possível, é computacionalmente inviável devido aos grandes parâmetros usados na criptografia elíptica real.

Portanto, ir da chave privada para a chave pública é, por definição, uma viagem só de ida.

Assim como a chave privada, a chave pública é normalmente representada por uma sequência hexadecimal. Mas espere, como vamos de um ponto em um plano, descrito por dois números, para um único número? Em uma chave pública não compactada, os dois números de 256 BIT que representam o x e eas coordenadas são simplesmente coladas em uma longa sequência. Também podemos aproveitar a simetria da curva elíptica para produzir uma chave pública compactada, mantendo apenas o xvalor e anotando em qual metade da curva o ponto está. A partir dessa informação parcial, podemos recuperar ambas as coordenadas.

Assinando dados com a chave privada

Agora que temos um par de chaves privada e pública, vamos assinar alguns dados!

Os dados podem ter qualquer comprimento. O primeiro passo usual é fazer o hash dos dados para gerar um número contendo o mesmo número de bits (256) que a ordem da curva. Aqui, por uma questão de simplicidade, pularemos a etapa de hash e apenas assinaremos os dados brutospor. Nós chamaremosGo ponto base, a ordem eea chave privada. A receita para assinar é a seguinte:

• Escolha um inteiro k entre 1 e n - 1.
• Calcule o ponto (x, y) = k * G, usando multiplicação escalar.
• Encontre r = x mod n. Se r = 0, retorne ao passo 1.
• Encontre s = (z + r * d) / k mod n. Se s = 0, retorne ao passo 1.
• A assinatura é o par (r, s)

Como um lembrete, na etapa 4, se os números resultarem em uma fração (o que na vida real quase sempre acontece), o numerador deve ser multiplicado pelo inverso do denominador. Na etapa 1, é importante queonão deve ser repetido em assinaturas diferentes e não pode ser adivinhado por terceiros. Ou seja,o deve ser aleatório ou gerado por meios determinísticos que são mantidos em Secret de terceiros. Caso contrário, seria possível extrair a chave privada da etapa 4, uma vez que , por,r,oe são todos conhecidos. Você pode ler sobre um exploit passado deste tipoaqui.

Vamos escolher nossos dados para serem o número 17, e Siga a receita. Nossas variáveis:

z = 17 (dados)

n = 79 (ordem)

G = (2, 22) (ponto base)

d = 2 (chave privada)

• Escolha um número aleatório:

k = aleatório(1, n - 1)

k = aleatório(1, 79 - 1)

k = 3 (isso é realmente aleatório? OK, você nos pegou, mas isso tornará nosso exemplo mais simples!)

1. Calcule o ponto. Isso é feito da mesma maneira que determinar a chave pública, mas para abreviar, vamos omitir a aritmética para adição de pontos e duplicação de pontos.

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

x = 62

e = 63

1. Encontrar r:

r = x mod n

r = 62 módulo 79

r = 62

1. Encontrar :

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 módulo 79

s = (17 + 124) / 3 módulo 79

s = 141 / 3 módulo 79

s = 47 módulo 79

s = 47

Note que acima conseguimos dividir por 3, pois o resultado foi um inteiro. Em casos da vida real, usaríamos o inverso deo(como antes, escondemos alguns detalhes sangrentos ao computá-los em outro lugar):

s = (z + r * d) / k mod n

s = (17 + 62 * 2) / 3 módulo 79

s = (17 + 124) / 3 módulo 79

s = 141 / 3 módulo 79

s = 141 * 3-1 mod 79

s = 141 * 53 módulo 79

s = 7473 mod 79

s = 47

1. Nossa assinatura é o par (r, ) = (62, 47).

Assim como acontece com as chaves privadas e públicas, essa assinatura normalmente é representada por uma sequência hexadecimal.

Verificando a assinatura com a chave pública

Agora temos alguns dados e uma assinatura para esses dados. Um terceiro que tem nossa chave pública pode receber nossos dados e assinatura, e verificar que somos os remetentes. Vamos ver como isso funciona.

Com Pqsendo a chave pública e as outras variáveis definidas como antes, os passos para verificar uma assinatura são os seguintes:

• Verifique se r e s estão entre 1 e n - 1.
• Calcular w = s-1 mod n
• Calcular u = z * w mod n
• Calcular v = r * w mod n
• Calcule o ponto (x, y) = uG + vQ
• Verifique se r = x mod n. A assinatura é inválida se não for.

Por que essas etapas funcionam? Estamos pulando a prova, mas você pode ler os detalhesaqui. Vamos Siga a receita e ver como funciona. Nossas variáveis, mais uma vez:

z = 17 (dados)

(r, s) = (62, 47) (assinatura)

n = 79 (ordem)

G = (2, 22) (ponto base)

Q = (52, 7) (chave pública)

• Verifique sere estão entre 1 e - 1. Verifique e verifique.

r: 1 <= 62 < 79

s: 1 <= 47 < 79

1. Calcularc:

w = s-1 mod n

w = 47-1 mod 79

w = 37

1. Calcularvocê:

você = zw mod n

você = 17 * 37 mod 79

você = 629 mod 79

você = 76

1. Calcularvocê:

v = rw mod n

v = 62 * 37 módulo 79

v = 2294 mod 79

v = 3

1. Calcule o ponto (x,e):

(x, y) = uG + vQ

Vamos decompor a duplicação e a adição de pontos emuG e vQseparadamente.

uG = 76G

uG = 2(38G)

uG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(G + 2(G + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2(2G) ) ) ) )

Sente-se por um momento para apreciar que, ao usar o truque de agrupamento, reduzimos 75 operações de adição sucessivas para apenas seis operações de duplicação de pontos e duas operações de adição de pontos. Esses truques serão úteis quando os números ficarem realmente grandes.

Trabalhando de dentro para fora:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )

uG = 2( 2(G + 2(G + 2(25, 17) ) ) )

uG = 2( 2(G + 2( (2, 22) + (21, 42) ) )

uG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

uG = 2( 2(38, 26) )

uG = 2(27, 40)

uG = (62, 4)

E agora paravQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

Colocando-os juntos:

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

Claramente o passo 5 é a maior parte do trabalho. Para o passo final,

1. Verifique se r = x mod n

r = x mod n

62 = 62 mod 79

62 = 62

Nossa assinatura é válida!

Conclusão

Para aqueles que viram todas as equações e pularam para o final, o que acabamos de aprender?

Desenvolvemos alguma intuição sobre a profunda relação matemática que existe entre chaves públicas e privadas. Vimos como, mesmo nos exemplos mais simples, a matemática por trás de assinaturas e verificação rapidamente se complica, e podemos apreciar a enorme complexidade que deve estar envolvida quando os parâmetros envolvidos são números de 256 BIT . Vimos como a aplicação inteligente dos procedimentos matemáticos mais simples pode criar as funções de “alçapão” unidirecionais necessárias para preservar a assimetria de informações que define a propriedade de um Bitcoin. E temos uma confiança recém-descoberta na robustez do sistema, desde que protejamos cuidadosamente o conhecimento de nossas chaves privadas.

Em outras palavras, é por isso que é comumente dito que o Bitcoin é “apoiado pela matemática”.

Se você conseguiu superar as partes complicadas, esperamos que isso lhe tenha dado confiança para dar o próximo passo e tentar a matemática por conta própria (umaCalculadora aritmética modulartorna a matemática de campo finito muito mais fácil). Descobrimos que passar pelas etapas de assinatura e verificação de dados manualmente fornece uma compreensão mais profunda da criptografia que permite a forma única de propriedade do bitcoin.

Este artigo foi republicado aqui com a permissão do autor. Originalmente publicado emCadeia.com. O autor agradece especialmente a Steven Phelps pela ajuda neste artigo.

Eric Rykwalder é um engenheiro de software e um dos Cadeia.comfundadores.