Define the AIR program for our STF

[Nashtare]

Our State Transition Function could be similar to whats's being prover in the rollup tutorial for R1CS in https://github.com/arkworks-rs/r1cs-tutorial but with extra checks to prevent double spendings (for instance nonce check)

[Nashtare]

We may also need to uniformize the use of Rescue throughout the AIR program of the STF. Currently, the adaptation of the Merkle tree by Travis is using the implementation (tailored for f128 but that's a detail) in examples/src/utils/rescue.rs, from the Rescue Prime specification, with security margin at 40% to reduce the number of rounds to 7 and a state of 6 field elements, while I'm using for Schnorr signature verification the implementation in f252 with security margin of 50%, 14 rounds and a state of 4 field elements.

The Schnorr signature takes 512 steps as a standalone AIR before merging it with the rest of the operations (258 steps in practice, padded to the next power of two).

Depending on whether we want to go for a sidechain state size of 2^16 or 2^32 for a start, and depending if we process the Schnorr verification sequentially or in parallel with Merkle path authentication and update, one option may be preferable than the other.

• if we process things in parallel, it would be preferable to change the Merkle implementation to use Rescue with 14 rounds (padded to 16), and smaller hash state, as it would lead to 512 steps for the Merkle part, not more than the padded Schnorr verification.

• if things are done sequentially (i.e. reusing existing registers for further operations), then it would most likely (to be verified) be useful to use the current implementation in Merkle, as otherwise 1 transition would already be too large (number of steps wise) and proving time would probably be impractical for large batches of 4096 / 8192 transactions, as originally expected.

[Nashtare]

Actually, the Schnorr signature verification number of steps is dominated by the cost of doing a double-and-add. But as both the Scalar Field and the Base Field are of size 252, we could skip the first bits, hence having the whole execution trace being padded to 256 steps instead of 512.
Then this would impact the choice in the above comment for Merkle, as if we do things in parallel, with a state of 2^32, using the first instantiation of Rescue Prime would give us 256 steps as well (32 * 8) while using the one currently implemented for f252 and used in Schnorr would lead to 512 steps for the Merkle portion, hence leading to an overall periodic trace of size Nx512 steps (for N transactions) instead of Nx256.

[Nashtare]

AIR program finalized. There remains some optimizations / proper analysis to ensure that everything is correct but we can close this issue.