\section{Cryptographic Foundations of Bitcoin}
\label{sec:foundations}

Bitcoin's security rests on three computational assumptions that are structurally unrelated: the hardness of the
discrete-logarithm problem in the group of rational points of one specific elliptic curve, \secp{}; the preimage and
collision resistance of SHA-256 (used directly, doubled as SHA-256d in the proof of work, composed with RIPEMD-160
in legacy addresses, and in the tagged-hash form of BIP340/BIP341); and the unforgeability of two signature schemes,
ECDSA and BIP340 Schnorr, which reduce---under different assumptions and with very different proof structures---to
the first two. Figure~\ref{fig:depmap} summarises the dependency structure; the dashed box contains the three
hardness assumptions whose mathematical structure is the subject of this paper.

\begin{figure}[htbp]
  \centering
  \input{figures/fig_dependency_map}
  \caption{Cryptographic dependency map of Bitcoin (illustrative diagram). Arrows point from a component to the
  components that depend on it. Research Axes~A--C of this paper concern the three dashed hardness assumptions; Axis~D
  concerns the method by which such assumptions can be probed automatically.}
  \label{fig:depmap}
\end{figure}

Table~\ref{tab:primitives} lists the primitives, the assumption each rests on and the generic security level that
the assumption provides.

\begin{table}[htbp]
  \centering\footnotesize
      \caption{Cryptographic primitives of Bitcoin, their hardness assumptions and generic security levels.}
    \label{tab:primitives}
  \resizebox{\textwidth}{!}{%
    \begin{tabular}{@{}llllp{4.2cm}@{}}
      \toprule
      Primitive & Mathematical object & Assumption & Generic cost & Used for \\
      \midrule
      \secp{} group & $E(\F_p)$, $y^2=x^3+7$, $\#E=n$ prime & ECDLP & $\sqrt{\pi n/12}\approx 2^{127.0}$ (rho + automorphisms) & key pairs, all signatures \\
      ECDSA & $(r,s)$ with $s=k^{-1}(z+rd)$ & ECDLP + conversion-function idealisation & as above & legacy and SegWit v0 spends \\
      BIP340 Schnorr & $(x(R),s)$ with $s=k+ed$ & ECDLP in ROM (forking lemma) & as above & Taproot (SegWit v1) spends, MuSig2 \\
      SHA-256 & 64-step Davies--Meyer compression, Merkle--Damg\aa rd & preimage / collision resistance & $2^{256}$ / $2^{128}$ & transaction and block hashes (doubled), Merkle trees, tagged hashes, HMAC, PoW \\
      RIPEMD-160$\circ$SHA-256 & 160-bit hash of a 256-bit hash & preimage / collision resistance & $2^{160}$ / $2^{80}$ & legacy addresses (P2PKH, P2WPKH) \\
      Tagged hash & $\mathrm{SHA256}(\mathrm{SHA256}(t)\|\mathrm{SHA256}(t)\|m)$ & domain separation, ROM & as SHA-256 & BIP340 challenges and nonces, Taproot commitments \\
      \bottomrule
    \end{tabular}
  }
  \par\smallskip{\footnotesize Generic costs are the best known attacks on an ideal instance of each size; Sections~\ref{sec:secp}--\ref{sec:sha} verify that \secp{} and SHA-256 are not known to deviate from them.}

\end{table}

This section fixes notation and states the mathematical facts the rest of the paper builds on. We give proofs or
exact verification scripts for the facts that are specific to \secp{} (Section~\ref{sec:secp}); classical theorems are
cited to the standard references \citep{silverman2009arithmetic,washington2008elliptic,hankerson2004guide,galbraith2012mathematics}.

\subsection{Finite-field arithmetic}

Let $p$ be an odd prime and $\F_p = \Z/p\Z$. Addition, subtraction and multiplication are integer operations followed
by reduction modulo $p$; inversion uses the extended Euclidean algorithm or Fermat's identity $a^{-1}=a^{p-2}$. For the
\secp{} prime $p = 2^{256}-2^{32}-977$ the reduction can exploit the special form: writing a $512$-bit product as
$c = c_1 2^{256} + c_0$ gives $c \equiv c_0 + c_1(2^{32}+977) \pmod p$, and two such folds reduce to $[0,2p)$. This is a
generalised-Mersenne reduction in the sense of \citet{solinas1999generalized}; it is a constant-factor implementation
advantage, not an algebraic weakness---the multiplicative group $\F_p^*$ has order $p-1 = 2\cdot 3\cdot 7\cdot 13441\cdot q$
with $q$ a large prime, and no structure of $\F_p$ enters any known attack on the curve. Square roots are needed to
decompress points: since $p\equiv 3 \pmod 4$, $\sqrt{a} = a^{(p+1)/4}$ whenever $a$ is a quadratic residue. All our
implementations use exact integer arithmetic (Python integers, PARI/GP, Rust \code{u128} products); floating point is
never used for a field operation.

\subsection{Elliptic curves and the group law}

An elliptic curve over $\F_p$ ($p>3$) in short Weierstrass form is
\begin{equation}
  E:\quad y^2 = x^3 + ax + b, \qquad a,b\in\F_p,\quad \Delta = -16(4a^3 + 27b^2)\ne 0 .
  \label{eq:weierstrass}
\end{equation}
The set $E(\F_p)$ of solutions $(x,y)\in\F_p^2$ together with a point at infinity $\Oinf$ forms an abelian group with
$\Oinf$ as identity and $-(x,y) = (x,-y)$. For $P=(x_1,y_1)$, $Q=(x_2,y_2)$ with $P\ne\pm Q$,
\begin{equation}
  P+Q = (x_3,y_3),\qquad \lambda = \frac{y_2-y_1}{x_2-x_1},\quad x_3 = \lambda^2 - x_1 - x_2,\quad y_3 = \lambda(x_1-x_3)-y_1,
  \label{eq:add}
\end{equation}
and for doubling ($y_1\ne 0$) the same formulas apply with the tangent slope $\lambda = (3x_1^2+a)/(2y_1)$
(Figure~\ref{fig:ecgeom}). That~\eqref{eq:add} returns a point of $E$ is a polynomial identity modulo the two curve
equations; we verified it symbolically (check~S1 of \code{theory/elliptic\_curves/symbolic\_checks.py}, reduction of the
numerator of $y_3^2 - x_3^3 - ax_3 - b$ by a Gr\"obner basis of the ideal generated by the curve equations gives
zero). Associativity is the one group axiom that is not a one-line identity; the standard proofs go through the
Riemann--Roch theorem or an explicit, lengthy polynomial verification \citep[Ch.~2]{washington2008elliptic}.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.9\textwidth]{ec_geometry.pdf}
  \caption{Geometry of the group law (illustrative, over $\R$): the chord through $P$ and $Q$ meets the curve in a third
  point whose reflection is $P+Q$; the tangent at $P$ gives $2P$. Over $\F_p$ the same formulas~\eqref{eq:add} apply
  with no geometric picture. Generated by \code{scripts/fig\_ec\_geometry.py}.}
  \label{fig:ecgeom}
\end{figure}

Projective or Jacobian coordinates avoid the field inversion in~\eqref{eq:add} \citep{cohen1998efficient}; our
reference code counts group operations in the affine model (one inversion per operation), while the Rust engine
amortises inversions across parallel walks with Montgomery's simultaneous-inversion trick \citep{montgomery1987speeding}.
Operation counts (additions, doublings, inversions, multiplications) are reported next to wall-clock time throughout.

\subsection{Scalar multiplication}

For $k\in\Z$ and $P\in E(\F_p)$, $[k]P = P + \cdots + P$ ($k$ terms). Left-to-right double-and-add costs
$\ell$ doublings and on average $\ell/2$ additions for an $\ell$-bit scalar; signed-window (wNAF) recoding with window
$w$ reduces the additions to about $\ell/(w+1)$ plus $2^{w-2}$ precomputed points \citep{hankerson2004guide}.
Double-scalar products $[u]P+[v]Q$, which dominate signature verification, are computed by Straus--Shamir
interleaving \citep{straus1964addition} and multi-scalar products $\sum_i [a_i]P_i$ by Pippenger's bucket method
\citep{pippenger1980evaluation}; see Section~\ref{sec:signatures}.

\subsection{Group order, Hasse's theorem and subgroup structure}

\begin{theorem}[Hasse]\label{thm:hasse}
$\lvert\,\#E(\F_p) - (p+1)\,\rvert \le 2\sqrt{p}$.
\end{theorem}
The integer $t = p+1-\#E(\F_p)$ is the trace of the Frobenius endomorphism $\pi:(x,y)\mapsto(x^p,y^p)$, which
satisfies $\pi^2 - t\pi + p = 0$ in $\End(E)$. Point counting is polynomial time by Schoof's algorithm and its
Elkies--Atkin improvements \citep{schoof1985elliptic,schoof1995counting}; we use PARI/GP's \code{ellcard} to generate
prime-order synthetic curves of 20--56 bits and to re-verify $\#\secp(\F_p)$. The group $E(\F_p)$ is either cyclic or a
product of two cyclic groups; when $\#E(\F_p)=n$ is prime, as for \secp{}, every non-identity point generates the whole
group and the cofactor is $h=1$.

\subsection{Isomorphisms, twists and the $j$-invariant}

Two curves $y^2=x^3+ax+b$ and $y^2=x^3+a'x+b'$ are isomorphic over $\F_p$ iff $a'=u^4a$, $b'=u^6b$ for some
$u\in\F_p^*$; the $j$-invariant $j = 1728\cdot 4a^3/(4a^3+27b^2)$ classifies curves up to isomorphism over
$\overline{\F}_p$. Curves with $a=0$ have $j=0$ and admit, when $p\equiv 1\pmod 3$, six isomorphisms to themselves
(automorphisms) rather than the generic two. The quadratic twist $E'$ of $E$ has $\#E'(\F_p) = p+1+t$; its order
matters because an implementation that does not validate inputs may be driven onto the twist (``twist security'').

\subsection{Endomorphisms and complex multiplication}

$\End(E)$, the ring of rational maps $E\to E$ preserving $\Oinf$, always contains $\Z$ (scalar multiplications) and
$\pi$. For an ordinary curve ($t\not\equiv 0 \pmod p$), $\End(E)$ is an order in the imaginary quadratic field
$K=\Q(\sqrt{t^2-4p})$ containing $\Z[\pi]$. When $j=0$ and $p\equiv 1 \pmod 3$ the map
$\phi(x,y) = (\beta x, y)$ with $\beta^3=1$, $\beta\ne 1$, is an automorphism of order~3, $K = \Q(\sqrt{-3})$ and
$\End(E) = \Z[\omega]$, $\omega = (-1+\sqrt{-3})/2$, the Eisenstein integers---the maximal order of $K$, so no larger
endomorphism ring is possible. In particular $4p = t^2 + 3f^2$ for an integer $f$ (the conductor of $\Z[\pi]$ in
$\Z[\omega]$), and every endomorphism is $u + v\phi$ with $u,v\in\Z$, of degree $u^2 - uv + v^2$. This observation
is the starting point of Section~\ref{sec:secp}: the only efficiently computable endomorphisms beyond scalars are the
six automorphisms, and we show that the Gallant--Lambert--Vanstone constants of \secp{} are literally the
coordinates of $\bar\pi - 1$ in $\Z[\omega]$.

\subsection{Scalar decomposition}

If $\phi$ acts on the cyclic group $\langle G\rangle$ of prime order $n$ as $[\lambda]$ with $\lambda^2+\lambda+1\equiv 0
\pmod n$, any scalar can be written $k \equiv k_1 + k_2\lambda \pmod n$ with $\lvert k_1\rvert,\lvert k_2\rvert = O(\sqrt n)$ by
reducing $(k,0)$ modulo the lattice $L = \{(u,v): u+v\lambda\equiv 0 \pmod n\}$ \citep{gallant2001faster}. Then
$[k]P = [k_1]P + [k_2]\phi(P)$ is a double-scalar product with half-length scalars, which halves the number of
doublings. The bound $\max(\lvert k_1\rvert,\lvert k_2\rvert) < c\sqrt n$ for an explicit $c$ is proved in
\citet{sica2002analysis}; we measure it exactly in Section~\ref{sec:results}.

\subsection{The discrete-logarithm problem and generic-group complexity}

\begin{definition}[ECDLP]
Given $G$ of prime order $n$ and $Q\in\langle G\rangle$, find $d\in[0,n)$ with $Q=[d]G$.
\end{definition}

In the generic-group model \citep{shoup1997lower,nechaev1994complexity} an algorithm may only apply the group
operation to opaque encodings of elements; any such algorithm needs $\Omega(\sqrt n)$ operations to solve the DLP in a
group of prime order $n$ with constant probability. The matching upper bounds are Shanks' baby-step giant-step
\citep{shanks1971class} ($\approx 2\sqrt n$ operations, $\sqrt n$ memory) and Pollard's rho \citep{pollard1978monte}
($\approx\sqrt{\pi n/2}$ expected operations under the random-mapping heuristic, constant memory), parallelised with
linear speed-up by distinguished points \citep{vanoorschot1999parallel}. Section~\ref{sec:dlog} reviews these methods
and their refinements. The ``square-root barrier'' of our title is this generic bound: it can be beaten only by an
algorithm that uses the \emph{representation} of the group---an algebraic attack. Known algebraic attacks on elliptic
curves (transfer to $\F_{p^k}^*$ when the embedding degree $k$ is small, the anomalous-curve attack when $n=p$,
index calculus via Weil descent or summation polynomials over extension fields) each require a structural property
that \secp{} verifiably lacks (Section~\ref{sec:secp}). For prime fields with no small-degree subfield, no algorithm
with complexity below $\sqrt n$ is known \citep{galbraith2016recent}.

\subsection{What ``beyond the square-root barrier'' can and cannot mean}

Three kinds of improvement must be kept apart. (i)~\emph{Constant-factor} improvements reduce the constant in
$c\sqrt n$: the negation map ($c\to c/\sqrt2$), the order-6 automorphism group of $j=0$ curves ($c\to c/\sqrt6$), better
iteration functions, batched inversions. (ii)~\emph{Non-uniform} or preprocessing improvements trade a one-time
computation of size $T$ for a per-instance cost of $\sqrt{n/T}$, within the bound $ST^2=\tilde\Omega(n)$
\citep{corrigangibbs2018discrete}; the total work is never below $\sqrt n$. (iii)~\emph{Asymptotic} improvements, which
would break the generic bound, require a new algebraic idea and are the object of hypotheses~A1--A5. The paper
measures (i) and (ii) precisely on synthetic groups and gives negative results for the specific algebraic candidates
of~(iii) that we could formulate.