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
244 stars 36 forks source link

Compile constraint polynomials on the run #165

Closed sshine closed 1 week ago

sshine commented 1 year ago

Problem

In order to .prove() and .verify() one must currently run cargo run --bin constraint-evaluation-generator before cargo build. This overwrites some Rust files in triton-vm/src/ that currently contain stubs that panic. It is possible to .run() and .simulate() without panic, since constraint polynomials are not involved.

This makes working on Triton VM a little annoying, but worse so depending on triton-vm as a 3rd-party library impossible:

Current patchy solutions is to either:

Solutions

  1. Commit auto-generated code: This is currently ~220KiB of auto-generated code, which will make the git history grow every time something related to constraint polynomials changes. We can expect this number to increase when adding constraints, and possibly double for a tasm back-end. In another repo for another code generator, this led to hundreds of megabytes in a few weeks. We don't like this.
    • A Cargo build.rs script: Early experimentation suggested that there's a circular dependency problem: The constraint-evaluation-generator crate depends on triton-vm, so depending on the generator in triton-vm's build.rs creates the circular dependency. To remove the circularity, one would need for the constraint polynomials to live in a separate crate that does not depend on triton-vm, but I believe the coupling here is non-trivial to resolve. (The constraints are expressed in terms of things that relate to tables, so those types need to be abstract.)
    • A Builder-like proc macro: Add a #[derive(...)] that calls the constraint generator. Since constraint-evaluation-generator is pretty fast by now, this should come with very few downsides. We would need to release constraint-evaluation-generator on crates.io, though, perhaps under a name like triton-constraints-macro or such.
jan-ferdinand commented 1 year ago

Relates to #164

einar-triton commented 1 year ago

Workaround suggested: Make ConstraintGen a public crate and use cargo public --allow-dirty to publish it.

einar-triton commented 1 year ago

unassigning myself. I believe @sshine's supervision is needed to publish a new version of the crate with constraints baked in.

jan-ferdinand commented 1 week ago

Fixed with #323.