text:
\section{Summary and Discussion}
{
	In this work we propose a framework of decentralized custody schemes based on overlapping group assignments.
	This custody scheme allows better efficiency as well as stronger liveness,
	and its security is guaranteed in a game-theoretic sense without resorting to any central authorities or trusted party.
	We believe such decentralized custody scheme will find applications in digital finance as well as DeFi on blockchains.

	Future improvements of this work include explicit constructions of compact assignments with much less custodian groups,
	efficient approximation algorithms for estimating the actual efficiency factor of a given custody scheme in our framework,
	and more rigorous analysis of liveness guarantee as well as the tradeoff between liveness and security.
}

\bibliographystyle{splncs04}

\section{Proof of lemmas and theorems}

	\subsection{Proof of Lemma~\ref{lem_des_all}}\label{app_pro_lem_des_all}
	\begin{proof}
		For simplicity, let $s:= \gamma n$ be the number of nodes that the adversary corrupts, and
		\[\eta_{s} = \frac{s}{n}\frac{\binom{n}{k}}{\sum_{t = r}^{k}\binom{s}{t}\binom{n - s}{k - t}} - 1\]
		be the efficiency factor of the system in this case. We will compare $\eta_{s}$ with $\eta_{s - 1}$. Specifically, we compare every corresponding pair of terms in the sum. For any $r \leq t \leq k$, we have
		\begin{align*}
			\left. s\cdot \frac{\binom{n}{k}}{\binom{s}{t}\binom{n - s}{k - t}} \middle/ (s - 1)\cdot \frac{\binom{n}{k}}{\binom{s - 1}{t}\binom{n - s + 1}{k - t}} \right. &= \left. \frac{(n - s - k + t)!(s - t)!}{(n - s)!(s - 1)!} \middle/ \frac{(n - s - k + t + 1)!(s - t - 1)!}{(n - s + 1)!(s - 2)!} \right. \\
			&= \frac{(s - t)(n - s + 1)}{(n - s - k + t + 1)(s - 1)},
		\end{align*}
		and
		\begin{align*}
			&\qquad\ \frac{(s - t)(n - s + 1)}{(n - s - k + t + 1)(s - 1)} \leq 1 \\
			&\Longleftrightarrow (s - t)(n - s + 1) \leq (n - s - k + t + 1)(s - 1) \\
			&\Longleftrightarrow s(k - 1) \leq (t - 1)n + k - 1 \\
			&\Longleftarrow\ s \leq \frac{\mu k - 1}{k - 1}n + 1.
		\end{align*}
		Here, the second inequality is due to $s \leq n - k$, while the fourth inequality is due to $t > \mu k$. The result implies that $\eta_{s} \leq \eta_{s - 1}$ always holds when $s \leq \frac{\mu k - 1}{k - 1}n + 1$, which proves the lemma as $s = \gamma n$.
		\qed
	\end{proof}

	\subsection{Proof of Theorem~\ref{the_des_all}}\label{app_pro_the_des_all}
	\begin{proof}
		We will first prove that the system is reliable when $k \geq 10$ and $\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k} \leq \gamma \leq \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}$, and combine the result with Lemma~\ref{lem_des_all} to prove the theorem. Note here that as $n \geq 2k$, there must exist some $\gamma$ in $[\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k}, \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}]$ such that $\gamma n$ is an integer.

		Recall that the system is $\gamma$-reliable as long as
		\[\gamma \geq \sum_{\mu k < t \leq k} \frac{\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}}{\binom{n}{k}},\]
		by the tail bound of hypergeometric distribution (see Section~\ref{sec_pre}) and that $\gamma < \mu$, we have
		\[\sum_{\mu k < t \leq k} \frac{\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}}{\binom{n}{k}} \leq \exp(-kD(\mu \| \gamma)) \leq \left(4\gamma (1 - \gamma)\right)^{k/2}.\]

		The last equality is due to
		\[D(\mu \| \gamma) > D(\frac{1}{2} \| \gamma) = \frac{1}{2} \ln \frac{1}{2\gamma} + \frac{1}{2} \ln \frac{1}{2(1 - \gamma)} = \frac{1}{2} \ln \frac{1}{4\gamma(1 - \gamma)},\]
		as $\gamma < 1/2 < \mu$. (See Section~\ref{sec_pre}.)

		When $\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k} \leq \gamma \leq \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}$ and $k \geq 10$,
		\begin{align*}
			\left(4\gamma (1 - \gamma)\right)^{k/2} & \leq \left(1 - 4\left(\frac{2\sqrt{k} + 1}{2k}\right)^2\right)^{k / 2} \\
			&\leq \exp \left(-\frac{(2\sqrt{k} + 1)^2}{2k}\right) \\
			&\leq \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k} \leq \gamma,
		\end{align*}

		The second inequality is due to $(1 - 1/x)^x \leq 1/e$ for any $x > 1$. This implies that the system is $\gamma$-reliable when $\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k} \leq \gamma \leq \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}$. Note that when $\mu > 1/2$, $n \geq 2k$ and $k \geq 10$,
		\[\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k} \leq \frac{1}{2} - \frac{1}{2(k - 1)} + \frac{1}{n} < \min \left(\frac{\mu k - 1}{k - 1} + \frac{1}{n}, 1 - \frac{k}{n}\right),\]
		with Lemma~\ref{lem_des_all}, the result is reached.
		\qed
	\end{proof}

	\subsection{Proof of Theorem~\ref{the_des_blo}}\label{app_pro_the_des_blo}
	\begin{proof}
		When $\binom{s}{r} \leq \left. \binom{n}{r} \middle/ \binom{k}{r} \right.$, by Lemma~\ref{lem_des_blo}, we have the following lower bound on the efficiency factor of the system:
		\[\eta \geq \frac{s}{n}\frac{\binom{n}{r}}{\binom{k}{r}\binom{s}{r}} - 1.\]

		For the system to be reliable, it is sufficient if we have
		\[\frac{s}{n}\frac{\binom{n}{r}}{\binom{k}{r}\binom{s}{r}} \geq 1.\]

		Note that
		\begin{align*}
		\frac{s}{n}\frac{\binom{n}{r}}{\binom{k}{r}\binom{s}{r}} &= \frac{s}{n} \left. \frac{n!(s - r)!}{(n - r)!s!} \middle/ \binom{k}{r} \right. \\
		&= \frac{n - 1}{s - 1}\cdot \cdots \cdot\frac{n - r + 1}{s - r + 1}\cdot \frac{r}{k}\cdot \frac{r - 1}{k - 1}\cdot \cdots \cdot\frac{1}{k - r + 1} \\
		&= \prod_{t = 1}^{r - 1}\frac{(n - t)(r - t)}{(s - t)(k - t)} \cdot \frac{r}{k} \\
		&> \prod_{t = 1}^{r - 1}\frac{(n - t)(r - t)}{(s - t)(k - t)} \cdot \mu.
		\end{align*}
		which is satisfied if we have
		\[\frac{(n - t)(r - t)}{(s - t)(k - t)} \geq \mu^{-\frac{1}{r - 1}},\quad \forall 1 \leq t \leq r - 1.\]

		Let $c := \mu^{-\frac{1}{r - 1}} > 1$, the above condition is equivalent to
		\[c(s - t)(k - t) - (n - t)(r - t) \leq 0,\quad \forall 1 \leq t \leq r - 1,\]
		and by the property of quadratic functions, we only need to work on the case of $t = 1$ and $t = r - 1$.

		When $t = 1$, the condition becomes
		\[\frac{s - 1}{n - 1} \leq \frac{r - 1}{c(k - 1)},\]
		note that $\frac{s - 1}{n - 1} < \frac{s}{n} = \gamma$. Hence it is sufficient with
		$\gamma \leq \frac{r - 1}{c(k - 1)}$. When $\mu \geq 1/2$, $r \geq 2$ and $n \geq 3k - 3$, we have $c = \mu^{-\frac{1}{r - 1}} < 3/2$. Therefore,
		\begin{align*}
			s \leq \frac{n}{c\cdot k} + r - 1 &\Longrightarrow \gamma \leq \frac{1}{c\cdot k} + \frac{r - 1}{n} \\
			&\Longrightarrow \gamma \leq \frac{1}{c(k - 1)} + \frac{2(r - 2)}{n} \\
			&\Longrightarrow \gamma \leq \frac{1}{c(k - 1)} + \frac{2(r - 2)}{3(k - 1)} \\
			&\Longrightarrow \gamma \leq \frac{1}{c(k - 1)} + \frac{r - 2}{c(k - 1)} \\
			&\Longrightarrow \gamma \leq \frac{r - 1}{c(k - 1)}.
		\end{align*}

		When $t = r - 1$, the condition becomes
		\[n - r + 1 \geq c(s - r + 1)(k - r + 1), \]
		or
		\[s \leq \frac{n - r + 1}{c(k - r + 1)} + r - 1.\]

		which establishes when $s \leq \frac{n}{ck} + r - 1$, as $\frac{n}{k} \leq \frac{n - r + 1}{k - r + 1}$.
		\qed
	\end{proof}

	\subsection{Proof of Lemma~\ref{lem_des_pol_aug}}\label{app_pro_lem_des_pol_aug}
	\begin{proof}
		We say a subset of $S$ is \emph{first-entry-unrepeated} if all nodes in the subset are with different first entry. Now that the adversary corrupts $s$ nodes in total. Let $s_i$ be the number of corrupted nodes with first entry $i$. We have $s = s_0 + s_1 + \cdots s_{k - 1}$. Therefore, the number of size-$d$ first-entry-unrepeated subsets that is totally corrupted is
		\[\sum_{0 \leq i_1 < i_2 \cdots < i_d \leq k - 1}s_{i_1}s_{i_2}\cdots s_{i_d}.\]

		To give an upper bound on the above formula, we extend the problem to the case where $s_0, s_1, \cdots, s_{k - 1}$ are multiples of $1/k$. (The original problem is when $s_0, s_1, \cdots, s_{k - 1}$ are all integers.) For any two indices $u, v$, suppose $s_v - s_u \geq 2/k$, note that
		\begin{align*}
			&\quad \sum_{0 \leq i_1 < i_2 \cdots < i_d \leq k - 1}s_{i_1}s_{i_2}\cdots s_{i_d} \\
			&= s_us_v\sum_{0 \leq i_1 < i_2 \cdots < i_{d - 2} \leq k - 1
			\atop
			\{i_1, i_2, \cdots, i_{d - 2}\} \cap \{u, v\} = \emptyset}s_{i_1}s_{i_2}\cdots s_{i_{d - 2}}
			+ (s_u + s_v)\sum_{0 \leq i_1 < i_2 \cdots < i_{d - 2} \leq k - 1
			\atop
			\{i_1, i_2, \cdots, i_{d - 1}\} \cap \{u, v\} = \emptyset}s_{i_1}s_{i_2}\cdots s_{i_{d - 1}} \\
			&+ \sum_{0 \leq i_1 < i_2 \cdots < i_d \leq k - 1
			\atop
			\{i_1, i_2, \cdots, i_d\} \cap \{u, v\} = \emptyset}s_{i_1}s_{i_2}\cdots s_{i_d}.
		\end{align*}

		Hence, the sum is strictly increase by substituting $s_u$ with $s_u' = s_u + 1/k$ and $s_v$ with $s_v' = s_v - 1/k$. Therefore, the sum reaches a maximum with $s_0 = s_1 = \cdots = s_{k - 1} = s/k$ in the generalized case, which implies that with $s_0, s_1, \cdots, s_{k - 1}$ all integers, we have
		\[\sum_{0 \leq i_1 < i_2 \cdots < i_d \leq k - 1}s_{i_1}s_{i_2}\cdots s_{i_d} \leq \binom{k}{d}\left(\frac{s}{k}\right)^d,\]
		or that the number of size-$d$ first-entry-unrepeated subsets that is totally controlled by the adversary is upper bounded by $\binom{k}{d} (s / k)^d$. Let $\mathcal{M}$ denote the set of corrupted nodes. By (\ref{ieq:ApAq}), every size-$d$ first-entry-unrepeated subset of $\mathcal{M}$ appears in at most one corrupted group. On the other hand, every corrupted group contains at least $r$ corrupted nodes all with different first entry, and hence $\ge \binom{r}{d}$ size-$d$ first-entry-unrepeated subsets. Consequently, the number of corrupted groups is upper bounded by $\frac{\binom{k}{d}s^d}{\binom{r}{d}k^d}$, and the efficiency factor $\eta$ is lower bounded by
		\[\eta \geq \frac{\gamma \binom{r}{d}k^{2d}}{\binom{k}{d}s^d} - 1 = {\gamma^{1 - d} \cdot \binom{r}{d}}\Big/{\binom{k}{d}} - 1,\]
		as $s = \gamma n = \gamma k^2$.
	\end{proof}

	\subsection{Proof of Theorem~\ref{the_des_pol_aug}}\label{app_pro_the_des_pol_aug}
	\begin{proof}
		As per Lemma~\ref{lem_des_pol_aug}, it is sufficient if we have
		\[\gamma^{d - 1} \leq \left. \binom{r}{d} \middle/ \binom{k}{d} \right..\].

		As we have
		\begin{align*}
			\left. \binom{r}{d} \middle/ \binom{k}{d} \right. &= \frac{(k - d)!r!}{(r - d)!k!} \\
			&\geq \frac{2\pi}{e^2} \frac{(k - d)^{k - d + \frac{1}{2}}r^{r + \frac{1}{2}}}{(r - d)^{r - d + \frac{1}{2}}k^{k + \frac{1}{2}}} \\
			&= \frac{2\pi}{e^2} \sqrt{\frac{(k - d)r}{(r - d)k}}\cdot \frac{(k - d)^{k - d}}{k^k}\cdot \frac{r^r}{(r - d)^{r - d}} \\
			&= \frac{2\pi}{e^2} \sqrt{\frac{(k - d)r}{(r - d)k}}\cdot \frac{1}{\left(1 + d / (k - d)\right)^{k - d}}\cdot \frac{r^r}{(r - d)^{r - d}k^d}\\
			&\frac{2\pi}{e^{d + 2}}\sqrt{\frac{(1 - \nu)\mu}{\mu - \nu}}\left(\frac{\mu^{\mu}}{(\mu - \nu)^{\mu - \nu}}\right)^k,
		\end{align*}
		the theorem is proved by having the last formula no less than $\gamma^{d - 1}$. Here, we use Stirling's formula (see Section~\ref{sec_pre}) to estimate the factorial term in the second line. Meanwhile, in the second line from the bottom, we apply that $(1 + 1/x)^x < e$ for all $x > 0$.
		\qed
	\end{proof}

	\subsection{Proof of Theorem~\ref{the_boo_ran}}\label{app_pro_the_boo_ran}
	\begin{proof}
		To show the result, first consider a specific attacking strategy from the adversary who precisely corrupts $\gamma n$ nodes. We call the strategy $\mathcal{M}$. Denote $g(\mathcal{M})$ be the corrupted groups with strategy $\mathcal{M}$ under the group assignment scheme $\mathcal{A}$. Clearly, $g(\mathcal{M}) \leq f(\gamma; \mathcal{A}, \mu)$ by definition.

		Now suppose we uniformly draw $\beta m$ groups from $\mathcal{A}$ to obtain $\mathcal{A}'$, and let $X$ be a random variable indicating the number of corrupted groups in the new scheme $\mathcal{A}'$. By hypergeometric tail bound (see Section~\ref{sec_pre}), we have
		\begin{align*}
			\Pr\left[X \geq \left(\frac{f(\gamma; \mathcal{A}, \mu)}{m} + \delta\right)\cdot \beta m\right] &= \Pr\left[X \geq \left[\frac{g(\mathcal{M})}{m} + \left(\frac{f(\gamma; \mathcal{A}, \mu) - g(\mathcal{M})}{m} + \delta\right)\right] \cdot \beta m \right] \\
			&\leq \exp\left(-2\beta m\cdot\left(\frac{f(\gamma; \mathcal{A}, \mu) - g(\mathcal{M})}{m} + \delta \right)^2\right) \\
			&\leq \exp(-2\beta m \cdot \delta^2).
		\end{align*}
		Here, $\delta > 0$ is a parameter to be determined. The probability is over all possible choices of $\mathcal{A}'$. Let $f(\gamma; \mathcal{A}',\mu) $ denote the maximal number of groups that can be corrupted with $\gamma n$ compromised nodes in the new scheme $\mathcal{A}'$, by a union bound, we have
		\[\Pr\left[f(\gamma; \mathcal{A}',\mu) \geq \beta f(\gamma; \mathcal{A}, \mu) + \delta \cdot \beta m\right] \leq \exp(-2\beta m \cdot \delta^2) \binom{n}{\gamma n}.\]

		By Stirling's formula (see Section~\ref{sec_pre}),
		\begin{align*}
		\binom{n}{\gamma n} &= \frac{n!}{(\gamma n)!(n - \gamma n)!} \\
		&\leq \frac{e}{2\pi} \frac{n^{n + \frac{1}{2}}}{(\gamma n)^{\gamma n + \frac{1}{2}}(n - \gamma n)^{n - \gamma n + \frac{1}{2}}} \\
		&= \frac{e}{2\pi} \sqrt{\frac{1}{n \gamma (1 - \gamma)}}\cdot \left(\frac{1}{\gamma^{\gamma}(1 - \gamma)^{ 1 - \gamma}}\right)^n \\
		&\leq \frac{e}{2\pi} \left(\frac{1}{\gamma^{\gamma}(1 - \gamma)^{ 1 - \gamma}}\right)^n.
		\end{align*}

		Hence,
		\[\Pr[f(\gamma; \mathcal{A}',\mu) \geq \beta f(\gamma; \mathcal{A}, \mu) + \delta \cdot \beta m] \leq \exp(-2\beta m \cdot \delta^2) \binom{n}{\gamma n} \leq \frac{e}{2\pi} \exp(-2\beta m \cdot \delta^2 + n \xi).\]

		Let $\beta m \cdot \delta^2 = \frac{1 + c}{2}\cdot n\xi$, then w.p. no less than $1 - \frac{e}{2\pi}\exp(-cn\xi)$, we have $f(\gamma; \mathcal{A}',\mu) \leq \beta f(\gamma; \mathcal{A}, \mu) + \delta \cdot \beta m$. Under such case, the efficiency factor $\eta'$ of $\mathcal{A}'$ with malicious rate $\gamma$ is lower bounded by
		\begin{align*}
			\eta' &= \gamma \frac{\beta m}{f(\gamma; \mathcal{A}',\mu)} - 1 \\
			&\geq \gamma \frac{m}{f(\gamma; \mathcal{A}, \mu) + \delta \cdot m} - 1 \\ &= \gamma \frac{m}{\frac{\gamma m}{\eta + 1} + \delta \cdot m} - 1 \\
			&= \gamma \frac{\eta + 1}{\gamma + \delta \cdot (\eta + 1)} - 1 \\
			&= \frac{\gamma \sqrt{\beta m}(\eta + 1)}{\gamma \sqrt{\beta m} + \sqrt{(1 + c)n \xi / 2}(\eta + 1)} - 1.
		\end{align*}
		The third line is due to the definition of $\eta$:
		\[\eta = \gamma \cdot \frac{m}{f(\gamma; \mathcal{A}, \mu)} - 1.\]
		\qed
	\end{proof}

	\subsection{Proof of Theorem~\ref{the_hard}}\label{app_pro_the_hard}
	\begin{proof}
		First of all, it is trivial that the given problem is harder than only to determine the number of corrupted groups under the best attacking strategy. We only consider the latter in this proof. Technically, we will work on the two cases, $r < k$ and $r = k$ respectively.
		\begin{itemize}
			\item $r < k$. We first deal with the case when $r = 1$. In fact, in this case, when $k = 2$, then finding the optimal attacking strategy is naturally equivalent to the MAX $s$-VC problem in common graphs. Here, the MAX $s$-VC problem is to compute the maximum number of edges that $s$ vertices can cover given a graph of size $n$. This problem is known to be NP-hard.

			When $k > 2$, the problem is equivalent to the MAX $s$-VC problem in $k$-uniform hypergraphs. Here, a $k$-uniform hypergraph is a hypergraph in which each edge contains exactly $k$ vertices. We reduce the MAX $s$-VC problem in common graphs to this problem. Specifically, consider a realization of the problem in the graph $G = (V, E)$ with $m$ edges. We transfer $G$ to a $k$-uniform hypergraph $G' = (V', E')$ by adding $(k - 2)m$ vertices to $V$. Denote these vertices as $v_1^1, v_1^2, \cdots, v_1^m, \cdots, v_{k - 2}^1, v_{k - 2}^2, \cdots, v_{k - 2}^m$. For each edge $e_i$ in $G$, we add $v_1^i, v_2^i, \cdots, v_{k - 2}^i$ to $e_i$ and obtain an edge $e_i'$ in $E'$ with $k$ vertices. Now consider the MAX $s$-VC solution in $G'$. Obviously, there is an optimum which contains no point in $V' - V$, as any point in $V' - V$ appears in only one edge, and substituting a selected point in $V' - V$ with an unselected point in the same edge that belongs to $V$ will cause no loss on the objective function. If all vertices in that edge that belongs to $V' - V$ are selected, we can alternatively pick any non-chosen vertices in $V' - V$, still with no loss on the goal. Therefore, the modified instance in the $k$-uniform hypergraph owns the same objective value with the original problem in common graphs. Note that the reduction step itself is polynomial as $m$ is a polynomial of $n$. At the same time, $s = (n + (k - 2)m))^{\Omega(1)}$ since $k$ is a constant and $m$ is within a polynomial of $n$. Hence, the MAX $s$-VC problem in $k$-uniform hypergraphs is NP-hard as well.

			Here, we should mention that the MAX $s$-VC problem in $k$-uniform hypergraphs ($k \geq 2$) is indeed a special case of the MAX $s$-Cover problem, with each element existing in precisely $k$ sets. The reduction is to deem each vertex as a set, including all edges incident to the vertex. There is a simple $(1 - e^{-1})$-approximation greedy algorithm for the MAX $s$-Cover problem~\cite{Hochbaum96,Cornuejols77}. Furthermore, it is known that in general, for any $\epsilon > 0$, there is no $(1 - e^{-1} - \epsilon)$-approximation for this problem unless P = NP~\cite{Feige98}. Nevertheless, concerning MAX $s$-VC in common graphs, there is a $(0.75 + \delta)$-approximation algorithm for some constant $\delta > 0$~\cite{FeigeL01}. Meanwhile, the MAX $s$-VC problem in $k$-uniform hypergraphs with $k \geq 3$ can also be approximated strictly within the ratio $0.75$~\cite{AgeevS04}.

			When $k > r > 1$, the original problem is equivalent to the following problem:
			\begin{problem}\label{pro_hard_1}
				For a $k$-uniform hypergraph $G = (V, E)$ where $|V| = n$, we say an edge is covered only if at least $r$ vertices incident to the edge is selected. With $s$ vertices, compute the maximal number of edges that can be covered.
			\end{problem}
			we reduce the problem of finding a MAX $(s - r + 1)$-VC problem in $(k - r + 1)$-uniform hypergraphs to this problem. Again, consider an instance $G = (V, E)$ of the latter problem. We add $(r - 1)$ vertices to $V$, as well as including them in each hyperedge in $E$ to achieve $G' = (V', E')$, which is an instance in Problem~\ref{pro_hard_1}. Consider the optimal solution in this problem. We claim that there always exists an optimum that concludes the appended $(r - 1)$ vertices, as changing any chosen vertex in $V$ to a point in $V' - V$ will never lessen the objective value. Under such optimum, an edge in $G'$ is covered if and only if the corresponding edge in $G$ is covered in the MAX $(s - r + 1)$-VC problem in $(k - r + 1)$-uniform hypergraph. Therefore, the two instances own the same objective value in their respective questions. Furthermore, such reduction is polynomial-bounded, which leads to the NP-hardness of Problem~\ref{pro_hard_1}.\\

			\item $r = k$. When $k = 2$, the problem becomes
			\begin{problem}\label{pro_hard_2}
				Given a common graph $G = (V, E)$ where $|V| = n$ and $s < n$, compute the maximal number of edges that $s$ vertices can \textit{completely} cover. Here, an edge is completely covered if and only if both endpoints are chosen.
			\end{problem}

			Consider a optimal solution $C$ with $|C| = s$, then the number of edges that are incident with any vertex in $V - C$ is minimized. Hence, Problem~\ref{pro_hard_2} is bidirectional-reducible to the following problem:
			\begin{problem}\label{pro_hard_3}
				Given a common graph $G = (V, E)$ where $|V| = n$ and $s < n$, compute the minimal number of edges that $n - s$ vertices can cover.
			\end{problem}

			Problem~\ref{pro_hard_3} is the uniform-weighted case of the fixed cost minimum edge cover (FCMC) problem defined in~\cite{GandhiK15}, which is proved to be NP-hard even to approximate with a factor $(2 - \epsilon)$ under the Small Set Expansion Conjecture in the same paper. Hence, under such assumption, Problem~\ref{pro_hard_2} is hard to solve. For the case when $k > 2$, we can reduce Problem~\ref{pro_hard_2} with $k$-uniform hypergraphs to the corresponding problem with the similar reduction as what we do with Problem~\ref{pro_hard_1}.
		\end{itemize}
		\qed
	\end{proof}

	\subsection{Proof of Theorem~\ref{the_hard_con}}\label{app_pro_the_hard_con}
	\begin{proof}
		We give the algorithm in Algorithm~\ref{alg_hard}. Specifically, in step $1 \leq i \leq n$ (Line~\ref{alg_hard_iter}), given a temporary corrupted list $T$ and honest list $N$, the adversary decides whether or not to corrupt node $i$. To figure this out, the adversary needs to compute the expected amount of corrupted groups $X_i$ conditioning on nodes in $T \cup \{i\}$ already compromise and nodes in $N$ are honest (Line~\ref{alg_hard_com}). In detail, the adversary should compute the conditional probability on each group is corrupted and take a sum to derive $X_i$. If $X_i \geq \kappa m$, node $i$ will be included in $T$ (Line~\ref{alg_hard_inc}), else it will be given up by the adversary (Line~\ref{alg_hard_dis}). The algorithm ends whenever $s$ nodes are already chosen (Line~\ref{alg_hard_end1}) or $n - s$ nodes are already given up (Line~\ref{alg_hard_end2}). Algorithm~\ref{alg_hard} runs in time $O(kmn)$ as there are at most $n$ steps, and in each step, one needs to compute the conditional probability for each of $m$ groups, and Computing each conditional probability gives the time complexity of $O(k)$.
		\begin{algorithm}[!ht]
			\caption{Corrupting at least an average amount of groups.}
			\label{alg_hard}
			\renewcommand{\algorithmicrequire}{\textbf{Input:}}
			\renewcommand{\algorithmicensure}{\textbf{Output:}}
			\begin{algorithmic}[1]
				\REQUIRE The node set $S = \{1, 2, \cdots, n\}$, the group assignment scheme $\mathcal{A}$ with parameters $m$ and $k$, least number of nodes to control a group $r$, number of corrupted nodes $s = \gamma n$.
				\ENSURE $T \subseteq S$ with $|T| = s$, such that when $T$ is corrupted, the adversary can at least control $\kappa m$ groups, with $\kappa$ defined as $\kappa := \Pr[\mathcal{H}(n, s, k) \geq r]$.

				\STATE $T = \emptyset, N = \emptyset$
				\FOR{$i = 1$ to $n$} \label{alg_hard_iter}
				\STATE Compute the expected amount of compromised groups $X_i$ conditioning on nodes in $T \cup \{i\}$ are malicious and nodes in $N$ are honest \label{alg_hard_com}
				\IF{$X_i \geq \kappa m$} \label{alg_hard_jud}
				\STATE $T = T \cup \{i\}$ \label{alg_hard_inc}
				\ELSE
				\STATE $N = N \cup \{i\}$ \label{alg_hard_dis}
				\ENDIF

				\IF{$|T| \geq s$} \label{alg_hard_end1}
				\RETURN $T$
				\ENDIF
				\IF{$|N| \geq n - s$} \label{alg_hard_end2}
				\RETURN $S - N$
				\ENDIF
				\ENDFOR
			\end{algorithmic}
		\end{algorithm}

		Clearly, Algorithm~\ref{alg_hard} is sure to end up with a size-$s$ subset $T$ of $S = \{1, 2, \cdots, n\}$. To show that corrupting $T$ will lead to at least $\kappa m$ groups controlled by the adversary, we need the following lemma.
		\begin{lemma}\label{lem_hard_ind}
			Suppose Algorithm~\ref{alg_hard} does not end after step $i$. Let $Y_i (i \geq 0)$ be the expected amount of corrupted nodes conditioning on $T$ is corrupted and $N$ is honest after step $i$, then $Y_{i + 1} \geq Y_{i}$. Specifically, we have $Y_0 = \kappa m$.
		\end{lemma}
		\begin{proof}
			To show this lemma, Let $X$ be a random variable denoting the number of corrupted groups. Furthermore, let $a_i < s$ and $b_i < n - s$ be respectively the size of $T_i$ and $N_i$ after step $i$, $a_i + b_i = i$. Then we have the following equality:
			\[Y_i = \mathbb{E}[X | T_i, N_i] = \frac{s - a_i}{n - i}\cdot \mathbb{E}[X | T_i \cup \{i + 1\}, N_i] + \frac{n - s - b_i}{n - i}\cdot \mathbb{E}[X | T_i, N_i \cup \{i + 1\}].\]
			Here, $\mathbb{E}[X | T_i, N_i]$ is for the expectation of $X$ conditioning on $T_i$ malicious and $N_i$ honest. Hence, at least one of the $\mathbb{E}[X | T_i \cup \{i + 1\}, N_i]$ and $\mathbb{E}[X | T_i, N_i \cup \{i + 1\}]$ is no less than $Y_i$. According to Line~\ref{alg_hard_jud}, $Y_{i + 1} \geq Y_{i}$.
			\qed
		\end{proof}

		With Lemma~\ref{lem_hard_ind}, note that $Y_0 = \kappa m$, then the theorem is proved.
		\qed
	\end{proof}
\end{subappendices}

\section{Compact Group Assignments via Random Sampling}\label{sec_boo}

We notice that in previous constructions a group assignment $\mathcal{A}$ may contain too many custodian groups which makes the induced custody scheme impossible to manage in practice.
To mitigate this problem,
we propose a randomized sampling technique to
construct compact custody schemes with a small number of custodian groups sampled from $\mathcal{A}$ as representative.

Given a group assignment $\mathcal{A}$ consisting of $m$ groups,
as well as a sampling rate $\beta \in (0,1)$,
we uniformly sample a subset of $\beta m$ elements from $\mathcal{A}$ as the new assignment $\mathcal{A}'$,
and then construct custody scheme based on $\mathcal{A}'$.
This sampling process does not change the authentication threshold $\mu$.
In what follows we analyze the efficiency of $\mathcal{A}'$ comparing to $\mathcal{A}$.

For a given corrupted fraction $\gamma$, let $\xi$ be a function of $\gamma$ defined as follows:
\begin{equation}
	\xi := -\left(\gamma \log \gamma + \left(1 - \gamma\right)\log (1 - \gamma)\right).
\end{equation}

The efficiency factor of custody scheme induced by $\mathcal{A}'$ is lower bounded as in the following theorem:

\begin{theorem}\label{the_boo_ran}
	Let $\mathcal{A}$ and $\xi$ be defined as above,
	and suppose the corrupted fraction $\gamma$ satisfies $n \gamma(1 - \gamma) \geq 1$ (which is trivial if $n>4$ and $\gamma n\ge 2$).
	Let $\mathcal{A'}$ be the group assignment uniformly sampled from $\mathcal{A}$ with $\beta\in (0,1)$,
	and let $\eta'$ denote the efficiency factor of $\mathcal{A'}$.
	Then, for arbitrary $c \geq 0$,  with probability at least $1 - \frac{e}{2\pi}\exp(-cn\xi)$ the following lower bound for $\eta'$ holds against the same $\gamma$-adversary:
	\[\eta' \geq \frac{\gamma(\eta + 1)\cdot \sqrt{\beta m}}{\gamma \cdot\sqrt{\beta m} + (\eta + 1)\cdot \sqrt{(1 + c)n \xi / 2}} - 1.\]
\end{theorem}

\begin{proof}[Sketch]
	The theorem is proved in two steps.

	First, we bound the probability that a specific attacking strategy corrupts more than $\beta f(\gamma; \mathcal{A}, \mu) + \sqrt{n\xi \cdot \beta m}$ in the new assignment $\mathcal{A'}$, where the probability is taken over the random sampling process of $\mathcal{A'}$.
	In particular, for an adversary with a fixed corruption set, let $X:=X(\mathcal{A'})$ be the random variable denoting the number of  groups in $\mathcal{A'}$ corrupted by that adversary.
	Then, with the hypergeometric tail bound, we lower bound $X$ as follows:
	\[\Pr_{\mathcal{A'}}\left[X \geq \beta \cdot f(\gamma; \mathcal{A}, \mu) + \sqrt{\left(\frac{1 + c}{2}\right)\cdot n\xi \cdot \beta m}\right] \leq \exp(-(1 + c)n\xi).\]

	Then, the following inequality holds by applying a union bound on all possible $\binom{n}{\gamma n}$ corrupting sets:
	\[\Pr_{\mathcal{A'}}\left[f(\gamma; \mathcal{A}', \mu) \geq \beta \cdot f(\gamma; \mathcal{A}, \mu) + \sqrt{\left(\frac{1 + c}{2}\right)\cdot n\xi \cdot \beta m}\right] \leq \frac{e}{2\pi}\exp(-cn\xi).\]

	Therefore, with probability at least $1-\frac{e}{2\pi}\exp(-cn\xi)$ there is $f(\gamma; \mathcal{A}', \mu) \leq \beta f(\gamma; \mathcal{A}, \mu) + \sqrt{n\xi \cdot \beta m}$,
	from which we conclude the following bound and finish the proof.
	\[\eta' \geq \frac{\gamma (\eta + 1)\cdot \sqrt{\beta m}}{\gamma \cdot \sqrt{\beta m} + (\eta + 1) \cdot\sqrt{(1 + c)n \xi / 2}} - 1,\]
	The complete proof is deferred to Appendix~\ref{app_pro_the_boo_ran}.
	\qed
\end{proof}

The following corollary follows Theorem~\ref{the_boo_ran} immediately.
\begin{corollary}
	Let $\mathcal{A}$ be a group assignment with efficiency factor $\eta$ against adversary controlling $s$ corrupted nodes.
	Let $\mathcal{A'}$ be the sampled group assignment from $\mathcal{A}$ with $(\eta + 1)n\xi / \gamma^2$ groups.
	Then, with probability at least $1 - \frac{e}{2\pi}\exp(-n\xi)$,
	the custody scheme induced by $\mathcal{A'}$ has efficiency factor $\eta' \geq \sqrt{\eta + 1} - 2$ against same adversary with $s$ corrupted nodes.
\end{corollary}

To illustrate the effect of the above sampling technique, we present the following two examples with concrete numbers.

\begin{example}[Sampling from symmetric designs]\label{exa_ran_all}
	Consider $\mathcal{A}_{all}$ with $n = 1,000$ and $k = 25$. Let $\mu = 2/3$ and $s = 428$ (or $\gamma = 0.428$).
	If we uniformly at random sample $88,695$ groups from $\mathcal{A}_{all}$ to form $\mathcal{A}'$,
	then by Theorem~\ref{the_boo_ran}, the sampled custody scheme has efficiency factor $\eta' \geq 5$ with probability $1 - \frac{e}{2\pi} \approx 0.5674$ over the random sampling process. Further, if $s = 388$ (or $\gamma = 0.388$) and $m'=323,825$ groups, then $\eta' \geq 10$ with probability $1 - \frac{e}{2\pi}$.
\end{example}

\begin{example}[Sampling from polynomial designs]\label{exa_ran_pol}
	Consider $\mathcal{A}_{poly}$ with $n = 961$, $k = 31$ and $d = 12$. Let $\mu = 2/3$ and $s = 314$ (or $\gamma \approx 0.3267$). If we uniformly at random draw $138,767$ groups from $\mathcal{A}_{poly}$ to form $\mathcal{A}'$,
	then by Theorem~\ref{the_boo_ran} there is $\eta' \geq 5$ with probability $1 - \frac{e}{2\pi} \approx 0.5674$ over the random sampling process.
	Further, if $s = 285$ (or $\gamma \approx 0.2966$) and sampling $m'=481,017$ groups, then $\eta' \geq 10$ with probability $1 - \frac{e}{2\pi}$.
\end{example}
\section{Constructions of Group Assignments}\label{sec_des}

In this section, we propose three types of group assignments and analyze the performance of resultant custody schemes.
We also provide empirical analysis of these schemes with concrete numbers for a better understanding.

\subsection{Type 1: Symmetric Design}\label{sec_des_all}

\begin{construction}\label{con:sym}
    Given $n$ and $k$, let $\mathcal{A}_{all}$ be a family consisting of all size-$k$ subsets of $S$ as custodian groups,
    i.e. $\mathcal{A}_{all}$ is an assignment with $m = \binom{n}{k}$ groups where each group has $k$ nodes.
    Then for every authentication threshold $\mu$,
    a custody scheme can be constructed from $\mathcal{A}_{all}$.
\end{construction}

Since all nodes are symmetric in $\mathcal{A}_{all}$,
it immediately follows that the number of corrupted groups in the above custody scheme only depends on the number of corrupted nodes.
Thus it suffices to consider the adversary corrupts any set of $\gamma n$ nodes,
and the number of corrupted groups can be calculated as follows:
\begin{equation}
    f(\gamma; \mathcal{A}, \mu) =
    \sum_{r\le t\le k} \binom{\gamma n}{t}\binom{n-\gamma n}{k-t}
    =  \binom{n}{k} \cdot \sum_{t = r}^{k} \frac{\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}}{\binom{n}{k}}.
 \end{equation}

By Definition~\ref{def_sec} and recalling $m = \binom{n}{k}$,
the custody scheme is $\gamma$-reliable if and only if:
\begin{equation*}
    \gamma \geq \frac{f(\gamma; \mathcal{A}, \mu)}{m} = \sum_{t = r}^{k} \frac{\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}}{\binom{n}{k}},
\end{equation*}
and the efficiency factor $\eta$ turns out:
\[\eta =\frac{\gamma m - f(\gamma; \mathcal{A},\mu)}{f(\gamma; \mathcal{A},\mu)} = \frac{\gamma \binom{n}{k}}{\sum_{t = r}^{k}\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}} - 1.\]

The reliability of $\mathcal{A}_{all}$ against adversary corrupting exactly $\gamma n$ nodes naturally implies to security against adversary corrupting $\le \gamma n$ nodes for reasonable $\gamma$,
as proved in the following lemma.
For typical choice of $\mu \geq 1/2$ and $\gamma < 1-k/n$,
the translation from reliability to security holds for
$\gamma < \mu-\frac{1}{2(k-1)}$.

\begin{lemma}\label{lem_des_all}
    Suppose $\mathcal{A}_{all}$ is a group assignment following Construction~\ref{con:sym} with parameters $n$ and $k$.
    If the custody scheme derived from $\mathcal{A}_{all}$ and any authentication threshold $\mu$ is $\gamma$-reliable
    and $\gamma \leq \min\left\{\frac{\mu k - 1}{k - 1} + \frac{1}{n}, 1 - \frac{k}{n}\right\}$,
    then it is secure against $\gamma$-adversary (i.e. $\gamma'$-reliable for every $\gamma'\le \gamma$).
\end{lemma}

The proof of Lemma~\ref{lem_des_all} is obtained by comparing $\eta$ for adversary corrupting $s$ nodes and $s-1$ nodes.
See Appendix~\ref{app_pro_lem_des_all} for the complete proof.

Based on Lemma~\ref{lem_des_all},
we prove that $\mathcal{A}_{all}$ is secure for $\gamma$ close to $1/2$ and appropriately large $k$.
\begin{theorem}\label{the_des_all}
    When $\mu \geq 1/2$, $k \geq 10$ and $n \geq 2k$, the custody scheme derived from $\mathcal{A}_{all}$ and $\mu$ is secure against $\gamma_{all}$-adversary, for $\gamma_{all}$ defined as follows:
    \[\gamma_{all} := \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}.\]
\end{theorem}
\begin{proof}[Sketch]
    We first show that when $n \geq 2k$ and $k \geq 10$, the system is reliable for $\gamma \in [\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k}, \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}]$. In fact, recall that the system is secure as long as
    \[\gamma \geq \sum_{\mu k < t \leq k} \frac{\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}}{\binom{n}{k}},\]
    and by the tail bound of hypergeometric distribution, it is sufficient with
    \[\gamma \geq \exp(-kD(\mu \| \gamma)) \geq \sum_{\mu k < t \leq k} \frac{\binom{\gamma n}{t}\binom{n - \gamma n}{k - t}}{\binom{n}{k}}.\]

    By the property of Kullbeck-Leibler divergence on two real numbers, we can obtain the above if we have
    \[\gamma \geq \left(4\gamma (1 - \gamma)\right)^{k/2} \geq \exp(-kD(\mu \| \gamma)),\]
    which establishes as long as $\gamma \in [\frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{k}, \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k}]$, $\mu > 1/2$, $k \geq 10$ and $n \geq 2k$.

    Lemma~\ref{lem_des_all} shows that as long as the system is reliable w.r.t $\gamma < \frac{1}{2} - \frac{1}{\sqrt{k}} - \frac{1}{2k} < \min\left\{\frac{\mu k - 1}{k - 1} + \frac{1}{n}, 1 - \frac{k}{n}\right\}$, then the system is secure against $\gamma$-adversary. Therefore, we finish the proof.
    The complete proof of this theorem is deferred to Appendix~\ref{app_pro_the_des_all}.
    \qed
\end{proof}

\begin{figure}[!htbp]
    \centering
    \subfigure[]{\includegraphics[scale=0.15]{Sections/Figures/all_1_2.png}\label{fig_des_all_1}}
    \subfigure[]{\includegraphics[scale=0.15]{Sections/Figures/all_2_3.png}\label{fig_des_all_2}}
    \caption{The efficiency factor $\eta$ versus the corrupted fraction $\gamma$ for $\mathcal{A}_{all}$ as in Construction~\ref{con:sym}. In particular, $\eta<0$ if the custody scheme is not secure for corresponding $\gamma$.}
    \label{fig_des_all}
\end{figure}

Fig.~\ref{fig_des_all} depicts the relation between efficiency factor $\eta$ and adversary corrupted fraction $\gamma$,
for $n\in\{20,50\}$, $k\in\{6,7\}$, and $\mu\in\{1/2, 2/3\}$.
From this figure we can see that with fixed $n$, $k$ and $\mu$, the efficiency factor $\eta$ decreases as $\gamma$ grows. Further, for combinations of reasonably large $n$ and $k$,
the efficiency factor $\eta$ can be more than $10$ while $\gamma$ is roughly $1/3$.
For instance,
when $n = 20$, $k = 6$ and $\mu = 2/3$ as in Fig.~\ref{fig_des_all_2},
there is $m = \binom{20}{6} = 38,760$ and the efficiency factor $\eta = 21.1486$ against adversary with power $\gamma = 2/5$.

Fig.~\ref{fig_des_all_ano} depicts the behavior of the efficiency factor $\eta$ versus the custodian group size $k$, for $n \in\{20, 50\}$, $\mu \in\{1/2, 2/3\}$ and $\gamma \in\{1/5, 1/4, 1/3\}$.
The figure shows in general $\eta$ increases with $k$ in custody schemes induced by $\mathcal{A}_{all}$.
The sawteeth appears on the curves because of the rounding of $r$ and $s$,
i.e. the authentication threshold and the number of corrupted nodes.

\begin{figure}[!ht]
    \centering
    \subfigure[]{\includegraphics[scale=0.2]{Sections/Figures/all_another_20_1_2.png}\label{fig_des_all_ano_1}}
    \subfigure[]{\includegraphics[scale=0.2]{Sections/Figures/all_another_20_2_3.png}\label{fig_des_all_ano_2}}
    \subfigure[]{\includegraphics[scale=0.2]{Sections/Figures/all_another_50_1_2.png}\label{fig_des_all_ano_3}}
    \subfigure[]{\includegraphics[scale=0.2]{Sections/Figures/all_another_50_2_3.png}\label{fig_des_all_ano_4}}
    \caption{The efficiency factor $\eta$ versus the custodian group size $k$ for $\mathcal{A}_{all}$ as in Construction~\ref{con:sym}. Blank points on the right side refer to $\eta=\infty$ when adversary cannot corrupt even a single group.}
    \label{fig_des_all_ano}
\end{figure}

Finally we remark that the construction of $\mathcal{A}_{all}$ by itself is mainly a theoretical result.
Because the size of such group assignment $m = \binom{n}{k}$ grows too fast and hence $n$ and $k$ must be severely bounded in practice,
e.g. $n \sim 20$ and $k \sim 5$.
Otherwise it would be too expensive or even impossible to manage
the custody scheme consisting of $m$ custodian groups.
A solution to mitigate the above issues is by random sampling,
as exhibited in Section~\ref{sec_boo}.

\subsection{Type 2: Block Design}\label{sec_des_blo}

In this section, we consider group assignment schemes induced by block designs (see Section~\ref{sec_pre} for necessary preliminaries).
In fact, block designs naturally extend Construction~\ref{con:sym},
in the sense that $\mathcal{A}_{all}$ is a degenerated block design with $\lambda = 1$.
In what follows, a ``block'' in the block design is also called a ``group'' in the group assignment scheme.

The following lemma shows the effectiveness of block designs:
\begin{lemma}\label{lem_des_blo}
    For every $r$-$(n, k, \lambda)$-design and $\mu=r/k$,
    the induced custody scheme is $\gamma$-reliable with efficiency factor $\eta$ lower bounded as follows:
    \[\eta \geq \frac{s}{n}\cdot \left. \frac{\binom{n}{r}}{\binom{k}{r}} \middle/ \min\left\{\binom{s}{r}, \frac{\binom{n}{r}}{\binom{k}{r}}\right\}\right. - 1.\]
\end{lemma}

The above lemma holds since with $s=\gamma n$ corrupted nodes,
the adversary controls at most $\lambda\cdot \binom{s}{r}$ custodian groups out of $m = \lambda\cdot \binom{n}{r}/\binom{k}{r}$ groups in total.

Fig.~\ref{fig_des_blo} shows the lower bound of $\eta$ obtained by Lemma~\ref{lem_des_blo} versus the adversary's power $\gamma$ for different block designs with $\mu=(r-1)/k$.

\begin{figure}[!htbp]
    \centering
   	\includegraphics[scale=0.25]{Sections/Figures/block_design.png}
    \caption{The lower bound on $\eta$ by Lemma~\ref{lem_des_blo},  versus the corrupted fraction $\gamma$, when $\mu=(r-1)/k$.
    All four designs shown in this figure have explicit constructions~\cite{Stinson07}. $\eta<0$ if the custody scheme is not secure for corresponding $\gamma$.}
    \label{fig_des_blo}
\end{figure}

Resembling what we do in Section~\ref{sec_des_all}, we prove that block designs are always reliable with properly small $\gamma$.
\begin{theorem}\label{the_des_blo}
    Let $s = \gamma n$ be the number of corrupted nodes and $\mu=(r-1)/k$.
    Suppose we have $\mu \geq 1/2$, $r > \mu k \geq 2$ and $n \geq 3k - 3$. The custody scheme induced by an $r$-$(n, k, \lambda)$-design is $\gamma$-reliable
    as long as $\binom{s}{r} \leq \left. \binom{n}{r} \middle/ \binom{k}{r} \right.$ and $s \leq \frac{n}{k}\mu^{\frac{1}{r - 1}} + r - 1$.
    Furthermore, the reliability is monotone in $\gamma$ and hence it immediately translates to security against adversary corrupting up to $\gamma n$ nodes.
\end{theorem}
\begin{proof}[Sketch]
	We consider the lower bound of the efficiency factor $\eta$ given by Lemma~\ref{lem_des_blo}. Under the condition that $\binom{s}{r} \leq \left. \binom{n}{r} \middle/ \binom{k}{r} \right.$, the system is reliable when
	\[\frac{s}{n}\frac{\binom{n}{r}}{\binom{k}{r}\binom{s}{r}} \geq 1.\]

	A key observation is that,
	\[\frac{s}{n}\frac{\binom{n}{r}}{\binom{k}{r}\binom{s}{r}} = \prod_{t = 1}^{r - 1}\frac{(n - t)(r - t)}{(s - t)(k - t)} \cdot \frac{r}{k} > \prod_{t = 1}^{r - 1}\frac{(n - t)(r - t)}{(s - t)(k - t)} \cdot \mu.\]
	With the above observation we conclude the following holds for any $1 \leq t \leq r - 1$,
	\[\frac{(n - t)(r - t)}{(s - t)(k - t)} \geq \mu^{-\frac{1}{r - 1}}.\]

	Therefore,
	\[\frac{s}{n}\frac{\binom{n}{r}}{\binom{k}{r}\binom{s}{r}} > \prod_{t = 1}^{r - 1}\frac{(n - t)(r - t)}{(s - t)(k - t)} \cdot \mu \geq \left(\mu^{-\frac{1}{r - 1}}\right)^{r - 1} \cdot \mu = 1.\]

	The full proof of the theorem is deferred to Appendix~\ref{app_pro_the_des_blo}.
	\qed
\end{proof}

Theorem~\ref{the_des_blo} guarantees the security of the custody scheme for proper $\gamma$.
Although Lemma~\ref{lem_des_blo} does not provide an ideal lower bound estimation for large $\gamma$ (see Fig.~\ref{fig_des_blo}),
we still manage to achieve some satisfying results.
In particular, using the custody scheme induced from the $5$-$(24, 8, 1)$-design with $m = 759$ custodian groups with $\mu = 1/2$,
the efficiency factor $\eta \ge 30.6250$ for $\gamma = 1/4$.
This significantly outperforms the symmetric design $\mathcal{A}_{all}$,
which has $m = 38,760$ and $\eta = 16.9444$ when $n = 20$, $k = 6$, $\mu=1/2$ and $\gamma = 1/4$
(see Fig.~\ref{fig_des_all_1}).

\subsection{Type 3: Polynomial Design}\label{sec_des_pol}

In this section, we propose another way to construct group assignments
using polynomial-based combinatorial designs.

\begin{construction}\label{con:poly}
    For a prime $k$ and fixed positive integer $d < k$,
    let $S = \{(a, b) \;|\; a, b \in \mathbb{Z}/k\mathbb{Z}\}$
    be the set of $n=k^2$ elements in $(\mathbb{Z}/k\mathbb{Z})^2$.
    The polynomial design of group assignment $\mathcal{A}_{poly}$ is a family of $m = k^{d}$ subsets of $S$ defined as follows:
    \begin{align}
        \mathcal{A}_{poly} &:= \left\{ A_p \;|\; \text{$p$ is degree-$d$ monic polynomials over $\mathbb{Z}/k\mathbb{Z}$} \right\},
    \end{align}
    where

        $A_p := \left\{(0, p(0)), (1, p(1)), \cdots, (k - 1, p(k - 1))\right\}$.

    For every authentication threshold $\mu$,
    a custody scheme can be constructed from $\mathcal{A}_{poly}$.
\end{construction}

It is easy to verify that $\mathcal{A}_{poly}$ consists of $m$ distinct groups,
and the intersection of any two distinct groups in $\mathcal{A}_{poly}$ is bounded by $d$,
following the Fundamental Theorem of Algebra.
\begin{equation}\label{ieq:ApAq}
    \forall A_p,A_q\in\mathcal{A}_{poly} \land A_p\ne A_q
    \implies |A_p\cap A_q| < d.
\end{equation}

Hence, we lower bound the efficiency factor of custody schemes in Construction~\ref{con:poly} as below.
\begin{lemma}~\label{lem_des_pol_aug}
	The efficiency factor $\eta$ for $\mathcal{A}_{poly}$ as in Construction~\ref{con:poly} is lower bounded as follows:
	\[\eta \geq {\gamma^{1 - d} \cdot \binom{r}{d}}\Big/{\binom{k}{d}} - 1.\]

\end{lemma}

We say a subset of $S$ is \emph{first-entry-unrepeated} if all nodes in the subset are with different first entry. Let $\mathcal{M}$ denote the set of corrupted nodes, then the number of size-$d$ first-entry-unrepeated subsets of $\mathcal{M}$ is upper bounded by $\binom{k}{d} (s / k)^d$. By (\ref{ieq:ApAq}), every size-$d$ first-entry-unrepeated subset of $\mathcal{M}$ appears in at most one corrupted group. On the other hand, every corrupted group contains at least $r$ corrupted nodes all with different first entry, and hence $\ge \binom{r}{d}$ size-$d$ first-entry-unrepeated subsets. For the full proof of Lemma~\ref{lem_des_pol_aug}, please see Appendix~\ref{app_pro_lem_des_pol_aug}.

In the following theorem, we analyze the security of custody schemes in Construction~\ref{con:poly}.
\begin{theorem}\label{the_des_pol_aug}
	Let $d = \nu k$, then the custody scheme derived from $\mathcal{A}_{poly}$ is secure against $\gamma_{poly}$-adversary for $\gamma_{poly}$ defined as:
		\[\gamma_{poly} := \left(\frac{2\pi}{e^{d + 2}}\sqrt{\frac{(1 - \nu)\mu}{\mu - \nu}}\left(\frac{\mu^{\mu}}{(\mu - \nu)^{\mu - \nu}}\right)^k\right)^{\frac{1}{d - 1}}.\]
\end{theorem}
\begin{proof}[Sketch]
	By Lemma~\ref{lem_des_pol_aug}, the custody scheme remains reliable as long as
	\[\gamma^{d - 1} \leq \left. \binom{r}{d} \middle/ \binom{k}{d} \right..\]

	The binomial term can be lower bounded using Stirling's formula,
	which turns out:
	\[\left. \binom{r}{d} \middle/ \binom{k}{d} \right. \geq \frac{2\pi}{e^{d + 2}}\sqrt{\frac{(1 - \nu)\mu}{\mu - \nu}}\left(\frac{\mu^{\mu}}{(\mu - \nu)^{\mu - \nu}}\right)^k.\]
	We prove the theorem by letting the right hand side of above formula no less than $\gamma^{d - 1}$. The full proof with complete calculation is deferred to Appendix~\ref{app_pro_the_des_pol_aug}.
	\qed
\end{proof}

As an instance of Theorem~\ref{the_des_pol_aug},
the custody scheme with $n = 49$, $k = 7$, $d = 3$ and $\mu = 1/2$ is secure against adversary with power $\gamma \leq 0.1673$,
or equivalently the number of compromised nodes $s \leq 8$.

\begin{figure}[!htbp]
	\centering
	\subfigure[]{\includegraphics[scale=0.15]{Sections/Figures/poly_1_2_new.png}\label{fig_des_pol_1}}
	\subfigure[]{\includegraphics[scale=0.15]{Sections/Figures/poly_2_3_new.png}\label{fig_des_pol_2}}
	\caption{The lower bound for the efficiency factor $\eta$ (by Lemma~\ref{lem_des_pol_aug}) versus the corrupted fraction $\gamma$, for $\mu=1/2$ and $\mu=2/3$. Recall that $n = k^2$ in $\mathcal{A}_{poly}$ and $\eta<0$ if the custody scheme is not secure for corresponding $\gamma$.}
	\label{fig_des_pol}
\end{figure}

Fig.~\ref{fig_des_pol} depicts the relation between the lower bound of $\eta$ by Lemma~\ref{lem_des_pol_aug} and the adversary corruption factor $\gamma$,
for $\mu \in \{1/2, 2/3\}$ and $n,k,d$ as shown in the figure.
It is easy to see that $\eta$ increases as $n,k$ and $d$ become larger.
For specific choices we get $\eta \geq 20.9094$ against adversary with $\gamma = 3/11$,
when $\mu = 2/3$ and $\mathcal{A}_{poly}$ is parameterized by $n = 121$, $k = 11$ and $d = 5$.
Furthermore, we remark that the efficiency factor $\eta$ increases rapidly when $\gamma$ decreases. For instance,
$\eta \ge 109.9166$ when reducing $\gamma$ from $3/11$ to $2/11$ in the above example.
That is, the efficiency factor increased by $5$ times at the cost of relaxing the tolerance of $33$ corrupted nodes down to $22$.

\section{Discussion}\label{sec_dis}

There are still other ways that may enhance the performance of a group assignment scheme. For example, we may involve some drawer-like consensus mechanism so that we can include more nodes in the system. However, such skill may largely damage the efficiency of the protocol. Aside from introducing randomness (in Section~\ref{sec_boo}), seeking extending ways to boost the performance of a group assignment scheme is left as a future work.

In Section~\ref{sec_hard}, we have shown that given a group allocation scheme, it is generally NP-hard for the adversary to figure out the best attacking strategy. Nevertheless, we give a deterministic algorithm to figure out a corruption strategy such that the number of compromised groups is above average. In later works, we will discover an approximation algorithm for such problem. Combining the result with the uniform sampling strategy, we can figure out whether a sampling instance meets our requirement.
\section{Hardness Results}\label{sec_hard}

In this section, we consider the hardness issue of finding the best corrupting scheme. In general, with a common group assignment scheme $\mathcal{A}$, it is hard for the polynomial-time adversary to figure out the best attack strategy.
\begin{theorem}\label{the_hard}
    Take $k$ and $r$ as predetermined constants, then, with the group assignment scheme $\mathcal{A}$ which includes $n$ nodes and the group number $m$ be within a polynomial in $n$, and the adversary controlling $s := \gamma n = n^{\Omega(1)}$ nodes, we have the following results:
    \begin{itemize}
        \item When $1 \leq r < k$, it is NP-hard to find the optimal attacking strategy.
        \item When $r = k$, under the Small Set Expansion Conjecture~\cite{RaghavendraST12}, it is NP-hard to find the optimal attacking strategy.
    \end{itemize}
\end{theorem}
\begin{proof}[Sketch]
	To show the NP-hardness of the problem with $1 < r < k$, we consider the MAX $s$-VC problem; for the case of $r = k$, we consider the fixed cost minimum edge cover (FCMC) problem defined in~\cite{GandhiK15}. For the details on the reduction step, please refer to Appendix~\ref{app_pro_the_hard}.
	\qed
\end{proof}

Theorem~\ref{the_hard} shows that generally, it is hard for the computationally bounded adversary to figure out the best attacking strategy. Nevertheless, there is a deterministic algorithm for the adversary to figure out a strategy which corrupts at least an average amount of groups. Let $\kappa := \Pr[\mathcal{H}(n, s, k) \geq r]$, recall that $\kappa m$ is the expected amount of groups the adversary can corrupt when the $\gamma n$ corrupted nodes are chosen uniformly at random. We have the following theorem:
\begin{theorem}\label{the_hard_con}
    Let $\kappa$ be defined as above. Suppose computing each binomial coefficient takes time $O(1)$. Then there is a deterministic algorithm that gives an attacking strategy which corrupts at least $\kappa m$ groups, running in time $O(kmn)$.
\end{theorem}
\begin{proof}[Sketch]
	Specifically, we construct an $O(kmn)$ deterministic algorithm (see Algorithm~\ref{alg_hard}) and prove that the algorithm always return a corrupting strategy no beneath the average. Specifically, in each step, we judge whether or not to corrupt a node conditioning on previous choices. We prove that after each step before the algorithm ends, the conditional expectation of the number of corrupted groups is no less than average given previous decisions. Hence the algorithm always returns a solution no worse than average. For the construction of the algorithm and full proof, please see Appendix~\ref{app_pro_the_hard_con}.
	\qed
\end{proof}

\section{Introduction}\label{sec_intro}

Custody is a core financial service in which
an institution, known as the custodian, holds in safekeeping assets such as stocks, bonds, precious metals and currency on behalf of the client.
Custody service reduces the risk of clients losing their assets or having them stolen,
and in many scenarios a third party custodian is required by regulation to avoid systematic risk.
In general, security is the most important reason why people use custody service and place their assets for safekeeping in custodian institutions.

The security of traditional custody service is usually endorsed by the reputation of the custodian,
together with the legal and regulatory system.
Such centralized endorsement used to be the only viable option until the emergence of digital assets.
A major advantage of digital assets over their physical counterparts is that they are intrinsically integrated with information technology such as Internet and modern cryptography.
Along with the evolution of cryptographic authentication technology, e.g. multiple/threshold signature scheme and zero-knowledge proof systems,
it becomes technically feasible to have in safekeeping assets held by multiple custodians,
so that no single custodian is able to use the assets covertly.

From a systematic point of view,
custody service provided by a federation of multiple independent custodian has better robustness and resistance against single point failure,
and hence achieves a higher level of security.
Such credit enhancement is especially important for safekeeping of cryptoassets on decentralized blockchains such as Bitcoin~\cite{Nakamoto08} and Ethereum~\cite{Wood14},
where the legal and regulatory system is absent or at least way behind the development of applications.
For example, the largest cryptocurrency exchange at that time,
Mt. Gox, announced that approximately 850,000 bitcoins were stolen and went bankrupt in 2014~\cite{web_mtg};
and in the year $2019$ alone, at least $7$ cryptocurrency exchanges claimed being hacked and loss of cryptoassets totaled to around $1.39$ billion dollars~\cite{web_hacked}.
However, it is difficult for customers to distinguish that whether the claimed loss was caused by hacker attack or internal fraud and embezzlement,
and hence raises the need for decentralized custody.

Decentralized custody finds applications in many scenarios related to blockchain and digital finance.
A motivating example is the \emph{cross-chain asset mapping} service which maps cryptoassets on one blockchain to tokens on another blockchain for inter-chain operability.
For instance, the mapping from Bitcoin to Ethereum
enables usage of tokens representing bitcoins within Ethereum ecosystem,
and in the meanwhile, the original bitcoins must be safeguarded so that the bitcoin tokens are guaranteed redeemable for real bitcoins in full.
Nowadays the volume of cryptoassets invested into Ethereum DeFi applications has been increasing at an extraordinary pace and broke two billion dollars recently \cite{web_defi},
among which a significant fraction (e.g. hBTC~\cite{hBTC}, imBTC~\cite{imBTC}, tBTC~\cite{tBTC}, wBTC~\cite{wBTC}, renBTC~\cite{renBTC}, etc.) is mapped from Bitcoin.
Due to the reality that most of those DeFi applications and tokens remain in a gray area of regulation,
decentralized cryptoasset custody (within or across institutions) turns out an attractive approach for better security and credit enhancement.

In this work, we propose a framework of decentralized asset custody scheme which is secure in the game-theoretic sense.
More specifically, custodians and assets are distributed into multiple custodian groups,
where each group consists of few custodians as its members and fully controls a small portion of in safekeeping assets.
The authentication of each custodian group can be implemented with voting or threshold signature among group members.
Under this framework transactions can be processed more efficiently within group members,
since the computational and communicational cost is significantly reduced.
The liveness and robustness is also improved since even a single alive custodian group is able to process some transactions.

The security of our proposed custody scheme is guaranteed in a game-theoretic sense:
every custodian in this scheme must offer a fund as security deposit,
and the system remains secure as long as an adversary cannot steal more asset than his deposit,
i.e. comparing to launching an attack the adversary would be better off by just withdrawing the security deposit of custodian nodes under his control.
Specifically, we prove that for adversary corrupting a bounded fraction of custodians,
the proposed decentralized custody scheme is able to safeguard customer assets of multiple times value of the total security deposit.

\subsection{Related Works}

The prototype of decentralized custody scheme first appears in Bitcoin as multisignature (multisig) \cite{web_multisig},
where the authentication requires signatures from multiple private keys rather than a single signature from one key.
For example, an $M$-of-$N$ address requires signatures by $M$ out of totally $N$ predetermined private keys to move the money.
This na\"{i}ve scheme works well for small $M$ and $N$ but cannot scale out,
because the computational and communicational cost of authenticating and validating each transaction grows linearly in $M$ and $N$.
Both efficiency and liveness of the scheme are compromised for large $M$ and $N$, especially in the sleepy model proposed by Pass and Shi~\cite{PS17} where key holders do not always response in time.
In practice, multisignature scheme is typically used at wallet level rather than as a public service,
since the scheme becomes costly for large $N$ and most Bitcoin wallets only support $N\le 7$.

Multisignature schemes may be coupled with advanced digital signature techniques such as threshold signature~\cite{GagolKSS20,BonehGG17} or aggregate signature~\cite{schnorr1991efficient,bellare2006multi,maxwell2019simple}
to reduce the cost of verifying multi-signed signatures.
However, the signing process still requires involvement of at least $M$ parties and the cost of communication can hardly be significantly reduced.
Furthermore we remark that these advanced signature techniques are also compatible with our scheme,
as authentication mechanism for single custodian groups.

There are also custody solutions based on scripts or contract codes. These schemes usually only work within a single blockchain since it is difficult to get reliable information outside the consensus boundary, which essentially requires an oracle.
Although there are techniques such as Atomic Swap~\cite{web_ato} and Hashlock/Hash TimeLock Contracts (HTLC)~\cite{web_multisig} enabling code-based cross-chain interoperability,
the use cases are limited and far from being able to provide general purpose custody service.

As for the cross-chain asset mapping service,
existing solutions include following three types:
\begin{itemize}
	\item Centralized: custody in a trusted central authority, with the endorsement fully from that authority, e.g.
	hBTC~\cite{hBTC}, wBTC~\cite{wBTC} and imBTC~\cite{imBTC};

	\item Consortium: custody in multisignature accounts controlled by an alliance of members, and endorsed by all alliance members, e.g. cBTC~\cite{cBTC} (in its current version) and Polkadot~\cite{Wood16};

	\item Decentralized (with deposit/collateral):
	custody provided by permissionless custodians,
	with security guaranteed by over-collateralized cryptoassets,
	e.g. tBTC~\cite{tBTC} and renBTC~\cite{renBTC}.
\end{itemize}
Although the last type seems satisfiable in decentralization and security against single point failure and collusion,
there are significant drawbacks as well:
the first drawback is the inefficiency of over-collateralization,
i.e. tBTC requires the custodian to provide collateral worth of $150\%$ value of customer's assets,
and renBTC requires $300\%$;
the second drawback is that the collateral is not the same type as the in safekeeping assets,
and hence it may be insufficient to endorse safety of the custody service in market volatility.

Furthermore, we remark that tBTC and renBTC have security guaranteed in the game-theoretic sense that an adversary will not launch a non-profitable attack,
and renBTC even partition custodians (i.e. Darknodes in its context) into groups for better efficiency and liveness.
However, renBTC applies the trivial non-overlapping group partition and hence it has poor capital efficiency.
More importantly, it cannot support homogeneous collateral as in safekeeping assets,
since otherwise an adversary corrupting a single group will be able to control more assets than his own security deposit.

\subsection{Our Contributions}\label{sec_intro_con}

In this work, we propose the framework of implementing decentralized asset custody scheme with overlapping group assignments, where such group assignment consists of many subsets of custodians as groups,
and each group is controlled by few group members and holds a small faction of the total assets including both funds from customers and security deposit from custodians.

By distributing in safekeeping assets into many small custodian groups,
every customer-requested transaction can be assigned to a specific custodian group and thereafter processed within the group members.
Thus each transaction only requires attention and approval from custodians in that small group (rather than a majority of all participants in the scheme),
which reduces the cost and latency of transaction processing.
Furthermore this framework provides better liveness guarantee,
since transaction can be processed even if only one single custodian group has sufficient many members available online,
and in the mean while the vast majority of custodians in the system can stay offline.

Our custody scheme achieves security in the game-theoretic sense that for an adversary corrupting $\gamma$ fraction of individual custodians and $\gamma$ is not too large,
the number of corrupted groups would be less than $\gamma$.
Therefore, the adversary cannot jeopardize the system as long as the total security deposit of corrupted custodians outweighs the total assets held by corrupted groups,
since any loss caused by such an adversary can be easily compensated with security deposits of misbehaved custodians.

The model of our decentralized custody scheme is formalized in Section~\ref{sec_mod},
where we formally define security of a decentralized custody scheme.
Furthermore we introduce the notion of efficiency factor $\eta$ to measure the capital efficiency, which measures the capability of safely holding assets for exterior customers with a fixed total amount of security deposit.

We propose in Section~\ref{sec_des} specific constructions of the underlying group assignments based on enumeration of all subsets of a fixed size and two kinds of combinatorial designs respectively.
We also analyze the security and efficiency factors of custody schemes induced by these constructions.
For example, we show it is possible to assign $20$ custodians into $38,760$ groups such that as long as adversary corrupts $\gamma\le 2/5$ fraction of all custodians,
the whole custody scheme is capable of safekeeping assets worthy of $\eta>20$ times of total security deposits, i.e. the scheme can safely hold over $100$ units of value with total security deposit of $5$ unit.
Furthermore, based on the polynomial combinatorial design,
the decentralized custody scheme is able to support $121$ participants as custodians with $161,051$ groups such that the efficiency factor $\eta>60$ against any adversary corrupting no more than $2/11$ of custodians.
In general, the efficiency factor is better for larger number of participants and groups,
except for the drawback that the number of groups grows polynomially in the number of participants and hence soon becomes infeasible to manage in practice.

To mitigate the problem of too many groups in one assignment,
we apply a random sampling on the group assignment and prove that with high probability the newly sampled assignment has a comparable efficiency factor.
More specifically,
if the original custody scheme consists of $n$ participants and has the efficiency factor $\eta$ against adversary corrupting at most $\gamma$ faction of all participants,
then by sampling ${O}\left( n \eta \cdot \log(\gamma^{-1})/\gamma \right) \sim {O}\left( n \eta\right)$ many groups the newly generated custody scheme would have efficiency factor $\eta'\ge \sqrt{\eta+1}-2$ against the same adversary with high probability.
See Section~\ref{sec_boo} for the precise statement and more details.

Concretely, using the random sampling technique we are able to construct a custody scheme of $1000$ participants and $323,825$ groups such that
the efficiency factor $\eta>10$ against adversary corrupting up to $388$ participants.

In Section~\ref{sec_hard} we investigate the complexity of finding optimal corrupting solutions.
We prove that given a group assignment,
it is easy to find a solution no worse than average case but it turns out NP-hard to find an optimal corrupting strategy in general.
However, this is still insufficient to complement the randomized sampling construction as a validation method.

\section{Introduction}\label{sec_intro}

\subsection{Background and Motivation}\label{sec_intro_bac}

In the past decade, a surge of interest on cryptocurrencies and the underlying blockchain techniques have emerged, tracing back to the great success of Bitcoin, the digital currency proposed by Nakamoto~\cite{Nakamoto08}. The core idea of Bitcoin and subsequent cryptocurrencies, for example, Ethereum~\cite{Wood14}, is decentralization. Traditional modes of currency circulation, e.g., bank transfer, always require a central authority to verify and record a transaction. Hidden trouble under such mechanisms is that a single entity may suffer from intentionally severe attacks or simply commit a malicious behavior, which will result in an irretrievable impact on users. In contrast, in a decentralized setting, even if a minority of nodes fail due to crash or some means of attack, the whole system remains safe. In the financial scene, the idea of decentralization can greatly reduce the power of the single authority. This is the main reason why these cryptocurrencies are getting welcomed by the community.

Nowadays, with a massive amount of cryptocurrencies in the market, a key problem we face is to have different cryptocurrencies recognize each other. Therefore, these cryptocurrencies are connected rather than each being an "isolated island". This issue is also known as "interoperability" in the literature and relative techniques are known as cross-chain techniques. Breakthroughs on this subject will further allow users to treat digital assets simply as real-world currencies without losing decentralization, e.g., currency exchange can be achieved. There are already lots of research in this field. For example, Atomic Swap~\cite{web_ato} realizes the exchanging of specific cryptocurrencies. Some other works focus on building a platform that provides interoperability among different blockchains with either homogeneous architectures~\cite{web_cos} or heterogeneous architectures~\cite{Wood16}. We recommend readers to a survey on these cross-chain techniques~\cite{ZamyatinAZKMKK19}.

This work is inspired by an important issue in the cross-chain field known as decentralized custody of digital assets. We take the example of Bitcoin and Ethereum to illustrate the problem. Suppose a user wants to trade some ETH for BTC with the same total value. The demand here is that the user should be able to redeem the same amount of ETHs back at any time. Due to technical limitations on the script of Bitcoin, we cannot directly apply existing skills like atomic swap to tackle the problem. The solution is to establish an account on Bitcoin, which is controlled externally by a smart contract on Ethereum. The smart contract is collaboratively running on multiple distributed nodes, who are in charge of temporarily keeping the asset of exterior users. In detail, these nodes will be shuffled into multiple groups, and each group will be responsible for maintaining a certain part of assets. Such contract is deemed as a \textit{bridge} across different cryptocurrencies.

When designing such a contract, the most essential issue to consider is security, or that a user can never lose any asset under malicious behaviors. There are two aspects related to security: 1) how can each group safely process and verify a transaction, and 2) how do we group these nodes. For 1), a common method is to apply threshold signature schemes, which guarantees that a transaction is acknowledged only when endorsed by a certain fraction of nodes within the group. In this work, we aim at solving 2). We remark here that 2) is much important for the efficiency of the protocol. To become an asset keeper, a node has to pledge a certain amount of tokens to fill the potential loss of users when the contract suffers from an attack. A good grouping strategy, or group assignment scheme, will reduce the bonds that are required for anyone to become an asset keeper, hence, enhance the flexibility of the contract, and attract more nodes to execute the protocol.

\subsection{Related Works}\label{sec_intro_rel}

Previous works on decentralized asset custody mainly focus on threshold signature schemes. Specifically, there has been an abundance of protocols for threshold ECDSA~\cite{BonehGG17,CanettiMP20,CastagnosCLST19,CastagnosCLST20,DalskovKOSS19,DamgardJNPO20,DoernerKLS18,DoernerKLS19,GagolKSS20,GennaroG18,GennaroGN16,Lindell17,LindellN18} that support any number of parties in a group and any threshold. These works can be viewed as complements of the group assignment schemes we cover in this work. Combining the two, we can build an integrated decentralized asset custody mechanism.

To the authors' knowledge, there is currently no work discussing group assignment schemes in the context of decentralized asset custody. As for existing protocols, wBTC~\cite{wBTC} and imBTC~\cite{imBTC} use a trusted central authority to hold custody over the created Bitcoin account. This is somehow, against the original purpose of Bitcoin and other cryptocurrencies to avoid centralization. At the same time, pBTC~\cite{pTokens} also relies on a trusted environment to execute the contract. Synthetic~\cite{sBTC}, adopt a decentralized method. However, the underlying asset is irredeemable to some extent. For tBTC~\cite{tBTC}, in its current version (v1), whenever a deposit request is created, the system will randomly select three signers as a group, and a transaction is admitted only when all three signers agree. As a result, for the sake of security, the total required bonds are at least 150\% of the lot size, which provides low efficiency in practice. For hBTC~\cite{hBTC}, such a bond will be 100\% of the total lot size, which is still not satisfying. renBTC~\cite{renBTC} applies a sharding technique. In renBTC, Darknodes(signers of the protocol) are shuffled into non-overlapping groups, known as shards, and each shard maintains the assets of a corresponding part of users. Such a strategy tends to be dangerous since only a small fraction of corrupted nodes can steal all the tokens managed by the shard. Therefore, renBTC demands bonds of 100K REN tokens to run a Darknode, which is about 900 million USD in the real market. Hence, renBTC is again, prone to centralization.

\subsection{Our Contributions}\label{sec_intro_con}

In summary, this work makes the following contributions:
\begin{itemize}
    \item To our knowledge, we are the first to model the problem of group assignment schemes in the context of decentralized asset custody. (See Section~\ref{sec_mod}.) With a threshold signature scheme as an oracle, we explicitly define the security of a group assignment scheme given a certain fraction of malicious nodes. When the scheme is secure to our definition, we further define the efficiency factor of the scheme, which indicates the least amount of tokens that signers need to pledge, given the total deposit from exterior users.
    \item We show the particularity on the security of group assignment schemes. Specifically, the value range of corrupted fraction for the system to be insecure may not be continuous, which differs from the previous consensus schemes~\cite{KatzK09,PeaseSL80}. Meanwhile, in general, there is no group assignment scheme that is always safe under any malicious fraction.
    \item We consider three concrete types of group assignment schemes: 1) including all possible subsets of $k$ distinct nodes; 2) block designs (see Section~\ref{sec_pre}); and 3) a design constructed with polynomials. For each of the three types, we show that the scheme is secure when the number of malicious nodes is within a certain threshold. (See Section~\ref{sec_des}.) In the meantime, for each of these types, when the system is secure, we give an accurate or lower bound on their corresponding efficiency factors, which indicates the performance of each scheme. Nevertheless, all these three schemes perform a lot better than previous works. We also give a numerical analysis for a recommendation on parameter choices.
    \item We show that applying randomness to a given group assignment scheme may further enhance its behavior. (See Section~\ref{sec_boo}.) Intuitively, one can largely reduce the number of groups to maintain, without losing too much on the efficiency of the scheme. We give an example to concretely show the power of randomness.
    \item At last, we prove that in general, given a group allocation scheme, it is NP-hard for the adversary to figure out the best attacking strategy. This result further guarantees the meanings of group allocation schemes in practice. (See Section~\ref{sec_hard}.) At the same time, we give a deterministic polynomial-time algorithm to find a corruption strategy which behaves no worse than average. In Section~\ref{sec_dis}, we further propose some interesting problems for future work.
\end{itemize}

Technically, when theoretically analyze each of the specific design, we repeatedly use hypergeometric tail bounds and Stirling's formula to give bounds on certain partial sums or factorials. For necessary preliminaries on these tools, please see Section~\ref{sec_pre} and~\ref{sec_pre}. These techniques are also applied when analyzing the power of randomness.

\section{Model}\label{sec_mod}

In this work we consider the decentralized custody scheme without relying on any trusted party.
More specifically, we investigate the feasibility that $n$ participants (a.k.a. $n$ \emph{nodes}) $S = \{1, 2, \cdots, n\}$ jointly provide the custody service,
such that the security is guaranteed as long as the number of corrupted participants is bounded by a fraction of $n$, e.g. the adversary cannot corrupt more than $n/3$ nodes simultaneously.
This assumption of existence of an honest majority is much milder than assuming a single party trusted by everyone, and hence it likely leads to better security guarantee in practice.

Furthermore, we consider the security of the custody scheme in a game-theoretic sense:
the adversary may corrupt multiple nodes, but he will not launch an attack if the profit does not exceed the cost of launching such an attack.
In other words, misbehavior of adversary nodes is not considered as breaking the security as long as the resultant damage is recoverable.
To increase the cost of attack and compensate potential loss caused by attacks,
we require every custodian in our scheme to provide a security deposit, which will be confiscated and used for compensation in case of misbehavior.
Thus, no rational adversary would ever launch an attack if the security deposit outweighs the revenue of a successful attack.

\medskip
\noindent\textbf{A trivial but useless solution.}
In the most trivial solution, the asset under custody can only be moved when approved by all custodians or at least a majority of them.
However, getting such an approval becomes expensive and even infeasible in practice as $n$ grows,
especially when honest participants may go off-line (as in the sleepy model~\cite{PS17}),
which renders the trivial scheme useless.
\medskip

Although the above solution is not satisfiable,
it does provide enlightening ideas for designing a better custody scheme.
The threshold authorization scheme guarantees that
the adversary cannot move any asset under custody if he does not control enough many nodes.
In a more general view, this is a particular case of game-theoretically secure schemes where
the adversary's security deposit outweighs his revenue of launching an attack
when the adversary has bounded power.
As long as this property is satisfied the custody scheme should be secure in the game-theoretic sense.

In particular, the following toy example shows feasibility of implementing our idea with multiple subsets of $S$ as custodian groups,
i.e. each subset of $S$ only controls a fraction of the total asset under custody.

\begin{example}[Toy example]\label{exa_con}
    Consider the case when $n=5$, total asset under custody is $10$, and total security deposit is $6\times 5 =30$.
    Let each of the $\binom{5}{3}=10$ triads of $S$ form a custodian group,
    and assign the asset under custody and the security deposit equally to every group, i.e. each custodian group controls $4$ units.
    If the asset controlled by each custodian group can be moved with approval of $2$ out of $3$ members in that group,
    then an adversary controlling $2$ nodes is able to corrupt exactly $3$ custodian groups.
    However, by controlling $3$ groups the adversary can only move $4\times 3 = 12$ units, which is no more than the security deposit of adversary nodes, which is also $12$.
    Thus the custody scheme for $n=5$ is secure against adversaries controlling no more than two nodes.
\end{example}

In what follows, we will formalize the model of decentralized custody scheme with asset distributed among custodian groups.

Let $S = \{1, 2, \cdots, n\}$ be the set of all nodes,
and let $\mathcal{A}$ denote the custodian group assignment,
which is a family of $m$ subsets of $S$.
We emphasize that these subsets do not have to be disjoint.
In fact, it is imperative to use overlapping subsets in any meaningful solution.

In this work we focus on the symmetric setting where every node provides the same amount of security deposit and every group in $\mathcal{A}$ is of the same size $k$.
We let a universal parameter $\mu \in [1/2, 1)$ denote the authentication threshold for every single custodian group,
i.e. with approval of \emph{strictly above} $\mu k$ group members the asset controlled by that group can be settled arbitrarily.
In particular, our discussion mainly focuses on $\mu = 1/2$ and $\mu = 2/3$,
corresponding to authentication with simple majority, and greater than $2/3$ majority respectively.
\footnote{$\mu \geq 1/2$ is the necessary and sufficient condition for Byzantine agreement under synchrony, i.e. when all members are well-connected~\cite{KatzK09}.
$\mu \geq 2/3$ is necessary and sufficient for Byzantine agreement under partial synchrony or asynchrony even
with digital signatures~\cite{PeaseSL80}.
We further remark that smaller $\mu$ implies less security but better liveness, e.g. when $\mu \to 1$ even a single corrupted member is able to block a custodian group.
However, the discussion of liveness is beyond the scope of this work.}
For simplicity we let $r=\lceil \mu k + \epsilon \rceil$ denote the smallest integer greater than $\mu k$,
and hence the authentication of every custodian group is essentially an $r$-of-$k$ threshold signature scheme.

We represent the adversary power with $\gamma \in (0, 1)$,
which refers to the fraction of corrupted nodes in $S$.
Specifically, we let
$s=\lfloor \gamma n \rfloor$ denote the number of corrupted nodes in $S$.
For succinctness we slightly abuse the notation and assume that $\gamma n$ is always an integer, i.e. $s=\gamma n\in \mathbb{N}$.
The adversary is allowed to adaptively select corrupted nodes and then get all information and full control of those nodes thereafter, as long as the number of corrupted node does not exceed $s$.
In case a group in $\mathcal{A}$ contains $\ge r$ corrupted nodes,
we say that group is corrupted.
Furthermore, we remark that the adversary has reasonably bounded computing power,
so that he cannot break cryptographic primitives such as digital signatures.

Given a custodian scheme with group assignment $\mathcal{A}$ and authentication threshold $\mu$, together with $\gamma$ for the bound of adversary power,
we use the function $f(\gamma; \mathcal{A},\mu)$ to denote the maximal number of groups that may be corrupted
by an adversary controlling up to $s=\gamma n$ nodes (although it is indeed NP-hard to find the optimal attacking strategy in general, as discussed in Section~\ref{sec_hard}).
Formally,
\begin{equation}
    f(\gamma; \mathcal{A},\mu) := \max_{B\subseteq S: |B|=\gamma n}

    \big|\{ A\in \mathcal{A} \;\big|\; | A \cap B|\ge \mu k \}\big|.

\end{equation}

From $f(\gamma; \mathcal{A},\mu)$ we define the security of this specific custody scheme as follows:

\begin{definition}[Security of Custody Schemes]\label{def_sec}
    For a custody scheme with assignment $\mathcal{A}$ of $m$ groups and parameters $\mu$, $\gamma$ as above,
    we say that the custody scheme is \emph{$\gamma$-reliable} if
    \[f(\gamma; \mathcal{A},\mu) \le \gamma \cdot m.\]
    Furthermore, the scheme is called \emph{secure against $\gamma$-adversary} (or simply \emph{secure})
    if it is $\gamma'$-reliable for every $\gamma'\in[0,\gamma]$.
\end{definition}

The above definition of security guarantees that by controlling $\gamma n$ nodes,
the adversary is only able to corrupt $f(\gamma; \mathcal{A},\mu)$ custodian groups.
Therefore, by launching an attack the adversary is able to seize the funds of $f(\gamma; \mathcal{A},\mu)$ custodian groups,
at the cost of losing the security deposit of $\gamma n$ corrupted nodes.
The custody scheme is secure as long as the asset under custody of $f(\gamma; \mathcal{A},\mu)$ groups is bounded by the security deposit of $\gamma n$ nodes,
which indeed requires $f(\gamma; \mathcal{A},\mu) \le \gamma m$ since the deposit of $\gamma n$ nodes can be as much as asset under custody of $\gamma m$ groups.

Note that the gap between $f(\gamma; \mathcal{A},\mu)$ and $\gamma m$ corresponds to the ratio of external asset that can be securely held compared to security deposit,
which should be as large as possible.
For example, $f(\gamma; \mathcal{A},\mu) = \gamma m$ implies that
the custody scheme is only capable of securely holding the security deposit of its members but cannot provide custody service for any external users.
To describe the ability of securely holding exterior assets,
we introduce the notion of efficiency factor as in the following definition:

\begin{definition}[Efficiency factor]\label{def_eff}
    Given a custody scheme with $\mathcal{A},m,\mu$ and $\gamma$ defined as above,
    the \emph{efficiency factor} of this scheme, denoted by $\eta$,
    is defined as:
    \[\eta :=  \frac{\gamma m - f(\gamma; \mathcal{A},\mu)}{f(\gamma; \mathcal{A},\mu)}.\]
\end{definition}

It is immediate to verify that $\eta \ge 0$ for any custody scheme secure as in Definition~\ref{def_sec}.
This factor $\eta$ indeed equals to the maximal ratio of capable exterior assets to pledged assets that the underlying custody scheme is able to handle.
For example, $\eta=1$ means the system is secure when the total value of exterior assets is no more than total pledged security deposit.

Putting into our formal definition,
the trivial solution has only one custodian group (i.e. $m=1$, $k=n$),
and $\eta=\infty$ for $\gamma \leq \mu$ and $\eta<0$ for $\gamma > \mu$;
the custody scheme in Example~\ref{exa_con} has its efficiency factor $\eta$ changing
according to the adversary power $\gamma$ as summarized in the following table.

\begin{table}[!t]
    \caption{The efficiency factor of the custodian assignment as in Example~\ref{exa_con}}
    \label{tab_exa_con}
    \centering
    \renewcommand{\arraystretch}{1.35}
    \setlength{\tabcolsep}{5pt}

    \begin{tabular}{|{l}| *{4} {c|}}
        \hline
        {\bf Parameters $\backslash$ Adversary power} ($\gamma$) & $\gamma = 1/5$ & $\gamma = 2/5$ & $\gamma = 3/5$ & $\gamma = 4/5$  \\
        \hline

        { Corrupted nodes} ($s$) & $1$ & $2$ & $3$ & $4$  \\

        { Corrupted custodian groups} ($f(\gamma; \mathcal{A},\mu)$) & $0$ & $3$ & $7$ & $10$ \\

        { Efficiency factor} ($\eta$) & $\infty$ & $1/3$ & $-1/7$ & $-1/5$ \\
        \hline
    \end{tabular}
    \smallskip\\
    \flushleft\itshape
    The authentication threshold is realized as $r=2$ and $\mu=1/2$ (in this example equivalent to have $\mu\in [1/3,2/3)$).
    For $\gamma = 1/5$ and $\gamma = 2/5$, the scheme is secure with $\eta=\infty$ and $\eta = 1/3$ respectively.
    For $\gamma \ge 3/5$ the scheme is insecure and $\eta\le 0$.}
\end{table}

From the formalization of our decentralized custody scheme,
it is clear that the custodian group assignment $\mathcal{A}$ is the core of the whole custody scheme.
In particular, for every specific group assignment $\mathcal{A}$ and fixed constant $\mu$ (say, $\mu\in\{1/2, 2/3\}$),
the parameters $n,m,k$ are already specified in $\mathcal{A}$,
and the maximal number of corrupted groups and
the efficiency factor $\eta$ are functions solely depending on the adversary power $\gamma$.

Therefore, in the rest of this article we will focus on construction and analysis of custodian group assignments.
More specifically, we want the group assignment to support a decentralized custody scheme with the efficiency factor $\eta$ as large as possible for adversary power $\gamma$ bounded within a reasonable range (e.g. $\gamma <1/3$ or so),
and at the same time the group assignment $\mathcal{A}$ should
have large $n$ (e.g. over a thousand) and small $m$ and $k$ (e.g. ideally bounded by one hundred).

\subsection{Limitation and Impossibilities}

First we remark that the reliability and efficiency factor of an assignment $\mathcal{A}$ is not necessarily monotone.
That is, there exists $\gamma_a>\gamma_b$ such that
the custody scheme induced by some $\mathcal{A}$ is $\gamma_a$-reliable but not $\gamma_b$-reliable, as exhibited in the following example.

\begin{example}\label{exa_cla_change}
    Consider the case $S = \{1, 2, \cdots, 10\}$, $\mu = 2/3$,
    and the assignment scheme $\mathcal{A} = \{(1, 2, 3, 4, 5), (6, 7, 8, 9, 10)\}$.
    For $\gamma = 2/5$, the system is not $\gamma$-reliable
    since an adversary with $4$ corrupted nodes may corrupt one group and get half of the total security deposit.
    However, when $\gamma = 3/5$, the system is $\gamma$-reliable since the adversary controls at most one group with more than half of the total deposit.
\end{example}

We also remark that in general a decentralized custody scheme based on group assignments cannot be $\gamma$-reliable for all $\gamma$ unless $r = k$.
Since when $r<k$, by corrupting $n-1$ nodes the adversary is able to corrupt all custodian groups and hence get full control of the whole system.

\section{Preliminaries}\label{sec_pre}

\paragraph{Hypergeometric distribution and tail bound.}

A hypergeometric distribution $\mathcal{H}(N, K, n)$ is a discrete probability distribution with the following probability mass function:
\[\Pr[\mathcal{H}(N, K, n) = k] = \frac{\binom{K}{k}\binom{N - K}{n - k}}{\binom{N}{n}}.\]

Hypergeometric distribution draws the probability of getting $k$ items with a feature in $n$ draws without replacement, from totally $N$ items, $K$ of which with that feature. We are mostly interested in the tail bound of Hypergeometric distribution.
\begin{lemma}[\cite{Hoeffding63,chvatal79}]
	Let $X \sim \mathcal{H}(N, K, n)$ and $p = K/N$, then we have the following:
	\begin{align*}
	&\Pr[X \leq (p - t)n] \leq \exp(-nD(p - t \| p)) \leq \exp(-2nt^2), \quad 0 < t < p \\
	&\Pr[X \geq (p + t)n] \leq \exp(-nD(p + t \| p)) \leq \exp(-2nt^2), \quad 0 < t < 1 - p
	\end{align*}
	where $D(\cdot \| \cdot)$ stands for the Kullback-Leibler divergence with input real numbers naturally generalized to probability distributions, i.e.
	$D(a \| b) := a\cdot\ln \left({a}/{b}\right) + (1 - a)\cdot\ln \big((1 - a)/(1 - b)\big)$, for $a, b\in (0,1)$.
\end{lemma}

For $0 < a < b < c < 1$, the naturally generalized Kullback-Leibler divergence satisfies $D(a \| b) < D(a \| c)$,  $D(c \| b) < D(c \| a)$, $D(b \| a) < D(c \| a)$, $D(b \| c) < D(a \| c)$.

\paragraph{Stirling's formula.}

Stirling's formula provides good estimation of factorial terms.
Specifically, we will use the following version.
\begin{lemma}[\cite{Robbins55}]
	For any integer $n \geq 1$, we have
	$\sqrt{2\pi} \cdot e^{-n}n^{n + \frac{1}{2}} < n! < e^{1 - n}n^{n + \frac{1}{2}}$.
\end{lemma}

\paragraph{Block designs.}

A block design is a particular combinatorial design consisting of a set and a family of subsets (called blocks) whose arrangements satisfy generalized concepts of balance and symmetry.

\begin{definition}[Block design, from~\cite{Stinson07}]
	Let $n, k, \lambda$ and $r$ be positive integers such that $n > k \geq r$.
	A block design $(S, \mathcal{A})$ is called an $r$-$(n, k, \lambda)$-design if
	$|S| = n$ and $\mathcal{A}$ is a family of $k$-element subsets of $S$ (called blocks), such that
	every $r$-element subset of $S$ is contained in exactly $\lambda$ blocks in $\mathcal{A}$.

\end{definition}

In this work we mainly consider designs with $\lambda = 1$, and hence $\mathcal{A}$ cannot contain duplicate blocks.

\begin{corollary}
	In a $r$-$(n, k, \lambda)$-design, the number of blocks is $m = \lambda \left. \binom{n}{r} \middle/ \binom{k}{r} \right.$.
\end{corollary}
\begin{corollary}
	Suppose $(S, \mathcal{A})$ is an $r$-$(n, k, \lambda)$-design. Then for any $1 \leq t \leq r$, $(S, \mathcal{A})$ is also a $t$-$(n, k, \lambda_t)$-design, for
	$\lambda_t = \lambda\cdot{\binom{n - t}{r - t}}/{\binom{k - t}{r - t}}$.
\end{corollary}
\begin{corollary}
	Suppose $(S, \mathcal{A})$ is an $r$-$(n, k, \lambda)$-design. Then for any $Z \subseteq S$ with size $|Z|=t \leq r$, $(S - Z, \{A - Z: Z \subseteq A \in \mathcal{A}\})$ is a $(r - t)$-$(n - t, k - t, \lambda)$-design.
\end{corollary}

Furthermore, we remark that although non-trivial block designs exist universally by~\cite{Stinson07},
only very few such designs are explicitly constructed.

redpajama_set_name: RedPajamaArXiv