For practice to using halo2
This library makes use of the PSE Fork of Halo2.
List of available experiments:
- Experiment 1 - Inclusion Check
- Experiment 2 - Inclusion Check V2
- Experiment 3 - Dummy Hash V1
- Experiment 4 - Dummy Hash V2
- Experiment 5 - Merkle Tree V1
- Experiment 6 - Merkle Tree V2
- Experiment 7 - Poseidon Hash
- Experiment 8 - Merkle Tree v3
- Experiment 9 - LessThan Chip with Dynamic Lookup Table V1
- Experiment 10 - LessThan Chip V2
- Experiment 11 - LessThan Chip V3
- Experiment 12 - Merkle Sum Tree
- Experiment 13 - Add Carry v1
- Experiment 14 - Add Carry v2
- Experiment 15 - Overflow Check
- Experiment 16 - Overflow Check v2
- Experiment 17 - Safe Accumulator
cargo test --all-features -- --nocapture
This command will test all the circuits and print the representation of the circuits inside the prints folder.
The inclusion check Chip is a Chip built using 2 advice columns, 1 selector column and 1 instance column. The advice columns contain the list of usernames and balances. The instance column contains the username and balance of the user that I am generating the proof for. Let's call it pubUsername and pubBalance This should be public and the snark should verify that there's a row in the advise column where pubUsername and pubBalance entries match. At that row the selector should be turned on.
| username | balance | instance |
|---|---|---|
| 12332 | 200 | 56677 |
| 56677 | 100 | 100 |
| 45563 | 700 |
The constraint is enforced as a permutation check between the cell of the advice column and the cell of the instance column.
In this example, we don't really need a selector as we are not enforcing any custom gate.
The 2 advice columns and the 1 instance column are instantiated inside the configure function of the circuit and passed to the configure function of the chip. That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case).
Q: What is PhantomData?
A: In Rust, std::{marker::PhantomData} is a struct that has no fields and is used to indicate to the compiler that a type parameter or a generic type argument is being used in the code, even though it doesn't appear directly in any of the struct's fields or methods. An example of that can be found => https://github.com/enricobottazzi/halo2-fibonacci-ex/blob/master/src/bin/example3.rs#L137 or inside the InclusionCheckChip struct in the inclusion_check example
Q: How do you define the InclusionCheckChip struct?
A: In Rust, when you define a struct with a type parameter, such as InclusionCheckChip<F>, you are creating a generic struct that can work with any type that satisfies certain constraints. In this case, the type parameter F has a constraint : Field, which means that F must implement the Field trait.
| username | balance | usernameAcc | balanceAcc | selector | instance |
|---|---|---|---|---|---|
| - | - | 0 | 0 | - | 56677 |
| 12332 | 200 | 0 | 0 | 0 | 100 |
| 56677 | 100 | 56677 | 100 | 1 | - |
| 45563 | 700 | 56677 | 100 | 0 | - |
The constraint is enforced as a permutation check between the cell of the advise column and the cell of the instance column. In this example:
- We need to use the selector to be turned on on the required line to enforce the custom gate
- The permutation check is enforced between the last row of the
usernameAccandbalanceAcccolumns and the instance column values
The 4 advice columns and the 1 instance column are instantiated inside the configure function of the circuit and passed to the configure function of the chip. That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case). The selector is instantiated inside the configure function of the chip. That's because this selector is specific for the InclusionCheck chip and doesn't need to be shared across other chips.
Experiment of a dummy hash from halo2-merkle-tree.
The dummy hash function is 2 * a = b.
a can be viewed as the input of the hash function. b is the output of the hash function.
The zk snark verifies that the prover knows a such that the output of the hash function is equal to b.
| a | b | hash selector | instance |
|---|---|---|---|
| 2 | 4 | 1 | 4 |
a and b here are the advice column, namely the private inputs of circuit.
The instance column contains the public input of the circuit namely the result of the hash function that the zk snark should verify.
The 2 advice columns and the 1 instance column are instantiated inside the configure function of the circuit and passed to the configure function of the chip. That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case). The hash selector is instantiated inside the configure function of the chip. That's because this selector is specific for the InclusionCheck chip and doesn't need to be shared across other chips.
Experiment of a dummy hash from halo2-merkle-tree.
The dummy hash function is a + b = c.
a and b can be viewed as the input of the hash function. c is the output of the hash function.
The zk snark verifies that the prover knows a and b such that the output of the hash function is equal to c.
| a | b | c | hash selector | instance |
|---|---|---|---|---|
| 2 | 7 | 9 | 1 | 9 |
a and b and c here are the advice column, namely the private inputs of circuit.
The instance column contains the public input of the circuit namely the result of the hash function that the zk snark should verify.
Same as dummy hash V2.
Experiment of a merkle tree from halo2-merkle-tree.
The dummy hash function for the merkle tree is a + b = c.
The chip is made of 3 advice columns a, b and c, 3 selector columns bool_selector, swap_selector and hash_selector and 1 instance column instance.
The input passed to instantiate a circuit are the leaf the we are trying to prove the inclusion of in the tree, path_elements which is an array of the siblings of the leaf and path_indices which is an array of bits indicating the relative position of the node that we are performing the hashing on to its sibilings (path_elements). For example a path index of 1 means that the sibling is on the left of its node, while a path index of 0 means that the sibling is on the right of its node. Therefore the hashing needs to be performed in a specific order. Note that considering our dummy hash, the order of the hashing is not important as the result is the same. But this will be important when implementing a real hash function.
The assignment of the values to the columns is performed using a region that covers 2 rows:
| a | b | c | bool_selector | swap_selector | hash_selector |
|---|---|---|---|---|---|
| leaf | path_element | index | 1 | 1 | 0 |
| input left | input right | digest | 0 | 0 | 1 |
At row 0, we assign the leaf, the element (from path_element) and the bit (from path_indices). At this row we turn on bool_selector and swap_selector.
At row 1, we assign the input left, the input right and the digest. At this row we turn on hash_selector.
The chip contains 3 custom gates:
- If the
bool_selectoris on, checks that the value inside the c column is either 0 or 1 - If the
swap_selectoris on, checks that the swap on the next row is performed correctly according to thebit - If the
hash_selectoris on, checks that the digest is equal to the (dummy) hash between input left and input right
Furthermore, the chip contains a permutation check:
- Verfies that the
leafis equal to theleafpassed as (public) value to the instance column - Verifies that the last
digestis equal to therootof the tree which is passed as (public) value to the instance column
The MerkleTreeV1Config contains 3 advice column, 1 bool_selector, 1 swap_selector, 1 hash_selector, and 1 instance column. The advice columns and the instance column are instantiated inside the configure function of the circuit and passed to the configure function of the chip. That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case). The selectors are instantiated inside the configure function of the chip. That's because these selectors are specific for the MerkleTreeV1 chip and don't need to be shared across other chips.
This Merkle Tree specification works exactly the same as the previous one. The only difference is that it makes use of the Hash2Chip and Hash2Config created in experiment 4 rather than rewriting the logic of the hash inside the MerkleTree Chip, as it was done in experiment 5.
It's worth nothing how the Hash2Chip and Hash2Config are used in this circuit. As mentioned in the Halo2 book - Composing Chips these should be composed as in a tree.
- MerkleTreeV2Chip
- Hash2Chip
The MerkleTreeV2Config contains 3 advice column, 1 bool_selector, 1 swap_selector, 1 instance column and the Hash2Config.
The advice columns and the instance column are instantiated inside the configure function of the circuit and passed to the configure function of the MerkleTreeV2Chip. That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case). The bool_selector and swap_seletor are instantiated inside the configure function of the MerkleTreeV2Chip. That's because these selectors are specific for the MerkleTreeV2Chip and don't need to be shared across other chips. The child chip Hash2Chip is instantiated inside the configure function of the MerkleTreeV2Chip. That's because the Hash2Chip is specific for the MerkleTreeV2Chip by passing in the advice columns and the instance column that are shared between the two chips. In this way we can leverage Hash2Chip with its gates and its assignment function inside our MerkleTreeV2Chip.
Create a chip that performs a Poseidon hash leveraging the gadget provided by the Halo2 Library. Based on this implementation => https://github.com/jtguibas/halo2-merkle-tree/blob/main/src/circuits/poseidon.rs
The PoseidonChip, compared to the Pow5Chip gadget provided by the Halo2Library, adds a vector of advice columns that takes the input of the hash function and one instance column that takes the expected output of the hash function.
Similarly to the previous experiment, the PoseidonChip is a the top-level chip of the circuit while the Pow5Chip can be seen as a child chip as you can see from the configuration of the PoseidonChip
The configuration tree looks like this:
- PoseidonChip
- Pow5Chip
The PoseidonConfig contains a vector of advice columns, 1 instance column and the Pow5Config.
The vector of advice columns and the instance column are instantiated inside the configure function of the circuit and passed to the configure function of the PoseidonChip. In particular the vector of advice columns contains as many columns as the WIDTH of the Poseidon hash function (more details later).
That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case). Further columns part of the configuration of the Pow5Chip are created inside the configure function of the PoseidonChip and passed to the configure function of the Pow5Chip.
At proving time:
- We instatiate the PoseidonCircuit with the input of the hash function and the expected output of the hash function
let input = 99u64;
let hash_input = [Fp::from(input), Fp::from(input), Fp::from(input)];
// compute the hash outside of the circuit
let digest =
poseidon::Hash::<_, P128Pow5T3, ConstantLength<3>, 3, 2>::init().hash(hash_input);
let circuit = PoseidonCircuit::<Fp, P128Pow5T3, 3, 2, 3> {
hash_input: hash_input.map(|x| Value::known(x)),
digest: Value::known(digest),
_spec: PhantomData,
};In particular we can see that the poseidon hash is instantiated using different parameters such as P128Pow5T3, ConstantLength<3>, 3, 2 (when performing the hash), and P128Pow5T3, 3, 2, 3 when instantiating the circuit. These values represent poseidon specific parameters such as the number of rounds to be performed. The only thing that we should care about in our APIs is ConstantLength<n> and the parameter L in the PoseidonCircuit struct. This represent the number of inputs of the hash function and can be modified by the developer.
-
The columns (
hash_inputs,instance) are created in theconfigurefunction of the PoseidonCircuit. All the other columns (the columns to be passed to thepow5_config) are created in theconfigurefunction of the Poseidon Chip. This function returns the PoseidonConfig instantiation. -
The instantiation of the PoseidonConfig is passed to the
syntesizefunction of the PoseidonCircuit. This function will pass the input values for the witness generation to the chip that will take care of assigning the values to the columns and verifying the constraints. In particular, it will:- call
load_private_inputson the poseidon chip to assign the hash input values to the advice columnshash_inputs. This function will return the assigned cells inside the advice columnshash_inputs - call
hashon the poseidon chip passing the hash input values to the advice columnshash_inputs. This function will return the assigned cells inside the advice columnshash_inputs. Later it will initialize thepow5_chipand call thehashfunction on thepow5_chippassing thehash_inputcolumn. This function will return an assigned cell that represents the constrained output of the hash function. - call the
expose_publicfunction on the poseidon chip by passing in the assigned cell output of thehashfunction. This function will constrain it to be equal to the expected hash output passed into the public instance column.
- call
This experiment re-implements the Merkle Tree circuit of experiment 6 using the PoseidonChip created in experiment 7.
The Configuration tree looks like this:
- MerkleTreeV3Chip
- PoseidonChip
- Pow5Chip
- PoseidonChip
The MerkleTreeV3 Config contains 3 advice columns, 1 instance column, a boolean selector, a swap selector and the PoseidonConfig.
The 3 advice columns and the instance column are instantiated inside the configure function of the circuit and passed to the configure function of the MerkleTreeV3Chip. That's because in this way these columns can be shared across different chips inside the same circuit (although this is not the case). The bool_selector and swap_seletor are instantiated inside the configure function of the MerkleTreeV3Chip. That's because these selectors are specific for the MerkleTreeV3Chip and don't need to be shared across other chips.
The child chip PoseidonChip is instantiated inside the configure function of the MerkleTreeV2Chip. In this way we can leverage PoseidonChip with its gates and its assignment function inside our MerkleTreeV2Chip.
At proving time:
-
We instatiate the MerkleTreeV3 Circuit with the leaf, the path_elements and the path_indices
-
The 3 advice columns and the instance column are created in the
configurefunction of the MerkleTreeV3 Circuit. All the other columns (hash_inputs, namely the columns to be passed to theposeidon config) are created in theconfigurefunction of the MerkleTreeV3 Chip. This function returns a MerkleTreeV3Config instance. -
The instantiation of the PoseidonConfig is passed to the
syntesizefunction of the PoseidonCircuit. This function will pass the input values for the witness generation to the chip that will take care of assigning the values to the columns and verifying the constraints. In particular, it will:- call
assign leafon the merkle tree chip to leaf value inside a cell in the advice columna. This function will return the assigned cells. - call the
expose_publicfunction on the merkle tree chip by passing in the assigned cell output of theassign leaffunction. This function will constrain it to be equal to the expected leaf hash passed into the public instance column. - call the
merkle_prover_layerfunction on the chip for each level of the merkle tree. - call the
expose_publicfunction by passing in the last output of themerkle_prove_layerfunction. This function will constrain it to be equal to the expected root passed into the public instance column.
- call
This Chip takes an input inside the input column advice. Say that we want to check if the input is less than 5. The instance column will be loaded with the values 0, 1, 2, 3, 4. The chip will then copy each value contained in the instance column to an advice_table advice column. The chip set a constraint on input to be less than 5 by creating a dynamic lookup check between the input and the advice_table column. If the input is less than 5, then the lookup will be successful and the constraint will be satisfied.
The dynamic constraint is set using the lookup_any API. The dynamic caracteristic is needed to let the prover add the value to compare input with at witness generation time.
TO DO:
- Make it generic for Field F
- Describe it
This LessThan Chip is imported from the ZK-evm circuits gadgets. The LessThan Chip takes two values that are part of the witness (lhs and rhs) and returns 1 if lhs < rhs and 0 otherwise.
The LessThan Chip Configuration contains:
- 1 advice column
ltthat denotes the result of the comparison: 1 iflhs < rhsand 0 otherwise - An array of
diffadvice columns of length N_BYTES. It is basically the difference betweenlhsandrhsexpressed in 8-bit chunks. - An field element
rangethat denotes the range in which bothlhsandrhsare expected to be. This is calculated as2^N_BYTES * 8whereN_BYTESis the number of bytes that we want to use to represent the valueslhsandrhs.
The configure function takes as input the lhs and rhs virtual cells from a higher level chip and enforces the following gate:
lhs - rhs - diff + (lt * range) = 0
Note that the gate enforces inside this child chip, the constraint is dependent on the value of some cells passed from an higher level chip. The parent chip and the child chip are sharing a region. That's why the assign function inside the LTChip takes as input the region rather than the layouter as usual.
The assignment function takes as input the lhs and rhs values and assigns the values to the columns such that:
lhs < rhsbool is assigned to theltadvice column- if
lhs < rhs,lhs - rhs + rangeis assigned to thediffadvice columns - else
lhs - rhsis assigned to thediffadvice columns
Again, note that the assignment function doesn't take assigned value of type Value<F> but simple values of type F where F is a generic Field Element. This example makes clear the difference between assignment and setting constraints. The assignment function is responsible for assigning values to the columns. You can perform the assignemnt starting from values that are not necessarily computed from the circuit itself. The constraint function is responsible for setting the constraints between the columns, this process is prior and independent to the assignment/witness generation.
Now the custom gate should make more sense. Considering an example where lhs = 5 and rhs = 10 and N_BYTES is 1. Range would be 256 and diff would be a single advice column containing the value 251. The gate would be:
`5 - 10 - 251 + (1 * 256) = 0`
Considering an example where lhs = 10 and rhs = 5 and N_BYTES is 1. Range would be 256 and diff would be a single advice column containing the value 5. The gate would be:
`10 - 5 - 5 + (0 * 256) = 0`
The less_than_v2 circuit contains the instruction on how to use the LessThan Chip in a higher level circuit. The only added gate is that the check value in the advice column of the higher level circuit (which is the expected result of the comparison) should be equal to the lt value in the advice column of the LessThan Chip.
Lastly, let's consider a case where lhs lies outside the range. For example lhs = 1 and rhs = 257 and N_BYTES is 1. Diff is a single advice column but it can't represent the value 256 in 8 bits!
TO DO:
- Understand the whole functioning
- Check whether it is possible to import it from the zkevm circuits lib.
- Need to enforce the LT expression to be equal to 1 on a higher-level circuit!
This experiment makes use of the same chip as in V2. The only difference here is that on the higher level circuit level we impose the LessThan value to be constrained to 1.
The only difference here is the additional constraint added at line 61
vec![..., q_enable * (Expression::Constant(F::from(1)) - check)]
This property is constrained by assigning 1 to the check in the synthesize function. The constraint set inside the top level circuit checks that check is equal to lt in the child chip.
The Circuit built on top of that chip (circuits/less_than_v3.rs) also makes use of the hash_v1 chip. This is just an experiment to remark that you can reuse the generic Field trait from eth_types::{Field} to instantiate a chip that is generic on a Field of trait F from halo2_proofs::arithmetic::FieldExt. That's because the Field trait is a wrapper around the FieldExt type (and other 2 types) => https://github.com/privacy-scaling-explorations/zkevm-circuits/blob/4cfccfa6c3b251284ff61eeb907d548d59206753/eth-types/src/lib.rs#LL51C72-L51C72.
It means that you can use the eth_field::Field type to instantiate a chip that is generic on a F that implements the FieldExt trait.
This chip implements the logic of a Merkle Sum Tree. The peculiarity of a Merkle Sum Tree are that:
- Each node inside the tree (both Leaf Nodes and Middle Nodes) contains an hash and a value.
- Each Leaf Node contains a hash and a value.
- Each Middle Node contains a hash and a value where hash is equal to
Hash(left_child_hash, left_child_sum, right_child_hash, right_child_sum)and value is equal toleft_child_sum + right_child_sum.
A level inside the tree consists of the following region inside the chip:
For the level 0 of the tree:
| a | b | c | d | e | bool_selector | swap_selector | sum_selector |
|---|---|---|---|---|---|---|---|
| leaf_hash | leaf_balance | element_hash | element_balance | index | 1 | 1 | 0 |
| input_left_hash | input_left_balance | input_right_hash | input_right_balance | computed_sum | 0 | 0 | 1 |
At row 0, we assign the leaf_hash, the leaf_balance, the element_hash (from path_element_hashes), the element_balance (from path_element_balances) and the bit (from path_indices). At this row we turn on bool_selector and swap_selector.
At row 1, we assign the input_left_hash, the input_right_balance, the input_right_hash, the input_right_balance and the digest.
At this row we activate the poseidon_chip and call the hash function on that by passing as input cells [input_left_hash, input_left_balance, input_right_hash, input_right_balance]. This function will return the assigned cell containing the computed_hash.
The chip contains 4 custom gates:
- If the
bool_selectoris on, checks that the value inside the c column is either 0 or 1 - If the
swap_selectoris on, checks that the swap on the next row is performed correctly according to thebit - If the
sum_selectoris on, checks that the sum between theinput_left_balanceand theinput_right_balanceis equal to thecomputed_sum - checks that the
computed_hashis equal to the hash of theinput_left_hash, theinput_left_balance, theinput_right_hashand theinput_right_balance. This hashing is enabled by theposeidon_chip.
For the other levels of the tree:
| a | b | c | d | e | bool_selector | swap_selector | sum_selector |
|---|---|---|---|---|---|---|---|
| computed_hash_prev_level | computed_sum_prev_level | element_hash | element_balance | index | 1 | 1 | 0 |
| input_left_hash | input_left_balance | input_right_hash | input_right_balance | computed_sum | 0 | 0 | 1 |
When moving to the next level of the tree, the computed_hash_prev_level is copied from the computed_hash of the previous level. While the computed_sum_prev_level is copied from the computed_sum at the previous level.
Furthermore, the chip contains four permutation check:
- Verfies that the
leaf_hashis equal to theleaf_hashpassed as (public) value to the instance column - Verfies that the
leaf_balanceis equal to theleaf_balancepassed as (public) value to the instance column - Verifies that the last
computed_hashis equal to the (expected)rootof the tree which is passed as (public) value to the instance column - Verifies that the last
computed_sumis equal to the (expected)balance_sumof the tree which is passed as (public) value to the instance column
TO DO:
- Replace usage of constants in Inclusion Check.
- Fix printing functions
- Check the security of the Poseidon Hash
Allowing the addition of new values to previously accumulated amounts into two columns, acc_hi and acc_lo.
Circuit looks like this,
| - | value | acc_hi(x * 2^16) | acc_lo(x * 2^0) | instance |
|---|---|---|---|---|
| 0 | - | 0 | 0 | 0x1 |
| 1 | 0xffff | 0 | 0xffff | 0 |
| 2 | 0x1 | 0x1 | 0 | - |
| 3 | - | - | - | - |
the first rows's values assigned with zero. And assign_advice_row function needs values for addition, these will be copied cell from the region. and then permutation check like below.
// following above table
0 == (value + (acc_hi[1] * (1 << 16)) + acc_lo[1])
- ((acc_hi[2] * (1 << 16)) + acc_lo[2] )cargo test --package halo2-experiments --lib -- circuits::add_carry_v1
TO DO: -> moved to next version.
- [ ] Range check for left most column of multi-columns for accumulation
- [ ] Support 2^256 in Accumulated value with multi-columns
Allowing the addition of new values to previously accumulated amounts into two columns, acc_hi and acc_lo.
Circuit looks like this
| - | value | acc_hi_inv | acc_hi(x * 2^16) | acc_lo(x * 2^0) | instance |
|---|---|---|---|---|---|
| 0 | - | - | 0 | 0xfffe | 0x1 |
| 1 | 0x1 | * | 0 | 0xffff | 0xfffe |
| 2 | - | - | - | - | 0x0 |
| 3 | - | - | - | - | 0x1 |
As similar like v1, used simple configuration. but added one more constraint with one more advice column for inverted number. this constraint polynomial followed is_zero gadget from zkevm-circuit.
the addition constraint like below.
// following above table
0 == acc_hi[1] * (1 - acc_hi[1] * acc_hi_inv[1]) This chip implemented an overflow checking for columns of the accumulation amount of assets. There is an extra column for accumulating value. the column be used for inverting a number in the overflow column.
There are two selectors in this chip.
- 'add_carry_selector': toggle sum of new value in 'a' column and accumulated value.
- 'overflow_check_selector': toggle check to see if the sum in the 'sum_overflow' column equals zero.
for checking if a number is zero in the 'sum_overflow' column, activate 'is_zero' chip.
The code for the 'is_zero' chip was taken from the "halo2-example" repository.
There are two tests for 'overflow circuit'.
- None overflow case
- value sum_overflow_inv sum_overflow sum_hi(x * 2^16) sum_lo(x * 2^0) instance 0 - - - 0 0xfffe 0 1 0x1_0003 * * 0x2 0x1 0xfffe 2 - - - - - 0x2 3 - - - - - 0x1
At row 1, We can calculated 'acc_hi' has 0x20000 value. and 'sum_lo' is 0x1 value. it is matched a sum of 0x1_0003 in 'value' column at row 1 and 0xfffe in 'sum_lo' at row 0. we may strict a number more than or equal '2^16' in 'value' column. In here, we used more than '2^16' for testing.
- Overflow case
- value sum_overflow_inv sum_overflow sum_hi(x * 2^16) sum_lo(x * 2^0) instance 0 - - - 0 0xfffe 0 1 0x1_0000_0002 * 0x1 0x1 0x1 0xffff 2 - - - - - 0x1 3 - - - - - 0x1 4 - - - - - 0x1
In this case, addition value is more than 2^32. so, the circuit got panic with this input due to 'is_zero' chip.
The overflow_check_v2 chip is designed to provide a more robust mechanism for checking overflow conditions in computations.
The overflow_check_v2 chip accomplishes this by decomposing the values in cells, which allows it to handle larger numbers. In other words, instead of storing a large number in a single cell, it breaks down the number into smaller parts and stores each part in a separate cell. This method enables the circuit to handle much larger numbers than would be possible with a single cell.
The primary purpose of this chip is to verify the equality between the original value and its decomposed counterpart. By doing this, the chip can ensure that the decomposed values correctly represent the original value and that no overflow has occurred during computations.
However, while the chip can handle larger numbers by decomposing them into smaller parts, it's important to note that it can't handle values that are larger than the prime number of the finite field. This is a fundamental limit of the chip and the underlying circuit.
For better understanding, let's consider a scenario where we check for overflow in three steps, 'a', 'b', and 'a + b', at the circuit level. Assume that the prime number of the finite field is 255, 'a' is 42, and 'b' is 221. It's easy to see that both 'a' and 'b' are valid and don't overflow. However, 'a + b' equals 262, which is over the prime number. Thus, the chip will only return the result as 7 (262 mod 255), not 262, because it's over the modulus.
The key feature is in here overflow_check_v2 circuit
// check overflow
chip.assign(layouter.namespace(|| "checking overflow value a"), self.a)?;
chip.assign(layouter.namespace(|| "checking overflow value b"), self.b)?;
chip.assign(layouter.namespace(|| "checking overflow value a + b"), self.a + self.b,)?;Note that those 'a' and 'b' are bigInt type. So, we do not worry about overflowing when add it before using the input variable to assign method.
The safe_accumulator is a chip designed to accumulate values within a circuit and effectively manage the risk of overflow. Its main purpose is to maintain an accumulated total of values that could potentially be larger than the modulus of the finite field in the circuit.
It achieves this by breaking down the total value into smaller parts and storing each part in a separate cell. This allows the chip to effectively handle much larger numbers than would be possible with a single cell.
Now, let's dive into the structure of the safe_accumulator config in more detail.
pub struct SafeAccumulatorConfig<const MAX_BITS: u8, const ACC_COLS: usize> {
pub update_value: Column<Advice>,
pub left_most_inv: Column<Advice>,
pub add_carries: [Column<Advice>; ACC_COLS],
pub accumulate: [Column<Advice>; ACC_COLS],
pub instance: Column<Instance>,
pub is_zero: IsZeroConfig,
pub selector: [Selector; 2],
}The chip incorporates a mechanism to check for overflow, utilizing the leftmost accumulate column for this purpose. Consequently, you need to configure one additional column beyond the maximum accumulation value. For instance, if you're checking values beyond 64 bits (8 bytes), you should configure 9 columns in the circuit, with MAX_BITS set to 8. Alternatively, you can set MAX_BITS to 16 and use 5 columns, given that 16 * 4 equals 64 bits. To prevent malicious computations on the leftmost accumulate column, constraints for other accumulate columns are put in place, similar to the mechanism used in the add_carry_v1 chip.
The chip has constraints that the accumulated values fall within a predefined range. It also ensures that the carry values are binary. These features work together to prevent overflow and maintain the integrity of the accumulated total.
A unique advantage of the safe_accumulator over some other chips (like add_carry_v1) is that it can handle numbers larger than the modular limit of the finite fields in the circuit. This makes it particularly useful in scenarios where we need to deal with large numbers that might exceed the field modulus.
However, this chip is experimental and has limitations. The values added to the accumulator are limited by MAX_BITS and might need decomposition for handling larger values.