Assinaturas Schnorr

As assinaturas Schnorr são melhores que o ECDSA para criar e verificar assinaturas digitais.

Elas são mais simples, mais eficientes e mais seguras que o ECDSA.

Além disso, a matemática mais simples também permite somar assinaturas, bem como verificar várias assinaturas ao mesmo tempo. Estes são dois recursos que não estão disponíveis com o ECDSA.

As assinaturas Schnorr foram adicionadas ao Bitcoin em 2021 como parte da atualização Taproot, e são usadas atualmente para destravar scripts de bloqueio P2TR.

Nesta página vou mostrar como implementar assinaturas Schnorr no Bitcoin, e também dar uma breve explicação de como elas funcionam.

# -------------------------
# Parâmetros da Curva Elíptica
# -------------------------
# estes são os parâmetros para secp256k1, a mesma curva usada no ECDSA
# nota: definindo estas como variáveis $global para que sejam acessíveis dentro das funções abaixo (sem ter que passá-las como argumentos)

# y² = x³ + ax + b
$a = 0
$b = 7

# corpo primo
$p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 #=> 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

# número de pontos na curva que podemos alcançar ("ordem")
$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 #=> 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# ponto gerador (o ponto inicial na curva usado para todos os cálculos)
$G = {
  x: 55066263022277343669578718895168534326250603453777594175500187360389116729240, #=> 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
  y: 32670510020758816978083085130507043184471273380659243275938904335757337482424, #=> 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
}

# --------------------------
# Matemática da Curva Elíptica
# --------------------------

# Inverso Modular: Ruby não tem uma função modinv nativa
def inverse(a, m = $p)
  m_orig = m         # armazenar módulo original
  a = a % m if a < 0 # garantir que a seja positivo
  y_prev = 0
  y = 1
  while a > 1
    q = m / a

    y_before = y # armazenar valor atual de y
    y = y_prev - q * y # calcular novo valor de y
    y_prev = y_before # definir y anterior como o valor antigo de y

    a_before = a # armazenar valor atual de a
    a = m % a # calcular novo valor de a
    m = a_before # definir m como o valor antigo de a
  end
  return y % m_orig
end

# Double: somar um ponto a ele mesmo
def double(point)
  # verificar ponto no infinito (máximo divisor comum entre 2y e p não é 1)
  if (((2 * point[:y]) % $p).gcd($p) != 1) # extraído do BitcoinECDSA.php
    raise "Ponto no infinito."
  end

  # slope = (3x₁² + a) / 2y₁
  slope = ((3 * point[:x] ** 2 + $a) * inverse((2 * point[:y]), $p)) % $p # usando inverse para ajudar com a divisão

  # x = slope² - 2x₁
  x = (slope ** 2 - (2 * point[:x])) % $p

  # y = slope * (x₁ - x) - y₁
  y = (slope * (point[:x] - x) - point[:y]) % $p

  # Retornar o novo ponto
  return { x: x, y: y }
end

# Add: somar dois pontos
def add(point1, point2)
  # duplicar se ambos os pontos forem iguais
  if point1 == point2
    return double(point1)
  end

  # verificar ponto no infinito (máximo divisor comum entre x1-x2 e p não é 1)
  if ((point1[:x] - point2[:x]).gcd($p) != 1) # extraído do BitcoinECDSA.php
    raise "Ponto no infinito."
  end

  # slope = (y₁ - y₂) / (x₁ - x₂)
  slope = ((point1[:y] - point2[:y]) * inverse(point1[:x] - point2[:x], $p)) % $p

  # x = slope² - x₁ - x₂
  x = (slope ** 2 - point1[:x] - point2[:x]) % $p

  # y = slope * (x₁ - x) - y₁
  y = ((slope * (point1[:x] - x)) - point1[:y]) % $p

  # Retornar o novo ponto
  return { x: x, y: y }
end

# Multiply: usar operações double e add para multiplicar rapidamente um ponto por um valor inteiro (ex.: chave privada)
def multiply(k, point = $G)
  # criar uma cópia do ponto inicial (para uso na adição depois)
  current = point

  # converter inteiro para representação binária
  binary = k.to_s(2)

  # algoritmo double-and-add para multiplicação rápida
  binary.split("").drop(1).each do |char| # da esquerda para a direita, ignorando o primeiro caractere binário
    # 0 = double
    current = double(current)

    # 1 = double e add
    current = add(current, point) if char == "1"
  end

  # retornar o ponto final
  current
end

# ---------
# Funções
# ---------
# funções auxiliares

# converter string hexadecimal de bytes para inteiro
def int(bytes)
  return bytes.to_i(16)
end

# converter inteiro para string hexadecimal de bytes
def bytes(int)
  return int.to_s(16).rjust(64, "0") # converter para hex e preencher com zeros para ter 32 bytes (64 caracteres)
end

# -----------
# Hash Marcado (Tagged Hash)
# -----------
require "digest" # biblioteca para função hash SHA256

# aplicar hash em alguns dados usando SHA256 com um prefixo de marcação (tag)
def tagged_hash(tag, message)

  # criar um hash da tag primeiro
  tag_hash = Digest::SHA256.hexdigest(tag) # aplicar hash na string diretamente

  # prefixar a mensagem com o hash da tag (o tag_hash é prefixado duas vezes para que o prefixo tenha 64 bytes no total)
  preimage = [tag_hash + tag_hash + message].pack("H*") # também converter para sequência de bytes antes de hashear

  # SHA256(tag_hash || tag_hash || message)
  result = Digest::SHA256.hexdigest(preimage);

  return result
end

# ----
# Chaves
# ----
# Exemplo de chave privada (em hexadecimal)
private_key = "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef"

# Chave pública é o ponto gerador multiplicado pela chave privada
point = multiply(int(private_key))

# a chave pública é apenas o valor x deste ponto
public_key = bytes(point[:x]) # converter coordenada x para bytes hexadecimais

#puts public_key #=> dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659

# ----
# Assinar
# ----
puts "Assinando:"

private_key = "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef"
aux_rand = "0000000000000000000000000000000000000000000000000000000000000001" # bytes auxiliares para contribuir com a aleatoriedade do nonce (a segurança não depende disto ser aleatório)
message = "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89"

puts " private key: #{private_key}"
puts " aux rand:    #{aux_rand}"
puts " message:     #{message}"

# converter chave privada para um inteiro
d0 = int(private_key)

# garantir que a chave privada esteja em uma faixa válida (maior que 0 e menor que o número de pontos na curva)
unless (1..$n-1).include?(d0)
  raise "chave privada deve estar na faixa 1..n-1"
end

# calcular o ponto da chave pública a partir da chave privada
public_key_point = multiply(d0) # multiply() verifica ponto no infinito

# negar a chave privada se a chave pública que ela cria não tiver um valor y par, senão manter a chave privada igual
# nota: devido à forma como a curva elíptica funciona, negar a chave privada produzirá uma chave pública com a mesma coordenada x, mas com o valor y oposto
if public_key_point[:y] % 2 != 0
  d = $n - d0
else
  d = d0
end

# criar um hash marcado dos bytes auxiliares
aux_rand_hash = tagged_hash("BIP0340/aux", aux_rand)

# primeiro passo para criar o nonce é XOR a chave privada com o hash dos bytes auxiliares
t = d ^ int(aux_rand_hash)

# criar o nonce hasheando t (do passo anterior) junto com a chave_pública e a mensagem
k0 = int(tagged_hash("BIP0340/nonce", bytes(t) + bytes(public_key_point[:x]) + message)) % $n # a chave pública está incluída no hash para assinaturas Schnorr "com prefixo de chave"

# verificar se o nonce não é zero
if k0 == 0
  raise "nonce não deve ser zero (isto é quase impossível, mas verificando mesmo assim)"
end

# usar este nonce para obter um ponto na curva
random_point = multiply(k0) # multiply() verifica ponto no infinito

# negar o nonce usado para criar o ponto aleatório se a chave pública que ele cria não tiver um valor y par
if random_point[:y] % 2 != 0
  k = $n - k0
  # nota: devido à forma como a curva elíptica funciona, a chave privada inversa produzirá um valor y par
else
  k = k0
end

# criar o valor do desafio e hasheando o ponto aleatório com a chave pública e a mensagem
e = int(tagged_hash("BIP0340/challenge", bytes(random_point[:x]) + bytes(public_key_point[:x]) + message)) % $n

# valor r é a coordenada x do ponto R
r =  random_point[:x]

# valor s: (k + e*d) mod n
s = (k + e * d) % $n # isto é linear (enquanto s no ECDSA é não-linear)

# assinatura são os valores r e s convertidos para string hexadecimal de 32 bytes e concatenados
sig = bytes(r) + bytes(s)

# você deve verificar se a assinatura é válida antes de retorná-la
puts "              ↓"
puts " signature:   #{sig}" #=> 6896bd60eeae296db48a229ff71dfe071bde413e6d43f917dc8dcf8c78de33418906d11ac976abccb20b091292bff4ea897efcb639ea871cfa95f6de339e4b0a
puts

# ------
# Verificar
# ------
puts "Verificando:"

public_key = "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659"
message = "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89"
sig = "6896bd60eeae296db48a229ff71dfe071bde413e6d43f917dc8dcf8c78de33418906d11ac976abccb20b091292bff4ea897efcb639ea871cfa95f6de339e4b0a"

puts " public key:  #{public_key}"
puts " message:     #{message}"
puts " signature:   #{sig}"

# converter chave pública (coordenada x apenas) em um ponto - lift_x() no BIP 340
x = int(public_key) # converter coordenada x de hex para inteiro
y_sq = (x**3 + 7) % $p # usar a equação da curva elíptica (y² = x³ + ax + b) para descobrir o valor de y a partir de x
y = y_sq.pow(($p+1)/4, $p) # secp256k1 é escolhida de forma especial para que a raiz quadrada de y seja y^((p+1)/4)

# verificar se a coordenada x é menor que o tamanho do corpo
if x >= $p
  raise "o valor x na chave pública não é uma coordenada válida porque não é menor que o tamanho do corpo da curva elíptica"
end

# verificar se o valor y calculado é a raiz quadrada de y_sq (caso contrário a chave pública não era uma coordenada x válida na curva)
if (y**2) % $p != y_sq
  raise "chave pública não é uma coordenada x válida na curva"
end

# se o valor y calculado for ímpar, negá-lo para obter o valor y par (para esta coordenada x)
if y % 2 != 0
  y = $p - y
end

# ponto da chave pública
public_key_point = {x: x, y: y}

# extrair o valor r da assinatura e converter para inteiro
r = sig[0..63] # primeiros 32 bytes (64 caracteres)

# extrair o valor s da assinatura e converter para inteiro
s = sig[64..-1] # últimos 32 bytes (64 caracteres)

# verificar se r é menor que o tamanho do corpo
if int(r) >= $p
  raise "o valor r na assinatura não é menor que o tamanho do corpo da curva elíptica"
end

# verificar se s é menor que o número de pontos na curva (ordem)
if int(s) >= $n
  raise "o valor s na assinatura não é menor que o número de pontos na curva elíptica"
end

# criar o desafio e hasheando o ponto aleatório com a chave pública e a mensagem (igual ao processo de assinar)
e = tagged_hash("BIP0340/challenge", r + bytes(x) + message).to_i(16) % $n # convertendo a coordenada x inteira para string hexadecimal de 32 bytes

# criar um ponto na curva multiplicando o ponto gerador por s
point1 = multiply(int(s), $G)

# criar outro ponto na curva multiplicando o ponto da chave pública por e
point2 = multiply($n - e, public_key_point) # nota: usamos ($n - e) para que a adição de pontos no passo seguinte seja uma subtração (point1 - point2)

# somar estes pontos para calcular um terceiro ponto (R)
point3 = add(point1, point2) # add() verifica ponto no infinito

# verificar se R tem valor y par
if point3[:y] % 2 != 0
  raise "o R calculado durante a verificação da assinatura tem um valor y ímpar (deveria ser par)"
end

# verificação da assinatura: verificar se o terceiro ponto calculado corresponde à coordenada x do ponto aleatório (r) fornecido na assinatura
puts "              ↓"
puts " result:      success" if point3[:x] == int(r)
puts " result:      fail" if point3[:x] != int(r)

Implementação

Como você cria uma assinatura Schnorr?

Primeiramente, as assinaturas Schnorr usam criptografia de curva elíptica. Não é essencial entender matemática de curva elíptica antes de implementar assinaturas Schnorr, mas ajuda.

De qualquer forma, as assinaturas Schnorr usam a curva elíptica Secp256k1 (mesma do ECDSA):

# y² = x³ + ax + b
$a = 0
$b = 7

# corpo primo
$p = 115792089237316195423570985008687907853269984665640564039457584007908834671663 #=> 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

# número de pontos na curva que podemos alcançar ("ordem")
$n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 #=> 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# ponto gerador (o ponto inicial na curva usado para todos os cálculos)
$G = {
  x: 55066263022277343669578718895168534326250603453777594175500187360389116729240, #=> 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
  y: 32670510020758816978083085130507043184471273380659243275938904335757337482424, #=> 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
}

Além disso, você também precisa ser capaz de multiplicar pontos em uma curva elíptica (mesma do ECDSA):

# Inverso Modular: Ruby não tem uma função modinv nativa
def inverse(a, m = $p)
  m_orig = m         # armazenar módulo original
  a = a % m if a < 0 # garantir que a seja positivo
  y_prev = 0
  y = 1
  while a > 1
    q = m / a

    y_before = y # armazenar valor atual de y
    y = y_prev - q * y # calcular novo valor de y
    y_prev = y_before # definir y anterior como o valor antigo de y

    a_before = a # armazenar valor atual de a
    a = m % a # calcular novo valor de a
    m = a_before # definir m como o valor antigo de a
  end
  return y % m_orig
end

# Double: somar um ponto a ele mesmo
def double(point)
  # verificar ponto no infinito (máximo divisor comum entre 2y e p não é 1)
  if (((2 * point[:y]) % $p).gcd($p) != 1) # extraído do BitcoinECDSA.php
    raise "Ponto no infinito."
  end

  # slope = (3x₁² + a) / 2y₁
  slope = ((3 * point[:x] ** 2 + $a) * inverse((2 * point[:y]), $p)) % $p # usando inverse para ajudar com a divisão

  # x = slope² - 2x₁
  x = (slope ** 2 - (2 * point[:x])) % $p

  # y = slope * (x₁ - x) - y₁
  y = (slope * (point[:x] - x) - point[:y]) % $p

  # Retornar o novo ponto
  return { x: x, y: y }
end

# Add: somar dois pontos
def add(point1, point2)
  # duplicar se ambos os pontos forem iguais
  if point1 == point2
    return double(point1)
  end

  # verificar ponto no infinito (máximo divisor comum entre x1-x2 e p não é 1)
  if ((point1[:x] - point2[:x]).gcd($p) != 1) # extraído do BitcoinECDSA.php
    raise "Ponto no infinito."
  end

  # slope = (y₁ - y₂) / (x₁ - x₂)
  slope = ((point1[:y] - point2[:y]) * inverse(point1[:x] - point2[:x], $p)) % $p

  # x = slope² - x₁ - x₂
  x = (slope ** 2 - point1[:x] - point2[:x]) % $p

  # y = slope * (x₁ - x) - y₁
  y = ((slope * (point1[:x] - x)) - point1[:y]) % $p

  # Retornar o novo ponto
  return { x: x, y: y }
end

# Multiply: usar operações double e add para multiplicar rapidamente um ponto por um valor inteiro (ex.: chave privada)
def multiply(k, point = $G)
  # criar uma cópia do ponto inicial (para uso na adição depois)
  current = point

  # converter inteiro para representação binária
  binary = k.to_s(2)

  # algoritmo double-and-add para multiplicação rápida
  binary.split("").drop(1).each do |char| # da esquerda para a direita, ignorando o primeiro caractere binário
    # 0 = double
    current = double(current)

    # 1 = double e add
    current = add(current, point) if char == "1"
  end

  # retornar o ponto final
  current
end

Chaves

Para criar e verificar assinaturas Schnorr, você precisa começar gerando um par de chaves.

1. Chave Privada
2. Chave Pública

Estas chaves privadas e chaves públicas são quase exatamente as mesmas que você já gera no Bitcoin.

1. Chave Privada

Uma chave privada é um número de 256 bits gerado aleatoriamente.

Geralmente é representada como uma string hexadecimal de 32 bytes:

6c8bedef612883700a7e66e2746eba4db006fd28bdd6db8f389a8845a0e3b59d

Chave Privada

Chave Privada

Gere um número aleatório de 256 bits.

Gerar aleatório Restaurar

Bits

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Binário

0b

0 bits Decimal

0d

Hexadecimal

0x

0 bytes

Nunca use uma chave privada gerada por um site, nem digite sua chave privada em um site. Sites podem facilmente salvar a chave privada e usá-la para roubar seus bitcoins.

Nunca use uma chave privada gerada por um site, nem digite sua chave privada em um site. Sites podem facilmente salvar a chave privada e usá-la para roubar seus bitcoins.

2. Chave Pública

Uma chave pública é criada multiplicando o ponto gerador na curva elíptica pela chave privada.

Por exemplo:

chave pública = {
  x: 94143704248521553317086831157498059579898345832673799690735511018320990355030,
  y: 44438543306112247703620323006762464482367802894269621488396118668492541437765,
}

Multiplicação na Curva

Multiplicação de Ponto (EC Multiply)

Multiplique um ponto na curva elíptica secp256k1.

Ponto Gerador Ponto Aleatório

Ponto 1

x:

0d

y:

0d

Multiplicador

0d

+1 Aleatório

Ponto 1 × Multiplicador

x:

0d

y:

0d

Steps [mostrar]

Chave Pública

Chave Pública

Calcule a chave pública a partir de uma chave privada.

Gerar aleatória Chave Privada 0 bytes

Chave Pública

Coordenadas

x:

0d

y:

0d

Uma chave pública é apenas um ponto em uma curva elíptica. A chave pública final são essas coordenadas em hexadecimal.

Compressão

Comprimida (prefixo 02/03) Não comprimida (prefixo 04) x-only (sem prefixo)

A curva é simétrica no eixo x, então a chave comprimida guarda só a coordenada x e se o y é par ou ímpar. A x-only é usada em saídas Taproot.

Chave pública serializada 0 bytes

Nunca digite sua chave privada em um site, nem use uma chave privada gerada por um site. Sites podem facilmente salvar a chave privada e usá-la para roubar seus bitcoins.

Esta é a mesma forma como você geraria qualquer outra chave pública.

Porém, ao usar assinaturas Schnorr no Bitcoin, a chave pública codificada é apenas a coordenada x representada como uma string hexadecimal de 32 bytes:

d02372c4789c6a1d6cf6cf137cc708153a4dbf70ec3ecd0b578476c5a2b4be56

Chaves públicas para assinaturas Schnorr no Bitcoin sempre usam a coordenada y par. Portanto, a informação sobre a coordenada y não é incluída como parte da chave pública codificada.

Você pode converter uma chave pública comprimida típica para uma chave pública usada em assinaturas Schnorr simplesmente removendo o primeiro byte (que é usado para indicar a polaridade da coordenada y):

chave pública comprimida = 03d02372c4789c6a1d6cf6cf137cc708153a4dbf70ec3ecd0b578476c5a2b4be56
chave pública schnorr    =   d02372c4789c6a1d6cf6cf137cc708153a4dbf70ec3ecd0b578476c5a2b4be56

# ---------
# Funções
# ---------
# funções auxiliares

# converter string hexadecimal de bytes para inteiro
def int(bytes)
  return bytes.to_i(16)
end

# converter inteiro para string hexadecimal de bytes
def bytes(int)
  return int.to_s(16).rjust(64, "0") # converter para hex e preencher com zeros para ter 32 bytes (64 caracteres)
end

# ----
# Chaves
# ----
# Exemplo de chave privada (em hexadecimal)
private_key = "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef"

# Chave pública é o ponto gerador multiplicado pela chave privada
point = multiply(int(private_key))

# a chave pública é apenas o valor x deste ponto
public_key = bytes(point[:x]) # converter coordenada x para bytes hexadecimais

#puts public_key #=> dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659

Assinar

Assinatura Schnorr

Assinatura Schnorr

Assine uma mensagem usando uma chave privada.

