%%% Document Class

\documentclass[11pt]{letter}
\usepackage[margin=1in]{geometry}


%%% Packages

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{hyperref}


%%% Variables

\newcommand{\courseName}{Math 480A2}
\newcommand{\hwNumber}{11}
\newcommand{\hwDueDate}{November 10, 2022}


%%% Definitions

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\iff}{\leftrightarrow}

\renewcommand{\vec}[1]{\mathbf{#1}}

\DeclareMathOperator{\Prob}{Pr}               % probability
\newcommand{\Exp}{\mathbb{E}}                 % expected value
\newcommand{\C}{{\rm c}}                      % complement
\newcommand{\card}[1]{\left|#1\right|}        % cardinality
\newcommand{\Pv}{\mathcal{P}}                 % prover
\newcommand{\Vf}{\mathcal{V}}                 % verifier

\DeclareMathOperator{\AND}{AND}
\DeclareMathOperator{\OR}{OR}

\renewcommand{\theenumi}{\Alph{enumi}}
\newcounter{saveenum}

%%% Document

\begin{document}

\begin{center}
	{\large \courseName, Homework \hwNumber}\\
	Due \hwDueDate\\
\end{center}

{\small \textit{Homework is graded out of a total of 10 points.  Collaboration is permitted, but you must list all coauthors on a problem's solution at the top of the page, and your writing must be your own.}}

\vspace{5mm}

\textbf{Problem 1.} (4 points) Suppose that $G$ is a graph with $n = 2^{15}$ vertices and $m = 2^{20}$ edges.  Recall that the interactive proof protocol for graph 3-colorability of the graph $G$ has soundness error $\delta_S$ at most $1 - 1/m$, meaning that running the protocol will detect a cheating prover with probability at least $1/m$.  How many independent repetitions of the protocol are necessary in order to detect a cheating prover at least 99\% of the time?  How many individual commitments will the prover send to the verifier during this many repetitions?  How many of these commitments will be opened?

\vspace{3mm}

\textbf{Problem 2.} (4 points) Construct the Merkle tree associated with the vector of messages \[(m_1, m_2, m_3, m_4) = (0, 3, 1, 2)\] using the SHA256 cryptographic hash function.  When writing down your solution, you may abbreviate the hashes to their first 4 hexadecimal characters (representing the first 16 bits of the output in base-16), but make sure to use the complete hashes when computing successive layers of the tree.

To compute the SHA256 hash evaluations, you may use the following website: \url{https://emn178.github.io/online-tools/sha256.html}.  Make sure to select ``Input type: Hex'' from the drop-down menu so that your values aren't interpreted as ``bytes associated with ASCII characters''.  If the settings are correct, then \texttt{SHA256(0)} should evaluate to ``\texttt{6e34...}'', not ``\texttt{5fec...}''.

\vspace{3mm}

\textbf{Problem 3.} (2 points) In the Merkle tree constructed in Problem 2, what is the Merkle path associated with the message $m_2$?  How can you compute the Merkle root using only the values in this Merkle path?

\end{document}