Dobrando extensões quárticas em multiplicações 2N-4 e por que as camadas de comprometimento baseadas em linhas não conseguem acompanhar – zk-s(nt)arks

DR

Fornecemos um backend algébrico exato para dobramento no estilo sumcheck sobre uma extensão quártica E/F. Usando uma base de potência móvel \{1, r_i, r_i^2, r_i^3\} que rastreia a órbita recíproca, o mecanismo de dobra funciona exatamente 2N – 4 multiplicações de campo base em Ffolhas com valor agregado — uma redução de 5x em relação à linha de base direta de base fixa. Todo o avaliador especializado em sementes T_{\tau,n}: F^N \para F^4 é descrito por um descritor público reduzido de 4(n-1) palavras de campo, em comparação com as 4N palavras exigidas por vetores de linha explícitos. No entanto, qualquer camada de comprometimento downstream que aceite apenas linhas explícitas não pode consumir esta compactação e deve materializar a completa 4N-representação de palavras.

Motivação

Os protocolos de dobramento no estilo Sumcheck descrevem suas atualizações rodada por rodada em um nível esquemático. Para extensões quadráticas isso é inofensivo — a dobra local é uma identidade de livro didático. Mas a partir do grau 4, três coisas tornam-se não triviais simultaneamente: o transporte da base móvel após cada passo recíproco, a atualização do coeficiente para o polinômio mínimo redondo e a contagem exata de multiplicação do mecanismo resultante.

Nenhum trabalho anterior isola todos os três de forma fechada para um grau de extensão fixo. Isso é importante para as camadas downstream: sem uma especificação algébrica exata, os protocolos de compromisso e abertura devem derivar novamente a estrutura redonda internamente ou recorrer a interfaces genéricas de vetor de linha que perdem a especialização de semente de tamanho logarítmico.

Esta nota preenche essa lacuna para o caso quártico (E:F) = 4 com uma alternância 0/1 cronograma e registra a consequência da interface de que o consumo de linha explícita destrói a compactação.

Resultados: dobrar o desempenho do motor

Consertar F = \mathbb{F}_q com \text{char}(F) > 3, E = \mathbb{F}_{q^4}e N = 2^n. A tabela a seguir compara a dobra da base móvel especializada com a linha de base direta da base fixa, ambas medidas no campo escalar BN254.

Cada entrada no specialized muls coluna é igual exatamente 2N – 4confirmando a contagem teórica. A razão de multiplicação converge para 5,00× em todas as profundidades testadas, correspondendo à previsão assintótica (m_{F,\texto{pub}} + m_{E,\texto{pub}})/4. As acelerações do relógio de parede variam de 2,72× a 5,00×; a lacuna da razão aritmética reflete os efeitos da hierarquia de memória em níveis maiores N.

Como funciona

O motor algébrico possui três camadas. Esboçamos apenas as identidades essenciais; as provas completas estão na nota.

1. Órbita recíproca

Consertar uma semente \ tau \ em E com F(\tau) = E. Defina a órbita do desafio público por

$$r_1 = \tau, \qquad r_{i+1} = \frac{1}{r_i – c_i}, \qquad c_i = \begin{cases} 0, & i \text{ ímpar}, \ 1, & i \text{ par}. \end{casos}$$

Cada ponto de órbita satisfaz F(r_i) = Eentão \{1, r_i, r_i^2, r_i^3\} é um F-base de E em cada rodada. O estado ativo do mecanismo de dobra é sempre um vetor de quatro palavras (a_0, a_1, a_2, a_3)\em F^4interpretado através de um denominador compartilhado como um elemento de E.

2. Dobra local (Etapa A)

Na rodada euum par adjacente de estados (s_0, s_1) é dobrado por

$$u = s_0 + S_{\mu_i}(s_1 – s_0),$$

onde

$$S_{\mu} = \begin{pmatrix} 0 & 0 & 0 & \mu_0 \ 1 & 0 & 0 & \mu_1 \ 0 & 1 & 0 & \mu_2 \ 0 & 0 & 1 & \mu_3 \end{pmatrix}$$

e \mu_i = (\mu_{i,0}, \mu_{i,1}, \mu_{i,2}, \mu_{i,3}) são os coeficientes do polinômio mínimo de r_i. O principal facto estrutural: em Ffolhas com valor, o vetor de diferença s_1 – s_0 concentra toda a dependência de sementes em um único escalar \delta_3. A etapa A, portanto, custa exatamente 4 multiplicações por par sobrevivente – uma para cada \mu_j\delta_3.

3. Transporte gráfico

Após a Etapa A, o estado deve ser reexpresso na base da próxima rodada. Este é o mapa de transporte R_{c_i}:

• Rodadas ímpares (c_i = 0): R_0(u_0, u_1, u_2, u_3) = (u_3, u_2, u_1, u_0). Uma inversão de coordenadas – multiplicações zero.

• Rodadas pares (c_i = 1): R_1 envolve adições e multiplicações pelas constantes públicas 2 e 3, que são realizadas por cadeias de adição – multiplicações zero no modelo de custo canônico.

