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

transpose codewords only once when proving #120

Closed
jan-ferdinand opened this issue Nov 14, 2022 · 1 comment · Fixed by #144
Closed

transpose codewords only once when proving #120

jan-ferdinand opened this issue Nov 14, 2022 · 1 comment · Fixed by #144
Labels
🖐 blocked Requires something else first. 🤖 code Changes the implementation 🟡 prio: medium Not super urgent ⏩ speedup Makes stuff go faster.

Comments

@jan-ferdinand
Copy link
Member

jan-ferdinand commented Nov 14, 2022

When evaluating the AIR constraints to compute the quotient codewords, the STARK prover currently treats each table separately. For each table, the table's corresponding trace codewords over the arithmetic domain (see #114) are computed, tansposed, and used as evaluation points on the table's AIR constraints.

Refactor the code such that concatenating all trace codewords and transposing the result can be used for all table's constraints. This probably requires a consistent globally canonical ordering of all tables,1 globally unique column indices derived from that ordering, and indexing into the transposed codewords using these indices.

Footnotes

  1. We probably have that already. To the best of my knowledge, we currently don't rely on its existence.

@jan-ferdinand jan-ferdinand added 🟡 prio: medium Not super urgent 🤖 code Changes the implementation ⏩ speedup Makes stuff go faster. labels Nov 14, 2022
@jan-ferdinand
Copy link
Member Author

Blocked by #139.

@jan-ferdinand jan-ferdinand added the 🖐 blocked Requires something else first. label Nov 23, 2022
@jan-ferdinand jan-ferdinand mentioned this issue Nov 29, 2022
25 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
🖐 blocked Requires something else first. 🤖 code Changes the implementation 🟡 prio: medium Not super urgent ⏩ speedup Makes stuff go faster.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant