Deterministic Johnson--Lindenstrauss Projections from Pisot $\beta$-Transformations for Zero-Knowledge Private Routing

Resumo Técnico: Projeções de Johnson–Lindenstrauss Determinísticas a partir de Transformações $\beta$-Pisot para Roteamento Privado com Zero-Knowledge

1. Definição do Problema

Em sistemas de prova de Conhecimento Zero (ZK) para roteamento privado, um provador deve certificar que um embedding de mensagem $v \in \mathbb{R}^d$ pertence a uma classe semântica permitida definida por um conjunto de centroides públicos $C = \{c_1, \dots, c_N\}$. Isso é tipicamente feito via um teste de centroide mais próximo, o que requer $O(Nd)$ restrições aritméticas. Dado o dimensionamento moderno de embeddings ($d \in [768, 4096]$), essa contagem de restrições domina o tamanho da prova e o tempo do provador.

O remédio padrão é uma projeção de Johnson–Lindenstrauss (JL) para reduzir a dimensão para $m \ll d$. No entanto, matrizes JL clássicas são aleatórias. Em um contexto de ZK, usar uma matriz aleatória força o circuito a realizar o compromisso (commit) da matriz e provar sua amostragem correta, reintroduzindo justamente o custo computacional que a projeção deveria eliminar. Além disso, matrizes aleatórias exigem a prova do processo de amostragem, criando um risco de vazamento (leakage). O desafio é construir uma matriz de projeção pública, determinística e fixa que:

1. Preserve distâncias par a par de forma provável.
2. Seja nativa ao campo finito do circuito.
3. Não requeira aleatoriedade in-circuit ou provas de amostragem.

2. Metodologia

Os autores propõem construir a matriz de projeção $A$ a partir da órbita padronizada de uma transformação $\beta$-Pisot.

• O Mapa: Uma $\beta$-transformação $T_\beta x = \beta x - \lfloor \beta x \rfloor$ no intervalo unitário, onde $\beta > 1$ é um número Pisot (um inteiro algébrico cujos conjugados de Galois residem estritamente dentro do disco unitário, ex: a razão áurea).
• Dinâmica: O mapa é um sistema caótico determinístico de "estiramento e dobra" (stretch-and-fold) com uma medida de Parry invariante única $\mu$. Crucialmente, porque $\beta$ é Pisot, o operador de transferência do mapa possui um gap espectral, fazendo com que as correlações entre observáveis decaiam geometricamente ($|r_k| \le C\theta^k$).
• Construção da Matriz:
  • Uma semente pública $x_0$ é selecionada.
  • Um gap de amostragem $g$ é fixo para garantir que as amostras sejam tomadas além do tempo de correlação.
  • As entradas da matriz $A_{ij}$ são preenchidas sequencialmente com os valores da órbita normalizados $z_p = \psi(T_\beta^{pg} x_0)$.
  • A projeção é $\Phi(v) = Av/\sqrt{m}$.
• Reprodutibilidade em Campo Finito: Diferente de mapas caóticos genéricos, a propriedade Pisot garante que a órbita seja exatamente reproduzível em um campo finito fixo. O custo de gerar $k$ passos é linear em $k$ (especificamente $O(k \log_2 \beta)$ bits), enquanto mapas caóticos genéricos (como o mapa logístico) exigem crescimento exponencial de bits ($O(2^k)$) para manter a aritmética exata.

3. Principais Contribuições

O artigo apresenta quatro contribuições teóricas e práticas principais:

1. Limites de Viés e Variância Independentes de Dimensão:

   • Viés: Os autores provam que o viés do estimador de norma ao quadrado é limitado por um termo que decai geometricamente com o gap de amparagem $g$, independente da dimensão ambiente $d$ (Lema 1). Isso é derivado do gap espectral do $\beta$-map, oferecendo uma garantia mais forte do que argumentos de equidistribuição padrão.
   • Variância: Eles mostram que a variância do estimador escala como $V_0/m$. Crucialmente, sob uma hipótese de concentração declarada, a constante $V_0$ é independente da dimensão (não cresce com $d^2$), ao contrário de limites brutos que sugerem $O(d^2)$. Isso implica que uma dimensão de projeção $m$ fixa é suficiente, independentemente de quão grande $d$ se torne.

2. Existência de uma Única Semente Pública:

   • O Teorema 1 prova que existe uma única semente pública $x_0$ que preserva todas as $\binom{N}{2}$ distâncias par a par dos centroides dentro de $(1 \pm \varepsilon)$.
   • Esta semente pode ser encontrada via uma busca offline eficiente. Uma vez encontrada, a matriz é fixa, pública e não requer compromisso de aleatoriedade durante a prova ZK.

3. Reprodutibilidade Exata via Propriedade Pisot:

   • O artigo identifica que a propriedade Pisot (não apenas o caos genérico) é essencial para o deployment em ZK. Ela garante que a órbita possa ser reproduzida exatamente em um campo finito fixo com custo computacional linear por passo. Mapas caóticos genéricos falham aqui devido ao crescimento exponencial da precisão necessária (denominadores) para evitar a divergência de ponto flutuante.

4. Robustez e Busca:

   • Um raio de robustez certificável de forma fechada é fornecido (Proposição 1), definindo a perturbação máxima que uma consulta pode suportar sem alterar seu centroide projetado mais próximo.
   • A busca pela semente é incondicional (garantida pelos limites de variância), mas pode ser melhorada para uma dependência logarítmica de $N$ se uma desigualdade de concentração específica para o mapa de gap espectral for válida.

4. Resultados Experimentais

A construção foi avaliada contra seis projeções padrão: Gaussiana, Rademacher, Achlioptas esparsa, Subsampled Randomized Hadamard Transform (SRHT) e uma matriz de sequência caótica (Yu et al.).

• Qualidade Estatística: A projeção Pisot iguala a qualidade estatística das projeções aleatórias.
  • Taxa de Variância: A variância do estimador segue a lei $1/m$ e sobrepõe-se à referência de $2/m$ da JL Gaussiana.
  • Independência de Dimensão: A constante de variância $V_0$ permanece estável próxima a 2 conforme $d$ aumenta de 64 para 1024, confirmando a previsão teórica independente da dimensão.
  • Distorção: A distorção relativa de pior caso sobre todos os pares de centroides acompanha a linha de base da JL Gaussiana.
• Desempenho da Tarefa: Em uma tarefa de roteamento de centroide mais próximo de 24 classes com $d=256$, a projeção Pisot recuperou 100% de precisão com $m=32$ (uma compressão de 8x), idêntica aos outros métodos.
• Reprodutibilidade: Simulações confirmaram que implementações de ponto flutuante divergem das órbitas exatas após $\approx 50-70$ passos (correspondendo às previsões de Lyapunov), enquanto a representação $\beta$-ádica de Pisot permanece exata e compacta (139 bits para 200 passos vs. $1.66 \times 10^6$ bits para um mapa logístico).

5. Significância e Alegações

O artigo afirma que esta construção é o único método que satisfaz simultaneamente três requisitos críticos para o roteamento privado com ZK:

1. Livre de aleatoriedade in-circuit: Não há necessidade de realizar o commit ou provar a amostragem de uma matriz aleatória.
2. Exatamente reproduzível em um campo finito fixo: Alcançado via propriedade Pisot com um custo de $\log_2 \beta$ por passo, evitando o custo $O(2^k)$ de mapas caóticos genéricos.
3. Estatisticamente equivalente a projeções aleatórias: Corresponde à taxa de variância e propriedades de distorção das matrizes JL padrão.

Os autores observam que, embora a qualidade estatística seja provada, o passo teórico de elevar o limite de busca de semente incondicional $O(N^2)$ para um limite condicional $O(\log N)$ depende de uma desigualdade de concentração específica para o operador de transferência, que permanece um passo teórico em aberto. Na prática, o método permite mudar de minutos/gigabytes de geração de prova para segundos, tornando o roteamento privado verificável viável para embeddings de alta dimensão.