# ZKCTF 2024 Writeup

[TOC]

## Day1

https://github.com/scalebit/zkCTF-day1

### Checkin 100pt

checkin

import hashlib
import json
import requests
from pwn import *
from web3 import Web3
import time
import os

RPC_URL = "http://47.76.89.7:8545/"
FAUCET = "http://47.76.89.7:8080/api/claim"
CHALLENGE_IP = "47.76.89.7"
CHALLENGE_PORT = 20010
CHAINID = 19875
AIRDROP = False

provider = Web3(Web3.HTTPProvider(RPC_URL))

# $ cast wallet new
private_key = "0x2abc57ce76f7b2117b8ff48d02617bbaf1a0c42f25540f7926cdffff0f621884"
player_address = "0x490c28B6E6880b30642753F03eD7c25Ef180E16e"

def wait_for_tx(provider, tx_hash):
    # eth.wait_for_transaction_receipt is available,
    # but manually implemented for in-progress message
    while True:
        try:
            receipt = provider.eth.get_transaction_receipt(tx_hash)
            print("Receipt:", receipt)
            print("Balance after tx:", provider.eth.get_balance(player_address))
            return receipt
        except Exception as e:
            if "not found" in str(e):
                print("Waiting for the transaction...")
            else:
                raise e
        time.sleep(3)

def build_param(provider):
    return {
        "gas": 5000000,
        "gasPrice": Web3.to_wei(100, "gwei"),
        "nonce": provider.eth.get_transaction_count(player_address),
    }

def transact_and_wait(provider, transaction, private_key):
    print("Sending:", transaction)
    signed_tx = provider.eth.account.sign_transaction(transaction, private_key)
    tx_hash = provider.eth.send_raw_transaction(signed_tx.rawTransaction)
    return wait_for_tx(provider, tx_hash)

if AIRDROP:
    print("[*] Get ether from faucet")
    tx_hash = requests.post(FAUCET, data={"address": player_address}).text.split(': ')[1]
    wait_for_tx(provider, tx_hash)

print("[*] Generate abi from source")
if not os.path.exists("out"):
    os.system(f"solc verifier.sol --abi -o out")

print("[*] Deploy challenge contract")
io = remote(CHALLENGE_IP, CHALLENGE_PORT)
io.sendlineafter(b"input your choice:", b"1")
io.recvuntil(b"deployer account: ")
deployer_address = io.recvline().strip().decode()
io.recvuntil(b"token: ")
token = io.recvline().strip()
print(f"{deployer_address=}")
print(f"{token=}")
io.close()

transact_and_wait(provider, {
        "chainId": CHAINID,
        "to": deployer_address,
        "value": provider.to_wei(0.01, "ether"),
        "gas": 5000000,
        "gasPrice": Web3.to_wei(100, "gwei"),
        "nonce": provider.eth.get_transaction_count(player_address)
    }, private_key)

io = remote(CHALLENGE_IP, CHALLENGE_PORT)
io.sendlineafter(b"input your choice:", b"2")
io.sendlineafter(b"input your token:", token)
io.recvuntil(b"contract address: ")
contract_address = io.recvline().strip().decode()
print(f"{contract_address=}")

with open(f"out/Checkin.abi") as f:
    abi = json.load(f)
    challenge = provider.eth.contract(contract_address, abi=abi)

print("[*] Compile circuit")
os.system(f"circom CheckIn.circom --r1cs --wasm")

print("[*] Generate proof")
with open("input.json", 'w') as f:
    json.dump({"a": 1, "b": 2}, f)
os.system(f"node CheckIn_js/generate_witness.js CheckIn_js/CheckIn.wasm input.json witness.wtns")
os.system(f"snarkjs g16p CheckIn_groth16.zkey witness.wtns proof.json public.json")
os.system("snarkjs generatecall > calldata.txt")

print("[*] Submit proof")
with open("calldata.txt") as f:
    calldata = f.read().strip().replace("][", "], [")
pa, pb, pc, public_inputs = eval(calldata)
pa = [int(x, 0) for x in pa]
pb = [[int(x, 0) for x in line] for line in pb]
pc = [int(x, 0) for x in pc]
public_inputs = [int(x, 0) for x in public_inputs]

function = challenge.functions.verify(pa, pb, pc, public_inputs)
transaction = function.build_transaction(build_param(provider))
transact_and_wait(provider, transaction, private_key)

print("[*] Get flag")
io = remote(CHALLENGE_IP, CHALLENGE_PORT)
io.sendlineafter(b"input your choice:", b"3")
io.sendlineafter(b"input your token:", token)
io.interactive()

### Kid's Math 200pt

use halo2_proofs::arithmetic::FieldExt;
use halo2_proofs::{
    arithmetic::Field,
    circuit::{AssignedCell, Chip, Layouter, Region, SimpleFloorPlanner, Value},
    dev::MockProver,
    pasta::{EqAffine, Fp},
    plonk::{
        create_proof, keygen_pk, keygen_vk, verify_proof, Advice, Circuit, Column,
        ConstraintSystem, Error, Expression, Fixed, Instance, ProvingKey, Selector, SingleVerifier,
        VerifyingKey,
    },
    poly::{commitment::Params, Rotation},
    transcript::{Blake2bRead, Blake2bWrite, Challenge255},
};
use serde::{Deserialize, Serialize};
use std::marker::PhantomData;

#[derive(Debug, Clone)]
pub struct FibonacciConfig {
    pub col_a: Column<Advice>,
    pub col_b: Column<Advice>,
    pub col_c: Column<Advice>,
    pub col_pa: Column<Fixed>,
    pub col_pb: Column<Fixed>,
    pub col_pc: Column<Fixed>,
    pub selector: Selector,
    pub instance: Column<Instance>,
}

#[derive(Debug, Clone)]
struct FibonacciChip<F: FieldExt> {
    config: FibonacciConfig,
    _marker: PhantomData<F>,
}

impl<F: FieldExt> FibonacciChip<F> {
    pub fn construct(config: FibonacciConfig) -> Self {
        Self {
            config,
            _marker: PhantomData,
        }
    }

    pub fn configure(meta: &mut ConstraintSystem<F>) -> FibonacciConfig {
        let col_a = meta.advice_column();
        let col_b = meta.advice_column();
        let col_c = meta.advice_column();
        let col_pa = meta.fixed_column();
        let col_pb = meta.fixed_column();
        let col_pc = meta.fixed_column();
        let selector = meta.selector();
        let instance = meta.instance_column();

        meta.enable_equality(col_a);
        meta.enable_equality(col_b);
        meta.enable_equality(col_c);
        meta.enable_equality(instance);

        ///////////////////////// Please implement code here /////////////////////////
        meta.create_gate("poly", |meta| {
            let s = meta.query_selector(selector);
            let a = meta.query_advice(col_a, Rotation::cur());
            let b = meta.query_advice(col_b, Rotation::cur());
            let c = meta.query_advice(col_c, Rotation::cur());
            let pa = meta.query_fixed(col_pa, Rotation::cur());
            let pb = meta.query_fixed(col_pb, Rotation::cur());
            let pc = meta.query_fixed(col_pc, Rotation::cur());
            vec![s * (- (a * pa) + (b * pb) - pc - c)]
        });
        ///////////////////////// End implement /////////////////////////
        
        FibonacciConfig {
            col_a,
            col_b,
            col_c,
            col_pa,
            col_pb,
            col_pc,
            selector,
            instance,
        }
    }

    #[allow(clippy::type_complexity)]
    pub fn assign_first_row(
        &self,
        mut layouter: impl Layouter<F>,
    ) -> Result<(AssignedCell<F, F>, AssignedCell<F, F>, AssignedCell<F, F>), Error> {
        layouter.assign_region(
            || "first row",
            |mut region| {
                self.config.selector.enable(&mut region, 0)?;

                let a_cell = region.assign_advice_from_instance(
                    || "f(0)",
                    self.config.instance,
                    0,
                    self.config.col_a,
                    0,
                )?;

                let b_cell = region.assign_advice_from_instance(
                    || "f(1)",
                    self.config.instance,
                    1,
                    self.config.col_b,
                    0,
                )?;

                let c_cell = region.assign_advice(
                    || "a + b",
                    self.config.col_c,
                    0,
                    || a_cell.value().copied() + b_cell.value(),
                )?;

                // Assign pa here!
                ///////////////////////// Please implement code here /////////////////////////
                region.assign_fixed(
                    || "pa",
                    self.config.col_pa,
                    0,
                    || Value::known(F::from(125)),
                )?;
                ///////////////////////// End implement /////////////////////////
                // Assign pb here!
                ///////////////////////// Please implement code here /////////////////////////
                region.assign_fixed(
                    || "pb",
                    self.config.col_pb,
                    0,
                    || Value::known(F::from(127)),
                )?;
                ///////////////////////// End implement /////////////////////////
                // Assign pc here!
                ///////////////////////// Please implement code here /////////////////////////
                region.assign_fixed(
                    || "pc",
                    self.config.col_pc,
                    0,
                    || Value::known(F::from(126)),
                )?;
                ///////////////////////// End implement /////////////////////////
                Ok((a_cell, b_cell, c_cell))
            },
        )
    }

    pub fn assign_row(
        &self,
        mut layouter: impl Layouter<F>,
        prev_b: &AssignedCell<F, F>,
        prev_c: &AssignedCell<F, F>,
    ) -> Result<AssignedCell<F, F>, Error> {
        layouter.assign_region(
            || "next row",
            |mut region| {
                self.config.selector.enable(&mut region, 0)?;

                prev_b.copy_advice(|| "a", &mut region, self.config.col_a, 0)?;
                prev_c.copy_advice(|| "b", &mut region, self.config.col_b, 0)?;

                let c_value = - prev_b.value().copied() * Value::known(F::from(125))
                    + prev_c.value().copied() * Value::known(F::from(127))
                    - Value::known(F::from(126));

                let c_cell =
                    region.assign_advice(|| "c", self.config.col_c, 0, || c_value)?;

                region.assign_fixed(
                    || "pa",
                    self.config.col_pa,
                    0,
                    || Value::known(F::from(125)),
                )?;
                // Assign pb here!
                ///////////////////////// Please implement code here /////////////////////////
                region.assign_fixed(
                    || "pb",
                    self.config.col_pb,
                    0,
                    || Value::known(F::from(127)),
                )?;
                ///////////////////////// End implement /////////////////////////
                // Assign pc here!
                ///////////////////////// Please implement code here /////////////////////////
                region.assign_fixed(
                    || "pc",
                    self.config.col_pc,
                    0,
                    || Value::known(F::from(126)),
                )?;
                ///////////////////////// End implement /////////////////////////
                Ok(c_cell)
            },
        )
    }

    pub fn expose_public(
        &self,
        mut layouter: impl Layouter<F>,
        cell: &AssignedCell<F, F>,
        row: usize,
    ) -> Result<(), Error> {
        layouter.constrain_instance(cell.cell(), self.config.instance, row)
    }
}

#[derive(Default, Serialize, Deserialize)]
pub struct FibonacciCircuit<F>(pub PhantomData<F>);

impl<F: FieldExt> Circuit<F> for FibonacciCircuit<F> {
    type Config = FibonacciConfig;
    type FloorPlanner = SimpleFloorPlanner;

    fn without_witnesses(&self) -> Self {
        Self::default()
    }

    fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
        FibonacciChip::configure(meta)
    }

    fn synthesize(
        &self,
        config: Self::Config,
        mut layouter: impl Layouter<F>,
    ) -> Result<(), Error> {
        let chip = FibonacciChip::construct(config);

        let (_, mut prev_b, mut prev_c) =
            chip.assign_first_row(layouter.namespace(|| "first row"))?;

        for _i in 3..5 {
            let c_cell = chip.assign_row(layouter.namespace(|| "next row"), &prev_b, &prev_c)?;
            prev_b = prev_c;
            prev_c = c_cell;
        }

        chip.expose_public(layouter.namespace(|| "out"), &prev_c, 2)?;
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::FibonacciCircuit;
    use halo2_proofs::{dev::MockProver, pasta::Fp};
    use std::marker::PhantomData;

    #[test]
    fn fibonacci_example1() {
        let k = 4;
        //1,2,3,5,?
        let quiz = 134;
        let a = Fp::from(1); // F[0]
        let b = Fp::from(2); // F[1]
        let out = Fp::from(quiz); // F[5]

        let circuit = FibonacciCircuit(PhantomData);

        let mut public_input = vec![a, b, out];

        let prover = MockProver::run(k, &circuit, vec![public_input.clone()]).unwrap();
        prover.assert_satisfied();
    }
}

### Int Division 200pt

use halo2_proofs::{
    arithmetic::Field,
    circuit::{AssignedCell, Chip, Layouter, Region, Value},
    plonk::{Advice, Column, ConstraintSystem, Error, Expression, Instance, Selector, TableColumn},
    poly::{kzg, Rotation},
};
use std::{cell, marker::PhantomData};

const RANGE_BITS: usize = 8;

pub struct DivChip<F: Field> {
    pub config: DivConfig,
    _marker: PhantomData<F>,
}

// You could delete or add columns here
#[derive(Clone, Debug)]
pub struct DivConfig {
    // Dividend
    a: Column<Advice>,
    // Divisor
    b: Column<Advice>,
    // Quotient
    c: Column<Advice>,
    // Remainder
    r: Column<Advice>,
    // Aux
    k: Column<Advice>,
    // Range
    range: TableColumn,
    // Instance
    instance: Column<Instance>,
    // Selector
    selector: Selector,
    q_lookup: Selector,
}

impl<F: Field> Chip<F> for DivChip<F> {
    type Config = DivConfig;
    type Loaded = ();

    fn config(&self) -> &Self::Config {
        &self.config
    }

    fn loaded(&self) -> &Self::Loaded {
        &()
    }
}

impl<F: Field> DivChip<F> {
    pub fn construct(config: <Self as Chip<F>>::Config) -> Self {
        Self {
            config,
            _marker: PhantomData,
        }
    }

    pub fn configure(meta: &mut ConstraintSystem<F>) -> <Self as Chip<F>>::Config {
        // Witness
        let col_a = meta.advice_column();
        let col_b = meta.advice_column();
        let col_c = meta.advice_column();
        let col_r = meta.advice_column();
        let col_k = meta.advice_column();
        // Selector
        let selector = meta.complex_selector();
        let q_lookup = meta.complex_selector();
        // Range
        let range = meta.lookup_table_column();
        // Instance
        let instance = meta.instance_column();

        meta.enable_equality(col_a);
        meta.enable_equality(col_b);
        meta.enable_equality(col_c);
        meta.enable_equality(col_r);
        meta.enable_equality(col_k);
        meta.enable_equality(instance);

        ///////////////////////// Please implement code here /////////////////////////
        // unimplemented!();
        /// check1: dividen == divisor*quotient+remainder
        /// check2: remainder < divisor
        meta.create_gate("div check", |meta|{
            let a = meta.query_advice(col_a, Rotation::cur());
            let b = meta.query_advice(col_b, Rotation::cur());
            let c = meta.query_advice(col_c, Rotation::cur());
            let r  = meta.query_advice(col_r, Rotation::cur());
            let k = meta.query_advice(col_k, Rotation::cur());
            let s_div = meta.query_selector(selector);
            vec![
                (a.clone() - (b.clone()*c.clone()+r.clone())) * s_div.clone(),
                (b.clone() - (r.clone() + k.clone())) * s_div.clone(),
            ]
        });

        meta.lookup("look up a", |meta|{
            let a = meta.query_advice(col_a, Rotation::cur());
            let q_lookup = meta.query_selector(q_lookup);
            vec![
                (a.clone() * q_lookup.clone(), range.clone())
            ]
        });
        meta.lookup("look up b", |meta|{
            let b = meta.query_advice(col_b, Rotation::cur());
            let q_lookup = meta.query_selector(q_lookup);
            vec![
                (b.clone() * q_lookup.clone(), range)
            ]
        });
        meta.lookup("look up c", |meta|{
            let c = meta.query_advice(col_c, Rotation::cur());
            let q_lookup = meta.query_selector(q_lookup);
            vec![
                (c.clone() * q_lookup.clone(), range)
            ]
        });
        meta.lookup("look up r", |meta|{
            let r = meta.query_advice(col_r, Rotation::cur());
            let q_lookup = meta.query_selector(q_lookup);
            vec![
                (r.clone() * q_lookup.clone(), range)
            ]
        });
        meta.lookup("look up k", |meta|{
            let k = meta.query_advice(col_k, Rotation::cur());
            let q_lookup = meta.query_selector(q_lookup);
            vec![
                (k.clone() * q_lookup.clone(), range)
            ]
        });
        
        
        ///////////////////////// End implement /////////////////////////

        DivConfig {
            a: col_a,
            b: col_b,
            c: col_c,
            r: col_r,
            k: col_k,
            range,
            instance,
            selector,
            q_lookup,
        }
    }

    // Assign range for U8 range check
    pub fn assign_range(&self, mut layouter: impl Layouter<F>) -> Result<(), Error> {
        // let config = &self.config;
        ///////////////////////// Please implement code here /////////////////////////
        // unimplemented!();
        let mut count = F::ZERO;
        layouter.assign_table(||"table column", |mut table|{
            for index in 0..(1 << 8) {
                table.assign_cell(
                    || "table_column",
                    self.config.range,
                    index,
                    || Value::known(count),
                )?;
                count = count+F::ONE;
            }
            Ok(())
        })?;
        ///////////////////////// End implement /////////////////////////

        Ok(())
    }

    // Assign witness for division
    pub fn assign_witness(
        &self,
        mut layouter: impl Layouter<F>,
        a: F,
        b: F,
        c: F,
    ) -> Result<AssignedCell<F, F>, Error> {
        // let config = &self.config;
        ///////////////////////// Please implement code here /////////////////////////
        // unimplemented!();
        let cell_c = layouter.assign_region(||"assign first row", |mut region|{
            region.assign_advice(||"assign a", self.config.a, 0, ||Value::known(a))?;
            region.assign_advice(||"assign b", self.config.b, 0, ||Value::known(b))?;
            let cell_c = region.assign_advice(||"assign c", self.config.c, 0, ||Value::known(c))?;
            let mut r = a-b*c;
            region.assign_advice(||"assign r ", self.config.r, 0, ||Value::known(r))?;
            println!("a-b*c r {:?}",a-b*c);
            region.assign_advice(||"assign b-r", self.config.k, 0, ||Value::known(b-r))?;
            println!("b-r > 0  {:?}",b-r);
            self.config.selector.enable(&mut region, 0)?;          
            self.config.q_lookup.enable(&mut region, 0)?;     
            Ok(cell_c) 
        })?;
        Ok(cell_c)
        ///////////////////////// End implement /////////////////////////
    }

    pub fn expose_public(
        &self,
        mut layouter: impl Layouter<F>,
        cell: &AssignedCell<F, F>,
    ) -> Result<(), Error> {
        layouter.constrain_instance(cell.cell(), self.config.instance, 0)
    }
}

/* ================Circuit========================== */
use halo2_proofs::circuit::SimpleFloorPlanner;
use halo2_proofs::plonk::Circuit;
#[derive(Clone, Debug)]
pub struct CircuitConfig {
    config: DivConfig,
}

#[derive(Default, Debug)]
pub struct DivCircuit<F: Field> {
    pub a: F,
    pub b: F,
    pub c: F,
}

impl<F: Field> Circuit<F> for DivCircuit<F> {
    type Config = CircuitConfig;
    type FloorPlanner = SimpleFloorPlanner;
    #[cfg(feature = "circuit-params")]
    type Params = ();

    fn without_witnesses(&self) -> Self {
        Self::default()
    }

    fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
        let config = DivChip::<F>::configure(meta);
        CircuitConfig { config }
    }

    fn synthesize(
        &self,
        config: Self::Config,
        mut layouter: impl Layouter<F>,
    ) -> Result<(), Error> {
        let chip = DivChip::<F>::construct(config.config);
        chip.assign_range(layouter.namespace(|| "assign range"))?;
        let cell_c = chip.assign_witness(
            layouter.namespace(|| "assign witness"),
            self.a,
            self.b,
            self.c,
        )?;
        chip.expose_public(layouter.namespace(|| "expose public"), &cell_c)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use ff::PrimeField;
    use halo2_proofs::dev::MockProver;
    use halo2curves::bn256::Fr;

    #[test]
    fn sanity_check() {
        let k = 10;
        let a = Fr::from_u128(10);
        let b = Fr::from_u128(3);
        let c = Fr::from_u128(3);
        let circuit: DivCircuit<Fr> = DivCircuit { a, b, c };
        let prover = MockProver::run(k, &circuit, vec![vec![c]]).unwrap();
        assert_eq!(prover.verify(), Ok(()));
    }
}

use halo2_proofs::{
    plonk::{create_proof, keygen_pk, keygen_vk, verify_proof, ProvingKey},
    poly::kzg::{
        commitment::{KZGCommitmentScheme, ParamsKZG},
        multiopen::{ProverGWC, VerifierGWC},
        strategy::SingleStrategy,
    },
    transcript::{
        Blake2bRead, Blake2bWrite, Challenge255, TranscriptReadBuffer, TranscriptWriterBuffer,
    },
    SerdeFormat,
};
use halo2curves::bn256::{Bn256, Fr, G1Affine};
use rand::rngs::OsRng;
use std::{
    fs::File,
    io::{BufReader, BufWriter, Write},
};

fn generate_keys(k: u32, circuit: &DivCircuit<Fr>) -> (ParamsKZG<Bn256>, ProvingKey<G1Affine>) {
    let params = ParamsKZG::<Bn256>::setup(k, OsRng);
    let vk = keygen_vk(&params, circuit).expect("vk should not fail");
    let pk = keygen_pk(&params, vk, circuit).expect("pk should not fail");
    (params, pk)
}

fn generate_proof(k: u32, circuit: DivCircuit<Fr>) {
    let (params, pk) = generate_keys(k, &circuit);
    let instances: &[&[Fr]] = &[&[circuit.c]];
    let f = File::create(format!("{}", "proof")).unwrap();
    let mut proof_writer = BufWriter::new(f);
    let mut transcript = Blake2bWrite::<_, _, Challenge255<_>>::init(&mut proof_writer);
    create_proof::<
        KZGCommitmentScheme<Bn256>,
        ProverGWC<'_, Bn256>,
        Challenge255<G1Affine>,
        _,
        Blake2bWrite<_, G1Affine, Challenge255<_>>,
        _,
    >(
        &params,
        &pk,
        &[circuit],
        &[instances],
        OsRng,
        &mut transcript,
    )
    .expect("prover should not fail");
    let proof_writer = transcript.finalize();
    let _ = proof_writer.flush();
    // Dump params
    {
        let f = File::create(format!("{}", "param")).unwrap();
        let mut writer = BufWriter::new(f);
        params
            .write_custom(&mut writer, SerdeFormat::RawBytes)
            .unwrap();
        let _ = writer.flush();
    }
    // Dump vk
    {
        let f = File::create(format!("{}", "vk")).unwrap();
        let mut writer = BufWriter::new(f);
        pk.get_vk()
            .write(&mut writer, SerdeFormat::RawBytes)
            .unwrap();
        let _ = writer.flush();
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use ff::PrimeField;
    use halo2_proofs::dev::MockProver;
    use halo2curves::bn256::Fr;

    #[test]
    fn sanity_check() {
        let k = 10;
        let a = Fr::from_u128(10);
        let b = Fr::from_u128(3);
        let c = Fr::from_u128(3);
        let circuit: DivCircuit<Fr> = DivCircuit { a, b, c };
        let prover = MockProver::run(k, &circuit, vec![vec![c]]).unwrap();
        assert_eq!(prover.verify(), Ok(()));
    }
}

### Roundabout 300pt

#### Part 1

Reverse the simple 2-round Feistel network

$$ m.outs[0] = 3066844496547985532785966973086993824 = S[0].xL_{out} = (1+a)^5 \Rightarrow a = 19830713$$

#### Part 2
$$c=3066844496547985532785966973086993824$$
$$9b^2+37622140664026667386099315436167897444086165906536960040182069717656571868=c^2b^2 $$

$$\Rightarrow (c^2-9)b^2=37622140664026667386099315436167897444086165906536960040182069717656571868$$
$$\Rightarrow b=2$$

import hashlib
import json
import requests
from pwn import *
from web3 import Web3
import time
import os

RPC_URL = "http://47.76.89.7:8545/"
FAUCET = "http://47.76.89.7:8080/api/claim"
CHALLENGE_IP = "47.76.89.7"
CHALLENGE_PORT = 20011
CHAINID = 19875
AIRDROP = False

provider = Web3(Web3.HTTPProvider(RPC_URL))

# $ cast wallet new
private_key = "0x2abc57ce76f7b2117b8ff48d02617bbaf1a0c42f25540f7926cdffff0f621884"
player_address = "0x490c28B6E6880b30642753F03eD7c25Ef180E16e"

def wait_for_tx(provider, tx_hash):
    # eth.wait_for_transaction_receipt is available,
    # but manually implemented for in-progress message
    while True:
        try:
            receipt = provider.eth.get_transaction_receipt(tx_hash)
            print("Receipt:", receipt)
            print("Balance after tx:", provider.eth.get_balance(player_address))
            return receipt
        except Exception as e:
            if "not found" in str(e):
                print("Waiting for the transaction...")
            else:
                raise e
        time.sleep(3)

def build_param(provider):
    return {
        "gas": 5000000,
        "gasPrice": Web3.to_wei(100, "gwei"),
        "nonce": provider.eth.get_transaction_count(player_address),
    }

def transact_and_wait(provider, transaction, private_key):
    print("Sending:", transaction)
    signed_tx = provider.eth.account.sign_transaction(transaction, private_key)
    tx_hash = provider.eth.send_raw_transaction(signed_tx.rawTransaction)
    return wait_for_tx(provider, tx_hash)

if AIRDROP:
    print("[*] Get ether from faucet")
    tx_hash = requests.post(FAUCET, data={"address": player_address}).text.split(': ')[1]
    wait_for_tx(provider, tx_hash)

print("[*] Generate abi from source")
if not os.path.exists("out"):
    os.system(f"solc verifier.sol --abi -o out")

print("[*] Deploy challenge contract")
io = remote(CHALLENGE_IP, CHALLENGE_PORT)
io.sendlineafter(b"input your choice:", b"1")
io.recvuntil(b"deployer account: ")
deployer_address = io.recvline().strip().decode()
io.recvuntil(b"token: ")
token = io.recvline().strip()
print(f"{deployer_address=}")
print(f"{token=}")
io.close()

transact_and_wait(provider, {
        "chainId": CHAINID,
        "to": deployer_address,
        "value": provider.to_wei(0.01, "ether"),
        "gas": 5000000,
        "gasPrice": Web3.to_wei(100, "gwei"),
        "nonce": provider.eth.get_transaction_count(player_address)
    }, private_key)

io = remote(CHALLENGE_IP, CHALLENGE_PORT)
io.sendlineafter(b"input your choice:", b"2")
io.sendlineafter(b"input your token:", token)
io.recvuntil(b"contract address: ")
contract_address = io.recvline().strip().decode()
print(f"{contract_address=}")

with open(f"out/Roundabout.abi") as f:
    abi = json.load(f)
    challenge = provider.eth.contract(contract_address, abi=abi)

print("[*] Compile circuit")
os.system(f"circom Roundabout.circom --r1cs --wasm")

print("[*] Generate proof")
with open("input.json", 'w') as f:
    json.dump({"a": 19830713, "b": 2}, f)
os.system(f"node Roundabout_js/generate_witness.js Roundabout_js/Roundabout.wasm input.json witness.wtns")
os.system(f"snarkjs g16p Roundabout_groth16.zkey witness.wtns proof.json public.json")
os.system("snarkjs generatecall > calldata.txt")

print("[*] Submit proof")
with open("calldata.txt") as f:
    calldata = f.read().strip().replace("][", "], [")
pa, pb, pc, public_inputs = eval(calldata)
pa = [int(x, 0) for x in pa]
pb = [[int(x, 0) for x in line] for line in pb]
pc = [int(x, 0) for x in pc]
public_inputs = [int(x, 0) for x in public_inputs]


function = challenge.functions.verify(pa, pb, pc, public_inputs)
transaction = function.build_transaction(build_param(provider))
transact_and_wait(provider, transaction, private_key)

print("[*] Get flag")
io = remote(CHALLENGE_IP, CHALLENGE_PORT)
io.sendlineafter(b"input your choice:", b"3")
io.sendlineafter(b"input your token:", token)
io.interactive()

### Ethereal Quest 400pt

TLDR: Exploit the leaked $\tau$ to forge proofs

#### Find $\tau$

Googling the constant in `SRS_G1_X` => https://github.com/matter-labs/era-compiler-tests/blob/9a8c6d99d84cec7343e79a28b2a6df49aef57796/yul/precompiles/ecmul_source.yul#L68-L82

$\tau = 115792089237316195423570985008687907853269984665640564039457584007913129639935$

#### Forge proofs

$$ \pi = \frac{1}{\tau - i} (C - f(i)\cdot G_1) $$

case "forge":
    var sword []fr.Element
    f, err := os.Open("sword.json")
    panicErr(err)
    defer f.Close()
    decoder := json.NewDecoder(f)
    err = decoder.Decode(&sword)
    panicErr(err)

    nonce, err := mintContract.GetNonce(nil, transactor.From)
    panicErr(err)
    nonceFr := new(fr.Element)
    nonceFr.SetBigInt(nonce)
    fmt.Printf("Minting the %s gem\n", ordinal(int(nonce.Int64())))

    var commitment bn254.G1Affine
    x := new(big.Int)
    y := new(big.Int)
    x.SetString("20134758549359140843263308188386124980029362768750192346333946559660133597144", 10)
    y.SetString("16682898361056444335233067474677257163471745908046817430632223194406920803311", 10)
    commitment.X.SetBigInt(x)
    commitment.Y.SetBigInt(y)

    s := new(big.Int)
    s.SetString("115792089237316195423570985008687907853269984665640564039457584007913129639935", 10)

    forge_y := new(big.Int)
    forge_y.SetString("233", 10)

    order := new(big.Int)
    order.SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10)

    // k = 1/(s-nonce)
    k := new(big.Int)
    k.Sub(s, nonce)
    k.ModInverse(k, order)

    // proof = k*(C - forge_y*G1)
    proof := new(bn254.G1Affine)
    tmp := new(bn254.G1Affine)
    tmp.ScalarMultiplication(&SRS.Pk.G1[0], forge_y)
    proof.Sub(&commitment, tmp)
    proof.ScalarMultiplication(proof, k)
    fmt.Printf("Proof: %s\n", spew.Sdump(proof))

    proofPoint := G1AffineToG1Point(proof)

    _, err = mintContract.Mint(transactor, *proofPoint, forge_y)

## Day2

https://github.com/scalebit/zkCTF-day2

### Is Zero 200pt

use std::marker::PhantomData;

use halo2_proofs::halo2curves::ff::PrimeField;
use halo2_proofs::{
    arithmetic::Field,
    circuit::{AssignedCell, Chip, Layouter, Region, SimpleFloorPlanner, Value},
    plonk::{Advice, Circuit, Column, ConstraintSystem, Error, Expression, Selector},
    poly::Rotation,
};

trait NumericInstructions<F: Field>: Chip<F> {
    /// Variable representing a number.
    type Num;

    fn load_private(
        &self,
        layouter: impl Layouter<F>,
        v: &[Value<F>],
    ) -> Result<Vec<Self::Num>, Error>;

    fn is_zero(
        &self,
        layouter: impl Layouter<F>,
        a: &[Self::Num],
        b: &[Self::Num],
    ) -> Result<Vec<Self::Num>, Error>;
}

/// The chip that will implement our instructions! Chips store their own
/// config, as well as type markers if necessary.
pub struct FieldChip<F: Field> {
    config: FieldConfig,
    _marker: PhantomData<F>,
}

/// Chip state is stored in a config struct. This is generated by the chip
/// during configuration, and then stored inside the chip.
#[derive(Clone, Debug)]
pub struct FieldConfig {
    advice: [Column<Advice>; 3],
    s_is_zero: Selector,
}

impl<F: Field> FieldChip<F> {
    fn construct(config: <Self as Chip<F>>::Config) -> Self {
        Self {
            config,
            _marker: PhantomData,
        }
    }

    fn configure(
        meta: &mut ConstraintSystem<F>,
        advice: [Column<Advice>; 3],
    ) -> <Self as Chip<F>>::Config {
        for column in &advice {
            meta.enable_equality(*column);
        }
        let s_is_zero = meta.selector();
        ///////////////////////// Please implement code here /////////////////////////
        // unimplemented!();
        /// x | 1/x  | 1- x*1/x
        /// check1: x*iszeroexpr == 0
        /// check2: iszeroexpr == b
        meta.create_gate("is zero", |meta|{
            let x = meta.query_advice(advice[0], Rotation::cur());
            let x_1 = meta.query_advice(advice[1], Rotation::cur());
            let is_zero_expr = Expression::Constant(F::ONE) - (x.clone()*x_1.clone());
            let s_is_zero = meta.query_selector(s_is_zero);
            let b = meta.query_advice(advice[2], Rotation::cur());
            vec![
                (x.clone()*is_zero_expr.clone()) * s_is_zero.clone(),
                (b.clone() - is_zero_expr.clone()) * s_is_zero.clone()
            ]
        });
        ///////////////////////// End implement /////////////////////////
        FieldConfig { advice, s_is_zero }
    }
}

impl<F: Field> Chip<F> for FieldChip<F> {
    type Config = FieldConfig;
    type Loaded = ();

    fn config(&self) -> &Self::Config {
        &self.config
    }

    fn loaded(&self) -> &Self::Loaded {
        &()
    }
}

/// A variable representing a number.
#[derive(Clone)]
struct Number<F: Field>(AssignedCell<F, F>);

impl<F: Field> NumericInstructions<F> for FieldChip<F> {
    type Num = Number<F>;

    fn load_private(
        &self,
        mut layouter: impl Layouter<F>,
        values: &[Value<F>],
    ) -> Result<Vec<Self::Num>, Error> {
        let config = self.config();

        layouter.assign_region(
            || "load private",
            |mut region| {
                values
                    .iter()
                    .enumerate()
                    .map(|(i, value)| {
                        region
                            .assign_advice(|| "private input", config.advice[0], i, || *value)
                            .map(Number)
                    })
                    .collect()
            },
        )
    }

    fn is_zero(
        &self,
        mut layouter: impl Layouter<F>,
        a: &[Self::Num],
        b: &[Self::Num],
    ) -> Result<Vec<Self::Num>, Error> {
        // let config = self.config();
        assert_eq!(a.len(), b.len());

        layouter.assign_region(
            || "is_zero",
            |mut region: Region<'_, F>| {
                a.iter()
                    .zip(b.iter())
                    .enumerate()
                    .map(|(i, (a, b))| {
                        ///////////////////////// Please implement code here /////////////////////////
                        // unimplemented!();
                        self.config.s_is_zero.enable(&mut region, i)?;
                        a.0.copy_advice(||"copy a", &mut region, self.config.advice[0], i)?;
                        let value_inv = a.0.value().map(|value| value.invert().unwrap_or(F::ZERO));
                        region.assign_advice(||"assign inv", self.config.advice[1],i, ||value_inv)?;
                        b.0.copy_advice(||"copy b", &mut region, self.config.advice[2], i).map(Number)
                        ///////////////////////// End implement /////////////////////////
                    })
                    .collect()
            },
        )
    }
}

#[derive(Default)]
pub struct MyCircuit<F: Field> {
    pub a: Vec<Value<F>>,
    pub b: Vec<Value<F>>,
}

impl<F: Field> Circuit<F> for MyCircuit<F> {
    // Since we are using a single chip for everything, we can just reuse its config.
    type Config = FieldConfig;
    type FloorPlanner = SimpleFloorPlanner;

    fn without_witnesses(&self) -> Self {
        Self::default()
    }

    fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
        // We create the three advice columns that FieldChip uses for I/O.
        let advice = [
            meta.advice_column(),
            meta.advice_column(),
            meta.advice_column(),
        ];
        FieldChip::configure(meta, advice)
    }

    fn synthesize(
        &self,
        config: Self::Config,
        mut layouter: impl Layouter<F>,
    ) -> Result<(), Error> {
        let field_chip = FieldChip::<F>::construct(config);

        // Load our private values into the circuit.
        let a = field_chip.load_private(layouter.namespace(|| "load a"), &self.a)?;
        let b = field_chip.load_private(layouter.namespace(|| "load b"), &self.b)?;

        field_chip.is_zero(layouter.namespace(|| "is_zero"), &a, &b)?;

        Ok(())
    }
}

pub fn get_example_circuit<F: PrimeField>() -> MyCircuit<F> {
    let a = [F::from(0), F::from(2)];
    let b = [F::from(1), F::from(0)];

    // Instantiate the circuit with private inputs.
    MyCircuit {
        a: a.iter().map(|&x| Value::known(x)).collect(),
        b: b.iter().map(|&x| Value::known(x)).collect(),
    }
}

#[test]
fn is_zero_circuit_test() {
    use halo2_proofs::dev::MockProver;
    use halo2curves::pasta::Fp;

    let k = 4;

    // good case 0 : input == 0 and output ==1
    // good case 1 : (input == 2 and output == 0)
    let a = [Fp::from(0), Fp::from(2)];  // value
    let b = [Fp::from(1), Fp::from(0)];  // flag
    let circuit = MyCircuit {
        a: a.iter().map(|&x| Value::known(x)).collect(),
        b: b.iter().map(|&x| Value::known(x)).collect(),
    };
    let prover = MockProver::run(k, &circuit, vec![]).unwrap();
    assert_eq!(prover.verify(), Ok(()));
}

### Familiar Strangers 300pt

`6026017665971213533282357846279359759458261226685473132380160 % (1<<201) = 2812141577453232982198433661597034554413855239119887461777408`

`-401734511064747568885490523085290650630550748445698208825344 % (1<<201) = 2812141577453232982198433661597034554413855239119887461777408`

level1: 2812141577453232982198433661597034554413855239119887461777408

`3533700027045102098369050084895387317199177651876580346993442643999981568 % (1<<241) = 5897488333439202455083409550285544209858125342430750230241414742016`

`-3618502782768642773547390826438087570129142810943142283802299270005870559232 % (1<<251) = 5897488333439202455083409550285544209858125342430750230241414742016`

level2: 00005897488333439202455083409550285544209858125342430750230241414742016

### Mixer 300pt

Classic missing nullifier check -> double spend

Simply repeat the last transaction several times with different nullifiers that are equal in the finite field to drain the contract.

### What a Waste 400pt

Despite the fact that both the challenge name and the information given suggests that we are supposed to exploit a toxic waste leakage to forge a proof, after hours of attempts, none of us could find out how the random number provided could be utilized.

Instead, we used an unintended approach. After studying the vkey provided (mostly by looking at the coefs section), we realized that the original circuit actually had only one constraint, which was of a form similar to `(w2 * 5466109193624317948043479940313519306487052612053217191828155546078399544129) * (w1* 1863851486250177851956702286077330295839365094776194627624287948729995643802 + w2* 20024391385589097370289703459179944792708999305639839716073916237845812851815) - ??? == 0`

Since there is only one constraint, we guessed that the constraints of the circuit might not be strict, so we tried some special corner cases and found that the validation could be passed when $w_0=1,w_1=w_2\ (\text{or } w_2=0),w_3=0$.