Dot-Step - Githubissues

TritonVM / triton-vm

Triton is a virtual machine that comes with Algebraic Execution Tables (AET) and Arithmetic Intermediate Representations (AIR) for use in combination with a STARK proof system.

https://triton-vm.org

Apache License 2.0

223 stars 35 forks source link

Dot-Step #272

Closed aszepieniec closed 1 month ago

aszepieniec commented 1 month ago

This PR:

Introduces two new instructions to the VM, xxdotstep and xbdotstep which executes one iteration of a typical dot product loop.
Adds state evolution logic and constraints for the new instructions.

T~~wo tasks remain before t~~his PR is ready:

[x] Update documentation.
[x] Fix failing test constant_folding_processor_table which detects duplicate nodes.

jan-ferdinand commented 1 month ago

I would also ask you to rebase & force-with-lease push to remove “wip” commits. :relieved:

Sword-Smith commented 1 month ago

I see you've moved the constant folding. It makes sense to do what you can on insertion, but I wanted to ask if we're still cathing as much as we did previously. I think we are but was wondering if you guys have more insight.

jan-ferdinand commented 1 month ago

We've thought it through and concluded that we are catching all the same cases as before. Moving it further ahead in the pipeline serves two benefits (and has no downsides as far as we can see):

constant folding does not have to be called manually, and
semantically duplicate nodes are detected earlier, removing the strange behavior that nodes with different IDs evaluate to the same expression.

jan-ferdinand commented 1 month ago

Thanks! Good work. :blush: