a unique $3$-uniform hypergraph with $m=n$ and an SDR — the well-known _Fano
plane_.

######  Definition 54 (Fano plane (see, e.g., [Juk11])).

The Fano plane is the unique projective plane of order $2$, and can be
represented by the _Fano hypergraph_ $G=(V,E)$ (see Figure 10) with
${V}={\left\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\right\\}}$ and

$E={\left\\{\\{v_{1},v_{2},v_{3}\\},\\{v_{1},v_{4},v_{5}\\},\\{v_{1},v_{6},v_{7}\\},\\{v_{2},v_{4},v_{6}\\},\\{v_{2},v_{5},v_{7}\\},\\{v_{3},v_{4},v_{7}\\},\\{v_{3},v_{5},v_{6}\\}\right\\}}.$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$

Figure 10: The Fano hypergraph.

######  Lemma 55.

The unique $3$-uniform hypergraph which is (1) a $1$-intersecting family, (2)
has $m=n$, and (3) has an SDR is the Fano hypergraph.

###### Proof.

Let $G=(V,E)$ satisfy the properties of the claim. WLOG, we begin with an
arbitrary pair of intersecting edges,
$e_{1}={\left\\{v_{1},v_{2},v_{3}\right\\}}$ and
$e_{2}={\left\\{v_{1},v_{4},v_{5}\right\\}}$, pictured below:

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

We proceed by adding edges one at a time while maintaining property $(1)$. To
add the third edge $e_{3}$, since the graph is $1$-intersecting, there are two
cases:

  * (a)

$e_{3}={\left\\{v_{1},v_{6},v_{7}\right\\}}$ intersects both $e_{1}$ and
$e_{2}$ at vertex $v_{1}$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$

  * (b)

$e_{3}={\left\\{v_{3},v_{5},v_{6}\right\\}}$ does not intersect $e_{1}$ and
$e_{2}$ at $v_{1}$. By symmetry, we may represent this as below.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

Figure 11: A (linear) $3$-cycle.

Let us now add the fourth edge, which can be done in one of two ways: Either
we add a new vertex, or we do not add a new vertex.

  * •

If we add a new vertex: For case (a), we obtain a graph isomorphic to

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$

This does not have $m=n$ and cannot be extended into a $1$-intersecting family
since any further edge (of size $3$) would have to intersect $4$ existing
edges. For (b), a case analysis reveals that the only way to extend by adding
a new vertex while maintaining the $1$-intersection property is via a graph
isomorphic to:

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$

Figure 12: How to add a fourth edge to extend case (b) via a new vertex.

  * •

If we do not add a new vertex:

    1. 1.

Case (a) can only be extended while maintaining the $1$-intersecting property
via a graph isomorphic to that in Figure 12.

    2. 2.

For case (b), either we obtain a graph isomorphic to Figure 12, or we add
$e_{4}=\\{v_{2},v_{4},v_{6}\\}$ to obtain Figure 13.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

Figure 13: One of two ways to add a $4$th edge to extend case (b) without
adding a new vertex.

From the fifth edge onward, an analogous case analysis yields at each step
that only two types of edges can be added at this point which preserve the
$1$-intersecting property: A “crossing edge” (as in Figure 12)
${\left\\{v_{1},v_{6},v_{7}\right\\}}$,
${\left\\{v_{3},v_{4},v_{7}\right\\}}$, or
${\left\\{v_{2},v_{5},v_{7}\right\\}}$, or a “circular edge” (as in Figure 13)
${\left\\{v_{2},v_{4},v_{6}\right\\}}$. When all such edges are added, we
arrive at $7$ edges total and obtain the Fano hypergraph. No fewer edges
satisfies the $m=n$ property, and clearly one cannot add another edge at this
point while satisfying the $1$-intersecting property. Finally, that $G$ has an
SDR can either be verified directly or by applying Corollary 49. ∎

###  5.2 Linear hypergraphs

In Section 5.1.1, we studied the set of $3$-uniform hypergraphs in which if a
pair of distinct edges intersect, then the intersection size is at least $2$.
We now take the complementary approach by asking that any pair of distinct
edges intersect on _at most one_ vertex. Such hypergraphs are called _linear_
; note that linear hypergraphs are not necessarily $1$-intersecting.

To set the context, linear hypergraphs in general (i.e. not necessarily with
an SDR) are a complicated, but well-studied, class. Let $L_{3}^{l}$ denote the
set of edge intersection graphs of linear $3$-uniform hypergraphs. (An _edge
intersection graph_ (EIG) is the generalization of a line graph to the setting
of hypergraphs $G$; namely, the vertices of the EIG are the hyperedges of $G$,
and two vertices of the EIG are neighbors if and only if their hyperedges in G
intersect. Note that an EIG is a graph, i.e. a $2$-uniform hypergraph.) It is
known that $L_{3}^{l}$ has no “finite characterization” in terms of a finite
list of forbidden induced subgraphs [NRSS82]. However, the same paper does
give the following characterization: A graph $G$ is in $L_{k}^{l}$ if and only
if $G$ has so-called _Krausz dimension_ $k$. Unfortunately, it was later shown
[HK97] that deciding if Krausz dimension is at most $3$ is NP-complete (even
on planar graphs of degree at most $5$); thus, determining if a graph is an
EIG of a linear $3$-uniform hypergraph is NP-complete, suggesting the class of
linear $3$-uniform hypergraphs is quite complex.

In our setting, we study linear $3$-uniform hypergraphs $G$ with the
additional guarantees that $m=n$ and that $G$ has an SDR. Nevertheless, we are
not able to complete a structural characterization. Instead, we find various
interesting “canonical-looking” examples. For brevity, we henceforth denote a
linear $3$-uniform hypergraph with $m=n$ and an SDR as an LGraph.

##### Minimum size and the Fano plane.

What is the minimum size an LGraph can have?

######  Theorem 56.

The minimum size of an LGraph is $m=n=7$, and the Fano hypergraph (Figure 10)
is the unique LGraph of this size.

###### Proof.

The lower bound on minimum size follows from an old lemma of Corrádi.

######  Lemma 57 (Corrádi 1969 [Juk11]).

Let $A_{1},...,A_{N}$ be $r-$element sets and $X$ be their union. If
$|A_{i}\cap A_{j}|\leq k$ for all $i\neq j$, then $\left\lvert
X\right\rvert\geq(r^{2}N)/(r+(N-1)k).$

Plugging in our LGraph parameters $k=1$, $r=3$, $E=\\{A_{1},...,A_{m}\\}$,
${V}=X=\\{1,...,n\\}$, yields that $\left\lvert E\right\rvert=\left\lvert
V\right\rvert\geq 7$. Note that the Fano hypergraph is an LGraph with $m=n=7$,
which also happens to be $1$-intersecting. To show uniqueness, we hence show
that _any_ LGraph with $m=n=7$ must be $1$-intersecting; the claim then
follows from Lemma 55.

To show that any LGraph with $m=n=7$ must be $1$-intersecting, suppose, for
sake of contradiction, that $G=(V,E)$ is an LGraph with $m=n=7$ and edges
$e_{1}$,$e_{2}$ with $e_{1}\cap e_{2}=\emptyset$. Then, the subgraph of $G$
induced by ${\left\\{e_{1},e_{2}\right\\}}$ is isomorphic to

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$

Since $G$ is linear, any edge we add must contain $v_{4}$, and in turn, must
also contain a _unique_ vertex from each of
${\left\\{v_{1},v_{2},v_{3}\right\\}}$ and
${\left\\{v_{5},v_{6},v_{7}\right\\}}$. Thus, the maximum number of edges we
may add is $3$, giving a total of $5$ edges, which is a contradiction. ∎

##### The tiling of the torus.

There is a sense in which the Fano hypergraph is the “most compact” LGraph. On
the opposite extreme, an example of what seems the “least compact” LGraph is
the “tiling of the torus”, given in Figure 14. More precisely, this is the
specialization of Example 15 to the case $k=3$ and $a_{1}=a_{2}=3$.

$v_{1}$$v_{1}$$v_{1}$$v_{2}$$v_{2}$$v_{3}$$v_{3}$$v_{4}$$v_{4}$$v_{5}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$

Figure 14: A $3\times 3$ tiling of the torus. Note the closed boundary
conditions, i.e. we identify two vertices with the same label as being the
same vertex.

##### The Helly property.

Another well-studied hypergraph property is the _Helly_ property, which
requires that any intersecting family $F$ of hyperedges of the hypergraph $G$
have non-empty intersection. An equivalent, perhaps more geometrically
intuitive, characterization is the following:

######  Corollary 58 (Page 23 of [Ber85], stated as Corollary 5.1 of [BCU01]).

A hypergraph $H$ has the Helly property if and only if for any three vertices
$a_{1},a_{2},a_{3}$, the family of hyperedges which contains at least two of
these vertices has non-empty intersection.

In the special case of linear hypergraphs, the Helly property forbids a
“linear 3-cycle”, as illustrated in Figure 11. In this sense, linear Helly
hypergraphs roughly generalize triangle-free graphs.

Observe now that the two “canonical-looking” LGraphs we have discussed thus
far, the Fano plane and the tiling of the torus, do _not_ satisfy the Helly
property. This raises the question: Do all LGraphs violate the Helly property?
In Lemma 59, we answer this question negatively by giving an LGraph with the
Helly property. Thus, even with numerous restrictions (i.e. $m=n$, linear,
Helly), the set of $3$-uniform hypergraphs with SDRs seems non-trivial.

######  Lemma 59.

There exists a linear $3$-uniform hypergraph $G=(V,E)$ with $\left\lvert
E\right\rvert=\left\lvert V\right\rvert=28$ such that $G$ satisfies the Helly
property, and $G$ has an SDR.

###### Proof.

Since the Helly property forbids a linear $3$-cycle, the idea of the
construction is to build a longer linear cycle, with added “links” between
vertices to ensure $m=n$. We call this the “interlinked cycle” (iCycle) for
short; a formal specification is given in Figure 15, and a graphical depiction
in Figure 16. The claimed properties are tedious, but straightforward, to
verify.

e | v | e | v | e | v | e | v | e | v
---|---|---|---|---|---|---|---|---|---
1 | (1,2,28) | 7 | (12,13,14) | 13 | (24,25,26) | 19 | (8,14,19) | 25 | (3,15,27)
2 | (2,3,4) | 8 | (14,15,16) | 14 | (26,27,28) | 20 | (6,12,21) | 26 | (1,6,24)
3 | (4,5,6) | 9 | (16,17,18) | 15 | (5,22,28) | 21 | (4,10,23) | 27 | (1,10,20)
4 | (6,7,8) | 10 | (18,19,20) | 16 | (7,20,26) | 22 | (2,8,25) | 28 | (1,13,17)
5 | (8,9,10) | 11 | (20,21,22) | 17 | (9,18,24) | 23 | (10,15,20) |  |
6 | (10,11,12) | 12 | (22,23,24) | 18 | (11,16,22) | 24 | (6,15,24) |  |
Figure 15: A formal specification of the iCycle. The columns labelled _e_ and
_v_ index the edges and $3$-tuples corresponding to those edges, respectively.
The underlined element of each $3$-tuple denotes the qubit matched to that
edge.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$$v_{11}$$v_{12}$$v_{13}$$v_{14}$$v_{15}$$v_{16}$$v_{17}$$v_{18}$$v_{19}$$v_{20}$$v_{21}$$v_{22}$$v_{23}$$v_{24}$$v_{25}$$v_{26}$$v_{27}$$v_{28}$

Figure 16: The iCycle.

∎

##### Do all linear $3$-uniform hypergraphs with $m=n$ have an SDR?

The examples we have studied in this section are all LGraphs, even with
constraints such as the Helly property. This raises the question: Could _all_
linear $3$-uniform hypergraphs with $m=n$ have SDR’s? Intuitively, this is
plausible, as the linear property forces a $3$-uniform hypergraph to be
“spread out” in a rough sense. We now answer this question in the negative,
and the construction of the counterexample will teach us something about the
structure of LGraphs.

For this, we first require a definition of a _block_ and useful lemma.

######  Definition 60 (Block).

For hypergraph $G=(V,E)$, let $G_{E^{\prime}}$ denote the edge-induced
subgraph of $G$ by $E^{\prime}\subseteq E$. Then, we call $G_{E^{\prime}}$ a
_block_ if it has an equal number of vertices and edges.

######  Lemma 61.

Let $G=(V,E)$ be a hypergraph with an SDR. Let $A$ denote a block in $G$.
Then, the SDR matches the vertices in $A$ to the edges in $A$. Moreover, for
any other block $B$ in $G$, $A$ and $B$ are vertex-disjoint.

###### Proof.

Let $A=(V_{A},E_{A})$ be a block in $G$. Since $A$ is edge-induced, the only
vertices which can match to the edges in $E_{A}$ are those in $V_{A}$. Since
$\left\lvert V_{A}\right\rvert=\left\lvert E_{A}\right\rvert$ by definition of
a block, our first claim follows. The second claim now follows as a corollary,
since if $A$ and $B$ intersect on vertex $v\in V$, then _both_ $A$ and $B$
require $v$ as part of their respective SDR’s by our first claim, which is
impossible since each vertex can only be matched to a single edge. ∎

######  Theorem 62.

There exists a linear hypergraph with $m=n$ which does not have an SDR.

###### Proof.

The intuitive idea is to “stitch together” three copies of (say) the Fano
hypergraph with an extra edge, so that there is no way to match the new edge
to a vertex. This loses the $m=n$ property; we then add further edges and
vertices to recover the property. The resulting hypergraph is depicted in
Figure 17. That the graph lacks an SDR follows from Lemma 61; specifically,
let $e$ denote the unique edge incident on all three Fano hypergraphs. Since
the latter are blocks, none of their vertices can be matched to $e$, implying
$e$ cannot be matched. ∎

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$

Figure 17: A linear hypergraph with $m=n$ and no SDR. The three large
triangles denote any block with an SDR, such as the Fano hypergraph.

As an aside, note that the construction of Theorem 62 can be modified to also
satisfy the Helly property — namely, replace each copy of the Fano hypergraph
with a copy of the iCycle, discard the inner two circular edges
${\left\\{v_{2},v_{8},v_{5}\right\\}}$ and
${\left\\{v_{3},v_{4},v_{7}\right\\}}$ and the two “straight-line” edges
${\left\\{v_{9},v_{8},v_{7}\right\\}}$ and
${\left\\{v_{4},v_{5},v_{6}\right\\}}$, and discard vertices
$v_{4},v_{5},v_{7},v_{8}$. The resulting hypergraph is linear, Helly, and
satisfies $m=n$, but does not have a matching. Thus, the construction of
Theorem 62 appears to yield a fairly systematic approach for constructing
hypergraphs without SDR’s, but still satisfying other desirable properties
such as being linear or Helly.

## Acknowledgements

The first result of this project was partially completed while NdB was
affiliated with the Centrum Wiskunde & Informatica; SG thanks Ronald de Wolf
and Centrum Wiskunde & Informatica for their hospitality. SG thanks Howard
Barnum and David Reeb regarding discussions on algebraic geometry, and David
Gosset for discussions on Quantum SAT. NdB acknowledges support from the EPSRC
National Quantum Technology Hub in Networked Quantum Information Processing.
SG acknowledges support from NSF grants CCF-1526189 and CCF-1617710.

## References

  * [ASSZ16] Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang.  Linear Time Algorithm for Quantum 2SAT.  In Yuval Rabani Ioannis Chatzigiannakis, Michael Mitzenmacher and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [BCU01] A. Bretto, H. Cherifi, and S. Ubéda.  An efficient algorithm for Helly property recognition in a linear hypergraph.  Electronic Notes in Theoretical Computer Science, 46:177 – 187, 2001.  IWCIA 2001, 8th International Workshop on Combinatorial Image Analysis.
  * [Ber85] C. Berge.  Graphs.  North-Holland, 1985.
  * [BG94] M. Bellare and S. Goldwasser.  The complexity of decision versus search.  SIAM Journal on Computing, 23(1):97–119, 1994.
  * [Bra06] S. Bravyi.  Efficient algorithm for a quantum analogue of 2-SAT.  Available at arXiv.org e-Print quant-ph/0602108v1, 2006.
  * [dBG16] Niel de Beaudrap and Sevag Gharibian.  A Linear Time Algorithm for Quantum 2-SAT.  In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:21, Dagstuhl, Germany, 2016\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [DF12] Rodney G. Downey and M. R. Fellows.  Parameterized Complexity.  Springer Publishing Company, Incorporated, 2012.
  * [FMR08] E. Fischer, J.A. Makowsky, and E.V. Ravve.  Counting truth assignments of formulas of bounded tree-width or clique-width.  Discrete Applied Mathematics, 156(4):511 – 529, 2008.  Third Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics & Algorithm.
  * [GHLS14] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin.  Quantum Hamiltonian complexity.  Foundations and Trends® in Theoretical Computer Science, 10(3):159–282, 2014.
  * [GHO13] Robert Ganian, Petr Hliněný, and Jan Obdržálek.  Better algorithms for satisfiability problems for formulas of bounded rank-width.  Fundam. Inf., 123(1):59–76, January 2013.
  * [GN13] D. Gosset and D. Nagaj.  Quantum 3-SAT is QMA1-complete.  In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 756–765, 2013.
  * [GPST16] Serge Gaspers, Christos H. Papadimitriou, Sigve Hortemo Sæther, and Jan Arne Telle.  On satisfiability problems with a linear structure.  In IPEC, 2016.
  * [HK97] Petr Hlinený and Jan Kratochvíl.  Computational complexity of the krausz dimension of graphs.  In WG, 1997.
  * [JF56] L. R. Ford Jr. and D. R. Fulkerson.  Maximal flow through a network.  Canadian Journal of Mathematics, 8:399–404, 1956.
  * [Juk11] S. Jukna.  Extremal Combinatorics With Applications in Computer Science.  Springer, second edition, 2011.
  * [Kar72] R. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103. New York: Plenum, 1972.
  * [KKR06] J. Kempe, A. Kitaev, and O. Regev.  The complexity of the local Hamiltonian problem.  SIAM Journal on Computing, 35(5):1070–1097, 2006.
  * [KS16] Gyula Y. Katona and Péter G.N. Szabó.  Bounds on the number of edges in hypertrees.  Discrete Mathematics, 339(7):1884 – 1891, 2016.  7th Cracow Conference on Graph Theory, Rytro 2014.
  * [KSV02] A. Kitaev, A. Shen, and M. Vyalyi.  Classical and Quantum Computation.  American Mathematical Society, 2002.
  * [LLM+10] C. R. Laumann, A. M. Läuchli, R. Moessner, A. Scardicchio, and S. L. Sondhi.  Product, generic, and random generic quantum satisfiability.  Physical Review A, 81:062345, 2010.
  * [LMSS10] C. R. Laumann, R. Moessner, A. Scardicchio, and S. L. Sondhi.  Phase transitions and random quantum satisfiability.  Quantum Information & Computation, 10:1–15, 2010.
  * [NRSS82] Ranjan N. Naik, S.B. Rao, S.S. Shrikhande, and N.M. Singhi.  Intersection graphs of k-uniform linear hypergraphs.  European Journal of Combinatorics, 3(2):159 – 172, 1982.
  * [Osb12] T. J. Osborne.  Hamiltonian complexity.  Reports on Progress in Physics, 75(2):022001, 2012.
  * [PSS16] Daniel Paulusma, Friedrich Slivovsky, and Stefan Szeider.  Model counting for cnf formulas of bounded modular treewidth.  Algorithmica, 76(1):168–194, September 2016.
  * [Sch85] Arnold Schönhage.  Quasi-GCD computations.  Journal of Complexity, 1(1):118 – 137, 1985.
  * [Sch86] A. Schönhage.  Equation solving in terms of computational complexity.  In Proceedings of the International Congress of Mathematicians, pages 131–153, 1986.
  * [SS10] Marko Samer and Stefan Szeider.  Algorithms for propositional model counting.  Journal of Discrete Algorithms, 8(1):50 – 64, 2010.
  * [STV15] Sigve Hortemo Sæther, Jan Arne Telle, and Martin Vatshelle.  Solving #sat and maxsat by dynamic programming.  J. Artif. Int. Res., 54(1):59–82, September 2015.
  * [Sze04] Stefan Szeider.  On Fixed-Parameter Tractable Parameterizations of SAT, pages 188–202.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
  * [Wol] D. A. Wolfram.  Solving generalized fibonacci recurrences.  Fibonacci Quart., 36(2):129–145.


# Distributed Attestation Revocation in Self-Sovereign Identity ††thanks: This
work was funded by NWO/TKI grant BLOCK.2019.004.

Rowdy Chotkan  Distributed Systems
Delft University of Technology
Delft, The Netherlands
<EMAIL_ADDRESS>Jérémie Decouchant  Distributed Systems
Delft University of Technology
Delft, The Netherlands
<EMAIL_ADDRESS>Johan Pouwelse  Distributed Systems
Delft University of Technology
Delft, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

Self-Sovereign Identity (SSI) aspires to create a standardised identity layer
for the Internet by placing citizens at the centre of their data, thereby
weakening the grip of big tech on current digital identities. However, as
millions of both physical and digital identities are lost annually, it is also
necessary for SSIs to possibly be revoked to prevent misuse. Previous attempts
at designing a revocation mechanism typically violate the principles of SSI by
relying on central trusted components. This lack of a distributed revocation
mechanism hampers the development of SSI. In this paper, we address this
limitation and present the first fully distributed SSI revocation mechanism
that does not rely on specialised trusted nodes. Our novel gossip-based
propagation algorithm disseminates revocations throughout the network and
provides nodes with a proof of revocation that enables offline verification of
revocations. We demonstrate through simulations that our protocol adequately
scales to national levels.

###### Index Terms:

Self-Sovereign Identity, revocation, offline verification

##  I Introduction

In our modern societies, citizens do not own their identities. The European
Union recently announced that it would maintain a trusted and secure digital
identity for each European citizen [1]. The majority of current digital
identities are also maintained by Big Tech, which results in potential privacy
issues as the digital presence of citizens can be monitored [2]. Furthermore,
these digital identities can be revoked at the platform owner’s discretion
leading to loss of access to a plethora of other dependent connected services
[3]. The Self-Sovereign Identity (SSI) concept overcomes these digital and
societal issues by relying directly on the Internet, which currently does not
embed any native method to determine who is communicating with whom [4]. As
such, the SSI movement aims to create a standardised identity layer for the
Internet, generating digital trust through verifiable identities and putting
citizens at the centre of their data.

Previous works laid out the relevant principles and architectures of SSI [5].
However, in particular, SSI must be able to handle compromised identities,
which might appear as a consequence of theft, loss, or a data breach. For the
past five years in the USA, more than a million data breaches occurred
annually [6], resulting in the loss of billions of credentials. Furthermore,
0.8% of UK passports [7] and 340,000 identity documents in The Netherlands [8]
are lost annually. Revocation of these credentials is required to minimise
further potential negative consequences.

Identity revocation remains a key technical challenge in Self-Sovereign
Identity. As portrayed by Table I (further discussed in section III), previous
SSI distributed revocation designs paved the way but they are still
incomplete. Existing SSI and digital identity solutions such as
Sovrin111https://sovrin.org/, Veramo222https://veramo.io/ (formerly known as
uPort) and IRMA333https://irma.app/ violate the principles of SSI itself by
addressing revocation through centralisation and trusted third parties,
whereas the cardinal requirement for SSI is an authoritarian-free ecosystem.
Furthermore, recent natural disasters demonstrate that assuming the presence
of always up-and-running digital infrastructure is not safe [9]. Digital
identities are to be disaster-proof. Dependence on central parties for
verification prevents offline usability and, moreover, introduces inherent
inequalities in the network, leading to censorship or privacy issues [10].

In this paper, we address the identity revocation problem and alleviate an
important issue that has been hampering the mass deployment of Self-Sovereign
Identities. In a summary, we make the following contributions. We present the
first revocation protocol for SSI that is fully distributed, supports offline
verification of revocations and does not rely on additional trust assumptions.
We evaluate this protocol using our pioneering serverless phone-to-phone
infrastructure [11, 12], and a fully functioning SSI application that is
backed by the Dutch government, which demonstrate the usability of distributed
revocation on smartphones at a national level.

[]

| Domain | Type | Mature1 | Description |  | No network
---
operators
| Offline
---
availability
| No authority
---
interactivity
| Offline
---
verification
| No
---
SPOF
| Full
---
accuracy
This work (section V) | SSI | Attestation | ✓ | First fully distributed SSI revocation mechanism. | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Abraham et al. [13] | SSI | Attestation | ✓ | Revocations stored on public permissioned blockchain. | ✗ | ✓ | ✓ | ✓ | ✓ | ✓
Baars [14] | SSI | Credential | ✗ | Revocations stored on smart contracts. | ✗ | ✗ | ✗ | ✗ | ✗ | ✓
Eschenauer and Gligor [15] | DSN | Node | ✗ | Single authority propagates revocations. | ✗ | ✓ | ✗ | ✓ | ✗ | ✓
Haas et al. [16] | VANET | Certificate | ✗ | RSUs and v2v propagation. | ✗ | ✓ | ✓ | ✓ | ✓ | ✗
IRMA [17] | SSI | Attestation | ✓ | Uses centralised database. | ✗ | ✗ | ✗ | ✗ | ✗ | ✗
Laberteaux et al. [18] | VANET | Certificate | ✗ | RSUs and v2v propagation. | ✗ | ✓ | ✓ | ✓ | ✓ | ✓
Lasla et al. [19] | C-ITS | Node | ✗ | Revocations stored on blockchain and RSUs. | ✗ | ✓ | ✓ | ✗ | ✓ | ✓
Liau et al. [20] | P2P | Certificate | ✗ | Uses distribution points and P2P communication. | ✗ | ✓ | ✗ | ✓ | ✓ | ✓
Popescu et al. [21] | DS | Certificate | ✗ | Revocations handled locally by authority. | ✓ | ✗ | ✗ | ✓ | ✗ | ✗
Sovrin [22] | SSI | Attestation | ✓ | Uses public permissioned blockchain. | ✗ | ✗ | ✓ | ✗ | ✓ | ✓
Speelman [23] | SSI | Credential | ✗ | Uses active verification with issuer. | ✓ | ✗ | ✗ | ✗ | ✗ | ✓
Stokkink et al. [24, 25] | SSI | Attestation | ✓ | (Central) revocation registers, DLs, validity terms. | ✓ | ✗ | ✗ | ✗ | ✗ | ✓
Veramo (uPort) [26] | SSI | Attestation | ✗ | Uses public permissionless blockchain. | ✓ | ✗ | ✓ | ✗ | ✓ | ✓
Xu et al. [27] | SSI | Node | ✗ | List of accepted nodes stored on blockchain. | ✗ | ✓ | ✓ | ✗ | ✓ | ✓

  * 1

Refers to maturity of the technology.

TABLE I: Comparison of existing revocation solutions

##  II Problem Description

Figure 1: Interactions in a Self-Sovereign Identity system.

Because of theft or loss, digital identities may become compromised. To
mitigate further damage, compromised credentials must be revoked. Revocation
is also required when a credential becomes (prematurely) voided, e.g., an
employee who is no longer employed by a company should no longer be given
access to its infrastructure.

Figure 1 portrays the interactions between the three relevant parties of an
SSI system following the definitions set out by the W3C [28]. An Issuer
attests to a claim of a Subject by creating an attestation (step 1). A
Verifier is then able to determine the validity of said claim by
cryptographically verifying the attestation (step 2). In the instance that the
attestation is to be revoked (step 3), the verification of the attestation by
the Verifier must fail. The Subject can not be trusted to make the revocation
available to the Verifier, as this sensibly goes against its own interest.
Furthermore, revocations must be disseminated to any party that needs to
verify the corresponding credential.

Bringing the Verifier in direct contact with the Issuer would go against the
principles of Self-Sovereign Identity as this would defeat the purpose of
attestations [5]. Furthermore, the cardinal requirement of SSI is that no
third party is required or able to observe or otherwise interfere with the
creation or verification of identity data [25].

Existing revocation mechanisms typically introduce centralised mechanics to
handle revocations [17, 22] or require Proof-of-Work blockchains [26]. Both
methods have limitations. First, relying on a centralised infrastructure may
lead to censorship or privacy issues [10]. Second, blockchains suffer from
privacy issues [29], low throughput and limited flexibility [30]. Furthermore,
they are prone to legislation limiting their use [31].

The lack of a fully distributed revocation mechanism limits the mass
deployment of Self-Sovereign Identities. It remains an open problem to design
a revocation mechanism that does not depend on a central infrastructure or on
third parties during verification and allows clients to independently verify
credentials to prevent censorship.

We formulate the following problem description. First, an Issuer revokes their
attestation for a credential. This revocation must be made apparent to all
clients that may verify the credential and acknowledge the Issuer as an
attestor. All clients are interconnected by a network overlay that they
establish and maintain, and in which they have equal permissions. As direct
communication with an Issuer or reliance on centralised infrastructure for
verification goes against the principles of Self-Sovereign Identity, the
propagation of revocations must be decentralised. Furthermore, neither an
Issuer nor a receiving party can be expected to be online at all times, yet,
all revocations are to be spread across the network in order to reach
Verifiers. Furthermore, as all clients have equal permissions, they have to be
able to individually decide whether or not to accept revocations.

##  III Related Work

Table I summarises our analysis of the revocation state-of-the-art in identity
systems, and precises their respective limitations. This table also compares
our revocation mechanism (see section V) to the related work. We consider the
following characteristics: maturity of the solution, network operator
requirement, availability of offline revocations, reliance on interactions
with authorities (i.e., Issuers in the case of SSI), possibility of offline
verification of revocations, presence of single points of failure (SPOFs), and
accuracy of the verification mechanism (e.g. false positives or false
negatives). As one can see, our solution qualitatively outperforms existing
solutions. We note that blockchains allow for the realisation of distributed
revocation. However, they suffer from obstacles such as privacy and security
issues and low throughput [30].

As our key contribution addresses revocation, we focus on related work that
discusses this topic. We found out that revocation in Self-Sovereign Identity
is not widely discussed in academia, and as such, we selected works that
address distributed revocation in a broader context. We organise the related
works in groups that focus on the revocation of (SSI) credentials,
certificates, and nodes.

Sovrin [22] and IRMA [17] propose the usage of cryptographic accumulators for
revocation of (SSI) credentials based on the works of Camenish et al. [32]. A
cryptographic accumulator is a probabilistic data structure that allows a
large set of values to accumulate into a short witness value that can then be
used to prove certain membership operations (e.g. inclusion checks). In the
aforementioned solutions, a subject provides a proof of non-revocability of
their credentials through this witness value. A verifier can then check this
proof using the witness value, which is published on the blockchain. Sovrin
does not allow for offline verification of credentials as both the subject and
the verifier are required to retrieve the latest witness value during the
verification of a credential. Similarly, IRMA does not allow offline
verification because communication with its infrastructure is required.
Furthermore, cryptographic accumulators can be computationally expensive to
the extent that it is discouraged to use them for each verification in IRMA
[17] and their probabilistic nature is prone to false positives. Veramo
(uPort) [26] uses a single Ethereum smart contract for marking attestations as
revoked. The usage of the Ethereum blockchain requires synchronisation of
blocks in order to guarantee certainty on stored revocations. Furthermore, a
single smart contract introduces a security risk [33]. Xu et al. use a
blockchain to store legitimate subjects, indirectly disallowing access for
revoked subjects in the SSI system [27]. Updating this set is performed by the
operators of the blockchain, which introduces centralised authorities. Abraham
et al. propose the usage of a revocation list stored on a blockchain, on which
consensus is reached through the nodes of the blockchain, maintained by
operators [13]. Offline verification is achieved through the storage of this
revocation list. As the revocation list is not stored per authority, clients
require full storage of this list, leading to storage overhead. We note that
all revocations in an SSI system can grow up to gigabytes of storage, which
hinders the deployment on devices with low memory (e.g. smartphones).
Furthermore, the usage of a blockchain introduces further overhead as clients
have to synchronise blocks. Stokkink et al. propose a fully distributed SSI
system using direct peer-to-peer communication [24, 25]. They allow for three
revocation mechanisms: i) linkage to a central revocation register, belonging
to the Issuer; ii) the usage of distributed ledger technology; iii) the usage
of short validity terms. The centralised approach opposes the sovereignty of
the protocol, something that is acknowledged by the authors, blockchains again
suffer from the aforementioned issues and short validity terms place too much
power in the hands of Issuers. Speelman implements the approaches of [24, 25],
and additionally, proposes an active check as the main revocation method [23].
Baars proposes the usage of smart contracts for storing revocations of
attestations [14], introducing security risks [33].

Mechanisms for the revocation of PKI certificates are present in traditional
Public Key Infrastructures (PKIs) such as PKIX [34]. Broadly speaking, a PKI
uses a Certificate Authority (CA) to publish a Certificate Revocation List
(CRL), containing revoked certificates. In this structure, CAs are inherently
central authorities, having relatively absolute power over revocations. These
CAs, acting as trusted third parties, are central points of failure, suffer
from MITM attacks, and are corruptable [35].

PGP’s web of trust [36] attempted to overcome this by handling revocation in a
decentralised fashion, in which the revocation of keys was handled by the
owner through revocation certificates. These certificates indicate that the
key was compromised and should therefore no longer be used. However, PGP and
its web of trust have been shown to be impractical [37] and require central
key servers. Another alternative to PKI is the Decentralised Public Key
Infrastructure (DPKI) [35, 38]. DPKI proposes the usage of alternative storage
solutions for storing revocations of public keys. The proposed solutions use
blockchains and, thus, require synchronisation of blocks for verification,
introducing overhead and possibly low throughput as discussed previously.

Laberteaux et al. discuss the revocation of PKI certificates in vehicular ad
hoc networks (VANETS) through the distribution of CRLs [18]. Distribution is
handled through Road Side Units (RSUs), serving as specialised nodes
propagating the CRLs, and through epidemic spread between vehicles. The
revocations are stored in Bloom filters. Haas et al. build upon this work by
guaranteeing a certain degree of privacy by using group signatures [39] when
requesting certificates from the CA [16]. However, the revocations are handled
by a single CA and the reliance on Bloom filters introduces the possibility of
false positives. Liau et al. propose the distribution of CRLs through direct
peer updates, reducing the communication overhead caused by periodic CRL
synchronisation [20]. Signatures over CRLs allow nodes to build trust in
others. However, direct peer updates may prove to be suboptimal in the case of
highly adaptive networks such as that of mobile devices. Propescu et al.
discuss the revocation of certificates based on the clustering of clients and
probabilistic auditing for honesty of revocation distributors [21]. This
auditing is probabilistic in order to reduce performance requirements,
however, this allows for malicious nodes to possibly exist for quite some
time.

Eschenauer and Gligor discuss the revocation of nodes in distributed sensor
networks [15]. Revocation is handled by a single node serving as an authority,
delegating revocations to regular sensor clients. We note that the
introduction of a single authority goes against the principles of SSI. Lasla
et al. discuss the revocation of malicious vehicles in Cooperative Intelligent
Transportation Systems (CITS) [19]. They use a blockchain for storing
revocations through a distributed vehicle admission and revocation scheme.
Again, we note that blockchains suffer from the aforementioned hurdles such as
privacy and security issues.

##  IV System & Threat Model

We focus on the revocation of attestations and related SSI interactions in an
identity network. An identity network is a peer-to-peer (P2P) network that
implements the identity service that is maintained and used by its peers. The
network can be openly joined by any peer (also called a client) at any time.
We build upon the terminology of the W3C’s DID to define the potential roles
of peers [40]. A peer can assume one or several roles among those of Subject,
Issuer and Verifier: a Subject is a client that holds credentials; an Issuer
attests to a claim and is able to revoke its attestation; a Verifier verifies
credentials. Any two clients are assumed to eventually be able to directly
communicate with each other. We assume that clients are always connected to a
subset of other clients, which are called their neighbours, with which they
exchange identity-related information. Moreover, clients are deemed not to be
necessarily always online. However, when they are online they are reachable
and can communicate with other peers. As such, nodes periodically exchange
membership information with their neighbours, replace them, and exchange
revocation information with them.

Adversaries or malicious actors may be present in the network. We assume that
adversaries do not aid in maintaining the health of the network (via the
spread of revocations discussed in section V). These actors are not able to
drop arbitrary messages but are able to send fabricated messages (e.g.,
replayed) to other clients. These messages are discarded by honest nodes as
they can be evaluated as invalid.

##  V Architecture & Theoretical Analysis

Our revocation mechanism overcomes the hurdle of interactivity with
authorities whilst enabling offline verification. Clients do not require to be
online during verification of a credential, they merely require occasional
synchronisation of revoked attestations by communicating with other nodes in
the network. This is achieved through three concepts.

###  V-A Trusted Issuers

In real life, a person has (relatively speaking) a choice of whether to
acknowledge a certain authority. Following this fashion, this is also possible
in our revocation architecture: each client manages, as we coin, a Trusted
Issuer Storage (TIS). The TIS is a register containing the public keys of the
Issuers that are trusted by a client. Each of these Issuers is referred to as
a Trusted Issuer (TI). Hence, a distinction is made by each client,
individually, on the trusted authorities in the network. A client exclusively
accepts the revocations made by their TIs. The results of acceptance are the
storage of the revocations by the client and further propagation of the
revocations in the network. This significantly reduces storage requirements
under the assumption that a client is not interested in revocations made by an
Issuer that physically resides far away. TIs distinguish themselves from
traditional TTPs as they are only able to influence the legitimacy of
attestations that they created. Furthermore, they only aid in the verification
process and, thus, do not provide a definite answer.

Issuers publish their revocations as sets containing the hashes of revoked
credentials. These sets are uniquely identified using a label and subsequent
sets only contain new revocations. Our implementation uses the SHA3-256
algorithm for hashing and an incremental integer for version labelling. The
version label is unique for each Issuer, but not across revocation sets made
by other Issuers. The Issuer signs its set of revocations and the label for
authenticity. Hence, an issuer revokes its attestation by publishing the hash
of the credential that the attestation belongs to. This counteracts the
possibility for clients to hide a revoked attestation.

###  V-B Attestation Revocation List

All received revocations are stored by a client for later reference in, what
we coin, its Attestation Revocation List (ARL). The ARL is a register holding
the revocations made by the TIs it trusts. It is, similarly to the TIS, stored
and managed by each client individually. In the ARL, revocations are grouped
by the TI that revoked the attestation and by the unique version label that is
assigned by the TI. This makes it possible for a client to store duplicate
revocations if multiple TIs revoked their attestation for the same credential.
This is per design, as it allows Verifiers to build more trust in rejecting a
revoked credential. Furthermore, storing revocations per TI counteracts
malicious TIs from revoking attestations made by other Issuers.

As the number of revocations can grow to a large amount, we use Bloom filters
[41] to speed up the verification process for Verifiers, whilst overcoming
their probabilistic nature. All Verifiers, in addition to storing the
attestations, add them to a Bloom filter. Using their filter, Verifiers first
test whether an attestation belongs to the ARL, after which, upon success, the
definitive search is performed (to handle possible false positives). Raya et
al. [42] discuss the benefits of Bloom filters in Certificate Revocation
Lists, which can provide similar speed improvements for the ARL, as both
require validation of whether an item is part of a set of revoked items.

Furthermore, we note that the ARL can be replaced exclusively by a
probabilistic data structure. A client may choose to accept the probabilistic
nature of a Bloom filter over an exact membership check. Such clients are not
able to aid in the propagation of the revocations, though the low memory
requirements may sometimes prove to make the protocol suitable, e.g., for IoT
devices. However, as a result, verification of credentials on the client may
be affected by false positives. Whilst this does not explicitly impact
security, it could lead to the false rejection of non-revoked credentials. As
such, this is only suitable for Verifiers that expect to verify low numbers of
credentials. For perspective: a Bloom filter of 907.24 KiB, using 10 hash
functions, storing 100,000 items has a false positive probability of 1 in 1
billion.

(a) Centralised revocation propagation

(b) Direct propagation from Issuer

(c) Indirect propagation through gossip

Figure 2: Fully distributed revocation

###  V-C Propagation

In order to disseminate revocations, the architecture requires a protocol that
ensures that information is spread across the entire network, whilst also
ensuring that unavailable clients receive the information at a later instance.
For this, we use a gossip protocol with static re-transmissions. Gossip
protocols are communication protocols that allow for a periodic exchange of
data with (random) peers [43].

In order to maintain a low overhead and allow for selective revocation
updates, revocations are propagated using advertisements. Gossiping nodes
advertise their known revocations, after which a receiving node is able to
selectively request revocations. Advertisements are structured as key-value
pairs of the digest of a TI’s public key and the latest version known by the
gossiping client. A receiving client requests updates by sending back key-
value pairs of the digests of each TI’s public key it is interested in and the
lowest version it is missing. The gossiping client then sends back all the
requested revocations. Authenticity is guaranteed using the signatures. Based
on the publication dates attached to revocations, clients are able to ignore
revocations, optimising storage usage as they may no longer be relevant in the
system due to expired validity terms of the corresponding attestations.

Figure 2 illustrates the communication of revocations from an initial Issuer
to a set of clients. 2(a) portrays the traditional client-server model in
which all revocations are received by the clients through a single central
party, indicated by the green-coloured clients. This system is limited by the
requirement of a direct link between all nodes and the central Issuer. A
central Issuer may introduce security and availability issues and possibly
leads to censorship.

Our gossip-based approach utilises the structure visible in 2(b) and 2(c).
2(b) portrays the initial gossip from an Issuer to a set of neighbours. In
this instance, all clients are honest, acknowledge the Issuer, and are online
during the propagation window (the time at which the Issuer has its gossip
iteration). After which, the clients continue to propagate the revocations, in
the same fashion, eventually spanning across the network. This is depicted in
2(c). Thus, after the initial gossip by the Issuer, no further interaction
with said Issuer is required for the propagation of the revocations. This
figure also shows relays to clients that are already gossiped to, indicating
that clients have multiple opportunities to receive the latest revocations.

Our algorithm has a worst-case runtime of $\mathcal{O}(n)$, with $n$ being the
network size, as in the worst case a single node updates the entire network.
However, it is expected to be logarithmic with respect to the number of nodes,
as each node that has received the latest revocations from a TI can gossip to
the remaining uninformed nodes, speeding up the propagation time for the
remaining nodes. Furthermore, not the entire network is interested in all
revocations.

As becomes apparent from this description, dishonest nodes pose no large
threat to the propagation of revocations. They could introduce a slight delay
due to fewer clients gossiping information or due to the spread of fabricated
revocations, which will be discovered by receiving clients. We do note that
depending on the network topology, Eclipse attacks [44] are a possibility that
can be circumvented through direct connections with Issuers wherever possible.

##  VI Algorithms & Simulation

In order to realise the proposed revocation mechanism discussed in section V,
each client in the network runs three algorithms. A gossiping client runs
algorithm 1, which enables the periodic advertisement of revocations. First, a
random subset of peers is generated using the node selection function (line
2). This function generates a set of peers from the neighbours known by the
client. Next, an advertisement is gossiped to each of these peers (lines 3-4).
Finally, the gossiping client awaits the start of the next gossip interval
(line 5). An advertisement consists of pairs of Issuer public keys and their
latest known version of revocations.

A node receiving an advertisement runs algorithm 2. In this procedure, the
node verifies whether any TI is present in the advertisement (lines 2-3). Then
it verifies, using the FindMissingVersion routine, whether it misses or is
uninformed about revocation versions belonging to the Trusted Issuer (lines
4-5). More specifically, FindMissingVersion determines on an advertisement
containing the revocation version $v_{i}$ part of revocations made by TI
$a_{i}$ with public key $pk_{i}$ whether
$\exists(v_{j},pk_{i})\in\mathcal{ARL}$ such that
$\forall(v_{k},pk_{i})\in\mathcal{ARL}$ it holds that $(v_{j}\geq v_{k}\wedge
v_{j}<v_{i})~{}\vee~{}(v_{j+1}\notin\mathcal{ARL}\wedge v_{j+1}<v_{i})$. If
this is the case, an update is requested from the gossiping client for the
respective Issuer and the lowest missing version (line 6). The advertising
node verifies whether it advertised to the node recently and sends the
revocations.

Following the reception of requested revocations, a node executes algorithm 3.
This procedure verifies the relevance of the revocations (line 1) and their
validity (line 2). This validity check is performed by verifying the attached
signature over the revocations and their version using the public key of the
TI. Finally, the revocations are stored in the ARL (line 3).

###  VI-A Simulation

The analysis of the mechanism is two-fold. Firstly, we discuss a simulation
showcasing scalability amongst a relatively high number of clients using the
aforementioned algorithms. Secondly, we showcase analysis through the
deployment on smartphones in section VII. The simulation was performed on a
system with an Intel i7-6700HQ CPU clocked at 2.60 GHz and 16 GB of RAM.

1

2

3

input : $\mathcal{C}$Set of neighbours

$\mathcal{A}$Set of known Issuer-version pairs

$t_{g}$Gossip interval

$n_{g}$Gossip amount

output : Revocation advertisements

4

5while  _True_ do

6 $\mathcal{C}_{g}\leftarrow$ SelectPeers ($\mathcal{C},n_{g}$);

7 foreach  _$c_{i}\in\mathcal{C}_{g}$_ do

8 GossipRevocations(_$c_{i},\mathcal{A}$_);

9

10 Wait(_$t_{g}$_);

11

12

Algorithm 1 Revocation advertisement gossip

1

2

3

4

input : $\mathcal{A}$Set of known Issuer-version pairs

output : Revocation update request

5 _On reception of $\mathcal{A}$ by Client $c_{i}$_;

6 for  _Issuer $a_{i}$, Version $v_{j}$ in $\mathcal{A}$_ do

7 if  _$a_{i}\in\mathcal{TIS}$_ then

8 $v_{local}$ $\leftarrow$ FindMissingVersion(_$a_{i}$_);

9 if  _$v_{local}$ $<v_{j}$_ then

10 RequestUpdate(_$c_{i}$ ,$a_{i}$,$v_{local}$_);

11

12

13

14

Algorithm 2 Revocation update request procedure

1

2

3

4

5

6

7

8

input : $R$Set of revocations

$v_{i}$Revocations version

$s_{i}$Signature

$pk_{i}$Issuer public key

output : $R\subseteq\mathcal{ARL}$

9

10if  _Issuer $pk_{i}$ in $\mathcal{TIS}$_ then

11 if  _Verify(_$pk_{i}$ , $s_{i}$, $v_{i}|R$_)_ then

12 $\mathcal{AR}L\leftarrow\mathcal{ARL}\cup R$;

13

14 else

15 $\bot$

16

17else

18 $\bot$

Algorithm 3 Revocation reception Figure 3: Revocation scaling

The simulation has been performed through the mimicking of gossip of 340,000
revocations between clients released by a single client serving as a revoking
Issuer. Each client runs the three algorithms and acknowledges the Issuer as a
TI. The measurements of the simulation were gathered by simulating the
execution time of the algorithm until full propagation of the revocations
across a simulated network comprised of 100,000 nodes. The network is
simulated using a weighted regular graph with differing degrees. A uniformly
distributed weight between 0 and 20ms is introduced per link to simulate the
impact of network latency, based on the global average reported by [45].
Furthermore, the cost associated with the transfer of 340,000 SHA3-256 hashes
of 32 bytes is simulated using the global average upload speed of around 65
Mbps [45]. The revocations are released on $t=0$ by the Issuer. Each
simulation is repeated 5 times. Due to multiple paths existing to each node, a
client has multiple opportunities to receive revocations. Revocations are
gossiped to all neighbours on reception.

###  VI-B Simulation Results

The averages of the timings are visible in Figure 3. As expected, increasing
the number of neighbours $d$ per client leads to lower propagation times. The
simulation using $d=100$, however, shows a small decrease in performance when
operating under fewer clients. Nonetheless, at 100,000 clients, this
simulation leads to the lowest propagation time as expected. The observed
decrease in performance, under fewer clients, can be explained by the overhead
introduced by gossiping to 100 clients upon receiving new revocations. The
results seem to indicate that the propagation increases logarithmically with
respect to the number of clients and that the number of neighbours should be
bound, not only due to performance limitations but also due to overhead in
communication introduced by advertising to a larger number of clients.
Overall, the simulation portrays that the algorithm is able to achieve
realistic timings, taking up to 160 seconds to achieve propagation. In
blockchain solutions, the propagation time depends on when the next block
containing the revocations is mined, where the average block time on e.g.
Bitcoin is 10 minutes plus transaction fees.

##  VII Implementation & Performance Analysis

Sections V & VI presented a novel fully distributed revocation algorithm with
offline verification capabilities for Self-Sovereign Identity systems. Based
on this architecture, two implementations have been made using a pioneering
phone-to-phone infrastructure we developed previously444Official (Python)
documentation: https://py-ipv8.readthedocs.io/en/latest/ [11, 12]. This
serverless Web3 fabric allows for direct client-to-client communication,
enabling a fully distributed infrastructure at the core of the solution. Using
this implementation, we wrote an application for Android, backed by the Dutch
National Office for Identity Data (RvIG) [46], showcasing the feasibility on
smartphones. The resulting implementations can be found in our public
repositories555Infrastructure: https://github.com/Tribler/kotlin-
ipv8666Android application: https://github.com/Tribler/trustchain-superapp.
The analysis of the implementation has been performed in a test setup
measuring the time required to gossip revocations between an Issuer and three
Verifier clients running on smartphones. For revocations, we generated a
dataset of 1 million revoked 32 bytes SHA3-256 hashes, a format used by the
implementation. Revocations were split up into sets of 1000 in order to
minimise the impact of a single packet loss. For the default parameters, the
gossip-interval $t_{g}$ was set to $100$ ms in order to maximise the
throughput of gossip. The number of selected peers $n_{g}$ was set to 5 as our
phone-to-phone infrastructure uses 20 simultaneous connections per default.
However, due to the network size of the test setup, the parameters are of
minor impact.

TABLE II:

Phone | Propagation time (s)
---|---
Galaxy s10 | 1066
Pixel 2 XL (emul.) | 903
Pixel 4 (emul.) | 801

###  VII-A Revocation Amount

Table II showcases the revocation scaling in a system of 1 client gossiping
revocations and 3 clients receiving revocations. Our results indicate that the
propagation time scales linearly with respect to the number of revocations.
One million revocations take up to 1066 seconds or just under 18 minutes. As
this can be deemed more than 4 years’ worth of revocations [8] in the
Netherlands, we deem this scalability usable as the propagation is expected to
grow logarithmic with respect to the number of clients in larger networks.

Compared to the simulations discussed in section VI, the performance is worse.
We note that this can be explained mostly due to communication overhead caused
by UDP packet splitting. The tremendous amount of packets led to many packet
drops, in turn leading to the loss of specific revocation versions. As the
reference implementation naively provides the gossiping client with a lower
bound of missing versions, the additional network traffic of already gossiped
versions causes additional packet losses. This snowballing effect worsens the
performance of the algorithm. As such, the investigation of other network
protocols or more sophisticated handling of packet loss can prove to
significantly improve performance. However, the achieved performance can be
deemed usable.

##  VIII Conclusion

This paper addresses revocation in Self-Sovereign Identity systems. We deem
revocation to be the last remaining open issue for SSI to become a feasible
contender for the next generation of identity systems. We proposed the first
fully distributed revocation mechanism requiring no interactivity with any
central parties, whilst adhering to the principles of the SSI paradigm.
Revocations are propagated through the network using a gossip-based protocol,
in which the acknowledgement of revocations is up to the discretion of
Verifiers. Offline verification is enabled through local storage and no
dependency on revoking Issuers. The feasibility of this revocation mechanism
has been validated using a fully distributed SSI implementation. Our results
show that fully distributed SSI is feasible on modern smartphones and that
this is a promising direction to further explore. We conclude that our
proposed architecture is a sizeable step towards placing identity back into
the hands of the citizens.

## References

  * The European Commission [2021] The European Commission, “Commission Recommendation (EU) 2021/946 of 3 June 2021 on a common Union Toolbox for a coordinated approach towards a European Digital Identity Framework,” Jun. 2021. [Online]. Available: http://data.europa.eu/eli/reco/2021/946/oj/eng
  * Tene and Polonetsky [2012] O. Tene and J. Polonetsky, “Big data for all: Privacy and user control in the age of analytics,” _Nw. J. Tech. & Intell. Prop._, vol. 11, p. xxvii, 2012\.
  * Rogers [2020] R. Rogers, “Deplatforming: Following extreme internet celebrities to telegram and alternative social media,” _European Journal of Communication_ , vol. 35, no. 3, pp. 213–229, 2020.
  * Cameron [2005] K. Cameron, “The laws of identity,” _Microsoft Corp_ , vol. 5, pp. 8–11, 2005.
  * Mühle et al. [2018] A. Mühle, A. Grüner _et al._ , “A survey on essential components of a self-sovereign identity,” _Computer Science Review_ , vol. 30, pp. 80–86, Nov. 2018.
  * Johnson [2021] J. Johnson, “Annual number of data breaches and exposed records in the United States from 2005 to 2020,” Mar. 2021. [Online]. Available: https://www.statista.com/statistics/273550/data-breaches-recorded-in-the-united-states-by-number-of-breaches-and-records-exposed/
  * HM Passport Office et al. [2018] HM Passport Office, Border Force _et al._ , “Report your lost or stolen passport,” June 2018. [Online]. Available: https://www.gov.uk/government/news/report-your-lost-or-stolen-passport
  * Brummelkamp et al. [2015] G. Brummelkamp, J. Wils, and J. Boog, “Evaluatie proeftuin vermissing reisdocumenten,” Panteia, Zoetermeer, Tech. Rep., 12 2015.
  * Zhang and Rui [2021] P. Zhang and G. Rui, “China floods: ’digital dark age’ after disaster wreaks havoc on internet and electricity,” July 2021. [Online]. Available: https://www.scmp.com/news/people-culture/environment/article/3142544/china-floods-digital-dark-age-after-disaster-wreaks
  * Khovratovich and Law [2017] D. Khovratovich and J. Law, “Sovrin: digital identities in the blockchain era,” The Sovrin Foundation, Tech. Rep., 2017. [Online]. Available: https://sovrin.org/library/sovrin-digital-identities-in-the-blockchain-era/
  * Halkes and Pouwelse [2011] G. Halkes and J. Pouwelse, “Udp nat and firewall puncturing in the wild,” in _NETWORKING_ , 2011.
  * Zeilemaker et al. [2013] N. Zeilemaker, B. Schoon, and J. Pouwelse, “Dispersy bundle synchronization,” _TU Delft_ , 2013.
  * Abraham et al. [2020] A. Abraham, S. More _et al._ , “Revocable and offline-verifiable self-sovereign identities,” _TrustCom_ , 2020.
  * Baars [2016] D. Baars, “Towards self-sovereign identity using blockchain technology,” Master’s thesis, 2016.
  * Eschenauer and Gligor [2002] L. Eschenauer and V. D. Gligor, “A key-management scheme for distributed sensor networks,” in _CCS_ , 2002.
  * Haas et al. [2011] J. J. Haas, Y. C. Hu, and K. P. Laberteaux, “Efficient certificate revocation list organization and distribution,” _IEEE Journal on Selected Areas in Communications_ , vol. 29, no. 3, pp. 595–604, Mar. 2011.
  * Alpár et al. [2017] G. Alpár, F. van den Broek _et al._ , “Irma: practical, decentralized and privacy-friendly identity management using smartphones,” _HotPETs 2017_ , 2017.
  * Laberteaux et al. [2008] K. P. Laberteaux, J. J. Haas, and Y.-C. Hu, “Security certificate revocation list distribution for vanet,” in _ACM International workshop on VANET_ , 2008, pp. 88–89.
  * Lasla et al. [2018] N. Lasla, M. Younis _et al._ , “Efficient Distributed Admission and Revocation Using Blockchain for Cooperative ITS,” in _NTMS_ , Mar. 2018, pp. 1–5.
  * Liau et al. [2005] C. Y. Liau, S. Bressan, and K.-L. Tan, “Efficient Certificate Revocation : A P2P Approach,” _HICSS’05_ , 2005.
  * Popescu et al. [2003] B. C. Popescu, B. Crispo, and A. S. Tanenbaum, “A certificate revocation scheme for a large-scale highly replicated distributed system,” in _ISCC_ , 2003.
  * Tobin and Reed [2016] A. Tobin and D. Reed, “The inevitable rise of self-sovereign identity,” _The Sovrin Foundation_ , 2016.
  * Speelman [2020] T. Speelman, “Self-Sovereign Identity: Proving Power over Legal Entities,” Master’s thesis, 2020.
  * Stokkink and Pouwelse [2018] Q. Stokkink and J. Pouwelse, “Deployment of a blockchain-based self-sovereign identity,” in _IEEE iThings, GreenCom, CPSCom and SmartData_ , 2018.
  * Stokkink et al. [2020] Q. Stokkink, D. Epema, and J. Pouwelse, “A Truly Self-Sovereign Identity System,” _arXiv:2007.00415_ , 2020.
  * Lundkvist et al. [2016] C. Lundkvist, R. Heck _et al._ , “Uport: A platform for self-sovereign identity,” Oct. 2016. [Online]. Available: https://blockchainlab.com/pdf/uPort_whitepaper_DRAFT20161020.pdf
  * Xu et al. [2020] J. Xu, K. Xue _et al._ , “An identity management and authentication scheme based on redactable blockchain for mobile networks,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 6, 2020.
  * Sporny et al. [2019a] M. Sporny, D. Longley, and D. Chadwick, “Basic concepts,” in _Verifiable Credentials Data Model 1.0_. W3C, Nov. 2019\. [Online]. Available: https://www.w3.org/TR/vc-data-model/
  * Yli-Huumo et al. [2016] J. Yli-Huumo, D. Ko _et al._ , “Where is current research on blockchain technology?—a systematic review,” _PloS one_ , vol. 11, no. 10, p. e0163477, 2016.
  * Hughes et al. [2019] L. Hughes, Y. K. Dwivedi _et al._ , “Blockchain research, practice and policy: Applications, benefits, limitations, emerging research themes and research agenda,” _International Journal of Information Management_ , vol. 49, pp. 114–129, 2019.
  * Xie [2019] R. Xie, “Why china had to ban cryptocurrency but the us did not: A comparative analysis of regulations on crypto-markets between the us and china,” _Wash. U. Global Stud. L. Rev._ , vol. 18, p. 457, 2019.
  * Camenisch and Lysyanskaya [2002] J. Camenisch and A. Lysyanskaya, “Dynamic accumulators and application to efficient revocation of anonymous credentials,” in _CRYPTO_ , 2002.
  * Praitheeshan et al. [2019] P. Praitheeshan, L. Pan _et al._ , “Security analysis methods on ethereum smart contract vulnerabilities: a survey,” _arXiv:1908.08605_ , 2019.
  * [34] IETF, “Public-key infrastructure (x.509) (pkix).” [Online]. Available: https://datatracker.ietf.org/wg/pkix/
  * Allen et al. [2015] C. Allen, A. Brock _et al._ , “Decentralized public key infrastructure. a white paper from rebooting the web of trust,” 2015.
  * Zimmermann [1999] P. Zimmermann, “Why I Wrote PGP,” 1999. [Online]. Available: https://www.philzimmermann.com/EN/essays/WhyIWrotePGP.html
  * Whitten and Tygar [1999] A. Whitten and J. D. Tygar, “Why johnny can’t encrypt: A usability evaluation of pgp 5.0.” in _USENIX Sec._ , 1999.
  * Fromknecht et al. [2014] C. Fromknecht, D. Velicanu, and S. Yakoubov, “A decentralized public key infrastructure with identity retention.” _IACR Cryptol. ePrint Arch._ , vol. 2014, p. 803, 2014.
  * Chaum and Van Heyst [1991] D. Chaum and E. Van Heyst, “Group signatures,” in _Workshop on the Theory and Application of of Cryptographic Techniques_. Springer, 1991, pp. 257–265.
  * Sporny et al. [2019b] M. Sporny, D. Longley, and D. Chadwick, “Verifiable credentials data model 1.0,” Nov. 2019. [Online]. Available: https://www.w3.org/TR/vc-data-model/
  * Bloom [1970] B. H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” _Communications of the ACM_ , vol. 13, no. 7, pp. 422–426, 1970.
  * Raya et al. [2007] M. Raya, P. Papadimitratos _et al._ , “Eviction of Misbehaving and Faulty Nodes in Vehicular Networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 25, no. 8, 2007.
  * Kwiatkowska et al. [2008] M. Kwiatkowska, G. Norman, and D. Parker, “Analysis of a gossip protocol in prism,” _ACM SIGMETRICS_ , vol. 36, no. 3, pp. 17–22, 2008.
  * Castro et al. [2002] M. Castro, P. Druschel _et al._ , “Secure routing for structured peer-to-peer overlay networks,” _ACM SIGOPS Operating Systems Review_ , vol. 36, no. SI, pp. 299–314, 2002.
  * Ookla [2021] Ookla, “Speedtest global index,” July 2021. [Online]. Available: https://www.speedtest.net/global-index
  * RvIG [2020] RvIG, “De mens centraal bij Self Sovereign Identity,” 2020. [Online]. Available: https://magazines.rvig.nl/idee/2020/13/de-mens-centraal-bij-self-sovereign-identity