Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize MSM for small scalars #416

Open
mratsim opened this issue Jun 30, 2024 · 0 comments
Open

Optimize MSM for small scalars #416

mratsim opened this issue Jun 30, 2024 · 0 comments

Comments

@mratsim
Copy link
Owner

mratsim commented Jun 30, 2024

Modern polynomial IOPs (Interactive Oracle Proofs) try to commit to only small values.

This is especially important for proving hash functions implemented via a bit-based approach (for xor/shift/rotate/...) vs lookup based approach. In that case, many scalars will be just 1.

One such optimization is to not double if the miniMSM coefs are all 0:

func miniMSM[bits: static int, EC, ECaff](
r: var EC,
buckets: ptr UncheckedArray[EC],
bitIndex: int, miniMsmKind: static MiniMsmKind, c: static int,
coefs: ptr UncheckedArray[BigInt[bits]], points: ptr UncheckedArray[ECaff], N: int) {.meter.} =
## Apply a mini-Multi-Scalar-Multiplication on [bitIndex, bitIndex+window)
## slice of all (coef, point) pairs
var windowSum{.noInit.}: typeof(r)
windowSum.bucketAccumReduce(
buckets, bitIndex, miniMsmKind, c,
coefs, points, N)
# 3. Mini-MSM on the slice [bitIndex, bitIndex+window)
r ~+= windowSum
when miniMsmKind != kBottomWindow:
for _ in 0 ..< c:
r.double()

The bucketAccumReduce function for example might probably be modified to return if there is at-least a non-zero coefficient found so we do a single pass over the data.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant