nonnative
v0.3.0
A biblioteca nonnative fornece restrições R1CS para verificar cálculos em um campo não nativo em um sistema de prova.
A biblioteca é baseada na estrutura de escrita de restrições arkworks-rs e é lançada sob a licença MIT e a licença Apache v2 (consulte Licença).
AVISO: Este é um protótipo de prova de conceito acadêmico; em particular, não recebeu uma revisão cuidadosa do código. Esta implementação NÃO está pronta para uso em produção.
Esta biblioteca implementa um gadget de campo para um campo principal Fp sobre outro campo principal Fq onde p != q .
Ao escrever sistemas de restrição para muitas provas criptográficas, ficamos restritos a um campo nativo (por exemplo, o campo escalar da curva amigável ao emparelhamento). Isto pode ser inconveniente; por exemplo, a composição recursiva de provas por meio de ciclos de curvas exige que o verificador calcule sobre um campo não nativo.
A biblioteca torna possível escrever cálculos sobre um campo não nativo da mesma forma que escreveríamos cálculos sobre o campo nativo. Isso naturalmente introduz sobrecarga adicional, que minimizamos usando uma variedade de otimizações.
Como o campo não nativo implementa a característica FieldVar no arkworks, podemos tratá-lo como uma variável de campo nativa ( FpVar ).
Podemos fazer as operações de campo padrão, como + , - e * . Veja o exemplo a seguir:
let a = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "a" ) , || Ok ( a_value ) ) ? ;
let b = NonNativeFieldVar :: < Fr , Fq > :: new_witness ( ns ! ( cs, "b" ) , || Ok ( b_value ) ) ? ;
// add
let a_plus_b = & a + & b ;
// sub
let a_minus_b = & a - & b ;
// multiply
let a_times_b = & a * $b ;
// enforce equality
a . enforce_equal ( & b ) ? ; Após cada multiplicação, nossa biblioteca executa internamente uma operação de redução , que reduz um tipo intermediário NonNativeFieldMulResultVar ao tipo normalizado NonNativeFieldVar . Isso permite que um usuário execute perfeitamente uma sequência de operações sem se preocupar com os detalhes subjacentes.
No entanto, esta operação é dispendiosa e por vezes evitável. Podemos reduzir o número de restrições usando este tipo intermediário, que suporta apenas adições. Para multiplicar, deve ser reduzido para NonNativeFieldVar . Veja abaixo um exemplo de esqueleto.
Para calcular a * b + c * d , a implementação simples (mas mais cara) é a seguinte:
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
Isso executa duas operações de redução no total, uma para cada multiplicação.
Podemos economizar uma redução usando NonNativeFieldMulResultGadget , da seguinte forma:
let a_times_b = a.mul_without_reduce(&b)?;
let c_times_d = c.mul_without_reduce(&d)?;
let res = (&a_times_b + &c_times_d)?.reduce()?;
Ele executa apenas uma operação de redução e é aproximadamente 2x mais rápido que a primeira implementação.
A biblioteca emprega a ideia padrão de usar vários membros para representar um elemento do campo de destino. Por exemplo, um elemento no TargetField pode ser representado por três elementos BaseField (isto é, os membros).
TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
Depois de alguns cálculos, os membros ficam sobrecarregados e precisam ser reduzidos , para poder realizar mais cálculos.
Usamos fortemente as técnicas de otimização em [KPS18] e [OWWB20]. Ambas as obras possuem suas próprias bibliotecas de código aberto: xJsnark e bellman-bignat. Comparada com eles, esta biblioteca funciona com o ambiente arkworks e também é otimizada para densidade em vez de número de restrições, o que é útil para provas holográficas de conhecimento zero como Marlin.
A biblioteca está licenciada sob qualquer uma das seguintes licenças, a seu critério.
A menos que você declare explicitamente o contrário, qualquer contribuição enviada por você para inclusão nesta biblioteca deverá ser licenciada duplamente conforme acima (conforme definido na Licença Apache v2), sem quaisquer termos ou condições adicionais.
[KPS18]: AE Kosba, C. Papamanthou e E. Shi. "xJsnark: uma estrutura para computação verificável eficiente", em Anais do 39º Simpósio sobre Segurança e Privacidade , ser. S&P '18, 2018, pp.
[OWWB20]: A. Ozdemir, RS Wahby, B. Whitehat e D. Boneh. "Escalonando computação verificável usando acumuladores de conjunto eficientes", em Anais do 29º Simpósio de Segurança USENIX , ser. Segurança '20, 2020.
