Dê um mergulho profundo na árvore Verkle para Ethereum

Comparado ao Merkle Tree, o Verkle Tree foi muito melhorado no tamanho da prova como uma parte crítica da atualização do ETH2.0. Quando se trata de dados com o tamanho de um bilhão, a prova Merkle Tree levará 1kB, enquanto a prova Verkle Tree não precisa de mais de 150 bytes.

O conceito Verkle Tree foi proposto em 2018 (mais detalhes podem ser encontrados aqui ). A 23ª análise técnica da Sin7Y demonstrará o princípio da Verkle Tree.

Merkle Tree

Antes de mergulhar na Árvore Verkle, é importante entender o conceito da Árvore Merkle. Merkle Tree é um Acumulador comum, que pode ser usado para provar que existe um elemento no Acumulador conforme mostrado na figura a seguir:

Para provar que (chave: valor) = (06: 32) existe na Árvore (marcado em verde), a Prova deve conter todos os nós marcados em vermelho na figura.

O verificador pode calcular a Raiz de acordo com o método mostrado na Figura 1 e depois compará-la com a Raiz esperada (marcada em cinza).

É previsível que, com a profundidade e a largura da árvore aumentando, o tamanho da prova também será maior (para branched-2, a complexidade é log_2(n) , enquanto para branched-k, é (k−1)log_k (n) .

Além disso, o verificador precisa realizar um grande número de cálculos de Hash desde o nível básico até o nível superior. Assim, o aumento da profundidade e largura da Árvore leva ao aumento da carga de trabalho do verificador, o que é inaceitável.

Verkle Tree - Conceito

Simplesmente aumentar a largura da Árvore pode reduzir sua profundidade, mas o tamanho da prova não será reduzido porque o tamanho da prova muda do log_2(n) original para (k−1)log_k(n) .

Ou seja, para cada camada, o provador precisa fornecer (k−1) informações adicionais do nó. No artigo Verkle Tree, John Kuszmaul mencionou um esquema para reduzir a complexidade da prova para logk(n) .

Se definirmos k=1024 , a prova será reduzida em log_2(k) = 10 vezes .

O design da Árvore Verkle é mostrado a seguir:

Para cada nó, existem duas informações: (1) valor; (2) prova de existência π . Por exemplo, o marcado em verde (H(k,v),π_03) mostra que H(k,v) existe no compromisso C_0 e π_03 é a prova desse argumento.

Da mesma forma, (C_0,π_0) significa que C_0 existe no compromisso C_Root e π_0 é a prova desse argumento.

No artigo Verkle Tree, o método de tal compromisso de existência é chamado de compromisso vetorial . Se o esquema de compromisso Vector for usado para executar o compromisso de existência para os dados originais, a Prova com complexidade O(1 ) será obtida enquanto a complexidade da Prova de Construção e a da Prova de atualização são O(n^2),O(n) respectivamente.

Portanto, para encontrar um equilíbrio, o esquema K-ary Verkle Tree é usado no papel Verkle Tree (como mostrado na Figura 2) para tornar a complexidade da construção Proof, update Proof e Proof ser O(kn),O(klogk n ),O(logk n) respectivamente.

A comparação de desempenho específico é mostrada na Tabela 1:

Neste artigo, não pretendemos fornecer uma introdução detalhada a alguns esquemas específicos de comprometimento de vetores, que John Kuszmaul explicou bem em seu artigo.

Felizmente, em comparação com o compromisso vetorial, temos uma ferramenta mais eficiente chamada compromisso polinomial.

Dado um grupo do conjunto de coordenadas (c_0,c_1,....,c_n) e um conjunto de valores (y_1,y_2,....,y_n) , você pode construir um polinômio ( interpolação de Lagrange ), satisfazendo P(c_i )=y_i e conduza um compromisso com este polinômio.

KZG10 e IPA são esquemas comuns de compromisso polinomial (neste ponto, o compromisso é um ponto na curva elíptica, geralmente entre 32 e 48 bytes de tamanho).

Base

KZG para ponto único

Tome KZG10 como exemplo. Para o polinômio P(x) , usamos [P(s)]_1 para representar o compromisso polinomial.

Como todos sabemos, para P(x) , se P(z)=y , então (x−z)|(P(x)−y) . Ou seja, se definirmos Q(x)=(P (x)−y)/(x−z) , então Q(x) é um polinômio.

Agora, geramos uma prova para P(x)P(x) para satisfazer P(z)=yP(z)=y. Ou seja, calcule [Q(s)]1[Q(s)]1 e envie para o verificador, que precisa verificar:

Como s é um ponto escolhido aleatoriamente no domínio finito F, a probabilidade do comportamento maligno bem-sucedido do provador é grau(Q)/P ( lema de Schwartz–Zippel ).

KZG para pontos múltiplos

Agora, queremos provar que os valores do polinômio P(x) em (z0,z1,....,zk−1) são (y1,y2,....,yk−1) , respectivamente. Portanto, precisamos definir dois polinômios:

De acordo com a descrição acima, precisamos satisfazer V(x)|(P(x)−I(x)) . Ou seja, existe um polinômio Q(x) , satisfazendo:

Portanto, o Provedor precisa fornecer os compromissos [P(s)]_1,[Q(s)]_1 para P(x) e Q(x) e enviar os compromissos ao verificador.

O verificador calcula [I(s)]_1,[V(s)]_2 localmente e verifica a equação:

É claro que o tamanho da prova é constante, não importa quantos pontos existam. Se escolhermos a curva BLS12-381, o tamanho da prova é de apenas 48 bytes, o que é muito eficiente.

Verkle Tree - ETH

Comparado ao Merkle Tree, no qual para provar a existência de um elemento, o provador ainda precisa fornecer a prova com tamanho O(log_2n) , o Verkle Tree fez uma grande melhoria no tamanho da prova.

Vamos verificar um exemplo simples de Verkle Tree.

Pode-se ver que, semelhante à estrutura da Merkle Patricia Tree, os nós podem ser divididos em três tipos - nó vazio, nó interno e nó folha.

A largura de cada árvore de nó interno é 16 (0000->1111 em hexadecimal). Para provar que o estado do nó folha é (0101 0111 1010 1111 -> 1213), precisamos realizar o compromisso com o nó interno A e o nó interno B:

1. Prove que o valor do compromisso do nó interno B é hash (0101 0111 1010 1111, 1213) no índice 1010.

   
   

2. Prove que o valor do compromisso do nó interno A é hash (cm_B) no índice 0111.

   
   

3. Prove que o valor do compromisso do nó Raiz é hash (cm_A) no índice 0101;

Use C_0(InnernodeB),C_1(InnernodeA),C_2(Root) para representar os compromissos mencionados acima e correspondê-los ao polinômio f_i(x) respectivamente.

Portanto, o Provedor precisa provar:

Comprimir para vários polígonos

Para facilitar, usaremos z_i para representar o índice.

O provador precisa provar que para o conjunto polinomial f_0(x),f_1(x),....,f_m−1(x) , ele satisfaz as seguintes condições nos pontos z_0,z_1,....,z_m− 1 , respectivamente:
De acordo com a descrição anterior (KZG para Single point), para cada polinômio, existe um polinômio quociente satisfazendo:
O provador precisa realizar o compromisso com o polinômio original e o polinômio quociente e enviá-lo ao verificador:

O verificador executa a verificação:
É óbvio que não queremos que o verificador execute tantas operações de emparelhamento (é caro). Portanto, precisamos executar um Compress da seguinte maneira.

Gere alguns números aleatórios r_0,r_1,....,r_m−1 e reúna os polinômios quocientes acima:
Suponha que se e somente se cada q_i(x) for um polinômio, g(x) será um polinômio (a probabilidade de que as frações entre q_i(x ) se desloquem exatamente é muito baixa por causa dos números aleatórios).

O provador realiza o compromisso com o polinômio g(x) e envia [g(s)]_1 ao verificador.

Em seguida, deixe o verificador acreditar que [g(s)]_1 é o compromisso com o polinômio g(x) .

Observe a forma do polinômio g(x)g(x), que pode ser escrita como:

Escolha um valor tt aleatoriamente e há:

Defina o polinômio:

O seu compromisso pode ser calculado com o seguinte método:

Então o valor do polinômio h(x)−g(x)h(x)−g(x) no ponto tt é:

Calcule o quociente polinomial q(x)=(h(x)−g(x)−y)/(x−z) .

Calcule o compromisso π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1 e envie para o verificador.

O verificador realiza a seguinte verificação:

1. Calcular

   

2. Verificar

   

Propriedades principais

1. Qualquer número de pontos pode ser provado usando este esquema sem alterar o tamanho da Prova. (Para cada compromisso, há uma prova π .)

   
   

2. O valor de y_i não precisa ser fornecido explicitamente, pois é o hash do próximo valor da camada.

   
   

3. O valor de x_i não precisa ser fornecido explicitamente, pois pode ser julgado por Key.

   
   

4. A informação pública utilizada inclui o par chave/valor a ser comprovado e os compromissos correspondentes desde o nível básico até o nível superior.

Referências

1. Dankrad Feist, “PCS multiproofs using random assessment,” https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html , acessado: 2022-05-10.

   
   

2. Vitalik Buterin, “Verkle tree,” https://vitalik.ca/general/2021/06/18/verkle.html , acessado: 2022-05-10.

   
   

3. John Kuszmaul, “Verkle Trees,” https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf , acessado: 2022-05-10.