Adds the RCOMB1 instruction

0xPolygonMiden / miden-vm

STARK-based virtual machine

MIT License

618 stars 156 forks source link

Adds the RCOMB1 instruction #1216

Closed Al-Kindi-0 closed 7 months ago

Al-Kindi-0 commented 7 months ago

Describe your changes

Adds a helper instruction to do random linear combination in base field.

Checklist before requesting a review

Repo forked and branch created from next according to naming convention.
Commit messages and codestyle follow conventions.
Relevant issues are linked in the PR description.
Tests added for new functionality.
Documentation/comments updated according to changes.

Al-Kindi-0 commented 7 months ago

Looks great! Thank you! I left a some comments inline - but also, a couple additional comments:
1. Let's update the changelog.

Done!

2. Let's update mdBook documentation. This would include [this](https://0xpolygonmiden.github.io/miden-vm/design/stack/op_constraints.html) and [this](https://0xpolygonmiden.github.io/miden-vm/design/stack/crypto_ops.html) sections, but also maybe something else.

Updated, should I add a figure similar to the one for the FRI fold op?

3. After we merge this, we'll probably need to rebase [#1140](https://github.com/0xPolygonMiden/miden-vm/pull/1140) to make sure we handle additional memory requests correctly.

Will create an issue for this once we merge

Al-Kindi-0 commented 7 months ago

Also, I believe we have a test for RpoFalcon512 verification, and since it is passing all should be good on that front - right?

That's true, I changed Falcon to use the new instruction but not the STARK verifier. The Falcon test is passing so everything should be good for that and most probably for the STARK verifier too. Still the new op is used in a slightly different way to how it is used in the STARK verifier (it discards the values of the r accumulator) so I wanted to be cautious. However, we can remove the emulating procedure and change the STARK verifier to make used of the new op if you think it makes sense.