scroll-tech / scroll-tech/ceno

Registers as single values + Replace ripple-carry method

Open
#285 3 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

speed
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:

  1. Represent register values as a single value (u32) instead of two ([u16; 2]).
  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:

  • rd is 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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.