💻 computer science

NP-Completeness and Physical Zero-Knowledge Proof of Hotaru Beam

Este artigo demonstra que o quebra-cabeça lógico Hotaru Beam é NP-completo e apresenta um protocolo de prova de conhecimento zero físico para provar a posse de uma solução sem revelá-la.

Autores originais: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Publicado 2026-03-03

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Taisei Otsuji, Peter Fulla, Takuro Fukunaga

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um quebra-cabeça lógico chamado Hotaru Beam (ou "Feixe de Vaga-lume"). O objetivo é conectar pontos brilhantes (os vaga-lumes) em uma grade desenhando linhas retas que fazem curvas. Mas há uma regra chata: você não pode apenas desenhar; você precisa provar que sabe exatamente como conectar tudo, sem mostrar o desenho para ninguém. É como se você fosse um mágico que precisa provar que tem a solução do truque, mas sem revelar o segredo.

Este artigo de pesquisa é sobre duas coisas principais:

Provar que esse quebra-cabeça é matematicamente difícil (do tipo "NP-completo").
Criar um método "físico" (usando cartas de baralho) para provar que você tem a solução, sem nunca mostrar a solução em si.

Vamos descomplicar isso com analogias do dia a dia.

1. O Problema: O Labirinto de Vaga-lumes

Pense no tabuleiro como uma folha de papel quadriculado. Em alguns cruzamentos, há círculos (os vaga-lumes). Alguns têm números escritos dentro.

A Regra: Você deve desenhar um "feixe de luz" saindo de cada vaga-lume.
O Desafio: O feixe deve fazer exatamente o número de curvas indicado pelo número no círculo (se houver).
O Objetivo Final: Todos os vaga-lumes devem estar conectados entre si por esses feixes, formando uma única grande teia, sem que os feixes se cruzem ou se dividam.

Os autores provaram matematicamente que, se o tabuleiro for grande o suficiente, encontrar essa solução é tão difícil quanto resolver os problemas mais complexos da computação. É como tentar adivinhar a senha de um cofre: se você tiver a senha, é fácil abrir; mas descobrir a senha do zero pode levar uma eternidade.

2. A Solução Mágica: O Protocolo de "Prova de Conhecimento Zero"

Aqui entra a parte divertida. Como provar que você sabe a senha sem dizer qual é?

Os autores criaram um jogo usando cartas de baralho. Imagine que você (o "Provedor") quer convencer um amigo (o "Verificador") de que você resolveu o quebra-cabeça, mas você não pode deixar ele olhar o papel.

As Ferramentas Mágicas:

O Tabuleiro de Cartas: Em vez de papel, o tabuleiro é feito de cartas viradas para baixo.
- Cartas com corações (♡) representam espaços vazios onde a luz pode passar.
- Cartas com espadas (♣) representam caminhos que já foram "pintados" (a luz passou por ali).
- Cartas com números representam os vaga-lumes.
A Tabela de Conexões: Imagine uma lista de amigos. Se dois vaga-lumes estão conectados, você marca um "Sim" (uma carta especial) na lista deles.

O Truque (O Protocolo):

O processo funciona como um jogo de esconde-esconde com cartas:

Esconder o Caminho: Você pega uma carta que representa o início do feixe de luz. Você escolhe um caminho (esquerda ou direita) e "pinta" o caminho trocando as cartas de coração (vazio) por espadas (caminho ocupado).
O Mistério da Curva: Se o feixe precisa fazer uma curva, você usa um truque de embaralhamento (chamado de "embaralhamento de pilhas"). É como se você pegasse uma pilha de cartas, misturasse com as costas para cima, e dissesse: "Eu fiz uma curva aqui, mas você não sabe onde exatamente, só sabe que a regra foi seguida".
A Prova de Conexão: No final, você precisa provar que todos os vaga-lumes estão conectados. Você usa a "Tabela de Conexões". Se o vaga-lume A está conectado ao B, e o B ao C, você usa um truque de cartas para mostrar que A e C também estão conectados, sem revelar o caminho que liga A a C.

A Analogia do Restaurante:
Imagine que você é um chef que criou um prato secreto. O cliente quer provar que você sabe cozinhar, mas não quer ver a receita.

Você coloca os ingredientes (cartas) na mesa.
Você faz o prato (desenha as linhas) cobrindo tudo com um pano (virando as cartas).
Você entrega o prato pronto. O cliente prova e vê que está delicioso (a lógica está correta).
O cliente nunca viu a receita, mas sabe que você é o chef.

3. Por que isso é importante?

Segurança: Isso mostra como podemos verificar informações sensíveis (como senhas ou soluções de problemas complexos) sem vazá-las. É a base de muitas tecnologias de criptografia modernas.
Simplicidade: O incrível é que eles não usaram computadores complexos para isso. Usaram apenas cartas, papel e lógica humana. Isso torna a prova acessível a qualquer pessoa, não apenas a especialistas em matemática.
Novas Ideias: Eles inventaram dois "truques" novos (o protocolo de inserção de segmento e a tabela de conexões) que podem ser usados para resolver outros quebra-cabeças geométricos no futuro.

Resumo Final

Os autores pegaram um quebra-cabeça difícil de vaga-lumes, provaram que ele é matematicamente complexo e criaram um jogo de cartas onde você pode provar que o resolveu sem nunca mostrar o desenho. É como dizer: "Eu sei o caminho para o tesouro", e provar isso fazendo o mapa aparecer magicamente na sua mão, mas sem nunca deixar o outro jogador ver o papel onde o mapa estava escrito.

Visão Geral

O artigo apresenta dois resultados principais sobre o quebra-cabeça lógico Hotaru Beam (criado pela Nikoli):

A prova de que o problema de decidir se uma instância de Hotaru Beam possui uma solução é NP-completo.
O desenvolvimento de um Prova de Conhecimento Zero (ZKP) Física (implementável com cartas e objetos do cotidiano) que permite a um provador (Peter) convencer um verificador (Vera) de que ele conhece a solução do quebra-cabeça sem revelar nenhuma informação sobre a solução em si.

1. O Problema: Hotaru Beam

Definição: O jogo é jogado em uma grade retangular contendo círculos chamados "vagalumes" (fireflies). Cada vagalume possui um ponto de partida na borda e, opcionalmente, um número no interior.
Objetivo: Desenhar "feixes" de luz (linhas) conectando todos os vagalumes em um único componente conectado.
Regras:
- Não interseção/ramificação: Os feixes não podem cruzar nem se ramificar.
- Restrição de Curvatura (Bending Constraint): Se um vagalume tem um número $k$ no interior, o feixe que sai dele deve fazer exatamente $k$ curvas (dobras). Se não houver número, o número de curvas é ilimitado.
- Conectividade: Todos os vagalumes devem estar conectados entre si através dos feixes.

2. Metodologia e Resultados Principais

A. Prova de NP-Completude

Os autores provam que o Hotaru Beam é NP-completo através de uma redução a partir do problema Planar Monotone 3-SAT (uma variante restrita do problema de satisfatibilidade booleana).

Redução: Eles constroem "gadgets" (mecanismos) baseados em vagalumes e restrições de curvatura que simulam:
- Variáveis: Gadgets que permitem duas configurações de feixes (representando Verdadeiro ou Falso).
- Cláusulas: Gadgets que conectam às variáveis apenas se a atribuição de valor satisfizer a cláusula.
Lógica: A instância do Hotaru Beam tem solução se e somente se a fórmula booleana correspondente for satisfatível. A construção garante que a conectividade global e as restrições de curvatura forcem a consistência lógica da atribuição de variáveis.

B. Protocolo de ZKP Física

O protocolo utiliza cartas com padrões (♣, ♠, ♡, ♢) e valores numéricos para codificar a solução. O objetivo é manter a ZK-Propriedade (Vera não aprende nada além da existência da solução).

Componentes Chave do Protocolo:

Representação do Tabuleiro (Board):
- A grade é representada por cartas. Pontos de grade vazios são cartas ♡ (indicando que podem ser atravessados). Vagalumes são cartas numeradas.
- À medida que Peter "desenha" o feixe, as cartas ♡ são substituídas por cartas ♣ (indicando que o caminho foi ocupado) ou ♢ (indicando o ponto de virada/curva).
Tabela de Conexões (Connections Table):
- Uma estrutura de $n$ colunas (uma para cada vagalume) contendo pares de cartas lógicas.
- Um par $(\clubsuit, \heartsuit)$ representa Verdadeiro (conectado) e $(\heartsuit, \clubsuit)$ representa Falso.
- Invariante: Se a $j$ -ésima carta lógica na coluna $i$ é Verdadeira, os vagalumes $i$ e $j$ pertencem ao mesmo componente conectado.
Protocolo de Incorporação de Segmento (Segment Embedding Protocol):
- Este é o núcleo da prova, permitindo que Peter desenhe um segmento do feixe sem revelar a direção exata ou o número de curvas (se não for fixo).
- Máscara (Mask Sequence): Peter usa uma sequência auxiliar de cartas embaralhada para selecionar e substituir cartas no tabuleiro.
- Técnicas de Ocultação:
  - Pile-shifting shuffle: Embaralhamento circular para esconder a posição absoluta.
  - Pile choosing: Permite selecionar uma pilha (linha/coluna) para operar sem que Vera saiba qual foi escolhida.
  - Prova de Pertencimento a Conjunto: Para verificar se uma carta é um número (vagalume) sem revelar qual número é.
Execução do Protocolo:
- Peter desenha os feixes vagalume por vagalume.
- Para cada feixe, ele divide o caminho em segmentos retos e aplica o protocolo de incorporação.
- Ele atualiza a Tabela de Conexões para refletir que os vagalumes conectados agora compartilham o mesmo componente (usando operações de disjunção lógica nas cartas).
- No final, Peter garante que todas as cartas lógicas na tabela sejam Verdadeiras (indicando que todos os vagalumes estão conectados), realizando operações de fusão de componentes até que a tabela esteja completa.

3. Contribuições Inovadoras

O artigo destaca duas ideias inovadoras para lidar com as restrições específicas do Hotaru Beam:

Protocolo de Implementação de Feixes com Contagem de Curvas: Diferente de outros quebra-cabeças (como Numberlink), o Hotaru Beam exige controle rigoroso do número de curvas. O protocolo de "segment embedding" permite que o provador demonstre que fez o número correto de curvas (ou zero, se permitido) sem revelar a geometria exata do caminho.
Rastreamento de Conexões Dinâmico: A introdução da "Tabela de Conexões" permite verificar a conectividade global (um requisito complexo) de forma incremental e segura, garantindo que a prova de conectividade final seja válida sem revelar a topologia da rede de feixes.

4. Significado e Impacto

Teoria da Complexidade: Estabelece formalmente a dificuldade computacional do Hotaru Beam, adicionando-o à lista de quebra-cabeças lógicos NP-completos.
Criptografia Física: Demonstra que é possível construir protocolos ZKP físicos eficientes e intuitivos para problemas geométricos complexos que envolvem restrições de contagem e conectividade.
Aplicabilidade Geral: As técnicas desenvolvidas (especialmente o protocolo de segmentação e a tabela de conexões) são sugeridas como ferramentas valiosas para projetar ZKPs para outros objetos geométricos e quebra-cabeças em grades, superando as limitações de protocolos genéricos baseados em circuitos booleanos.

Em resumo, o trabalho combina a teoria da complexidade computacional com a criptografia prática, oferecendo uma solução elegante para provar a posse de uma solução de um quebra-cabeça lógico complexo usando apenas cartas e manipulação física.