\def\hs{\hspace{0.4 cm}}

\documentclass[aspectratio=169,usenames,dvipsnames]{beamer}

\usetheme{lined}
\usecolortheme{beaver}
\setbeamertemplate{footline}[default]
%\beamertemplatenavigationsymbolsempty

\newcommand{\ks}{{\color{blue}k}}
\newcommand{\xs}{{\color{blue}x}}
\setlength{\fboxsep}{1ex}

\title{\huge What \texttt{OP\_CANT} We Do With \texttt{OP\_CAT}}
\author{
~\\
\small
Andrew Poelstra\\
Director, Blockstream Research\\
March 12, 2024
}
\date{\includegraphics[scale=0.2]{blockstream-1.png}}

\begin{document}
\frame{ \maketitle }

\frame
{
    \frametitle{Contents}
    \begin{itemize}
    \item Covenants.\\~\\
    \item Everything else.
    \end{itemize}
}

\frame
{
    \frametitle{Covenants}

    Covenants, broadly, are about constraining the transaction context.\\~\\
    \begin{itemize}
    \item \texttt{CSV} and \texttt{CLTV} do this in a super limited way.\\~\\
    \item \texttt{CHECKSIG} et al appear to be even more limited.\\~\\
    \item \ldots but are they?
    \end{itemize}
}

\frame
{
    \frametitle{Covenants}

    (Tap)script is a language with 255 opcodes, in principle.\\~\\
    \begin{itemize}
    \item Roughly 90 just push stuff, 90 are insta-fail/insta-suceed.\\~\\
    \item Of the 80 or so ``real'' opcodes, exactly 5 access the transaction context:
    \begin{itemize}
    \item \texttt{CHECKSIG}, \texttt{CHECKSIGVERIFY}, \texttt{CHECKSIGADD}
    \item \texttt{CHECKSEQUENCEVERIFY}, \texttt{CHECKLOCKTIMEVERIFY}
    \item \texttt{CAT} would not.
    \end{itemize}
    \end{itemize}
}

\frame
{
    \frametitle{Covenants}

    In a Blockchain context, we don't \alert{compute} but \alert{verify}. There
    are not \alert{inputs} and \alert{outputs} but \alert{statments} and
    \alert{witnesses}.
}

\frame
{
    \frametitle{Covenants}

    So \texttt{CHECKSIGVERIFY} doesn't take a signature/message/pubkey and
    output pass/fail.~\\~\\
    Instead it makes a claim about the relationship between these three
    objects, and the objects themselves are the witness.\\~\\
    The claim is not just ``this key signed this message'' but something
    algebraically specific.~\\~\\
    And \texttt{OP\_CAT} lets us be more specific.
}

\frame
{
    \frametitle{Covenants}

    The Schnorr signing equation is $s = k + ex$, where $x$ is a secret key,
    $k$ is the ``secret nonce'' and $e$ is a hash of our transaction data.\\~\\
    \begin{itemize}
    \item Setting the pubkey to $G$ forces $x = 1$.\\~\\
    \item With \texttt{CAT} we can also force $k = 1$.\\~\\
    \item Then $s = e + 1$.~\\~\\
    \end{itemize}
    Using \texttt{CAT} again we can reconstruct $e$ using explicit transaction
    data, and compensate for that annoying +1.
}

\frame
{
    \frametitle{Everything Else}

    \texttt{CAT} can also be used to implement:

    \begin{itemize}
    \item Big-integer arithmetic from 4-byte arithmetic (\texttt{ADD} and \texttt{SUB} anyway).\\~\\
    \item Verifying PoW in Script.\\~\\
    \item Lexicographic comparisons of arbitrary-length strings; simulating \texttt{LEXCAT}.\\~\\
    \item One-time Schnorr signatures (which reveal secret keys).
    \end{itemize}
}

\frame
{
    \frametitle{Everything Else}

    It can be used to implement Lamport or Winternitz one-time signatures.\\~\\
    \begin{itemize}
    \item Lamport public keys consist of 256 pairs of hashes.\\~\\
    \item Signatures hash a message and reveal one preimage for each bit of the hash.\\~\\
    \item Can be done in Script with \texttt{CAT}. (Jeremy Rubin 2021)\\~\\
    \item \alert{Can sign transaction data \emph{or} arbitrary messages.}
    \end{itemize}
}

\frame
{
    \frametitle{Everything Else}

    Can be used to implement Merkle trees, which have some \alert{direct} applications:\\~\\
    \begin{itemize}
    \item Tree signatures (multisigs with millions or billions of keys).\\~\\
    \item Trees of verification conditions (using \texttt{SIZE} to distinguish keys, hashes, etc).\\~\\
    \item Compressing BitVM into fewer transactions.\\~\\
    \item c.f. \texttt{MERKLEBRANCHVERIFY} (BIP 116) (Friedenbach, Alm, BtcDrak 2017)
    \end{itemize}
}

\frame
{
    \frametitle{Everything Else}

    Can be used to implement Merkle trees, which have some \alert{indirect} applications:\\~\\
    \begin{itemize}
    \item Any function with a small enough domain can be precomputed as a Merkelized lookup
      table (e.g. 16-bit multiplication/division).\\~\\
    \item Can extend 16-bit math to bignum math by splitting large values.\\~\\
    \item Modular arithmetic? EC ops? ZK verifiers?\\~\\
    \item Cut-and choose protocols?
    \end{itemize}
}

\frame
{
    \frametitle{Thank you}

    Original blog post about CAT covenants\\
    \url{https://wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html}~\\~\\
    Implementation by rot13maxi\\
    \url{https://github.com/taproot-wizards/purrfect\_vault}~\\~\\
    I am Andrew Poelstra \texttt{catman@wpsoftware.net}
}

\end{document}