scroll-tech / scroll-tech/ceno
Registers as single values + Replace ripple-carry method
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 153
- Forks
- 43
- Avg merge
- 3d 13h
- Merged PRs (30d)
- 4
Description
There are two related aspects that can be optimized:
- Represent register values as a single value (
u32) instead of two ([u16; 2]). - Implement arithmetic operations using field arithmetic.
1. Register value as u32
An instruction needs up to 4 register values (rs1, rs2, rd_before, rd_after), and each takes two limbs. It’s a major cost since all instructions use registers. See methods register_read and register_write.
The decomposition of input values into [u16; 2] is not actually so useful.
- Unsigned arithmetic only needs to range-check the output (not the input limbs).
- Signed arithmetic needs to decompose differently to somehow extract the sign bit.
- Bitwise logic uses
[u8; 4]and does not benefit from[u16; 2]. - Comparisons and branches only need to check the difference
rs1 - rs2. - Memory ops do not need decomposition, only to copy full values.
We can save everywhere by representing register content as a single value without limb decomposition. Different circuits may have different representations inside, but they read/write the single u32. Similarly for memory.
2. Using field arithmetic
Some circuits currently work on u16 or u8 limbs. For instance, ADD uses a ripple carry adder from the module uint.rs. This uses more witnesses, lookups, and total lookup fields, than necessary. Moreover, it forces everything else to work with [u16; 2] even if they don’t want to.
Instead, arithmetic can be implemented using field arithmetic. Only the output is decomposed and range-checked. The relation between inputs and output is a constraint.
Example for ADD:
rdis range-checked as[u16; 2], plus an overflow bit,- The constraint is
rs1 + rs2 = rd + overflow.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with register_read and register_write to trace how register and memory values are represented, then inspect the ripple-carry implementation in uint.rs, including the ADD circuit. Compare the current limb-based approach with the proposed single-u32 register values and field-arithmetic constraints. Done means both representation and arithmetic changes are implemented consistently across the affected circuits.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend, cryptography
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100