One of neat tricks used in Barretenberg implementation of Sha256 table-based constraint system is the special algorithm for handling majority and choose functions:
\begin{eqnarray}
maj(x, y, z) &=& (x∧y)⊕(x∧z)⊕(y∧z) \\ ch(x, y, z) &=& (x∧y)⊕(¬x∧z).
\end{eqnarray}
Instead of introducing many separate tables for each type of primitive boolean function (^, ⊕, ¬) and then applying them repeatedly in the right order, we may take the more efficient approach.
Consider the following tables:
x | y | z | maj(x, y, z) | x + y + z |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 2 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 2 |
1 | 1 | 0 | 1 | 2 |
1 | 1 | 1 | 0 | 3 |
x | y | z | choose(x, y, z) | x + 2y + 3z |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 3 |
0 | 1 | 0 | 0 | 2 |
0 | 1 | 1 | 1 | 5 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 4 |
1 | 1 | 0 | 1 | 3 |
1 | 1 | 1 | 1 | 6 |
In these tables, third column is our logical function log(x,y z), and the last column is the corresponding algebraic encoding alg(x,y,z), chosen so that the transformation \(f\) from alg \(\to\) log is well-defined. Note that in the last table, the value 3 appears twice on two different rows but the corresponding value in the third column on those rows is the same (0).
This observations suggest introducing the following algorithm for handling complex logical operatiosn (such as maj and ch:
This trick leads to more compact constrain systems in two ways:
However we have simplified things a little.The actual Sha256 hash mixes complex logical operations with circular rotations. Our sparse representation is friendly to the first (by design), but not to the second. Barretenberg authors solve this problem by introducing several different tables which do rotation and convertion to sparse form in one fell swoop. This strategy is fine to Sha256 (though not ideal) where the number of different rotation moduli is rather small, but carries serious obstacles for Keccak, where each of 25 lanes is shifted by unique modulus.
Let's see, if we could do better here. Assume, that our sparse algebraic encoding for x in base \(b\) is
\[ x = \sum_i^nx_i b^i,\] where each \(x_i\) is \(\in [0, c-1]\) . In fact, the only actual restriction for the choice of base \(b\) is that all separate chunks \(x_i\) should be uniqely decodable and retrived from \(x\), or in other words:
The map \(([0, c-1] \times n) \to \mathbb{F}: (x_0, \dots, x_{n}) \to \sum_i^nx_i b^i\) is injective.
The most simplest and natural choice is \(b = c\), and we may also take \(b = c+1\) or \(b=2c\), or any larger base \(b\) as long as \(x = \sum_i^nx_i b^i\) doesn't wrap around modulus p of field \(\mathbb{F}\). In this case, injectivity is trivial.
However, there is a special choice of base \(b\) which forces x to wrap around \(p\), but super friendly to rotations. Take \(b=g\) - root of unity of order n: \[g^{n} = 1, g^i \neq 1, \forall i <= n.\]
If we still posess injectivity property for such choice of \(b=g\), then both goals are achieved: logical operations are encoded as algebraic relations and are done on chunk-to-chunk basis and numbers are rotated by multiplication by corresponding powers of \(g\). Using this, we may pack both rotations and arithmetic in the same Plonk gates.
In practice, we are mostly interested for the following special cases of this injectivity problem:
Note that, for Sha256 with \(c = 8, n = 32\) the total number of all possible linear combinations \(\sum_i x_ig^i\) is \(8^{32} = 2^{3 \cdot 32} = 2^{96}\), so that injectivity cannot be checked by brute-force. If there exists rigorous positive solution to this injectivity problem, it will help to further reduce the number of gates and tables in Sha256 and Keccak Plookup implementations.
or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing