# Sin7Y Tech Review (27): Combined Selector
![](https://i.imgur.com/wLVmzWJ.png)
## Customized gate
When designing the zkvm circuit, because of many custom gates determined, there are a lot of binary selectors are introduced. Taking the (field) division gate as an example, we plan to design a gate to verify that the relationship $q = x/y$ works among three elements $q,x,y$. For convenience, we will not perform the field division operation at the circuit level, instead, we will make it by verifying the following logical relationship:
$$
x * inv_y = q \\
inv_y * y = 1 \ \ // ensure\ y \neq 0
$$
Between the two elements, there is an equal relationship. Therefore, we have the following Trace table:
| Step | $$s_*$$ | .... | $$s_{div}$$ | .... | $$w_0$$ | $$w_1$$ | $$w_2$$ | $$w_3$$ | |
| ---- | ------- | ---- | ----------- | ---- | ------- | ------- | ------- | --------- | ---------- |
| .... | .... | .... | .... | .... | | | | | |
| k | 0 | 0 | 1 | 0 | x | y | q | $$inv_y$$ | //division |
| .... | .... | .... | .... | .... | | | | | |
Define the polynomial $w_0(x),w_1(x),w_2(x),w_3(x)$ for columns $w_0,w_1,w_2,w_3$, then the rows corresponding to the division operation shall satisfy：
$$
w_0(x) \cdot w_3(x) - w_2(x) = 0\\ w_1(x) \cdot w_3(x) - 1 = 0
$$
To ensure that the relationship above can be satisfied in the corresponding row, a selector is needed to make the corresponding division to constrain the verification. Therefore, we have introduced a new column $s_{div} = \{0,0,...1,...0\}$$. When it is transformed to the polynomial $s_{div}(x)$, the above equation will be:
$$
s_{div}(x)\cdot(w_0(x) \cdot w_3(x) - w_2(x)) = 0\\ s_{div}(x)\cdot(w_1(x) \cdot w_3(x) - 1) = 0
$$
## Combined selector
From the example above, we can see that when we define a new customized gate, a selector column $s_*$ needs to be introduced to correspond to the gate. If we represent the corresponding constraint polynomial of the gate with $t_*(x)$, we can obtain the following constraints finally:
$$
s_{add}(x) \cdot t_{add}(x) = 0 \\ s_{div}(x) \cdot t_{add}(x) = 0 \\ s_{cube}(x) \cdot t_{cube}(x) = 0 \\ s_{sqrt}(x) \cdot t_{sqrt}(x) = 0\\ ...
$$
For the prover needs to conduct commitments to all polynomials during the proof generation, overmuch selector polynomials introduced will increase the workload of the prover and the verifier. Therefore, it is necessary to optimize the selector number while the following two conditions must be satisfied:
1. There is no loss for the meaning of selector polynomial, that is, only specific gates can be used;
2. Less selector polynomial
In "Plonky2: Fast Recursive Arguments with PLONK and FRI"(https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf), there is an optimization method "Binary-Tree Based Selector", which reduces the number of the select polynomial to $log(k)$, and $k$ is the number of the customized gate. In the Halo2 paper, the zcash team has put forward a new optimization method, which may realize a smaller number of the polynomial (in correlation with the constraint polynomial $t_*(x)$ and the parameters set for the constraint polynomial max_degree).
To understand it easier, let's take a simple example (for specific algorithm, please refer to [Selector combining - The halo2 Book](https://zcash.github.io/halo2/design/implementation/selector-combining.html))
| Step | $$s_{add}$$ | $$s_{div}$$ | $$s_{cube}$$ | $$s_{sqrt}$$ | $$w_0$$ | $$w_1$$ | $$w_2$$ | $$w_3$$ | |
| ---- | ----------- | ----------- | ------------ | ------------ | ------- | ------- | ------- | ------- | ---------- |
| 0 | 1 | 0 | 0 | 0 | $$a_0$$ | $$b_0$$ | $$c_0$$ | $$d_0$$ | //add |
| 1 | 0 | 1 | 0 | 0 | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$d_1$$ | //division |
| 2 | 0 | 0 | 1 | 0 | $$a_2$$ | $$b_2$$ | $$c_2$$ | $$d_2$$ | //cube |
| 3 | 0 | 0 | 0 | 1 | $$a_3$$ | $$b_3$$ | $$c_3$$ | $$d_3$$ | //sqrt |
We can see that we have set 4 selector columns for 4 kinds of customized gates, which are not what we want just like the aforementioned. Therefore, this will increase the workload of the prover and the verifier. Here we define a new column $q$, satisfying:
$$
q = \begin{cases} k &\text{if } \ the\ selector\ labelled\ k \ is\ 1 \\ 0 &\text{if } \ all\ the \ selectors\ is\ 0 \end{cases}
$$
If we define a set $\{s_{add},s_{div},s_{cube},s_{sqrt}\}$ (called as disjoint, that is to make there is no common point between possible rows) for selectors $s_{add},s_{div},s_{cube},s_{sqrt}$, then based on the definition of column $q$, we have:
| Step | $$s_{add}$$ | $$s_{div}$$ | $$s_{cube}$$ | $$s_{sqrt}$$ | $$q$$ | $$w_0$$ | $$w_1$$ | $$w_2$$ | $$w_3$$ | |
| ---- | ----------- | ----------- | ------------ | ------------ | ----- | ------- | ------- | ------- | ------- | ---------- |
| 0 | 1 | 0 | 0 | 0 | 1 | $$a_0$$ | $$b_0$$ | $$c_0$$ | $$d_0$$ | //add |
| 1 | 0 | 1 | 0 | 0 | 2 | $$a_1$$ | $$b_1$$ | $$c_1$$ | $$d_1$$ | //division |
| 2 | 0 | 0 | 1 | 0 | 3 | $$a_2$$ | $$b_2$$ | $$c_2$$ | $$d_2$$ | //cube |
| 3 | 0 | 0 | 0 | 1 | 4 | $$a_3$$ | $$b_3$$ | $$c_3$$ | $$d_3$$ | //sqrt |
Here, define a new selector polynomial form based on column $q$, and for the number $k$ selector polynomial, we have:
$$
q(x)\prod_{1 \le h \le len(selectors), h \not = k }(h - q(x))
$$
For example, for the constraint: $s_{add} \cdot t_{add}(x) = 0$, can be rewritten into:
$$
q(x)\prod_{1 \le h \le len(selectors), h \not = 1 }(h - q(x)) \cdot t_{add}(x) = 0
$$
The above formula can be expanded into:
$$
q(x)\cdot (2- q(x))\cdot(3-q(x))\cdot (4-q(x))\cdot t_{add}(x) = 0
$$
Set
$$
combined_q(x) = q(x)\cdot (2- q(x))\cdot(3-q(x))\cdot (4-q(x))
$$
Then, the true value figure is obtained:
| x | $$combined_q(x)$$ | $$s_{add}(x)$$ |
| ---- | ----------------- | -------------- |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 2 | 0 | 0 |
| 3 | 0 | 0 |
It can be seen that it does the same thing as the original selector. Therefore, for constraints
$$
s_{add}(x) \cdot t_{add}(x) = 0 \\ s_{div}(x) \cdot t_{add}(x) = 0 \\ s_{cube}(x) \cdot t_{cube}(x) = 0 \\ s_{sqrt}(x) \cdot t_{sqrt}(x) = 0\\ ...
$$
We can rewrite the constrains into:
$$
q(x)\prod_{1 \le h \le len(selectors), h \not = 1 }(h - q(x)) \cdot t_{add}(x) = 0 \\ q(x)\prod_{1 \le h \le len(selectors), h \not = 2 }(h - q(x)) \cdot t_{add}(x) = 0 \\ q(x)\prod_{1 \le h \le len(selectors), h \not = 3 }(h - q(x)) (x) \cdot t_{cube}(x) = 0 \\ q(x)\prod_{1 \le h \le len(selectors), h \not = 4 }(h - q(x)) \cdot t_{sqrt}(x) = 0\\ ...
$$
For the constraints above, we only need to conduct commitment to the polynomial $q(x)$. But it is worth noting that, this method has also increased the degree of the constraint.
So far, we have achieved the two points mentioned above:
1. There is no loss for the meaning of selector polynomial, that is, only specific gates can be used;
2. Less selector polynomial
Of course, there are limitations to the constrained Degree in the protocol, so the selector number participating in the combine is bounded, that is, the number of the single combined selector depends on the boundary value of the Degree and max_degree of the constraint polynomial $t_*(x)$. Therefore, more combined columns are needed, and anyway, the number is still much smaller than the original one.
For more handling cases and algorithm details, please refer to [Selector combining - The halo2 Book](https://zcash.github.io/halo2/design/implementation/selector-combining.html).
## References
1. "The halo2 Book", https://zcash.github.io/halo2/design/implementation/selector-combining.html
2. Polygon Zero Team, "Plonky2: Fast Recursive Arguments with PLONK and FRI", https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf, accessed: 2022-02-06

During DevConnect Istanbul, I had the privilege of engaging with various project teams and researchers dedicated to privacy-oriented initiatives. We discussed a range of privacy-related topics. To my surprise, I found that the concept of ‘privacy’ is interpreted quite differently by different people, generally falling into two distinct categories:

11/29/2023At Ola, we strongly agree with a16z’s statement in their article “Achieving Crypto Privacy and Regulatory Compliance” about web3:

11/29/2023A comparative study of Aztec, Miden, and Ola In this article, we delve into the concept of "Hybrid Rollup," examining how projects Aztec, Miden, and Ola approach this technology. We investigate their unique smart contract languages, explore state tree designs, and consider the trade-offs in privacy designs. Our objective is to provide a comprehensive overview of Hybrid Rollup technologies, helping you understand their key components and envision their future trajectory. What is Hybrid Rollup? We are delighted to see that our recent initiatives have been garnering an increasing amount of attention in the market. "Hybrid Rollup" is the most accurate summary of what we at Ola have been working on: Rollup: a. It operates at Layer 2, but it also has the flexibility to function at Layer 3, depending on the platform utilized for the verification contract deployment.b. It's a scalability solution.c. It has programmability - "Rollup" doesn't specifically indicate this feature; "Programmable Rollup" is more accurate. Hybrid: a. It supports public, private, and hybrid contract types.b. Developers can freely choose the contract type based on their needs.c. Users can freely choose the transaction type in hybrid contracts.

6/13/2023This article is the 34th series of the Sin7y Tech Review and will mainly interpret SuperNova, which is a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set. These seem to be fantastic features. This article will mainly interpret how these features are implemented. For easy understanding, all interpretations are based on the paper itself. What is folding? First, let's look at the definition in the paper:As shown by the green marker in the figure: input: two (instance, witness) pairs

5/23/2023
Published on ** HackMD**