nonnative
v0.3.0
La biblioteca nonnative proporciona restricciones R1CS para verificar cálculos en un campo no nativo en un sistema de prueba.
La biblioteca se basa en el marco de escritura de restricciones arkworks-rs y se publica bajo la licencia MIT y la licencia Apache v2 (ver Licencia).
ADVERTENCIA: Este es un prototipo de prueba de concepto académico; en particular, no ha recibido una revisión cuidadosa del código. Esta implementación NO está lista para su uso en producción.
Esta biblioteca implementa un dispositivo de campo para un campo principal Fp sobre otro campo principal Fq donde p != q .
Cuando escribimos sistemas de restricciones para muchas pruebas criptográficas, estamos restringidos a un campo nativo (por ejemplo, el campo escalar de la curva compatible con el emparejamiento). Esto puede resultar inconveniente; por ejemplo, la composición recursiva de pruebas mediante ciclos de curvas requiere que el verificador calcule sobre un campo no nativo.
La biblioteca permite escribir cálculos en un campo no nativo de la misma manera que se escribirían cálculos en el campo nativo. Naturalmente, esto introduce una sobrecarga adicional, que minimizamos mediante una variedad de optimizaciones.
Debido a que el campo no nativo implementa el rasgo FieldVar en arkworks, podemos tratarlo como una variable de campo nativo ( FpVar ).
Podemos realizar las operaciones de campo estándar, como + , - y * . Vea el siguiente ejemplo:
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 ) ? ; Después de cada multiplicación, nuestra biblioteca realiza internamente una operación de reducción , que reduce un tipo intermedio NonNativeFieldMulResultVar al tipo normalizado NonNativeFieldVar . Esto permite al usuario realizar sin problemas una secuencia de operaciones sin preocuparse por los detalles subyacentes.
Sin embargo, esta operación es cara y, en ocasiones, evitable. Podemos reducir la cantidad de restricciones utilizando este tipo intermedio, que solo admite adiciones. Para multiplicar, se debe reducir nuevamente a NonNativeFieldVar . Vea a continuación un ejemplo de esqueleto.
Para calcular a * b + c * d , la implementación sencilla (pero más costosa) es la siguiente:
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
Esto realiza dos operaciones de reducción en total, una para cada multiplicación.
Podemos ahorrar una reducción usando NonNativeFieldMulResultGadget , de la siguiente manera:
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()?;
Realiza solo una operación de reducción y es aproximadamente 2 veces más rápido que la primera implementación.
La biblioteca emplea la idea estándar de utilizar múltiples miembros para representar un elemento del campo objetivo. Por ejemplo, un elemento en TargetField puede estar representado por tres elementos BaseField (es decir, las extremidades).
TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
Después de algunos cálculos, las extremidades se sobrecargan y es necesario reducirlas para poder realizar más cálculos.
Utilizamos mucho las técnicas de optimización en [KPS18] y [OWWB20]. Ambos trabajos tienen sus propias bibliotecas de código abierto: xJsnark y bellman-bignat. En comparación con ellas, esta biblioteca funciona con el entorno arkworks y también está optimizada para la densidad en lugar del número de restricciones, lo cual es útil para pruebas holográficas de conocimiento cero como Marlin.
La biblioteca tiene licencia bajo cualquiera de las siguientes licencias, a su discreción.
A menos que indique explícitamente lo contrario, cualquier contribución que usted envíe para su inclusión en esta biblioteca tendrá una licencia dual como se indica arriba (como se define en la licencia Apache v2), sin términos ni condiciones adicionales.
[KPS18]: AE Kosba, C. Papamanthou y E. Shi. "xJsnark: un marco para una computación verificable eficiente", en Actas del 39º Simposio sobre Seguridad y Privacidad , ser. S&P '18, 2018, págs. 944–961.
[OWWB20]: A. Ozdemir, RS Wahby, B. Whitehat y D. Boneh. "Escalar la computación verificable utilizando acumuladores de conjuntos eficientes", en Actas del 29º Simposio de seguridad de USENIX , ser. Seguridad '20, 2020.
