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

Muito longo; Para ler

People Mentioned

Company Mentioned

Coin Mentioned

@sin7y

HISTÓRIAS RELACIONADAS