Skip to content

Perform multiple merge verifications at once to reduce the number of MSMs #1471

Closed

Description

@federicobarbacovi

The recursive merge verification in the kernel works by taking (t_1, T_{prev,1}, T_1) and verifying that T_1 = t_1 || T_{prev,1}, and then (once #1351 is closed) that T_2 = t_2 || T_1. The merge could take ({t_i}_i, T_prev, T) and verify that T = t_1 || ... || t_n || T_prev.

In our case n = 2 and we would trade 2 size-16 MSMs (the bases of the MSMs are t_1, T_{prev, 1}, T_1, X^{l_1-1} t_1(1/X) and t_2, T_1, T_2, X^{l_2-1} t_2(1/X)) for 1 size-20 MSM (the bases of the MSM are t_1, t_2, T_prev, T, X^{l_1 - 1} t_1(1/X), X^{l_2 - 1} t_2(1/X))

Activity

  1. changed the title [-]Perform multiple merge verification at once to reduce the number of MSMs[/-] [+]Perform multiple merge verifications at once to reduce the number of MSMs[/+] on Jul 10, 2025
  2. federicobarbacovi commented on Jan 5, 2026

    @federicobarbacovi
    Author

    The current state of the proposal to optimise the inner merges is here: https://hackmd.io/Bo9mWVjHRFOQawquti6UIQ

  3. federicobarbacovi commented on May 5, 2026

    @federicobarbacovi
    Author
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions