# Scattering from controlled defects in woodpile photonic crystals

Stefan Aeby  Department of Physics, University of Fribourg, 1700 Fribourg,
Switzerland  Geoffroy J. Aubry<EMAIL_ADDRESS>Department of Physics,
University of Fribourg, 1700 Fribourg, Switzerland  Nicolas Muller  Department
of Physics, University of Fribourg, 1700 Fribourg, Switzerland  HES-SO,
Fribourg, Switzerland  Frank Scheffold<EMAIL_ADDRESS>Department of
Physics, University of Fribourg, 1700 Fribourg, Switzerland

(August 27, 2024)

###### Abstract

Photonic crystals with a sufficiently high refractive index contrast display
partial or full band gaps. However, imperfections in the metamaterial cause
light scattering and extinction of the interfering propagating waves. Positive
as well as negative defect volumes may contribute to this kind of optical
perturbation. In this study, we fabricate and characterize three-dimensional
woodpile photonic crystals, with a pseudo-bandgap for near-infrared optical
wavelengths. By direct laser writing, we intentionally introduce random
defects in the periodic structure. We show that we can model random defect
scattering by considering the difference between the disordered and the
regular structure. Our findings pave the way towards better control and
understanding of the role of defects in photonic materials that will be
crucial for their usability in potential applications.

## Introduction

Dielectric materials with a periodic variation of the refractive index display
photonic stop bands for an optical wave propagating in specific directions
Joannopoulos  _et al._ (2008). The Bragg length $L_{\mathrm{B}}$ is a measure
for the number of crystal layers penetrated by the incident beam and it is
directly related to the scattering strength of the crystal layers. The
attenuation of the wave in the direction of a stopband scales roughly
exponentially as the thickness $L$ of the crystal is increased beyond
$L_{\mathrm{B}}$ Galisteo-López  _et al._ (2003); Marichy  _et al._ (2016).
For a perfect crystal, and $L\to\infty$, destructive interference always leads
to vanishing transmission in the stop band’s direction irrespective of the
refractive index contrast Spry and Kosan (1986). Bandgaps in one and two-
dimensional photonic crystals are now widely employed in applications such as
supercontinuum fiber lasers Russell (2003) and for data processing using
optical modules based on 2D silicon photonic crystal technology Hochberg and
Baehr-Jones (2010).
In a three-dimensional (3D) full photonic bandgap (PGB) material, for specific
wavelengths, the propagation of light is inhibited in all directions. However,
only above a certain threshold refractive index contrast full photonic
bandgaps exist Joannopoulos  _et al._ (2008); Ho  _et al._ (1994). 3D photonic
crystals (PCs) are metamaterials fabricated from mesoscopic building blocks.
In contrast to the case of atomic or molecular crystals, these building blocks
are not identical. Therefore, all photonic crystal materials possess some
intrinsic degree of disorder due to surface roughness, size dispersion,
stress-induced deformations, in addition to defects, stacking faults, crystal
grain boundaries. The influence of disorder is often so strong that the
interaction of the propagating wave with the periodic Bragg planes competes
with scattering on similar length scales. In early work on opal photonic
crystals the manifestation of intrinsic defects has been discussed and a
plethora of studies found that it is nearly impossible to fabricate perfect
crystals made by self-assembly of colloids Vlasov  _et al._ (2000). As a
consequence, artificial opals of polystyrene spheres or air holes in TiO2
(titanium dioxide) display diffuse, multiple-scattering in tandem with Bragg
diffraction Koenderink and Vos (2003); Huang  _et al._ (2001). Similar
observations have been made for quasi-crystals Ledermann  _et al._ (2006).
Improved self-assembly protocols and lithography have led to higher quality
photonic crystals, but despite the progress made, imperfections still play a
significant role López (2003); Soukoulis and Wegener (2011). While disorder in
photonic crystals is often considered a nuisance, it also highlights the rich
and fascinating interplay between defect states, wave tunneling and
percolation, random diffuse scattering, and directed Bragg scattering of light
Skipetrov (2004); Florescu  _et al._ (2010); Froufe-Pérez  _et al._ (2017);
Fernandes  _et al._ (2013); Pratesi  _et al._ (2013); Aubry  _et al._ (2020).
Moreover, the interaction between the band structures and defect scattering
might facilitate the observation of other critical coherent transport
phenomena such as Anderson localization of light. In a seminal paper published
in 1987, Sajeev John suggested the presence of localized defect states close
to the band edge of a photonic crystal, due to multiple scattering and a
reduced density of states John (1987). Finally, defect states can be
introduced in a photonic crystal deliberately to implement a particular
function, such as for optical sensing applications, lasing, or optical
circuitry Joannopoulos  _et al._ (2008); Ishizaki  _et al._ (2013).
Controlling and understanding the role of defects and disorder in photonic
crystals is thus of paramount importance.

## Results

Here, we report on a study about intrinsic and intentionally added defects in
photonic crystals (PCs) Yablonovitch (1987). The tight control over the
position and size of the defects we have, sets our study apart from earlier
work on intrinsic defects Koenderink  _et al._ (2005) or intentionally added
defects in opals García  _et al._ (2011). By direct laser writing (DLW) in a
polymer resist Sun  _et al._ (1999); Deubel  _et al._ (2004) (Photonic
Professional, Nanoscribe, Germany), we fabricate high-quality woodpile (WP)
photonic crystals. For optimal results, we use the IP-Dip photoresist
(Nanoscribe, Germany), refractive index $n_{\mathrm{IP-Dip}}=1.53$ Dottermusch
_et al._ (2019). Our PCs display a pseudo-gap in the near-infrared range as
shown in Fig. 1(a) Ledermann  _et al._ (2006). We intentionally add defects to
our crystals to probe the effect of disorder on the photonic properties of the
PCs. We introduce two types of defects: positive and negative defects, see Fig
1, and we place these defects uniformly over the sample volume with a variable
defect number density $\rho$.

Figure 1: Computer generated renderings of (a) woodpile structure, (b) a
woodpile structure with positive defects, (c) a woodpile structure with
negative defects. Scanning electron micrograph of polymer woodpile structures
fabricated by DLW, with (d) positive (rod cross section area +280%, image
taken at an angle of 52∘), and (e) negative defects (-100%, top view). Scale
bar is 5 $\mu$m.

The basic WP-structures are composed of horizontal arrays of parallel rods,
where $d$ denotes the in-plane distance between two rods. Alternating layers
are rotated by 90∘ and shifted by $d/2$ every 2 layers. Hence, the structure
repeats itself every 4 layers in the stacking direction given be $d_{z}$. We
use a ratio $d_{z}/d=\sqrt{2}$ which results in a face-centered-cubic-lattice
(FCC, see Supplementary Information Fig. S3). The rods of adjacent layers
slightly overlap, as indicated in Figure 1 (a-c), and we define a _rod-
segment_ as the distance between two rod intersections. Note that one rod-
segment corresponds to the primitive unit cell lattice constant, see Fig. S3.
By locally enlarging (reducing) the thickness of a rod-segment, Fig. 1(b,c),
we create positive (negative) defects. We denote the percent increase of the
rod cross sectional area with $\kappa$. We control the thickness of the rods
by setting the power of the DLW-laser below or above the default power used to
fabricate the woodpile crystal. For the crystal structures, the in-plane-
distance between rods, which is equal to the rod-segment length, is set to
$d=1.2\ \mu$m. All the samples have a total size of $70\times 70\times 8.5\
\mu\mathrm{m}^{3}$ which corresponds to five lattice constant of the
conventional cubic unit cell of the FCC lattice (20 rods layers) in
$\hat{\mathbf{z}}$\- direction, i.e., perpendicular to rods long axis, Fig. 1
(a).
Due to the asymmetric shape of the DLW focal volume, set by the point-spread
function of the DLW-microscope objective, the cross-section of the rods is
elliptical with an aspect ratio of nearly three. For each laser power used, we
measure the rod cross sectional area with a scanning electron microscope
(SEM); see Materials and Methods. For the crystal, we find for the long axis
$a=0.42\ \mu$m, and the short axis $b=0.15\ \mu$m.
Figure 2 shows the reflectance and transmittance spectra recorded for a series
of samples.

Figure 2: Experimental reflectance (solid lines) and transmittance (dashed
lines) of woodpile structures with different defect number densities. The
density ranges from 0 to 0.24 $\mathrm{\mu m^{-3}}$. (a) spectra for negative
defects ($\kappa=-74\%$ cross section surface), (b) for positive
($\kappa=+158\%$). The blue ellipses in inset show the standard dimensions of
the WP-rods, while the orange ellipses show the dimensions the negative (a)
and positive (b) defects.

The measurements were performed by Fourier Transform Infrared Spectroscopy
(FTIR, Bruker Vertex 70, and Hyperion Spectrometer). As we use a Cassegrain
mirror-objective in the FTIR-microscope, the light is transmitted and detected
along a hollow cone with an acceptance angle between
$\theta_{\mathrm{min}}$=15∘ and $\theta_{\mathrm{max}}$=30∘ with
$\theta_{\mathrm{mean}}$=22.5∘ compared to the
$\Gamma-\mathrm{X}_{z}$-direction of the crystal (see Supplementary
Information Fig. S5 for the FCC-Brillouin zone scheme). We measure the spectra
averaged over an area of about 40x40 $\mu\mathrm{m}^{2}$ covering wavelengths
between 0.9 and $2.6\ \mu$m while for wavelengths larger than $2.6\ \mu$m, the
polymer absorbs light (for details see Materials and Methods). We use a
silver-coated mirror as a reference for the reflectance spectra. To calibrate
the transmittance, we measure the spectrum of the bare substrate next to the
samples. For each set of fabrication parameters, we produce several samples,
and each curve in Fig. 2 represents an average over three to five different
sample realizations. The darkest lines shows the spectra of the crystalline
samples, i.e., without any added defects. The transmittance (reflectance)
displays a profound dip (peak) indicating the presence of a pseudo-gap in the
chosen incident direction. We find that by increasing the number density
$\rho$ of defects, the peak of the reflectance and the dip of the
transmittance become less marked meaning that the quality of the bandgap is
affected by the presence of defects. Interestingly, we also observe that the
peaks are shifted to higher (lower) wavelengths when increasing the density of
positive (negative) defects. To study this effect quantitatively, we plot in
Fig. 3 the position of the reflectance maxima for different defect sizes and
defect densities against the polymer filling fraction $\phi$ of each sample
(see Materials and Methods for the method used to estimate the filling
fraction).

Figure 3: Center position (circles) of the reflection peak marking the
position of the photonic pseudo-gap in the presence of defects. Each color
corresponds to a different defect size. The values of $\kappa$ denote the
volume of the defect in units of the unperturbed rod-segment. $-100$%
indicates a missing link, $+310$% means the interstitial space between
parallel rods is entirely filled, marking the two extreme cases. The error
bars correspond to the standard deviation of the different realizations for
equal fabrication parameters. The vertical line indicates the filling fraction
of the WP crystal. In red: pseudo-gap span (area) and center (crosses)
calculated with MPB for the WP crystal with elliptical rods as a function of
the rods filling fraction keeping the rods aspect ratio constant. The grey
line shows the expected scaling of the gap wavelength assuming a linear
dependency with the Maxwell-Garnet effective refractive index
$n_{\text{eff}}$.

Interestingly, we find that all the data collapse on a master curve. The
pseudo-gap center wavelength increases roughly linearly with $\phi$,
independent of whether the defect volume or number density is varied to
achieve a certain $\phi$-value. Our results are consistent with effective
medium theories, such as the Maxwell-Garnett mixing formula Garnett (1904),
that predict that the effective refractive index $n_{\mathrm{eff}}$ roughly
scales linearly with $\phi$ in the studied range, see the yellow line in Fig.
3. This shift of $\lambda_{G}$ can be explained as follows. The reflectance
maximum is due to Bragg back-scattering at a scattering angle $\Theta\simeq
180^{\circ}$ where the momentum transfer
$\vec{q}=2\vec{k}\sin[\Theta/2]\equiv\vec{G}$ matches a reciprocal lattice
vector $\vec{G}$ with $\left|k\right|=2\pi n_{\text{eff}}/\lambda_{G}$. Thus,
we expect that the maximas’ $\lambda_{G}$ scale with the effective refractive
index of the medium $n_{\text{eff}}$ such that $\lambda_{G}/n_{\text{eff}}$
remains constant. We, therefore, can explain the linear increase of the
bandgap-center wavelength with a change in the average polymer filling
fraction, and we find this effect to be surprisingly robust against defect
scattering.
We corroborate this finding’s accuracy by band structure calculations with MPB
(MIT Photonic Bands) Johnson and Joannopoulos (2001) for WP photonic crystal
with different filling fractions. For all the filling fractions, the
calculations, shown as red crosses in Fig. 3, were performed for elliptical
rods with a constant aspect ratio of $a/b=0.42/0.15=2.8$. To accurately
compare the simulations with the measurements using a Cassegrain-objective, we
proceed as follows. We calculate the intersections of the widths of the gaps
for all the directions, making an angle $\theta_{\mathrm{eff}}$ relative to
the $\Gamma-\mathrm{X}_{z}$ direction where $\theta_{\mathrm{eff}}$ is defined
by the incident direction and the refraction at the interface, for details see
Materials and Methods. With increasing filling fraction $\phi$, the MPB-value
of $\lambda_{G}$ increases and its evolution follows the Maxwell-Garnett
effective refractive index, as shown in Fig. 3
Next, we study the scattering by the intentionally induced defects. We use a
modified Beer-Lambert’s law to extract the scattering mean free path
$\ell_{\mathrm{s}}$ from the simultaneous reflection $R$ and transmission $T$
measurements of the PC,

$\displaystyle T(L)+R(L)=\alpha\exp\left(-L/\ell_{\mathrm{s}}\right),$ (1)

where $L$ is the thickness of the sample. This relation is valid before the
onset of diffraction and for negligible absorption García  _et al._ (2009).
Both conditions are met in our case over the range of wavelength studied; see
also Supplementary Information Fig. S2. The additional factor $\alpha$ in Eq.
(1) takes account of systematic errors in the calibration procedure. The bare
substrate and the sample covered substrate deviate in two ways. First, the
sample acts as an antireflection coating since the effective index
$n_{\text{eff}}\simeq 1.3$ lies in between glass and air, which leads to an
increased optical transmission $T$. Second, the sample thickness, $L\simeq
8.5\ \mu$m, is only a small multiple of the wavelength, which results in
Fabry-Pérot interferences between the paths reflected by the sample top and
the WP/substrate interface. As a consequence, we observe slow oscillations in
$T(\lambda)$ which complicates proper calibration. To achieve a model
independent calibration, for each set of samples, we take averages of $T+R$
between $\lambda=2.45\ \mu$m, and $2.55\ \mu$m, where we expect
$T+R\simeq\alpha$ for the crystal structure. We find typical values of
$\alpha$ between 0.948 and 0.964. From the data shown in Fig. 2, and using Eq.
(1), we extract $\ell_{\mathrm{s}}$ as a function of $\lambda$ as shown in
Fig. 4.

Figure 4: Turbidity (inverse of the scattering mean free path) of woodpile
structures with (a) negative and (b) positive defects. The different color of
the curves encode the defect number density $\rho$ in $\mathrm{\mu m^{-3}}$ in
the sample. The samples are the same as in Fig. 2.

## Discussion

We first note that the turbidity of the WP crystals, given by the reciprocal
of the scattering mean free path, $1/\ell_{\mathrm{s}}$, is finite, and it
rises in the low-wavelength regime. The residual scattering from WP crystals,
observed previously in Deubel  _et al._ (2004), is caused by intrinsic
roughness, small displacements, undulations, and deformations in the crystal.
The turbidity of a crystal in the presence of artificially added defects is
therefore determined by defect scattering and by intrinsic scattering. In Fig.
5, we illustrate how we can understand the scattering from our materials as a
sum of scattering from the WPs and the intentionally added defects. If we
assume that these two contributions contribute independently, we can express
the measured turbidity $1/\ell_{\mathrm{s}}$ as follows Pine  _et al._ (1990)

$\displaystyle\frac{1}{\ell_{\mathrm{s}}}=\frac{1}{\ell_{\mathrm{s,0}}}+\frac{1}{\ell_{\mathrm{s,ind}}},$
(2)

where $1/\ell_{\mathrm{s,0}}$ corresponds to the intrinsic scattering and
$1/\ell_{\mathrm{s,ind}}$ to the artificial defects scattering.

Figure 5: The measured turbidity of the samples is the sum of two
contributions, the intrinsic turbidity of the woodpile crystals (due to DLW
imperfections) on one hand, and the induced turbidity due to the artificially
added defects on the other hand.

The same expression can be derived in the frame of the classical theory for
the resistivity of ordinary metals Ashcroft and Mermin (1976). In the latter
case the resistivity is controlled by the scattering mean free path of
electrons; $1/\ell_{\mathrm{s,0}}$ corresponds to the residual resistivity
contribution, due to intrisic defects, and $1/\ell_{\mathrm{s,ind}}$ to the
temperature dependent contribution $\propto T$, also known as the Wiedemann-
Frantz law, due to electron-phonon scattering.
Both for negative (Fig. 4(a)) and positive (Fig. 4(b)) defects, we see that
the induced turbidity increases with the defect number density $\rho$. In Fig.
6, we plot the same data, $1/\ell_{\mathrm{s,ind}}$, at a selected wavelength
($\lambda_{0}=1.57\ \mu$m) as a function of the defect number density.

Figure 6: Induced turbidity for different defect volumes measured at
$\lambda_{0}=1.57\ \mu$m for negative (a) and positive defects (b) as a
function if the defects number density. Each color corresponds to a different
relative change of the rod cross section for a single defect with respect to
the default rod. Lines are linear fits done on the first points.

We plot the data for negative and positive defects of different size in
separate panels Fig. 6 (a) and (b). The induced turbidity increases linearly
with $\rho$ for sufficiently small defect number densities, supporting the
validity of our assumptions in Eq.(2) in this limit, $\rho\leq 0.1\ \mu$m-3.
The linear scaling of $1/\ell_{\mathrm{s,ind}}$ suggests that induced defects
act as independent scatterers. Indeed, the turbidity of a medium consisting of
identical uncorrelated scatterers is given by
$1/\ell_{\mathrm{s}}=\rho\sigma$, where $\sigma$ denotes the total scattering
cross-section of a scatterer. For higher concentrations, positional
correlations and proximity effects lead to deviations from the linear
dependence Fraden and Maret (1990); Rezvani Naraghi  _et al._ (2015); Aubry
_et al._ (2017).

Figure 7: Total scattering cross-section of defect scatterers. Symbols show
$C_{\mathrm{sca,hc}}$ extracted from the slopes of the curves
$\left(\rho\ell_{\mathrm{s,ind}}\right)^{-1}$ (solid lines shown in Fig. 6).
The effective radius of the defect rod-segments is denoted by $r_{\text{d}}$
with $r_{\text{d}}=r=0.25\mu$m for the standard rod size in the crystal
(vertical dashed line).

Our results suggest that the initial slope of $1/\ell_{\mathrm{s}}(\rho)$ is a
measure for the total scattering cross section of defects

$\displaystyle\frac{1}{\ell_{\mathrm{s,ind}}}$ $\displaystyle=\rho
C_{\mathrm{sca,hc}}.$ (3)

In Fig. 7, we report the values for $C_{\mathrm{sca,hc}}$ extracted in the
low-$\rho$ regime as a function of
$r_{\mathrm{d}}=\sqrt{a_{\mathrm{d}}b_{\mathrm{d}}}$ where $a_{\mathrm{d}}$
and $b_{\mathrm{d}}$ are the long and short axis of the defect rod-segments.
For all the samples studied, we report data for five different wavelengths.
Inspired by earlier work on disordered opals, Ref. Koenderink  _et al._
(2005), we model the defect scattering in the frame of the 1st Born, also
known as Rayleigh-Gans-Debye (RGD) scattering, approximation. We hypothesize
that we can treat the WP crystal as an effective, homogeneous background
medium, and scattering arises from the local density differences, as shown in
Figure 5. To this end, we calculate the known RGD-expression for the total
scattering cross-section of a hollow cylinder $C_{\mathrm{sca,hc}}$ with a
length $d=1.2\mu$m equal to a rod segment Bohren and Huffman (1998).

For simplicity, in our calculations, we consider scattering from hollow
cylinders with $n_{\mathrm{IP-Dip}}$ in air ($n_{\text{air}}=1$), and limiting
radii $r_{\mathrm{d}}=\sqrt{a_{\mathrm{d}}\cdot b_{\mathrm{d}}}$,
$r=\sqrt{a\cdot b}=0.25\ \mu$m. For positive defects $r_{\mathrm{d}}>r$ while
for negative defects $r_{\mathrm{d}}<r$. We explicitly take into account the
optical geometry imposed by the Cassegrain objective. To this end, we
calculate $C_{\mathrm{sca,hc}}$ for an angle between the incoming beam and the
cylinder axis
$\zeta=90^{\circ}-\left<\theta_{\mathrm{eff}}\right>=71.3^{\circ}$.
$\theta_{\mathrm{eff}}$ is the angle after refraction by the effective medium
($n_{\mathrm{eff}}$) when the incident angle is $22.5^{\circ}$ (Cassegrain
objective). We calculate $\left<\theta_{\mathrm{eff}}\right>$ by averaging
$\theta_{\mathrm{eff}}$ over the different $n_{\mathrm{eff}}$ obtained by
varying the filling fraction over the experimental range ($0.3<\phi<0.5$). The
effective refractive index $n_{\mathrm{eff}}$ also enters via the effective
wavenumber $k_{\mathrm{eff}}=2\pi n_{\mathrm{eff}}/\lambda_{0}$.
In contrast to earlier studies on disordered opals Koenderink and Vos (2003);
Koenderink  _et al._ (2005), our entire modeling predictions, shown as lines
in Fig. 7, are fit-parameter free. Overall, we find an good agreement between
the data and the model: the calculated scattering cross-sections follow the
trend of the experimental data. The agreement between theory and experiment is
nearly quantitative for the higher wavelengths where the intrinsic scattering
is negligible, and the transmission of the unperturbed crystal is high,
signaling a trend toward an effective homogeneous medium.
In conclusion, in this study, we have quantified the effect of intrinsic and
induced defects on photonic crystals’ optical properties. We demonstrate that
both the bandgap position and its quality are simultaneously affected by
defect scattering. The study presented in this work can provide essential
guidelines how to quantify and model defect scattering. Our study also
provides a modelling framework for diffuse scattering in PCs that lays the
ground toward more complex disordered PCs based photonic materials. Such
materials, based on higher refractive index building block, could become
crucial to reach conditions for Anderson localization of light Sperling  _et
al._ (2016).

## Materials and methods

### Rod size measurement

The lateral size of the rods, or the short axis of the elliptical cross
section, can be assessed by taking a top-view electron micrograph. The
measurement of the long axis of the elliptical rods inside the structure is
more difficult. We tried to obtain a side-view of the rods using ion-beam
milling but this posed problems due to the melting of the polymer when exposed
to the ion beam. To circumvent this problem, we wrote single rods with
different laser powers between two large pillars, as shown Supplementary
Information Fig. S1. This procedure allowed us to take SEM-images of the rods
created by using different laser powers in DLW, from the top and at an
inclined angle of 45∘. We measure the short and long axis several times at
different locations. The FWHM of the grey value profile of a line
perpendicular to the rod is taken to determine the size. We obtain a mean
value by measuring the size on different positions on the same image and get a
standard deviation of about 7%, which we attribute to the uneven surface of
the rods and the limited accuracy of the procedure.

### Absorption spectrum of the IP-Dip polymer

Supplementary Information Fig. S2 shows the absorption spectrum of a glass
substrate coated with a $10\mu$m layer of developed IP-Dip photoresist. In the
wavelength-band between $\lambda=1$ and $2.6\ \mu$m absorptive losses are
small. Between $\lambda=2.45$ and $2.55\ \mu$m we observe a average drop of
transmittance by 2.7%. For the thinner ($L\simeq 8.5\mu$m) and air-filled WP-
layers we estimate that absorptive losses attenuate the transmitted power by
less than 1%.

### Assessment of the Polymer Filling Fraction

The overlap between alternating layers of rods is taken into account in order
to accurately estimate numerically the filling fraction of each sample. To
this end, we discretize the unit cell of the digital representation of the
woodpile structure, and label every volume element (or voxel) belonging to at
least one rod. We then calculate the ratio between the labeled and unlabeled
voxels to get the filling fraction. Using this method, we calculate $\phi_{0}$
for the unit cell of the perfect woodpile, but also $\phi_{0,\mathrm{d}}$ for
the unit cell containing a single defect. The parameters of the rods are taken
from the rod size measurements.For a sample having a defect density $\rho$,
the filling fraction of the sample is then $\phi=(1-\rho V_{0})\phi_{0}+\rho
V_{0}\phi_{0,\mathrm{d}}$ where $V_{0}$ is the volume of the unit cell.

### Band structure calculations

The woodpile is a FCC lattice, see Supplementary Information Fig. S3. Its band
structure is calculated in the first Brilloin zone, see Supplementary
Information Fig. S5. Usually, the (pseudo)gap is observed in the
$\Gamma-\mathrm{X}_{z}$ direction (See Supplementary Information Fig. S5). In
our measurement, because of the Cassegrain objective, we observe transmission
of light having an incident angle between 15∘ and 30∘. We therefore have to
compare our measurements with band structure calculation for the same angles.
To achieve this, we performed calculations of the band structure in the
$\Gamma-\mathrm{P}_{\theta}(\varphi)$ directions as a function of the
azimuthal angle $\varphi$ for a fixed polar angle of
$\theta=\arcsin\left(\theta_{\mathrm{mean}}/n_{\mathrm{eff}}\right)$ with
$\theta_{\mathrm{mean}}=(15^{\circ}+30^{\circ})/2$ due to the Cassegrain
objective and $n_{\mathrm{eff}}(\phi)$ calculated with the Maxwell-Garnett
mixing formula Garnett (1904) (See Supplementary Information Fig. S5 and its
legend for the geometry).

Supplementary Information Figure S4 shows the band structure for different
$\Gamma-\mathrm{P}_{\theta}(\phi)$ directions. $\theta$ is constant and $\phi$
is equally distributed between 0 and 90∘ (for symmetry reasons we don’t need
to calculate for all angles between 0 and 360∘ because the structure is
invariant by a rotation of 90∘ around the $\hat{\mathbf{z}}$ axis). The
bandgap corresponds to the intersection of the bandgaps calculated for
$\phi\in[0,90^{\circ}]$.

### Rayleigh-Gans-Debye scattering of a hollow cylinder

The form factor of a finite cylinder of radius $r$ and length $L$ (see
Supplementary Fig. S6 for the geometry), illuminated by a beam making an angle
$\zeta$ with its axis oriented along the $\hat{\mathbf{z}}$ axis, as found in
Bohren and Huffman (1998), is

$\displaystyle f_{\mathrm{c}}$ $\displaystyle=\frac{1}{\pi
r^{2}L}\int_{-L/2}^{L/2}e^{-ikAz}dz\int_{0}^{r}\rho\,d\rho\int_{0}^{2\pi}e^{-ik\rho(B\cos\psi+C\sin\psi)}d\psi.$
(4)

The integration is done in cylindrical coordinates $(\rho,\psi,z)$, which axis
$\hat{\mathbf{z}}$ is oriented along the direction of the cylinder. Note that
in this calculation, to take advantage of the radial symmetry, the cylinders
are oriented _along_ the $\hat{\mathbf{z}}$ axis, whereas in the rest of the
paper they are _perpendicular_ to the $\hat{\mathbf{z}}$ axis. $k=2\pi
n_{\mathrm{eff}}/\lambda_{0}$ (where $n_{\mathrm{eff}}$ is the effective
refractive index of the medium, and $\lambda_{0}$ the wavelength in vacuum of
the incoming beam) is the wave number. Finally,

$\displaystyle A$ $\displaystyle=\cos\zeta+sin\theta\cos\varphi$ (5)
$\displaystyle B$ $\displaystyle=\sin\theta\sin\varphi$ (6) $\displaystyle C$
$\displaystyle=\cos\theta-sin\zeta$ (7) $\displaystyle M$
$\displaystyle=\sqrt{B^{2}+C^{2}},$ (8)

where $\theta\in\left[0,\pi\right]$ and $\varphi\in\left[0,2\pi\right]$ are
the spherical coordinates angles for scattered wave.

To calculate the form factor of a hollow cylinder, one just has to perform the
second integration between $r_{1}$ and $r_{2}$ (the inner and outer radii of
the cylinder) instead of $0$ and $r$. Performing all the integration, we
obtain

$\displaystyle
f_{\mathrm{hc}}(\theta,\varphi;\zeta)=\frac{2}{L(r_{2}^{2}-r_{1}^{2})}\frac{r_{2}J_{1}(kr_{2}M)-r_{1}J_{1}(kr_{1}M)}{kM}\frac{2\sin(kAL/2)}{kA}$
(9)

$J_{1}$ is the Bessel function of the first kind of order 1.

The Rayleigh-Gans-Debye scattering cross section for a cylinder making an
angle of $\zeta$ with respect to the incoming beam is then defined through the
integral over all solid angles $\Omega$

$\displaystyle C_{\mathrm{sca,hc}}(\zeta)$
$\displaystyle=\int_{4\pi}\frac{k^{4}}{4\pi^{2}}(m-1)^{2}v^{2}\left|f_{\mathrm{hc}}(\theta,\varphi;\zeta)\right|^{2}\left[\cos^{2}\theta\cos^{2}\varphi+\sin^{2}\varphi\right]d\Omega.$
(10)

The integrations over $\theta$ and $\varphi$ are performed numerically.

In this paper, the incoming light makes an angle
$\zeta=\frac{\pi}{2}-\theta_{\mathrm{eff}}$ with the axis of the cylinders,
where
$\theta_{\mathrm{eff}}=\arcsin{\left(\theta_{\mathrm{mean}}/n_{\mathrm{eff}}\right)}$.
$n_{\mathrm{eff}}$ should depend on the filling fraction, each curve and point
plotted in the main text Fig. 7 is deduced from measurements done varying the
filling fraction. We therefore kept $n_{\mathrm{eff}}$ constant and equal to
the value of the Maxwell-Garnett refractive index of the perfect structure.

###### Acknowledgements.

We thank Luis Froufe-Pérez for fruitful discussions. We acknowledge financial
support by the Swiss National Science Foundation under grants No. 169074 and
188494. This work benefited from support from the Swiss National Science
Foundation via the National Center of Competence in Research Bio-Inspired
Materials.

## Data and code availability

All experimental and numerical data discussed in this manuscript, and the
associated codes for analyzing or generating those data can be obtained upon
reasonable request.

## Competing interest

The authors declare no competing interest.

## References

  * Joannopoulos  _et al._ (2008) J. Joannopoulos, S. Johnson, J. Winn, and R. Meade,  _Photonic Crystals: Molding the Flow of Light_, 2nd ed. (Princeton University Press, 2008).
  * Galisteo-López  _et al._ (2003) J. F. Galisteo-López, E. Palacios-Lidón, E. Castillo-Martínez, and C. López, Optical study of the pseudogap in thickness and orientation controlled artificial opals, Phys. Rev. B 68, 115109 (2003).
  * Marichy  _et al._ (2016) C. Marichy, N. Muller, L. S. Froufe-Pérez, and F. Scheffold, High-quality photonic crystals with a nearly complete band gap obtained by direct inversion of woodpile templates with titanium dioxide, Scientific Reports 6, 21818 (2016).
  * Spry and Kosan (1986) R. J. Spry and D. J. Kosan, Theoretical analysis of the crystalline colloidal array filter, Appl. Spectrosc. 40, 782 (1986).
  * Russell (2003) P. Russell, Photonic crystal fibers, Science 299, 358 (2003).
  * Hochberg and Baehr-Jones (2010) M. Hochberg and T. Baehr-Jones, Towards fabless silicon photonics, Nature Photonics 4, 492 (2010).
  * Ho  _et al._ (1994) K. Ho, C. Chan, C. Soukoulis, R. Biswas, and M. Sigalas, Photonic band gaps in three dimensions: New layer-by-layer periodic structures, Solid State Communications 89, 413 (1994).
  * Vlasov  _et al._ (2000) Y. A. Vlasov, V. N. Astratov, A. V. Baryshev, A. A. Kaplyanskii, O. Z. Karimov, and M. F. Limonov, Manifestation of intrinsic defects in optical properties of self-organized opal photonic crystals, Phys. Rev. E 61, 5784 (2000).
  * Koenderink and Vos (2003) A. F. Koenderink and W. L. Vos, Light exiting from real photonic band gap crystals is diffuse and strongly directional, Phys. Rev. Lett. 91, 213902 (2003).
  * Huang  _et al._ (2001) J. Huang, N. Eradat, M. E. Raikh, Z. V. Vardeny, A. A. Zakhidov, and R. H. Baughman, Anomalous coherent backscattering of light from opal photonic crystals, Phys. Rev. Lett. 86, 4815 (2001).
  * Ledermann  _et al._ (2006) A. Ledermann, L. Cademartiri, M. Hermatschweiler, C. Toninelli, G. A. Ozin, D. S. Wiersma, M. Wegener, and G. von Freymann, Three-dimensional silicon inverse photonic quasicrystals for infrared wavelengths, Nature Materials 5, 942 (2006).
  * López (2003) C. López, Materials aspects of photonic crystals, Advanced Materials 15, 1679 (2003).
  * Soukoulis and Wegener (2011) C. M. Soukoulis and M. Wegener, Past achievements and future challenges in the development of three-dimensional photonic metamaterials, Nature Photonics 5, 523 (2011).
  * Skipetrov (2004) S. E. Skipetrov, Disorder is the new order, Nature 432, 285 (2004).
  * Florescu  _et al._ (2010) M. Florescu, S. Torquato, and P. J. Steinhardt, Effects of random link removal on the photonic band gaps of honeycomb networks, Applied Physics Letters 97, 201103 (2010).
  * Froufe-Pérez  _et al._ (2017) L. S. Froufe-Pérez, M. Engel, J. J. Sáenz, and F. Scheffold, Band gap formation and anderson localization in disordered photonic materials with structural correlations, Proceedings of the National Academy of Sciences 114, 9570 (2017).
  * Fernandes  _et al._ (2013) S. N. Fernandes, Y. Geng, S. Vignolini, B. J. Glover, A. C. Trindade, J. P. Canejo, P. L. Almeida, P. Brogueira, and M. H. Godinho, Structural color and iridescence in transparent sheared cellulosic films, Macromolecular Chemistry and Physics 214, 25 (2013).
  * Pratesi  _et al._ (2013) F. Pratesi, M. Burresi, F. Riboli, K. Vynck, and D. S. Wiersma, Disordered photonic structures for light harvesting in solar cells, Opt. Express 21, A460 (2013).
  * Aubry  _et al._ (2020) G. J. Aubry, L. S. Froufe-Pérez, U. Kuhl, O. Legrand, F. Scheffold, and F. Mortessagne, Experimental evidence for transparency, band gaps and anderson localization in two-dimensional hyperuniform disordered photonic materials, arXiv (2020), submitted, 2003.00913 .
  * John (1987) S. John, Strong localization of photons in certain disordered dielectric superlattices, Phys. Rev. Lett. 58, 2486 (1987).
  * Ishizaki  _et al._ (2013) K. Ishizaki, M. Koumura, K. Suzuki, K. Gondaira, and S. Noda, Realization of three-dimensional guiding of photons in photonic crystals, Nature Photonics 7, 133 (2013).
  * Yablonovitch (1987) E. Yablonovitch, Inhibited spontaneous emission in solid-state physics and electronics, Phys. Rev. Lett. 58, 2059 (1987).
  * Koenderink  _et al._ (2005) A. F. Koenderink, A. Lagendijk, and W. L. Vos, Optical extinction due to intrinsic structural variations of photonic crystals, Phys. Rev. B 72, 153102 (2005).
  * García  _et al._ (2011) P. D. García, R. Sapienza, C. Toninelli, C. López, and D. S. Wiersma, Photonic crystals with controlled disorder, Phys. Rev. A 84, 023813 (2011).
  * Sun  _et al._ (1999) H.-B. Sun, S. Matsuo, and H. Misawa, Three-dimensional photonic crystal structures achieved with two-photon-absorption photopolymerization of resin, Applied Physics Letters 74, 786 (1999).
  * Deubel  _et al._ (2004) M. Deubel, G. von Freymann, M. Wegener, S. Pereira, K. Busch, and C. M. Soukoulis, Direct laser writing of three-dimensional photonic-crystal templates for telecommunications, Nature Materials 3, 444 (2004).
  * Dottermusch  _et al._ (2019) S. Dottermusch, D. Busko, M. Langenhorst, U. W. Paetzold, and B. S. Richards, Exposure-dependent refractive index of nanoscribe IP-Dip photoresist layers, Opt. Lett. 44, 29 (2019).
  * Garnett (1904) J. C. M. Garnett, Colours in metal glasses and in metallic films, Philos. Trans. R. Soc. London A: Math., Phys. 203, 385 (1904).
  * Johnson and Joannopoulos (2001) S. G. Johnson and J. D. Joannopoulos, Block-iterative frequency-domain methods for Maxwell’s equations in a planewave basis, Opt. Express 8, 173 (2001).
  * García  _et al._ (2009) P. D. García, R. Sapienza, L. S. Froufe-Pérez, and C. López, Strong dispersive effects in the light-scattering mean free path in photonic gaps, Phys. Rev. B 79, 241109 (2009).
  * Pine  _et al._ (1990) D. J. Pine, D. A. Weitz, J. X. Zhu, and E. Herbolzheimer, Diffusing-wave spectroscopy: dynamic light scattering in the multiple scattering limit, J. Phys. France 51, 2101 (1990).
  * Ashcroft and Mermin (1976) N. W. Ashcroft and N. D. Mermin,  _Solid state physics_ (Harcourt College Publishers, 1976).
  * Fraden and Maret (1990) S. Fraden and G. Maret, Multiple light scattering from concentrated, interacting suspensions, Phys. Rev. Lett. 65, 512 (1990).
  * Rezvani Naraghi  _et al._ (2015) R. Rezvani Naraghi, S. Sukhov, J. J. Sáenz, and A. Dogariu, Near-field effects in mesoscopic light transport, Phys. Rev. Lett. 115, 203903 (2015).
  * Aubry  _et al._ (2017) G. J. Aubry, L. Schertel, M. Chen, H. Weyer, C. M. Aegerter, S. Polarz, H. Cölfen, and G. Maret, Resonant transport and near-field effects in photonic glasses, Phys. Rev. A 96, 043871 (2017), 1705.07634 .
  * Bohren and Huffman (1998) C. F. Bohren and D. R. Huffman,  _Absorption and Scattering of Light by Small Particles_ (Wiley, New York, 1998).
  * Sperling  _et al._ (2016) T. Sperling, L. Schertel, M. Ackermann, G. J. Aubry, C. Aegerter, and G. Maret, Can 3D light localization be reached in ‘white paint’?, New Journal of Physics 18, 013039 (2016), 1510.08092 .

## Supplementary Information

This document contains all the figures referenced in the Materials and Methods
section.

Figure S1: Structure printed by DLW to determine the dimensions of a single
rod. (a) Top view; (b) same sample viewed from different angle. We placed the
defects at different heights in order to allow a size measurement from a side
view. This inforamtion is then used to calculate the long and short axis of
the rod cross section as discussed in the text. We have color-code the image
as follows: (blue) the laser power is set to the usual writing power of the
woodpile crystal structure ($I_{0}$). On the left hand side of the structure,
a single positive defect per line is shown in red ($2\,I_{0}$) (a) and orange
($1.44\,I_{0}$) (b). On the right hand side, the entire rod is written with
the increased laser power. Scale bars are 20$\mu$m. Figure S2: Absorption
spectrum of a thin homogeneous film of made of the developed photoresin IP-Dip
used in the study. The thickness of the layer is $10\ \mu$m. The red shaded
area indicates the onset of absorption of the water vapour in air. The yellow
shaded areas highlight the absorption bands of the polymer.  Figure S3:
Conventional FCC unit cell of the woodpile structure. The black arrows
correspond to the cartesians unit vectors, the red arrows to the FCC primitive
vectors. The volume marked in dark yellow corresponds shows the primitive unit
cell. Figure S4: Band structure calculation for the directions making a polar
angle $\theta=19.1^{\circ}$ with the $\hat{\mathbf{z}}$ direction calculated
for the perfect structure where the cylinder cross-section have an aspect
ratio $a/b$. The blue area is the bandgap. Figure S5: The blue volume
corresponds to the first Brilloin zone of the FCC lattice whose primitive
vectors are drawn in red. The blue vectors correspond to the reciprocal space
primitive vectors. $\Gamma$, Xz, W, U are high symmetry points on the Brilloin
zone surface. P${}_{\theta}(\varphi)$ is the point on the first Broilloin zone
whose coordinates are $(\theta,\varphi)$ in spherical coordinates. Figure S6:
Coordinates used in the derivation of the Rayleigh-Gans-Debye scattering
cross-section of a finite cylinder.


If $G_{1}\sim G_{2}$, then $G_{1}$ and $G_{2}$ are Block consistent.

Let $\prec$ denote an arbitrary total ordering of the nodes (processes)
$p_{i}$ and $p_{j}$.

_[Total ordering]_ _Total ordering_ is a relation $\Rightarrow$ satisfying the
following: for any event $v_{i}$ in $p_{i}$ and any event $v_{j}$ in $p_{j}$,
$v_{i}\Rightarrow v_{j}$ if and only if either (i) $C_{i}(v_{i})<C_{j}(v_{j})$
or (ii) $C_{i}(v_{i})$=$C_{j}(v_{j})$ and $p_{i}\prec p_{j}$.

This defines a total ordering relation. The Clock Condition implies that if
$v_{i}\rightarrow v_{j}$ then $v_{i}\Rightarrow v_{j}$.

####  8.2.7 Main chain

The Main chain consists of new blocks, each of which is created based on a new
Atropos.

######  Definition 8.12 (Consistent Chain).

Two DAGs $G_{1}$ and $G_{2}$ are Chain consistent: if $G_{1}$ and $G_{2}$ are
Block consistent and they have the same number of blocks.

######  Proposition 8.12.

All honest nodes are Chain consistent.

######  Theorem 8.13 (Finality).

All honest nodes produce the same ordering and consensus time for finalized
event blocks.

###### Proof.

As proved in the above Section 8.2.3, the set of roots is consistent across
the nodes. From section 8.2.4, the set of Clotho events is consistent across
the nodes. In Section 8.2.5, our topological sorting of Clotho, which uses
validator’stake, Lamport’s timestamp is deterministic, and so it will give the
same ordering of Atropos events. The Atropos’s timestamp is consistent between
the nodes, as proved in Section 8.2.5. Section 8.2.6 outlines a proof that the
topology ordering of vertices in each subgraph under an Atropos is the same
across the nodes. Also finalized event blocks in each block is assigned the
same consensus time, which is the Atropos’s consensus timestamp. ∎

####  8.2.8 Fork free

######  Definition 8.13 (Fork).

The pair of events ($v_{x}$, $v_{y}$) is a fork if $v_{x}$ and $v_{y}$ have
the same creator, but neither is a self-ancestor of the other. Denoted by
$v_{x}\pitchfork v_{y}$.

For example, let $v_{z}$ be an event in node $n_{1}$ and two child events
$v_{x}$ and $v_{y}$ of $v_{z}$. if $v_{x}\hookrightarrow^{s}v_{z}$,
$v_{y}\hookrightarrow^{s}v_{z}$, $v_{x}\not\hookrightarrow^{s}v_{y}$,
$v_{y}\not\hookrightarrow^{s}v_{z}$, then ($v_{x}$, $v_{y}$) is a fork. The
fork relation is symmetric; that is $v_{x}\pitchfork v_{y}$ iff
$v_{y}\pitchfork v_{x}$.

######  Lemma 8.14.

$v_{x}\pitchfork v_{y}$ iff $cr(v_{x})=cr(v_{y})$ and $v_{x}\parallel v_{y}$.

###### Proof.

By definition, ($v_{x}$, $v_{y}$) is a fork if $cr(v_{x})=cr(v_{y})$,
$v_{x}\not\hookrightarrow^{a}v_{y}$ and $v_{y}\not\hookrightarrow^{a}v_{x}$.
Using Happened-Before, the second part means $v_{x}\not\rightarrow v_{y}$ and
$v_{y}\not\rightarrow v_{x}$. By definition of concurrent, we get
$v_{x}\parallel v_{y}$. ∎

######  Lemma 8.15.

(Fork detection). If there is a fork $v_{x}\pitchfork v_{y}$, then $v_{x}$ and
$v_{y}$ cannot both be roots on honest nodes.

###### Proof.

Here, we show a proof by contradiction. Any honest node cannot accept a fork
so $v_{x}$ and $v_{y}$ cannot be roots on the same honest node. Now we prove a
more general case. Suppose that both $v_{x}$ is a root on node $n_{x}$ and
$v_{y}$ is root on node $n_{y}$, where $n_{x}$ and $n_{y}$ are honest nodes.
Since $v_{x}$ is a root, it reached events created by more than $2/3$ of total
validating power. Similarly, $v_{y}$ is a root, it reached events created by
more than $2W/3$. Thus, there must be an overlap of more than $W$/3 members of
those events in both sets. Since Lachesis protocol is 1/3-aBFT, we assume less
than 1/3 of total validating power are from malicious nodes, so there must be
at least one honest member in the overlap set. Let $n_{m}$ be such an honest
member. Because $n_{m}$ is honest, $n_{m}$ can detect and it does not allow
the fork. This contradicts the assumption. Thus, the lemma is proved. ∎

######  Proposition 8.16 (Fork-free).

For any Clotho $c$, the subgraph $G[c]$ is fork-free.

######  Lemma 8.17 (Fork free lemma).

If there is a fork $v_{x}\pitchfork v_{y}$, this fork will be detected by a
Clotho.

###### Proof.

Suppose that a node creates two event blocks ($v_{x},v_{y}$), which forms a
fork. Let’s assume there exist two Clotho $c_{x}$ and $c_{y}$ that can reach
both events. From Algorithm 1, each Clotho must reach more than $2W/3$. Thus,
there must more than $W/3$ of honest nodes would know both $c_{x}$ and
$c_{y}$. Lachesis protocol assumes that less than $W/3$ are from malicious
nodes. Therefore, there must exist at least a node that knows both Clothos
$c_{x}$ and $c_{y}$. Then that node must know both $v_{x}$ and $v_{y}$. So the
node will detect the fork. This is a contradiction. The lemma is proved. ∎

######  Theorem 8.18 (Fork Absence).

All honest nodes build the same global DAG $G^{C}$, which contains no fork.

###### Proof.

Suppose that there are two event blocks $v_{x}$ and $v_{y}$ contained in both
$G_{1}$ and $G_{2}$, and their path between $v_{x}$ and $v_{y}$ in $G_{1}$ is
not equal to that in $G_{2}$. We can consider that the path difference between
the nodes is a kind of fork attack. Based on Lemma 8.17, if an attacker forks
an event block, each chain of $G_{i}$ and $G_{2}$ can detect and remove the
fork before the Clotho is generated. Thus, any two nodes have consistent OPERA
DAG. ∎

###  8.3 Semantics of Lachesis

This section gives the formal semantics of Lachesis consensus protocol. We use
CCK model [34] of an asynchronous system as the base of the semantics of our
Lachesis protocol. We present notations and concepts, which are important for
Lachesis protocol. We adapt the notations and concepts of CCK paper to suit
our Lachesis protocol. Events are ordered based on Lamport’s happened-before
relation. In particular, we use Lamport’s theory to describe global states of
an asynchronous system.

####  8.3.1 Node State

A node is a machine participating in the Lachesis protocol. Each node has a
local state consisting of local histories, messages, event blocks, and peer
information.

_[State]_ A (local) state of node $i$ is denoted by $s_{j}^{i}$ consisting of
a sequence of event blocks $s_{j}^{i}$=$v_{0}^{i}$, $v_{1}^{i}$, $\dots$,
$v_{j}^{i}$.

In a DAG-based protocol, each event block $v_{j}^{i}$ is _valid_ only if the
reference blocks exist before it. A local state $s_{j}^{i}$ is corresponding
to a unique DAG. In StakeDag, we simply denote the $j$-th local state of a
node $i$ by the DAG $g_{j}^{i}$. Let $G_{i}$ denote the current local DAG of a
process $i$.

_[Action]_ An action is a function from one local state to another local
state.

An action can be either: a $send(m)$ action of a message $m$, a $receive(m)$
action, and an internal action. A message $m$ is a triple $\langle
i,j,B\rangle$ where the sender $i$, the message recipient $j$, and the message
body $B$. In StakeDag, $B$ consists of the content of an event block $v$. Let
$M$ denote the set of messages. Semantics-wise, there are two actions that can
change a process’s local state: creating a new event and receiving an event
from another process.

_[Event]_ An event is a tuple $\langle s,\alpha,s^{\prime}\rangle$ consisting
of a state, an action, and a state.

Sometimes, the event can be represented by the end state $s^{\prime}$. The
$j$-th event in history $h_{i}$ of process $i$ is $\langle
s_{j-1}^{i},\alpha,s_{j}^{i}\rangle$, denoted by $v_{j}^{i}$.

_[Local history]_ A local history $h_{i}$ of $i$ is a sequence of local states
starting with an initial state. A set $H_{i}$ of possible local histories for
each process $i$.

A process’s state can be obtained from its initial state and the sequence of
actions or events that have occurred up to the current state. Lachesis
protocol uses append-only semantics. The local history may be equivalently
described as either of the followings:

$h_{i}=s_{0}^{i},\alpha_{1}^{i},\alpha_{2}^{i},\alpha_{3}^{i}\dots$
$h_{i}=s_{0}^{i},v_{1}^{i},v_{2}^{i},v_{3}^{i}\dots$
$h_{i}=s_{0}^{i},s_{1}^{i},s_{2}^{i},s_{3}^{i},\dots$

In Lachesis,, a local history is equivalently expressed as:

$h_{i}=g_{0}^{i},g_{1}^{i},g_{2}^{i},g_{3}^{i},\dots$

where $g_{j}^{i}$ is the $j$-th local DAG (local state) of the process $i$.

_[Run]_ Each asynchronous run is a vector of local histories. Denoted by
$\sigma$ = $\langle h_{1},h_{2},h_{3},...h_{N}\rangle$.

Let $\Sigma$ denote the set of asynchronous runs. A global state of run
$\sigma$ is an $n$-vector of prefixes of local histories of $\sigma$, one
prefix per process. The happened-before relation can be used to define a
consistent global state, often termed a consistent cut, as follows.

####  8.3.2 Consistent Cut

An asynchronous system consists of the following sets: a set $P$ of process
identifiers; a set $C$ of channels; a set $H_{i}$ is the set of possible local
histories for each process $i$; a set $A$ of asynchronous runs; a set $M$ of
all messages. If node $i$ selects node $j$ as a peer, then $(i,j)\in C$. In
general, one can express the history of each node in DAG-based protocol in
general or in Lachesis protocol in particular, in the same manner as in the
CCK paper [34].

We can now use Lamport’s theory to talk about global states of an asynchronous
system. A global state of run $\sigma$ is an $n$-vector of prefixes of local
histories of $\sigma$, one prefix per process. The happened-before relation
can be used to define a consistent global state, often termed a consistent
cut, as follows.

_[Consistent cut]_ A consistent cut of a run $\sigma$ is any global state such
that if $v_{x}^{i}\rightarrow v_{y}^{j}$ and $v_{y}^{j}$ is in the global
state, then $v_{x}^{i}$ is also in the global state. Denoted by
$\mathbf{c}(\sigma)$.

By Theorem 8.4, all nodes have consistent local OPERA DAGs. The concept of
consistent cut formalizes such a global state of a run. Consistent cuts
represent the concept of scalar time in distributed computation, it is
possible to distinguish between a “before” and an “after”. In Lachesis, a
consistent cut consists of all consistent OPERA DAGs. A received event block
exists in the global state implies the existence of the original event block.
Note that a consistent cut is simply a vector of local states; we will use the
notation $\mathbf{c}(\sigma)[i]$ to indicate the local state of $i$ in cut
$\mathbf{c}$ of run $\sigma$.

The formal semantics of an asynchronous system is given via the satisfaction
relation $\vdash$. Intuitively $\mathbf{c}(\sigma)\vdash\phi$,
“$\mathbf{c}(\sigma)$ satisfies $\phi$,” if fact $\phi$ is true in cut
$\mathbf{c}$ of run $\sigma$. We assume that we are given a function $\pi$
that assigns a truth value to each primitive proposition $p$. The truth of a
primitive proposition $p$ in $\mathbf{c}(\sigma)$ is determined by $\pi$ and
$\mathbf{c}$. This defines $\mathbf{c}(\sigma)\vdash p$.

######  Definition 8.14 (Equivalent cuts).

Two cuts $\mathbf{c}(\sigma)$ and $\mathbf{c^{\prime}}(\sigma^{\prime})$ are
equivalent with respect to $i$ if:

$\mathbf{c}(\sigma)\sim_{i}\mathbf{c^{\prime}}(\sigma^{\prime})\Leftrightarrow\mathbf{c}(\sigma)[i]=\mathbf{c^{\prime}}(\sigma^{\prime})[i]$

A message chain of an asynchronous run is a sequence of messages $m_{1}$,
$m_{2}$, $m_{3}$, $\dots$, such that, for all $i$, $receive(m_{i})$
$\rightarrow$ $send(m_{i+1})$. Consequently, $send(m_{1})$ $\rightarrow$
$receive(m_{1})$ $\rightarrow$ $send(m_{2})$ $\rightarrow$ $receive(m_{2})$
$\rightarrow$ $send(m_{3})$ $\dots$.

We introduce two families of modal operators, denoted by $K_{i}$ and $P_{i}$,
respectively. Each family indexed by process identifiers. Given a fact $\phi$,
the modal operators are defined as follows:

_[ $i$ knows $\phi$]_ $K_{i}(\phi)$ represents the statement “$\phi$ is true
in all possible consistent global states that include $i$’s local state”.

$\mathbf{c}(\sigma)\vdash
K_{i}(\phi)\Leftrightarrow\forall\mathbf{c^{\prime}}(\sigma^{\prime})(\mathbf{c^{\prime}}(\sigma^{\prime})\sim_{i}\mathbf{c}(\sigma)\
\Rightarrow\ \mathbf{c^{\prime}}(\sigma^{\prime})\vdash\phi)$

_[ $i$ partially knows $\phi$]_ $P_{i}(\phi)$ represents the statement “there
is some consistent global state in this run that includes $i$’s local state,
in which $\phi$ is true.”

$\mathbf{c}(\sigma)\vdash
P_{i}(\phi)\Leftrightarrow\exists\mathbf{c^{\prime}}(\sigma)(\mathbf{c^{\prime}}(\sigma)\sim_{i}\mathbf{c}(\sigma)\
\wedge\ \mathbf{c^{\prime}}(\sigma)\vdash\phi)$

The last modal operator is concurrent common knowledge (CCK), denoted by
$C^{C}$.

######  Definition 8.15 (Concurrent common knowledge).

$C^{C}(\phi)$ is defined as a fixed point of $M^{C}(\phi\wedge X)$

CCK defines a state of process knowledge that implies that all processes are
in that same state of knowledge, with respect to $\phi$, along some cut of the
run. In other words, we want a state of knowledge $X$ satisfying:
$X=M^{C}(\phi\wedge X)$. $C^{C}$ will be defined semantically as the weakest
such fixed point, namely as the greatest fixed-point of $M^{C}(\phi\wedge X)$.
It therefore satisfies:

$C^{C}(\phi)\Leftrightarrow M^{C}(\phi\wedge C^{C}(\phi))$

Thus, $P_{i}(\phi)$ states that there is some cut in the same asynchronous run
$\sigma$ including $i$’s local state, such that $\phi$ is true in that cut.

Note that $\phi$ implies $P_{i}(\phi)$. But it is not the case, in general,
that $P_{i}(\phi)$ implies $\phi$ or even that $M^{C}(\phi)$ implies $\phi$.
The truth of $M^{C}(\phi)$ is determined with respect to some cut
$\mathbf{c}(\sigma)$. A process cannot distinguish which cut, of the perhaps
many cuts that are in the run and consistent with its local state, satisfies
$\phi$; it can only know the existence of such a cut.

_[Global fact]_ Fact $\phi$ is valid in system $\Sigma$, denoted by
$\Sigma\vdash\phi$, if $\phi$ is true in all cuts of all runs of $\Sigma$.

$\Sigma\vdash\phi\Leftrightarrow(\forall\sigma\in\Sigma)(\forall\mathbf{c})(\mathbf{c}(a)\vdash\phi)$

_[Valid Fact]_ Fact $\phi$ is valid, denoted $\vdash\phi$, if $\phi$ is valid
in all systems, i.e. $(\forall\Sigma)(\Sigma\vdash\phi)$.

_[Local fact]_ A fact $\phi$ is local to process $i$ in system $\Sigma$ if
$\Sigma\vdash(\phi\Rightarrow K_{i}\phi)$.

####  8.3.3 State in aBFT Lachesis

We introduce a new modal operator, written as $M^{C}$, which stands for
“majority concurrently knows”. The definition of $M^{C}(\phi)$ is as follows.

######  Definition 8.16 (Majority concurrently knows).

$M^{C}(\phi)=_{def}\bigwedge_{i\in S}K_{i}P_{i}(\phi),$

where $S\subseteq P$ and $|S|>2n/3$.

This is adapted from the “everyone concurrently knows” in CCK paper [34]. In
the presence of one-third of faulty nodes, the original operator “everyone
concurrently knows” is sometimes not feasible. Our modal operator
$M^{C}(\phi)$ fits precisely the semantics for BFT systems, in which
unreliable processes may exist.

A weighted version of “majority concurrently knows” is “Quorum concurrently
knows”, which is defined as follows:

######  Definition 8.17 (Quorum concurrently knows).

$Q^{C}(\phi)=_{def}\bigwedge_{i\in S}K_{i}P_{i}(\phi),$

where $S\subseteq P$ and $w(S)>2W/3$.

The total weight of a set is equal to the sum of the weights of each node in
the set; that is, $w(S)=\sum_{1}^{|S|}{w(n_{i})}$.

######  Theorem 8.19.

If $\phi$ is local to process $i$ in system $\Sigma$, then
$\Sigma\vdash(P_{i}(\phi)\Rightarrow\phi)$.

######  Lemma 8.20.

If fact $\phi$ is local to 2/3 of the processes in a system $\Sigma$, then
$\Sigma\vdash(M^{C}(\phi)\Rightarrow\phi)$ and furthermore
$\Sigma\vdash(C^{C}(\phi)\Rightarrow\phi)$.

######  Definition 8.18.

A fact $\phi$ is attained in run $\sigma$ if
$\exists\mathbf{c}(\sigma)(\mathbf{c}(\sigma)\vdash\phi)$.

Often, we refer to “knowing” a fact $\phi$ in a state rather than in a
consistent cut, since knowledge is dependent only on the local state of a
process. Formally, $i$ knows $\phi$ in state $s$ is shorthand for

$\forall\mathbf{c}(\sigma)(\mathbf{c}(\sigma)[i]=s\Rightarrow\mathbf{c}(\sigma)\vdash\phi)$

For example, if a process in Lachesis protocol knows a fork exists (i.e.,
$\phi$ is the exsistenc of fork) in its local state $s$ (i.e., $g_{j}^{i}$),
then a consistent cut contains the state $s$ will know the existence of that
fork.

######  Definition 8.19 ($i$ learns $\phi$).

Process $i$ learns $\phi$ in state $s_{j}^{i}$ of run $\sigma$ if $i$ knows
$\phi$ in $s_{j}^{i}$ and, for all previous states $s_{k}^{i}$ in run
$\sigma$, $k<j$, $i$ does not know $\phi$.

The following theorem says that if $C_{C}(\phi$ is attained in a run then all
processes $i$ learn $P_{i}C^{C}(\phi)$ along a single consistent cut.

######  Theorem 8.21 (attainment).

If $C^{C}(\phi)$ is attained in a run $\sigma$, then the set of states in
which all processes learn $P_{i}C^{C}(\phi)$ forms a consistent cut in
$\sigma$.

We have presented a formal semantics of Lachesis protocol based on the
concepts and notations of concurrent common knowledge [34]. For a proof of the
above theorems and lemmas in this Section, we can use similar proofs as
described in the original CCK paper.

With the formal semantics of Lachesis, the theorems and lemmas described in
Section 8.2 can be expressed in term of CCK. For example, one can study a fact
$\phi$ (or some primitive proposition $p$) in the following forms: ‘is there
any existence of fork?’. One can make Lachesis-specific questions like ’is
event block $v$ a root?’, ’is $v$ a clotho?’, or ’is $v$ a atropos?’. This is
a remarkable result, since we are the first that define such a formal
semantics for DAG-based protocol.

##  9 Alternatives for scalability

###  9.1 Layering-based Model

In this section, we present an approach that uses graph layering on top of our
PoS DAG-based Lachesis protocol. Our general model is given in StakeDag
protocol [33], which is based on layering-based approach of ONLAY framework
[31]. After using layering algorithms on the OPERA DAG, the assigned layers
are then used to determine consensus of the event blocks.

####  9.1.1 Layering Definitions

For a directed acyclic graph $G$=($V$,$E$), a layering is to assign a layer
number to each vertex in $G$.

_[Layering]_ A layering (or levelling) of $G$ is a topological numbering
$\phi$ of $G$, $\phi:V\rightarrow Z$, mapping the set of vertices $V$ of $G$
to integers such that $\phi(v)$ $\geq$ $\phi(u)$ \+ 1 for every directed edge
($u$, $v$) $\in E$. If $\phi(v)$=$j$, then $v$ is a layer-$j$ vertex and
$V_{j}=\phi^{-1}(j)$ is the jth layer of $G$.

From happened before relation, $v_{i}\rightarrow v_{j}$ iff
$\phi(v_{i})<\phi(v_{j})$. Layering $\phi$ partitions the set of vertices $V$
into a finite number $l$ of _non-empty_ disjoint subsets (called layers)
$V_{1}$,$V_{2}$,$\dots$, $V_{l}$, such that $V$ = $\cup_{i=1}^{l}{V_{i}}$.
Each vertex is assigned to a layer $V_{j}$, where $1\leq j\leq l$, such that
every edge ($u$,$v$) $\in E$, $u\in V_{i}$, $v\in V_{j}$, $1\leq i<j\leq l$.

_[Hierarchical graph]_ For a layering $\phi$, the produced graph
$H$=($V$,$E$,$\phi$) is a _hierarchical graph_ , which is also called an
$l$-layered directed graph and could be represented as
$H$=($V_{1}$,$V_{2}$,$\dots$,$V_{l}$;$E$).

Approaches to DAG layering include minimizing the height [3, 39], fixed width
layering [12] and minimizing the total edge span. A simple layering algorithm
to achieve minimum height is as follows: First, all source vertices are placed
in the first layer $V_{1}$. Then, the layer $\phi(v)$ for every remaining
vertex $v$ is recursively defined by $\phi(v)$ = $max\\{\phi(u)|(u,v)\in E\\}$
\+ 1. This algorithm produces a layering where many vertices will stay close
to the bottom, and hence the number of layers $k$ is kept minimized. By using
a topological ordering of the vertices [28], the algorithm can be implemented
in linear time $O$($|V|$+$|E|$).

####  9.1.2 H-OPERA DAG

We introduce a new notion of H-OPERA DAG, which is built on top of the OPERA
DAG by using graph layering.

######  Definition 9.1 (H-OPERA DAG).

An H-OPERA DAG is the result hierarchical graph $H=(V,E,\phi)$.

H-OPERA DAG can also be represented by
$H$=($V_{1}$,$V_{2}$,$\dots$,$V_{l}$;$E$). Vertices are assigned with layers
such that each edge ($u$,$v$) $\in E$ flows from a higher layer to a lower
layer i.e., $\phi(u)$ $>$ $\phi(v)$.

Generally speaking, a layering can produce a proper hierarchical graph by
introducing dummy vertices along every long edge. However, for consensus
protocol, such dummy vertices can increase the computational cost of the
H-OPERA itself and of the following steps to determine consensus. Thus, in
ONLAY we consider layering algorithms that do not introduce dummy vertices.

A simple approach to compute H-OPERA DAG is to consider OPERA DAG as a static
graph $G$ and then apply a layering algorithm such as either LongestPathLayer
(LPL) algorithm or Coffman-Graham (CG) algorithm on the graph $G$. LPL
algorithm can achieve HG in linear time $O$($|V|$+$|E|$) with the minimum
height. CG algorithm has a time complexity of $O$($|V|^{2}$), for a given $W$.

To handle large $G$ more efficiently, we introduce online layering algorithms.
We adopt the online layering algorithms introduced in [31]. Specifically, we
use _Online Longest Path Layering_ (O-LPL) and _Online Coffman-Graham_ (O-CG)
algorithm, which assign layers to the vertices in diff graph
$G^{\prime}$=($V^{\prime}$,$E^{\prime}$) consisting of new self events and
received unknown events. The algorithms are efficient and scalable to compute
the layering of large dynamic S-OPERA DAG. Event blocks from a new graph
update are sorted in topological order before being assigned layering
information.

####  9.1.3 Root Graph

There is a Root selection algorithm given in Section 3.8. Here, we present a
new approach that uses root graph and frame assignment.

######  Definition 9.2 (Root graph).

A root graph $G_{R}$=($V_{R}$, $E_{R}$) is a DAG consisting of vertices as
roots and edges represent their reachability.

In root graph $G_{R}$, the set of roots $V_{R}$ is a subset of $V$. Edge
($u$,$v$) $\in$ $E_{R}$ only if $u$ and $v$ are roots and $u$ can reach $v$
following edges in $E$ i.e., $v\rightarrow u$. Root graph contains the $n$
genesis vertices i.e., the $n$ leaf event blocks. A vertex $v$ that can reach
at least 2/3$W$ \+ 1 of the current set of all roots $V_{R}$ is itself a root.
For each root $r_{i}$ that new root $r$ reaches, we include a new edge ($r$,
$r_{i}$) into the set of root edges $E_{R}$. Note that, if a root $r$ reaches
two other roots $r_{1}$ and $r_{2}$ of the same node, and
$\phi(r_{1})>\phi(r_{2})$ then we include only one edge ($r$, $r_{1}$) in
$E_{R}$. This requirement ensures that each root of a node can have at most
one edge to any other node.

Algorithm 5 Root graph algorithm

1:Require: H-OPERA DAG

2:Output: root graph $G_{R}=(V_{R},E_{R})$

3:$R\leftarrow$ set of leaf events

4:$V_{R}\leftarrow R$

5:$E_{R}\leftarrow\emptyset$

6:function buildRootGraph($\phi$, $l$)

7: for each layer $i$=1..$l$ do

8: $Z\leftarrow\emptyset$

9: for each vertex $v$ in layer $\phi_{i}$ do

10: $S\leftarrow$ the set of vertices in $R$ that $v$ reaches

11: if $w_{S}>2/3W$ then

12: for each vertex $v_{i}$ in $S$ do

13: $E_{R}\leftarrow E_{R}\cup\\{(v,v_{i})\\}$

14: $V_{R}\leftarrow V_{R}\cup\\{v\\}$

15: $Z\leftarrow Z\cup\\{v\\}$

16: for each vertex $v_{j}$ in $Z$ do

17: Let $v_{old}$ be a root in $R$ such that $cr(v_{j})=cr(v_{old})$

18: $R\leftarrow R\setminus\\{v_{old}\\}\cup\\{v_{j}\\}$

Figure 10a shows an example of the H-OPERA DAG, which is the resulting
hierarchical graph from a laying algorithm. Vertices of the same layer are
placed on a horizontal line. There are 14 layers which are labelled as L0, L1,
…, to L14. Roots are shown in red colors. Figure 10b gives an example of the
root graph constructed from the H-OPERA DAG.

(a) Hierarchical graph with frame assignment

(b) Root graph

(c) Root-layering of a root graph

Figure 10: An example of hierachical graph and root graph

####  9.1.4 Frame Assignment

We then present a determinstic approach to frame assignment, which assigns
each event block a unique frame number. First, we show how to assign frames to
root vertices via the so-called _root-layering_. Second, we then assign non-
root vertices to the determined frame numbers with respect to the topological
ordering of the vertices.

######  Definition 9.3 (Root-layering).

A root layering assigns each root with a unique layer (frame) number.

Here, we apply root layering on the root graph $G_{R}=(V_{R},E_{R})$. Then, we
use root layering information to assign frames to non-root vertices. A frame
assignment assigns every vertex $v$ in H-OPERA DAG $H$ a frame number
$\phi_{F}(v)$ such that

  * •

$\phi_{F}(u)\geq\phi_{F}(v)$ for every directed edge $(u,v)$ in $H$;

  * •

for each root $r$, $\phi_{F}(r)=\phi_{R}(r)$;

  * •

for every pair of $u$ and $v$: if $\phi(u)\geq\phi(v)$ then
$\phi_{F}(u)\geq\phi_{F}(v)$; if $\phi(u)=\phi(v)$ then
$\phi_{F}(u)=\phi_{F}(v)$.

Figure 10c depicts an example of root layering for the root graph in Figure
10b.

####  9.1.5 Consensus

For an OPERA DAG $G$, let $G[v]$ denote the subgraph of $G$ that contains
nodes and edges reachable from $v$.

_[Consistent chains]_ For two chains $G_{1}$ and $G_{2}$, they are consistent
if for any event $v$ contained in both chains, $G_{1}[v]=G_{2}[v]$. Denoted by
$G_{1}\sim G_{2}$.

_[Global OPERA DAG]_ A global consistent chain $G^{C}$ is a chain such that
$G^{C}\sim G_{i}$ for all $G_{i}$.

The layering of consistent OPERA DAGs is consistent itself.

_[Consistent layering]_ For any two consistent OPERA DAGs $G_{1}$ and $G_{2}$,
layering results $\phi^{G_{1}}$ and $\phi^{G_{2}}$ are consistent if
$\phi^{G_{1}}(v)=\phi^{G_{2}}(v)$, for any vertex $v$ common to both chains.
Denoted by $\phi^{G_{1}}\sim\phi^{G_{2}}$.

######  Theorem 9.1.

For two consistent OPERA DAGs $G_{1}$ and $G_{2}$, the resulting H-OPERA DAGs
using layering $\phi_{LPL}$ are consistent.

The theorem states that for any event $v$ contained in both OPERA DAGs,
$\phi_{LPL}^{G_{1}}(v)=\phi_{LPL}^{G_{2}}(v)$. Since $G_{1}\sim G_{2}$, we
have $G_{1}[v]=G_{2}[v]$. Thus, the height of $v$ is the same in both $G_{1}$
and $G_{2}$. Thus, the assigned layer using $\phi_{LPL}$ is the same for $v$
in both chains.

######  Proposition 9.2 (Consistent root graphs).

Two root graphs $G_{R}$ and $G^{\prime}_{R}$ from two consistent H-OPERA DAGs
are consistent.

We can have similar proofs for the consistency of roots, clothos, and atropos
as in Section 8.2.3 8.2.4, 8.2.5.

####  9.1.6 Main procedure

Algorithm 7 shows the main function serving as the entry point to launch
StakeDag protocol. The main function consists of two main loops, which are
they run asynchronously in parallel. The first loop attempts to request for
new nodes from other nodes, to create new event blocks and then communicate
about them with all other nodes. The second loop will accept any incoming sync
request from other nodes. The node will retrieve updates from other nodes and
will then send responses that consist of its known events.

Algorithm 6 StakeDag Main Function 1:function Main Function 2:  _loop_ :  3:
Let $\\{n_{i}\\}$ $\leftarrow$ $k$-PeerSelectionAlgo()  4: Sync request to
each node in $\\{n_{i}\\}$ 5: (SyncPeer) all known events to each node in
$\\{n_{i}\\}$ 6: Create new event block: newBlock($n$, $\\{n_{i}\\}$)  7:
(SyncOther) Broadcast out the message  8: Update DAG $G$ 9: Call
ComputeConsensus($G$)  10:  _loop_ :  11: Accepts sync request from a node
12: Sync all known events by StakeDag protocol  1:function
ComputeConsensus(DAG)  2: Apply layering to obtain H-OPERA DAG*  3: Update
flagtable  4: Compute validation score*  5: Root selection  6: Compute root
graph*  7: Compute global state  8: Clotho selection  9: Atropos selection
10: Order vertices and assign consensus time  11: Compute Main chain
---

###  9.2 STAIR Model

We present a model to allow low-staked accounts to join as a validating node,
as described in STAIR [32]. In this model, we distinguish nodes into users
(low-staked), validators (high-staked) and monitors (zero-staked). Users have
less than $U$ tokens, but can join the network as a validator node. We give a
summary to highlights the idea of STAIR’s model.

Event Block Creation: Unlike StakeDag, STAIR requires one of the other-ref
blocks is from a creator of an opposite type. That is, if $n_{i}$ is a User,
then one of the other-ref parents must be from a Validator block. If $n_{i}$
is a Validator, then one of the other-ref parents must be a User block.

x-DAG: Cross-type DAG: STAIR protocol maintains the DAG structure x-DAG, which
is based on the concept of S-OPERA DAG in our StakeDag protocol [33]. x-Dag
chain is a weighted directed acyclic graph $G$=($V$,$E$), where $V$ is the set
of event blocks, $E$ is the set of edges. Each vertex (or event block) is
associated with a _validation score_ , which is the total weights of the roots
reachable from it. When a block becomes a root, it is assigned a _weight_ ,
which is the same with the validating power $p_{i}$ of the creator node.

Figure 11: Examples of x-DAG with users and validators

Figure 11 gives an example of x-DAG, which is a weighted acyclic directed
graph stored as the local view of each node. There are five nodes in the
example, three of which are normal users with validating power of 1, and the
rest are validators. Each event block has $k$=2 references. User blocks are
colored Black and Validator blocks are in Red. Each Red block has one Red
parent (same creator) and one Black parent (created by a User). Each Black
block has one Black parent (same creator) and one Red parent (created by a
Validator). As depicted, the example x-DAG is a RedBlack k-ary (directed
acyclic) graph.

Stake-aware Peer Synchronization: In STAIR protocol, we present a approach for
stake-aware peer synchronization to improve the fairness, safety and liveness
of the protocol. STAIR protocol enforces User nodes (low stake) to connect
with Validators (high stake) in order to gain more validating power for User’s
new own blocks. Validators are also required to connect User nodes so as to
validate the User’s new blocks. Algorithm 7 shows the main function serving as
the entry point to launch STAIR protocol.

Algorithm 7 STAIR Main Function

1:$\mathcal{U}$ $\leftarrow$ set of users ($t_{i}<U$).

2:$\mathcal{V}$ $\leftarrow$ set of validators ($t_{i}\geq U$).

3:function Main Function($n_{m}$)

4:  _loop_ :

5: Let $\\{n_{i}\\}$ $\leftarrow$ $k$-PeerSelectionAlgo($n_{m}$,
$\mathcal{U}$, $\mathcal{V}$)

6: Sync request to each node in $\\{n_{i}\\}$

7: (SyncPeer) all known events to each node in $\\{n_{i}\\}$

8: Create new event block: newBlock($n_{m}$, $\\{n_{i}\\}$)

9: (SyncAll) Broadcast out the message

10: Update x-DAG $G$

11: Call ComputeConsensus($G$)

12:  _loop_ :

13: Accepts sync request from a node

14: Sync all known events by STAIR protocol

Saga points: To measure the performance of participants, we propose a new
notion, called Saga points (Sp). The Saga points or simply ’points’ of a node
$n_{i}$, is denoted by $\alpha_{i}$. As an example, Sp point is defined as the
number of own events created by $n_{i}$ that has a parent (other-ref) as a
finalized event (Atropos).

In STAIR, we propose to use Saga points to scale the final value of validating
power, say $w^{\prime}_{i}=\alpha_{i}.w_{i}$. Saga point is perfectly a good
evidence for the validation achievement made by a node. Saga point is hard to
get and nodes have to make a long time commitment to accumulate the points.

##  10 Reference

##

  * [1] J. Aspnes.  Randomized protocols for asynchronous consensus.  Distributed Computing, 16(2-3):165–175, 2003.
  * [2] L. Baird.  Hashgraph consensus: fair, fast, byzantine fault tolerance.  Technical report, 2016.
  * [3] J. Bang-Jensen and G. Z. Gutin.  Digraphs: theory, algorithms and applications.  Springer Science & Business Media, 2008.
  * [4] I. Bentov, A. Gabizon, and A. Mizrahi.  Cryptocurrencies without proof of work.  In International Conference on Financial Cryptography and Data Security, pages 142–157. Springer, 2016.
  * [5] BitShares.  Delegated proof-of-stake consensus.
  * [6] V. Buterin et al.  Ethereum white paper.  GitHub repository, 1:22–23, 2013.
  * [7] M. Castro and B. Liskov.  Practical byzantine fault tolerance.  In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI ’99, pages 173–186, Berkeley, CA, USA, 1999\. USENIX Association.
  * [8] J. Chen and S. Micali.  ALGORAND: the efficient and democratic ledger.  CoRR, abs/1607.01341, 2016.
  * [9] S.-M. Choi, J. Park, Q. Nguyen, and A. Cronje.  Fantom: A scalable framework for asynchronous distributed systems.  arXiv preprint arXiv:1810.10360, 2018.
  * [10] S.-M. Choi, J. Park, Q. Nguyen, K. Jang, H. Cheob, Y.-S. Han, and B.-I. Ahn.  Opera: Reasoning about continuous common knowledge in asynchronous distributed systems, 2018.
  * [11] A. Churyumov.  Byteball: A decentralized system for storage and transfer of value, 2016\.
  * [12] E. G. Coffman, Jr. and R. L. Graham.  Optimal scheduling for two-processor systems.  Acta Inf., 1(3):200–213, Sept. 1972.
  * [13] T. A. Crew.  Ark whitepaper.
  * [14] G. Danezis and D. Hrycyszyn.  Blockmania: from block dags to consensus, 2018.
  * [15] EOS.  EOS.IO technical white paper.
  * [16] Ethcore.  Parity: Next generation ethereum browser.
  * [17] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich.  Algorand: Scaling byzantine agreements for cryptocurrencies.  In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51–68. ACM, 2017.
  * [18] S. King and S. Nadal.  Ppcoin: Peer-to-peer crypto-currency with proof-of-stake.  19, 2012.
  * [19] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong.  Zyzzyva: speculative byzantine fault tolerance.  ACM SIGOPS Operating Systems Review, 41(6):45–58, 2007.
  * [20] J. Kwon.  Tendermint: Consensus without mining.  https://tendermint.com/static/docs/tendermint.pdf, 2014.
  * [21] L. Lamport.  Time, clocks, and the ordering of events in a distributed system.  Communications of the ACM, 21(7):558–565, 1978.
  * [22] L. Lamport et al.  Paxos made simple.  ACM Sigact News, 32(4):18–25, 2001.
  * [23] L. Lamport, R. Shostak, and M. Pease.  The byzantine generals problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982.
  * [24] D. Larimer.  Delegated proof-of-stake (dpos), 2014.
  * [25] C. LeMahieu.  Raiblocks: A feeless distributed cryptocurrency network, 2017.
  * [26] S. D. Lerner.  Dagcoin, 2015.
  * [27] C. Li, P. Li, W. Xu, F. Long, and A. C.-c. Yao.  Scaling nakamoto consensus to thousands of transactions per second.  arXiv preprint arXiv:1805.03870, 2018.
  * [28] K. Mehlhorn.  Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness, volume 2 of EATCS Monographs on Theoretical Computer Science.  Springer, 1984.
  * [29] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song.  The honey badger of bft protocols.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31–42. ACM, 2016.
  * [30] S. Nakamoto.  Bitcoin: A peer-to-peer electronic cash system, 2008.
  * [31] Q. Nguyen and A. Cronje.  ONLAY: Online Layering for scalable asynchronous BFT system.  arXiv preprint arXiv:1905.04867, 2019.
  * [32] Q. Nguyen, A. Cronje, M. Kong, A. Kampa, and G. Samman.  Stairdag: Cross-dag validation for scalable BFT consensus.  CoRR, abs/1908.11810, 2019.
  * [33] Q. Nguyen, A. Cronje, M. Kong, A. Kampa, and G. Samman.  StakeDag: Stake-based Consensus For Scalable Trustless Systems.  CoRR, abs/1907.03655, 2019.
  * [34] P. Panangaden and K. Taylor.  Concurrent common knowledge: defining agreement for asynchronous systems.  Distributed Computing, 6(2):73–93, 1992.
  * [35] A. Panarello, N. Tapas, G. Merlino, F. Longo, and A. Puliafito.  Blockchain and iot integration: A systematic survey.  Sensors, 18(8):2575, 2018.
  * [36] R. Pass and E. Shi.  Fruitchains: A fair blockchain.  In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 315–324. ACM, 2017.
  * [37] F. H. Q. M. S. S. Pierre Chevalier, Bartomiej Kamin ski.  Protocol for asynchronous, reliable, secure and efficient consensus (parsec), 2018.
  * [38] S. Popov.  The tangle, 2017.
  * [39] R. Sedgewick and K. Wayne.  Algorithms.  Addison-Wesley Professional, 4th edition, 2011.
  * [40] H. H. S. Sheikh, R. M. R. Azmathullah, and F. R. R. HAQUE.  Proof-of-work vs proof-of-stake: A comparative analysis and an approach to blockchain consensus mechanism.  2018\.
  * [41] Y. Sompolinsky, Y. Lewenberg, and A. Zohar.  Spectre: A fast and scalable cryptocurrency protocol.  IACR Cryptology ePrint Archive, 2016:1159, 2016.
  * [42] Y. Sompolinsky and A. Zohar.  Phantom, ghostdag: Two scalable blockdag protocols, 2008.
  * [43] Steem.  Steem white paper.
  * [44] S. N. Sunny King.  Ppcoin: Peer-to-peer crypto-currency with proof-of-stake, 2012.
  * [45] P. Vasin.  Blackcoin’s proof-of-stake protocol v2.  URL: https://blackcoin.co/blackcoin-pos-protocol-v2-whitepaper.pdf, 71, 2014.
  * [46] B. Vitalik and G. Virgil.  Casper the friendly finality gadget.  CoRR, abs/1710.09437, 2017.