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   ). A 23ª análise técnica da Sin7Y demonstrará o princípio da Verkle Tree. aqui   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 é   , enquanto para branched-k, é   . log_2(n) (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   original para   . log_2(n) (k−1)log_k(n)  Ou seja, para cada camada, o provador precisa fornecer   informações adicionais do nó. No artigo Verkle Tree, John Kuszmaul mencionou um esquema para reduzir a complexidade da prova para   . (k−1) logk(n)  Se definirmos   , a prova será reduzida em   . k=1024 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   mostra que   existe no compromisso   e   é a prova desse argumento. π (H(k,v),π_03) H(k,v) C_0 π_03  Da mesma forma,   significa que   existe no compromisso   e   é a prova desse argumento. (C_0,π_0) C_0 C_Root π_0  No artigo Verkle Tree, o método de tal compromisso de existência é chamado de   . Se o esquema de compromisso Vector for usado para executar o compromisso de existência para os dados originais, a Prova com complexidade   ) será obtida enquanto a complexidade da Prova de Construção e a da Prova de atualização são   respectivamente. compromisso vetorial O(1 O(n^2),O(n)  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   respectivamente. O(kn),O(klogk n ),O(logk n)  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   e um conjunto de valores   , você pode construir um polinômio (   ), satisfazendo   e conduza um compromisso com este polinômio. (c_0,c_1,....,c_n) (y_1,y_2,....,y_n) interpolação de Lagrange P(c_i )=y_i    e   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). KZG10 IPA   Base   KZG para ponto único  Tome KZG10 como exemplo. Para o polinômio   , usamos   para representar o compromisso polinomial. P(x) [P(s)]_1  Como todos sabemos, para   , se   , então   . Ou seja, se definirmos   , então   é um polinômio. P(x) P(z)=y (x−z)|(P(x)−y) Q(x)=(P (x)−y)/(x−z) Q(x)  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   em   são   , respectivamente. Portanto, precisamos definir dois polinômios: P(x) (z0,z1,....,zk−1) (y1,y2,....,yk−1)  De acordo com a descrição acima, precisamos satisfazer   . Ou seja, existe um polinômio   , satisfazendo: V(x)|(P(x)−I(x)) Q(x)  Portanto, o Provedor precisa fornecer os compromissos   para   e   e enviar os compromissos ao verificador. [P(s)]_1,[Q(s)]_1 P(x) Q(x)  O verificador calcula   localmente e verifica a equação: [I(s)]_1,[V(s)]_2  É 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 Verkle Tree fez uma grande melhoria no tamanho da prova. O(log_2n)  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:  Prove que o valor do compromisso do nó interno B é hash (0101 0111 1010 1111, 1213) no índice 1010.  Prove que o valor do compromisso do nó interno A é hash (cm_B) no índice 0111.  Prove que o valor do compromisso do nó Raiz é hash (cm_A) no índice 0101;  Use   para representar os compromissos mencionados acima e correspondê-los ao polinômio   respectivamente. C_0(InnernodeB),C_1(InnernodeA),C_2(Root) f_i(x)  Portanto, o Provedor precisa provar:   Comprimir para vários polígonos  Para facilitar, usaremos   para representar o índice. z_i  O provador precisa provar que para o conjunto polinomial   , ele satisfaz as seguintes condições nos pontos   , 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: f_0(x),f_1(x),....,f_m−1(x) z_0,z_1,....,z_m− 1  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   e reúna os polinômios quocientes acima:  Suponha que se e somente se cada   for um polinômio,   será um polinômio (a probabilidade de que as frações entre   ) se desloquem exatamente é muito baixa por causa dos números aleatórios). r_0,r_1,....,r_m−1 q_i(x) g(x) q_i(x  O provador realiza o compromisso com o polinômio   e envia   ao verificador. g(x) [g(s)]_1  Em seguida, deixe o verificador acreditar que   é o compromisso com o polinômio   . [g(s)]_1 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   e envie para o verificador. π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1  O verificador realiza a seguinte verificação:   Calcular   Verificar   Propriedades principais  Qualquer número de pontos pode ser provado usando este esquema sem alterar o tamanho da Prova. (Para cada compromisso, há uma prova   .) π  O valor de   não precisa ser fornecido explicitamente, pois é o hash do próximo valor da camada. y_i  O valor de   não precisa ser fornecido explicitamente, pois pode ser julgado por Key. x_i  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  Dankrad Feist, “PCS multiproofs using random assessment,”   , acessado: 2022-05-10. https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html  Vitalik Buterin, “Verkle tree,”   , acessado: 2022-05-10. https://vitalik.ca/general/2021/06/18/verkle.html  John Kuszmaul, “Verkle Trees,”   , acessado: 2022-05-10. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf

Ethereum

Twitter

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Este áudio é produzido no idioma original da história!

Muito longo; Para ler

Dê um mergulho profundo na árvore Verkle para Ethereum

Dê um mergulho profundo na árvore Verkle para Ethereum

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

De fóruns a feeds: como os algoritmos de mídia social moldam a interação digital

Guia do arquiteto para construir arquitetura de referência para um Datalake de IA/ML

Criando produtos criptográficos centrados no usuário: a importância do feedback do cliente

Aumente sua produtividade com estas 18 ferramentas para desenvolvedores 🚀🔥

De fóruns a feeds: como os algoritmos de mídia social moldam a interação digital

Guia do arquiteto para construir arquitetura de referência para um Datalake de IA/ML

Criando produtos criptográficos centrados no usuário: a importância do feedback do cliente

Aumente sua produtividade com estas 18 ferramentas para desenvolvedores 🚀🔥

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps