Skip to content

Stark proof: deduplicate rows for lifted traces #966

@adr1anh

Description

@adr1anh

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    starksRelated to Plonky3 migration

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions