Specify proof format

[daira]

The current spec and the paper say 288 bytes (2304 bits), but the output of the prover says "Proof size in bits: 2294". I think the prover output is just not taking into account some padding up to byte boundaries, but it needs checking.

[daira]

Ugh. I cannot check this because the design totally obscures the length. The serialization of the proof in PourTransaction is here, which ends up delegating to libsnark here. That appears to be using an encoding that includes newlines, which doesn't seem right. (See also zcash/zcash#799 .)

[ebfull]

The serialization of a proof roughly looks like this:

0 17612361513530480674378975179266709127269922021928487126876489869237656992009 14563544828503275026048991934680479317531683523228555628088175785737578997456 0 11665967180809316837427172704428012177275570009999287251519313751178052523706 3825373665115248789987827008808607959843660840532075779037655603563733546915 0 1512944644096709666994701772951134712539877442829639331390027099537831460178 21108588009879674453301517694741570678409821320758047333783692090898316267033 6988771373265295709746458064530366661173858709561975813746940462364398843130 3169016985223199348589162548753306601097946367607036445333017869956148759245 0 481496066089698400755384776793745449266501609594604824583114106624323887040 9928273969256303692670114653525023050250725149635554952572462510297006788637 0 5421360068365057424705314379215839041722198801513594160961446793767886379086 13746799995415326012942485049866215646731785753918612959961443041141371138759 0 1626115502709902917532651531135719024120735939505500757899977602641503798569 8287120659242942099183107878456833312343423238284209384440961211361591440229 0 4190862787284536895552904039578020440571299203849094832580731602301093995735 16204895273540348629993474763179292469369137774985407822294548468823304453782 0 11768150195926159655449736485498370273979206657314024160932865307617829277606 6626169680254995735688599247854239437008063298207297895562483516714205453335

This appears to be 9 points on the curve, which can be compressed to 288 bytes with point compression and binary serialization.

[ebfull]

I enabled point compression and binary serialization and got a proof string with this (hex):

305e7269292fe1761bfc9d74cf5126dbf1376f9bb1457d1aac7c50144cf1d15f10312030cdec6c5cc0d88c52755f6a06dd8c869b6817d8ffb3b9c2500a4ae6bf1809ba1a300a3040c5d5aaeebbdab4ca5b18d8c158d356d338d142e0892e9d84d10b72a7356e1cca813890c45f8db483fbefab584496e6fee0992b7bcf6523506097877cd6af1d3120309864aa21c182cd7da0b3db151d3324fd235628d6fc4bdd8bd7b6501e25db6c2d300a30084cfd3634d6c25ace337554b016eef57c16b84e799d22904c248078e097372c30203088083a31849433031cd0133922676ca0ffeb70c00699a3be29943d7b6fe95509300a300e2e443974b7d08951f9a6993706f3e4733f947f6c1d577cd57112809f6fbb1d310a30ce8d66003b5a14487bc929ee195a392afeecdd75514d3b2e4166c4fc025e7c27310a

That's 321 bytes.

[daira]

Now I'm confused as to which proof system we're using. A BCG+13 proof is 322 bytes: "Given σ and (x, a) in the relation R_C, the SNARK prover outputs a proof consisting of 12 group elements (11 in G₁ and 1 in G₂). The proof length is 2576 bits (322 bytes)." But that's for an 80-bit security level. I thought Zerocash was using a different proof system (BCTV14), in which a proof has 7 G₁ elements and 1 G₂ element (see Figure 10 of that paper), and is 288 bytes for a 128-bit security level.

[daira]

OK, we're definitely using BCTV14 because there are 8 elements in the text serialization. (The third point is from G₂ and is twice as long.) Not sure where the extra 33 bytes came from.

[daira]

Are you sure it's 321 bytes? I make that string 312 bytes:

>>> len("305e7269292fe1761bfc9d74cf5126dbf1376f9bb1457d1aac7c50144cf1d15f10312030cdec6c5cc0d88c52755f6a06dd8c869b6817d8ffb3b9c2500a4ae6bf1809ba1a300a3040c5d5aaeebbdab4ca5b18d8c158d356d338d142e0892e9d84d10b72a7356e1cca813890c45f8db483fbefab584496e6fee0992b7bcf6523506097877cd6af1d3120309864aa21c182cd7da0b3db151d3324fd235628d6fc4bdd8bd7b6501e25db6c2d300a30084cfd3634d6c25ace337554b016eef57c16b84e799d22904c248078e097372c30203088083a31849433031cd0133922676ca0ffeb70c00699a3be29943d7b6fe95509300a300e2e443974b7d08951f9a6993706f3e4733f947f6c1d577cd57112809f6fbb1d310a30ce8d66003b5a14487bc929ee195a392afeecdd75514d3b2e4166c4fc025e7c27310a")/2.0
312.0

[ebfull]

I may have mismathed.

[ebfull]

I implemented point compression and binary serialization with ALT_BN128, and got 304 byte proofs. Is it possible that the two implementations don't have the same serialization?

[ebfull]

I believe point compression makes for some really slow deserialization of the proving key, something on the order of several minutes.

[daira]

Compression of points in a proof should be independent of compression of points in the proving key. The former would not cause a significant performance problem.

[ebfull]

Agreed; however we don't have that flexibility yet. I filed scipr-lab/libsnark#28 for that.

[daira]

See also scipr-lab/libsnark#38

[daira]

Fixed in 2016.0-beta-1.