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.

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

Optimisation: Enable layouter to assign "equality-only" cells or regions #334

Open
str4d opened this issue Jul 16, 2021 · 0 comments
Open

Optimisation: Enable layouter to assign "equality-only" cells or regions #334

str4d opened this issue Jul 16, 2021 · 0 comments
Labels
A-planning Area: Circuit floor planner and layouter logic C-feature-request Category: This is a request for a new feature or functionality. I-performance

Comments

@str4d
Copy link
Contributor

str4d commented Jul 16, 2021

We have a bunch of places in the Orchard Action circuit where we assign a value (or several values) to one or more cells in a region, and then only use those cells for equality constraints (into other parts of the circuit).

We should add a Layouter::assign_equality_region API to enable explicitly optimizing this case. The layouter would track all cells in this region as "equality-only", with no real cell location, and the region itself would never appear in the circuit. Then, when the cells from that region are used:

  • If this is the first time the cell is used in an equality constraint, the layouter assigns the value instead of equality-constraining, and marks that cell as "assigned".
  • If this is the second or later time, the layouter adds an equality constraint to the first assigned cell.
  • If this is anything other than an equality constraint, circuit synthesis returns an error.
@str4d str4d mentioned this issue Jul 16, 2021
Closed
@daira daira added C-feature-request Category: This is a request for a new feature or functionality. I-performance labels Jul 16, 2021
@str4d str4d mentioned this issue Jul 16, 2021
Merged
str4d added a commit to zcash/orchard that referenced this issue Jul 21, 2021
@str4d
Optimise layout of witnessed Sinsemilla message pieces
3462d3e 
The Sinsemilla chip witnesses message pieces in individual regions, and
then copies them into the `hash_piece` region to initialize the running
sum. Previously these occured in the same column, but we can reduce the
utilized rows of the Action circuit by moving these into a less-used
column.

If zcash/halo2#334 is implemented, this change
would be unnecessary, as the witnessed message piece regions would never
be assigned into the circuit.
@str4d str4d mentioned this issue Jul 22, 2021
Merged
@str4d str4d added the A-planning Area: Circuit floor planner and layouter logic label Jul 22, 2021
str4d added a commit to zcash/orchard that referenced this issue Jul 23, 2021
@str4d
More small circuit optimisations
204fa32 
- Placing the Poseidon `state` columns after the `partial_sbox` column
  instead of before it causes them to line up with vast stretch of free
  space, enabling the pad-and-add region to be layed out there.

- Using the `Region::assign_advice_from_constant` API to initialise the
  Poseidon state removes fixed-column contention between that region and
  fixed-base scalar multiplication, enabling it to also be layed out
  within the free space.
  - If zcash/halo2#334 were implemented then
    this region would disappear.

- The overflow check in variable-base scalar mul is also moved into the
  columns with free space.
str4d added a commit to zcash/orchard that referenced this issue Jul 24, 2021
@str4d
More small circuit optimisations
46bca5e 
- Placing the Poseidon `state` columns after the `partial_sbox` column
  instead of before it causes them to line up with vast stretch of free
  space, enabling the pad-and-add region to be layed out there.

- Using the `Region::assign_advice_from_constant` API to initialise the
  Poseidon state removes fixed-column contention between that region and
  fixed-base scalar multiplication, enabling it to also be layed out
  within the free space.
  - If zcash/halo2#334 were implemented then
    this region would disappear.

- The overflow check in variable-base scalar mul is also moved into the
  columns with free space.
therealyingtong pushed a commit to zcash/orchard that referenced this issue Jul 24, 2021
@str4d @therealyingtong
More small circuit optimisations
f6c658e 
- Placing the Poseidon `state` columns after the `partial_sbox` column
  instead of before it causes them to line up with vast stretch of free
  space, enabling the pad-and-add region to be layed out there.

- Using the `Region::assign_advice_from_constant` API to initialise the
  Poseidon state removes fixed-column contention between that region and
  fixed-base scalar multiplication, enabling it to also be layed out
  within the free space.
  - If zcash/halo2#334 were implemented then
    this region would disappear.

- The overflow check in variable-base scalar mul is also moved into the
  columns with free space.
therealyingtong pushed a commit to zcash/orchard that referenced this issue Jul 25, 2021
@str4d @therealyingtong
More small circuit optimisations
092cc38 
- Placing the Poseidon `state` columns after the `partial_sbox` column
  instead of before it causes them to line up with vast stretch of free
  space, enabling the pad-and-add region to be layed out there.

- Using the `Region::assign_advice_from_constant` API to initialise the
  Poseidon state removes fixed-column contention between that region and
  fixed-base scalar multiplication, enabling it to also be layed out
  within the free space.
  - If zcash/halo2#334 were implemented then
    this region would disappear.

- The overflow check in variable-base scalar mul is also moved into the
  columns with free space.
@str4d str4d mentioned this issue May 18, 2022
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-planning Area: Circuit floor planner and layouter logic C-feature-request Category: This is a request for a new feature or functionality. I-performance
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@daira @str4d