... | @@ -222,11 +222,11 @@ a * b + c = d |
... | @@ -222,11 +222,11 @@ a * b + c = d |
|
## AddMod
|
|
## AddMod
|
|
|
|
|
|
计算addMod操作码我们等于验证a,b,n,r 其中n是mod值,r是余数。我们有 **(a+b)%n = r**。我们可以将这个约束转化为 **(a+b) = n * q + r**(商q可能超过256bit)。所以为了约束简单我们可以将上式转换如下:
|
|
计算addMod操作码我们等于验证a,b,n,r 其中n是mod值,r是余数。我们有 **(a+b)%n = r**。我们可以将这个约束转化为 **(a+b) = n * q + r**(商q可能超过256bit)。所以为了约束简单我们可以将上式转换如下:
|
|
1. **a % n= a_div_n + a_remainder** $\Leftrightarrow$ **a = n * a_div_n + a_remainder**
|
|
1. **a % n= a_div_n + a_remainder**
|
|
2. **(a_remainder + b) = (a_remainder_plus_b +a_remainder_plus_b_overflow << 256 )**
|
|
2. **(a_remainder + b) = (a_remainder_plus_b +a_remainder_plus_b_overflow << 256 )**
|
|
3. **(a_remainder_plus_b + a_remainder_plus_b_overflow << 256 ) % n= b_div_n + r**
|
|
3. **(a_remainder_plus_b + a_remainder_plus_b_overflow << 256 ) % n= b_div_n + r**
|
|
|
|
|
|
那么需要具体的约束如下,对于第1个等式:
|
|
那么需要具体的约束大致如下,对于第1个等式:
|
|
- a,n,a_remainder,a_div_n 存在mul_add_words约束 a_div_n * n + a_remainder = a
|
|
- a,n,a_remainder,a_div_n 存在mul_add_words约束 a_div_n * n + a_remainder = a
|
|
- 当n!=0时候, 存在a_remainder < n 约束
|
|
- 当n!=0时候, 存在a_remainder < n 约束
|
|
|
|
|
... | @@ -236,7 +236,7 @@ a * b + c = d |
... | @@ -236,7 +236,7 @@ a * b + c = d |
|
对于第3个等式:
|
|
对于第3个等式:
|
|
- b_div_n,n,b_remainder,a_reduced_plus_b_overflow 存在mul_add_words约束, b_div_n * n + r = a_remainder_plus_b + a_remainder_plus_b_overflow << 256 (mul_add_512_gadget)
|
|
- b_div_n,n,b_remainder,a_reduced_plus_b_overflow 存在mul_add_words约束, b_div_n * n + r = a_remainder_plus_b + a_remainder_plus_b_overflow << 256 (mul_add_512_gadget)
|
|
|
|
|
|
- 当n!=0时候,r < n 约束
|
|
- 当n!=0时, 存在r < n 约束
|
|
|
|
|
|
### layout
|
|
### layout
|
|
```
|
|
```
|
... | | ... | |