This is the first post about our 2024 ACSAC paper on light client syncing after offline phases. In a nutshell, we experiment with light clients based on so-called transitive signatures. This post discusses the underlying cryptographic primitive. Specifically, I’ll

  • define transitive (multi-)signatures,
  • present a BLS-based construction and
  • argue that it’s secure under a cryptographic assumption (in a bit more detail than our paper’s appendix had space for).

Another post shows a light client protocol design.

Motivation

Most light client protocols assume that consensus uses standard or only slightly restricted signature schemes (eg, over a SNARK-friendly elliptic curve). In protocols that aim to be particularly verifier-friendly, untrusted helper nodes create succinct proofs that a new block is the successor of the light client’s last known block. That proof covers some or all of the intermediary signature verifications that the light client would otherwise have to perform on its own. But signature checks within proofs are notoriously expensive. Our research explores whether this complexity be avoided when using specialized signatures in consensus.

Transitive signatures

The kind of signatures we use in the paper are known in the literature as transitive signatures. They have the interesting property that signatures by the same signer on messages that are consecutive in a well-defined sense can be aggregated. Then, the aggregated signature can be verified with respect to the public key, the first message and the last message regardless of how many messages came in between. More formally, transitive signatures allow signing edges of a graph and aggregation can be performed along paths such that verification complexity is independent of the path length.

In our paper, this definition is extended to (aggregate) multi-signatures where the single signer from the standard definition is replaced with groups of signers. Each group may sign a different message sequence. For completeness, I’ll now also make the proofs of possession explicit that serve to instantiate the paper’s abstract “registration phase” (formally, knowledge of secret key assumption). A transitive multi-signature then consists of: $\newcommand{\KeyGen}{\mathsf{KeyGen}} \newcommand{\sk}{\mathsf{sk}} \newcommand{\SK}{\mathsf{SK}} \newcommand{\pk}{\mathsf{pk}} \newcommand{\PK}{\mathsf{PK}} \newcommand{\pop}{\mathsf{pop}} \newcommand{\apk}{\mathsf{apk}} \newcommand{\VerifyPoP}{\mathsf{VerifyPoP}} \newcommand{\Sign}{\mathsf{Sign}} \newcommand{\Aggregate}{\mathsf{Aggregate}} \newcommand{\Verify}{\mathsf{Verify}} \newcommand{\G}{\mathbb{G}} \newcommand{\chall}{\mathsf{Chall}} \newcommand{\cdh}{\mathsf{CDH}} \newcommand{\groupHash}{H} \newcommand{\advA}{A} \newcommand{\advB}{B} \newcommand{\sig}{\sigma} \newcommand{\Sig}{S}$

  • $\KeyGen() \Rightarrow \sk, \pk, \pop$
  • $\VerifyPoP(\pk, \pop) \Rightarrow 0/1$
  • $\Sign(\sk, x, y) \Rightarrow \sigma$
  • $\Aggregate(\sigma_1, \dots, \sigma_N) \Rightarrow \Sig$
  • $\Verify((\PK_1, \dots, \PK_n), ((x_1, z_1), \dots, (x_n, z_n)), \Sig) \Rightarrow 0/1$

Correctness means that if $\PK_1, \dots, \PK_n$ are lists of public keys, if for each $\pk_{i,j} \in \PK_i$, $\sigma_{i,j}$ and $\sigma_{i,j}’$ are signatures accepted by $\Verify(((\pk_{i,j})), ((x_i, y_i)), \sigma_{i,j})$ and, respectively, by $\Verify(((\pk_{i,j})), ((y_i, z_i)), \sigma_{i,j}’)$ and if $\Sig$ is generated by $\Aggregate(\sigma_{1,1}, \dots, \sigma_{n, |\PK_n|}, \sigma_{1,1}’, \dots, \sigma_{n, |\PK_n|}’)$, then $\Verify((\PK_1, \dots, \PK_n), ((x_1, z_1), \dots, (x_n, z_n)), \Sig)$ will return 1. This also means that further applications of $\Aggregate$ with signatures over messages like $(z_i, w_i)$ lead to a single signature over the messages $(x_i, w_i)$.

Security requires that no probabilistic polynomial-time adversary with access to a signing oracle for a fixed public key $\pk$ can, with non-negligible probability, output lists of public keys $\PK_1, \dots, \PK_n$, lists of proofs $\Pi_1 = (\pi_{1,1}, \dots, \pi_{1, |Pi_1|}), \dots, \Pi_n = (\pi_{n,1}, \dots, \pi_{n,|\Pi_n|})$, a signature $\Sig$ and $(x_1, z_1), \dots, (x_n, z_n)$ such that

  • $\Verify((\PK_1, \dots, PK_n), ((x_1,z_1),\dots,(x_n,z_n)), \Sig)$ accepts,
  • for all $i \in [n]$, $| \PK_i | = |\Pi_i|$ and, for all $j \in [|\PK_i|]$ with $\pk_{i,j} \neq \pk$, $\VerifyPoP(\pk_{i,j}, \pi_{i,j})$ accepts,
  • there is $k \in [n]$ such that $\pk \in \PK_k$ and there is no path between $x_k$ and $z_k$ in the graph induced by the signing queries to the $\pk$ oracle.

Construction

The BLS-like transitive signature construction originates in the GapTS-2 scheme from this paper. Let $\G, \hat{\G}, \G_T$ be groups of prime order $p$ with a bilinear map $e : \G \times \hat{\G} \rightarrow \G_T$ and generators $g \in \G, \hat{g} \in \hat{\G}$. Denote the group operation as $+$ and its repeated application as $\cdot$. Let $H : \{0,1\}^* \rightarrow \hat{\G}$ and $H’ : \G \rightarrow \hat{\G}$ be hash functions. Here is an extension of GapTS-2 with aggregation and proofs of possession:

  • $\KeyGen()$: picks random exponent $\sk \in \mathbb{Z}_p^*$ and sets $\pk = \sk \cdot g$, $\pop = \sk \cdot H’(\pk$).
  • $\VerifyPoP(\pk, \pop)$ checks $e(g, \pop) =^? e(\pk, H’(\pk))$.
  • $\Sign(\sk, x, y)$ sets $\sigma = \sk \cdot (H(y)-H(x))$.
  • $\Aggregate(\sigma_1, \dots, \sigma_N)$ sets $\Sig = \sigma_1 + \cdots + \sigma_N$.
  • $\Verify((\PK_1, \dots, \PK_n), ((x_1, z_1), \dots, (x_n, z_n)), \Sig)$ sets $\apk_i = \sum_{j \in [|\PK_i|]} \pk_{i,j}$ for all $i \in [n]$ and checks $e(g, \Sig) =^? \sum_{i \in [n]} e(\apk_i, H(z_i)-H(x_i))$.

GapTS-2

GapTS-2 is the above scheme with the restrictions $n = 1$ and $|\PK_i|=1$, no $\pop$ and no functions $\Aggregate$ and $\VerifyPoP$. For completeness, below is a proof of its security based on the following assumption.

$q$-one-more co-computational Diffie-Hellman ($q$-OM co-CDH)

Let $a$ be uniformly sampled from $\mathbb{Z}_p^{*}$, let $\chall$ be an algorithm that samples $b \in \mathbb{Z}_p^{*}$ uniformly at random and returns $b \cdot g$ and let $\cdh$ be an ideal oracle that returns $xy \cdot \hat{g}$ given $x \cdot g$, $x \cdot \hat{g}$ and $y \cdot \hat{g}$. Under the $q$-one-more co-computational Diffie-Hellman assumption there is no probabilistic polynomial time algorithm that, on input $a \cdot g, a \cdot \hat{g}$ and with oracle access to $\chall$ and $\cdh$

  • makes less than $q$ calls to $\cdh$,
  • makes exactly $q$ calls to $\chall$ which return $b_1 \cdot g, \dots, b_q \cdot g$ and
  • outputs, with non-negligible probability, $a b_1 \cdot g, \dots, a b_q \cdot g$.

Plausibility of the assumption

In this paper from Asiacrypt 2021, the plausibility of a one-more CDH assumption which uses $\G_1=\G_2$ is argued for with respect to a restricted class of attackers, namely, in the generic group model (GGM). The same paper also argues for the plausibility of the one-more discrete logarithm assumption. In fact, hardness of the one-more CDH assumption follows from a strengthened version of the one-more discrete log assumption. To prove the one-more discrete log assumption, as well as its strenghened version, the paper presents a new lemma about the size of the intersection of the zeroes of polynomials in finite fields with certain arrangements of hyperplanes. This lemma serves as an alternative to the Schwartz-Zippel lemma which standard proofs in the GGM use (but which did not suffice for the studied one-more assumptions).

It is argued in this CCS 2023 paper that the previous paper’s claim about the one-more discrete logarithm assumption carries over to the setting of asymmetric pairing groups where $\G_1 \neq \G_2$. However, this requires another new lemma that generalizes the other paper’s lemma that replaced Schwartz-Zippel. Specifically, the previous lemma’s hyperplanes are generalized to degree-2 hypersurfaces. Besides using the improved lemma, the structure of the proof for the discrete log assumption resembles the previous paper’s. I believe that the improved lemma can also be used to prove GGM hardness of the strenghtened one-more discrete log assumption in the asymmetric group setting. This should then also imply the hardness of the one-more CDH assumption required for GapTS-2.

More concretely, as far as I understand, the best current algorithm for $q$-one-more co-computational Diffie-Hellman in practically relevant elliptic curves would be an adaptation of a discrete logarithm attack like this one: If $d$ divides either $p-1$ or $p+1$ and the attacker makes $d$ queries, the attack complexity is only around $O(\sqrt{p/d})$ group operations. Now, widely-used pairing friendly curves are specifically designed such that $p-1$ is divisible by a moderately large power of two: For example, BLS12-381 has $p$ of around 255 bits such that $p-1$ is divisible by $2^{32}$ (and also by a few other small primes). Thus, when the adversary makes correspondingly many $\cdh$ queries, the attack complexities are roughly $2^{111}$ group operations.

Security of GapTS-2

Security requires that no attacker $\advA$ with a signing oracle for a fixed public key $\pk$ can, with non-negligible probability, output $x, z$ and a signature $\sig$ such that $\Verify((\pk),(x,z),\sig)$ accepts even though there is no path from $x$ to $z$ in the graph $G$ (where queries to the $\pk$ oracle implicitly add nodes and edges to $G$). Suppose there existed such an adversary $\advA$ that made $q$ queries to $\groupHash$ which is modelled as a random oracle. We construct an attacker $\advB$ against $q$-OM co-CDH.

Step 1. Using $A$

$\advB$ starts with $a \cdot g$ and $a \cdot \hat{g}$ and hands $a \cdot g$ to $\advA$ as the public key. $\advB$ must answer $\advA$’s random oracle and signing queries. The interaction with $\advA$ works as follows.

  • To simulate the random oracle, if $\groupHash$ is queried for a value for which it has been queried before, the previous answer is returned. To answer a new query to $\groupHash$, a query to $\chall$ is made and the response is returned.
  • When $\advA$ makes a signing query for $(y_1, y_2)$ where the graph already contains a path between $y_1$ and $y_2$, $\advB$ uses $\Aggregate$. Otherwise, $\advB$ calls $\cdh$ with $a \cdot g$, $a \cdot \hat{g}$ and $\groupHash(y_2)-\groupHash(y_1)$ to obtain $a \cdot (\groupHash(y_2)-\groupHash(y_1))$ which is returned as the signature. This way, the edges in $G$ which correspond to signatures created from $\cdh$ calls form a minimum spanning tree in each connected component.

  • Eventually, $\advA$ outputs $x, z, \sig$ such that $e(g, \sig) = e(a \cdot g, \groupHash(z)-\groupHash(x))$, which implies $\sig = a \cdot (b_z-b_x) \cdot \hat{g}$, where $b_x$ and $b_z$ are determined by the $\chall$ calls from the corresponding $\groupHash$ simulations.

Next, $\advB$ makes a $\cdh$ query with $a \cdot g, a \cdot \hat{g}$ and $\groupHash(x)$ to obtain $a \cdot b_x \cdot \hat{g}$. By adding $\sigma$, $\advB$ then obtains $a \cdot b_z \cdot \hat{g}$. Note that two $\chall$ calls were needed to define $\groupHash(x)$ and $\groupHash(z)$ but, thanks to $\sigma$, only one $\cdh$ call was needed to obtain both Diffie-Hellman secrets.

Step 2. A few more queries

We now analyze how many further $\cdh$ queries are needed to obtain the Diffie-Hellman secrets corresponding to all other $\chall$ queries. For $\chall$ calls that defined some $\groupHash(y)$ where $y$ is not part of any signature, that is, not a node in $G$, $\advB$ needs to make one $\cdh$ query. It remains to be shown that for every connected component of $G$ with $c$ nodes and a minimum spanning tree with $d<c$ edges – which means that $c$ $\chall$ calls and $d$ $\cdh$ calls were made –, $\advB$ needs at most $c-d$ further $\cdh$ calls to obtain the $c$ Diffie-Hellman secrets. Then, all in all, $\advB$ will have obtained one more Diffie-Hellman secret than $\cdh$ calls were made and we’re done. We proceed by induction over $d$:

  • Hypothesis. For a connected component $C$ with $c$ nodes ($\chall$ calls) and a minimum spanning tree with $d$ edges ($\cdh$ calls), $c-d$ further $\cdh$ calls suffice to obtain all $c$ Diffie-Hellman secrets.
  • Base case, $d=1$. If the minimum spanning tree of the component $C$ has one edge, then $C$ has two nodes, say $y_1$ and $y_2$ with hashes $\groupHash(y_1) = b_1 \cdot \hat{g}$ and $\groupHash(y_2) = b_2 \cdot \hat{g}$. The single edge corresponds to the signature $\sig_{12} = a \cdot (\groupHash(y_2)-\groupHash(y_1))$. $\advB$ can make one $\cdh$ query with input $a \cdot g, a \cdot \hat{g}, \groupHash(y_1)$ to obtain $s = a \cdot b_1 \cdot \hat{g}$. This allows computing the other Diffie-Hellman secret as $s + \sig_{12} = a \cdot b_2 \cdot \hat{g}$. (If $x \in \{y_1,y_2\}$, no further query is needed as $a \cdot \groupHash(x)$ is already known.)
  • Induction step, $d-1 \rightarrow d$. Let $y_1, y_2$ be connected nodes in a minimum spanning tree of $C$ such that $\groupHash(y_1) = b_1 \cdot \hat{g}$, $\groupHash(y_2) = b_2 \cdot \hat{g}$ and such that $y_2$ is a leaf, that is, the only edge of $y_2$ in the minimum spanning tree is the edge to $y_1$. Let the signature corresponding to the edge between $y_1$ and $y_2$ be $\sig_{12} = a \cdot (\groupHash(y_2)-\groupHash(y_1))$. Let $C’$ be the graph obtained from removing $y_2$ and all its edges from $C$. $C’$ has $c-1$ nodes and has a minimum spanning tree with $d-1$ edges, namely the tree of $C$ minus the node $y_2$. By the induction hypothesis, $c-1-(d-1) = c-d$ $\cdh$ calls suffice to obtain the $c-1$ Diffie-Hellman secrets corresponding to the nodes in $C’$. In particular, $\advB$ can obtain $s = a \cdot b_1 \cdot \hat{g}$. This allows computing the remaining Diffie-Hellman secret as $s + \sig_{12} = a \cdot b_2 \cdot \hat{g}$.

Security of signature aggregation

As per our paper (appendix A.2), security of the multi-signer scheme can be reduced to the single signer scheme. That is, a succesful attacker $A$ against the $n>1$ version implies an attacker $B$ against the $n=1$ version, ie, GapTS-2. For simplicity, we make a knowledge of exponent (KOE) assumption (which holds, for example, in the algebraic group model), by which the adversary’s ability to output valid proofs of possession implies that $B$ can use $A$’s code to determine the corresponding secret keys.

So, $\advB$ starts in the $n=1$ security experiment with a public key $\pk$. $\advB$ forwards $\pk$ to $\advA$ and passes each of $\advA$’s oracle queries along to the signing oracele or to the random oracle. Eventually, $\advA$ outputs $\PK_1, \dots, \PK_n, \Pi_1, \dots, \Pi_n, (x_1,z_1), \dots, (x_n,z_n)$ and $\Sig$. As per the KOE assumption, $\advB$ extracts the lists of secret keys $\SK_1, \dots, \SK_n$ corresponding to the public keys other than $\pk$. (At each position $j$ where the entry in $\PK_i$ is $\pk$, the list $\SK_i$ has a 0.)

Let $\sk^* = \log_g(\pk)$. If $\Sig$ passed verification, then $\Sig = \sum_{i \in [n]} \apk_i \cdot (H(z_i)-H(x_i))$ where \(\apk_i = \begin{cases}\sum_{\sk \in \SK_i} \sk & \text{if } \pk \in \PK_i \\ c_i \sk^* + \sum_{\sk \in \SK_i} \sk & \text{otherwise}\end{cases}\) where $c_i = |\{j \in [|\PK_i|] : \pk_{i,j} = \pk\}|$. Hence, $B$ first subtracts $\sum_{i \in [n]} \left(\sum_{\sk \in \SK_i} \sk\right) (H(z_i)-H(x_i))$ from $\Sig$ to obtain $\Sig’ = \sk^* \cdot \left(\sum_{i \in I} c_i (H(z_i)-H(x_i))\right)$ where $I \subset [n]$ is the set of all $i$ such that $\pk \in \PK_i.$ $\advB$ then picks $k \in I$ such that the graph induced by the signing queries contains no path from $x_k$ to $z_k$. $\advB$ queries signatures $\sig_i’ = \sk^* \cdot (H(z_i)-H(x_i))$ for each $i \in I \setminus \{k\}$. Finally, $\advB$ computes $\Sig’ - \sum_{i \in I \setminus \{k\}} \sig_i’ = \sk^* \cdot (H(z_k)-H(x_k))$. This constitutes a valid forgery for GapTS-2, completing the proof.