lurk-lab / arecibo

An advanced fork of Nova
https://lurk-lang.org/
MIT License
65 stars 27 forks source link

[Zeromorph] Avoid decompressing G2 points #91

Open storojs72 opened 8 months ago

storojs72 commented 8 months ago

Zeromorph verification executes pairing check with the input composed in the following way:

let pi = proof.pi;
let pairing_inputs = [
   (&c, &(-vk.s_offset_h).into()),
   (
     &pi,
     &(E::G2::from(vk.vp.beta_h) - (vk.vp.h * x))
       .to_affine()
       .into(),
   )
];

where vk.s_offset_h, vk.vp.beta_h and vk.vp.h are G2 points. In serialised form, compressed G2 points are represented as 64 bytes:

. . .
"vk_ee":{
   "vp":{
   "g":"2c6a92f8691642e6f4830e904e7c33b3b08e943e732154eca7897cd354a9bd59",
   "h":"40fe7193ec3e7adb474a338a8b55aefd065fd1d038cb80934ea313ec1c66762f9d6606bfcfb440ce81e306136d092e3e5302b422925129d2b71e80fe39bde614",
   "beta_h":"5fb81e39772b0e58a3c2620c694a22c50a7802245255b751f6896a174ba6852e851461a2fb9e5894d095827dd6b0e424d4622c5a8d2ee3a07c84bbb1e130a665"
   },
   "s_offset_h":"5fb81e39772b0e58a3c2620c694a22c50a7802245255b751f6896a174ba6852e851461a2fb9e5894d095827dd6b0e424d4622c5a8d2ee3a07c84bbb1e130a665"
}
. . .

Pairing check on Solidity side (Ethereum's precompile) requires input in specific form, where G2 points are decompressed. Decompressing points on Solidity side is just wasting gas, since it is not actually a useful computation required to be performed on-chain.

Can we update the CompressedSNARK and VerifierKey structures serialisation - to store G2 points in uncompressed form (and exclude implicit decompression from implementation of the reference verifier)?

Probably related to https://github.com/lurk-lab/solidity-verifier/issues/40

huitseeker commented 7 months ago

while I'm pretty sure we won't make our proof use compressed points, this note on deserialization matters: https://github.com/privacy-scaling-explorations/halo2curves/issues/109#issuecomment-1849702276