A contagem total em todas as rodadas é, portanto: a rodada 1 contribui com 0 (entradas escalares) e cada par subsequente contribui exatamente com 4 multiplicações da Etapa A. Resumindo:

$$M_{\text{canon}}(N) = 4 \cdot \left(\frac{N}{2} – 1\right) = 2N – 4.$$

Exemplo resolvido: N = 4

O caso N = 4 é a menor instância não trivial. Deixar x = (x_0, x_1, x_2, x_3)\em F^4 e \mu_2 = (\mu_{2,0}, \mu_{2,1}, \mu_{2,2}, \mu_{2,3}). A matriz completa do avaliador é:

$$T_{\tau,2}(x) = \begin{pmatrix} 2-\mu_{2,3} & -1 & \mu_{2,3}-1 & 1 \ 5-\mu_{2,2}-3\mu_{2,3} & -2 & \mu_{2,2}+3\mu_{2,3}-3 & 3 \ 4-\mu_{2,1}-2\mu_{2,2}-3\mu_{2,3} & -1 & \mu_{2,1}+2\mu_{2,2}+3\mu_{2,3}-3 & 3 \ 1-\sum_{j}\mu_{2,j} & 0 & \sum_{j}\mu_{2,j}-1 & 1 \end{pmatrix} \begin{pmatriz} x_0 \ x_1 \ x_2 \ x_3 \end{pmatriz}.$$

As quatro linhas são os vetores de linha explícitos \lambda_{\tau,2}^{(0)}, \dots, \lambda_{\tau,2}^{(3)}. A contagem de multiplicação é M_{\text{canon}}(4) = 4 = 2 \cdot 4 – 4correspondendo à fórmula geral.

Observe que \mu_1 não aparece: a primeira rodada nas folhas escalares é independente da semente, então o descritor reduzido para n = 2 contém apenas \mu_2 – exatamente 4(n-1) = 4 palavras de campo.

A consequência da interface

O avaliador T_{\tau,n} é um público F-mapa linear de F^N para F ^ 4. Um compromisso downstream ou camada de abertura pode interagir com este objeto de duas maneiras:

1. Consumir o descritor estruturado (\mu_2, \pontos, \mu_n) diretamente – 4(n-1) palavras de campo.

2. Materialize os quatro vetores de linha explícitos \lambda_{\tau,n}^{(k)} \in F^N – 4N palavras de campo.

A opção 2 é forçada sempre que a API de compromisso aceita apenas Vec linhas. A tabela a seguir mostra quanto isso custa na prática.

O padrão é claro. A expansão do descritor é executada em Sobre) tempo e permanece abaixo de 500 μs mesmo na profundidade 24. A materialização de linha é executada em SOBRE) tempo: na profundidade 20, já leva 637 ms e produz 128 MB de payload; na profundidade 24, leva 10,2 segundos e produz 2 GB.

Esta não é uma afirmação de dureza — as linhas podem ser calculadas em tempo linear a partir do descritor estruturado. É uma afirmação de interface: no momento em que uma camada downstream escolhe uma API somente de linha, a especialização logarítmica da semente é destruída. UM 4(n-1)-descritor de palavra que determina completamente o avaliador deve ser expandido em 4N coeficientes explícitos, convertendo um objeto de 92 palavras em uma carga útil de 2 GB em N = 2^{24}.

Qualquer camada downstream que queira preservar o Sobre)A especialização de palavras deve consumir o próprio descritor recíproco estruturado – ou algo equivalente a ele – em vez de apenas vetores de linha explícitos.

Nota de solidez

A nota também registra um resultado mínimo de solidez da teoria da informação. A transcrição da órbita determinística – para onde aponta a órbita pública r_1, \pontos, r_n são reutilizados como desafios sumcheck – é perfeitamente incorreto: um provador trapaceiro pode forçar a aceitação com probabilidade 1 para qualquer afirmação falsa. Isso vale porque r_i \notin \{0, 1\} dá ao provador graus de liberdade suficientes em cada rodada.

A correção é padrão: confirme a saída reivindicada y\em F^4 antes de ver um novo vetor de escalarização aleatória \rhoem seguida, execute sumcheck com novos desafios de verificador independente em F. Em um modelo oracle onde o verificador tem acesso exato à extensão multilinear da entrada no ponto amostral final, uma afirmação falsa y \neq T_{\tau,n}(x) é aceito com probabilidade no máximo (2n+1)/q.

Prova completa: Seção B da nota.

Perguntas abertas

1. Consumo de compromisso estruturado. Os esquemas de compromisso práticos (baseados em KZG, baseados em rede ou baseados em IPA) podem consumir o 4(n-1)-word descritor estruturado diretamente, sem materializar linhas explícitas?

2. Generalização de alto grau. O caso quártico é isolado aqui porque todas as identidades locais cabem de forma fechada. Para (E:F) > 4como cresce a complexidade do transporte e como persiste a vantagem da base móvel?

3. Impacto de ponta a ponta. Os benchmarks acima medem a aritmética em nível de kernel. Espera-se que grande parte da redução de multiplicação de 5× sobreviva uma vez incluídos o compromisso, a abertura e as despesas gerais do Fiat-Shamir?

Nota completa
CSV de referência
PoC