Análise dos princípios dos STARKs da Binius e considerações de otimização
1. Introdução
Uma das principais razões para a baixa eficiência dos STARKs é que a maioria dos valores nos programas reais é bastante pequena, mas, para garantir a segurança das provas baseadas em árvores de Merkle, ao usar a codificação de Reed-Solomon para expandir os dados, muitos valores redundantes adicionais ocupam todo o domínio, mesmo que o valor original em si seja muito pequeno. Para resolver esse problema, a redução do tamanho do domínio tornou-se uma estratégia chave.
A largura de codificação dos STARKs de 1ª geração é de 252 bits, a largura de codificação dos STARKs de 2ª geração é de 64 bits, e a largura de codificação dos STARKs de 3ª geração é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta uma grande quantidade de espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, com codificação compacta e eficiente sem qualquer espaço desperdiçado, ou seja, os STARKs de 4ª geração.
Comparado ao Gol