## Requirements for a STARK to be perfectly Zero-Knowledge

This intends to be a comprehensive list of the requirements a STARK implementation should have in order for the proofs to be zero knowledge.

## Requirement 1: How many random numbers are enough to blind a polynomial?
The trace polynomial (aka witness polynomial) are calculated by interpolating the witness vector.
The size of the trace polynomial has an upper bound of the size of the subgroup D over which we are performing the interpolation. A basic requirement for a STARK is having |D| > T+1, where T is the length of the execution trace. The size of D is fixed, as a parameter for the STARK. The size of T varies. In practice this means that the trace gets padded with zeros before interpolation so its size matches |D|. To achieve zero knowledge we can pad the remaining unused slots with random numbers instead, which would not we known to the verifier.

[This PR](https://github.com/facebook/winterfell/pull/84) allows the user to select how many rows (at the end of the table) are exempted to have transition constrains applied to them. Which is good: random numbers at the end of the table would act as blinding, but would not pass transition constraints, which would have the verification fail. Not performing checks on the blinding factors is a requirement for a back-end implementation to have zero knowledge.
The `end_exemptions` in lambdaclass STARK seems to be similar to the `divisor` in winterfell, and could be used in a similar manner.

The number of random field elements needed are dependent on how many queries the verifies does when the FRI commitment scheme starts. For each FRI query, one extra blinding factor needs to be added to the trace polynomial. The back-end implementation then should have a counter function that computes how many queries are going to be made, and can then calculate how many blinding factors are needed at the end of the trace.

We can use the [counter function](https://github.com/0xPolygonZero/plonky2/blob/76da1383384a99691506b3904dd8c2ddfd057555/plonky2/src/plonk/circuit_builder.rs#L862) used in plonky2, which I (Xuyang) have verified.

## Requirement 2: Blinding composition polynomials
The composition polynomial is a randomized linear combination of the boundary polynomials and the transition polynomials. To get an additional level of blindness a random polynomial obtained as the interpolation of a vector of random numbers of length equal to the maximum degree accepted with the FRI low-degree test.
If in Requirement 1 we were adding rows of random numbers at the end of the execution trace, this procedure is in turn equivalent to adding an extra column with random field elements to the trace matrix.

Besides adding the random rows, we may still need add a random codeword to the deep fri combination, which is omitted in plonky2 though.
The processes are:
1. Prover: commit the random codeword r that corresponds to a polynomial of maximal degree
2. Prover: combine the random polynomial with the deep fri polynomial
3. Prover: add the queries/opens on the random codeword to the proof
4. Verifier: check the nonlinear combination
5. Verifier check the queries/opens of the random codeword

## Requirement 3: salted Merkle commitments
Salted leafs in the Merkle tree should used when the base field over which the STARK is constructed is small. This is not relevant in our use because we are going to use big fields, for they are required by the security goals of the resource machine.
Specifically, lambdaclass STARK prover uses the STARK field:
$P = 2^{251}+17*2^{192}+1$
And winterfell can use quadratic and cubic extentions of the goldiloc field that can reach a security of ~100 bits.

## Requirement 4: evaluations on a coset
This requirement is met by both lambaclass STARK prover and Winterfell. It guarantees that the evaluations used by the FRI verifier and the evaluations used on the trace polynomials are done on disjointed cosets, to prevent information leackage in the FRI query phase.

## Further consideration: parameters analysis to guarantee desired bits of security
Generally speaking, we should perform a detailed analysis to check what parameters should be used in the stark prover we ultimately use to guarantee us the desired bits of security for the Resource Machine. More in details, once we pick a number of bits of security we are happy with we should derive:
* The base field size, and whether we need to use and expansion of it
* The blow up facor of the STARK proving system
* The number of queries in the FRI-based polynomial commitment scheme
* Whether to use additional proof of work for increased security of the STARK (grinding factor)

---
References:
[plonky2 issue on zero knowledge](https://github.com/0xPolygonZero/plonky2/issues/29)
[winterfell issue on zero knowledge](https://github.com/facebook/winterfell/issues/9)
[Anatomy of a STARK take on zero knowledge](https://aszepieniec.github.io/stark-anatomy/stark#adding-zero-knowledge)