Stark proof: deduplicate rows for lifted traces
Open
starks
- Dominant language
- Rust
- Stars
- 772
- Forks
- 352
- Avg merge
- 1d 12h
- Merged PRs (30d)
- 93
Description
The Lifted Merkle tree proof contains one row of the full lifted trace for each query. If two queries point to the same logical row of a smaller trace, that row will be duplicated.
This should not occur often when traces are approximately the same size, but in the context of an Air with many possible sizes (especially small ones) this could inflate the proof size artificially.
If this turns out too complicated, the alternative is to use out-of-the-box compression algorithm which sound easily detect the duplication.
Contributor guide
Assessment
This issue has not been assessed yet.