Exemplo Aleatório Chave Privada (d')

0x

Aleatório

0 bytes Bytes Auxiliares (aux_rand)

0x

+1 Aleatório

0 bytes Mensagem (m)

0x

0 bytes

Detalhes [mostrar]

Chave Pública (P) = d'G

x:

0x

y:

0x

Chave Privada (d) = (n − d') se P[y] é ímpar

0x

Nonce Privado

aux_rand_hash = hash_BIP0340/aux(aux_rand)

0x

t = d XOR aux_rand_hash

0x

k' = int(hash_{BIP0340/nonce}(t ‖ P[x] ‖ m)) % n

0x

Nonce Público (R) = k'G

x:

0x

y:

0x

k = (n − k') se R[y] é ímpar

0x

Challenge (e) = int(hash_{BIP0340/challenge}(R[x] ‖ P[x] ‖ m)) % n

0x

Assinatura

r = R[x]

0d

s = (k + e·d) % n

0d

Assinatura

0x

0 bytes

Nunca insira sua chave privada em um site, nem use uma chave privada gerada por um site. Sites podem facilmente salvar a chave privada e usá-la para roubar seus bitcoins.

# ---------
# Funções
# ---------
# funções auxiliares

# converter string hexadecimal de bytes para inteiro
def int(bytes)
  return bytes.to_i(16)
end

# converter inteiro para string hexadecimal de bytes
def bytes(int)
  return int.to_s(16).rjust(64, "0") # converter para hex e preencher com zeros para ter 32 bytes (64 caracteres)
end

# -----------
# Hash Marcado (Tagged Hash)
# -----------
require "digest" # biblioteca para função hash SHA256

# aplicar hash em alguns dados usando SHA256 com um prefixo de marcação (tag)
def tagged_hash(tag, message)

  # criar um hash da tag primeiro
  tag_hash = Digest::SHA256.hexdigest(tag) # aplicar hash na string diretamente

  # prefixar a mensagem com o hash da tag (o tag_hash é prefixado duas vezes para que o prefixo tenha 64 bytes no total)
  preimage = [tag_hash + tag_hash + message].pack("H*") # também converter para sequência de bytes antes de hashear

  # SHA256(tag_hash || tag_hash || message)
  result = Digest::SHA256.hexdigest(preimage);

  return result
end

# ----
# Assinar
# ----
puts "Assinando:"

private_key = "b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef"
aux_rand = "0000000000000000000000000000000000000000000000000000000000000001" # bytes auxiliares para contribuir com a aleatoriedade do nonce (a segurança não depende disto ser aleatório)
message = "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89"

puts " private key: #{private_key}"
puts " aux rand:    #{aux_rand}"
puts " message:     #{message}"

# converter chave privada para um inteiro
d0 = int(private_key)

# garantir que a chave privada esteja em uma faixa válida (maior que 0 e menor que o número de pontos na curva)
unless (1..$n-1).include?(d0)
  raise "chave privada deve estar na faixa 1..n-1"
end

# calcular o ponto da chave pública a partir da chave privada
public_key_point = multiply(d0) # multiply() verifica ponto no infinito

# negar a chave privada se a chave pública que ela cria não tiver um valor y par, senão manter a chave privada igual
# nota: devido à forma como a curva elíptica funciona, negar a chave privada produzirá uma chave pública com a mesma coordenada x, mas com o valor y oposto
if public_key_point[:y] % 2 != 0
  d = $n - d0
else
  d = d0
end

# criar um hash marcado dos bytes auxiliares
aux_rand_hash = tagged_hash("BIP0340/aux", aux_rand)

# primeiro passo para criar o nonce é XOR a chave privada com o hash dos bytes auxiliares
t = d ^ int(aux_rand_hash)

# criar o nonce hasheando t (do passo anterior) junto com a chave_pública e a mensagem
k0 = int(tagged_hash("BIP0340/nonce", bytes(t) + bytes(public_key_point[:x]) + message)) % $n # a chave pública está incluída no hash para assinaturas Schnorr "com prefixo de chave"

# verificar se o nonce não é zero
if k0 == 0
  raise "nonce não deve ser zero (isto é quase impossível, mas verificando mesmo assim)"
end

# usar este nonce para obter um ponto na curva
random_point = multiply(k0) # multiply() verifica ponto no infinito

# negar o nonce usado para criar o ponto aleatório se a chave pública que ele cria não tiver um valor y par
if random_point[:y] % 2 != 0
  k = $n - k0
  # nota: devido à forma como a curva elíptica funciona, a chave privada inversa produzirá um valor y par
else
  k = k0
end

# criar o valor do desafio e hasheando o ponto aleatório com a chave pública e a mensagem
e = int(tagged_hash("BIP0340/challenge", bytes(random_point[:x]) + bytes(public_key_point[:x]) + message)) % $n

# valor r é a coordenada x do ponto R
r =  random_point[:x]

# valor s: (k + e*d) mod n
s = (k + e * d) % $n # isto é linear (enquanto s no ECDSA é não-linear)

# assinatura são os valores r e s convertidos para string hexadecimal de 32 bytes e concatenados
sig = bytes(r) + bytes(s)

# você deve verificar se a assinatura é válida antes de retorná-la
puts "              ↓"
puts " signature:   #{sig}" #=> 6896bd60eeae296db48a229ff71dfe071bde413e6d43f917dc8dcf8c78de33418906d11ac976abccb20b091292bff4ea897efcb639ea871cfa95f6de339e4b0a
puts

Método

1. Obtenha os dados necessários para assinar.

Para criar uma assinatura Schnorr, você precisa começar com os seguintes dados:

• Chave Privada (d') — Esta é a chave privada usada para criar a chave pública para a qual você quer criar uma assinatura.
• Bytes Auxiliares (aux_rand) — 32 bytes de dados gerados aleatoriamente. São usados para criar a parte aleatória da assinatura. O ideal é que estes bytes sejam completamente aleatórios, mas é perfeitamente aceitável simplesmente incrementar estes bytes auxiliares para cada assinatura que você criar a partir de uma chave privada específica.
• Mensagem (m) — A mensagem que você quer assinar. Pode ter qualquer tamanho, embora tipicamente seja um hash de 32 bytes de algum dado.

2. Calcule a chave pública (P).

P = d' · G

Para começar, calcule a chave pública (P) a partir da chave privada (d') usando multiplicação de curva elíptica.

Conversor de Número

Conversor de Números

Converta um número entre bases diferentes (binário, decimal, hexadecimal).

Binário (Base 2)

0b

0 dígitos Decimal (Base 10)

0d

0 dígitos Hexadecimal (Base 16)

0x

0 dígitos +1

Multiplicação na Curva

Multiplicação de Ponto (EC Multiply)

Multiplique um ponto na curva elíptica secp256k1.

Ponto Gerador Ponto Aleatório

Ponto 1

x:

0d

y:

0d

Multiplicador

0d

+1 Aleatório

Ponto 1 × Multiplicador

x:

0d

y:

0d

Steps [mostrar]

Em termos técnicos:

1. Converta a chave privada (d') para um inteiro.
2. Verifique se a chave privada é válida (no intervalo de 1..n-1, onde n é o número de pontos na curva elíptica).
3. Multiplique o ponto gerador (G) pela chave privada (d').

A chave pública é usada em alguns lugares ao criar a assinatura, por isso estamos fazendo isto no começo.

3. Negue a chave privada (d') se a coordenada y da chave pública (P[y]) for ímpar.

Se a chave privada produzir uma chave pública com uma coordenada y par, mantemos a chave privada como está:

d = d'

Porém, se a chave privada produzir uma chave pública com uma coordenada y ímpar, precisamos negar a chave privada subtraindo-a do número de pontos na curva:

d = n - d'

O esquema de assinatura Schnorr no Bitcoin assume que todos os pontos têm coordenadas y pares, então precisamos usar a versão "correta" da chave privada antes de usá-la nos próximos passos.

Uma chave privada negada produzirá uma chave pública com a mesma coordenada x, mas com a coordenada y oposta.

Portanto, mesmo que possamos negar a chave privada neste passo, a chave privada original ainda é válida, pois tanto a chave privada original quanto a versão negada produzem a "mesma" chave pública (isto é, a mesma coordenada x).

Por exemplo, aqui estão uma chave privada e sua negação. Tente converter ambas para chaves públicas para ver o que quero dizer:

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

private key (d)  = 49097021556540366728351378259471079529932651371354504836784826377767265482141
negated (n - d)  = 66695067680775828695219606749216828322904912907720399545820336763750896012196

private key (d)  = 0x6c8bedef612883700a7e66e2746eba4db006fd28bdd6db8f389a8845a0e3b59d
negated (n - d)  = 0x937412109ed77c8ff581991d8b9145b10aa7dfbdf171c4ac8737d6472f528ba4

Chave Pública

Chave Pública

Calcule a chave pública a partir de uma chave privada.

Gerar aleatória Chave Privada 0 bytes

Chave Pública

Coordenadas

x:

0d

y:

0d

Uma chave pública é apenas um ponto em uma curva elíptica. A chave pública final são essas coordenadas em hexadecimal.

Compressão

Comprimida (prefixo 02/03) Não comprimida (prefixo 04) x-only (sem prefixo)

A curva é simétrica no eixo x, então a chave comprimida guarda só a coordenada x e se o y é par ou ímpar. A x-only é usada em saídas Taproot.

Chave pública serializada 0 bytes

Nunca digite sua chave privada em um site, nem use uma chave privada gerada por um site. Sites podem facilmente salvar a chave privada e usá-la para roubar seus bitcoins.

4. Crie o nonce privado (k').

O nonce privado (k') é o elemento aleatório da assinatura. Ele é construído em três etapas:

1. Crie um hash marcado dos seus bytes auxiliares escolhidos (aux_rand):

aux_rand_hash = hashBIP0340/aux(aux_rand)

Hash Marcado

Tagged Hash

Cria um hash de dados com um prefixo de tag.
Usado em Schnorr sign, Schnorr verify e Taproot.

Exemplo aleatório

String

BIP0340/auxBIP0340/nonceBIP0340/challengeTapLeafTapBranchTapTweakTapSighash

Dados (Hex) 0 bytes

Resultado

SHA256(SHA256(string) || SHA256(string) || dados)

0 bytes

Os bytes auxiliares serão usados para modificar nossa chave privada (d), que será usada como fonte de aleatoriedade para nossa assinatura.

Os bytes auxiliares devem ser diferentes para cada assinatura. Caso contrário, o próximo nonce privado (k') será o mesmo para assinaturas diferentes, o que permitiria a um atacante calcular nossa chave privada.

2. Faça XOR da chave privada (d) com o hash dos bytes auxiliares (aux_rand_hash):

t = d XOR aux_rand_hash

Isto produz um valor temporário (t), que será diferente para cada assinatura que criarmos.

É perfeitamente aceitável incrementar os bytes auxiliares para cada assinatura em vez de gerar 32 bytes completamente aleatórios a cada vez, pois este valor temporário (t) ainda será único o suficiente para a assinatura ser segura. Porém, é preferível usar bytes auxiliares aleatórios a cada vez se você puder.

3. Crie o nonce privado final (k'):

k' = int(hashBIP0340/nonce(t || P[x] || m)) % n

Hash Marcado

Tagged Hash

Cria um hash de dados com um prefixo de tag.
Usado em Schnorr sign, Schnorr verify e Taproot.

Exemplo aleatório

String

BIP0340/auxBIP0340/nonceBIP0340/challengeTapLeafTapBranchTapTweakTapSighash

Dados (Hex) 0 bytes

Resultado

SHA256(SHA256(string) || SHA256(string) || dados)

0 bytes

Este nonce privado (k') é um hash marcado dos seguintes dados:

• t = valor temporário (da etapa anterior)
• P[x] = coordenada x da chave pública (do passo 2) convertida para bytes
• m = mensagem (do passo 1)

Então convertemos este hash para um inteiro e aplicamos módulo pelo número de pontos na curva elíptica (n).

Isto produz um número que podemos usar como nosso nonce privado (k') para criar a assinatura.

A entrada secreta deste hash é (t). Ela vem da combinação da chave privada (d) com os bytes auxiliares escolhidos (aux_rand).

O nonce privado (k') na maioria dos esquemas de assinatura é apenas um número gerado aleatoriamente.

Porém, usar esta configuração um pouco mais complicada significa que podemos usar nossa chave privada (d) como a "semente" para a aleatoriedade. Isto nos permite simplesmente incrementar alguns bytes auxiliares (aux_rand) para criar um nonce privado (k') seguro o suficiente. Isto pode ser mais seguro do que tentar gerar um número aleatório em algumas situações.

5. Calcule o nonce público (R).

O próximo passo é produzir uma versão pública do nosso nonce privado (k') que será compartilhada como parte de nossa assinatura. Isto é conhecido como nonce público (R):

R = k' · G

Para criar este nonce público, usamos multiplicação de curva elíptica para multiplicar o ponto gerador (G) pelo nonce privado (k') calculado no passo anterior.

Conversor de Número

Conversor de Números

Converta um número entre bases diferentes (binário, decimal, hexadecimal).

Binário (Base 2)

0b

0 dígitos Decimal (Base 10)

0d

0 dígitos Hexadecimal (Base 16)

0x

0 dígitos +1

Multiplicação na Curva

Multiplicação de Ponto (EC Multiply)

Multiplique um ponto na curva elíptica secp256k1.

Ponto Gerador Ponto Aleatório

Ponto 1

x:

0d

y:

0d

Multiplicador

0d

+1 Aleatório

Ponto 1 × Multiplicador

x:

0d

y:

0d

Steps [mostrar]

Em termos técnicos:

• Converta o nonce privado (k') para um inteiro.
• Verifique se o nonce privado não é zero (é quase impossível que isto aconteça, mas você deve verificar mesmo assim).
• Multiplique o ponto gerador (G) pelo nonce privado (k').

Este passo é o mesmo que criar uma chave pública, exceto que estamos multiplicando o ponto gerador pelo nonce privado (k') em vez de uma chave privada (d').

6. Negue o nonce privado (k') se a coordenada y do nonce público (R[y]) for ímpar.

Se a coordenada y do nonce público resultante (R[y]) for par, mantenha o nonce privado (k') como está:

k = k'

Mas se a coordenada y for ímpar, negue o nonce privado (k') para que ele produza um ponto com a mesma coordenada x, mas com uma coordenada y par:

k = n - k'

Novamente, todos os pontos da curva elíptica no esquema de assinatura Schnorr do Bitcoin são assumidos como tendo coordenada y par, então usamos a versão do nonce privado (k') que produz um ponto com coordenada y par.

7. Calcule o desafio (e).

e = int(hashBIP0340/challenge(R[x] || P[x] || m)) % n

Hash Marcado

Tagged Hash

Cria um hash de dados com um prefixo de tag.
Usado em Schnorr sign, Schnorr verify e Taproot.

Exemplo aleatório

String

BIP0340/auxBIP0340/nonceBIP0340/challengeTapLeafTapBranchTapTweakTapSighash

Dados (Hex) 0 bytes

Resultado

SHA256(SHA256(string) || SHA256(string) || dados)

0 bytes

O desafio (e) é um hash marcado dos seguintes dados:

• R[x] = coordenada x do nonce público (do passo 5) convertida para bytes
• P[x] = coordenada x da chave pública (do passo 2) convertida para bytes
• m = mensagem (do passo 1)

Então convertemos o resultado deste hash para um inteiro e aplicamos módulo pelo número de pontos na curva elíptica (n).

8. Construa a assinatura.

A assinatura completa consiste em duas partes:

1. r = R[x]

Esta é apenas a coordenada x do nonce público (R).

Precisamos enviar isto ao verificador como parte de nossa assinatura para que ele possa construir o mesmo desafio (e) durante a verificação.

2. s = (k + e · d) % n

Esta é a parte "real" da assinatura que prova ao verificador que conhecemos a chave privada (d) para a chave pública (P).

• O nonce privado (k) é usado para ocultar nossa chave privada (d).
• O desafio (e) é necessário para provar ao verificador que não trapaceamos ao criar a assinatura.

Por último, convertemos ambos os valores r e s para 32 bytes hexadecimais e os concatenamos para criar nossa assinatura codificada completa de 64 bytes:

signature = (r, s)

Verificar

Assinatura Schnorr

Verificação Schnorr

Verifique uma assinatura para uma chave pública e mensagem.

Exemplo Aleatório Chave Pública (P[x])

0x

Aleatório

0 bytes Mensagem (m)

0x

Aleatório

0 bytes Assinatura (r, s)

0x

0 bytes

Detalhes [mostrar]

Chave Pública (P)

x:

0d

y:

0d

Assinatura

r:

0d

s:

0d

Ponto 1 = sG

x:

0d

y:

0d

Challenge (e) = int(hash_{BIP0340/challenge}(r ‖ P[x] ‖ m)) % n

0d

(n − e)

0d

Ponto 2 = (n−e)P

x:

0d

y:

0d

R = sG + (n−e)P

x:

0d

y:

0d

Verificação (r = R[x])

r:

0d

R[x]:

0d

# ---------
# Funções
# ---------

require "digest" # biblioteca para função hash SHA256

# converter string hexadecimal de bytes para inteiro
def int(bytes)
  return bytes.to_i(16)
end

# converter inteiro para string hexadecimal de bytes
def bytes(int)
  return int.to_s(16).rjust(64, "0")
end

# -----------
# Hash Marcado
# -----------

def tagged_hash(tag, message)
  tag_hash = Digest::SHA256.hexdigest(tag)
  preimage = [tag_hash + tag_hash + message].pack("H*")
  result = Digest::SHA256.hexdigest(preimage);
  return result
end

# ------
# Verificar
# ------
puts "Verificando:"

public_key = "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659"
message = "243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89"
sig = "6896bd60eeae296db48a229ff71dfe071bde413e6d43f917dc8dcf8c78de33418906d11ac976abccb20b091292bff4ea897efcb639ea871cfa95f6de339e4b0a"

puts " public key:  #{public_key}"
puts " message:     #{message}"
puts " signature:   #{sig}"

# converter chave pública (coordenada x apenas) em um ponto - lift_x() no BIP 340
x = int(public_key)
y_sq = (x**3 + 7) % $p
y = y_sq.pow(($p+1)/4, $p)

if x >= $p
  raise "x value in public key is not a valid coordinate because it is not less than the elliptic curve field size"
end

if (y**2) % $p != y_sq
  raise "public key is not a valid x coordinate on the curve"
end

if y % 2 != 0
  y = $p - y
end

public_key_point = {x: x, y: y}

# extrair o valor r da assinatura e converter para inteiro
r = sig[0..63] # primeiros 32 bytes (64 caracteres)

# extrair o valor s da assinatura e converter para inteiro
s = sig[64..-1] # últimos 32 bytes (64 caracteres)

if int(r) >= $p
  raise "r value in signature is not less than the elliptic curve field size"
end

if int(s) >= $n
  raise "s value in signature is not less than the number of points on the elliptic curve"
end

# criar o desafio e hasheando o ponto aleatório com a chave pública e mensagem (mesmo que durante a assinatura)
e = tagged_hash("BIP0340/challenge", r + bytes(x) + message).to_i(16) % $n

# criar um ponto na curva multiplicando o ponto gerador por s
point1 = multiply(int(s), $G)

# criar outro ponto na curva multiplicando o ponto da chave pública por e
point2 = multiply($n - e, public_key_point)

# somar estes pontos para calcular um terceiro ponto (R)
point3 = add(point1, point2)

if point3[:y] % 2 != 0
  raise "calculated R during signature verification has an odd y value (it should be even)"
end

puts "              ↓"
puts " result:      success" if point3[:x] == int(r)
puts " result:      fail" if point3[:x] != int(r)

Método

1. Obtenha os dados necessários para verificar.

Três dados são necessários para verificar uma assinatura:

• Chave Pública (P[x]) — Esta é a chave pública para a chave privada que criou a assinatura. Esta chave pública é apenas a coordenada x de 32 bytes.
• Mensagem (m) — A mensagem que foi assinada. Geralmente é um hash de 32 bytes de dados de uma transação.
• Assinatura ((r, s)) — Esta assinatura de 64 bytes contém duas partes; a parte aleatória de 32 bytes (r) e a parte da assinatura de 32 bytes (s).

2. Converta a chave pública (P[x]) para um ponto.

Para realizar a etapa final de verificação, precisamos converter a chave pública codificada de volta para um ponto.

Porém, a chave pública (P[x]) que recebemos é apenas uma coordenada x. Portanto, precisamos calcular a coordenada y a partir dela para convertê-la de volta a um ponto.

1. Calculando a coordenada y.

Para começar, podemos encontrar o valor de y² inserindo x na equação da curva elíptica:

y² = x³ + 7

Então agora só precisamos encontrar a raiz quadrada de y² para obter y.

Porém, não é realmente possível "tirar a raiz quadrada" deste valor diretamente quando se trabalha com coordenadas na curva elíptica. Felizmente, os parâmetros Secp256k1 foram escolhidos de forma especial para que a raiz quadrada possa ser encontrada usando esta equação:

y = (y²)^((p+1)/4) % p

Nota: Eu não sei por que isto funciona. Só sei que funciona e que é muito útil.

E isto nos dá a coordenada y.

2. Selecione a coordenada y par.

Por último, como encontramos a raiz quadrada de um número, o resultado pode ser um de dois valores possíveis.

Na matemática cotidiana, a raiz quadrada de um número será positiva ou negativa. Mas na matemática de curva elíptica, esta coordenada y será par ou ímpar.

E lembre-se: só trabalhamos com coordenadas y pares para assinaturas Schnorr no Bitcoin. Então, se a coordenada y for ímpar, precisamos negá-la para obter o valor y par correspondente:

y = p - y

Isto nos dá a coordenada y par para a mesma coordenada x.

Agora temos ambas as coordenadas x e y que compõem o ponto completo da chave pública (P).

Ao negar uma coordenada y você a subtrai do tamanho do corpo p (veja os parâmetros). Isto é diferente do passo 3 da assinatura onde negamos o escalar d' subtraindo-o do número de pontos na curva (n).

Verifique se a coordenada x é válida antes de continuar:

• Verifique se x é menor que o tamanho do corpo (p).
• Verifique se o valor y calculado é igual a y² quando você o eleva ao quadrado. Se não for, a coordenada x era inválida desde o início.

Se alguma destas coisas não for verdade, a chave pública (P[x]) dada é inválida.

Este passo inteiro é conhecido como lift_x no BIP 340.

3. Extraia os valores r e s da assinatura.

A assinatura de 64 bytes é composta de duas partes:

• r (primeiros 32 bytes) — Este é R[x], que é a coordenada x do nonce público (R) gerado durante a assinatura. Ao verificar a assinatura, vamos conferir se conseguimos recriar este mesmo ponto.
• s (últimos 32 bytes) — Esta é a parte real da assinatura. É o valor "mágico" que prova que a pessoa que criou este valor s possui a chave privada para a chave pública fornecida.

Execute algumas verificações nestes dados de assinatura antes de continuar:

• Verifique se o valor r é menor que o tamanho do corpo (p).
• Verifique se o valor s é menor que o número de pontos na curva (n).

Se alguma destas coisas não for verdade, a assinatura é inválida.

4. Calcule o desafio (e).

e = int(hashBIP0340/challenge(r || P[x] || m)) % n

Hash Marcado

Tagged Hash

Cria um hash de dados com um prefixo de tag.
Usado em Schnorr sign, Schnorr verify e Taproot.

Exemplo aleatório

String

BIP0340/auxBIP0340/nonceBIP0340/challengeTapLeafTapBranchTapTweakTapSighash

Dados (Hex) 0 bytes

Resultado

SHA256(SHA256(string) || SHA256(string) || dados)

0 bytes

O desafio (e) é um hash marcado dos seguintes dados:

• r = Este é o valor R[x] que acabamos de extrair da assinatura (do passo anterior)
• P[x] = coordenada x da chave pública (do passo 1)
• m = mensagem (do passo 1)

Então convertemos este hash para um inteiro e aplicamos módulo pelo número de pontos na curva elíptica.

Você notará que este desafio (e) é o mesmo que o criado durante a assinatura. Isto porque tanto o assinante quanto o verificador precisam ser capazes de calcular o mesmo desafio de forma independente.

5. Verifique a assinatura.

Agora temos tudo que precisamos para verificar esta assinatura.

A verificação da assinatura é feita calculando três pontos na curva elíptica. Estes pontos são calculados usando multiplicação e adição de curva elíptica:

Ponto 1

point1 = s · G

O primeiro ponto é o valor s da assinatura multiplicado pelo ponto gerador (G).

Ponto 2

point2 = (n - e) · P

O segundo ponto é o desafio (e) multiplicado pela chave pública completa (P) que construímos no passo 2.

Porém, como o próximo ponto será calculado subtraindo este segundo ponto do primeiro, precisamos negar este escalar (e) subtraindo-o do número de pontos na curva (n).

Ao usar (n - e) · P em vez de e · P, o resultado da adição de curva elíptica no próximo passo será equivalente a uma subtração.

Ponto 3

point3 = s · G + (n - e) · P

O terceiro ponto (R) é calculado somando o ponto 1 e o ponto 2.

Isto é um rearranjo da equação de verificação original s · G = R + e · P:

1. s · G = R + e · P
2. R = s · G - e · P
3. R = s · G + (n - e) · P

Finalmente, verificamos se a coordenada x do ponto 3 (R) é igual ao valor r da assinatura:

r == R[x]

Se estes valores forem iguais, a assinatura é válida.

Se estes valores forem diferentes, a assinatura é inválida.

O valor r na assinatura é a coordenada x do ponto público aleatório escolhido pelo assinante. Só conseguiríamos calcular o mesmo valor de R[x] se eles forem capazes de nos fornecer um valor s válido em sua assinatura (em conjunto com a chave pública e a mensagem) para conseguir recriá-lo.

Verificação em Lote

O legal das assinaturas Schnorr é que você pode verificar várias assinaturas ao mesmo tempo.

Isto é conhecido como verificação em lote, e é mais rápido do que verificar cada assinatura individualmente.

# ---------
# Funções
# ---------

require "digest" # biblioteca para função hash SHA256

# converter string hexadecimal de bytes para inteiro
def int(bytes)
  return bytes.to_i(16)
end

# converter inteiro para string hexadecimal de bytes
def bytes(int)
  return int.to_s(16).rjust(64, "0")
end

# Hash Marcado (Tagged Hash)
def tagged_hash(tag, message)
  tag_hash = Digest::SHA256.hexdigest(tag)
  preimage = [tag_hash + tag_hash + message].pack("H*")
  result = Digest::SHA256.hexdigest(preimage);
  return result
end

# converter coordenada x para um ponto (com valor y par)
def lift_x(x)
  x = int(x)
  y_sq = (x**3 + 7) % $p
  y = y_sq.pow(($p+1)/4, $p)

  if x >= $p
    raise "x value in public key is not a valid coordinate because it is not less than the elliptic curve field size"
  end

  if (y**2) % $p != y_sq
    raise "public key is not a valid x coordinate on the curve"
  end

  if y % 2 != 0
    y = $p - y
  end

  return {x: x, y: y}
end

# ------------
# Verificação em Lote
# ------------

# dados para verificação em lote
signatures = [
  {public_key: '9abfac866a8fdd9b50cdf68b16f9861652f16ac6113949f4a5d4f6c57c192db2', message: '26e906314b0215b9035de37a6da02dc43fa60939eade2992058c4fdb4d43f845', signature: '5db322e0dd3718cc3a3f8fa21aa899fb1bebae4506c8fed6e9305e2f834202780c77078e3aef618275501df3caf1ab6cc45b0d102712e08b67b8545589347046'},
  {public_key: '1bdf2f729a6dde85b479e02430c311f7a5a409d6d147d4075f6d58f073a7a6d6', message: 'a8514d48b2b07a5e00ff844437e65d4a02d43fd6de85b7814a841cade6a904ac', signature: 'a61206a5dcaa820de0a382879c3f58298b2d28bee9a99ba3a04882b342a7470aa12e6e3d2f5af9a71d6c996f359fcdeae9810f06c1fe179410280294a88017ea'},
  {public_key: '691d8375c0965e72b70fdfe8e13613ff47405f3d0834c723d374c12c6a493742', message: 'c28a737f65457b54d8e7dfe49f45cf7adf20c97457f797b444cb98247bfea36d', signature: '8821b6b62a399555f23114904376c7916ac5bbbdb3105c6f97054d0fcc75ff7cd1d48e3572a130ea6b487cf60a9a7fbc4ccfb51003ca8a14b044da7d06267ac3'},
]

u = signatures.length

# ---
# Passo 1 - Gere um número aleatório para cada assinatura (exceto para a primeira)
# ---

# combinar as chaves públicas, mensagens e assinaturas
public_keys_combined = ""
messages_combined = ""
signatures_combined = ""

signatures.each do |x|
  public_keys_combined << x[:public_key]
  messages_combined << x[:message]
  signatures_combined << x[:signature]
end

# criar uma semente inicial para usar com a função hash
seed = Digest::SHA256.hexdigest([public_keys_combined + messages_combined + signatures_combined].pack("H*"))

# array para armazenar os números aleatórios
a = []

(1..u-1).each do |i|
  # gerar um número aleatório hasheando a semente com o índice
  random_number = Digest::SHA256.hexdigest(seed + i.to_s).to_i(16)

  unless (1..$n-1).include?(random_number)
    raise "random number (a) must be in the range 1..n-1"
  end

  a[i] = random_number
end

# ---
# Passo 2 - Calcule o lado esquerdo da equação
# ---
# left = (s_1 + (a_2 * s_2) + ... + (a_u * s_u)) * G

s_0 = signatures[0][:signature][64..-1].to_i(16)
left_scalar = s_0

(1..u-1).each do |i|
  s_i = signatures[i][:signature][64..-1].to_i(16)
  left_scalar += s_i * a[i]
end

left = multiply(left_scalar, $G)

# ---
# Passo 3 - Calcule o lado direito da equação
# ---
# right = [R_1 + (a_2 * R_2) + .. + (a_u * R_u)] + [(e_1 * P_1) + (a_2 * e_2 * P_2) + ... + (a_u * e_u * P_u)]

r_0 = signatures[0][:signature][0..63]
message_0 = signatures[0][:message]
public_key_0 = signatures[0][:public_key]

r_0_point = lift_x(r_0)

right = r_0_point

public_key_0_point = lift_x(public_key_0)

e_0 = tagged_hash("BIP0340/challenge", r_0 + public_key_0 + message_0).to_i(16) % $n

eP_0 = multiply(e_0, public_key_0_point)

right = add(right, eP_0)

(1..u-1).each do |i|
  r_i = signatures[i][:signature][0..63]
  message_i = signatures[i][:message]
  public_key_i = signatures[i][:public_key]

  r_i_point = lift_x(r_i)

  aR_i = multiply(a[i], r_i_point)

  right = add(right, aR_i)

  public_key_i_point = lift_x(public_key_i)

  e_i = tagged_hash("BIP0340/challenge", r_i + public_key_i + message_i).to_i(16) % $n

  ae_i = e_i * a[i]

  aeP_i = multiply(ae_i, public_key_i_point)

  right = add(right, aeP_i)
end

# ---
# Passo 4 - Verifique
# ---

puts left == right

Método

A verificação em lote usa a mesma equação fundamental da verificação de uma única assinatura:

A única diferença é que nós a expandimos (incluindo alguma multiplicação extra com números aleatórios) para que possamos verificar várias assinaturas ao mesmo tempo:

Mas não se preocupe, parece mais complicado do que realmente é.

1. Obtenha todos os dados necessários para a verificação em lote.

Para verificar várias assinaturas ao mesmo tempo, você precisa começar com alguns "trios" de assinatura.

Por exemplo:

• tripleta0 = (chave pública, mensagem, assinatura)
• tripleta1 = (chave pública, mensagem, assinatura)
• tripleta2 = (chave pública, mensagem, assinatura)

Como você pode ver, cada tripleta contém os mesmos dados necessários para a verificação de uma única assinatura.

Já que podemos ter um número variável de assinaturas, é útil definir algumas variáveis extras:

• i — O número de cada tripleta de assinatura (ex.: i=0 para a primeira)
• u — O número total de tripletas de assinatura (ex.: u=3 neste exemplo)

2. Gere um número aleatório (ai) para cada tripleta.

Começamos gerando um número aleatório para cada tripleta.

A forma recomendada de gerar estes números aleatórios é começar criando uma "semente" inicial (veja o BIP 340). Esta semente é o hash SHA-256 das chaves públicas, mensagens e assinaturas de cada uma das tripletas concatenadas:

semente = SHA-256(chaves públicas || mensagens || assinaturas)

Então usamos esta semente como ponto de partida para gerar todos os números aleatórios de que precisamos.

Por exemplo, uma forma simples de criar cada número aleatório é hashear esta semente com o número do índice (i) para cada tripleta. Isto produzirá um hash único, que convertemos para um inteiro e usamos como o número aleatório para cada tripleta:

ai = int(SHA-256(semente || i))

Não precisamos de um número aleatório para a primeira tripleta.

3. Execute a verificação em lote.

aka "desenhe o resto da coruja"

A equação de verificação em lote se parece com isto:

(s1 + a2s2 + .. au+su)G = (R1 + a2R2 + .. auRu) + (e1P1 + a2e2P2 + .. aueuPu)

Parece complexo, mas podemos dividir em três passos:

1. Calcule o lado esquerdo da equação.

(s1 + a2s2 + .. au+su)G

Para cada tripleta, multiplique o valor s da assinatura pelo seu número aleatório a.

Então some todos estes valores, e multiplique o resultado pelo ponto gerador (G).

Este passo é o mesmo que s·G na verificação de assinatura única. Exceto que aqui estamos multiplicando cada valor s por a e então somando todos primeiro.

2. Calcule o lado direito da equação

(R1 + a2R2 + .. auRu) + (e1P1 + a2e2P2 + .. + aueuPu)

Para cada tripleta calculamos dois pontos:

1. aiRi
   • R é o valor r da assinatura convertido para um ponto.
   • Não multiplicamos R1 por um número aleatório.
2. aieiPi
   • P é a chave pública convertida para um ponto.
   • O desafio e é calculado para cada tripleta da mesma forma que na verificação de assinatura única (passo 4).
   • Não multiplicamos e1P1 por um número aleatório.

Então somamos todos estes pontos, e isto nos dá o lado direito da equação.

Este passo é o mesmo que R + e·P na verificação de assinatura única. Exceto que aqui estamos multiplicando cada termo por a e então somando todos primeiro.

3. Verifique se o lado esquerdo é igual ao lado direito da equação.

Se ambos os lados da equação forem iguais, então todas as assinaturas são válidas.

Se ambos os lados da equação forem diferentes, então uma ou mais das assinaturas são inválidas.

É tecnicamente possível que os números aleatórios gerados criem uma equação equilibrada, mesmo que uma ou mais assinaturas sejam inválidas. Porém, a probabilidade disto acontecer é "desprezível". Em outras palavras, é perto demais de impossível para ser uma preocupação.

De onde vem esta equação?

A equação de verificação para uma única assinatura se parece com isto:

Então, se você tem duas assinaturas, pode combiná-las e verificá-las ao mesmo tempo assim:

Portanto, uma equação geral para combinar e verificar várias assinaturas ao mesmo tempo se parece com isto (onde u é o número total de assinaturas):

Porém, esta equação não é completamente segura, pois é possível construir uma assinatura que equilibre a equação para uma assinatura inválida. Então, para evitar que isto aconteça, multiplicamos cada equação de verificação individual pelo seu próprio número aleatório (que chamamos de a). Então a equação agora se parece com isto:

Por último, não precisamos multiplicar a primeira equação de verificação por um número aleatório, então simplesmente a deixamos de fora:

E é daí que vem esta equação de verificação em lote.

Esta equação aproveita o fato de que assinaturas Schnorr podem ser somadas (veja linearidade).

No diagrama de verificação em lote acima, reorganizei a equação para ficar assim:

(s1 + a2s2 + .. au+su)G = (R1 + e1P1) + (a2R2 + a2e2P2) + .. + (auRu + aueuPu)

Ambas as equações são a mesma; apenas reorganizei o lado direito para tornar o diagrama mais fácil de seguir.

Design

Como as assinaturas Schnorr são implementadas no Bitcoin?

A implementação das assinaturas Schnorr no Bitcoin inclui algumas modificações em relação ao esquema básico de assinatura Schnorr.

São ajustes menores específicos do Bitcoin; a matemática subjacente continua a mesma.

1. Codificação de Chave Pública
2. Prefixo de Chave
3. Hashes Marcados
4. Geração de Nonce
5. Codificação de Assinatura

Não sei o suficiente sobre criptografia para explicar os detalhes técnicos por trás de cada decisão de projeto na implementação das assinaturas Schnorr no Bitcoin, então vou dar uma visão geral simples de por que elas são implementadas dessa forma.

1. Codificação de Chave Pública

Ao usar assinaturas Schnorr no Bitcoin, uma chave pública é codificada como apenas a coordenada x de 32 bytes.

Isto economiza espaço em comparação com chaves públicas comprimidas de 33 bytes ou chaves públicas descomprimidas de 65 bytes.

O motivo é que não precisamos realmente da coordenada y, pois para qualquer coordenada x dada existem apenas duas coordenadas y possíveis:

1. Uma coordenada y par
2. Uma coordenada y ímpar

E ao reconstruir a chave pública completa, sempre usamos a coordenada y par das duas.

Portanto, para qualquer coordenada x de chave pública, usamos a equação da curva elíptica (y² = x³ + 7) para descobrir as duas coordenadas y potenciais, então selecionamos a par para nos dar as coordenadas (x, y) completas da chave pública.

# -------------------------
# Parâmetros da Curva Elíptica
# -------------------------

# corpo primo
$p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

# ---------
# Funções
# ---------

# converter string hexadecimal de bytes para inteiro
def int(bytes)
  return bytes.to_i(16)
end

# ---------------------------------
# Descomprimir Chave Pública (lift_x)
# ---------------------------------

# chave pública codificada (coordenada x de 32 bytes)
public_key = "dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659"

# calcular um dos possíveis valores y a partir da coordenada x
x = int(public_key)
y_sq = (x**3 + 7) % $p
y = y_sq.pow(($p+1)/4, $p)

# verificar se a coordenada x é menor que o tamanho do corpo
if x >= $p
  raise "x value in public key is not a valid coordinate because it is not less than the elliptic curve field size"
end

# verificar se o valor y calculado é a raiz quadrada de y_sq (caso contrário, a chave pública não era uma coordenada x válida na curva)
if (y**2) % $p != y_sq
  raise "public key is not a valid x coordinate on the curve"
end

# mostrar o valor atual de x e y (este valor y é ímpar, mas às vezes já será par)
puts "x: #{x}" #=> 101293062680523315514373137351023114440902235251657644508821325047911886333529
puts "y: #{y}" #=> 95491709537915294920828256998521669146617750390665870859237534620269297521559

# se o valor y calculado for ímpar, negue-o para obter o valor y par (para esta coordenada x)
if y % 2 != 0
  y = $p - y
end

# mostrar o valor y par
puts "y: #{y}" #=> 20300379699400900502742728010166238706652234274974693180220049387639537150104

Isto não torna o esquema de assinatura menos seguro?

Como estamos usando apenas a coordenada y par para cada chave pública, isto significa que duas chaves privadas diferentes produzirão a mesma chave pública codificada.

Por exemplo:

private_key_1 = b7e151628aed2a6abf7158809cf4f3c762e7160f38b4da56a784d9045190cfef
private_key_2 = 481eae9d7512d595408ea77f630b0c3757c7c6d77693c5e5184d85887ea57152

private_key_1_encoded_public_key = dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659
private_key_2_encoded_public_key = dff1d77f2a671c5f36183726db2341be58feae1da2deced843240f7b502ba659

Chave Pública

Chave Pública

Calcule a chave pública a partir de uma chave privada.

Gerar aleatória Chave Privada 0 bytes

Chave Pública

Coordenadas

x:

0d

y:

0d

Uma chave pública é apenas um ponto em uma curva elíptica. A chave pública final são essas coordenadas em hexadecimal.

Compressão

Comprimida (prefixo 02/03) Não comprimida (prefixo 04) x-only (sem prefixo)

A curva é simétrica no eixo x, então a chave comprimida guarda só a coordenada x e se o y é par ou ímpar. A x-only é usada em saídas Taproot.

Chave pública serializada 0 bytes

Nunca digite sua chave privada em um site, nem use uma chave privada gerada por um site. Sites podem facilmente salvar a chave privada e usá-la para roubar seus bitcoins.

A segunda chave privada neste exemplo é o inverso aditivo da primeira chave privada (ou seja, eu a neguei subtraindo-a do número de pontos na curva). Esta chave privada "invertida" produz exatamente a mesma coordenada x para a chave pública, mas com a coordenada y oposta.

Porém, surpreendentemente, o fato de duas chaves privadas produzirem a mesma chave pública não enfraquece a segurança das assinaturas Schnorr no Bitcoin.

2. Prefixo de Chave

No esquema de assinatura Schnorr padrão, o desafio (e) é criado hasheando o nonce público (kG) com a mensagem (m):

Porém, no Bitcoin este hash também inclui a coordenada x da chave pública (Px):

Isto é chamado de prefixo de chave (key-prefixing), e está incluído para prevenir ataques ao gerar assinaturas a partir de chaves públicas não endurecidas em uma carteira HD.

Este prefixo de chave também é usado ao gerar o nonce privado.

3. Hashes Marcados

Hash Marcado

Tagged Hash

Cria um hash de dados com um prefixo de tag.
Usado em Schnorr sign, Schnorr verify e Taproot.

Exemplo aleatório

String

BIP0340/auxBIP0340/nonceBIP0340/challengeTapLeafTapBranchTapTweakTapSighash

Dados (Hex) 0 bytes

Resultado

SHA256(SHA256(string) || SHA256(string) || dados)

0 bytes

Um hash marcado (tagged hash) é o hash de alguns dados com um prefixo de marcação adicional. Este método de hash foi introduzido como parte da implementação das assinaturas Schnorr no Bitcoin.

Isto dá a cada hash um contexto, então se você hashear os mesmos dados em um contexto diferente, você não obteria o mesmo resultado de hash.

Criar um hash marcado no Bitcoin é bem simples:

1. Faça o hash de uma string (a marcação) que descreve o contexto para o hash final.
2. Faça o hash dos dados com este hash da marcação (prefixando o hash da marcação duas vezes).

# -----------
# Hash Marcado
# -----------
require "digest" # biblioteca para função hash SHA256

# aplicar hash em alguns dados usando SHA256 com um prefixo de marcação
def tagged_hash(tag, message)

  # criar um hash da marcação primeiro
  tag_hash = Digest::SHA256.hexdigest(tag) # aplicar hash na string diretamente

  # prefixar a mensagem com o hash da marcação (o tag_hash é prefixado duas vezes para que o prefixo tenha 64 bytes no total)
  preimage = [tag_hash + tag_hash + message].pack("H*") # também converter para sequência de bytes antes de hashear

  # SHA256(tag_hash || tag_hash || message)
  result = Digest::SHA256.hexdigest(preimage);

  return result
end

tag = SHA256(string) || SHA256(string)
tagged_hash = SHA256(tag || data)

4. Geração de Nonce

Toda assinatura que você cria precisa incluir um nonce aleatório (k).

Na maioria dos esquemas de assinatura (ex.: ECDSA), este nonce é apenas um número gerado aleatoriamente. Mas na implementação das assinaturas Schnorr no Bitcoin, usamos um método específico para gerar cada nonce.

Em resumo:

1. A chave privada (d) é usada como a "semente" inicial.
2. Esta chave privada é combinada via XOR com o hash marcado de alguns bytes auxiliares (aux_rand_hash) para criar uma chave privada modificada (t).
3. O nonce aleatório (k) é então o hash marcado da chave privada modificada (t), chave pública (Px) e mensagem (m).

Este esquema para gerar o nonce faz a implementação da assinatura Schnorr parecer muito mais intimidante do que realmente é. No entanto, a parte de geração do nonce foi projetada desta forma para torná-la mais segura (porque você não precisa depender de sua fonte de aleatoriedade ser confiável), enquanto também protege contra tipos específicos de ataques.

Não sei o suficiente sobre criptografia para explicar as razões por trás deste design específico, então aqui estão alguns links que você pode achar úteis:

• k selection for Schnorr signatures — Primeiras explicações das razões por trás do esquema.
• [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340 — Resumo das razões por trás do esquema.
• Discussion on power analysis attacks — Isto contém o processo de pensamento por trás do esquema de geração de nonce.

Em resumo, pode parecer complexo, mas foi projetado desta forma por uma razão.

5. Codificação de Assinatura

Uma assinatura Schnorr é codificada concatenando o valor r de 32 bytes e o valor s de 32 bytes.

Portanto, uma assinatura Schnorr tem sempre 64 bytes de comprimento.

Codificação de Assinatura Schnorr vs. ECDSA

Para assinaturas ECDSA, os valores equivalentes de r e s são envolvidos dentro da codificação DER:

Esta codificação DER resulta em assinaturas que variam entre 70-72 bytes de comprimento.

Usar codificação DER para assinaturas sempre foi ineficiente porque os valores r e s têm sempre o mesmo tamanho, então os campos adicionais de tipo e tamanho usados no DER eram uma sobrecarga desnecessária. É por isso que a eliminamos para assinaturas Schnorr.

Como resultado, esta redução de pelo menos 6 bytes por assinatura economizará uma quantidade significativa de espaço na blockchain ao longo do tempo.

Satoshi provavelmente usou codificação DER porque era o método padrão para codificar assinaturas na biblioteca OpenSSL que ele estava usando na época. O fato de ser ineficiente foi provavelmente um descuido.

Benefícios

Quais são os benefícios das assinaturas Schnorr?

Há uma série de benefícios em usar assinaturas Schnorr em comparação com o ECDSA:

1. Simplicidade
2. Eficiência
3. Segurança
4. Linearidade
5. Não-maleabilidade

1. Simplicidade

O esquema de assinatura Schnorr é matematicamente mais simples que o ECDSA.

Esta é a equação para criar uma assinatura Schnorr:

Esta é a equação para criar uma assinatura ECDSA:

De um ponto de vista matemático, as assinaturas Schnorr são mais lógicas e mais elegantes.

De um ponto de vista prático, elas também são comprovadamente seguras e mais eficientes. Melhor ainda, a equação da assinatura Schnorr é linear, o que significa que você pode somar assinaturas (o que não é possível com ECDSA).

2. Eficiência

A equação para criar uma assinatura Schnorr usa apenas adição e multiplicação aritméticas:

Por outro lado, a equação para criar uma assinatura no ECDSA inclui multiplicação de curva elíptica e inverso modular:

Portanto, as assinaturas Schnorr são matematicamente mais eficientes e, consequentemente, mais rápidas de calcular.

Claro, nem a multiplicação de curva elíptica nem as operações de inverso modular usadas no ECDSA são exatamente lentas em um computador moderno. Mas não precisar realizar estas operações ao criar uma assinatura Schnorr proporciona um ganho de eficiência mesmo assim.

Outro benefício de eficiência das assinaturas Schnorr é que você pode verificar várias assinaturas ao mesmo tempo usando verificação em lote. Enquanto com ECDSA você só pode verificar assinaturas individualmente.

3. Segurança

A simplicidade da equação da assinatura Schnorr também significa que ela é comprovadamente segura.

Em outras palavras, existe uma prova matemática que mostra que as assinaturas Schnorr não podem ser quebradas a menos que você consiga resolver o problema do logaritmo discreto.

Em contraste, a complexidade da equação para criar assinaturas no ECDSA significa que não há prova formal de que seja segura. Isto se deve à inclusão da parte de multiplicação de curva elíptica, que torna difícil formar uma prova:

Existe uma forte suposição de que o ECDSA é seguro, mas não há uma prova real. Portanto, ter uma prova real de segurança é outra vitória para as assinaturas Schnorr.

ak mod p = b

3k mod 17 = 6

31 mod 17 = 3
32 mod 17 = 9
33 mod 17 = 10
34 mod 17 = 13
35 mod 17 = 5
36 mod 17 = 15
37 mod 17 = 11
38 mod 17 = 16
39 mod 17 = 14
310 mod 17 = 8
311 mod 17 = 7
312 mod 17 = 4
313 mod 17 = 12
314 mod 17 = 2
315 mod 17 = 6    <- encontrou a resposta

71916331368884415102528573409726749875552388602224548694948731024252851890102k mod 115792089237316195423570985008687907853269984665640564039457584007908834671663 = 11790564026517817731571347968670053249854067159256829888660539131158964346271

k = 93350855816723809765951314891371850338090431368773987746149549196975035370474

4. Linearidade

As assinaturas Schnorr são lineares, enquanto as assinaturas ECDSA não são:

Isto significa que você pode somar assinaturas Schnorr, algo que não é possível com assinaturas ECDSA.

Por exemplo, você pode somar chaves públicas tanto em Schnorr quanto em ECDSA:

Mas você só pode somar assinaturas em Schnorr (devido ao fato de serem lineares):

Esta capacidade de somar assinaturas Schnorr permite fazer coisas úteis como verificação em lote e construir scripts de bloqueio multifirma eficientes.

Exemplo Básico de Multisig

O fato de você poder somar assinaturas Schnorr significa que você pode produzir uma única assinatura que é válida para a soma de múltiplas chaves públicas.

Por exemplo, no script de bloqueio legado P2MS (que usa ECDSA), você tem que fornecer cada chave pública individual no script de bloqueio. E para desbloqueá-lo, você precisa fornecer uma assinatura para cada uma dessas chaves públicas.

Mas com assinaturas Schnorr, você pode somar todas as chaves públicas para criar uma "soma de chaves públicas" e colocar isso no script de bloqueio. Para desbloqueá-lo, você pode então criar uma assinatura para cada uma dessas chaves públicas, depois somá-las e colocar uma única "soma de assinaturas" no script de desbloqueio:

Isto proporciona dois grandes benefícios.

1. Espaço — Agora você só precisa fornecer uma única chave pública (32 bytes) e uma única assinatura (64 bytes) em vez de múltiplas de cada.
2. Velocidade — Agora você só precisa realizar uma única verificação de assinatura em vez de múltiplas.

Este é um exemplo simples usado para ilustrar como scripts multifirma podem funcionar usando assinaturas Schnorr. No entanto, este design básico é vulnerável a um ataque de "cancelamento de chave", então requer alguns ajustes adicionais para torná-lo completamente seguro para uso em transações Bitcoin (veja Musig). No entanto, a matemática subjacente funciona da mesma forma.

5. Não-maleabilidade

As assinaturas Schnorr são não-maleáveis, enquanto as assinaturas ECDSA são maleáveis.

• Maleável — Você pode fazer um ajuste em uma assinatura e ela ainda será válida.
• Não-maleável — Você não pode fazer nenhuma alteração em uma assinatura sem torná-la inválida.

Portanto, a não-maleabilidade é preferível.

A maleabilidade de assinatura tem sido um incômodo na história do Bitcoin, pois significava que TXIDs poderiam ser ajustados depois que você enviasse uma transação para a rede. Por exemplo, um minerador poderia pegar sua transação, negar o valor s em uma das assinaturas, e o TXID acabaria sendo diferente.

Esta "maleabilidade de transação" não era um grande problema, pois a transação ainda seria minerada e as moedas seriam enviadas para o mesmo lugar. Apenas significava que TXIDs não eram 100% confiáveis, então você não poderia construir aplicações sobre o Bitcoin que dependessem do TXID de uma transação permanecer o mesmo depois de enviá-la para a rede.

A maleabilidade de transação no Bitcoin foi amplamente "corrigida" através do BIP 62 (usando apenas o valor s baixo) e do Segwit (assinaturas não influenciam mais o TXID), mas a maleabilidade subjacente ainda existe no ECDSA.

Se as assinaturas Schnorr tivessem sido usadas no Bitcoin desde o início, a maleabilidade de transação nunca teria sido um problema.

Exemplo de Maleabilidade ECDSA vs. Schnorr

No ECDSA você pode usar o inverso aditivo do valor s da assinatura (n - s) e a assinatura ainda será válida:

Exemplo de Maleabilidade de Assinatura ECDSA (funciona):

# n é o número de pontos na curva elíptica (Secp256k1)
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

message = ef5a8f37fccf71096afd9a11a2da2b446d8b33689f4d20e26c638f4a989531fe

assinatura
r = 66877274282749947925738202103737060826792639332019467521650159742093834512161
s = 52838996486501912417250039507174624042914096621748978414744411801275148621923

assinatura (maleada)
r = 66877274282749947925738202103737060826792639332019467521650159742093834512161
n - s = 62953092750814283006320945501513283809923467657325925967860751340243012872414

chave pública = 03f8598d649e50f593c7fa78fa279e77deb5551e0983a06fecacbe4642f8e2aa49

Verificar ECDSA

Verificação ECDSA

Verifique uma assinatura usando o hash de uma mensagem e uma chave pública.

Exemplo Aleatório Hash da Mensagem (z)

0x

0 bytes

Assinatura

R:

0d

S:

0d

Chave Pública (Q)

0x

0 bytes

Verificação da Assinatura

x:

0d

y:

0d

Porém, se você tentar isto com uma assinatura Schnorr, o valor s negado (n - s) não será mais uma assinatura válida:

Exemplo de Maleabilidade de Assinatura Schnorr (não funciona):

# n é o número de pontos na curva elíptica (Secp256k1)
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

chave pública = f8598d649e50f593c7fa78fa279e77deb5551e0983a06fecacbe4642f8e2aa49
message = ef5a8f37fccf71096afd9a11a2da2b446d8b33689f4d20e26c638f4a989531fe

assinatura:
r = 114044020606335199196415233777177936773828372395311453975809869274310626581346
s = 68385771140937257490418462830158146547018738395060108953065794598947526976254
sig = fc22a0d2d248490485a4d47bf85de155477068ad3fc8ba25e44e306c9ca91b629730f98d5acb8b510cdf78c3a710ddfd79e7445f3e1b6f8031371d2ab442a2fe

assinatura (maleada):
r = 114044020606335199196415233777177936773828372395311453975809869274310626581346
n - s = 47406318096378937933152522178529761305818825884014795429539368542570634518083
sig = fc22a0d2d248490485a4d47bf85de155477068ad3fc8ba25e44e306c9ca91b6268cf0672a53474aef320873c58ef220140c79887712d30bb8e9b41621bf39e43

Verificar Schnorr

Verificação Schnorr

Verifique uma assinatura para uma chave pública e mensagem.

Exemplo Aleatório Chave Pública (P[x])

0x

Aleatório

0 bytes Mensagem (m)

0x

Aleatório

0 bytes Assinatura (r, s)

0x

0 bytes

Detalhes [mostrar]

Chave Pública (P)

x:

0d

y:

0d

Assinatura

r:

0d

s:

0d

Ponto 1 = sG

x:

0d

y:

0d

Challenge (e) = int(hash_{BIP0340/challenge}(r ‖ P[x] ‖ m)) % n

0d

(n − e)

0d

Ponto 2 = (n−e)P

x:

0d

y:

0d

R = sG + (n−e)P

x:

0d

y:

0d

Verificação (r = R[x])

r:

0d

R[x]:

0d

Conceitos Básicos

Como funcionam as assinaturas Schnorr?

Suponho que seria uma boa ideia explicar como funcionam as assinaturas Schnorr, e de onde vêm essas equações de criação e verificação:

Vou começar com o básico e evoluir.

1. Chaves

Primeiramente, para poder criar uma assinatura digital preciso gerar um par de chaves:

• Chave Privada (d) — Um número gerado aleatoriamente que mantenho em segredo.
• Chave Pública (dG) — Minha chave privada (d) multiplicada por outro número (G).

Nós dois concordamos com o número G de antemão. Então d é secreto, mas G não é.

Agora, mesmo que eu tenha "multiplicado" minha chave privada (d) pelo número G, vamos supor que não é realmente possível "dividir" a chave pública (dG) por G para voltar à chave privada (d). Eu sei que é possível com matemática básica, mas digamos que estamos usando um tipo especial de multiplicação que funciona da mesma forma que a multiplicação normal, mas não tem uma operação inversa de "divisão".

E confie em mim, esta operação especial de "multiplicação" realmente existe em criptografia (vou cobrir isso em um momento).

De qualquer forma, como usei esta operação especial de "multiplicação", posso realmente lhe dar minha chave pública (dG), e você não será capaz de descobrir qual é minha chave privada (d).

Este conjunto de chaves (e a operação especial de "multiplicação") é o ponto de partida para criar uma assinatura digital.

Objetivo

Meu objetivo é provar a você que tenho a chave privada (d) usada para criar a chave pública (dG), sem ter que revelar a chave privada em si.

Esta prova será chamada de minha assinatura digital (s).

2. Nonce

Antes de criar uma assinatura digital, preciso gerar um número aleatório de uso único chamado nonce (k).

Este nonce é usado para me ajudar a esconder minha chave privada, pois eu o adiciono à minha chave privada ao criar minha assinatura.

De qualquer forma, para que você possa verificar a assinatura, você precisará ter alguma informação sobre este nonce (k) também, mas não quero revelá-lo diretamente a você. Então multiplico meu nonce privado (k) pelo número G para criar um nonce público (kG).

Eu envio a você este nonce público (kG), e como usei a mesma função especial de "multiplicação" de antes, você não consegue retroceder a partir dele para descobrir qual é meu nonce privado (k).

Preciso usar um nonce diferente para cada assinatura que criar. Se eu usar o mesmo nonce privado (k) mais de uma vez, será possível para você descobrir minha chave privada (d).

3. Desafio

Agora que lhe enviei este nonce público (kG), preciso que você crie um desafio (e) e o envie para mim.

Este desafio (e) é um número aleatório que você gera, e vai me impedir de fabricar uma assinatura que pareça que conheço a chave privada (d) mesmo que não conheça.

Não sei qual será este desafio, e como já me comprometi a usar o nonce privado (k) ao lhe enviar o nonce público (kG), não será possível para mim ajustar meu valor de nonce privado (k) para me permitir produzir uma assinatura válida mesmo que não conheça a chave privada (d) para a chave pública (dG).

Em resumo, o desafio é usado para garantir que eu não possa trapacear.

4. Assinatura

Eu crio minha assinatura digital (s) multiplicando minha chave privada (d) pelo desafio (e), e então adiciono o nonce privado (k) a ele.

Então enviarei a você minha assinatura digital (s).

Você então executa a mesma equação. A única diferença é que você está realizando uma versão ampliada da equação, onde todos os números que estou usando foram ampliados pelo mesmo número G.

E se ambos os lados da sua equação forem iguais, você sabe que a assinatura digital (s) que lhe enviei só poderia ter sido criada por quem conhece a chave privada (d). Então isto prova que conheço a chave privada (d) para a chave pública (dG).

Qualquer pessoa que não conheça a chave privada (d) para a chave pública (dG) não teria sido capaz de calcular a assinatura digital (s) que satisfará sua equação.

Portanto, estas equações são o coração do esquema de assinatura Schnorr:

Estas são as mesmas equações do diagrama acima, apenas reorganizadas.

5. Exemplo simples

Tudo isso tem sido apenas um monte de equações usando letras até agora, então vamos usar alguns números reais para provar que estas equações funcionam.

Este exemplo usa apenas números pequenos e multiplicação simples.

Claro, estes números são pequenos demais para este sistema ser seguro, e a multiplicação normal não é uma boa escolha porque você pode simplesmente usar divisão para descobrir a chave privada original.

No entanto, em criptografia, usamos números muito grandes e um tipo especial de operação de "multiplicação" que não tem uma operação inversa de "divisão" (prometo que chegarei a isso em um momento).

Mas pelo menos você pode ver que estas equações funcionam.

6. Não interativo

A desvantagem da configuração atual é que ela é interativa.

Em outras palavras, você precisa me enviar o número do desafio (e) depois que eu lhe enviar o nonce público (kG), caso contrário eu poderia forjar a assinatura.

Seria melhor se esta configuração fosse não interativa, onde eu pudesse simplesmente gerar uma assinatura (s) sem que tivéssemos que trocar o nonce público (kG) e o desafio (e) primeiro.

E se eu pudesse criar o número do desafio (e) em vez disso?

Para fazer isto, eu precisaria ser capaz de me comprometer a usar meu nonce privado (k) de alguma forma, enquanto também fosse capaz de criar um número imprevisível para o desafio (e) do meu lado sem poder mudar de ideia sobre o nonce privado (k) depois.

A solução é usar uma função hash, e usá-la para hash do valor do nonce público (kG) para criar o desafio (e).

Uma função hash é perfeita porque produz um resultado imprevisível para qualquer dado que você alimentar nela. Além disso, ao aplicar hash no nonce público (kG), significa que estou comprometido a usar o nonce privado (k), porque não poderei alterá-lo depois sem modificar o desafio (e).

Então agora, em vez de termos que realizar uma troca interativa de kG e e antecipadamente, posso agora calcular uma assinatura digital (s) e enviá-la a você juntamente com o nonce público (kG) de uma só vez.

Você pode então usar esse nonce público (kG) para calcular o mesmo desafio imprevisível (e) que eu gerei do meu lado, e usar isto para verificar a assinatura digital (s) usando a mesma equação de antes:

Como resultado, usar uma função hash para criar o desafio (e) significa que convertemos este sistema de assinatura digital de interativo para não interativo. Esta é uma melhoria muito útil para nosso sistema.

Agora, toda vez que quiser criar uma assinatura digital, posso enviar uma para você junto com o nonce público (kG) sem que você precise me enviar um desafio (e) primeiro.

Então, graças à introdução da função hash para criar o desafio (e), as equações de criação e verificação agora se parecem com isto:

Esta técnica de usar uma função hash para criar o desafio de forma não interativa é conhecida como transformação de Fiat-Shamir.

7. Assinatura de mensagem

Até agora, venho apenas usando uma assinatura digital (s) para provar que sou o dono de uma chave pública (dG).

Isto é legal, mas seria ainda mais útil se eu pudesse assinar uma mensagem, de modo que se eu lhe enviasse uma assinatura (s) e uma mensagem (m), você possa verificar que eu disse ou concordo com aquela mensagem.

Isto é como assinar coisas na vida real. Sua assinatura por si só é única o suficiente para provar que você a fez, mas geralmente colocamos assinaturas em coisas como contratos para mostrar que concordamos com eles. A mensagem (m) aqui é o "contrato" no qual queremos colocar nossa assinatura (s).

No Bitcoin, por exemplo, esta mensagem geralmente são dados de transação. Ao assinar os dados da transação, podemos provar que somos os donos da chave pública para a qual alguns bitcoins foram bloqueados (para que possam ser desbloqueados), enquanto também concordamos com o destino para o qual estamos enviando as moedas. Ninguém pode então alterar estes dados da transação (por exemplo, tentar enviar as moedas para outro lugar) sem invalidar a assinatura.

De qualquer forma, para assinar uma mensagem, preciso incluir esta mensagem (m) como parte de minha assinatura (s) de alguma forma. Isto é feito incluindo a mensagem (m) como parte do hash quando estou criando o desafio (e).

Ao incluir a mensagem (m) dentro deste hash, estou me comprometendo com esta mensagem e tornando-a parte de minha assinatura final (s). Então, se alguém tentasse alterar a mensagem para dizer que eu disse algo diferente, a assinatura não verificaria para aquela mensagem.

De qualquer forma, agora que incluímos a mensagem como parte de nossa assinatura, as equações de criação e verificação se parecem com isto:

Estas são as equações fundamentais para um esquema de assinatura Schnorr não interativo. Você verá estas equações (nesta forma ou similar) toda vez que olhar qualquer explicação matemática de "assinaturas Schnorr".

8. Curvas elípticas

Finalmente, chegamos à parte especial da "multiplicação".

Até agora, estivemos usando multiplicação simples dentro de nossas equações. Mas isto não funcionará no mundo real, porque a multiplicação pode ser revertida usando divisão.

O que precisamos é de um tipo especial de "multiplicação" que tenha as mesmas propriedades da multiplicação normal (para que nossas equações ainda funcionem), mas não tenha uma operação inversa de "divisão".

É aí que entram as curvas elípticas.

Na verdade, existe uma operação de multiplicação que funciona em pontos de uma curva elíptica: você pode pegar um ponto na curva (ex. G), multiplicá-lo por um número (ex. d), e ele produzirá um ponto completamente novo na mesma curva (ex. dG). Mas curiosamente, se você der a alguém este novo ponto (dG), não há operação que permita "dividir" por G para descobrir o que era d.

Isto é perfeito para nosso sistema, e é a razão pela qual a matemática das assinaturas Schnorr é realizada sobre uma curva elíptica.

Além disso, você também pode somar dois pontos em uma curva elíptica, o que é importante porque também precisamos somar dois pontos durante a verificação (kG + edG).

Portanto, as equações funcionam da mesma forma que antes, mas as operações de multiplicar e somar agora ocorrem usando pontos em uma curva elíptica em vez de usar multiplicação e adição aritmética simples como vínhamos usando até este ponto.

Para ilustrar o tipo ligeiramente diferente de operação de multiplicação que estamos usando agora em nossas equações, usarei o operador ponto "⋅" para significar multiplicação de curva elíptica:

Existem outras opções para poder multiplicar sem divisão, mas as curvas elípticas são as mais populares em criptografia devido à sua segurança e velocidade.

9. Resumo

As equações finais de criação e verificação Schnorr se parecem com isto:

Mas também podemos simplificar:

• O desafio hash(kg || m) é chamado de e.
• O ponto do nonce público (kG) é chamado de R.
• O ponto da chave pública (dG) é chamado de P.

Então, se substituirmos estes termos em nossas equações, obtemos:

E é daí que vêm estas equações de criação e verificação no topo desta página.

Por último, podemos reorganizar a equação de verificação para obter:

E esta é a equação usada durante a verificação para assinaturas Schnorr no Bitcoin.

História

Por que as assinaturas Schnorr não foram usadas no Bitcoin desde o início?

O esquema de assinatura Schnorr estava sob patente quando o Bitcoin estava sendo desenvolvido.

Satoshi usou a biblioteca OpenSSL para a criptografia usada no Bitcoin, e as assinaturas Schnorr não estavam disponíveis nesta biblioteca na época, então eles usaram ECDSA em vez disso. Portanto, embora as assinaturas Schnorr sejam mais simples e mais úteis que o ECDSA, elas não eram uma opção viável na época em que o Bitcoin foi criado.

Aqui está um breve histórico:

• 1989 — A matemática para assinaturas Schnorr é publicada por Claus Schnorr no artigo Efficient identification and signatures for smart cards.
• 1990 — Claus Schnorr solicita uma patente do esquema de assinatura Schnorr.
• 1991 — Patente do esquema de assinatura Schnorr é concedida.
• 1992 — Dr. Scott Vanstone propõe o ECDSA como uma alternativa para criar assinaturas digitais.
• 1998 — ECDSA é aceito como padrão ISO.
• 1999 — ECDSA é aceito como padrão ANSI.
• 2000 — ECDSA é aceito como padrão IEEE e NIST.
• 2007 — Satoshi Nakamoto começa a trabalhar no Bitcoin e usa ECDSA para assinaturas.
• 2009 — Primeira versão do Bitcoin é lançada.
• 2010 — Patente do esquema de assinatura Schnorr expira.
• 2015 — Pesquisas começam sobre a inclusão de assinaturas Schnorr no Bitcoin.
• 2021 — Assinaturas Schnorr são introduzidas no Bitcoin como parte da atualização Taproot.

Resumo

As assinaturas Schnorr são uma atualização do ECDSA para criar e verificar assinaturas digitais no Bitcoin.

A única razão pela qual não usamos assinaturas Schnorr desde o início é porque elas foram patenteadas até 2010, então ECDSA foi a próxima melhor opção (que faz o trabalho, só não tão elegantemente). Mas como a patente expirou, estamos livres para usar assinaturas Schnorr e aproveitar todos os benefícios que vêm com elas.

Em termos mais contundentes:

Em outras palavras, as assinaturas Schnorr são como as assinaturas digitais deveriam ser.

A implementação de assinaturas Schnorr no Bitcoin parece mais complexa que o ECDSA, mas na verdade não é tão difícil quanto parece. A matemática subjacente é mais simples; é só que existem algumas implementações de design específicas do Bitcoin incluídas por cima. Então não deixe os diagramas complexos te desanimarem. Se você for passo a passo, não deve ser muito difícil de implementar.

Além disso, se você está interessado na matemática de como as assinaturas digitais funcionam, faz mais sentido tentar entender o esquema básico de assinatura Schnorr antes de passar para o ECDSA.

Você não precisa saber como as assinaturas Schnorr funcionam para poder adicioná-las ao seu código, mas é legal ver como elas funcionam.

Recursos

• BIP 340: Schnorr Signatures for secp256k1

• Cryptoshorts e02: Schnorr signature — Um vídeo simples e conciso explicando os fundamentos de como funcionam as assinaturas Schnorr.
• How to Design Schnorr Signatures — Excelente explicação do design das assinaturas Schnorr por Adam Gibson (Waxwing).
• Taproot, and Schnorr, and SIGHASH_NOINPUT, oh my! — Resumo dos benefícios das assinaturas Schnorr e Taproot por Pieter Wuille.
• Introduction to Schnorr Signatures with Elichai Turkel — Apresentação técnica sobre assinaturas Schnorr e seus usos no Bitcoin.