Análise dos princípios dos STARKs da Binius e reflexões sobre a sua otimização
1 Introdução
Um dos principais motivos para a baixa eficiência dos STARKs é que a maioria dos valores em programas reais é relativamente pequena, como índices em loops for, valores booleanos, contadores, etc. No entanto, para garantir a segurança das provas baseadas em árvores de Merkle, ao usar 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, reduzir o tamanho do domínio se tornou uma estratégia chave.
A largura de codificação da primeira geração de STARKs é de 252 bits, a largura de codificação da segunda geração de STARKs é de 64 bits, e a largura de codificação da terceira geração de STARKs é de 32 bits, mas a largura de codificação de 32 bits ainda apresenta um grande desperdício de espaço. Em comparação, o domínio binário permite operações diretas em bits, com codificação compacta e eficiente, sem desperdício arbitrário de espaço.