1\section{Cryptographic Foundations of Bitcoin}2\label{sec:foundations}34Bitcoin's security rests on three computational assumptions that are structurally unrelated: the hardness of the5discrete-logarithm problem in the group of rational points of one specific elliptic curve, \secp{}; the preimage and6collision resistance of SHA-256 (used directly, doubled as SHA-256d in the proof of work, composed with RIPEMD-1607in legacy addresses, and in the tagged-hash form of BIP340/BIP341); and the unforgeability of two signature schemes,8ECDSA and BIP340 Schnorr, which reduce---under different assumptions and with very different proof structures---to9the first two. Figure~\ref{fig:depmap} summarises the dependency structure; the dashed box contains the three10hardness assumptions whose mathematical structure is the subject of this paper.1112\begin{figure}[htbp]13 \centering14 \input{figures/fig_dependency_map}15 \caption{Cryptographic dependency map of Bitcoin (illustrative diagram). Arrows point from a component to the16 components that depend on it. Research Axes~A--C of this paper concern the three dashed hardness assumptions; Axis~D17 concerns the method by which such assumptions can be probed automatically.}18 \label{fig:depmap}19\end{figure}2021Table~\ref{tab:primitives} lists the primitives, the assumption each rests on and the generic security level that22the assumption provides.2324\begin{table}[htbp]25 \centering\footnotesize26 \caption{Cryptographic primitives of Bitcoin, their hardness assumptions and generic security levels.}27 \label{tab:primitives}28 \resizebox{\textwidth}{!}{%29 \begin{tabular}{@{}llllp{4.2cm}@{}}30 \toprule31 Primitive & Mathematical object & Assumption & Generic cost & Used for \\32 \midrule33 \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 \\34 ECDSA & $(r,s)$ with $s=k^{-1}(z+rd)$ & ECDLP + conversion-function idealisation & as above & legacy and SegWit v0 spends \\35 BIP340 Schnorr & $(x(R),s)$ with $s=k+ed$ & ECDLP in ROM (forking lemma) & as above & Taproot (SegWit v1) spends, MuSig2 \\36 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 \\37 RIPEMD-160$\circ$SHA-256 & 160-bit hash of a 256-bit hash & preimage / collision resistance & $2^{160}$ / $2^{80}$ & legacy addresses (P2PKH, P2WPKH) \\38 Tagged hash & $\mathrm{SHA256}(\mathrm{SHA256}(t)\|\mathrm{SHA256}(t)\|m)$ & domain separation, ROM & as SHA-256 & BIP340 challenges and nonces, Taproot commitments \\39 \bottomrule40 \end{tabular}41 }42 \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.}4344\end{table}4546This section fixes notation and states the mathematical facts the rest of the paper builds on. We give proofs or47exact verification scripts for the facts that are specific to \secp{} (Section~\ref{sec:secp}); classical theorems are48cited to the standard references \citep{silverman2009arithmetic,washington2008elliptic,hankerson2004guide,galbraith2012mathematics}.4950\subsection{Finite-field arithmetic}5152Let $p$ be an odd prime and $\F_p = \Z/p\Z$. Addition, subtraction and multiplication are integer operations followed53by reduction modulo $p$; inversion uses the extended Euclidean algorithm or Fermat's identity $a^{-1}=a^{p-2}$. For the54\secp{} prime $p = 2^{256}-2^{32}-977$ the reduction can exploit the special form: writing a $512$-bit product as55$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 a56generalised-Mersenne reduction in the sense of \citet{solinas1999generalized}; it is a constant-factor implementation57advantage, not an algebraic weakness---the multiplicative group $\F_p^*$ has order $p-1 = 2\cdot 3\cdot 7\cdot 13441\cdot q$58with $q$ a large prime, and no structure of $\F_p$ enters any known attack on the curve. Square roots are needed to59decompress points: since $p\equiv 3 \pmod 4$, $\sqrt{a} = a^{(p+1)/4}$ whenever $a$ is a quadratic residue. All our60implementations use exact integer arithmetic (Python integers, PARI/GP, Rust \code{u128} products); floating point is61never used for a field operation.6263\subsection{Elliptic curves and the group law}6465An elliptic curve over $\F_p$ ($p>3$) in short Weierstrass form is66\begin{equation}67 E:\quad y^2 = x^3 + ax + b, \qquad a,b\in\F_p,\quad \Delta = -16(4a^3 + 27b^2)\ne 0 .68 \label{eq:weierstrass}69\end{equation}70The set $E(\F_p)$ of solutions $(x,y)\in\F_p^2$ together with a point at infinity $\Oinf$ forms an abelian group with71$\Oinf$ as identity and $-(x,y) = (x,-y)$. For $P=(x_1,y_1)$, $Q=(x_2,y_2)$ with $P\ne\pm Q$,72\begin{equation}73 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,74 \label{eq:add}75\end{equation}76and for doubling ($y_1\ne 0$) the same formulas apply with the tangent slope $\lambda = (3x_1^2+a)/(2y_1)$77(Figure~\ref{fig:ecgeom}). That~\eqref{eq:add} returns a point of $E$ is a polynomial identity modulo the two curve78equations; we verified it symbolically (check~S1 of \code{theory/elliptic\_curves/symbolic\_checks.py}, reduction of the79numerator of $y_3^2 - x_3^3 - ax_3 - b$ by a Gr\"obner basis of the ideal generated by the curve equations gives80zero). Associativity is the one group axiom that is not a one-line identity; the standard proofs go through the81Riemann--Roch theorem or an explicit, lengthy polynomial verification \citep[Ch.~2]{washington2008elliptic}.8283\begin{figure}[htbp]84 \centering85 \includegraphics[width=0.9\textwidth]{ec_geometry.pdf}86 \caption{Geometry of the group law (illustrative, over $\R$): the chord through $P$ and $Q$ meets the curve in a third87 point whose reflection is $P+Q$; the tangent at $P$ gives $2P$. Over $\F_p$ the same formulas~\eqref{eq:add} apply88 with no geometric picture. Generated by \code{scripts/fig\_ec\_geometry.py}.}89 \label{fig:ecgeom}90\end{figure}9192Projective or Jacobian coordinates avoid the field inversion in~\eqref{eq:add} \citep{cohen1998efficient}; our93reference code counts group operations in the affine model (one inversion per operation), while the Rust engine94amortises inversions across parallel walks with Montgomery's simultaneous-inversion trick \citep{montgomery1987speeding}.95Operation counts (additions, doublings, inversions, multiplications) are reported next to wall-clock time throughout.9697\subsection{Scalar multiplication}9899For $k\in\Z$ and $P\in E(\F_p)$, $[k]P = P + \cdots + P$ ($k$ terms). Left-to-right double-and-add costs100$\ell$ doublings and on average $\ell/2$ additions for an $\ell$-bit scalar; signed-window (wNAF) recoding with window101$w$ reduces the additions to about $\ell/(w+1)$ plus $2^{w-2}$ precomputed points \citep{hankerson2004guide}.102Double-scalar products $[u]P+[v]Q$, which dominate signature verification, are computed by Straus--Shamir103interleaving \citep{straus1964addition} and multi-scalar products $\sum_i [a_i]P_i$ by Pippenger's bucket method104\citep{pippenger1980evaluation}; see Section~\ref{sec:signatures}.105106\subsection{Group order, Hasse's theorem and subgroup structure}107108\begin{theorem}[Hasse]\label{thm:hasse}109$\lvert\,\#E(\F_p) - (p+1)\,\rvert \le 2\sqrt{p}$.110\end{theorem}111The integer $t = p+1-\#E(\F_p)$ is the trace of the Frobenius endomorphism $\pi:(x,y)\mapsto(x^p,y^p)$, which112satisfies $\pi^2 - t\pi + p = 0$ in $\End(E)$. Point counting is polynomial time by Schoof's algorithm and its113Elkies--Atkin improvements \citep{schoof1985elliptic,schoof1995counting}; we use PARI/GP's \code{ellcard} to generate114prime-order synthetic curves of 20--56 bits and to re-verify $\#\secp(\F_p)$. The group $E(\F_p)$ is either cyclic or a115product of two cyclic groups; when $\#E(\F_p)=n$ is prime, as for \secp{}, every non-identity point generates the whole116group and the cofactor is $h=1$.117118\subsection{Isomorphisms, twists and the $j$-invariant}119120Two 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 some121$u\in\F_p^*$; the $j$-invariant $j = 1728\cdot 4a^3/(4a^3+27b^2)$ classifies curves up to isomorphism over122$\overline{\F}_p$. Curves with $a=0$ have $j=0$ and admit, when $p\equiv 1\pmod 3$, six isomorphisms to themselves123(automorphisms) rather than the generic two. The quadratic twist $E'$ of $E$ has $\#E'(\F_p) = p+1+t$; its order124matters because an implementation that does not validate inputs may be driven onto the twist (``twist security'').125126\subsection{Endomorphisms and complex multiplication}127128$\End(E)$, the ring of rational maps $E\to E$ preserving $\Oinf$, always contains $\Z$ (scalar multiplications) and129$\pi$. For an ordinary curve ($t\not\equiv 0 \pmod p$), $\End(E)$ is an order in the imaginary quadratic field130$K=\Q(\sqrt{t^2-4p})$ containing $\Z[\pi]$. When $j=0$ and $p\equiv 1 \pmod 3$ the map131$\phi(x,y) = (\beta x, y)$ with $\beta^3=1$, $\beta\ne 1$, is an automorphism of order~3, $K = \Q(\sqrt{-3})$ and132$\End(E) = \Z[\omega]$, $\omega = (-1+\sqrt{-3})/2$, the Eisenstein integers---the maximal order of $K$, so no larger133endomorphism ring is possible. In particular $4p = t^2 + 3f^2$ for an integer $f$ (the conductor of $\Z[\pi]$ in134$\Z[\omega]$), and every endomorphism is $u + v\phi$ with $u,v\in\Z$, of degree $u^2 - uv + v^2$. This observation135is the starting point of Section~\ref{sec:secp}: the only efficiently computable endomorphisms beyond scalars are the136six automorphisms, and we show that the Gallant--Lambert--Vanstone constants of \secp{} are literally the137coordinates of $\bar\pi - 1$ in $\Z[\omega]$.138139\subsection{Scalar decomposition}140141If $\phi$ acts on the cyclic group $\langle G\rangle$ of prime order $n$ as $[\lambda]$ with $\lambda^2+\lambda+1\equiv 0142\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)$ by143reducing $(k,0)$ modulo the lattice $L = \{(u,v): u+v\lambda\equiv 0 \pmod n\}$ \citep{gallant2001faster}. Then144$[k]P = [k_1]P + [k_2]\phi(P)$ is a double-scalar product with half-length scalars, which halves the number of145doublings. The bound $\max(\lvert k_1\rvert,\lvert k_2\rvert) < c\sqrt n$ for an explicit $c$ is proved in146\citet{sica2002analysis}; we measure it exactly in Section~\ref{sec:results}.147148\subsection{The discrete-logarithm problem and generic-group complexity}149150\begin{definition}[ECDLP]151Given $G$ of prime order $n$ and $Q\in\langle G\rangle$, find $d\in[0,n)$ with $Q=[d]G$.152\end{definition}153154In the generic-group model \citep{shoup1997lower,nechaev1994complexity} an algorithm may only apply the group155operation to opaque encodings of elements; any such algorithm needs $\Omega(\sqrt n)$ operations to solve the DLP in a156group of prime order $n$ with constant probability. The matching upper bounds are Shanks' baby-step giant-step157\citep{shanks1971class} ($\approx 2\sqrt n$ operations, $\sqrt n$ memory) and Pollard's rho \citep{pollard1978monte}158($\approx\sqrt{\pi n/2}$ expected operations under the random-mapping heuristic, constant memory), parallelised with159linear speed-up by distinguished points \citep{vanoorschot1999parallel}. Section~\ref{sec:dlog} reviews these methods160and their refinements. The ``square-root barrier'' of our title is this generic bound: it can be beaten only by an161algorithm that uses the \emph{representation} of the group---an algebraic attack. Known algebraic attacks on elliptic162curves (transfer to $\F_{p^k}^*$ when the embedding degree $k$ is small, the anomalous-curve attack when $n=p$,163index calculus via Weil descent or summation polynomials over extension fields) each require a structural property164that \secp{} verifiably lacks (Section~\ref{sec:secp}). For prime fields with no small-degree subfield, no algorithm165with complexity below $\sqrt n$ is known \citep{galbraith2016recent}.166167\subsection{What ``beyond the square-root barrier'' can and cannot mean}168169Three kinds of improvement must be kept apart. (i)~\emph{Constant-factor} improvements reduce the constant in170$c\sqrt n$: the negation map ($c\to c/\sqrt2$), the order-6 automorphism group of $j=0$ curves ($c\to c/\sqrt6$), better171iteration functions, batched inversions. (ii)~\emph{Non-uniform} or preprocessing improvements trade a one-time172computation of size $T$ for a per-instance cost of $\sqrt{n/T}$, within the bound $ST^2=\tilde\Omega(n)$173\citep{corrigangibbs2018discrete}; the total work is never below $\sqrt n$. (iii)~\emph{Asymptotic} improvements, which174would break the generic bound, require a new algebraic idea and are the object of hypotheses~A1--A5. The paper175measures (i) and (ii) precisely on synthetic groups and gives negative results for the specific algebraic candidates176of~(iii) that we could formulate.177