search

EspressoSystems / jellyfish

A Rust Implementation of the PLONK ZKP System and Extensions
https://jellyfish.docs.espressosys.com
MIT License
408 stars 106 forks source link

Eliminate unnecessary merkle proofs in ADVZ shares #671

Closed ggutoski closed 2 months ago

ggutoski commented 3 months ago

This issue drawn from https://github.com/EspressoSystems/jellyfish/pull/657#discussion_r1720327956

Currently each share now has multiplicity distinct merkle paths instead of just 1. That's a waste of bandwidth and it breaks backwards compatibility with jellyfish tag 0.4.5.

We should have only a single merkle proof for all evals.

ggutoski commented 3 months ago

The fix #657 breaks backwards compatibility with jellyfish tag 0.4.5 for serialization of ADVZ's Share struct because this field https://github.com/EspressoSystems/jellyfish/blob/7d71dbeff14f1a501b0b0dc391f1dffa1b8374fb/vid/src/advz.rs#L313 ...became this https://github.com/EspressoSystems/jellyfish/blob/7cd4f76b0844d4efdf9179fcdd7d4cae44bf7400/vid/src/advz.rs#L314

It seems impossible restore backwards compatibility. Any fix for this issue that restores evals_proof to its original type must change how the merkle tree is built, in which case future versions of jf-vid will disagree with past versions on how to build the merkle tree.

Given that we must break backwards compatibility somewhere, we should fix this issue and break how the merkle tree is built. The only alternative is to not fix this issue, in which case we continue to unnecessarily bloat share size by including unneeded merkle paths.