Skip to content

perf: Distinguish between unrolled multiplication with known and unknown base #44

@federicobarbacovi

Description

@federicobarbacovi

At the moment, unrolled multiplication is implemented assuming the spender of the transaction supplies the base of the multiplication. However, there are cases in which the base is known beforehand (e.g., Groth16 for gamma_abc). This issue is to distinguish between the case in which the base is known and the case in which the base is unknown.

In the case of unknown base, the script we have should already be optimal. In the case of known base, it is probably more efficient to perform double and add from the Least Significant Bit of the scalar multiplier rather than from the Most Significant Bit (as we are doing now). The reason is that starting from the LSB we can verify the gradients for the doubling (which are fixed, as they are the gradients to compute 2^n P, where P is the fixed base) using an hash commitment instead of the mathematical formula.

If it is the case that for a known base it is more efficient to perform double and add from LSB, we should convert unrolled_multiplication to unrolled_multiplication_with_unknown_base and write a new method unrolled_multiplication_with_known_base.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions