
\section{Security proofs}\label{sec:missing_proofs}


\section{Proof of \texorpdfstring{\Cref{thm:arcula_euf}}{Theorem 5.1}}\label{subsec:proof_arcula}
\input{arcula_proof.tex}


\section{Security Model of Hierarchical Deterministic Wallet}\label{sec:security_model_of_hierarchical_deterministic_wallet}
One of the contributions of this work is to formalize, for the first time, the security model of hierarchical deterministic wallets (HDW).
We define a hierarchical deterministic wallet over $5$ algorithms \ensuremath{(\Set, \DerivePub, \DerivePriv, \allowbreak \Sign, \Verify)}{}, where:
\begin{inlinelist}
\item $\pcalgostyle{Set}{}$ deterministically instantiates the wallet by generating the public parameters \pp{} and a set of the derivation key \ensuremath{\derkey_i}{}, one for each node $\ensuremath{\cv{i}}\in\ensuremath{V}$ of the hierarchy.
\item $\pcalgostyle{DPriv}{}$ and $\pcalgostyle{DPub}$ are responsible of the derivation of signing and public keys (\Cref{prp:determinism,prp:public_keys}).
  $\pcalgostyle{DPriv}{}$ derives the signing key \ensuremath{\sk_{j}}{} of a node \ensuremath{\cv{j}}{}, descendent of \ensuremath{\cv{i}}{}, by using the derivation key \ensuremath{\derkey_i}{} associated to \ensuremath{\cv{i}}{};
  $\pcalgostyle{DPub}{}$ derives the corresponding public key \ensuremath{\pk_{j}}{} by using the only the public parameters \pp{}.
\item $\pcalgostyle{Sign}$ and $\pcalgostyle{Vrfy}$ take inspiration from the standard signing and verification algorithms of a digital signature scheme.
\end{inlinelist}

Concretely, let \ensuremath{\cG = (\cV, \cE)}{} be a directed acyclic graph (DAG) representing an access hierarchy.
We define the set of descendants \ensuremath{\desc(\cvi)} = \set{\cvj{} \mid \cvi{} \leadsto_w \cvj{}}{} of node \ensuremath{\cv{j}}{} to be the set of nodes \ensuremath{\cv{j}}{} such that there exists a direct path $w$ from \ensuremath{\cv{i}}{} to \ensuremath{\cv{j}}{} in \ensuremath{G}{}.
A hierarchical deterministic wallet $\Pi=\ensuremath{(\Set, \DerivePub, \DerivePriv, \allowbreak \Sign, \Verify)}{}$, defined over a seed space \ensuremath{\mathcal{S}}{} and message space \ensuremath{\mathcal{M}}{} is defined in the following way:
\begin{description}
  \item[\ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}{}:] The deterministic setup algorithm takes as input a security parameter, an access graph \ensuremath{\cG = (\cV, \cE)}{}, and an initial seed $\ensuremath{\cS{}} \in \ensuremath{\mathcal{S}}{}$, and outputs the public parameters \pp{} and a set of derivation keys $\{\ensuremath{\derkey_i}{}\}_{\ensuremath{\cv{i}} \in \ensuremath{V}}$.
  \item[\ensuremath{\DerivePub(\pp{}, \cvi{})}{}:] The deterministic public derivation algorithm takes as input the public parameters \pp{}, a target node \ensuremath{\cv{i}}{}, and outputs the public key \ensuremath{\pk_{i}}{} associated to node \ensuremath{\cv{i}}{}.
  \item[\ensuremath{\DerivePriv(\pp{}, \allowbreak\ensuremath{\derkey_i}{}, \cvi{}, \cvj{})}{}:] The deterministic private derivation algorithm takes as input the public parameters \pp{}, the derivation key \ensuremath{\derkey_i}{} of node \ensuremath{\cv{i}}{}, and a target node $\ensuremath{\cv{j}}{} \in \desc(\cvi)$, and outputs the secret key \ensuremath{\sk_{j}}{} associated to node \ensuremath{\cv{j}}{}.
  \item[\ensuremath{\Sign{(\sski, m)}}{}:] The randomized signing algorithm takes as input a message $m \in \ensuremath{\mathcal{M}}$, and a secret key \ensuremath{\sk_{i}}{}, and outputs a signature $\sigma$.
  \item[\ensuremath{\Verify{(\ppki, m, \sigma)}}{}:] The deterministic verification algorithm takes as input a public key \ensuremath{\pk_{i}}{}, a message $m$, and a signature $\sigma$, and outputs a decisional bit $b$.
\end{description}

A hierarchical deterministic wallet is correct if any user can derive the private and public key of its descendants and create a valid signature on behalf of them.
This means that any node \ensuremath{\cv{i}}{} can derive the signing key \ensuremath{\sk_{j}}{} of any node $\ensuremath{\cv{j}}{} \in \ensuremath{Desc}{}(\ensuremath{\cv{i}})$ and produce, in turn, a valid signature $\sigma$ on behalf of \ensuremath{\cv{j}}{} (\emph{i.e.}, that passes the verification process against the public key \ensuremath{\pk_{j}}{} obtained through public key derivation).
\begin{definition}[Correctness of HDW]\label{def:HDW-corr}
A hierarchical deterministic wallet $\Pi = \ensuremath{(\Set, \DerivePub, \DerivePriv, \allowbreak \Sign, \Verify)}{}$, with seed space \ensuremath{\mathcal{S}}{} and message space \ensuremath{\mathcal{M}}{}, is correct if for every DAG $\ensuremath{G} = (\ensuremath{V}, \ensuremath{E})$, $\forall \ensuremath{\cv{i}},\ensuremath{\cv{j}} \in V, \, \forall \ensuremath{\cv{j}} \in \ensuremath{Desc}{}(\ensuremath{\cv{i}}), \forall \ensuremath{\cS{}} \in \ensuremath{\mathcal{S}}, \forall m \in \ensuremath{\mathcal{M}}$ the following conditions holds:
\begin{equation*}
  \prob{\ensuremath{\Verify{(\ppkj, m, \Sign(\sskj, m))}}{}= 1} \geq 1 - \negl{},
\end{equation*}
where $\ensuremath{(\pp{}, \{\ensuremath{\derkey_i}\}_{\ensuremath{\cv{i}}\in\ensuremath{V}})} = \ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}$, $\ensuremath{\sk_{j}} = \ensuremath{\DerivePriv(\pp{}, \allowbreak\ensuremath{\derkey_i}{}, \cvi{}, \cvj{})}$, and $\ensuremath{\pk_{j}} = \pcalgostyle{DPub}(\pp{},\allowbreak \ensuremath{\cv{j}}{})$.
\end{definition}

The security of a hierarchical deterministic wallet draws inspiration from existentially unforgeable signatures.
We allow an attacker to corrupt an arbitrary number of users in the hierarchy---by corrupting a user; the attacker implicitly corrupts also all her descendants.
In addition, the attacker also has access to a signing oracle, that returns signatures on arbitrary messages from any uncorrupted node.
We challenge the attacker to forge a signature for a new message on behalf of an uncorrupted node.
\begin{definition}[Hierarchical existential unforgeability of HDW]\label{def:HDH-euf}
  A hierarchical deterministic wallet is hierarchically existentially unforgeable under chosen-message attacks if for every DAG $\ensuremath{G}=(\ensuremath{V}, \ensuremath{E})$ and PPT adversary \pcalgostyle{A}{} the following condition holds:
  \begin{equation*}
   \prob{\ensuremath{\Game{}_{\Pi, \pcalgostyle{A}}^{\mathsf{heuf}}(\secpar, \ensuremath{G}{}}) = 1} \leq \negl,
  \end{equation*}
  where experiment \ensuremath{\Game{}_{\Pi, \pcalgostyle{A}}^{\mathsf{heuf}}(\secpar, \ensuremath{G}{}}){} is defined in the following way:
  \begin{description}
    \item[Setup:] The challenger samples a random $\ensuremath{\cS{}} \sample \ensuremath{\mathcal{S}}$ and executes $\ensuremath{(\pp{}, \{\ensuremath{\derkey_i}\}_{\ensuremath{\cv{i}}\in\ensuremath{V}})} = \ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}$.
    It gives the public parameters \pp{} to \pcalgostyle{A}{}.
    \item[Query:] The adversary \pcalgostyle{A}{} has access to the following oracles:
      \begin{description}
        \item[$\ensuremath{\ensuremath{\pcalgostyle{O}}_{\ensuremath{\mathsf{Corr}}}}(\cdot)$:] On input $\ensuremath{\cv{i}}{} \in \ensuremath{V}$, the challenger answers by giving \ensuremath{\derkey_i}{} to \pcalgostyle{A}{}.
          Let $\ensuremath{\mathcal{Q}}_{\ensuremath{\mathsf{Corr}}}$ denote the set of nodes \ensuremath{\cv{i}}{} that \pcalgostyle{A}{} corrupted, including their descendants \desc(\cvi){}.
        \item[$\ensuremath{\ensuremath{\pcalgostyle{O}}_{\Sign}}(\cdot, \cdot)$:] On input $(m, \ensuremath{\cv{i}}{}) \in \ensuremath{\mathcal{M}} \times \ensuremath{V}$, the challenger returns \ensuremath{\sigma \sample \sSignP}{} where \ensuremath{\sski = \DerivePriv(\pp{}, \ensuremath{\mathsf{d}}_0, \cvzero{}, \cvi{})}{}.
          Let $\ensuremath{\mathcal{Q}}{}_\pcalgostyle{Sign}$ denote the pairs $(m, \ensuremath{\cv{i}}{})$ for which \pcalgostyle{A}{} queried the oracle $\ensuremath{\ensuremath{\pcalgostyle{O}}_{\Sign}}$.
      \end{description}
    \item[Forgery:] \pcalgostyle{A}{} outputs a forgery $(\ensuremath{\cv{i}}{}, m, \sigma)$.
     If $\pcalgostyle{Vrfy}_{\ensuremath{\pk_{i}}}(m, \sigma) = 1$ where $\ensuremath{\pk_{i}}{} = \ensuremath{\DerivePub(\pp{}, \cvi{})}{}$ and $\ensuremath{\cv{i}} \notin \ensuremath{\mathcal{Q}}_\ensuremath{\mathsf{Corr}}$, $(m, \ensuremath{\cv{i}}{}) \notin \ensuremath{\mathcal{Q}}_\pcalgostyle{Sign}$, return $1$; otherwise return $0$.
  \end{description}
\end{definition}

\section{Arcula: A Secure Hierarchical Deterministic Wallet}\label{sec:arcula}
Arcula, the design that we present in this paper, satisfies the properties of HDW formalized by~\Cref{def:HDW-corr,def:HDH-euf}.
It is provably secure against key recovery;
it deterministically derives the private information from an initial seed;
and it enables identity-based public key derivation.
It achieves such result by relying on two fundamental intuitions:
Securely and deterministically generating a set of keys for the users of a hierarchy and then explicitly associating these keys with their identities.
By doing so, Arcula provides a groundbreaking design that brings identity-based cryptography to the blockchain, tackles explicitly novel use cases and applications, and stands on more than $20$ years of research in how to securely distribute keys to the users in a hierarchy.

At its core, indeed, Arcula derives the keys of the users by relying on a deterministic version of hierarchical key assignment schemes (HKA):
A provably secure process that, precisely as it happens in an HDW, takes as input a hierarchy of users and assigns a secret key to every user, so that users with higher privileges can derive the keys of those with fewer privileges.
To the best of our knowledge, hierarchical key assignment schemes have never been leveraged before implementing an HDW\@.
As a result, one of the contributions of this work is to bind together, for the first time, these seemingly unrelated fields of research.
In addition, hierarchical key assignment schemes provide several advantages:
They're highly efficient and have been extensively studied in the past;
they enable Arcula to implement arbitrarily complex hierarchies, to integrate temporal capabilities into the wallet, and to support the dynamic addition or removal of users to the hierarchy.

The following sections first provide a brief background on (deterministic) hierarchical key assignment schemes and then describe, in detail, our construction of Arcula.

\subsection{Deterministic Hierarchical Key Assignment}\label{sub:deterministic_hierarchical_key_assignment}
A hierarchical key assignment scheme~\cite{atallah:2009:dek:1455526.1455531} assigns a set of cryptographic keys to a set of users in a hierarchy.
The hierarchy, encoded as a directed acyclic graph, represents the access rights of users:
A path from a node \ensuremath{\cv{i}}{} to a node \ensuremath{\cv{j}}{} implies that the user \ensuremath{\cv{i}}{} has higher privileges than \ensuremath{\cv{j}}{} and can assume the same access rights of \ensuremath{\cv{j}}{}.
An efficient hierarchical key assignment scheme (HKA) enforces the access hierarchy while minimizing the number of keys distributed to the users.

Typically, HKA schemes sample the cryptographic secrets that they assign at random.
Our goal, however, is to leverage an HKA at the core of our wallet, where each secret is deterministically derived from a seed provided by the user.
To do so, we propose a deterministic modification of the HKA developed by Atallah \emph{et al.}~\cite{atallah:2009:dek:1455526.1455531} that is secure under key indistinguishability (and as a consequence guarantees~\Cref{prp:secret_keys} by design).

A Deterministic Hierarchical Key Assignment (DHKA) scheme with seed space $\ensuremath{\mathcal{S}}$ is composed of the following polynomial-time algorithms:
\begin{description}
  \item[\ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}{}:] The deterministic setup algorithm takes as input the security parameter, a DAG \ensuremath{\cG = (\cV, \cE)}{}, and an initial seed \ensuremath{\cSeed \in \ensuremath{\mathcal{S}}}{}, and outputs two mappings:
    \begin{inlinelist}
    \item a public mapping \ensuremath{\Pub : \cV \cup \cE \to	\bin^{*}}{}, associating a public label \ensuremath{\cl{i}}{} to each node \ensuremath{\cv{i}}{} in \ensuremath{G}{} and a public information \ensuremath{\cy{ij}}{} to each edge \ensuremath{(\cvi, \cvj) \in \cE}{};
    \item a secret mapping \ensuremath{\Sec : \cV \to \bin^\secpar \times \bin^\secpar}{}, associating a secret information \ensuremath{\cS{i}}{} and a cryptographic key \ensuremath{\cx{i}}{} to each node \ensuremath{\cv{i}}{} in \ensuremath{G}{}. (No secret information is associated to the edges).
    \end{inlinelist}
  \item[\ensuremath{\Derive(\cG{}, \Pub{}, \cvi{}, \cvj{}, \cSi{})}{}:]\tDerive{}
\end{description}

Informally, the correctness of a DHKA scheme requires that every user must be able to derive, correctly, the secret key of any other user lower in the hierarchy.
Its security definition, instead, requires that even if an attacker corrupts an arbitrary number of descendants of a node, he cannot distinguish its secret key from a uniformly random string.
We formalize the security model and the construction of our DHKA in~\Cref{sec:deterministic_wallets_through_dynamic_and_efficient_key_management}.



\subsection{Constructing Arcula from DHKA and signatures}\label{sub:arcula_implementation}

Arcula, our implementation of a hierarchical deterministic wallet, relies on deterministic hierarchical key assignment schemes (DHKA) and digital signatures.
This section details our construction, that we describe through the \ensuremath{(\Set, \DerivePub, \DerivePriv, \allowbreak \Sign, \Verify)}{} algorithms that define a hierarchical deterministic wallet.
The \pcalgostyle{Set}{} algorithm instantiates the scheme, starting from the initial seed to deterministically generate a pair of \emph{master public and secret} keys \ensuremath{(\msk, \mpk)}{}.
The master keys respectively serve two purposes:
To identify the users of the wallet and to assign a pair of \emph{signing} keys \ensuremath{(\skXi, \pkXi)}{} to each of them.
We generate the signing keys through the key indistinguishable DHKA scheme of~\Cref{sub:deterministic_hierarchical_key_assignment}, so that users can sign transactions on behalf of their descendants while guaranteeing the security of their keys against privilege escalation.
In more detail, the DHKA assigns to each user \ensuremath{\cv{i}}{} a derivation key \ensuremath{\derkey_i}{} that allows them to generate their own signing keys \ensuremath{\skX_{i}}{} and to derivate those of their descendants.
We set the master secret key to the derivation key of the user \ensuremath{\cv{0}}{} with highest privileges in the hierarchy\footnote{If there exist multiple users with maximum privileges it is always possible to modify the structure of the DAG and add a \emph{minimal} node that does not correspond to any real user, does not change the hierarchical ordering of the others, and has the highest privileges. We describe the modification in detail in~\Cref{sec:deterministic_wallets_through_dynamic_and_efficient_key_management}.}, \emph{i.e.}, $\ensuremath{\mathsf{msk}} = \ensuremath{\mathsf{d}}_0$.
The master public key \ensuremath{\mathsf{mpk}}{}, on the other hand, unequivocally identifies the wallet.
We set it to the public signing key of \ensuremath{\cv{0}}{} ($\ensuremath{\mathsf{mpk}} = \ensuremath{\overline{\pk}}_0$), and we combine it with the identifiers of users to achieve public key derivation.
In particular, we identify a user \ensuremath{\cv{i}}{} of the wallet by concatenating the master public key \ensuremath{\mathsf{mpk}}{} with the public label \ensuremath{\cl{i}}{} associated with her.
Finally, the \pcalgostyle{Set}{} algorithm binds the identifies of users to their signing key pair \ensuremath{(\skXi, \pkXi)}{} through a certificate, signed by the master secret key \ensuremath{\mathsf{msk}}{}\footnote{The master secret key \ensuremath{\mathsf{msk}}{} deterministically generates the (master) signing key $\ensuremath{\overline{\sk}}_0{}$, that we use to sign the certificates.}, that explicitly authorizes the signing key \ensuremath{\skX_{i}}{} to spend the coins destined to \ensuremath{\cv{i}}{}.
The \pcalgostyle{DPriv}{} and \pcalgostyle{DPub}{} algorithms respectively derive the signing keys (through the DHKA scheme) and the corresponding public keys (by combining the master public key \ensuremath{\mathsf{mpk}}{} and the node identifiers).
Finally, the \pcalgostyle{Sign}{} and the \pcalgostyle{Vrfy}{} algorithms handle the creation and verification of digital signatures.
Any node \ensuremath{\cv{i}}{} runs the \pcalgostyle{Sign}{} algorithm with its signing key \ensuremath{\skX_{i}}{} to create a signature and the \pcalgostyle{Vrfy}{} algorithm checks that there exists a certificate authorizing \ensuremath{\skX_{i}}{} to spend funds on behalf of the node \ensuremath{\cv{i}}{} (identified by the label \ensuremath{\cl{i}}{}) under the master secret key \ensuremath{\mathsf{msk}}{}.

On the blockchain, the master public key \ensuremath{\mathsf{mpk}}{} and the public label \ensuremath{\cl{i}}{} of a user form her address for receiving payments.
The users spend funds by signing transactions through their signing key \ensuremath{\skX_{i}}{} and by presenting, at the same time, the certificate that associates their keys to their identity and that authorizes them to spend funds.
This approach provides several advantages.
Receiving funds does not require the certificate---the identity-based public key derivation allows us to generate the address of any destination node without any private information.
Users only require their certificate when spending funds for the first time, \emph{i.e.}, when signing a transaction through their secret key \ensuremath{\skX_{i}}{}, and the creation of the certificate can happen entirely offline (\emph{i.e.}, in cold storage).
In addition, the signing keys \ensuremath{(\skXi, \pkXi)}{} can also provide users with unlinkability of their transactions.
As we describe in~\Cref{sub:transactions_unlinkability}, users that do not need the identity-based public key derivation can directly leverage the signing public key \ensuremath{\pkX_{i}}{} as a pseudonym address on which to receive funds and then spend them through the corresponding private key \ensuremath{\skX_{i}}{}.

\begin{construction}\label{const:cert-arcula}
Let \DHKA{} = \ensuremath{(\SetDHKA, \DeriveDHKA)}{}{} and \ensuremath{\ECDSA{} = \ensuremath{(\KeygenECDSA, \SignECDSA, \allowbreak \VerifyECDSA)}}{} be respectively a DHKA and a signatures signature scheme.
We build Arcula in the following way:
\begin{description}
 \item[\ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}:] On input the security parameter, a DAG $\ensuremath{G}{} = (\ensuremath{V}, \ensuremath{E})$, and a seed $\ensuremath{\cS{}} \in \ensuremath{\mathcal{S}}$ the algorithm proceeds as follows:
 \begin{enumerate}
   \item Compute $\ensuremath{(\Pub, \Sec)}{} = \ensuremath{\Set_{\DHKA}(\secparam, \cG, \cSeed)}{}$.
   \item For each node $\ensuremath{\cv{i}} \in \ensuremath{V}$:\label{enum:w_set_proof}
     \begin{enumerate}
       \item Let $\ensuremath{(\cSi, \cxi)}{} = \ensuremath{\Sec(\cvi)}{}$ and set $\ensuremath{\derkey_i}{} = \ensuremath{\cS{i}}{}$.\label{enum:w_set_proof_skip}
       \item $(\ensuremath{\overline{\sk}}_i, \ensuremath{\overline{\pk}}_i) = \pcalgostyle{Keygen}_{\ensuremath{\Sigma}}(\secparam; \ensuremath{\cx{i}}{})$.\label{enum:w_set_proof_inner}
     \end{enumerate}
   \item Output $\pp{} = (\ensuremath{G}{}, \pcalgostyle{Pub}{}, \ensuremath{\set{\ensuremath{\cert_{i}}}_{\ensuremath{\cv{i}} \in \ensuremath{V}}}{}, \ensuremath{\overline{\pk}}_0)$ and ${\{\ensuremath{\derkey_i}\}}_{\ensuremath{\cv{i}}\in\ensuremath{V}}$ where $\ensuremath{\cert_{i}} \sample \pcalgostyle{Sign}_{\ensuremath{\Sigma}}(\ensuremath{\overline{\sk}}_0, (\ensuremath{\overline{\pk}}_i, \ensuremath{\cl{i}}{}))$ for $\ensuremath{\cv{i}} \in \ensuremath{V}$, and $\ensuremath{\cl{i}} = \pcalgostyle{Pub}(\ensuremath{\cv{i}})$.\label{enum:sign_oracle_proof_inner}
 \end{enumerate}

 \item[$\pcalgostyle{DPub}(\pp{}, \ensuremath{\cv{j}})$:] On input the public parameters $\pp{} = (\ensuremath{G}{}, \pcalgostyle{Pub}{}, \ensuremath{\set{\ensuremath{\cert_{i}}}_{\ensuremath{\cv{i}} \in \ensuremath{V}}}{}, \ensuremath{\overline{\pk}}_0)$ and a node $\ensuremath{\cv{j}}{} \in \ensuremath{V}$, the algorithm returns $\pk_j= (\ensuremath{\overline{\pk}}_0, \ensuremath{\cl{j}}{})$ where $\ensuremath{\cl{j}} = \pcalgostyle{Pub}(\ensuremath{\cv{j}})$.

 \item[$\pcalgostyle{DPriv}(\pp{}, \ensuremath{\derkey_i}, \ensuremath{\cv{i}}, \ensuremath{\cv{j}})$:] On input the public parameters $\pp{} = (\ensuremath{G}{}, \pcalgostyle{Pub}{}, \ensuremath{\set{\ensuremath{\cert_{i}}}_{\ensuremath{\cv{i}} \in \ensuremath{V}}}{}, \ensuremath{\overline{\pk}}_0)$, the derivation key $\ensuremath{\derkey_i}{} = \ensuremath{\cS{i}}{}$, and two nodes $\ensuremath{\cv{i}}{}, \ensuremath{\cv{j}}{}\in \ensuremath{V}$ such that $\ensuremath{\cv{j}}{} \in \desc(\cvi)$, the algorithm runs $\ensuremath{\cx{j}} = \ensuremath{\Derive_{\DHKA}}(\ensuremath{G}{}, \pcalgostyle{Pub}{}, \ensuremath{\cv{i}}{}, \ensuremath{\cv{j}}{}, \ensuremath{\cS{i}}{})$ and $(\ensuremath{\overline{\sk}}_j, \ensuremath{\overline{\pk}}_j) = \pcalgostyle{Keygen}_{\ensuremath{\Sigma}}(\secparam; \ensuremath{\cx{j}}{})$.
 Finally, it returns $\sk_j = (\ensuremath{\overline{\sk}}_j, \ensuremath{\overline{\pk}}_j, \ensuremath{\ensuremath{\mathsf{cert}}}_j)$.

 \item[$\pcalgostyle{Sign}(\sk_{i}, m)$:] On input a signing key $\sk_i = (\ensuremath{\overline{\sk}}_i, \ensuremath{\overline{\pk}}_i, \ensuremath{\ensuremath{\mathsf{cert}}}_i)$ and a message $m$, the algorithms returns $\sigma = (\ensuremath{\overline{\pk}}_i, \sigma', \ensuremath{\cert_{i}})$ where $\sigma' \sample \pcalgostyle{Sign}_{\ensuremath{\Sigma}}(\ensuremath{\overline{\sk}}_i, m)$.

 \item[$\pcalgostyle{Vrfy}(\mathsf{pk}_{i}, m, \sigma{})$:] On input a public key $\pk_i=(\ensuremath{\overline{\pk}}_0,\ensuremath{\cl{i}})$, a message $m$, and a signature $\sigma{} = (\ensuremath{\overline{\pk}}_i, \sigma', \ensuremath{\cert_{i}})$, the algorithms returns $1$ if $\pcalgostyle{Vrfy}_{\ensuremath{\Sigma}}(\ensuremath{\overline{\pk}}_0, (\ensuremath{\overline{\pk}}_i, \ensuremath{\cl{i}}{}), \ensuremath{\cert_{i}}) = 1$ and $\pcalgostyle{Vrfy}_{\ensuremath{\Sigma}}(\ensuremath{\overline{\pk}}_i, m, \sigma') = 1$; otherwise it returns $0$.
\end{description}
\end{construction}

\begin{remark}
  Arcula shares a significant number of similarities with identity-based hierarchical signature schemes~\cite{10.1007/3-540-36178-2_34}.
  Its design, indeed, associates a pair of signing keys to the identity of a user and allows her to sign messages on behalf of her descendants.
  We point out, however, some fundamental differences.
  Most hierarchical identity-based signature schemes leverage a conspicuous number of public parameters and rely on bilinear mappings.
  This makes them unpractical to use in the existing blockchains:
  The underlying protocols should efficiently handle the bilinear mappings, and the public parameters that define the instantiation of the scheme should be stored on the blockchain itself.
  Our design of Arcula, on the other hand, explicitly takes into consideration the characteristics and the limitations of blockchain systems:
  We do not rely on bilinear mappings, and we only store a small portion of the public parameters \pp{} (one certificate per transaction, typically a single group element) on the blockchain.
\end{remark}

The correctness of the scheme comes directly from the correctness of the underlying primitives.
As for security, we establish the following result whose proof appears in~\Cref{subsec:proof_arcula}.
\begin{theorem}\label{thm:arcula_euf}
  Let \DHKA{} = \ensuremath{(\SetDHKA, \DeriveDHKA)}{}{} and $\ensuremath{\Sigma} = (\kgen_\ensuremath{\Sigma}, \pcalgostyle{Sign}_\ensuremath{\Sigma}, \pcalgostyle{Vrfy}_\ensuremath{\Sigma})$ be respectively a deterministic hierarchical key assignment and a signature scheme.
  If \ensuremath{\Gamma}{} is key indistinguishable (\Cref{def:sec_dka}) and $\ensuremath{\Sigma}$ is existentially unforgeable (\Cref{def:SigUnforgeability}), then the HDW $\Pi$ from \Cref{const:cert-arcula} is hierarchically existentially unforgeable (\Cref{def:HDH-euf}).
\end{theorem}

In the context of the security model that we defined in~\Cref{sub:threats_and_security_model}, Arcula's public derivation belongs to the \textbf{Untrusted Environment}---it merely relies on the concatenation of two public values, the master public key \ensuremath{\mathsf{mpk}}{} and the identifier \ensuremath{\cl{i}}{} of node \ensuremath{\cv{i}}{}.
Redeeming coins requires, instead, the \textbf{Hot Environment}.
The certificate \ensuremath{\cert_{i}}{} that associates \ensuremath{\cv{i}}{} to its public key \ensuremath{\pkX_{i}}{} is a public parameter of the wallet, but we require the node's corresponding private signing key \ensuremath{\skX_{i}}{} to sign a new transaction.
Compromising the secrets of node \ensuremath{\cv{i}}{} leads to compromising all its descendants, but none of the other nodes.
Finally, the master secret key \ensuremath{\mathsf{msk}}{} and the related signing key $\ensuremath{\overline{\sk}}_0$ must be safely kept in \textbf{Cold Storage}.
We leverage these keys in the setup phase to prepare the authorization certificate \ensuremath{\cert_{i}}{} of \ensuremath{\cv{i}}{} and, for this reason, it is critical to the security of the wallet:
An attacker can use it to forge a certificate that associates any pair of keys to any target node and spend, in turn, the coins held in the entire wallet.

To summarize, Arcula defines a hierarchical deterministic wallet that benefits from the following properties:
\ifCONF{}
\begin{inlinelist}
\else
\begin{enumerate}
\fi
  \item Is secure against privilege escalation (\Cref{prp:secret_keys}).
  \item Generates every cryptographic key from an initial seed (\Cref{prp:determinism}).
  \item Enables identity-based public-key derivation so that users can dynamically derive new public keys without accessing their own private keys (see~\Cref{prp:public_keys}).
  \item Enables secret-key derivation so that users can sign transactions on behalf of their descendants.
  \item Does not rely on any particular digital signature scheme.
  \item The DHKA at the core of Arcula is secure under key indistinguishability and handles any directed acyclic graph encoding a partially ordered hierarchy.
    In addition, it allows dynamic modifications to the hierarchy (\emph{i.e.}, by adding or removing nodes, as we detail in~\Cref{sec:dynamic_changes}) and controlling the key assignment according to some temporal constraints (\Cref{sec:time_bound_deterministic_hierarchical_key_assignment}).
\ifCONF{}
\end{inlinelist}
\else
\end{enumerate}
\fi
\section{Deterministic Wallets through Chain-Based Key Assignment}\label{sec:deterministic_wallets_through_chain_based_key_assigment}

\subsection{Chain-based Hierarchical Key Assignment schemes}\label{sub:chain_based_hierarchical_key_assignment_schemes}
After reviewing the existing literature in Hierarchical Key Assignment schemes we found that there exists a family of schemes, that:
\begin{itemize}
    \item Is provably secure under key indistinguishability.
    \item Does not require storing any public information.
    \item Provides efficient key derivation in both time and space.
\end{itemize}
Such schemes are based on chain or tree partitioning and have been first described by J. Crampton \emph{et al.}~\cite{crampton2010} in 2010.
The informal intuition behind these schemes is to partition any arbitrary hierarchy (encoded as a graph representing the partially ordered set, \emph{i.e.}, the hierarchy itself) in disjoint chains.
\begin{figure}[htpb]
    \centering
    \includegraphics[width=0.8\linewidth]{resources/bip44_partition.pdf}
    \caption{%
        Chain-based partitioning of the tree defined by BIP43 and BIP44 and depicted in~\Cref{fig:resources/bip44}.
    }\label{fig:resources/bip44_partition}
\end{figure}
Each chain is a simple sequence of nodes representing users or security labels. 
Within the chain the key derivation is simple, efficient, and straightforward: 
The secret of the $i$-th element of the chain is derived directly from the secret of the $i-1$-th element, \emph{i.e.}, its predecessor in the chain.
Nodes that \emph{connect} two or more chains of the hierarchy also serve a special purpose:
They serve as intermediate nodes for the key derivation in the chain they belong to, and they also hold additional keys to \emph{bridge} the other chains that they connect to.
As an example,~\Cref{fig:resources/bip44_partition} describes a partitioning the graph of~\Cref{fig:resources/bip44}. 
The node labeled with BTC belongs to chain $0$, the chain composed of all the leftmost elements of the tree.
As such, its secret is used to derive the secret of its children labeled with $0$ belonging to the same chain.
At the same time, it connects chain $1$ of its other children, labeled with $1$, to its chain and back to the tree:
For this reason, it will hold an additional secret, \emph{i.e.}, the secret of its children labeled with $1$, to allow for the derivation of its key and of those of its descendants.
In 2015, Crampton \emph{et al.}~\cite{crampton2015} showed that there always exists an optimal chain partition of an arbitrary hierarchy and describe a polynomial algorithm to find it.
In addition, they prove that with an optimal partitioning no user is required to store more than $w$ keys, where $w$ is the number of different chains.
An efficient implementation of HKA based on chain partitioning and pseudorandom functions (PRFs) has been proposed by Freire \emph{et al.}~\cite{freire2013} in 2013.
The authors also proved the security of the scheme under key indistinguishability.

\subsection{BIP44 HDW through HKA schemes}\label{sub:hdw_through_hka_schemes}
Our first goal is to leverage chain-based hierarchical key assignment to replicate the hierarchical deterministic wallet defined in BIP44 that we described in~\Cref{sub:from_keys_to_a_tree,fig:resources/bip44}.
We recall that BIP44 defines the wallet's hierarchy with a tree where children nodes are uniquely identified by their index with respect to their parent.

We begin by partitioning the tree in disjoint chains:
We use a modified Depth-First-Search (DFS) visit that puts any children with index $0$ (\emph{i.e.}, the leftmost) in the same chain of their parent, and all the others in as many new chains.
As a result, we get exactly $w$ chains, where $w$ is the maximum branching factor of the tree.
\Cref{fig:resources/bip44_partition} describes the result of the partitioning on the hierarchy of~\Cref{fig:resources/bip44}.
Then, we leverage a slight variation of the scheme described by Freire \emph{et al.}~\cite{freire2013} to deterministically assign a secret and a key to all the elements of the tree.

More in details, each chain describes a totally ordered hierarchy.
The derivation of the secret of each node works as follows.
Let $s_0$ be a secret assigned to the first element of the chain and let $\fash$ be a pseudorandom function (in our case, $\fash_k(x) = \text{SHA3\_512}(k \concat x)$).
For each node of index $i$ in the chain and for $i > 0$, the secret $s_i$ is defined as:
\begin{equation}
    s_i = \fash_{S_{i - 1}}(0)
\end{equation}
For any node $i$, the key $k_i$ is:
\begin{equation}
    k_i = \fash_{s_{i}}(-1)
\end{equation}

To select the $s_0^j$ secrets of the $w$ chains in the partitions, we proceed as follows.
We first derive the secret of the root node of the tree, $s_0^0$, from the user's seed $S_{-1}$ (as defined by BIP32).
\begin{equation}
    s_0^0 = \fash_{S_{-1}}(0)
\end{equation}
Any other head of a chain will have exactly one predecessor, since the hierarchy is a tree.
Let $j$ be a chain and, without loss of generality, let $j - 1$ be the chain that connects the chain $j$ back to the tree. 
Let the $i$-th node of the $j - 1$-th chain be the connection node.
Let the head of chain $j$ be the $n$-th children of the $i$-th node of chain $j - 1$.
Then:
\begin{equation}\label{eq:chain_connect}
    s_0^j = \fash_{s_i^{j - 1}}(n).
\end{equation}
$n$ is always different than $0$ in~\Cref{eq:chain_connect}, since otherwise the head of the chain $j$ would be the leftmost children of its parent and our DFS would put both nodes in the same chain.

The implementation of a chain-based HKA scheme proposed by Freire \emph{et al.}~\cite{freire2013} is secure under key-indistinguishability.
There, the authors choose the secrets $S_0^j$ of any head of a chain $j$ at random.
In our case instead, we choose it deterministically by using the secret of their parent node as the key of a PRF $\fash$.
However, since the output of $\fash$ is indistinguishable from a random string of the same length, our scheme is as secure as the one proposed by Freire \emph{et al.} under the same security definitions (\emph{i.e.}, key indistinguishability).

Since we are working on a tree, our chain-based scheme can also be compactly defined as follows.
For any node $u$, being the $n$-th children of its parent $v$ (regardless of its chain and of its position in the chain):
\begin{equation}\label{eq:compact}
    s_u = \fash_{s_v}(n)
\end{equation}
In addition, we note that we are not storing any additional information in the tree and that the total number of secrets is equal to the number of nodes.

Finally, we note that our implementation defines the same hierarchical structure of BIP44 (since we work on the same tree) and benefits from the properties defined in BIP32 (specifically,~\Cref{prp:determinism} and~\Cref{prp:secret_keys});~\Cref{prp:public_keys} does not hold --- our scheme always perform the \emph{hardened} key derivation described in BIP32.

\subsection{BIP32: An instance of chain-based HKA}\label{sub:bip32_an_instance_of_chain_based_hka}
The compact representation of our scheme defined in~\Cref{eq:compact} shows how the secret of a node $u$ exclusively depends on the secret of its parent $v$ and on its index as a children $n$. 
As such, the equation shows strong similarities with how BIP32 defines the key derivation for the $n$-th child of a root node in~\Cref{eq:secret_key_h}, with the pseudorandom function $\fash_k(x)$ defined as $\hash(k \concat x) + k$.
By transitivity, the same considerations apply to the chain-based definitions of our scheme.
This result shows, intuitively, that BIP32 is a particular instance of the chain-based HKA scheme proposed first by Crampton \emph{et al.} and then by Freire \emph{et al.}~\cite{crampton2010,freire2013}.
As such, even if we do not provide formal proof, we believe that BIP32 is secure under the same security definitions (\emph{i.e.}, key indistinguishability).


\section{Conclusions}\label{sec:conclusions}
In this work, we presented Arcula, a new hierarchical deterministic wallet (HDW) that brings identity-based signatures to the blockchain, and that is secure against privilege escalation.
We first developed a key indistinguishable deterministic hierarchical key assignment (DHKA) scheme, that we use to deterministically generate the set of cryptographic keys at the core of our wallet.
As a result, an attacker that compromises an arbitrary number of users in the hierarchy can not escalate his privileges and compromise other users higher in the hierarchy.
In addition, our wallet allows us to dynamically derive new addresses for receiving payments in an entirely untrusted environment, to recover every cryptographic key from an initial seed provided by the user, and also to spend coins on behalf of users lower in the hierarchy.
Our design of Arcula considers the legacy and future requirements of modern blockchains.
In particular, Arcula is independent of the underlying signature scheme, and it works on top of any protocol that allows the verification of signatures on an arbitrary message (\emph{e.g.}, Bitcoin Cash or Ethereum).
For these reasons, we hope that the outcomes of this work will be twofold:
To provide the secure and efficient hierarchical deterministic wallet that we need today and to propose a future-proof design that supports the financial applications and tools of enterprises and companies at scale.

\section{Security Model of Deterministic Hierarchical Key Assignment}\label{sec:deterministic_wallets_through_dynamic_and_efficient_key_management}
The correctness of a DHKA scheme requires that any user \ensuremath{\cv{i}}{} should be able to derive, correctly, the secret key \ensuremath{\cx{j}}{} of any user $\ensuremath{\cv{j}} \in \ensuremath{Desc}(\ensuremath{\cv{j}})$ lower in the hierarchy.

\begin{definition}[Correctness of DHKA]\label{def:kidhka}
  A DHKA $\Pi=(\pcalgostyle{Set},\pcalgostyle{Derive})$ with seed space $\ensuremath{\mathcal{S}}$ is correct if for every DAG $\ensuremath{G} = (\ensuremath{V}, \ensuremath{E})$, $\forall \secpar \in \NN$, $\forall v_i \in \ensuremath{V}$, $\forall \ensuremath{\cv{j}} \in \ensuremath{Desc}{}(\ensuremath{\cv{i}})$, $\forall \ensuremath{\cSeed \in \ensuremath{\mathcal{S}}}{}$:
  \begin{equation*}
    \prob{\cx{j} = \ensuremath{\Derive(\cG{}, \Pub{}, \cvi{}, \cvj{}, \cSi{})}{}} = 1,
  \end{equation*}
  where $\ensuremath{(\Pub, \Sec)} = \ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}$, $(\ensuremath{\cS{i}}, \ensuremath{\cx{i}}) = \pcalgostyle{Sec}(\ensuremath{\cv{i}})$, and $(\cS{j}, \cx{j}) = \pcalgostyle{Sec}(\ensuremath{\cv{j}})$.
\end{definition}

We now formalize the security level of the scheme.
We adapt the security definition originally defined by Atallah \emph{et al.}~\cite{atallah:2009:dek:1455526.1455531} to account for the determinism in our scheme.
We define the set of ancestors \ensuremath{\anc(\cvi)} = \set{\cvj{} \mid \cvj{} \leadsto_w \cvi{}}{} of a node \ensuremath{\cv{i}}{} to be the set of nodes \ensuremath{\cv{j}}{} such that there exists a path $w$ from \ensuremath{\cv{j}}{} to \ensuremath{\cv{i}}{} in \ensuremath{G}{}.

\begin{definition}[Key Indistinguishability of DHKA]\label{def:sec_dka}
  A DHKA $\Pi = (\pcalgostyle{Set}, \pcalgostyle{Derive}{})$ with seed space $\ensuremath{\mathcal{S}}$ is key indistinguishable if for every PPT adversary \pcalgostyle{A}{} and every DAG $\ensuremath{G} = (\ensuremath{V}, \ensuremath{E})$:
  \begin{equation*}
    \biggl| \prob{\ensuremath{\Game{}_{\Pi, \pcalgostyle{A}}^{\mathsf{sk-ind}}(\secpar, \ensuremath{G}{}}){} = 1} - \frac{1}{2} \biggr| \leq \negl{},
  \end{equation*}
  where \ensuremath{\Game{}_{\Pi, \pcalgostyle{A}}^{\mathsf{sk-ind}}(\secpar, \ensuremath{G}{}}){} is defined in the following way:
  \begin{description}
    \item [Setup:] The challenger receives a challenge node $\ensuremath{\cv{}^{*}}{} \in \ensuremath{V}$ from the adversary \pcalgostyle{A}{}.
      The challenger samples $\ensuremath{\cS{}} \sample \ensuremath{\mathcal{S}}$, then runs \ensuremath{\Set(\secparam, \cG,\allowbreak \cSeed)}{}, and gives the resulting public information \pcalgostyle{Pub}{} to the adversary \pcalgostyle{A}{}.
      The challenger samples a random bit $b^{*} \sample \bin$:
      If $b^{*} = 0$, it returns to \pcalgostyle{A}{} the cryptographic key \ensuremath{\cx{\cvstar}}{} associated to node \ensuremath{\cv{}^{*}}{};
      otherwise, it returns a random key \ensuremath{\bar{x}_{\cvstar}}{} of the corresponding length.
    \item[Query:] The adversary has access to a corrupt oracle $\ensuremath{\ensuremath{\pcalgostyle{O}}_{\ensuremath{\mathsf{Corr}}}}(\cdot)$. On input $\ensuremath{\cv{i}}{} \notin \ensuremath{Anc}(\ensuremath{\cv{}^{*}}{})$, the challenger retrieves $\ensuremath{(\cSi, \cxi)} = \ensuremath{\Sec(\cvi)}$ and sends \ensuremath{\cS{i}}{} to \pcalgostyle{A}{}.
    \item[Guess:] The adversary outputs a bit $b \in \bin$. If $b = b^*$ return $1$; otherwise return $0$.
  \end{description}
\end{definition}

\begin{remark}
We note that the adversary \pcalgostyle{A}{} depicted in \ensuremath{\Game{}_{\Pi, \pcalgostyle{A}}^{\mathsf{sk-ind}}(\secpar, \ensuremath{G}{}}){} is a static adversary who chooses the challenge node \ensuremath{\cv{}^{*}}{} before the experiment begins.
Ateniese \emph{et al.}~\cite[Theorem 1]{ateniese2012}, however, prove that any hierarchical key assignment scheme secure (in the sense of \ensuremath{\Game{}_{\Pi, \pcalgostyle{A}}^{\mathsf{sk-ind}}(\secpar, \ensuremath{G}{}}){}) against a static attacker is also secure against an adaptive attacker, \emph{i.e.}, against an adversary that adaptively chooses the challenge node \ensuremath{\cv{}^{*}}{}.
The authors prove that the two security models are polynomially equivalent since there exists a reduction between the static and the adaptive adversaries.
The static adversary can simply guess the challenge node \ensuremath{\cv{}^{*}}{} of the adaptive adversary and abort the simulation if the guess is incorrect.
For these reasons, we discuss the security of any DHKA scheme only in the setting of a static attacker.
\end{remark}

\subsection{The DHKA scheme}\label{sub:dhka_implementation}
This section describes the implementation of our deterministic hierarchical key assignment scheme over any DAG \ensuremath{G}{} encoding an access hierarchy.

We assume, without loss of generality, that:
\begin{inlinelist}
\item There exists a unique \emph{root} node $\ensuremath{\cv{0}}{} \in \ensuremath{V}{}$ of \ensuremath{G}{}, \emph{i.e.} the most-privileged node of the hierarchy encoded by \ensuremath{G}{} that can derive the keys of any other node.
  For any DAG \ensuremath{G}{}, it is always possible to elect a root node \ensuremath{\cv{0}}{}.
  Since \ensuremath{G}{} is a DAG, \ensuremath{\cv{0}}{} shall be one of the minimal nodes in a topological ordering of \ensuremath{G}{} and, equivalently, \ensuremath{\cv{0}}{} shall have no ancestors.
  If two or more nodes \ensuremath{\cv{j}}{} have no ancestors, then it is always possible to construct a new graph $\ensuremath{G}{}' = (\ensuremath{V} \cup \set{\ensuremath{\cv{0}}{}}, \ensuremath{E} \cup \set{(\ensuremath{\cv{0}}{}, \ensuremath{\cv{j}}) \mid \ensuremath{\cv{j}}{} \text{ has no ancestors}})$ such that the access hierarchy encoded by $\ensuremath{G}{}'$ is equivalent to the one of \ensuremath{G}{}, where the new node \ensuremath{\cv{0}}{} in $\ensuremath{G}'{}$ is the root of the graph (and has no associated users).
\item That every node \ensuremath{\cv{j}}{} has a fixed \emph{parent} node in the hierarchy, \emph{i.e.} a node \ensuremath{\cv{i}}{} such that the edge $\ensuremath{(\cvi, \cvj) \in \cE}{}$.
  As an example, we fix the parent node \ensuremath{\cv{j}}{} of \ensuremath{\cv{i}}{} to be the first ancestor of \ensuremath{\cv{i}}{} in any ordering of the nodes of the graph \ensuremath{G}{} (\emph{e.g.}, obtained with a depth-first-search of the graph) such that \ensuremath{(\cvi, \cvj) \in \cE}{}.
\end{inlinelist}

At a high level, we build on the randomized hierarchical key assignment scheme of Atallah \emph{et al.}~\cite{atallah:2009:dek:1455526.1455531} where each node \ensuremath{\cv{i}}{} of the hierarchy is identified by a random label \ensuremath{\cl{i}}{} and holds a random secret information \ensuremath{\cS{i}}{}, that it will use to generate its own cryptographic key and to derive the keys of the nodes lower in the hierarchy.
In our scheme, we modify the original design so that both the label \ensuremath{\cl{i}}{} and the secret information \ensuremath{\cS{i}}{} are deterministic.
We label each node through its index\footnote{
We will extend the node labels with a version number when handling dynamic changes to the hierarchy of the DHKA.
We refer the reader to~\Cref{sec:dynamic_changes} for more details.
} (\emph{i.e.}, $\ensuremath{\cl{i}}{} = \ensuremath{\cv{i}}{}$) and we derive its secret information \ensuremath{\cS{i}}{} deterministically (through a pseudorandom function) from the secret information of its parent.
We formally define our implementation of DHKA as follows.
\begin{construction}\label{const:dka}
  Let \ensuremath{\set{\fash_{k}}_{k \in \ensuremath{\mathcal{K}}_\secpar}}{} and $\ensuremath{\mathcal{E}}{} = (\pcalgostyle{Gen}, \enc, \dec)$ be respectively a family of pseudorandom functions and a symmetric key encryption scheme.
  Let \ensuremath{\cG = (\cV, \cE)}{} be a directed acyclic graph representing an access hierarchy.
  We build a DHKA scheme in the following way:
  \begin{description}
    \item[$\pcalgostyle{Set}{}(1^\secpar, \ensuremath{G}{}, S_{-1})$:] On input the security parameter, a directed acyclic graph \ensuremath{\cG = (\cV, \cE)}{}, and an initial seed $S_{-1}$, the algorithm proceeds as follows:
      \begin{enumerate}
        \item Compute \ensuremath{\cSzero = \dSzero{}}{} for $\cv{0} \in \ensuremath{V}$, where \ensuremath{\clzero = \dlzero}{} and \ensuremath{\cv{0}}{} is the \emph{root} of the directed acyclic graph \ensuremath{G}.\label{item:difference_root}
        \item For each vertex $\ensuremath{\cv{i}} \in \ensuremath{V}$ and $\ensuremath{\cv{j}} \in \ensuremath{V}$ such that \ensuremath{\cv{j}}{} is the \emph{parent} of \ensuremath{\cv{i}}{}, compute \ensuremath{\cSi = \dSi}{} where \ensuremath{\cli = \dli}{}.\label{item:difference_node}
        \item For each vertex $\ensuremath{\cv{i}} \in \ensuremath{V}$ compute \ensuremath{\cti = \dti}{} and \ensuremath{\cxi = \dxi}{}.
        \item For each edge \ensuremath{(\cvi, \cvj) \in \cE}, compute \ensuremath{\crij = \dr{\cti}{\clj}}{} and \ensuremath{\cyij \sample \dyij}{}.\footnote{We implicitly assume that the PRF output space and the symmetric encryption key space have the same distribution. In alternative, \crr{ij}{} can be used as randomness of key generation algorithm \pcalgostyle{Gen}{}.}
      \end{enumerate}
      Finally, the algorithm returns the public mapping \ensuremath{\Pub : \cV \cup \cE \to	\bin^{*}}{} and the secret mapping \ensuremath{\Sec : \cV \to \bin^\secpar \times \bin^\secpar}{}, defined as:
      \begin{gather*}
        \ensuremath{\Pub : \cvi \mapsto \cli \qquad \Pub : (\cvi, \cvj) \mapsto \cyij} \\
        \ensuremath{\Sec : \cvi \mapsto (\cSi, \cxi)}
      \end{gather*}
    \item[$\pcalgostyle{Derive}{}(\ensuremath{G}{}, \pcalgostyle{Pub}{}, v_i, v_j, S_i)$:] On input a directed acyclic graph \ensuremath{\cG = (\cV, \cE)}{}, a public mapping \pcalgostyle{Pub}{}, two nodes $v_i, v_j \in \ensuremath{V}$, and a seed $S_i$, the algorithm proceeds as follows:
      \begin{enumerate}
        \item If there is no path from \ensuremath{\cv{i}}{} to \ensuremath{\cv{j}}{} in \ensuremath{G}{}, return $\bot$;
        \item If $i = j$, retrieve \ensuremath{\cl{i}}{} from \pcalgostyle{Pub}{} and return \ensuremath{\cxj = \dxi}{};
        \item Otherwise, compute \ensuremath{\cti = \dti}{} and set $\bar{i} = i$ and $t_{\bar{i}} = t_i$; then
          \begin{enumerate}
            \item Let $\bar{j}$ be the successor of $\bar{i}$ $\text{in}$ the path from \ensuremath{\cv{i}}{} to \ensuremath{\cv{j}}{}. \label{itm:derive}
            \item Retrieve $\cl{\bar{j}}$ and $\cy{\bar{i}\bar{j}}$ from \pcalgostyle{Pub}{}
            \item Compute $\crr{\bar{i}\bar{j}} = \fash_{\ct{\bar{i}}}{(10 \concat \cl{\bar{j}})}$ and $\ct{\bar{j}} \concat \cx{\bar{j}} = \dec_{\crr{\bar{i}\bar{j}}}{(\cy{\bar{i}\bar{j}})}$.
            \item Set $\bar{i} = {\bar{j}}$ and $\ct{\bar{i}} = \ct{\bar{j}}$.
            \item If $\bar{j} = j$ then return $\ensuremath{\cx{j}}$; otherwise repeat from \Cref{itm:derive}.
          \end{enumerate}
      \end{enumerate}
  \end{description}
\end{construction}

The proposed key assignment scheme is entirely deterministic.
In particular, it differs from the design of Atallah \emph{et al.} at the~\Cref{item:difference_root,item:difference_node} of the \pcalgostyle{Set}{} algorithm in~\Cref{const:dka}.
The original key assignment scheme draws the values \ensuremath{\cl{i}}{} and \ensuremath{\cS{i}}{} (respectively, \ensuremath{\cl{0}}{} and \ensuremath{\cS{0}}) at random.
In our case, instead, we deterministically derive them from the identifier \ensuremath{\cv{i}}{} of the node and from the secret information \ensuremath{\cS{j}}{} of its \emph{parent} \ensuremath{\cv{j}}{} (respectively, from the seed \ensuremath{\cS{}}{}).

\input{complextity_DHKA.tex}

\begin{remark}
  At first glance, it might seem that fixing the randomness of the \pcalgostyle{Set}{} algorithm of the HKA by Atallah \emph{et al.}~\cite{atallah:2009:dek:1455526.1455531} is sufficient to enforce its determinism.
  We remark here that such a solution, alone, does not guarantee this result.
  When we fix the randomness of the \pcalgostyle{Set}{} algorithm of the HKA we are implicitly fixing an ordering on the sampling of the secret values \ensuremath{\cS{i}}{} of each node \ensuremath{\cv{i}}{}:
  Sampling at random \ensuremath{\cS{i}}{} before \ensuremath{\cS{j}}{}, as opposed to sampling \ensuremath{\cS{j}}{} before \ensuremath{\cS{i}}{}, will result in different secret values assigned to each node.
  For this reason, the HKA with fixed randomness would also require additional public information about the ordering of the nodes of the hierarchy.
  Our DHKA, instead, deterministically generates the secret values according to the structure of the hierarchy and not to any ordering of its nodes.
  This approach allows us to design a deterministic scheme that does not require any additional public information and that, furthermore, can take the determinism into account to reduce the amount of encrypted information stored on the edges of the hierarchy.
 
 
 
\end{remark}


We conclude this section by establishing the following result.
\begin{theorem}\label{th:d_key_ind}
  Let \ensuremath{\set{\fash_{k}}_{k \in \ensuremath{\mathcal{K}}_\secpar}}{} and $\ensuremath{\mathcal{E}}{} = (\pcalgostyle{Gen}{}, \enc, \dec{})$ be respectively a pseudorandom function family and a symmetric encryption scheme.
  If \ensuremath{\set{\fash_{k}}_{k \in \ensuremath{\mathcal{K}}_\secpar}}{} is pseudorandom (\Cref{def:prf}) and \ensuremath{\mathcal{E}}{} is semantically secure (\Cref{def:enc-def}), then the DKHA scheme $\Pi$ from \Cref{const:dka} is key indistinguishable.
\end{theorem}
\begin{proof}
 \input{dhka_proof.tex}
\end{proof}
\section{Handling Dynamic Changes to a Deterministic Key Assignment Access Hierarchy}\label{sec:dynamic_changes}

This section details how to handle dynamic changes to the access hierarchy (\emph{e.g.}, insertion of a node, or deletion of an edge) of our deterministic key assignment scheme of~\Cref{sec:deterministic_wallets_through_dynamic_and_efficient_key_management} and, in turn, within Arcula, our hierarchical deterministic wallet of~\Cref{sec:arcula}.

Handling dynamic changes to the access hierarchy of the DHKA requires us to consider two problems.
First, how to correctly enforce the hierarchy after the modification (\emph{e.g.}, preventing a node from accessing a subtree after an edge to that subtree is removed);
second, how to deal with modifications to the structure of \ensuremath{G}{} that change the path from the root to any node \ensuremath{\cv{i}}{} along which we deterministically derive the secret values \ensuremath{\cS{i}}{} (\emph{e.g.}, removing the parent of a node).
We solve these problems through the following strategies.
First, we modify the graph \ensuremath{G}{} by adding an explicit root node to it, \ensuremath{\cv{R}}{}, such that there exists an edge between \ensuremath{\cv{R}}{} and any \emph{root} node of \ensuremath{G}{} (\emph{i.e.}, any minimal node in a topological ordering of \ensuremath{G}{}).
More in details, we define $\ensuremath{G'} = (\ensuremath{V}{} \cup \set{\ensuremath{\cv{R}}}, \ensuremath{E}{} \cup \set{(\ensuremath{\cv{R}}, \ensuremath{\cv{i}}) \mid \ensuremath{\cv{i}} \text{ has no predecessors in \ensuremath{G}}})$.
It is easy to prove that both $\ensuremath{G}{}$ and \ensuremath{G'}{} define equivalent access hierarchies.

Next, we associate an additional identifier, that we call \emph{version}, to each node by including it in its label.
Let $\pcalgostyle{Ver}{}: \ensuremath{V} \rightarrow \NN$ be a public mapping associating an integer $\ensuremath{\cw{i}}{} \in \NN$ to any node $\ensuremath{\cv{i}}{} \in \ensuremath{V}$.
Every node \ensuremath{\cv{i}}{} initially starts from version $w_i = 0$, and we modify~\Cref{item:difference_root,item:difference_node} of~\Cref{const:dka} to account for it when deriving the node label \ensuremath{\cl{i}}{}:
\begin{align*}
  \ensuremath{\cl{i}} &= \ensuremath{\ensuremath{\cv{i}} \concat \ensuremath{\cw{i}}}{}
\end{align*}
Every time we modify the graph \ensuremath{G'}{} in such a way that it would require updating the secret of a node \ensuremath{\cv{i}}{}, we do so by updating its version \ensuremath{\cw{i}}{}, deterministically computing its new label \ensuremath{\cl{i}}{}, and, in turn, its new secret \ensuremath{\cS{i}}{}.

In the remainder of this section, we leverage the version associated to each node to perform a \emph{rekey} procedure, defined as follows for every node \ensuremath{\cv{h}}{} and for every node \ensuremath{\cv{p}}{} such that \ensuremath{\cv{p}}{} is the parent of \ensuremath{\cv{h}}{} in \ensuremath{G'}{}.
\rekey{}

Finally, we deal with the dynamic modifications of the graph:
\begin{description}
  \item[Deletion of an edge:] Let \ensuremath{(\cvi, \cvj) \in \cE}{} be the edge that is to be removed from \ensuremath{G'}{}.
    Our goal is twofold:
    First, to prevent \ensuremath{\cv{i}}{} from accessing the cryptographic keys of \ensuremath{\cv{j}}{}.
    Second, to make sure that if the deletion of the edge changes the derivation path from the root \ensuremath{\cv{R}}{} of the hierarchy to \ensuremath{\cv{j}}{}, then the deterministic generation of the secret \ensuremath{\cS{j}}{} changes accordingly.
    We begin by tackling this last problem.
    Let \ensuremath{\cv{p}}{} be the parent node of \ensuremath{\cv{j}}{} in \ensuremath{G'}{}.
    If $\ensuremath{\cv{i}}{} = \ensuremath{\cv{p}}{}$ and if there is no other edge $(\ensuremath{\cv{p'}}, \ensuremath{\cv{j}}{}) \in \ensuremath{E}$ (\emph{i.e.}, there does not exist another predecessor of \ensuremath{\cv{j}}{} that is a candidate to become its new parent), then the deletion of the edge \ensuremath{(\cvi, \cvj) \in \cE}{} results in disconnecting of \ensuremath{\cv{j}}{} from the access hierarchy.
    In that case, we add a connecting edge $(\ensuremath{\cv{R}}{}, \ensuremath{\cv{j}}{})$ to \ensuremath{G'}{} that creates a single-hop path from the root to \ensuremath{\cv{j}}{} and allows the deterministic key derivation of its secret \ensuremath{\cS{j}}{}.
    We note that the addition of this edge does not modify the access hierarchy, \emph{i.e.} it does not allow \ensuremath{\cv{j}}{} to derive the secrets of any node that was not previously between its descendants $\ensuremath{Desc}{(\ensuremath{\cv{j}}{})}$.

    Next, we prevent \ensuremath{\cv{i}}{} from accessing the cryptographic keys of \ensuremath{\cv{j}}{} by performing the \emph{rekey} procedure for each node $\ensuremath{\cv{h}}{} \in \ensuremath{Desc}{(\ensuremath{\cv{j}})}$ (this includes \ensuremath{\cv{j}}{} as well)
  \item[Deletion of a node:] The deletion of any node \ensuremath{\cv{i}}{} corresponds to first removing all the incoming and outgoing edges of \ensuremath{\cv{i}}{} through the procedure specified above.
    Then, to removing the public and secret information associated with \ensuremath{\cv{i}}{} from the \pcalgostyle{Pub}{}, \pcalgostyle{Sec}{}, and \pcalgostyle{Ver}{} data structures.
  \item[Insertion of an edge:] Let \ensuremath{(\cvi, \cvj) \in \cE}{} be the edge to be included into \ensuremath{G'}{}.
    We consider two cases:
    \begin{itemize}
      \item After the addition of the edge $\ensuremath{\cv{i}}$ is the parent of $\ensuremath{\cv{j}}$ in \ensuremath{G'}{}.
        As before, we perform the \emph{rekey} procedure for each node $\ensuremath{\cv{h}}{} \in \ensuremath{Desc}{(\ensuremath{\cv{j}})}$ to update their secret values and to allow the deterministic derivation.
       
      \item Otherwise,
        compute \ensuremath{\crij = \dr{\cti}{\clj}}{}, \ensuremath{\cyij \sample \dyij}{}, and augment \pcalgostyle{Pub}{} to contain the mapping $(\ensuremath{\cv{i}}, \ensuremath{\cv{j}}) \mapsto \ensuremath{\cy{ij}}$.
    \end{itemize}
  \item[Insertion of a new node:] Let \ensuremath{\cv{i}}{} be the node to insert, together with a set of new edges in and out of it.
    Let \ensuremath{\cv{j}}{} be the parent of \ensuremath{\cv{i}}{}.
    We begin by computing a deterministic public label \ensuremath{\cli = \dli \concat \cw{i}}{} (where $\ensuremath{\cw{i}}{} = 0$) and a deterministic secret value \ensuremath{\cSi = \dSi}{};
    then, we compute \ensuremath{\cki = \fash_{\cSi}(01 \concat \cli)}{} and we augment \pcalgostyle{Pub}{} with the mapping $\ensuremath{\cv{i}} \mapsto \ensuremath{\cl{i}}$, \pcalgostyle{Sec}{} with the mapping $\ensuremath{\cv{i}} \mapsto (\ensuremath{\cS{i}}, \ensuremath{\cx{i}})$, and \pcalgostyle{Ver}{} with the mapping $\ensuremath{\cv{i}} \mapsto 0$.
    Finally, we proceed to insert the edges one by one using the edge insertion procedure specified above.
  \item[Key Replacement:] To replace the cryptographic key \ensuremath{\cx{i}}{} associated to any node \ensuremath{\cv{i}}{}, we perform the \emph{rekey} procedure for each node $\ensuremath{\cv{h}}{} \in \ensuremath{Desc}{(\ensuremath{\cv{i}})}$
\end{description}

This approach allows our deterministic key assignment scheme to handle dynamic changes to its access hierarchy and requires the manager of the key assignment (\emph{e.g.}, a crypto-currencies exchange) to keep track of the version of the nodes stored within the \pcalgostyle{Ver}{} mapping in addition to the structure of the graph \ensuremath{G}{}.
Because of the determinism of our scheme, every change to a node \ensuremath{\cv{j}}{} also propagates to all its descendants.
As an example, the replacement of its secret key \ensuremath{\cx{j}}{} requires incrementing its version $\ensuremath{\cw{j}}{}$ in the label \ensuremath{\cl{j}}{} to compute a new secret value and a new cryptographic key.
In turn, this causes the secret information and the cryptographic keys of all its descendants \ensuremath{\cv{i}}{} to change as well (because of the deterministic derivation of the secret values \ensuremath{\cSi = \dSi}{}).
The cost of such an update depends on the particular application and the structure of the access hierarchy.
If we use the DHKA to handle the keys associated with traditional Bitcoin transactions, for example, updating the cryptographic key of a node requires sending its funds to a new address and involves the payment of a transaction fee.
Most of the times, however, we are particularly interested in appending new leaves to the access hierarchy (\emph{e.g.}, to create a new node for an incoming payment).
This operation is a particular case of the insertion of a new node with a single incoming edge.
It never modifies any derivation path, and, as a consequence, it does not perform the \emph{rekey} procedure, it does not change any cryptographic key, and it does not require transactions on the blockchain.
Finally, when we use Arcula to enable the public derivation of addresses, we identify the nodes of the wallet through the master public key \ensuremath{\mathsf{mpk}}{} and a label.
Both the addition of a new node and the update of the label \ensuremath{\cl{j}}{} of an existing node \ensuremath{\cv{j}}{} result in a new Arcula address (\emph{i.e.}, a locking script that contains a new label).
Spending the funds destined to the new address requires a new certificate, signed by the master secret key, that associates the new public key $\ensuremath{\overline{\pk}}_j'$ (obtained from the new intermediate key $x'_h$ after the \emph{rekey} procedure) to the new (or updated) label \ensuremath{\cl{j}}{}.


\section{Further Preliminaries}\label{sec:further_preliminaries}

\subsection{Pseudorandom Function (PRF) Family}\label{sub:pseudorandom_function_prf_family}
Let $\{\ensuremath{\mathcal{K}}_\secpar, \ensuremath{\mathcal{X}}_\secpar, \ensuremath{\mathcal{Y}}_\secpar\}_{\secpar \in \NN}$ be a sequence of sets.
For $\secpar \in \NN$, a PRF family \ensuremath{\set{\fash_{k}}_{k \in \ensuremath{\mathcal{K}}_\secpar}}{} is a set of functions such that $\fash{}_k : \ensuremath{\mathcal{X}}_\secpar \to \ensuremath{\mathcal{Y}}_\secpar$ and each function is evaluable by a deterministic polynomial time algorithm $\fash$, \emph{i.e.}, $\fash(k, \cdot) = \fash_k(\cdot)$.

Let \ensuremath{\mathcal{F}_{\secpar}}{} be the set of all functions from $\ensuremath{\mathcal{X}}_\secpar$ to $\ensuremath{\mathcal{Y}}_\secpar$.
For security, we require that a function randomly sampled from \ensuremath{\set{\fash_{k}}_{k \in \ensuremath{\mathcal{K}}_\secpar}} is indistinguishable by a function randomly sampled from \ensuremath{\mathcal{F}_{\secpar}}{}.
\input{prf_sec_def}
\noindent In this paper, we are interested in PRF families such that $\ensuremath{\mathcal{K}}{}_\secpar = \ensuremath{\mathcal{Y}}_\secpar = \bin^\secpar$.

\subsection{Symmetric Encryption Scheme}\label{subsec:sim-enc}
We follow the definition of symmetric encryption scheme provided by Atallah \emph{et al.}~\cite{atallah:2009:dek:1455526.1455531}.
A symmetric-key encryption scheme $\Pi = (\pcalgostyle{Gen}{}, \enc, \dec{})$ with message space \ensuremath{\mathcal{M}}{} is a triple of polynomial-time algorithm defined in the following way:
    \begin{description}
        \item[\ensuremath{\Gen{(\secparam)}}{}:] The randomized key generation algorithm takes as input a security parameter \secparam{} and outputs a secret key \sk{}.
        \item[\ensuremath{\enc(\sk, m)}{}:] The deterministic (possibly randomized) encryption algorithm takes as input a secret key \sk{}, a message $m \in \ensuremath{\mathcal{M}}{}$, and outputs a ciphertext $c$.
        \item[\ensuremath{\dec(\sk, c)}{}:] The deterministic decryption algorithm takes as input a secret key \sk{}, a ciphertext $c$, and outputs a message $m$.
    \end{description}

For correctness, we require that honestly generated ciphertexts must decrypt correctly.
\input{enc_corr_def.tex}
For security, we are interested in semantic security: It must be infeasible to distinguish between an encryption of a message $m$ from one of a random message.
\input{enc_sec_def.tex}


\section{Hierarchical Deterministic Wallets}\label{sec:hierarchical_deterministic_wallets}
A hierarchical deterministic wallet (HDW) enables a user to securely generate and store the cryptographic keys associated with her coins.
Blockchain-based crypto-systems typically rely on digital signatures and pairs of secret and public signing keys:
Users spend their assets by signing a transaction with the secret key;
the others verify the authenticity of the signature through the public key.
Public keys can be derived from the corresponding secret keys, but not vice-versa.
On a high level, a hierarchical deterministic wallet holds a collection of secret signing keys.

An HDW deterministically generates its keys by starting from an initial seed provided by the user.
As long as the user remembers the seed, she will be able to recover her keys, even in case of wallet loss.
Besides, an HDW also organizes the keys under an access hierarchy, where each element represents a group of users and associated a pair of signing keys to them.
The privileges of users depend on their level in the hierarchy.
Users with higher privileges (\emph{i.e.}, higher in the hierarchy), must be able to derive the keys of users on lower levels and in turn, to sign messages (\emph{i.e.}, transactions) on their behalf.
Users on lower levels, however, should not be able to escalate their privileges along the hierarchy, not even when colluding with others.
Finally, an HDW should also provide an additional fundamental property:
It must be possible to deterministically generate every public key of the wallet by starting from a \emph{master public key} (depending on the user seed), without requiring any secret information in the process.
As we shall see, this requirement enables a set of creative use cases for HDW (\emph{e.g.}, public auditing of blockchain assets, and generation of new keys in untrusted environments).

\subsection{Properties}\label{sub:properties}
In more detail, let \ensuremath{\sk_{i}}{} be the secret signing key of a user \ensuremath{\cv{i}}{} of a hierarchy and let \ensuremath{\pk_{i}}{} be the corresponding public key.
Let \ensuremath{\sk_{j}}{} and \ensuremath{\pk_{j}}{} be, respectively, the secret and public keys associated with a descendant \ensuremath{\cv{j}}{} of \ensuremath{\cv{i}}{} (\emph{i.e.}, a user with lower privileges in the hierarchy).
A hierarchical deterministic wallet shall have the following properties:
\begin{property}[Security against privilege escalation]\label{prp:secret_keys}
 For any set of colluding descendants of \ensuremath{\cv{i}}{} it is computationally infeasible to recover the secret key \ensuremath{\sk_{i}}{} of \ensuremath{\cv{i}}{}.
\end{property}
\begin{property}[Deterministic secret derivation]\label{prp:determinism}
  For each descendant \ensuremath{\cv{j}}{} of \ensuremath{\cv{i}}{}, the secret keys \ensuremath{\sk_{j}}{} is deterministically generated by using the secret information of \ensuremath{\cv{i}}{}.
  If \ensuremath{\cv{j}}{} has the highest privileges in the hierarchy, then her secret information are generated from a user-provided seed.
\end{property}
\begin{property}[Public-key derivation]\label{prp:public_keys}
  The public key \ensuremath{\pk_{j}}{} of each descendant \ensuremath{\cv{j}}{} of \ensuremath{\cv{i}}{} is deterministically generated only using public information;
  the generation process does not require the secret key \ensuremath{\sk_{i}}{} or any other secret information.
\end{property}

The three properties, together, define the ideal hierarchical deterministic wallet.
\Cref{prp:secret_keys} guarantees the security of the wallet:
Colluding users cannot escalate their privileges to recover the secret keys of others higher in the hierarchy.
\Cref{prp:determinism} ensures that all secrets are deterministically generated along the hierarchical path that links the most privileged users to their descendants, and so on.
\Cref{prp:public_keys} requires the public keys to be dynamically derivable without requiring any private information.
As we will see, in the past, this property proved to be particularly hard to achieve while also guaranteeing the security of the underlying wallets.
Nonetheless, it is crucially important as it enables the novel applications of HDW within the blockchain that we discuss in~\Cref{sub:applications}.
Finally, we note that every wallet in which the public derivation property holds, inevitably reveals the relation between the public keys of the wallet, making it impossible to achieve any privacy-related notion, \emph{e.g.}, unlinkability of transactions.
We discuss this issue in~\Cref{sub:transactions_unlinkability}.


\subsection{Applications}\label{sub:applications}
Hierarchical deterministic wallets enable different use cases, inspired by both well established and innovative financial applications that specifically tackle the needs of enterprises, governments, and financial institutions.
Individual users will also find HDW useful, leveraging their increased security and their deterministic reliability and, if they choose so, to achieve unlinkability of their transactions.

We discuss the benefits of HDW for individuals in~\Cref{sub:transactions_unlinkability}.
Here, instead, we focus on the applications of HDW at scale, that target (hundreds of) thousands of customers distributed across the world.

\ifCONF{}
 \begin{description}[style=unboxed,leftmargin=0cm]
\else
 \begin{description}
\fi
  \item[Enterprises:]
  In enterprises (\emph{e.g.}, financial institutions, or exchanges), the hierarchy of a deterministic wallet might reflect the underlying chain of command or the subdivision in regions, departments, and teams.
  It allows managers to distribute funds among different branches and ensure fiscal responsibility. In particular, each branch can manage its funds but are not allowed to spend those of other units.
  The deterministic generation of keys simplifies the management of secrets and guarantees a reliable recovery of the wallet, even in case of catastrophic loss.
  Cryptocurrency exchanges that manage the keys of hundreds of thousands of users might find this feature particularly useful:
  Through the HDW, they generate pairs of keys that take into account the hierarchy of users and then rely on the master seed to handle their recovery.
  Finally, the property of public-key derivation enables enterprises to comply with financial laws and regulations without jeopardizing the security of their infrastructure:
  \emph{E.g.} it allows a (possibly untrusted) auditor to inspect the funds that they hold by starting from the master public key and deriving all the public keys in the wallet without relying on any additional secret information.
  \item[e-commerce:]
  An HDW is distinctly beneficial to an e-commerce marketplace.
  Marketplaces, such as Amazon, typically advertise and sell products to buyers. They also allow third-party vendors to do the same.
Cryptocurrencies could help manage the payment flow to these vendors. When selling an item to a buyer, the marketplace generates a fresh payment address for each crypto-coin that it supports.
  As soon as the buyer transfers the required coins to one of the addresses and the blockchain confirms the transaction, the item gets shipped.
  The generation of fresh payment addresses leverages the properties of public-key derivation:
  Since it does not require any private information, it can take place in an untrusted environment (\emph{e.g.}, a web server exposed to the internet) and allows the e-commerce owner to derive the corresponding secret keys only when actually spending the funds (\emph{e.g.}, by deriving them offline starting from an intermediate key of the wallet).
  Even if an attacker compromises the webserver, he will not discover any secret keys, and thus funds received before the attack remain safe and intact. In addition, public-key derivation allows buyers or auditors to check the authenticity of the payment addresses since anyone can generate them from the public key of the marketplace.
 \item[Decentralized Finance (DeFi):]
  Decentralized Finance has recently started replacing many of the existing traditional financial tools (\emph{e.g.}, loans and futures) with open-source alternatives based on the blockchain and its smart contracts.
  With DeFi, HDW can unleash their full potential:
  The execution of smart contracts, indeed, cannot rely on any secret information as both the source code and the processing inputs are stored in the clear on the public blockchain.
  By combining HDW and public derivation, a DeFi smart contract can autonomously derive the public key of the recipient of a transaction (\emph{e.g.}, a user that will receive interests on a loan, or the employee of a company that will receive a percentage of its shares).
  The process could take place on the blockchain and does not require manual interactions.
  In turn, HDW and DeFi lay the foundations of a modern, democratic, and decentralized financial world.
\end{description}

\subsection{Threats and Security Model}\label{sub:threats_and_security_model}
We divide the set of possible threats to the security of hierarchical deterministic wallet in three security levels that we describe according to increasing requirements of trust.
\ifCONF{}
  \begin{description}[style=unboxed,leftmargin=0cm]
\else
  \begin{description}
\fi
  \item[Untrusted Environment: ] This level is entirely untrusted.
    It refers, for example, to the executing environment of a DeFi smart contract that relies on public key derivation (\Cref{prp:public_keys}) to generate fresh addresses to deliver payments.
  \item[Hot Environment: ]
    This level is semi-trusted.
    At this stage, the users can access their own secret keys and derive those of their descendants.
    An attacker that compromises a user of the hot environment will compromise, in turn, only her descendants in the hierarchy (\Cref{prp:secret_keys}).
  \item[Cold Storage: ]
    This is the most trusted level of the security model, holding the seed used to generate every key within the wallet deterministically.
    It typically corresponds to an offline location (\emph{e.g.}, a hardware token used to instantiate the wallet) that is physically secured (\emph{e.g.}, in a safe).
    An attacker that compromises the cold storage has full access to the wallet and to every asset that it holds.
\end{description}
In~\Cref{sub:arcula_at_a_glance,sec:related_works}, we analyze our construction and the related work under the spotlight of this security model.

\subsection{Arcula at First Glance}\label{sub:arcula_at_a_glance}

\begin{figure*}[tb]
  \centering
  \includegraphics[width=0.8\linewidth]{resources/arcula_glance.pdf}
  \caption{%
    A glance at the deterministic generation of secrets and identity-based public key derivation within Arcula.
    The users $l_1$ to $l_5$ at the bottom of the figure create a hierarchy, encoded as a directed acyclic graph.
    Arcula starts by deriving a pair of master keys $(\ensuremath{\mathsf{msk}}, \ensuremath{\mathsf{mpk}})$ from the seed.
    The users are unequivocally identified by concatenating the master public key \ensuremath{\mathsf{mpk}}{} with their identities (\emph{e.g.}, $l_5$).
    The master secret key \ensuremath{\mathsf{msk}}{} allows the deterministic generation of secrets, so that every secret transitively depends on the initial seed.
    The hierarchical deterministic key assignment at the core of Arcula relies on the \ensuremath{\mathsf{msk}}{} and enables users with higher privileges to derive the secrets of their descendants (\emph{e.g.}, enabling $l_1$ to start from her secret information and derive the secret key $\sk{}_4$ of $l_4$).
    Finally, Arcula associates secret keys to their corresponding identities by providing each user with a certificate signed by the \ensuremath{\mathsf{msk}}{}:
    $\ensuremath{\mathsf{cert}}_{4}$, \emph{e.g.}, associates $l_4$ with the secret key $\sk_{4}$.
    This approach enables Arcula to flexibly add new users to the hierarchy without requiring secret information.
    The user $l_5$ was dynamically added to the hierarchy, and her public key was obtained through identity-based derivation, but she still does not have any secret information associated with her.
    This means that she can receive funds (\emph{e.g.}, on the blockchain) and that the certificate and her secret information will only be required when she will spend them.
  }\label{fig:resources/arcula_glance}
\end{figure*}

\Cref{fig:resources/arcula_glance} provides an overview of the design of Arcula, our hierarchical deterministic wallet.
Arcula starts from the seed to deterministically generate a master pair of secret and public keys $(\ensuremath{\mathsf{msk}}, \ensuremath{\mathsf{mpk}})$.
After the initial instantiation, the seed and the master secret key can be safely moved to cold storage.
The master public key uniquely identifies the wallet and will be used in the public key derivation process.
In more detail, Arcula generates the public key of $i$-th user of the hierarchy by concatenating the master public key $\ensuremath{\mathsf{mpk}}$ and her identity $\ensuremath{\cl{i}}$ (\emph{e.g.}, a numerical index or a bit string).
As a result, public-key derivation in Arcula can be executed, by design, in any untrusted environment.
The master secret key $\ensuremath{\mathsf{msk}}$ allows, instead, to deterministically generate the secret keys $\ensuremath{\sk_{i}}$ corresponding to the users of the hierarchy.
In particular, Arcula generates the secret keys by relying on deterministic hierarchical key assignment:
A provably secure cryptographic scheme through which we assign a derivation key to every user of the hierarchy, that, in turn, they will use to derive their own secret key and those of their descendants.
The private key generation should be executed in the context of the hot environment, as compromising a single user will lead to compromising every descendant.
Finally, Arcula explicitly associates secret keys to their corresponding identity-based public keys through a certificate $\ensuremath{\mathsf{cert}}_i$, signed by the master secret key $\ensuremath{\mathsf{msk}}$, that links the public identity $\ensuremath{\cl{i}}$ (top of~\Cref{fig:resources/arcula_glance}) to the secret key \ensuremath{\sk_{i}}{} generated by the deterministic key assignment scheme (bottom of~\Cref{fig:resources/arcula_glance}).

The identity-based approach that we realized with Arcula provides several advantages:
First, it solves the problem of distributing a public key for each user of the hierarchy and of associating, off the blockchain, to the identity of an individual.
In addition, it allows for generating an unbounded number of addresses for receiving transactions.
On the other hand, Arcula relies on certificates signed by the master secret key to associate the secret key of a user with their identity, to which the transaction was addressed.
The users only require these certificates when they sign a transaction for the first time:
This means that their creation can be delayed until that moment and that it can happen entirely offline.

\section{Arcula in the real world}\label{sec:arcula_in_the_real_world}
With Arcula, we design a future-proof HDW that brings identity-based signatures to the blockchain item and that, at the same time, is also suitable to the most widely used crypto-systems of today.
We aim to join theory and practice, to create a wallet that fulfills our current and future needs in the crypto-coins space.

For this reason, we constrain our design with as few cryptographic assumptions as possible.
Arcula works with any existentially unforgeable signature scheme and only requires the verification of a signature on an arbitrary message (\emph{i.e.}, the certificate that associates the signing key to their corresponding user).
This design makes it immediately compatible with the Ethereum blockchain, which implements a Turing-complete language, and with all the forks based on Bitcoin that allow the signature verification of arbitrary messages (\emph{e.g.}, Bitcoin Cash).
The original Bitcoin implementation, instead, does not allow such operation (in fact, it goes as far as disabling the operations of string concatenation and integer multiplication that, initially, it allowed).

In this section, we show how Arcula performs in the real world, and we show how to spend and receive funds, out of the box, on the Bitcoin Cash blockchain.
Next, we discuss the modifications that would make it compatible with the original Bitcoin protocol and how it is possible to disable public derivation to obtain unlinkability of transactions.

\subsection{Technical Implementation}\label{sub:implementation}
Our open-source implementation of Arcula is available online.\footnote{
\ifFULL{}
  Available at \url{https://github.com/aldur/Arcula}.
\else
  Available at \url{https://doi.org/10.5281/zenodo.2791637}.
\fi
}
We instantiate the underlying DHKA leveraged by Arcula with the pseudorandom function $\fash_{k}(x) = \hash(k \concat x)$ (where $\hash{}(x)$ is the hash function $\text{SHA3-256}(x)$) and the authenticated AES256 with Galois/Counter Mode (GCM) as the symmetric encryption scheme.
We generate a hierarchal deterministic wallet based on the tree defined in BIP43 and BIP44~\cite{marek2014bip43,marek2014bip44}, where the keys to different crypto-coins correspond to different subtrees, and each branch of the subtrees is a chain associated to a single account that contains multiple receiving addresses.
We obtain an initial seed \ensuremath{\cS{}}{} of $512$ bits by following the specification of BIP39~\cite{marer2013bip39} that generates a seed from a random mnemonic sequence.
We generate the wallet that we use in our tests by fixing the randomness of the mnemonic generation process to the result of the operation $\hash(\text{\texttt{correct horse battery staple}})$.

\subsection{Arcula in Bitcoin Cash}\label{sub:bitcoin_and_bitcoin_cash}

A Bitcoin transaction is a cryptographically signed statement that transfers some coins from a sender to a receiver.
The sender of the coins signs the transaction through her secret key to spend, in turn, the coins destined to the corresponding public key.
Every transaction specifies a locking and an unlocking script.
These scripts respectively state the necessary conditions to spend, in a future transaction, the coins being transferred (\emph{i.e.}, their locking condition) and provide the information required to redeem them (\emph{i.e.}, to unlock them as a result of a past transaction).
Both scripts are written through a stack-based language that allows simple mathematical operations, stack manipulations, and enables simple cryptographic primitives (\emph{i.e.} computing the result of a hash function and verifying a signature).

A typical Bitcoin locking script specifies the address of the receiver (usually through the hash of its public key) and requires him to provide a valid signature to redeem the coins being transferred.
More in detail, the locking and unlocking scripts of a standard Bitcoin transaction are defined as follows.
Uppercase monospace words indicate operations of the Bitcoin scripting language, while angular brackets enclose variable inputs.
\begin{description}
  \item[Locking: ] \texttt{OP\_DUP}{} \texttt{OP\_HASH160}{} \texttt{<$\hash{(\pk)}$>} \texttt{OP\_EQUALVERIFY}{} \texttt{OP\_CHECKSIG}{}
  \item[Unlocking: ] \texttt{<$\sigma$>} \texttt{<\pk{}>}
\end{description}
Together, these scripts ensure that the public key \pk{} provided in the unlocking script is the pre-image of the hash $\hash(\pk)$ (the Bitcoin address) contained in the locking script;
then, verify the validity of the transaction signature $\sigma$ under the public key \pk{}.

In Arcula, instead, we identify the nodes of our wallet \ensuremath{\cv{i}}{} according to the master public key $\ensuremath{\mathsf{mpk}}{} = \ensuremath{\overline{\pk}}_0$ and to their public label \ensuremath{\cl{i}}{}.
For this reason, an Arcula address is simply the concatenation of the byte representations of these values that we encode in the locking script.
The unlocking script, on the other hand, contains the certificate $\ensuremath{\cert_{i}} \sample \pcalgostyle{Sign}_{\ensuremath{\Sigma}}(\ensuremath{\overline{\sk}}_0, (\ensuremath{\overline{\pk}}_i, \ensuremath{\cl{i}}{}))$ and associating the signing public key \ensuremath{\pkX_{i}}{} to the node \ensuremath{\cv{i}}{} with label \ensuremath{\cl{i}}{}, and a signature $\sigma$ of the transaction verifiable through the public signing key \ensuremath{\pkX_{i}}{}.
With Arcula, the locking and the unlocking scripts respectively become:
\begin{description}
  \ifFULL{}
  \item[Locking: ] \texttt{OP\_DUP}{} \texttt{OP\_TOALTSTACK}{} \texttt{<\ensuremath{\cl{i}}{}>} \texttt{OP\_CAT}{} \texttt{<\ensuremath{\mathsf{mpk}}{}>} \texttt{OP\_CHECKDATASIGVERIFY}{} \\
  \texttt{OP\_FROMALTSTACK}{} \texttt{OP\_CHECKSIG}{}
\else
  \item[Locking: ] \texttt{OP\_DUP}{} \texttt{OP\_TOALTSTACK}{} \texttt{<\ensuremath{\cl{i}}{}>} \texttt{OP\_CAT}{} \texttt{<\ensuremath{\mathsf{mpk}}{}>} \texttt{OP\_CHECKDATASIGVERIFY}{} \texttt{OP\_FROMALTSTACK}{} \texttt{OP\_CHECKSIG}{}
\fi
  \item[Unlocking: ] \texttt{<$\sigma$>} \texttt{<$\ensuremath{\cert_{i}}$>} \texttt{<\ensuremath{\pkX_{i}}{}>}
\end{description}
The two scripts:
\begin{inlinelist}
\item Verify that the certificate $\ensuremath{\cert_{i}}$ is a valid signature of the message $(\ensuremath{\pkX_{i}}, \ensuremath{\cl{i}})$ under the master public key \ensuremath{\mathsf{mpk}}{};
\item verify the validity of the transaction signature $\sigma$ under the signing public key \ensuremath{\pkX_{i}}{}.
\end{inlinelist}
In particular, the locking script checks the validity of the certificate through the operation \texttt{OP\_CHECKDATASIGVERIFY}{}, which allows the stack-based scripting language to validate a signature of an arbitrary message (the concatenation of $\ensuremath{\mathsf{mpk}}$ and \ensuremath{\cl{i}}{} obtained through the operation \texttt{OP\_CAT}{}).
The scripting language of the original Bitcoin does not implement such an operation yet.
Nonetheless, a significant portion of the Bitcoin community believes that its adoption would provide substantial benefits to the entire system, \emph{e.g.}, by enabling third-parties to store and verify independent messages on the blockchain.
For this reason, many Bitcoin forks (Bitcoin Cash, Bitcoin Ultimate, and Blockstream, to name a few), that aim at modernizing the protocol and at improving the stack-based language used in scripts, now implement this operation.

In our experiments, we focus, as an example, on Bitcoin Cash---the sixth cryptocurrency by market capitalization at the time of writing---and we evaluate Arcula on its test blockchain.
We first create a transaction\footnote{The transcripts of the transactions are available, respectively, at \url{https://bit.ly/2UI62tt} and \url{https://bit.ly/2UoQNGI}.} that locks $0.5$ BCH (the Bitcoin Cash crypto-coin) to a node of our wallet of~\Cref{sub:implementation}, identified through the master public key \ensuremath{\mathsf{mpk}}{} (also in the locking script) and the integer label $3$.
Next, we redeem the coins through a second transaction that provides the transaction signature $\sigma$ computed using the signing key \ensuremath{\skX_{i}}{}, an appropriate certificate \ensuremath{\cert_{i}}{} signed by the master secret key, and the public signing key \ensuremath{\pkX_{i}}{}.
We create both the signature and the certificate through the ECDSA signatures scheme on the \texttt{secp256k1} elliptic curve used in Bitcoin, and we encode the integer label \ensuremath{\cl{i}}{} of the node \ensuremath{\cv{i}}{} with $4$ bytes.

\begin{table}[tpb]
  \centering
  \small
  \caption{The script bytes sizes of a transaction to a standard Bitcoin address and to an Arcula address.}\label{tab:script_sizes}
  \begin{tabular}{c c c c}
    \toprule
    Address type & Locking Script & Unlocking Script & Total \\
    \midrule
    Standard   & $24$      & $106$      & $130$ \\
    Arcula    & $43$      & $179$      & $222$ \\
    \bottomrule
  \end{tabular}
\end{table}

\subsection{Transaction Costs}\label{sub:transaction_costs}
To study the costs of Bitcoin transactions to an Arcula address, we analyze the amount of storage that they require on the blockchain.
Every Bitcoin transaction devolves a small amount of fees to the system to incentive its inclusion in the next block of the chain.
Fees are usually measured in coins per byte, and, for this reason, the size of a transaction on the Bitcoin wire protocol is directly related to the amount of fees that it should pay to be included in the blockchain.
In particular, the length of the locking and unlocking scripts influences directly the final transaction cost.
\Cref{tab:script_sizes} compares the sizes, in bytes, of the locking and unlocking scripts of standard Bitcoin transactions and to an address of our wallet.
Every operation of the stack-based scripting language is encoded with a single byte;
a standard Bitcoin address is the result of a hash function that outputs $20$ bytes;
the ECDSA signature and the public key in the unlocking script require, respectively, $73$ and $33$ bytes.
By summing these values up, we find that the locking script of a transaction to a standard Bitcoin address is $24$ bytes long ($4$ script operations plus the receiver address) while the unlocking scripts take $106$ bytes (the ECDSA signature and its associated public key).
In Arcula, on the other hand, the locking script encodes $6$ operations, the identifier of a node (that we encode with $4$ bytes), and the cold storage public key ($33$ bytes, as opposed to its $20$ bytes hash), for a total of $43$ bytes.
The unlocking script, instead, contains two ECDSA signatures (one for the transaction and one for the certificate) and the signing public key;
as a result, it is $179$ bytes long.
Overall, the size of the locking and unlocking scripts for a transaction to an Arcula address is $222$ bytes, $70\%$ longer than the standard address counterparts.

In particular, the Bitcoin users aim at minimizing the size of the locking script, as its associated fees will be paid by the sender of the transaction, \emph{e.g.}, the customer of an online service, and the service providers usually aim at minimizing these costs.
Bitcoin solves this issue through the pay to script hash mechanism, proposed in BIP16~\cite{andresen2012bip16}, that reduces the size of any locking script to a constant at the cost of longer unlocking scripts.
The intuition is that instead of specifying the full locking script, the users can constrain the coins of a transaction by locking them to the hash of the original script;
then, in the unlocking script, they can provide both the pre-image of the hash, \emph{i.e.}, the full locking script, and its required inputs.
This approach brings several advantages.
First, any locking script can be expressed with a constant byte size that results in a fixed cost for the sender.
Second, it hides the details of the locking script until the users reveal the pre-image of the hash in an unlocking script, \emph{i.e.} when they redeem the coins sent by the transaction.
Finally, the Bitcoin protocol proposes a way to encode the pay to script hash locking scripts into standard Bitcoin addresses, so that exchanging transactions of this kind is entirely transparent to the software used by the sender.
By using the pay to script hash mechanism, any user can send a transaction to an Arcula address through her favorite Bitcoin wallet, in a transparent way that does not require any specific software modification to it.
More in details, an Arcula pay to script hash transaction is defined as follows, where the script that we input to the hash function is the locking script of a transaction to an Arcula address that we have seen before:
\begin{description}
\ifFULL{}
  \item[Script: ] \texttt{OP\_DUP}{} \texttt{OP\_TOALTSTACK}{} \texttt{<\ensuremath{\cl{i}}{}>} \texttt{OP\_CAT}{} \texttt{<\ensuremath{\mathsf{mpk}}{}>} \texttt{OP\_CHECKDATASIGVERIFY}{} \\
  \texttt{OP\_FROMALTSTACK}{} \texttt{OP\_CHECKSIG}{}
\else
  \item[Script: ] \texttt{OP\_DUP}{} \texttt{OP\_TOALTSTACK}{} \texttt{<\ensuremath{\cl{i}}{}>} \texttt{OP\_CAT}{} \texttt{<\ensuremath{\mathsf{mpk}}{}>} \texttt{OP\_CHECKDATASIGVERIFY}{} \texttt{OP\_FROMALTSTACK}{} \texttt{OP\_CHECKSIG}{}
\fi
  \item[Locking: ] \texttt{OP\_HASH160}{} \texttt{<\hash{(Script)}>} \texttt{OP\_EQUAL}{}
  \item[Unlocking: ] \texttt{<$\sigma$>} \texttt{<$\ensuremath{\cert_{i}}$>} \texttt{<\ensuremath{\pkX_{i}}{}>} \texttt{<Script>}
\end{description}

The pay to script hash mechanism reduces to $22$ bytes ($2$ operations and a $20$ bytes hash) the size of the locking script and, equivalently, the amount of fees that users have to spend to send funds to an Arcula address.
The size of the unlocking script, on the other hand, affects the fees that the users of Arcula need to pay when spending their coins.
In particular, when using pay to script hash, this amount of fees is slightly larger than the one required for a traditional Bitcoin transaction.
In many cases, however, the benefits that arise with Arcula justify the increase in the transaction cost.
An e-commerce marketplace, as an example, can leverage Arcula's public key derivation to dynamically derive new addresses (\emph{e.g.}, one for each product of her catalog) in an entirely untrusted environment (\emph{e.g.}, an online web-server) while keeping every signing keys at rest in trusted storage.
As a result, the provider obtains the flexibility of handling incoming payments on dynamic addresses and minimizes the risk of losing the coins associated with them.
When compared with the financial costs associated with this risk, the additional fees required by the Arcula transactions are negligible.
The public key derivation also brings other significant benefits.
Many financial regulations require, indeed, companies to be accountable for all the payments that they receive.
With Arcula, an auditor can reach this goal by merely inspecting the blockchain while looking for any address that contains the master public key \ensuremath{\mathsf{mpk}}{} that identifies the company.
Finally, many enterprises leverage $m$-of-$n$ signatures, where redeeming a transaction requires $m$ valid signatures among $n$ authorized public keys.
Their goal is to enforce the internal structure of the company (\emph{e.g.}, so that either managers or employees can sign transactions) or to divide the responsibility of spending coins evenly.
The unlocking scripts of $m$-of-$n$ transactions have considerable size:
They contain $m$ signatures and $n$ public keys.
By leveraging Arcula and enforcing an appropriate hierarchy that reflects their internal structure, these companies could reduce the size of the unlocking scripts to only two signatures (the transaction signature and the certificate) and two public keys (the master and signing public keys).

\subsection{Optimizations and compatibility with Bitcoin}\label{sub:optimizations}
The current implementation of Arcula does not require any modification to the underlying protocols and blockchains.
Nevertheless, we also propose a set of optimizations that, through minimal modifications to these protocols, reduce both the cost of transactions to Arcula addresses and the amount of storage required on the blockchain.
We begin by noting that any authorization certificate \ensuremath{\cert_{i}}{} can be used more than once.

For this reason, the first optimization that we propose is to \emph{cache} the certificate \ensuremath{\cert_{i}}{} as soon as it appears for the first time in an unlocking script.
Then, any subsequent transaction signed by \ensuremath{\skX_{i}}{} could specify a pointer to the certificate (\emph{e.g.}, with a shorter hash) instead of the certificate itself and, in turn, reduce the size of the unlocking script.
As an example, by pointing to the certificate with a $20$ bytes hash, we would reduce the size of the Arcula locking and unlocking scripts to be roughly $20$ bytes longer than their traditional counterparts.
Implementing this optimization requires a new operation in the scripting language to retrieve the certificate from the cache and to verify its validity.
On the other hand, if we allow for more complex modifications, we can change the signature scheme of the underlying protocols to reduce these space requirements to their optimal value further---a single signature per transaction.
Arcula can be implemented with a single signature by leveraging a sanitizable signature scheme~\cite{ateniese2005sanitizable}, \emph{i.e.} a scheme where an authorized party can modify a fraction of the message signed without interacting with the original signer.
The intuition is to combine the certificates with the signatures that authorize transactions:
Now, the certificate of user \ensuremath{\cv{i}}{} that associates her to the signing public key \ensuremath{\pkX_{i}}{} also includes an additional modifiable portion that will be filled with the transaction details.
To spend their coins, the users leverage their sanitizable key to replace the blank transaction with the details that they intend to sign.\footnote{The sanitizable keys can be hierarchically deployed by leveraging a second instance of DHKA.}
In their work, Ateniese \emph{et al.}~\cite{ateniese2005sanitizable} show how to construct a sanitizable signature scheme by combining any signature scheme with a chameleon hash function.
This construction would allow Arcula to be used with the traditional Bitcoin blockchain by implementing the sanitizable signatures on top of the ECDSA signature scheme that it already uses.
In addition, it would not change the expressiveness of the Bitcoin scripting language:
Instead of enabling the verification of signatures on arbitrary messages, it would simply extend the signature verification protocol to account for the certificate embedded in the sanitized signatures.

\subsection{Unlinkability of Transactions}\label{sub:transactions_unlinkability}
Individual users of hierarchal deterministic wallets are typically not interested in public key derivation.
Differently from enterprises and e-commerce marketplaces, for instance, they simply rely on HDW to recover their keys in case of hardware failure or catastrophic loss.
On the other hand, they are often interested in achieving unlinkability of their transactions, \emph{i.e.} in making sure that multiple transactions sent to their wallet can not be correlated together by an observer that passively monitors the blockchain.
In other words, they typically desire to trade the derivation of public keys in an untrusted setting for the ability to receive payments on uncorrelated pseudonyms.

Arcula allows them to reach this goal.
In more detail, these users can ignore the identity-based public key derivation that Arcula provides (and its associated master public key \ensuremath{\mathsf{mpk}}) and identify the nodes of the wallet with their public signing key \ensuremath{\pkX_{i}}{}.
On the blockchain, they can receive standard transactions (costing standard transaction fees) on the public signing key \ensuremath{\pkX_{i}}{} and then sign new transactions to redeem the coins through the corresponding private key \ensuremath{\skX_{i}}{}.
We generate this pair of keys through a DHKA scheme that is secure under key indistinguishability.
This means that every public signing key in the wallet is unlinkable from the others, because the DHKA cryptographic keys \ensuremath{\cx{i}}{} that we use as randomness to generate them are, in turn, indistinguishable from random strings of the appropriate length.
As a result, Arcula provides a provably secure alternative to the hardened mode of BIP32:
Individual users can generate as many pseudonyms as they need by branching or deepening the DAG that encodes their hierarchy, and then leverage the DHKA to generate keys and reliably recover them in case of loss.
Note that this modified version of Arcula does not require validation of signatures of arbitrary messages, enabling its usage with any blockchain system, including Bitcoin.

In addition, Arcula also allows users to achieve unlinkability of transactions while maintaining identity-based public key derivation.
The intuition is to use a chain code $c$, private to the environment where we execute the public derivation, to \emph{perturb} the master secret and public keys so that they look uncorrelated from the original keys to a passive observer.
We perform the perturbation once for each node in the wallet.
As a result, we associate them with a set of perturbed pairs of keys, labeled $(\ensuremath{\msk_{i}}, \ensuremath{\mpk_{i}})$, that we use to sign the certificate $\ensuremath{\cert_{i}}$ that associates their public signing key \ensuremath{\pkX_{i}}{} to their identity \ensuremath{\cv{i}}{}.
Now, we can address Bitcoin payments for the node \ensuremath{\cv{i}}{} to the $i$-th perturbation \ensuremath{\mpk_{i}}{} of the master public key \ensuremath{\mathsf{mpk}}{}, that is uncorrelated from any other key of the wallet.

More in detail, let \ensuremath{g}{} be a generator of the elliptic curve used in Bitcoin's ECDSA signature scheme.
The master public key is defined as $\ensuremath{\mathsf{mpk}} = \ensuremath{\mathsf{mpk}}_{0} = \ensuremath{\overline{\pk}}_0{} = \cGroupPub{\ensuremath{\overline{\sk}}_0{}}$.
Let $c$ be the secret chain code and let \fash{} be a pseudorandom function.
We create the $i$-th perturbed key \ensuremath{\mpk_{i}}{} of the master public key \ensuremath{\mathsf{mpk}}{} as follows:
\begin{equation*}
  \ensuremath{\mpk_{i}}{} = \cGroupPub{\ensuremath{\overline{\sk}}_0{} + \fash_{c}{(\ensuremath{\cl{i}}{})}} = \cGroupPub{\ensuremath{\overline{\sk}}_0{}} \cdot \cGroupPub{\fash_{c}{(\ensuremath{\cl{i}}{})}} = \ensuremath{\mathsf{mpk}} \cdot \cGroupPub{\fash_{c}{(\ensuremath{\cl{i}})}},
\end{equation*}
where \ensuremath{\cl{i}}{} is the label of node \ensuremath{\cv{i}}{}.
As long as the chain code $c$ is private, this construction ensures the unlinkability of transactions sent to the perturbed addresses~\cite{maxwell2011deterministic}.

In Arcula, we modify the~\Cref{enum:sign_oracle_proof_inner} of \Cref{const:cert-arcula} to sign the certificates $\ensuremath{\cert_{i}} \sample \pcalgostyle{Sign}_{\ensuremath{\Sigma}}(\ensuremath{\msk_{i}}, \ensuremath{\pkX_{i}})$ with the perturbed secret key $\ensuremath{\msk_{i}}{} = \ensuremath{\overline{\sk}}_0{} + \fash_{c}{(\ensuremath{\cl{i}}{})}$.
Note that we remove the label \ensuremath{\cl{i}}{} from the certificate since now every pair of perturbed keys is uniquely associated with precisely one pair of signing keys, and the perturbation already takes into explicit consider the label \ensuremath{\cl{i}}{} of node \ensuremath{\cv{i}}{}.
Finally, we replace the master public key $\ensuremath{\mathsf{mpk}}$ in the locking script with the $i$-th perturbed key \ensuremath{\mpk_{i}}{}, that verifies the certificate \ensuremath{\cert_{i}}{}, as follows:
\begin{description}
  \item[Locking: ] \texttt{OP\_DUP}{} \texttt{OP\_TOALTSTACK}{} \texttt{<\ensuremath{\mpk_{i}}{}>} \texttt{OP\_CHECKDATASIGVERIFY}{} \ifFULL{} \\ \fi{} \texttt{OP\_FROMALTSTACK}{} \texttt{OP\_CHECKSIG}{}
  \item[Unlocking: ] \texttt{<$\sigma$>} \texttt{<$\ensuremath{\cert_{i}}$>} \texttt{<\ensuremath{\pkX_{i}}{}>}
\end{description}
As a result, all the Arcula addresses of the same wallet look uncorrelated when they appear in the locking script of a transaction.
The perturbed private keys \ensuremath{\msk_{i}}{} are effectively equivalent to the original master secret key:
An attacker that compromises any perturbed key can recover the master secret key and compromise the entire wallet by forging new certificates for key pairs that he controls.
For this reason, the perturbed keys shall be kept in cold storage, or better yet, destroyed after the generation of the corresponding certificate.

To conclude, we briefly discuss how to derive, deterministically, the chain code $c$.
We propose to assign a different chain code $c_i$ to each node \ensuremath{\cv{i}}{} of the wallet by running our DHKA a second time:
In this way, an attacker that compromises a node in the hierarchy can only uncover the public identifiers of the nodes in its subtree, but would not gain any knowledge about the others in the hierarchy.
\section{Introduction}\label{sec:Intro}
In recent years, the adoption of blockchain-based crypto-systems grew at an exponential rate.
At their core, these systems create a decentralized and democratic financial world where users exchange their assets without relying on any central authority and where transactions get delivered to the destination in a handful of seconds, by spending cents of a dollar in fees.
For these reasons, these systems attracted the interest of financial operators, banks, (decentralized) exchanges, and e-commerce marketplaces that aim to increase the security and the usability of their systems, reduce their business costs, and prepare for the financial market of the future.
With the adoption of these systems at scale, however, we face a new set of technological and financial hurdles that we have never experienced before:
(1) How to secure the digital assets of a commercial company? (2) How to handle the delegation and separation of responsibilities within the enterprise's chain of command? (3) And how to enable a third-party (\emph{e.g.}, an auditor) to evaluate past transactions of the company, and (4) to gather the list of its assets on the blockchain?

In this work, we aim at solving these challenges, and we focus on hierarchical deterministic wallets.
Similarly to how we keep our coins and our bills in a physical wallet, a blockchain wallet holds all our crypto-assets (\emph{e.g.}, our Bitcoins, Ethers, and other coins).
In particular, wallets hold the cryptographic keys that allow us to spend these coins.
Our goal is to design a wallet that is cryptographically secure and easy to use:
We specifically tackle the use cases of the legacy and future blockchain-based crypto-systems and, in turn, the needs of the large-scale enterprises that rely on them.
The wallet that we aim to design is hierarchical and deterministic.
This means that:
\begin{inlinelist}
\item The users can securely organize their keys in a hierarchy that reflects, for example, the subdivision in departments of a company.
 This way, the managers of a company can spend funds on behalf of their departments, but each department can only spend its own funds.
\item The wallet deterministically generates every cryptographic key by starting from an initial seed (\emph{e.g.}, a pseudorandom sequence derived from a mnemonic phrase).
 As a result, the users can reliably recover all their keys even in the case of total loss (\emph{e.g.}, after a hardware failure or a natural disaster).
\end{inlinelist}

To this end, we present Arcula, a hierarchical deterministic wallet named after the small casket where ancient Romans used to store their jewels.
We build Arcula on a deterministic variation of {\em hierarchical key assignment schemes (HKAs)}, a popular cryptographic primitive that has been studied for more than 20 years.
Arcula implements arbitrarily complex access hierarchies, allows for their dynamic modifications, and can incorporate temporal capabilities into the generation and storage of keys.
In addition, Arcula ties the identities of users to their public signing keys without requiring additional secret information --- bringing to fruition identity-based hierarchical cryptography (\emph{e.g.}, signatures) within the blockchain ecosystem.
Unlike other wallets, Arcula achieves these properties while being formally secure against privilege escalation.
It relies on simple cryptographic primitives and does not depend on any particular digital signature scheme.
As a consequence, Arcula is compatible with any blockchain that enables the verification of signatures on arbitrary messages.
We show its implementation in action in Bitcoin Cash, a fork of the original Bitcoin crypto-system.

The rest of this work is organized as follows.
In~\Cref{sec:hierarchical_deterministic_wallets} we describe the properties of hierarchical deterministic wallets and their applications.
\Cref{sec:related_works} and~\Cref{sec:preliminaries} respectively discuss the related work and introduce the notation and the cryptographic primitives that we use throughout the paper.
\Cref{sec:security_model_of_hierarchical_deterministic_wallet} formalizes the security model of hierarchical deterministic wallets.
\Cref{sec:arcula} and \Cref{sec:arcula_in_the_real_world} describe our design of Arcula and show it in action in the real world.
Lastly,~\Cref{sec:conclusions} concludes the paper.



\section{Preliminaries}\label{sec:preliminaries}

\subsection{Notation}\label{sub:notation}
We use the notation $[n] = \{1,\ldots,n\}$.
Uppercase boldface letters (such as $\rv{X}$) are used to denote random variables, lowercase letters (such as $x$) to denote concrete values, calligraphic letters (such as $\ensuremath{\mathcal{X}}$) to denote sets, and sans serif letters (such as \pcalgostyle{A}{}) to denote algorithms.
Algorithms are modeled as (possibly interactive) Turing machines;
if algorithm \pcalgostyle{A}{} has access to some oracle \ensuremath{\pcalgostyle{O}}{}, we often write $\ensuremath{\mathcal{Q}}_{\ensuremath{\pcalgostyle{O}}{}}$ for the set of queries asked by \pcalgostyle{A}{} to \ensuremath{\pcalgostyle{O}}{}.

For a string $x\in\bin^*$, we let $|x|$ be its length;
$|\ensuremath{\mathcal{X}}|$ represents the cardinality of the set $\ensuremath{\mathcal{X}}$.
When $x$ is chosen randomly in $\ensuremath{\mathcal{X}}$, we write $x \sample \ensuremath{\mathcal{X}}$.
We write $y = \pcalgostyle{A}(x)$ to denote a run of the algorithm \pcalgostyle{A}{} on input $x$ and output $y$;
if \pcalgostyle{A}{} is randomized, $y$ is a random variable and $\pcalgostyle{A}{}(x;r)$ denotes a run of \pcalgostyle{A}{} on input $x$ and (uniform) randomness $r$.
We write $y \sample \pcalgostyle{A}(x)$ to denote a run of the randomized algorithm \pcalgostyle{A}{} over the input $x$ and uniform randomness.
An algorithm \pcalgostyle{A}{} is \emph{probabilistic polynomial-time} (PPT) if \pcalgostyle{A}{} is randomized and for any input $x,r\in\bin^*$ the computation of $\pcalgostyle{A}(x;r)$ terminates in a polynomial number of steps (in the input size).

Throughout the paper, we denote by $\secpar\in\NN$ the security parameter and we implicitly assume that every algorithm takes as input the security parameter. A function $\nu:\NN\rightarrow[0,1]$ is called \emph{negligible} in the security parameter $\secpar$ if it vanishes faster than the inverse of any polynomial in $\secpar$, \emph{i.e.}, $\nu(\secpar)\in \bigO{1/p(\secpar)}$ for all positive polynomials $p(\secpar)$.
We write $\negl$ to denote an unspecified negligible function in the security parameter.

\subsection{Signature Scheme}\label{subsec:signature-scheme}
A signature scheme with message space $\ensuremath{\mathcal{M}}$ is made of the following polynomial-time algorithms.
\begin{description}
  \item[$\pcalgostyle{Keygen}(\secparam)$:] The randomized key generation algorithm takes the security parameter and outputs a secret and a public key $(\sk, \pk)$.

  \item[$\pcalgostyle{Sign}(\sk, m)$:] The randomized signing algorithm takes as input the secret key $\sk$ and a message $m\in\ensuremath{\mathcal{M}}$, and produces a signature $\sigma$.

  \item[$\pcalgostyle{Vrfy}(\pk, m,\sigma)$:] The deterministic verification algorithm takes as input the public key $\pk$, a message $m$, and a signature $\sigma$, and it returns a decision bit.
\end{description}

A signature scheme is correct if honestly generated signatures always verify correctly.
\input{sig_corr_def.tex}
For security we are interested in existential unforgeability, \emph{i.e,} it must be infeasible to forge a valid signature on a new fresh message.
\input{sig_sec_def.tex}


\section{Related Work}\label{sec:related_works}

\ifCONF
\begin{table*}[tb]
\else
\begin{table}[tb]
\small
\fi
  \centering
  \caption{Comparison between Arcula and the existing state-of-the-art solutions.}\label{tab:state_of_the_art}
  \begin{tabular}{c c c c c}
    \toprule
\ifCONF
  & \begin{tabular}{c} Security to Privilege Escalation \\ (\Cref{prp:secret_keys}) \end{tabular} &
  \begin{tabular}{c} Public Key Derivation \\ (\Cref{prp:public_keys}) \end{tabular} &
  \begin{tabular}{c} Deterministic Generation \\ (\Cref{prp:determinism}) \end{tabular} &
\else
  & \begin{tabular}{c} Security to \\ Privilege Escalation \\ (\Cref{prp:secret_keys}) \end{tabular} &
  \begin{tabular}{c} Public Key \\ Derivation \\ (\Cref{prp:public_keys}) \end{tabular} &
  \begin{tabular}{c} Deterministic \\ Generation \\ (\Cref{prp:determinism}) \end{tabular} &
\fi
  Hierarchy \\
  \midrule
  BIP32~\cite{wuille2012bip32} & No & Yes & Yes & Tree \\
  Hardened BIP32~\cite{wuille2012bip32} & Yes & No & Yes & Tree \\
  Gutoski and Stebila~\cite{gutoski2015} & No & Bounded & Yes & Tree \\
  Fan \emph{et al.}~\cite{dblp:conf/desec/fantshk18} & No & Yes & Yes & Tree \\
  \midrule
  Poulami \emph{et al.}~\cite{das2019formal} & $-$ & $-$ & $-$ & No \\
  Goldfeder \emph{et al.}~\cite{goldfeder2015securing} & $-$ & $-$ & $-$ & No \\
  Gennaro \emph{et al.}~\cite{gennaro2016} & $-$ & $-$ & $-$ & No \\
  Dikshit and Singh~\cite{dikshit2017} & $-$ & $-$ & $-$ & No \\
  \midrule
  Arcula (\Cref{sec:arcula}) & Yes & Yes & Bounded & DAG \\
  \bottomrule
  \end{tabular}
\ifCONF
\end{table*}
\else
\end{table}
\fi

Bitcoin Improvement Proposal 32 (BIP32) defines the state of the art implementation of hierarchical deterministic wallets~\cite{wuille2012bip32}.
In short, let \ensuremath{g}{} be the generator point of an Elliptic Curve.
A private key \ensuremath{\sk_{i}}{} is associated with its public key \ensuremath{\ppki = \cGroupPub{\sski}}{}.
Let \hash{} be a hash function; the descendants' private keys \ensuremath{\sk_{j}}{} is defined as:
\begin{equation}\label{eq:secret_key}
  \ensuremath{\sk_{j}}{} = \hash(\ensuremath{\pk_{i}}{} \concat j) + \ensuremath{\sk_{i}}{}
\end{equation}
The corresponding public keys \ensuremath{\pk_{j}}{}, instead:
\ifFULL{}
\begin{align}
  \ensuremath{\pk_{j}}{} &= \cGroupPub{\ensuremath{\sk_{j}}{}} \nonumber \\
  \ensuremath{\pk_{j}}{} &= \cGroupPub{\hash(\ensuremath{\pk_{i}}{} \concat j) + \ensuremath{\sk_{i}}{}} \nonumber \\
  \ensuremath{\pk_{j}}{} &= \cGroupPub{\hash(\ensuremath{\pk_{i}}{} \concat j)} \cdot \cGroupPub{\ensuremath{\sk_{i}}{}} \nonumber \\
  \ensuremath{\pk_{j}}{} &= \cGroupPub{\hash(\ensuremath{\pk_{i}}{} \concat j)} \cdot \ensuremath{\pk_{i}}{}\label{eq:public_key}
\end{align}
\else
\begin{equation}
  \ensuremath{\pk_{j}}{} =
  \cGroupPub{\ensuremath{\sk_{j}}{}} =
  \cGroupPub{\hash(\ensuremath{\pk_{i}}{} \concat j) + \ensuremath{\sk_{i}}{}} =
 
  \cGroupPub{\hash(\ensuremath{\pk_{i}}{} \concat j)} \cdot \ensuremath{\pk_{i}}{}\label{eq:public_key}
\end{equation}
\fi
\Cref{eq:secret_key,eq:public_key} satisfy the properties of deterministic generation and public derivation (\Cref{prp:determinism,prp:public_keys}).
However,~\Cref{eq:secret_key} creates a privilege escalation vulnerability where the knowledge of a descendant private key \ensuremath{\sk_{j}}{} and the parent public key \ensuremath{\pk_{i}}{} allows recovering the parent private key \ensuremath{\sk_{i}}{}:
\begin{equation*}
  \ensuremath{\sk_{i}}{} = \ensuremath{\sk_{j}}{} - \hash(\ensuremath{\pk_{i}}{} \concat j) \mod \ensuremath{q}
\end{equation*}
This privilege escalation vulnerability has been discussed extensively~\cite{wuille2012bip32,vitalik:2013,courtois2014privatekr,gutoski2015}.
In the context of our threat model, there is no distinction between the cold storage and the hot environment, since compromising any node leads to compromising the entire wallet.

BIP32 addresses this issue by designing a \emph{hardened} key derivation method that generates a descendant private key $\sk^{h}_{j}$ as follows:
\begin{equation}
  \sk^{h}_{j} = \hash(\ensuremath{\sk_{i}}{} \concat i) + \ensuremath{\sk_{i}}{} \mod \ensuremath{q}{}\label{eq:secret_key_h}
\end{equation}
The hardened derivation solves the privilege escalation vulnerability but looses the public key derivation (\emph{i.e.}, trades~\Cref{prp:public_keys} for~\Cref{prp:secret_keys}).
Generating a hardened public key $\pk^{h}_{j}$ now requires the parent secret key \ensuremath{\sk_{i}}{}:
\begin{equation*}
  \pk^{h}_{j} = \cGroupPub{\sk^{h}_{j}} = \cGroupPub{\hash(\ensuremath{\sk_{i}} \concat j) + \ensuremath{\sk_{i}}{}} = \cGroupPub{\hash(\ensuremath{\sk_{i}}{} \concat j)} \cdot \ensuremath{\pk_{i}}{}
\end{equation*}

In~\Cref{tab:state_of_the_art} we compare Arcula, our hierarchical deterministic wallet, with (hardened) BIP32 and the related works.
BIP32 does not satisfy the security to privilege escalation property.
The hardened version of BIP32, instead, fails in deriving public keys without requiring additional secrets.
Gutoski and Stebila~\cite{gutoski2015} propose an HDW strengthens the security of BIP32.
Their design splits each secret key into $n$ shares, distributed to the descendants of the user;
reconstructing the secret key requires at least $m$ shares.
This solution provides weaker security than~\Cref{prp:secret_keys}, because $m$ colluding descendants of a user can recover the original secret key (as opposed to preventing any set of colluding descendants from escalating their privileges).
In addition, they support~\Cref{prp:public_keys} by publishing the public keys of all the users in the wallet.
They do not allow the generation of fresh public keys, and their derivation is bounded to the number of published keys.
Fan \emph{et al.}~\cite{dblp:conf/desec/fantshk18} develop an HDW based on Schnorr signatures and trapdoor hash functions that enables the users to sign new transactions without accessing their private keys.
A generic user can sign transactions on behalf of its descendants only after authorization by the root of the hierarchy that needs to reveal her the master private trapdoor key.
As a result, any authorized user is able not only to sign new transactions on behalf of its descendants but also of all the users of the hierarchy.
Compromising a single authorized user leads to revealing every secret stored in the wallet --- the cold storage and hot environment of our threat model overlap, and the scheme is not secure against privilege escalation.
Poulami \emph{et al.}~\cite{das2019formal} provide a formal definition of non-hierarchical deterministic wallets and show a set of modifications that make ECDSA-based deterministic wallets provably secure.
Goldfeder \emph{et al.}~\cite{goldfeder2015securing} and subsequently Gennaro \emph{et al.}~\cite{gennaro2016} propose a non-hierarchical deterministic wallet where the secret key is shared among $n$ parties, and at least $t$ of them are required to sign a transaction.
Dikshit and Singh~\cite{dikshit2017} extend the threshold-based ECDSA signatures to assign different weights to the participants of the protocol.
These works deal with non-hierarchical deterministic wallets, and they do not aim at achieving~\Cref{prp:secret_keys,prp:determinism,prp:public_keys} (depending on the hierarchical structure of the wallet).

Arcula, on the other hand, is the only solution secure against privilege escalation that, at the same time, enables identity-based unbound public key derivation.
Spending the coins addressed to one of its users, however, requires the creation of a certificate that associates their identities to their keys.
For this reason,~\Cref{prp:determinism} and, more precisely, spending coins within Arcula, is bound to the generation of a certificate, signed by the master secret key, that authorizes the users.
The deterministic generation of secret keys, instead, relies on an unbound hierarchical key assignment.
This approach provides some significant advantages and enables a set of novel use cases:
Users (\emph{e.g.}, enterprises, or smart contracts in decentralized finance) rely on the identity-based derivation to generate in untrusted environments fresh public keys and addresses on which they will securely receive coins.
The certificates will only be required before spending these coins, and their generation can happen entirely offline (\emph{e.g.}, in cold storage).

Finally, Arcula differentiates itself from the other solutions by supporting a complex access hierarchy --- \emph{e.g.}, a directed acyclic graph (DAG) --- instead of a tree.
Many of our novel use cases require more complex hierarchies.
Consider, for instance, two or more departments of a company that collaborate on a project.
They share a common budget and need to spend from it without revealing their own secret key.
The access hierarchy encoding this context would derive a single node, the budget, as a successor of multiple others (the departments).
\Cref{eq:secret_key,eq:public_key,eq:secret_key_h} cannot handle hierarchies where a node has more than one predecessor---constraining BIP32 only to implement access hierarchy that forms a tree.
The hierarchical key assignment scheme at the core of Arcula, instead, supports complex hierarchies and, in addition, it allows us to dynamically modify the hierarchy (\emph{e.g.}, by deleting an intermediate node) and to incorporate temporal capabilities (\emph{e.g.}, key expiration) into the wallet.



\section{Time-Bound Deterministic Hierarchical Key Assignment}\label{sec:time_bound_deterministic_hierarchical_key_assignment}
A hierarchical key assignment scheme aims at assigning a cryptographic key to every user of an access hierarchy so that users with higher privileges can autonomously derive the keys of the others within their subtrees, \emph{i.e.}, with lower privileges in the hierarchy.
Many use cases require constraining these assignments according to some time restrictions.
For example, a service provider aims to provide a user with her cryptographic keys only as long as she pays for her subscription to the service.
To achieve this goal, it can leverage a key assignment scheme that takes time into account, and that enables the users to deriver their cryptographic keys during a given period only (\emph{e.g.}, one month).
This section details how we incorporate these temporal capabilities into the deterministic hierarchical key assignment scheme of~\Cref{sec:deterministic_wallets_through_dynamic_and_efficient_key_management} and within Arcula, our design hierarchical deterministic wallet (\Cref{sec:arcula}).

In the last few years, many researchers focused on how to incorporate temporal capabilities into HKA schemes~\cite{ateniese2012,atallah2007,desantis2008}.
The solutions proposed first modify the hierarchy of the assignment to consider, at the same time, both the access privileges and the temporal constraints.
Then, assign a set of secrets to the nodes of the augmented hierarchy so that the users can perform the key derivation according to the time constraints.

We add these constraints to our DHKA by relying on the work of De Santis \emph{et al.}~\cite{desantis2008} that shows how to design a time-bound key-indistinguishable HKA scheme from any provably secure HKA scheme (and, in particular, from our DHKA).
Let \ensuremath{\cG = (\cV, \cE)}{} be an access hierarchy and let $\ensuremath{\mathcal{T}}{} = \set{t_1, t_2, \ldots, t_n}$ be a sequence of distinct time periods.
Each user \ensuremath{\cv{i}}{} belongs to a node of the hierarchy for a non-empty contiguous subsequence $\ensuremath{\ensuremath{\mathcal{T}}_{i}}{} = \set{t_j, \ldots, t_k} \subseteq \ensuremath{\mathcal{T}}$ of time periods.\footnote{In~\cite{desantis2008} the subsequence of time periods of a node $\ensuremath{\cv{i}}{} \in \ensuremath{V}$ is denoted by $\lambda_i$.}
Let $\ensuremath{\mathcal{P}}{} = \set{\ensuremath{\ensuremath{\mathcal{T}}_{i}}{}}_{\ensuremath{\cv{i}} \in \ensuremath{V}}$ be the set of time subsequences \ensuremath{\ensuremath{\mathcal{T}}_{i}}{} when every user $\ensuremath{\cv{i}}{} \in \ensuremath{V}$ belongs to the hierarchy.
The authors start from the observation that the contiguous subsequences $\ensuremath{\ensuremath{\mathcal{T}}_{i}}{} \in \ensuremath{\mathcal{P}}$ implicitly define a partially ordered hierarchy, where $\ensuremath{\ensuremath{\mathcal{T}}_{i}}{} < \ensuremath{\ensuremath{\mathcal{T}}_{j}}{} \iff \forall t_k \in \ensuremath{\ensuremath{\mathcal{T}}_{i}} \implies t_k \in \ensuremath{\ensuremath{\mathcal{T}}_{j}}$, \emph{i.e.} iff \ensuremath{\ensuremath{\mathcal{T}}_{i}}{} is included in \ensuremath{\ensuremath{\mathcal{T}}_{j}}{}.
They call this relation the \emph{interval hierarchy}, and they use its minimal representation, where every node except the leaves has precisely two edges, to augment the original access hierarchy encoded by the graph \ensuremath{G}{}.
As a result, they build a new graph, $\ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{} = (\ensuremath{V}_{\ensuremath{\mathcal{T}}{}}, \ensuremath{E}{}_{\ensuremath{\mathcal{T}}})$, that enforces both the access and the interval partially ordered hierarchies.
$\ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{}$ contains a copy of the interval hierarchy for each node in \ensuremath{G}{}.
A user \ensuremath{\cv{i}}{} derives the cryptographic key assigned to its descendant \ensuremath{\cv{j}}{} for the period $t_k \in \ensuremath{\ensuremath{\mathcal{T}}_{j}}{}$ by following the path in the augmented graph \ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{} along the copy of the interval hierarchy related to \ensuremath{\cv{j}}{} and then through the original access hierarchy encoded by $\ensuremath{G}{}$.
The instantiation of the (D)HKA scheme on the graph $\ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{}$ results in a (deterministic) time-bound hierarchical key assignment scheme.

By construction, the number of nodes and edges in \ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{} grows quadratically in the size of \ensuremath{\mathcal{T}}{} and in the dimension of \ensuremath{G}{}.
In turn, the amount of public information required by a generic HKA scheme on \ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{} grows comparably.
As we have seen in~\Cref{sub:dhka_implementation}, however, the determinism of our DHKA scheme allows us to reduce the amount of public information required significantly:
The nodes of the access hierarchy can derive the secret information of their descendants by leveraging their own secrets and only rely on the public information when a node has two or more predecessors.
In the same way, when we augment the access hierarchy encoded by \ensuremath{G}{} to account for the interval hierarchy into \ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{}, the determinism of the scheme allows us to reduce the amount of public information required.
The augmented hierarchy \ensuremath{\cG{}_{\ensuremath{\mathcal{T}}{}}}{}, indeed, stores a copy of the minimal interval hierarchy for every node of \ensuremath{G}{}.
Every node of the minimal interval hierarchy only has a single predecessor and, as a result, does not require any public information associated with its edges.
For this reason, when we leverage our design of DHKA to incorporate the temporal capabilities into an HKA scheme, the size of the public information required grows only linearly with the dimension of the access hierarchy \ensuremath{G}{} and, in particular, is independent of the cardinality of \ensuremath{\mathcal{T}}{}.

To conclude, we show how to incorporate these temporal capabilities into Arcula, our design of HDW based on DHKA and digital signatures.
Our construction provides the users of the access hierarchy with a certificate and a signing key.
The certificate, signed by the master secret key, authorizes the signing key to spend the coins addressed to their identities.
When we add the temporal capabilities to the DHKA, we assign a different signing key to each user \ensuremath{\cv{i}}{} for each time period $t_j \in \ensuremath{\ensuremath{\mathcal{T}}_{i}}{}$;
then, we provide her with a certificate $\ensuremath{\mathsf{cert}}_{i,j}$ for each key.
We prevent the users from signing new transactions through an outdated key by adding an expiration date to these certificates so that they are only valid until the end of the period $t_j$.
As a result, every user \ensuremath{\cv{i}}{} will require an updated certificate after each time period passes.
The stack-based scripting language of Bitcoin Cash does not allow yet to check for the expiration date of a certificate.
For this reason, our design of time-bound Arcula requires, at the time of writing, a more powerful scripting language, \emph{e.g.} an Ethereum smart contract.