8000 Suboptimal Instruction-Specific Constraints · Issue #339 · TritonVM/triton-vm · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Suboptimal Instruction-Specific Constraints #339

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.

Sign up for GitHub

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

Jump to bottom
Open
aszepieniec opened this issue Nov 21, 2024 · 4 comments
Open

Suboptimal Instruction-Specific Constraints #339

aszepieniec opened this issue Nov 21, 2024 · 4 comments
Labels
🤖 code Changes the implementation 🟢 prio: low Not at all urgent 📜 specification Relates to the specification ⏩ speedup Makes stuff go faster.

Comments

@aszepieniec
Copy link
Collaborator

Upon skimming the result of cargo test print_number_and_degrees_of_transition_constraints_for_all_instructions -- --nocapture, 8 instructions stand out as having max degree 10 or 11. I am skeptical that these constraints must be so expensive. With the fancy technique that enabled pick and place, i.e., using an inner product with potentially shifted weight vectors, I am sure we can shrink these instructions' polynomials' degrees' maximum.

Instruction #polys max deg Degrees
pop 1 16 10 [1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 4, 1, 1, 1]
divine 1 16 10 [1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 4, 1, 1, 1]
read_mem 1 30 10 [1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1]
write_mem 1 30 10 [1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 1, 1]
sponge_absorb 10 11 [1, 1, 1, 1, 1, 1, 11, 1, 1, 1]
sponge_squeeze 10 11 [1, 1, 1, 1, 1, 1, 11, 1, 1, 1]
read_io 1 16 10 [1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 5, 4, 1, 1]
write_io 1 16 10 [1, 1, 1, 1, 2, 2, 2, 2, 1, 5, 5, 10, 5, 4, 1, 1]
@jan-ferdinand jan-ferdinand added 📜 specification Relates to the specification 🟢 prio: low Not at all urgent 🤖 code Changes the implementation ⏩ speedup Makes stuff go faster. labels Dec 20, 2024
@jan-ferdinand
Copy link
Member
jan-ferdinand commented Mar 20, 2025 •
edited
Loading

The degree-11 polynomial in sponge_absorb and sponge_squeeze comes from the permutation argument between the processor table and the op-stack table, which needs to account for 10 op-stack elements in a single instruction. I'm not aware of any technique to incorporate these factors using a polynomial of smaller degree.1

Footnotes

  1. I'm not counting generic degree-lowering techniques, which are already being applied, of course. 😌 ↩

@jan-ferdinand
Copy link
Member

The degree-10 polynomials in all other instructions is also due to the permutation argument between the processor table and the op-stack table, altough the overall composition is a little different. Since all the instructions take an argument in range $1 \leqslant i \leqslant 5$, the concrete factor to absorb is being de-selected using the indicator polynomial, which is of degree 4. For argument $i$, the polynomial describing correct transition of the running product is of the form $\texttt{running\_product}' - \texttt{running\_product} \cdot \prod_{j=0}^{i}\texttt{factor}_i$ where $\texttt{factor}_i$ is of degree 1. For $i = 5$, this polynomial is of degree 6.

I don't know of a technique to reduce the degree of the the running-product part of the degree-10 polynomial. It might be possible to squeeze a degree or two out of the deselector polynomial, but I'd need to dig into it more. All in all, I'm not certain there are significant speedups to be had here.

@jan-ferdinand
Copy link
Member

I'm closing this issue, as (to the best of my knowledge) the technique that enabled instructions pick and place is not applicable to reduce the degrees of the pointed-out high-degree polynomials, and because I'm not aware of any clever tricks to reduce the degrees.

@aszepieniec aszepieniec reopened this Apr 2, 2025
@aszepieniec
Copy link
Collaborator Author

Summarizing a conversation @jan-ferdinand and I just had in the office:

  • The high degree comes from modifying the op stack bus many times, once for each op stack pointer shift.
  • The question is if the op stack table can't pre-pack and un-pack on the side of the op stack table, and then send packages over the bus so that the processor table does not have to spend a lot of constraints unpacking elements one by one.
  • We came up with an intuition for a concept:
    • Extend the op stack table by two columns, a package-index, and a package-accumulator.
    • The package-index says where in the package to put (or take) the current element (from).
    • When the package-accumulator is done, it gets sent over the bus.
    • Two extra columns is almost certainly less extra columns than what we currently need to press the degree from 11 to 4.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
🤖 code Changes the implementation 🟢 prio: low Not at all urgent 📜 specification Relates to the specification ⏩ speedup Makes stuff go faster.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@aszepieniec @jan-ferdinand
0