Quantum Circuit Optimization for ECDSA

Setup

Getting the benchmark running

How I set up the ECDSA.fail challenge on a fresh Ubuntu laptop, from an empty terminal to a validated score, with the reasoning at each step. The three system problems near the end were the most instructive part, so they get the most detail.

Step 1

Inventory before installing

Before adding anything, I checked what the machine already had, so every later step would start from a known state instead of a guess. Git and my GitHub SSH key were already set up; Rust was not installed.

terminal

git --version
rustc --version
cargo --version
ssh -T git@github.com

Step 2

Install Rust with rustup, not apt

Two reasons. Ubuntu's packaged Rust is years old. More importantly, the challenge repo pins an exact compiler version in a rust-toolchain file, and only rustup respects that file: the first time you build, it automatically downloads that exact version, so everyone in the competition builds with the same compiler.

One habit worth keeping: I downloaded the installer script to a file and read it before running it, instead of piping curl straight into a shell.

terminal

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs -o rustup-init.sh
less rustup-init.sh   # read it first
sh rustup-init.sh

Step 3

Create an empty GitHub repo, and no license

I created a new public repository with nothing in it: no README, no .gitignore, and, the part that actually matters, no license template. The challenge code is other people's work: parts are under CC BY 4.0 and attributed in a NOTICE file, and the rest belongs to the maintainers. A license is a grant of permission, and you can only grant permission for work you own. So I added no license file and kept their NOTICE intact.

Step 4

Clone the challenge and rewire the remotes

I cloned the official challenge repo, renamed its remote to upstream, and added my own repo as origin. That way my work pushes to my repository, and the community's future improvements can still be pulled from theirs.

terminal

git clone https://github.com/ecdsafail/ecdsafail-challenge.git
cd ecdsafail-challenge
git remote rename origin upstream
git remote add origin git@github.com:austinamissah/ecdsa-circuit-optimization.git

Step 5

Push, and a small lesson in force-pushing

My first push did not go through, because GitHub had auto-created an initial commit from a checkbox I missed. Before forcing anything, I verified the remote held only that stub commit, then used --force-with-lease, the safer force-push that refuses to overwrite anything you have not seen. The rule I follow: never force-push a branch other people build on. This was my own one-day-old solo repo, so it was safe.

terminal

git fetch origin
git log origin/main --oneline   # only GitHub's stub commit
git push --force-with-lease -u origin main

Step 6

Read before running

Before executing anything, I read the NOTICE file (who owns what), the rust-toolchain file (the pinned compiler, 1.93.0), and the whole benchmark.sh script. That last one matters: the script runs contestant code, which comes from unknown contributors, inside a bubblewrap sandbox with a read-only filesystem, no network, an unprivileged user, and one throwaway writable folder. The repo openly accepts code from many people, so the sandbox is not optional paranoia; it is the designed safety model.

Step 7

Build first, run second

Compiling everything without executing any contestant code keeps build errors and runtime problems separate, so when something fails you know which kind of failure you are looking at. The build finished with 25 warnings, all dead-code, all normal for a shared research codebase.

terminal

cargo build --release

Step 8

Three real system obstacles

The run then failed three times, each for a different reason. I diagnosed each one from the actual error message before changing anything.

a. The sandbox could not start

error

bwrap: loopback: Failed RTM_NEWADDR: Operation not permitted

Recent Ubuntu releases restrict unprivileged sandboxes, so the script's preferred path is to launch bubblewrap through sudo, which then drops the contestant code to an unprivileged user anyway. The fix is just to authorize sudo before running:

fix

sudo -v && ./benchmark.sh ...

b. Sudo forgot my password immediately

error

sudo: a password is required

This appeared from inside the script even though I had just typed my password. Ubuntu caches sudo credentials per terminal (a setting called tty_tickets), and the script launches the sandbox in a detached session with no terminal, where the cached ticket does not apply and sudo cannot ask again. The fix is a one-line sudoers drop-in, written the safe way: through sudo tee, permissions locked down, then validated with visudo before trusting it.

fix

echo 'Defaults !tty_tickets' | sudo tee /etc/sudoers.d/notty
sudo chmod 0440 /etc/sudoers.d/notty
sudo visudo -c   # validate before trusting it

The tradeoff: my password still expires after about 15 minutes, but within that window any of my processes can use sudo. On a single-user laptop I find that acceptable.

c. The sandbox could not reach the code

error

bwrap: execvp .../build_circuit: Permission denied

The sandbox runs contestant code as the user “nobody”, and modern Ubuntu creates home directories as mode 750, so other users cannot even pass through /home/<me> to reach the binary. I verified that with namei, then granted traverse-only access: others can pass through my home directory but still cannot list or read anything in it.

fix

namei -l target/release/build_circuit   # confirm where traversal fails
chmod o+x "$HOME"                       # traverse only, no list, no read

Step 9

Run the benchmark

With the three obstacles cleared, the harness ran end to end. It validated all 9,024 test points, confirmed every ancilla qubit returned to zero with no phase leakage, and scored the current community circuit at 1,320,763 average Toffoli gates × 1,152 qubits, about 1.52 × 10⁹, on my machine. That score is the community's accumulated optimization work, which I reproduced and validated; the profiling and analysis that followed are my own contribution.

terminal

./benchmark.sh --note "first local run, unmodified clone"

Step 10

Commit the evidence

The harness appends one row to results.tsv per run. I reviewed the diff, committed it under my own name, and pushed. The house rule: uncommitted work is invisible, so every session ends with a clean git status.

terminal

git diff results.tsv
git add results.tsv
git commit -m "First local benchmark run: baseline reproduced and validated"
git push

Where this leads

The environment is now boring, which is the goal: build, run, score, commit, repeat. The next work is profiling where the Toffoli gates are spent, and that is where the project notes on the main page pick up.

Keep going

Back to the project