# Development path proposal for ZkEVM

## Lib Decision
Independently of the library we pick, what we know for sure is that we will need to tweek it a bit.

### ZCash - halo2 - https://github.com/zcash/halo2
In the case of `halo2` we will basically need to:
- Strip the Polynomial Commitment Scheme for something like KZG10 and integrate it propperly (taking ammortization into account).
- PASTA curves won't be suitable for a KZG10 scheme (AFAIK), which means that at least, we will need to also switch to a different curve backend that follows the `ff`/`pairing` lib traits (Bn254 if possible).
- The replacement of the curve means that we need to have another pairing-friendly curve implemented and ready to be used with the `ff` trait lib. If that's not the case (the only one suitable would be [zcrypto/bls12_381](https://github.com/zkcrypto/bls12_381) AFAIK) we would need to also strip and replace the `ff` crate per `ark-ff` (the arkworks version). In that case, we gain the curves and the algebra implementations for free.

This lib is the preference as expressed in the last call as it's first of all beig audited and secondly and more importantly, being developed by a brilliant team. But we need to be concious of the amount of work that this will imply and wether is worth or not.
Another thing to take into consideration is **How easy is to write circuits with this lib, and to debug them**. Since that is something which could consume a lot of time during the development process.

### Dusk Network - dusk-plonk - https://github.com/dusk-network/plonk
In the case of `dusk-plonk` we will need to:
- Implement a bn254 lib and replace the actual bls12-381 that is in usage (not based in `ff` or any other trait lib). Or refactor the backend and make it generic, using the zcrypto or arkworks backends and their curve impls (probably arkworks as they have them all implemented).
- Check the status of the PLOOKUP integration (as is being done on a different fashion than on the halo2 impl IIRC). There's a paper comming in that will explain the logic.
And depending on that status, either help on the integration or just decide not to use it or do it differently.

Write and debug circuits with this lib is easy, but it hasn't been audited which is a quite big drawback.

## Start from the basis
Although we want to start coding circuits & gadgets ASAP, we need to be sure that we actually have proper test vectors in a format which is easy-to-use for us in any context (JSON for example).
Without some proper test vectors and a "minimally thought testing framework" we could fall into big problems when the time to test arrives.

This does not get blocked by the decision mentioned avobe. And therefore is a task that we can already start to work on [here](https://github.com/appliedzkp/zkevm-testing-vectors).

### ZkEVM testing vectors
The idea is simple. Get propper test vectors for our proof tests. But everything follows a reasoning line:

Generally the circuit design/testing procedure for the circuits could be the following:

1) We build the most basic and easiest gadgets/circuits for the most basic and easiest opcodes/slots. For example, one of the first things to test will be the PUSH and POP OPCODES, since they're included in all of the Slots (or at least the majority). Therefore, we will code a contract that has functions that execute those:

pragma solidity >=0.7.0 <0.9.0;

/**
 * @title StackPushPop
 * @dev Store & retrieve value in a variable
 */
contract StackPushPop {
    
    function push_pop() public {
        uint number = 8;
    }
}

From this two contract functions, we can extract the OPCODES, on a way we can represent them easily on a JSON or any other format that's easy to use for any language.
Once done, we can test specific state changes done by small and basic slots/OPCODES. And from this, we can start to go towards the most complex ones. Once we are sure that the gadgets/circuits for the small ones are correct and tested exhaustively.

The opcodes we want would be the ones from the specific testing functions:

{
    "push_pop" = [
    054 PUSH1 00
    056 PUSH1 08
    058 SWAP1
    059 POP
    060 POP
    ]
}

That will prevent us situations like:
- We build a circuit for a complex Slot that contains `ADD` or other "composite" OPCODES, and the circuit fails to verify a proof that should pass. If we're sure that the basis are tested, we know that the error is in the `ADD` circuit implementation and how we call the gadgets or similar, **BUT NEVER** on the implementation of the gadgets representing the OPCODES used inside `ADD`.

Once the basic opcodes like push and drop from stack are tested, we can move on to the next functions to test new slots which can deal for example with memory:

pragma solidity >=0.7.0 <0.9.0;

/**
 * @title Storage
 * @dev Store & retrieve value in a variable
 */
contract Storage {

    uint256 number;

    /**
     * @dev Store value in variable
     * @param num value to store
     */
    function sstore_test(uint256 num) public {
        number = num;
    }

    /**
     * @dev Return value 
     * @return value of 'number'
     */
    function sload_test() public view returns (uint256){
        return number;
    }
    
    
    // Size of 0_code will not be parametric to avoid `extcodesize`
    // usage
    function memory_test(address _addr) public view returns (bytes memory o_code) {
        assembly {
            let size := 0x40
            // allocate output byte array - this could also be done without assembly
            // by using o_code = new bytes(size)
            o_code := mload(0x40)
            // new "memory end" including padding
            mstore(0x40, 0x7f)
            // store length in memory
            mstore(o_code, size)
            // actually retrieve the code, this needs assembly
            extcodecopy(_addr, add(o_code, 0x20), 0, size)
        }
    }
}

Here we will of course need to use `PUSH` and `DUP`, but since they'll be already tested, we can focus on the tests for `SLOAD`, `SSTORE`, `MLOAD`, `MSTORE`.

As seen, having these contracts with functions which test specific slots/OPCODES on the most precise and individual way possible, allows us to extract OPCODES and previous and past states after the execution.
And that, is what we use as test vectors which will be then used to test our circuits.

## Parallel development

Since we will need to tweek any lib we pick but it should already give the change to write circuits, we could also decide to "split" ourseleves a bit. And while some part of the team takes care of replacing the backend of the lib, the other can use the previous backend **AS THE CIRCUIT API WILL STILL BE THE SAME** and on that way advance in the gadget/circuit testing path.

## TODOs
- [ ] Write contracts for the slots/OPCODES we want to test and check with the team wether they're suitable to be used as test vectors.
- [ ] Write some kind of BUS/BUS-Mapping prototype which will serve the data on the same way as the actual one will do it(at least on the same fashion).
On that way the tests will be more reallistic and close to the final application.
- [ ] Pick a PLONK lib and write the specific TODOs for it.
- [ ] Check cc's project as per data visualization: https://github.com/ChihChengLiang/vmtrace_visualizer