\begin{frame}
  \frametitle{Certificate Transparency (CT)}
  \begin{columns}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item Add transparency to CA ecosystem
        \item Publicly log all certificates
        \item No need\footnotemark{} to trust the log
          \begin{itemize}
            \item Membership proofs
            \item Append-only proofs
          \end{itemize}
      \end{itemize}
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=\textwidth]{img/ct}
      \burl{http://www.certificate-transparency.org/what-is-ct}
    \end{column}
  \end{columns}
  \footnotetext{As deployed right now we do trust the logs tho \Frowny}
\end{frame}

\begin{frame}
  \frametitle{Certificate logging in greater detail
    \titlefloatright{Merkle tree}}
  \centering
  \vfill
  \input{img/mt}
  \pause
  \vfill
  \begin{columns}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item Append new certificates in batches
      \end{itemize}
    \end{column}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item Sign tree head every hour \ding{224} STH
      \end{itemize}
    \end{column}
  \end{columns}
  \vfill
  %\vfill\centering\alert{Anyone can audit and monitor the log, but as deployed
  %  not much of this yet}
\end{frame}

\begin{frame}
  \frametitle{Generating a membership proof
    \titlefloatright{Audit path}}
  \centering
  \vfill
  \input{img/mtp}
  \vfill
  \begin{columns}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item Traverse tree from root to leaf
      \end{itemize}
    \end{column}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item Grab all sibling hashes on the way
      \end{itemize}
    \end{column}
  \end{columns}
  \vfill
\end{frame}

\begin{frame}
  \frametitle{Two approaches towards monitoring a CT log}
  \begin{columns}
    \begin{column}{0.49\textwidth}
      \centering
      \vbox to 0.8\textheight {
        \textbf{Self-monitoring}
        \vfill
        \input{img/self-monitor}
        \vfill
        \pause
        \begin{description}
          \item[\Frowny] Continuous uptime
          \item[\Frowny] Download everything
        \end{description}
        \pause
      }
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering
      \vbox to 0.8\textheight {
        \textbf{Monitoring-as-a-service}
        \vfill
        \input{img/tp-monitor}
        \pause
        \vfill
        \begin{description}
          \item[\Smiley] Ezpz
          \item[\Frowny] Trusted 3rd party
        \end{description}
      }
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Notion of what we would like to achieve
    \titlefloatright{`Wish list'}}
  \begin{columns}
    \begin{column}{0.59\textwidth}
      \begin{itemize}
        \item CT/bis backwards compatibility
        \item Piggy-back on gossip-audit model
        \item Self-monitor wildcards w/o full download
        \item Reduced 3rd party monitoring trust
      \end{itemize}
    \end{column}
    \begin{column}{0.39\textwidth}
      \centering
      \includegraphics[height=0.8\textheight]{img/wish}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{An overview of light-weight monitoring}
  \centering
  \input{img/overview}
  \vfill
  \begin{columns}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item A new Merkle tree for each batch
      \end{itemize}
    \end{column}
    \begin{column}{0.49\textwidth}
      \begin{itemize}
        \item Add snapshot to STH as extension
      \end{itemize}
    \end{column}
  \end{columns}
  \vfill\centering\alert{One wildcard (non-)membership notification per STH}\\
  \pause
  \alert{How do you know if you got all notifications \ding{224} index
    extension}
\end{frame}

\begin{frame}
  \frametitle{Wildcard notifications}
  \centering
  \input{img/wildcard}
  \begin{columns}
    \begin{column}{0.39\textwidth}
      \begin{itemize}
        \item Merkleize reverse-sorted list
      \end{itemize}
    \end{column}
    \begin{column}{0.59\textwidth}
      \begin{itemize}
        \item Wildcard proof \ding{224} at most two audit paths
      \end{itemize}
    \end{column}
  \end{columns}
  \pause
  \vfill\centering\alert{Security of this data structure? It is still just a
    Merkle tree...}
\end{frame}

\begin{frame}
  \frametitle{Performance evaluation \titlefloatright{Experimental setup}}
  \begin{columns}
    \begin{column}{0.49\textwidth} 
      \vbox to .6\textheight{
        \begin{itemize} 
          \item PoC: 351 lines of Go\footnotemark
          \item Interesting metrics
            \begin{itemize}
              \item Snapshot creation time
              \item Proof generation time
              \item Proof verification time
              \item Bandwidth overhead
            \end{itemize}
          \item Two log characteristics that matter
            \begin{itemize}
              \item STH frequency
              \item Batch size
            \end{itemize}
        \end{itemize}
        \vfill\centering\alert{We observed all Chrome-included logs for eight
          months to determine these characteristics}
      }
    \end{column}
    \begin{column}{0.49\textwidth}
      \vbox to 0.8\textheight{
        \centering
        \vfill
        \textbf{Google's Icarus Log}\\
        \vfill
        \includegraphics[width=\textwidth]{img/frequency}\\
        \vfill
        \includegraphics[width=\textwidth]{img/batch}
        \vfill
      }
    \end{column}
  \end{columns}
  \footnotetext{\burl{https://github.com/rgdd/lwm}}
\end{frame}

\begin{frame}
  \frametitle{Snapshot creation time}
  \centering
  \includegraphics[height=0.6\textheight]{img/snapshot}
  \vfill\centering\alert{Negligible in comparison to STH issuance rate (1h)}
\end{frame}

\begin{frame}
  \frametitle{Proof generation time}
  \centering
  \includegraphics[height=0.6\textheight]{img/proofgen}
  \vfill\centering\alert{At least 288M non-membership proofs per hour on a
    single core}
\end{frame}

\begin{frame}
  \frametitle{Proof generation and verification for *.com}
  \centering
  \includegraphics[height=0.6\textheight]{img/proofcom}
  \vfill\centering\alert{352k matches in max batch \ding{224} 29k proofs per
    hour on a single core}
\end{frame}

\begin{frame}
  \frametitle{Bandwidth overhead}
  \begin{columns}
    \begin{column}{0.69\textwidth}
      \begin{description}
        \item[Audit paths] max batch size \ding{224} 1 KB
        \item[Self-monitor] compare to median batch size of 32.6 MB
        \item[Notifier] 288M audit paths per hour \ding{224} 640 Mbps
      \end{description}
    \end{column}
    \begin{column}{0.39\textwidth}
      \centering\includegraphics[width=\textwidth]{img/perf}
      \burl{http://blog.coviam.com/wp-content/uploads/2016/07/Performance-Evaluation-Process-z.jpg}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Take away}
  \begin{columns}
    \begin{column}{0.79\textwidth}
      \begin{itemize}
      \item Unfortunate if CT monitoring relies on trusted parties
      \item Light-weight monitoring
        \begin{itemize}
          \item One verifiable wildcard notification per batch
          \item Untrusted notification component with push/pull model
          \item Untrusted log \ding{224} rely on one honest monitor
          \item Trusted log \ding{224} no need to also trust monitor
        \end{itemize}
      \end{itemize}
    \end{column}
    \begin{column}{0.19\textwidth}
      \centering\includegraphics[width=\textwidth]{img/takeaway}
    \end{column}
  \end{columns}
\end{frame}