##
- Definition of a gate: An arithmetic operation
- Definition of a wire: Directional integer input to a gate
- Definition of the witness: all values "witnessed" in the circuit computation

## R1CS
- All gates are "fan-in 2, fan-out 1" addition or multiplication gates
- "low degree constraints"
- because of how r1cs arithmetization works, [addition gates are "free"](https://crypto.stackexchange.com/questions/103947/arithmetic-circuits-to-r1cs-do-we-consider-addition-gates-or-not)

## PLONKish

- Types of columns
- Advice: private witness values that only the prover can see
- Fixed: hardcoded values determined when the proving and verifying key are generated
- Instance: public witness values that verifier must supply themselves to check proof
- Two types of constraints
- Gate constraints: our defined arithmetic expressions we pass wires into
- Copy constraints: wire one cell to another and force them to be equal

Vanilla PlonK equation
$$
\left(Q_{L_{i}}\right) a_{i}+\left(Q_{R_{i}}\right) b_{i}+\left(Q_{O_{i}}\right) c_{i}+\left(Q_{M_{i}}\right) a_{i} b_{i}+Q_{C_{i}}=0
$$

- Q: Fixed
- A: Advice
- Constrain addition of 4+3=7: `1(3) + 1(4) + -1(7) + 0(3*4) + 0 = 0`
- Constrain multiplication of 4*3=12: `0(3) + 0(4) + -1(12) + 1(3*4) + 0 = 0`
- Constrain constant value = 44: `1(44) + 0(?) + 0(?) + 0(44*?) + (-44) = 0

### Custom gates: Halo2
- [Fibonacci example](https://github.com/therealyingtong/halo2-hope)
- [merkle example](https://github.com/DrPeterVanNostrand/halo2-merkle/blob/main/src/main.rs)
- [battlezips example](https://www.figma.com/file/59ZzSGtuK7XH8cpL1Iwhz4/BattleZips-V2%3A-Halo-2-BoardValidity-Circuit?type=design&node-id=12-2&mode=design&t=vVg36JuKEkoS7Ca4-0)

### Custom gates in Barretenberg
- a bit out of my wheelhouse right now but can look quickly
- Barretenberg should have [4 advice columns and 11 fixed columns](https://github.com/AztecProtocol/barretenberg/blob/4a1b5322dc78921d253e6a374eba0b616ab788df/cpp/src/barretenberg/proof_system/circuit_builder/ultra_circuit_builder.hpp#L249-L263)
- [Boolean constraint](https://github.com/AztecProtocol/barretenberg/blob/4a1b5322dc78921d253e6a374eba0b616ab788df/cpp/src/barretenberg/proof_system/circuit_builder/ultra_circuit_builder.cpp#L333)