GKRFold: Compressão de prova GKR baseada em SumFold – zk-s(nt)arks

Masato Tsutsumi (Universidade Waseda) (X: neto)

versão mais recente: GKRFold: compressão de prova GKR baseada em SumFold – HackMD

Isenção de responsabilidade: Esta postagem está em um estágio inicial de ideia e as formulações lógicas e matemáticas podem não ser totalmente rigorosas. Agradecemos quaisquer comentários ou feedback sobre a ideia em si, bem como sugestões sobre a estrutura lógica.

Resumo

Neste artigo, apresentamos o GKRFold, um protocolo para compactar o tamanho da prova e o custo de verificação de n Provas SNARK baseadas em GKR. GKRFold incorpora SumFold – um componente originalmente proposto em NeutronNova (KS24) – para obter essa compactação. Em última análise, o processo de compactação produz uma única instância do Sumcheck junto com um compromisso. Como resultado, o verificador é obrigado a realizar apenas um Sumcheck e duas avaliações polinomiais aleatórias. Além disso, o protocolo é aplicável a instâncias uniformes e não uniformes do protocolo GKR.

1. Introdução

1.1. Protocolo GKR

O sistema de prova GKR (GKR15, XZZ19), um proeminente SNARK (Succinct Non-interactive ARgument of Knowledge) devido ao seu tempo de prova eficiente, tem sido empregado em sistemas como Expander e Ceno. Seu projeto é baseado na representação de cada camada do circuito como um polinômio da camada correspondente. A partir da saída, o protocolo retransmite sequencialmente uma afirmação sobre uma camada para uma afirmação sobre a camada subsequente, executando um protocolo Sumcheck na avaliação do polinômio da camada em um ponto escolhido aleatoriamente.

Mais precisamente, o polinômio da camada ( V_i ) é definido como

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ add_{i+1}(z,x,y)\bigl(V_{i+1}(x)+V_{i+1}(y)\bigr) + mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) \Bigr\},

onde as funções add_i(z,x,y) e mult_i(z,x,y) retorne 1 se o portão (z,x,y) em camada eu é uma porta de adição ou multiplicação, respectivamente, e 0 caso contrário.

Uma visão geral do protocolo GKR é a seguinte:

1. O provador envia a avaliação do circuito C(x,w)=y ao verificador.
2. Para cada camada eu = 1,\pontos,d-1 (excluindo a camada de entrada), o verificador lança um desafio selecionando um ponto aleatório r_i e então inicia o protocolo Sumcheck em V_i(r_i).
3. O verificador avalia diretamente a camada de entrada V_d(r_d).

Embora o provador possa gerar provas em SOBRE) tempo sem se comprometer com resultados intermediários ou depender de FFTs, o tempo de verificação e o tamanho da prova exibem uma complexidade de O(D\log N). Consequentemente, alcançar uma compressão de prova eficiente continua a ser um desafio importante.

1.2. NeutronNova e SumFold

SumFold, conforme introduzido em NeutronNova(KS24), é uma técnica que dobra um número arbitrário de instâncias de Sumcheck em uma única instância. Ao aplicar SumFold ao protocolo GKR, é possível compactar as múltiplas instâncias Sumcheck inerentes às provas GKR, reduzindo assim o tamanho geral da prova e o tempo de verificação.

1.3. Contribuições

Neste trabalho, propomos GKRFold, um novo método que aplica SumFold para compactar eficientemente n instâncias de provas GKR. As principais contribuições deste estudo são as seguintes:

1. Demonstramos que o SumFold pode ser utilizado de forma eficaz para compactar instâncias GKR, levando a melhorias substanciais no tamanho da prova e na eficiência da verificação.
2. Mostramos que GKRFold pode comprimir n Provas GKR, cada uma compreendendo d camadas (totalizando 6 \vezes n \vezes d instâncias Sumcheck), em uma única instância Sumcheck.

Este resultado reduz significativamente a sobrecarga associada à verificação de múltiplas provas GKR, tornando o protocolo mais prático para aplicações que requerem verificação sucinta e eficiente.

2. SumFold: ideia de alto nível

A explicação de MLE, Sumcheck e GKR é omitida aqui. Aqueles que desejam estudar os detalhes devem consultar os seguintes documentos.

Suponha que desejamos provar, via Sumcheck, uma função definida por uma composição

F(\vec{g}(x)),

onde F é um polinômio em t variáveis ​​e \vec{g} é um vetor de t polinômios em eu variáveis. Por exemplo, pode-se considerar o caso

F(\vec{g}(x)) = g_0(x) \cdot g_1(x) \cdots g_{t-1}(x),

que representa o produto dos componentes de \vec{g}(x).

O objetivo do SumFold é reduzir as provas de n Instâncias de verificação de soma

(T_i = \sum_x F(\vec{g}(x)))_{i \in (n)}

para uma única prova Sumcheck.

Definimos uma instância Sumcheck \mathsf{SC} que contém todas as informações necessárias para uma prova Sumcheck da seguinte forma:

SumFold dobra o n instâncias de \mathsf{SC} em um. A ideia principal por trás do SumFold consiste nas seguintes etapas:

1. Para todos eu = 1,\ldots,ndado

   T_i = \soma_x F(\vec{g}_i(x)),

   construir um polinômio Q(b) por interpolação tal que, para qualquer entrada b,

   Q(b) = T_b.

   Isto é conseguido da seguinte forma:

   • (a) Construir t polinômios f_j(b,x) via interpolação polinomial, onde cada polinômio gera g_{bj}(x) correspondente à $b$ésima instância.
   • (b) Reconstruir Q(b) aplicando a função F para a coleção \{f_1(b,x), \pontos, f_t(b,x)\}.
2. Comprometa-se com o polinômio Q(b). Este compromisso agrega efetivamente os compromissos de todos n Instâncias de verificação de soma.
3. O verificador seleciona um desafio aleatório r_b e designa a instância $r_b$th Sumcheck como a instância dobrada.

Verifica-se (ver Apêndice B do artigo NeutronNova (KS24)) que

Q(r_b) = T_{r_b}.

Protocolo (citado de (KS24)):

3. GKR Dobrar

3.0. Protocolo GKR Linear (Libra(XZZ19))

Nesta seção, descrevemos o algoritmo de tempo linear para o protocolo GKR. Primeiro, suponha que o seguinte polinômio de camada seja dado:

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} \Bigl\{ add_{i+1}(z,x,y)\bigl(V_{i+1}(x)+V_{i+1}(y)\bigr) + mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) \Bigr\}.

Particionamos esta expressão em três termos:

V_i(z) = \sum_{x,y \in \{0,1\}^{S_i}} add_{i+1}(z,x,y)V_{i+1}(x) \;+\;

\sum_{x,y \in \{0,1\}^{S_i}} add_{i+1}(z,x,y)V_{i+1}(y) \;+\;

\sum_{x,y \in \{0,1\}^{S_i}} mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr).

Para cada termo, um protocolo Sumcheck bifásico é executado. Por exemplo, considere o terceiro termo:

\sum_{x,y \in \{0,1\}^{S_i}} mult_{i+1}(z,x,y)\bigl(V_{i+1}(x) \cdot V_{i+1}(y)\bigr) =\sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)V_{i+1}(x),

onde

h_{i+1}(x) = \sum_{y \in \{0,1\}^{S_i}} mult_{i+1}(z,x,y)V_{i+1}(y).

O protocolo Sumcheck bifásico é então executado da seguinte forma:

1. Prove a correção de h_{i+1}(x) via Sumcheck.
2. Prove a exatidão do termo \sum_{x \in \{0,1\}^{S_i}} h_{i+1}(x)V_{i+1}(x) via Sumcheck.

Assim, para cada camada, um total de 2 \ vezes 3 = 6 As instâncias Sumcheck são executadas em paralelo.

3.1. GKRFold: Visão geral

Suponha que nos seja dado n Instâncias GKR, e que cada instância compreende d camadas. Então existe um total de n \vezes d polinômios de camada. Para cada camada, o protocolo requer 6 instâncias Sumcheck (conforme descrito acima), resultando em um total de

6 \vezes n \vezes d

Instâncias de verificação de soma.

Esses seis tipos de instâncias Sumcheck estão resumidos na tabela a seguir:

Observe que Sumcheck 1 e Sumcheck 2 têm naturalmente a forma

F(g_1(x)) = g_1(x).

No entanto, ao introduzir a função identidade constante g_e(x) = 1 (que sempre retorna 1), eles podem ser expressos de forma equivalente como

F(g_1(x), g_e(x)) = g_1(x) \cdot g_e(x).

Assim, todas as instâncias do Sumcheck compartilham a mesma forma funcional

F(g_1(x), g_2(x)) = g_1(x) \cdot g_2(x).

A correspondência entre essas instâncias do Sumcheck e a estrutura SumFold é fornecida na tabela acima.

Consequentemente, aplicando SumFold, o total de

6 \vezes n \vezes d

As instâncias Sumcheck podem ser dobradas em uma única instância Sumcheck.

3.2. GKRFold: Protocolo

Entrada:
n Instâncias GKR, representadas como

\Bigl\{\{SC_{i1}, SC_{i2}, SC_{i3}, SC_{i4}, SC_{i5}, SC_{i6}\}_{i \in (n \times d)},\, (\vec{x}_i, \vec{w}_i)_{i \in (n \times d)},\, (\vec{u}_i)_{i \in (n \times d)}\Bigr\} \in GKR^{n},

Saída:
(SC,\, r_b,\, \bar{Q}(r_b),(\vec{x}_i, \vec{w}_i), (\vec{u}_i))

Protocolo:

1. O provador envia os resultados da avaliação C_i(x,w) = y para cada instância ao verificador.

2. Com base nos polinômios da camada V_iatribua as seis instâncias do Sumcheck (SC1 a SC6) para cada camada.

3. Execute SumFold nas seguintes condições:

   • A função é definida como

     F(g_1(x), g_2(x)) = g_1(x) \cdot g_2(x).

   • O vetor \vec{g} é instanciado da seguinte forma:

     • SC$_1$: \{ add_{i+1}(z,x,y),\, g_e(x,y,z) \}
     • SC$_2$: \{ add_{i+1}(z,x,y),\, g_e(x,y,z) \}
     • SC$_3$: \{ mult_{i+1}(z,x,y),\, V_{i+1}(y) \}
     • SC$_4$: \{ h_{1,i+1}(x),\, V_{i+1}(x) \}
     • SC$_5$: \{ h_{2,i+1}(y),\, V_{i+1}(y) \}
     • SC$_6$: \{ h_{3,i+1}(x),\, V_{i+1}(x) \}

4. Verifique isso para todos eu = 1, \pontos, n,

   Q(6d \cdot i) = v_{i,d}(r_d),

   onde P é o polinômio construído via SumFold e v_{i,d}(r_d) denota a avaliação do polinômio da camada correspondente no desafio r_d.

5. O verificador avalia a camada de entrada V_d(r_d).

3.3. Prova do Teorema

Descreveremos os detalhes em um artigo posterior, mas deve ser possível provar que as propriedades de completude, solidez e conhecimento zero são satisfeitas de acordo com SumFold.

3.4. Custo

Deixar

• d denotar o número de camadas GKR,
• t = 2 denota o número de variáveis ​​​​em F,
• D denotar o grau de F,
• n denota o número de instâncias GKR, e
• eu denota o número de variáveis ​​​​em g.

As complexidades estão resumidas na tabela a seguir:

Seguindo o Teorema 2 no artigo NeutronNova (KS24):

Reconhecimento

Agradecimentos especiais a yugo por discutir a recursão do GKR durante o hackathon e fornecer feedback sobre ideias nos estágios iniciais desta pesquisa.

Referência

1. KS24
2. GKR15
3. XZZ19