Análise dos princípios STARKs da Binius e reflexões sobre a sua otimização
1 Introdução
Ao contrário dos SNARKs baseados em curvas elípticas, os STARKs podem ser vistos como SNARKs baseados em hash. Atualmente, uma das principais razões para a ineficiência dos STARKs é que, na maioria dos programas práticos, a maioria dos valores numéricos é bastante pequena, como índices de loop, valores booleanos, contadores, etc. No entanto, para garantir a segurança da prova baseada em árvore Merkle, ao usar a codificação de Reed-Solomon para expandir os dados, muitos valores redundantes ocupam todo o domínio, mesmo que os valores originais sejam pequenos. Para resolver esse problema, reduzir o 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 de 2ª geração é de 64 bits, e a de 3ª geração é de 32 bits, mas a codificação de 32 bits ainda tem muito espaço desperdiçado. Em comparação, o domínio binário permite operações diretas sobre os bits, tornando a codificação compacta e eficiente, sem desperdício, podendo ser considerada a 4ª geração dos STARK.