%%% 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}