search

toposware / certificate-stark

An example of state-transition AIR program backed by the winterfell library.
Apache License 2.0
3 stars 1 forks source link

Implement in-circuit Schnorr signature verification aggregation #9

Open Nashtare opened 2 years ago

Nashtare commented 2 years ago

See detailed explanations here.

The usefulness of this optimization may be impacted by issues related to #6 and #7, depending on how these extra features are dealt with (i.e. if they increase the execution trace length).

In particular, the new Rescue hash instantiation with the Cheetah curve allows us to reduce the total current Merkle execution trace's length to less than 256 rows (currently 512), which combined with a reduction in half of Schnorr's length (currently 512) would lead to a total execution trace length also reduced by half.

4l0n50 commented 2 years ago

I can't see how the usefulness might be impacted by fee handling or xc txs handling. If I'm not wrong, both issues might at most add extra txs and. The corresponding extra signatures might also be aggregated with the same technique.

Nashtare commented 2 years ago

We had mentioned that to preserve the current width (already large) we may want to do it sequentially, i.e. proceeding to regular accounts update and then (next rows) compute the fee handling to the specific account. This would increase the length of the Merkle sub program, and may interact badly when trying to halve the total execution trace length through schnorr aggregation.

4l0n50 commented 2 years ago

I see it might change the shape of the trace but I'm not sure it will impact the usefulness of schnorr aggregation. But I can't say why not so your point is valid: it may be impacted.