Passeio Aleatório

O modelo probabilístico da corrida entre atacante e rede honesta

Um passeio aleatório (random walk) é um processo estocástico que descreve uma trajetória composta por passos sucessivos e aleatórios. É a estrutura matemática mais natural para entender a competição entre o atacante e a rede honesta na corrida para construir a cadeia mais longa.

Esta página mostra como o modelo de passeio aleatório se aplica à segurança do Bitcoin, desde a análise original de Satoshi até simulações computacionais da probabilidade de um ataque bem-sucedido.

Conteúdo

O que é um Passeio Aleatório?

Passos para a esquerda ou para a direita, ao acaso

Imagine uma reta numérica. Você começa no 0. A cada segundo, você joga uma moeda: se der cara, você anda um passo para a direita (+1); se der coroa, um passo para a esquerda (−1). Sua posição após n passos é a soma de n variáveis aleatórias independentes. Essa é a forma mais simples de passeio aleatório — o passeio aleatório simétrico unidimensional.

Características fundamentais de um passeio aleatório:

A última propriedade é crucial: a dependência do futuro é apenas da posição atual, não de como se chegou até ela. É a propriedade de Markov: dado o presente, o futuro é independente do passado. O passeio aleatório é um dos exemplos mais simples de um processo de Markov.

O Passeio Aleatório no Bitcoin

A corrida entre atacante e honestos como uma caminhada

A competição entre o atacante e a rede honesta para minerar blocos é análoga a um passeio aleatório com tendência (drift). A cada bloco encontrado pela rede, acontece um passo:

A posição do atacante na reta numérica representa sua vantagem em blocos em relação à cadeia honesta. Se ele começa no ponto −z (z blocos atrás), o ataque termina com sucesso quando a posição atinge 0 ou positiva (ele alcançou ou ultrapassou a cadeia honesta).

Passeio Aleatório vs Processo de Poisson: Enquanto o Processo de Poisson descreve quando blocos são encontrados, o Passeio Aleatório descreve quem os encontra. Os dois modelos se complementam: o Poisson determina o ritmo dos eventos, o Random Walk determina o placar da competição.

Tendência (drift) da caminhada

Quando a moeda é viciada contra o atacante

No Bitcoin, a "moeda" do passeio aleatório não é justa. Se o atacante tem q = 0,3 (30% do poder de hash), a cada passo ele tem 30% de chance de andar para a direita e 70% de andar para a esquerda. O drift (tendência) do passeio é:

drift = 2q − 1

Para q = 0,3, o drift é −0,4: a cada passo, a posição esperada do atacante diminui 0,4 bloco. Ele tende a se afastar cada vez mais do zero, não a se aproximar.

# Distribuicao binomial da posicao apos n passos
# n = numero total de passos
# k = numero de passos "para a direita" (a favor do atacante)

def posicao_mais_provavel(q, n)
  # valor esperado da posicao apos n passos
  n * (2 * q - 1)
end

puts posicao_mais_provavel(0.4, 100)  # -20 (tende a ficar para tras)
puts posicao_mais_provavel(0.1, 100)  # -80 (fortemente para tras)
puts posicao_mais_provavel(0.49, 100) # -2  (quase empatado)

Isso significa que, para q < 0,5, a posição do atacante tende a −∞ (ele nunca alcança a cadeia honesta) à medida que o número de blocos cresce. A probabilidade de sucesso é determinada pela competição entre essa tendência de afastamento e as flutuações aleatórias que podem, por pura sorte, levá-lo de volta ao zero.

Quando q se aproxima de 0,5, o drift se aproxima de zero. Para q = 0,49, o drift é −0,02 — uma tendência muito fraca contra o atacante. Isso significa que ele pode flutuar por muito tempo antes de ser puxado para trás, e suas chances de eventualmente empatar são significativas.

Relação com a Ruína do Jogador

O mesmo processo, duas interpretações

O problema da ruína do jogador visto na página de Processos Estocásticos é, na verdade, o mesmo processo matemático do passeio aleatório com duas barreiras absorventes.

A relação é direta: o atacante começa com uma "fortuna" de 0 blocos de vantagem e precisa chegar a z blocos de vantagem (ou −∞, a ruína). No caso do Bitcoin, o interesse é de um lado só: o atacante começa em −z (desvantagem) e precisa chegar a 0 (vitória). É a ruína do jogador com o cassino jogando do lado oposto.

A probabilidade de o atacante eventualmente alcançar a cadeia honesta, partindo de uma desvantagem de z blocos, segue uma forma conhecida da ruína do jogador:

P(alcançar) = (q/p)z

Esta fórmula vale para q < p (atacante minoritário). Para q ≥ p, a probabilidade é 1 (o atacante eventualmente alcança com certeza, pois o drift é a seu favor ou neutro). É uma simplificação — a equação exata de Satoshi incorpora a distribuição de Poisson dos blocos —, mas captura a intuição central: a probabilidade cai exponencialmente com a profundidade z.

Simulação de Monte Carlo

Observando o passeio aleatório em ação

A simulação computacional do passeio aleatório é a forma mais intuitiva de entender a segurança do Bitcoin contra ataques. O código abaixo executa milhares de corridas entre o atacante e a rede honesta e mede a fração de vezes em que o atacante consegue alcançar a cadeia:

# Simulacao de uma caminhada aleatoria simples
# A cada passo: +1 (atacante minera um bloco) com prob. q
#                -1 (rede honesta minera um bloco) com prob. p
# O atacante comeca em desvantagem de -z blocos.
# Sucesso = alcanca vantagem 0 (empata) ou positiva.

def simulate(q, z, steps=10000)
  p = 1 - q
  pos = -z
  steps.times do
    pos += rand < q ? 1 : -1
    return true if pos >= 0
  end
  false
end

# Proporcao de sucessos em N simulacoes
def success_rate(q, z, trials=100000)
  trials.times.count { simulate(q, z) }.to_f / trials
end

puts success_rate(0.1, 5) # ~0.00002  (2 em 100.000)
puts success_rate(0.3, 5) # ~0.132    (13.2%)
puts success_rate(0.45, 5) # ~0.865   (86.5%)

Os resultados da simulação confirmam a teoria: para q = 0,1 e z = 5 (atacante com 10% do poder de hash tentando reverter 5 blocos), a chance de sucesso é de aproximadamente 0,002% — 2 em cada 100.000 tentativas. Para q = 0,3, esse número sobe para 13,2% — um risco significativo que justifica esperar por mais confirmações.

Você pode visualizar o passeio aleatório interativamente com o Simulador de Ataque na página do Ataque de 51%. Ele implementa a equação completa de Satoshi combinando a distribuição de Poisson com o passeio aleatório.

Tempo até o primeiro sucesso

Quanto tempo o atacante leva para alcançar a cadeia?

Além da probabilidade de sucesso, outra questão relevante é: quanto tempo o atacante leva para alcançar a cadeia honesta, dado que ele vai conseguir?

O tempo de primeiro sucesso (first passage time) para um passeio aleatório com drift negativo segue uma distribuição conhecida. Para valores de q razoavelmente abaixo de 0,5, o tempo esperado de sucesso (condicional a sucesso) é aproximadamente:

E[T] ≈ z / (p − q)

Intuitivamente: se o atacante está 6 blocos atrás e tem q = 0,3 (drift de −0,4), ele precisa, em média, de 6 / 0,4 = 15 blocos de vantagem líquida sobre os honestos para alcançá-los. Como a cada bloco ele ganha ou perde 1, o número total esperado de blocos até o sucesso é maior — da ordem de dezenas ou centenas de blocos. E isso é apenas a média: a distribuição tem uma cauda longa, com alguns ataques bem-sucedidos levando muito mais tempo.

Na prática, isso significa que um ataque de 51% não é instantâneo. Mesmo com poder de hash suficiente, o atacante precisa esperar — e durante essa espera, a rede honesta continua minerando, e transações legítimas continuam sendo confirmadas na cadeia principal. Quanto mais tempo o ataque leva, maior a chance de ser detectado.

Implicações para a segurança

O que o modelo nos ensina sobre confirmações

Em resumo, o passeio aleatório nos dá uma lente matemática para entender por que o modelo de consenso do Bitcoin funciona: a competição justa e aleatória pela mineração de blocos, combinada com a regra da cadeia mais longa, cria um sistema onde reverter transações se torna exponencialmente mais difícil com cada bloco que passa.

Recursos