# Bitcoin’s Latency–Security Analysis Made Simple

Dongning Guo
Northwestern University
<EMAIL_ADDRESS>Ling Ren
University of Illinois at Urbana-Champaign
<EMAIL_ADDRESS>
###### Abstract

Simple closed-form upper and lower bounds are developed for the security of
the Nakamoto consensus as a function of the confirmation depth, the honest and
adversarial block mining rates, and an upper bound on the block propagation
delay. The bounds are exponential in the confirmation depth and apply
regardless of the adversary’s attack strategy. The gap between the upper and
lower bounds is small for Bitcoin’s parameters. For example, assuming an
average block interval of ten minutes, a network delay bound of ten seconds,
and 10% adversarial mining power, the widely used 6-block confirmation rule
yields a safety violation between 0.11% and 0.35% probability.

##  1 Introduction

The famed Bitcoin white paper presented a novel Byzantine fault tolerant
consensus algorithm that is now known as the Nakamoto consensus [9]. A notable
property of the Nakamoto consensus is that the deeper a transaction is in a
longest blockchain, the safer it is to commit the transaction. In fact, the
probability that a transaction’s safety is violated decreases essentially
exponentially with the number of “confirmations”. A latency-security analysis
of the Nakamoto consensus aims at deriving upper bounds on the safety
violation probability of a given confirmation rule, under all possible attacks
allowed in a formally described model.

While the Nakamoto consensus protocol is simple and elegant, rigorously
analyzing its latency and security turns out to be quite challenging. The
Bitcoin white paper did not provide a formal model or rigorous analysis;
instead, it only considered one specific attack. Garay et al. [3] provided the
first latency-security analysis for the Nakamoto consensus against all
possible attacks. Follow-up works extended their analysis from a lockstep
synchrony model to the more realistic non-lockstep synchrony model [10, 11, 6,
12]. The fundamental fault tolerance limit of the Nakamoto consensus has also
been obtained [2, 4].

Most existing latency-security analysis of the Nakamoto consensus focused on
asymptotic results. This means they showed that transactions in the Nakamoto
consensus _eventually_ become permanent (also called committed, decided,
finalized, or immutable in the literature), but do not provide concrete
results on when that happens. Several recent works give concrete analysis [7,
8, 5] but their methods are quite complex. In particular, [7, 8] resort to a
stochastic analysis of races between renewal processes and focus on
confirmation by time rather than the more practically relevant confirmation by
depth. Reference [5] involves an complicated analysis of forkable strings and
an iterative dynamic programming algorithm to numerically evaluate a Markov
chain, and the results are not in a closed form.

In this paper, we develop two sets of simple upper and lower bounds on the
security of the Nakamoto consensus as a function of the confirmation depth,
the mining rates, and a block propagation delay upper bound. One set of upper
and lower bounds are essentially exponential functions in the confirmation
depth. A second set of closed-form bounds are numerically closer and still
easy to compute using finite sums of geometric and binomial distribution
functions.

The gap between the upper and lower bounds is small for the Bitcoin
parameters. For example, assuming on average one block is mined every ten
minutes, the delay bound is ten seconds, and 10% of the mining power is
adversarial, the probability of safety violation of the 6-block rule of thumb
is bounded between 0.11% and 0.35%. If the adversarial mining power increases
to 25%, one needs a 20-block rule to achieve similar bounds. For the Bitcoin
parameters and relatively small confirmation depths, our new upper bound is
tighter than the best existing result in [5].

In this paper, we introduce a new reduction technique to analyze Nakamoto
consensus protocols. We describe a “rigged” model in which some selected
blocks mined by honest nodes are converted into adversarial blocks. Such
conversion can only make the adversary more powerful. We judiciously select
those blocks for conversion such that the sequence of honest/adversarial
attributes of all blocks remains memoryless in the rigged model. We show that
the well-understood private-mining attack is a best attack in the rigged
model. Finally, we obtain simple upper and lower bounds on the safety
violation probability for the original model by analyzing the success
probability of the private-mining attack in the rigged model.

The remainder of the paper is organized as follows. In Section 2, we present
the canonical model for the Nakamoto consensus. The main theorems are given in
Section 3. In Section 4, we show that the well-known private-mining attack is
optimal under a special condition. In Section 5, we construct a rigged model
which on one hand makes the adversary more powerful, and on the other hand
makes the private-mining attack optimal. Two sets of upper and lower bounds on
the probability of safety violation are then obtained in Sections 5 and 6.
Numerical results are given in Section 7.

##  2 The Canonical Model

We assume the readers are familiar with how the Nakamoto consensus protocol
works. We briefly describe the protocol below only to introduce notation. The
protocol builds a growing sequence of transaction-carrying blocks where every
block is chained to its predecessor block by a solution to a computational
puzzle (i.e., a proof of work). At any point in time, every honest node
attempts to “mine” a new block that extends a longest chain of blocks
(blockchain) to its knowledge; once a new longest blockchain is mined or
received, an honest node sends it to other nodes through a gossip network. We
will use chains and blockchains interchangeably in this paper. A node commits
a block when at least $k-1$ blocks are mined on top of it as part of a longest
blockchain known to that node, where $k$ is a natural number chosen by the
node. We call this the $k$-confirmation commit rule.

We now define the blockchain data structure. Let us number all the blocks in
the time order they are mined. The $j$-th block in this numbering is called
block $j$ for short. We denote a blockchain using a sequence of block numbers,
e.g., in blockchain $(b_{0},b_{1},b_{2},\ldots,b_{m})$, the $i$-th block in
the chain is block $b_{i}$. A blockchain always starts with the Genesis block
$b_{0}=0$ that is known to all nodes by time 0, when the protocol starts. Each
subsequent block $b_{i}$ must contain a proof of work that binds it to the
predecessor block $b_{i-1}$. The last block, $b_{m}$ in the above example,
uniquely identifies the entire blockchain, so we will also refer to the above
blockchain as blockchain $b_{m}$ or chain $b_{m}$. The position of a block in
the blockchain is called its _height_. We will use $h_{b}$ to denote the
height of block $b$. In the above example, block $b_{i}$ is on height $i$,
i.e., $h_{b_{i}}=i$ (the Genesis block is on height 0).

We adopt a natural continuous-time model and model proof-of-work mining as a
homogeneous Poisson point process. Let $\lambda$ be the total mining rate of
the network (honest and adversarial nodes combined). Let
$\rho\in(\frac{1}{2},1]$ be the fraction of honest mining rate and $1-\rho$ be
the fraction of adversarial mining rate. Note that the model allows some of
the nodes to have zero mining rate, hence capturing light nodes. In the
canonical model, a block is said to be honest (resp. adversarial) if it is
mined by an honest (resp. adversarial) node. One can think of honest block
arrivals and adversarial blocks as two independent Poisson processes with
rates $\rho\lambda$ and $(1-\rho)\lambda$, respectively. Due to the Poisson
merging and splitting properties, it is equivalent to think of all blocks
arrivals as a single Poisson process with rate $\lambda$ where each block is
honest with probability $\rho$ and adversarial with probability $1-\rho$.

We use $t_{j}$ to denote the time block $j$ is mined. Evidently, $0=t_{0}\leq
t_{1}\leq t_{2}\leq\dots$. If block $j$ is mined by an honest node, it must
extend a longest blockchain to that node’s knowledge immediately before
$t_{j}$. Ties are broken arbitrarily or by the adversary at will. The honest
node will also immediately publish the newly mined block $j$ through a gossip
network.

Without loss of generality, we assume a single adversary controls all
adversarial mining power. If the adversary mines block $j$, the block may
extend any blockchain mined by time $t_{j}$ and may be presented to each
individual honest node at any time from $t_{j}$ onward at will. The adversary
in practice cannot predict the arrival times of future blocks but our results
hold even against an omniscient adversary that sees the arrival times of all
future blocks.

We assume the standard (non-lockstep) synchrony model. We abstract away the
topology and operations of the gossip network by assuming a universal block
propagation delay upper bound, denoted as $\Delta\geq 0$. Applying it to the
Nakamoto consensus, if any honest node mines or receives a new longest
blockchain $b$ at time $t$, then all nodes receive blockchain $b$ by time
$t+\Delta$.

A block may contain an arbitrary number of transactions. A transaction may
appear in multiple chains but it can appear at most once in any given chain.
The adversary’s goal is to attack the safety of a target transaction [9], as
defined below.

######  Definition 1 (Safety violation of a target transaction).

A target transaction’s safety is violated if a block containing the target
transaction is committed and a different block (which may or may not contain
the target transaction) is also committed on the same height.

In this paper, we assume the target transaction appears in every node’s view
at time $\tau$. We also assume all honest nodes adopt the $k$-confirmation
commit rule with the same $k$. Our goal is to obtain tight bounds on the
probability that the adversary violates the safety of the target transaction.

Table 1 illustrates frequently used notations in this paper.

$k$ | confirmation depth
---|---
$\lambda$ | total mining rate
$\rho$ | fraction of honest mining rate
$\Delta$ | block propagation delay upper bound
$h_{b}$ | height of block $b$
$t_{b}$ | mining time of block $b$
$p=\rho e^{-\lambda\Delta}$ | fraction of honest blocks
|  in the rigged model
Table 1: Some frequently used notations.

##  3 Main Results

######  Theorem 1.

Given the confirmation depth $k$ as a natural number, the delay bound
$\Delta\geq 0$, the total mining rate $\lambda>0$, and the fraction of honest
mining power $\rho\in(0,1]$, as long as

$\displaystyle p=\rho e^{-\lambda\Delta}>\frac{1}{2},$ (1)

a target transaction’s safety can be violated with probability no greater than

$\displaystyle\left(2+2\sqrt{\frac{p}{1-p}}\right)(4p(1-p))^{{k}}$ (2)

regardless of the adversary’s attack strategy.

Conversely, there exists an attack that violates the target transaction’s
safety with probability at least

$\displaystyle\frac{1}{\sqrt{{k}}}\left(4\rho(1-\rho)\right)^{{k}}.$ (3)

Interestingly, both the upper bound (2) and the lower bound (3) can be
expressed in the exponential form using a simple equality:

$\displaystyle(4p(1-p))^{{k}}=e^{-2{k}d\left(\frac{1}{2}\,\|\,p\right)}$ (4)

where $d(p\,\|\,q)=p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}$ denotes the
relative entropy between the Bernoulli($p$) and the Bernoulli($q$)
distributions. As we shall see, the safety violation event is tied in some
ways to the event that $k$ or more out of $2k$ independent Bernoulli trials
are successful. For large $k$, the probability of this event decays
exponentially in $k$, where the exponent takes the form of a relative entropy,
as is expected from the perspective of large deviations. We emphasize that the
bounds in Theorem 1 apply to all adversarial mining strategies and all choices
of the confirmation depth.

We also provide another pair of upper and lower security bounds that are
tighter than the bounds in Theorem 1. The second set of bounds take somewhat
more complicated form as finite series sums, but are still very easy to
evaluate using the probability mass function (pmf) and cumulative distribution
function (cdf) of the binomial and geometric distributions. Specifically, we
use the following variant of the geometric distribution with parameter
$p=1-q>\frac{1}{2}$. For $i=1,2,\dots$, its pmf is expressed as

$\displaystyle
P_{1}(i;p)=\left(\frac{q}{p}\right)^{i-1}\left(1-\frac{q}{p}\right),$ (5)

and its complementary cdf is expressed as

$\displaystyle\overline{F}_{1}(i;p)=\left(\frac{q}{p}\right)^{i}.$ (6)

We also denote the pmf of the binomial distribution with parameters $(n,q)$ as

$\displaystyle P_{2}(j;n,q)=\binom{n}{j}q^{j}(1-q)^{n-j}$ (7)

and the corresponding complementary cdf as

$\displaystyle\overline{F}_{2}(j;n,q)=\sum_{l=j+1}^{n}P_{2}(l;n,q).$ (8)

######  Theorem 2.

Given the confirmation depth $k$ as a natural number, the delay bound
$\Delta\geq 0$, the total mining rate $\lambda>0$, and the fraction of honest
mining power $\rho\in(0,1]$, as long as $p=\rho
e^{-\lambda\Delta}>\frac{1}{2}$, a target transaction’s safety can be violated
with probability no greater than

$\displaystyle\begin{split}\overline{F}_{1}(k;p)+\sum_{i=1}^{k}P_{1}(i;p)\cdot\bigg{(}\overline{F}_{2}(k-i;2{k}+1-i,1-p)+\sum_{j=0}^{k-i}P_{2}(j;2{k}+1-i,1-p)\cdot\overline{F}_{1}(2k+1-2i-2j;p)\bigg{)}\end{split}$
(9)

regardless of the adversary’s attack strategy.

Conversely, there exists an attack that violates the target transaction’s
safety with probability at least

$\displaystyle\begin{split}\overline{F}_{1}(k;\rho)+\sum_{i=1}^{k}P_{1}(i;\rho)\cdot\bigg{(}\overline{F}_{2}(k-i;2{k}+1-i,1-\rho)+\sum_{j=0}^{k-i}P_{2}(j;2{k}+1-i,1-\rho)\cdot\overline{F}_{1}(2k+2-2i-2j;\rho)\bigg{)}.\end{split}$
(10)

The proofs of these bounds are relegated to Sections 4–6. The exponential
bounds in Theorem 1 can be thought of as the large deviations approximations
of those in Theorem 2. As we shall see in Section 7, the bounds in Theorem 2
are numerically closer than the bounds in Theorem 1.

##  4 The Private-Mining Attack Is Conditionally Optimal

Let us introduce the simple private-mining attack. Its general structure was
mentioned explicitly in [15] and even earlier works.

######  Definition 2 (Private-mining attack against a target transaction
$tx$).

Starting from time 0, every adversarial block extends a longest blockchain
that does not contain $tx$. The propagation of every honest block is maximally
delayed (i.e., by $\Delta$). All adversarial blocks are kept private until the
the adversary can violate the safety of $tx$ by publishing all blocks.

Throughout this section, we assume the following simple condition on block
heights is always upheld:

######  Condition 3.

All honest blocks are on different heights. Also, honest blocks mined after
time $\tau$ (when the target transaction appears) are higher than honest
blocks mined by time $\tau$.

Condition 3 always holds if the delay bound $\Delta=0$. With $\Delta>0$,
honest nodes may mine multiple blocks on the same height. But Condition 3 can
be upheld by keeping no more than one honest block on each height. This
changes the mining statistics and we relegate this discussion to Section 5,
where we use this technique along with a reduction argument to bound the
safety violation probability. In this section, we will prove that under
Condition 3, the private-mining attack is one best attack in the following
sense:

######  Theorem 3.

Under Condition 3, if any attack succeeds in violating the target
transaction’s safety, then the private-mining attack also succeeds in
violating the target transaction’s safety.

Theorem 3 holds for any given honest and adversarial block mining times; in
other words, as long as Condition 3 holds, the private-mining attack is a best
attack for every sample path, regardless of statistics. It was claimed in [2,
Appendix F] that the private-mining attack is optimal in violating the safety
of a predetermined target block in the special case of $\Delta=0$, but the
proof therein does not apply to the case when the target block is mined by an
adversary. Thus, the optimality of the private-mining attack has not been
fully established thus far even in the case of $\Delta=0$.

Before proving the theorem, we establish some additional terminology and
simple facts. The private-mining attack consists of two stages. In the first
stage, between time $0$ to $\tau$, the adversary tries to build a “lead”,
formally defined as follows:

######  Definition 4 (lead).

The lead (of the adversary) at time $t$ is the height of the highest block
mined by time $t$ minus the height of the highest honest block mined by $t$.

By definition, the lead is never negative. In the private-mining attack up to
time $\tau$, if a highest (private) adversarial block is higher than any
honest block (the lead is positive), the adversary mines on this highest
adversarial block to try to increase the lead; otherwise, the lead is zero,
and the adversary mines on a highest honest block to try to obtain a positive
lead. We can show that this strategy maximizes the lead.

######  Lemma 5.

Under condition 3, the private-mining attack maximizes the lead at all times
up to $\tau$.

###### Proof.

Let $l_{t}$ denote the lead at time $t$. The lead may only change upon block
arrivals. Upon the mining of every adversarial block, the lead advances by at
most 1. Upon the mining of every honest block, the lead decreases by at least
1 unless it stays 0. Under the private-mining attack up to $\tau$, the lead
advances by exactly 1 upon the mining of every adversarial block; the lead
decreases by exactly 1 unless it stays 0 upon the mining of every honest
block. Hence, the private-mining attack achieves the maximum lead at all times
up to $\tau$. ∎

The second stage of the private-mining attack starts at time $\tau$. Honest
nodes will include $tx$ in the next block on the honest chain. The adversary
tries to build a private chain that does not contain the target transaction
$tx$. If there ever comes a time after an honest node commits the target
transaction, that the adversary’s private chain is as long as the public
chain, then the adversary publishes its private chain and the attack succeeds
in violating the safety of $tx$. If such an instance never occurs, then the
private-mining attack on $tx$ fails.

For convenience, we define the following notions:

######  Definition 6 (public).

A blockchain is public at time $t$ if it is included in all honest nodes’
views at time $t$. We say block $b$ is public if and only if blockchain $b$ is
public.

######  Definition 7 (credible).

A blockchain is credible at time $t$ if it is no shorter than any public
blockchain at time $t$.

Equivalently, a credible blockchain at time $t$ must be no shorter than at
least one honest node’s longest blockchain at time $t$. Under the
$k$-confirmation rule, a credible blockchain can be used to convince at least
one honest node to commit blocks that are $k$ deep in this blockchain.
Furthermore, an honest node attempts to extend only credible blockchains. A
block mined by an honest node must be credible at its mining time; it then
loses its credibility at a later time, and cannot regain credibility
afterward.

We are now ready to prove Theorem 3.

###### Proof of Theorem 3.

Let us first consider the hypothetical attack that violates the safety of the
target transaction $tx$. Let block $c$ and $d$ be a pair of blocks that
minimize $h_{+}=\max(h_{c},h_{d})$ and satisfy the following conditions (see
Figure 1 for illustrations):

  1. 1.

Blockchain $c$ is credible at time $t_{c}$, contains the target transaction in
a block $b$, and has height $h_{c}\geq h_{b}+{k-1}$, and

  2. 2.

Blockchain $d$ is credible at time $t_{d}$, has height $h_{d}\geq
h_{b}+{k-1}$, does not contain block $b$, and does not contain the target
transaction on heights up to $h_{b}-1$.

Blocks $c$ and $d$ as defined must exist in order for some honest node to
commit the target transaction in a block and some honest node (possibly the
same one) to commit a different block on the same height. Since chains $c$ and
$d$ are credible at their respective mining times, and higher and higher
honest blocks are mined over time, such a pair is determined by the time a
block on some height greater than $h_{+}$ becomes public.

Since $h_{c}\geq h_{b}+{k-1}$ and $h_{d}\geq h_{b}+{k-1}$, we have

$h_{+}=\max(h_{c},h_{d})\geq h_{b}+{k-1}.$ (11)

We further define

$\displaystyle\tau_{+}=\max(t_{c},t_{d}).$ (12)

Figure 1: Illustrations of blockchains $c$ and $d$. Illustrations of the two
cases in the proof of Lemma 9: $h_{a}\geq h_{b}-1$ (left) and $h_{a}<h_{b}-1$
(right).

Under the hypothetical attack, let block $u$ be the highest honest block mined
by time $\tau$, let $l_{\tau}$ be the lead at time $\tau$, and let block $a$
be the highest block on chain $d$ at time $\tau$. Note that $l_{\tau}+h_{u}$
is the height of the highest block at time $\tau$ while $a$ is one block at
time $\tau$. Thus,

$l_{\tau}+h_{u}\geq h_{a}.$ (13)

Let $H_{t,s}$ be the number of honest blocks mined during $(t,s]$. Let
$A_{t,s}$ be the number of adversarial blocks mined during $(t,s]$.

######  Lemma 8.

$H_{\tau,\tau_{+}-\Delta}\leq h_{+}-h_{u}.$

###### Proof.

Since block $u$ is an honest block mined by time $\tau$, all honest blocks
mined after $\tau$ will have height at least $h_{u}+1$ (Condition 3). Since
one of $c$ or $d$ is credible at time $\tau_{+}$ and has height at most
$h_{+}$, all honest blocks mined before $\tau_{+}-\Delta$ must have height at
most $h_{+}$. Finally, since honest blocks do not share a height (Condition
3), the lemma is proved. ∎

######  Lemma 9.

Every height from $h_{a}+1$ to $h_{+}$ contains an adversarial block mined
during $(\tau,\tau_{+}]$.

###### Proof.

We first show every height from $h_{a}+1$ to $\min(h_{c},h_{d})$ contains an
adversarial block mined during $(\tau,\tau_{+}]$. First, all blocks in
blockchain $c$ on height $h_{b}$ and above are mined after during
$(\tau,\tau_{+}]$; so are all blocks in blockchain $d$ on height $h_{a}+1$ and
above. We consider two cases as illustrated in Figure 1. If $h_{a}\geq
h_{b}-1$, there exist two blocks on every height from $h_{a}+1$ to
$\min(h_{c},h_{d})$ that are mined during $(\tau,\tau_{+}]$. Given condition
3, one block on every height from $h_{a}+1$ to $\min(h_{c},h_{d})$ must be an
adversarial block mined during $(\tau,\tau_{+}]$. If $h_{a}<h_{b}-1$, by the
same argument, one block on every height from $h_{b}$ to $\min(h_{c},h_{d})$
must be an adversarial block mined during $(\tau,\tau_{+}]$. Furthermore,
blocks extending $a$ from height $h_{a}+1$ to $h_{b}-1$ do not contain the
target transaction $tx$ due to the definition of blockchain $d$. These must be
adversarial blocks because honest nodes would have included $tx$.

Next, we show every height from $\min(h_{c},h_{d})+1$ to $\max(h_{c},h_{d})$
also contains an adversarial block mined during $(\tau,\tau_{+}]$. If
$h_{c}=h_{d}$, the statement is vacuous. If $h_{d}>h_{c}$, we can show that
blocks on chain $d$ between height $h_{c}+1$ to $h_{d}$ are adversarial
blocks. Suppose for the sake of contradiction that one of these blocks, say
block $f$, is an honest block. Then block $f$’s parent, denoted as block $e$,
must be credible at time $t_{e}$, does not contain $tx$ up to height
$h_{b}-1$, and has height

$\displaystyle h_{e}=h_{f}-1\geq h_{c}\geq h_{b}+{k-1}.$ (14)

Thus, $\max(h_{c},h_{e})=h_{+}-1$. This contradicts with $h_{+}$ being
minimized by the pair of blocks $c$ and $d$. The case of $h_{c}>h_{d}$ is
similar.

Thus, we have that every height from $h_{a}+1$ to $h_{+}$ contains an
adversarial block mined during $(\tau,\tau_{+}]$. ∎

Figure 2: Illustrations of the two cases in the proof of Lemma 10: $h_{a}\geq
h_{u}$ (left) and $h_{a}<h_{u}$ (right). (While block $u$ is included in
blockchain $c$ in the graphs, block $u$ can be found in either chain $c$ or
chain $d$ or neither. In the $h_{a}<h_{b}$ case, though $h_{a}$ is illustrated
to be larger than $h_{b}$ in the graph, we can have $h_{a}\leq h_{b}$.)

######  Lemma 10.

$A_{\tau,\tau_{+}}\geq h_{+}-h_{a}+\max(h_{u}-h_{b}+1,0)$.

###### Proof.

In the case of $h_{u}-h_{b}+1\leq 0$, this lemma becomes
$A_{\tau,\tau_{+}}\geq h_{+}-h_{a}$, which follows directly from Lemma 9. It
remains to prove $A_{\tau,\tau_{+}}\geq(h_{+}-h_{a})+(h_{u}-h_{b}+1)$ in the
case of $h_{u}\geq h_{b}$. In this case, block $b$ and its successors in chain
$c$ up to height $h_{u}$ must be adversarial, because honest nodes will only
mine on heights higher than $h_{u}$ after time $\tau$. We consider two cases
as illustrated in Figure 2.

If $h_{a}\geq h_{u}$, then there is an adversarial block mined during
$(\tau,\tau_{+}]$ on every height from $h_{b}$ to $h_{u}\leq h_{a}$, and (due
to Lemma 9) on every height from $h_{a}+1$ to $h_{+}$, giving
$A_{\tau,\tau_{+}}\geq(h_{+}-h_{a})+(h_{u}-h_{b}+1)$.

If $h_{a}<h_{u}$, then the successors of block $a$ in chain $d$ up to height
$h_{u}$ must also be adversarial, because honest nodes will only mine on
heights higher than $h_{u}$ after time $\tau$. Also note block $b$ and its
successors are not in chain $d$. Thus, at least
$(h_{u}-h_{b}+1)+(h_{u}-h_{a})$ adversarial blocks mined during
$(\tau,\tau_{+}]$ on heights no greater than $h_{u}$. Furthermore, at least
one adversarial block is mined during $(\tau,\tau_{+}]$ on every height from
$h_{u}+1$ to $h_{+}$ (as a consequence of Lemma 9). Thus,
$A_{\tau,\tau_{+}}\geq(h_{u}-h_{b}+1)+(h_{u}-h_{a})+(h_{+}-h_{u})=(h_{+}-h_{a})+(h_{u}-h_{b}+1)$
as desired. ∎

The following corollary is straightforward from Lemma 10:

######  Corollary 11.

$A_{\tau,\tau_{+}}\geq h_{+}-h_{a}$ and $A_{\tau,\tau_{+}}\geq
h_{+}-h_{a}+h_{u}-h_{b}+1$.

Let us now consider the private-mining attack. Under this attack, let block
$u^{\prime}$ be the highest honest block at time $\tau$ and let
$l^{\prime}_{\tau}$ be the lead at time $\tau$. The first honest block after
$\tau$ will be on height $h_{u^{\prime}}+1$ and it will contain the target
transaction. At time $\tau_{+}$, the public honest chain has length
$h_{u^{\prime}}+H_{\tau,\tau_{+}-\Delta}$ and the adversary’s private chain
has length $h_{u^{\prime}}+l^{\prime}_{\tau}+A_{\tau,\tau_{+}}$. The private-
mining attack succeeds as long as the following two conditions hold:

  1. (i)

the adversary’s private chain is no shorter than the public honest chain,
i.e., $l^{\prime}_{\tau}+A_{\tau,\tau_{+}}\geq H_{\tau,\tau_{+}-\Delta}$;

  2. (ii)

the adversary’s private chain is at least $k-1$ higher than the target
transaction, i.e., $l^{\prime}_{\tau}+A_{\tau,\tau_{+}}\geq{k}$.

Both conditions follow directly from the results we just established. For (i),

$\displaystyle l^{\prime}_{\tau}+A_{\tau,\tau_{+}}-H_{\tau,\tau_{+}-\Delta}$
$\displaystyle\geq l_{\tau}+(h_{+}-h_{a})-(h_{+}-h_{u})$ (15)
$\displaystyle=l_{\tau}+h_{u}-h_{a}$ (16) $\displaystyle\geq 0$ (17)

where (15) is due to Lemma 5, Lemma 8 and Corollary 11, and (17) is due to
(13). For (ii),

$\displaystyle l^{\prime}_{\tau}+A_{\tau,\tau_{+}}$ $\displaystyle\geq
l_{\tau}+h_{+}-h_{a}+h_{u}-h_{b}+1$ (18) $\displaystyle\geq
l_{\tau}+k-h_{a}+h_{u}$ (19) $\displaystyle\geq{k}$ (20)

where (18) is due to Lemma 5 and Corollary 11, (19) is due to (11), and (20)
is due to (13). Hence the proof of Theorem 3. ∎

##  5 The Safety Violation Probability: Proof of Theorem 2

In this section, we differentiate the notion of blocks mined by honest (resp.
adversarial) nodes and honest (resp. adversarial) blocks. In particular, we
modify the canonical model of Section 2 to define a _rigged_ model: We convert
selected blocks mined by honest nodes into adversarial blocks, in addition to
blocks mined by adversarial nodes. Only the remaining blocks mined by honest
nodes are honest blocks. We let the adversary be informed of which blocks are
converted. The rigged model makes the adversary strictly more powerful because
the adversary has the option of behaving honestly with these converted blocks.

We judiciously select blocks for conversion so that all honest blocks are
always on different heights. Theorem 3 now guarantees that the private-mining
attack is a best attack in the rigged model. We then upper bound the safety
violation probability of the private-mining attack in the rigged model, which
will serve as an upper bound on any attack in the canonical model.

In order to specify blocks for conversion, we introduce the following notions:

######  Definition 12 (Tailgaters and laggers).

Let block $j$ be mined at time $t_{j}$. If no other block is mined during
$(t_{j}-\Delta,t_{j}]$, then block $j$ is a lagger; otherwise, block $j$ is a
tailgater.

Now each block has two attributes: whether it is mined by an honest or an
adversarial node, and whether it is a tailgater or a lagger. Each block is
mined by an honest node with probability $\rho$ and by an adversarial node
with probability $1-\rho$. Recall that the inter-arrival times in a Poisson
process are independent and identically distributed and follow an exponential
distribution with the same rate parameter. Thus, each block is a lagger with
probability $g=e^{-\lambda\Delta}$ and a tailgater with probability $1-g$.
Moreover, whether a block is a lagger or tailgater is independent of whether
it is mined by an honest or an adversarial node as well as all other blocks’
attributes.

We convert all the tailgaters mined by honest nodes into adversarial blocks.
In other words, only laggers mined by honest nodes are honest blocks; all
other blocks are adversarial blocks. It is not difficult to see that, in this
rigged model, every block is honest with probability $p=g\rho$ and is
adversarial with probability $q=1-p$, independent of all other blocks. Hence
the sequence of honest/adversarial attributes of all blocks form a memoryless
binary process. Like regular adversarial blocks, the adversary can decide what
predecessor block a converted block extends, and when it is revealed to honest
nodes. A crucial property is that now every honest block is received by all
honest nodes before the next honest block is mined. Therefore, every honest
block will be on a higher height than all previous honest blocks, i.e.,
Condition 3 is always upheld in the rigged model.

###  5.1 The Upper Bound

Let $F$ denote the event that the private-mining attack violates the target
transaction’s safety in the rigged model. Now that the conversions make the
private-mining attack a best attack (Theorem 3), it remains to upper bound
$\Pr(F)$.

Let $h$ denote the height of the highest honest block mined by time $\tau$.
The first honest block mined after $\tau$ (on height $h+1$) includes the
target transaction $tx$. Let $L$ denote the lead of the adversary at time
$\tau$, so the private chain’s height is $h+L$ at $\tau$.

If $L\geq k$, the private chain at time $\tau$ is already high enough to
commit the adversarial block on height $h+1$. As soon as the honest chain
grows by $k$ blocks after $\tau$ to commit $tx$, the adversary releases its
private chain to violate its safety.

If $L<k$, the private chain at $\tau$ is not high enough to commit on height
$h+1$. Let $B$ denote the number of adversarial blocks out of the first
$\max(2k-L,0)$ blocks mined after time $\tau$. Note that $B$ is non-negative
for all possible values of $L$. If $L<k$ but $L+B\geq k$, then by the time
$2k-L$ blocks are mined after $\tau$, the private chain’s height $h+L+B\geq
h+k$ is sufficient to commit $tx$ at height $h+1$, and it is also no shorter
than the honest chain, whose height is $h+(2k-L-B)\leq h+k$. Again, the
adversary has been able to violate $tx$’s safety.

If $L+B<k$, the private chain is still not high enough to commit on height
$h+1$ by the time $2k-L$ blocks are mined after $\tau$. At this point, the
public honest chain is also higher than the private chain by at least

$\displaystyle(h+(2k-L-B)-1)-(h+L+B)$ $\displaystyle=2(k-L-B)-1$ (21)

where the “$-1$” is because the highest honest block is not necessarily
public. A necessary condition for violating the safety of $tx$ is that the
adversary gains enough advantage to make up for this deficit at a later time.
(This is not a sufficient condition because the highest honest block may be
public to add one to the actual deficit.) Let $M$ denote the maximum advantage
the adversary ever gains during subsequent mining. Specifically, $M$ is the
maximum reach of the following simple random walk: The walk starts at $0$; it
increments by one upon the mining of an adversarial block (with probability
$q$); and it decrements by one upon the mining of an honest block (with
probability $p$). The necessary condition is then $M\geq 2(k-B-L)-1$.

In summary, the safety violation event $F$ occurs only if one of the following
three mutually exclusive events occurs:

  * •

$L\geq k$,

  * •

$L<k$ but $L+B\geq k$,

  * •

$L+B<k$ but $M\geq 2(k-L-B)-1$.

As $L$, $B$, $M$ are all non-negative, the union of the preceding three events
can be concisely written as

$\displaystyle 2L+2B+M\geq{2k-1}.$ (22)

In the remainder of this subsection, we analyze the probability of this event
using the joint distribution of $(L,B,M)$.

By definition, the lead $L$ is determined by block mining times before $\tau$,
$B$ is determined by the time $\max(2k-L,0)$ additional blocks are mined after
$\tau$, and $M$ is determined by mining times after that. Due to the
memoryless nature of the rigged mining process, $M$ is independent of $(L,B)$.
Under the condition (1), as the maximum reach of the random walk, the
distribution of $M$ is geometric [13, equation (7.3.5)]:

$\displaystyle\Pr(M=l)=P_{1}(l+1;p)$ (23)

and

$\displaystyle\Pr(M\geq l)=\overline{F}_{1}(l;p)$ (24)

for every $l=0,1,\dots$, where $P_{1}$ and $\overline{F}_{1}$ are defined in
(5) and (6).

The lead $L$ is exactly the state of a (continuous-time) birth-death process:
It starts at state 0; the mining of each adversarial block corresponds to a
birth; and the mining of each honest block corresponds to a death. The process
is bounded by zero from below. It is fair to assume that $\tau$ is not small
to allow sufficient mixing in the Markov process, so that the distribution of
$L$ is identical to the stationary distribution of this birth-death process
[13, p. 254] under the condition (1). Interestingly, $L$ has exactly the same
geometric distribution as $M$.

Conditioned on $L=l<2k$, $B$ is a binomial random variable with parameters
$(2{k}-l,q)$, hence

$\displaystyle\Pr(B=j\mid L=l)$ $\displaystyle=P_{2}(j;2{k}-l,q),$ (25)

and

$\displaystyle\Pr(B>j\mid L=l)$ $\displaystyle=\overline{F}_{2}(j;2{k}-l,q)$
(26)

for every $l=0,1,\dots$, where $P_{2}$ and $\overline{F}_{2}$ are defined in
(7) and (8).

Therefore, we have

$\displaystyle\Pr(F)$ $\displaystyle\leq\Pr(2L+2B+M\geq 2k-1)$ (27)
$\displaystyle=\Pr(L\geq k)+\sum_{l=0}^{k-1}\Pr(L=l)\cdot\Pr(2L+2B+M\geq
2k-1\mid L=l)$ (28) $\displaystyle=\Pr(L\geq
k)+\sum_{l=0}^{k-1}\Pr(L=l)\cdot\bigg{(}\Pr(B>k-l-1\mid L=l)$
$\displaystyle\qquad+\sum_{j=0}^{k-l-1}\Pr(B=j\mid L=l)\cdot\Pr(M\geq
2k-1-2l-2j)\bigg{)}$ (29)
$\displaystyle=\overline{F}_{1}(k;p)+\sum_{l=0}^{k-1}P_{1}(l+1;p)\cdot\bigg{(}\overline{F}_{2}(k-l-1;2{k}-l,1-p)$
$\displaystyle\quad+\sum_{j=0}^{k-l-1}P_{2}(j;2{k}-l,1-p)\cdot\overline{F}_{1}(2k-1-2l-2j;p)\bigg{)}$
(30)

which is equal to the upper bound (9) in Theorem 2 (with $l$ replaced by
$i-1$).

###  5.2 The Lower Bound

A lower bound can be obtained by calculating the success probability of the
private-mining attack under $\Delta=0$. Note that with a zero delay, Condition
3 holds without any conversion, so the fraction of honest mining power should
be the original $\rho$ instead of $p$. Another material difference is that all
honest blocks become public immediately. Let $L^{\prime}$, $B^{\prime}$, and
$M^{\prime}$ be identically defined as their counterparts $L$, $B$, and $M$
except that the probability $p$ is replaced with $\rho$. Under zero delay, the
event that the private-mining attack violates the safety of the target
transaction (which appears at time $\tau$) is exactly
$2L^{\prime}+2B^{\prime}+M^{\prime}\geq 2k$. We denote this event as $F_{0}$.
Assuming again $\tau$ is not small, we have the following exact formula for
the probability of safety violation of the target transaction as a function of
$k$ and $\rho$:

$\displaystyle\Pr(F_{0})$
$\displaystyle=\Pr(2L^{\prime}+2B^{\prime}+M^{\prime}\geq 2k)$ (31)
$\displaystyle=\overline{F}_{1}(k;\rho)+\sum_{l=0}^{k-1}P_{1}(l+1;\rho)\cdot\bigg{(}\overline{F}_{2}(k-l-1;2k-l,1-\rho)$
$\displaystyle\qquad+\sum_{j=0}^{k-l-1}P_{2}(j;2k-l,1-\rho)\cdot\overline{F}_{1}(2k-2l-2j;\rho)\bigg{)}$
(32)

which is equal to the lower bound (10) in Theorem 2.

##  6 The Safety Violation Probability: Proof of Theorem 1

To gain additional insights, we evaluate the probability of the safety
violation event using simple bounding techniques.

###  6.1 The Upper Bound

Recall $\Pr(F)\leq\Pr(2L+2B+M\geq 2k-1)$ from (27). The moment generating
function (MGF) of the geometric random variables $L$ and $M$ can be expressed
as

$\displaystyle{\mathsf{E}}\left\\{e^{\nu
L}\right\\}={\mathsf{E}}\left\\{e^{\nu M}\right\\}=\frac{p-q}{p-qe^{\nu}}$
(33)

which holds for every $\nu<\log(p/q)$. Conditioned on $L=l$, $B$ is a
binomial($2{k}-l,q$) random variable, whose MGF is expressed as

$\displaystyle{\mathsf{E}}\left\\{e^{\nu
B}|L=l\right\\}=\left(p+qe^{\nu}\right)^{2{k}-l}$ (34)

for every real number $\nu$.

Using the Chernoff bound [14], we have for every $\nu>0$:

$\displaystyle\Pr$ $\displaystyle(2L+2B+M\geq 2k-1)$
$\displaystyle=\Pr\left(L+B+\frac{M}{2}\geq{{k-\frac{1}{2}}}\right)$ (35)
$\displaystyle\leq{\mathsf{E}}\left\\{e^{\nu\left(L+B+\frac{M}{2}{{-k+\frac{1}{2}}}\right)}\right\\}$
(36) $\displaystyle={\mathsf{E}}\left\\{{\mathsf{E}}\left\\{e^{\nu(L+B)}\mid
L\right\\}\right\\}{\mathsf{E}}\left\\{e^{\nu\frac{M}{2}}\right\\}e^{-\nu\left({{k-\frac{1}{2}}}\right)}$
(37) $\displaystyle={\mathsf{E}}\left\\{e^{\nu
L}\left(p+qe^{\nu}\right)^{2{k}-L}\right\\}\frac{p-q}{p-qe^{\frac{\nu}{2}}}e^{-\nu\left({{k-\frac{1}{2}}}\right)}$
(38)
$\displaystyle=\left(p+qe^{\nu}\right)^{2{k}}\frac{p-q}{p-q\frac{e^{\nu}}{p+qe^{\nu}}}\frac{p-q}{p-qe^{\frac{\nu}{2}}}e^{-\nu\left({{k-\frac{1}{2}}}\right)}$
(39) $\displaystyle=\left(p+qe^{\nu}\right)^{2k}e^{-\nu
k}\frac{(p-q)^{2}(p+qe^{\nu})e^{\frac{\nu}{2}}}{(p^{2}-q^{2}e^{\nu})(p-qe^{\frac{\nu}{2}})}.$
(40)

The exponential coefficient for $k$ is equal to

$\displaystyle 2\log(p+qe^{\nu})-\nu.$ (41)

To yield an asymptotic bound, we note that the tightest exponent for $k$ is
obtained with

$\displaystyle e^{\nu}=p/q$ (42)

and thus $p+qe^{\nu}=2p$. (Note that (42) guarantees that the MGF (33) can be
invoked to arrive at (39).) Using (27) and plugging (42) back into (40), we
get the upper bound of

$\displaystyle\Pr(F)$ $\displaystyle\leq\Pr(2L+2B+M\geq{2k-1})$ (43)
$\displaystyle\leq 2\,(4pq)^{k}\left(\sqrt{\frac{p}{q}}+1\right)$ (44)

which is equal to (2).

###  6.2 The Lower Bound

According to the discussion in Section 5.2, the safety violation event $F_{0}$
under the private-mining attack in the case of $\Delta=0$ is expressed exactly
as $2L^{\prime}+2B^{\prime}+M^{\prime}\geq 2k$. Evidently,

$\displaystyle\Pr(F_{0})>\Pr(L^{\prime}+B^{\prime}\geq{k}).$ (45)

It is not difficult to see that the larger the pre-mining lead $L^{\prime}$,
the more likely that $L^{\prime}+B^{\prime}$ meets the threshold ${k}$, hence
for every $l=0,1,\dots,k$,

$\displaystyle\Pr(B^{\prime}\geq{k}-l\mid
L^{\prime}=l)\geq\Pr(B^{\prime}\geq{k}\mid L^{\prime}=0).$ (46)

Let $B_{0}$ denote a binomial random variable with parameter $(2{k},q)$.
Equations (45) and (46) imply that

$\displaystyle\Pr(F_{0})>\Pr(B_{0}\geq{k}).$ (47)

Using [1, Lemma 4.7.2], we can write

$\displaystyle\Pr(F_{0})>\frac{1}{\sqrt{{k}}}e^{-2{k}d\left(\frac{1}{2}\,\|\,\rho\right)}$
(48)

where the relative entropy can be evaluated as

$\displaystyle d\Big{(}\frac{1}{2}\,\Big{\|}\,\rho\Big{)}$
$\displaystyle=-\frac{1}{2}\log(4\rho(1-\rho)).$ (49)

Hence (48) becomes the lower bound (3) in Theorem 1.

##  7 Numerical Results

Figure 3: Safety violation probability bounds as a function of the
confirmation depth $k$. All bounds given in Theorems 1 and (2) are calculated
for Bitcoin’s nominal mining rate ($\lambda=1/600$ blocks per second), a block
propagation delay bound of $\Delta=10$ seconds, and adversarial mining ratios
of 10% ($\rho=0.9$), 25% ($\rho=0.75$), and 40% ($\rho=0.6$). Figure 4: Safety
violation probability bounds as a function of the confirmation depth $k$. The
bounds given in Theorem (2) are shown along with the bound of [5] for
Bitcoin’s nominal mining rate ($\lambda=1/600$ blocks per second), a block
propagation delay bound of $\Delta=10$ seconds, and adversarial mining ratios
of 10% and 20%.

Figure 3 shows the upper and lower bounds of Theorems 1 and 2 for the Bitcoin
mining rate of $\lambda=1/600$ (10 minutes per block), a block propagation
delay bound of $\Delta=10$ seconds, and adversarial mining ratios of 10%
($\rho=0.9$), 25% ($\rho=0.75$), and 40% ($\rho=0.6$). The upper and lower
bounds of Theorem 2 are quite close for a wide range of honest-to-adversarial
mining power ratios. In addition, the two lower bounds are very close and
their gap does not depend on the absolute mining rates and the delay bound. We
also note that the upper bound of Theorem 1 can be too loose for very small
depths.

Consider the practical rule of thumb of committing a Bitcoin block or
transaction by 6 confirmations ($k=6$). If the adversary controls 10% of the
total mining power, the probability of safety violation is between 0.11% and
0.35%. If the confirmation depth is increased to $k=14$, the probability is
then between $2\times 10^{-7}$ and $2\times 10^{-6}$. If the adversary
controls 25% of the total mining power, similar guarantees are obtained at
approximately $k=21$ and $k=50$, respectively.

Figure 5: Safety violation probability bounds as a function of the
confirmation depth $k$. The bounds given in Theorem 2 are shown along with the
bound of [5] for Ethereum’s nominal mining rate ($\lambda=1/13$ blocks per
second), a block propagation delay bound of $\Delta=2$ seconds, and
adversarial mining ratios of 10% and 20%.

All the bounds are either exponential or nearly exponential in the
confirmation depth. We also note that the asymptotic slopes of the bounds of
Theorem 2 match those of Theorem 1. The more mining power the adversary
controls, the flatter the curves are. For the aforementioned Bitcoin
parameters, the fundamental fault tolerance limit is $49.8\%$, i.e., there is
no safety regardless of the confirmation depth if $\rho<0.502$ [2, 4].

We also show in Figure 4 the prior best results from [5] for comparison. For
small confirmation depths, our bounds are tighter than theirs despite our much
simpler method. For example, with 10% adversary, $\Delta=10$ seconds delay,
and 6-confirmation, our result upper bounds the safety violation probability
at 0.35%, compare to 0.48% from [5]. As confirmation depths increase, their
results eventually become tighter than ours; the cross-over point for the
above parameter occurs at $k=9$. With a 20% adversary, the cross-over point
has not occurred within $k\leq 11$.

Figure 5 shows the upper and lower bounds for Ethereum’s mining rate of
$\lambda=1/13$, a block propagation delay bound of $\Delta=2$ seconds, and
adversarial mining ratios of 10% ($\rho=0.9$) and 20% ($\rho=0.8$). It is easy
to produce numerical results for higher adversarial ratios, but we omit them
to keep the figure easy to read. As expected, our bounds are much looser for
Ethereum parameters where the block interval is short relative to the block
propagation delay bound. The methods from [5] yield tighter bounds for such
settings.

Because the lower bounds of both Theorems 1 and 2 depend only on the ratio of
honest and adversarial mining powers, the gap between the two lower bounds
remains small regardless of the absolute mining rates and delays. This is
clearly seen in Figure 3 for the Bitcoin parameters. (This is also observed
for Ethereum’s parameters, which we omit here.)

#### Acknowledgement.

The authors thank Dr. David Tse for helpful discussion. This work was
supported in part by the National Science Foundation under award numbers
2143058 and 2132700.

## References

  * [1] Robert B Ash.  Information theory.  Dover Publishers, 2012.
  * [2] Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni.  Everything is a race and nakamoto always wins.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020.
  * [3] Juan Garay, Aggelos Kiayias, and Nikos Leonardos.  The bitcoin backbone protocol: Analysis and applications.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 281–310. Springer, 2015.
  * [4] Peter Gaži, Aggelos Kiayias, and Alexander Russell.  Tight consistency bounds for bitcoin.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 819–838, 2020.
  * [5] Peter Gaži, Ling Ren, and Alexander Russell.  Practical settlement bounds for proof-of-work blockchains.  Cryptology ePrint Archive, 2021.
  * [6] Lucianna Kiffer, Rajmohan Rajaraman, and Shelat Abhi.  A better method to analyze blockchain consistency.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 729–744. ACM, 2018.
  * [7] Jing Li and Dongning Guo.  Liveness and consistency of Bitcoin and Prism blockchains: The non-lockstep synchronous case.  In International Conference on Blockchain and Cryptocurrency. IEEE, 2020.
  * [8] Jing Li, Dongning Guo, and Ling Ren.  Close latency-security trade-off for the nakamoto consensus.  In Proceedings of the 3rd ACM Conference on Advances in Financial Technologies, pages 100–113, 2021.
  * [9] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  Available online: http://bitcoin.org/bitcoin.pdf, 2008.
  * [10] Rafael Pass, Lior Seeman, and Abhi Shelat.  Analysis of the blockchain protocol in asynchronous networks.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 643–673. Springer, 2017.
  * [11] Rafael Pass and Elaine Shi.  Rethinking large-scale consensus.  In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 115–129. IEEE, 2017.
  * [12] Ling Ren.  Analysis of nakamoto consensus.  Cryptology ePrint Archive, 2019.
  * [13] Sheldon M. Ross.  Stochastic processes.  John Wiley & Sons, Inc., 2 edition, 1996.
  * [14] Sheldon M Ross.  A first course in probability.  Prentice Hall Upper Saddle River, NJ, 8 edition, 2010.
  * [15] Yonatan Sompolinsky and Aviv Zohar.  Bitcoin’s security model revisited.  arXiv preprint arXiv:1605.09193, 2016.


tcb@breakable

#  $\mathsf{DiffPattern}$: Layout Pattern Generation via Discrete Diffusion

Zixiao Wang1∗ Yunheng Shen2∗, Wenqian Zhao1, Yang Bai1, Guojin Chen1, Farzan
Farnia1, Bei Yu1
1Chinese University of Hong Kong 2 Tsinghua University
{zxwang22, wqzhao, ybai, gjchen21, farnia<EMAIL_ADDRESS><EMAIL_ADDRESS>* Equal contribution

###### Abstract

Deep generative models dominate the existing literature in layout pattern
generation. However, leaving the guarantee of legality to an inexplicable
neural network could be problematic in several applications. In this paper, we
propose $\mathsf{DiffPattern}$ to generate reliable layout patterns.
$\mathsf{DiffPattern}$ introduces a novel diverse topology generation method
via a discrete diffusion model with compute-efficiently lossless layout
pattern representation. Then a white-box pattern assessment is utilized to
generate legal patterns given desired design rules. Our experiments on several
benchmark settings show that $\mathsf{DiffPattern}$ significantly outperforms
existing baselines and is capable of synthesizing reliable layout patterns.

##  I Introduction

Reliable Very-Large-Scale Integration (VLSI) layout pattern libraries are the
foundation of various designs for manufacturability (DFM) research, including
perfection of design rules, Optical Proximity Correction (OPC) recipes [1],
lithography simulation [2, 3], layout hotspot detection [4], and so on. With
the rapidly growing requirement for layout patterns in machine-learning-based
lithography design applications, building a practical large-scale pattern
library could be highly time-consuming due to the long logic-to-chip design
cycle.

Various rule-based and learning-based layout pattern generation methods have
been proposed to address this issue. Early rule-based methods [5, 6] first
augment a set of predefined basic units by simple enhancement technology,
e.g., flipping and rotation. Then they randomly select several units and
splice them together. However, patterns generated in this way lack diversity
and are limited in quantity. Recently, learning-based generative methods [7,
8, 9] have shown the ability to produce a large number of diverse layout
patterns. Among them, pixel-based methods [7, 8] regard the pattern generation
problem as a binary image generation task. A lossless pattern representation,
Squish Pattern, is proposed by [10] to reduce computational costs. Squish
Pattern splits a large layout pattern into a significantly smaller binary
topology matrix and two geometric vectors. Pixel-based methods synthesize a
topology matrix with continual values and threshold it to get a new binary
topology matrix, which wastes computation and hurts model capacity. Also, the
sequential-based method in [9] models a layout pattern as a sequence of
polygons, which is further decomposed into a sequence of vertices and directed
edges. To get a new layout pattern, [9] generates a polygon sequence and
translates it into a layout pattern. For both kinds of them, the generative
model learns a latent regularization from the training set to avoid producing
illegal layout patterns that violate the design rules. We argue that the
implicit constraint learned from the training set may be neither flexible nor
reliable. Apart from the inconvenience that we need to train a new model on a
specific large-scale dataset that follows the new design rules when the design
rule changes, a considerable ratio of generated patterns violate the design
rules in these methods.

In this paper, we propose $\mathsf{DiffPattern}$, a pixel-based practical
layout pattern generation framework that consists of three main components: a)
Inspired by the great success of diffusion models [11, 12], we approach the
generation of topology as a denoising task for a random noise image. We
utilize a discrete diffusion model to predict the noise that should be removed
at every step. During the training and sampling procedure, each entry of the
image tensor can be expressed by a discrete state in a finite state space,
$\\{0,1\\}$ for example, and there is no need to manually set a threshold on a
continual output range as previous work does. The naturally discrete output
provides a reasonable regularization that avoids meaningless overfitting on
how to produce a discrete-like output since all the pixels in the training
samples are discrete in their values and position. b) To further enlarge the
information density of patterns and reduce computation costs,
$\mathsf{DiffPattern}$ adapts the idea of Squish Pattern Representation and
pushes it one step forward. A kind of lossless layout pattern representation
method called Deep Squish Pattern is proposed. Deep Squish Pattern folds a
topology matrix into a topology tensor, which shrinks the input size and
extends the channel dimension. Due to the fact that the efficiency of the
existing diffusion model is more sensitive to the input size [13] and
significantly less to the number of input channels, Deep Squish Pattern
provides an easy-to-compute solution and can be efficiently applied to other
pixel-based pattern generation methods. c) With newly generated topology
matrices, we aim to assign geometric vectors to them and restore legal layout
patterns. We develop a nonlinear system that can figure out the legal solution
for each topology matrix and can be easily adjusted to every design rule.
Empowered by the interpretable pattern assessment strategy,
$\mathsf{DiffPattern}$ achieves a notable 100% legality rate on generated
layout patterns in our setting.

Our main contributions can be summarized as follows:

  1. 1.

We develop a novel layout pattern generation method based on discrete
denoising for synthesizing layout topology.

  2. 2.

We propose a lossless layout pattern representation strategy, Deep Squish
Pattern, which accelerates pixel-based layout pattern generation schemes.

  3. 3.

We utilize a nonlinear system for pattern assessment where the system provides
a white-box method to legalize the layout patterns.

  4. 4.

We extensively evaluate our methodology on benchmark datasets showing that
$\mathsf{DiffPattern}$ can achieve state-of-the-art (SOTA) performance.

##  II Preliminaries

Figure 1: Illustration of denoising diffusion process.

###  II-A Diffusion Models

Diffusion models refer to denoising diffusion probabilistic models [11], which
have demonstrated great potential in generating high-quality images. A
diffusion model defines a Markov chain to represent the sample forward and
reverse diffusion process, as shown in Fig. 1. In the forward diffusion
process, the diffusion model produces a sequence of noisy samples
$\bm{T}_{1},...,\bm{T}_{K}$ by iteratively adding Gaussian noise to the
original sample $\bm{T}_{0}$ in $K$ steps, where the noise level is controlled
by a variance schedule $\left\\{\beta_{k}\in(0,1)\right\\}_{k=1}^{K}$:

$\bm{q}\left(\bm{T}_{k}|\bm{T}_{k-1}\right):=\mathcal{N}\left(\bm{T}_{k};\sqrt{1-\beta_{k}}\bm{T}_{k-1},\beta_{k}\bm{I}\right).$
(1)

When $K$ is large, the noisy sample at the final iteration $\bm{T}_{K}$ will
have an almost Gaussian distribution, which inspires the diffusion model to
construct a reverse diffusion process to produce fresh data samples from
randomly drawn Gaussian noise. The goal of the reverse diffusion process is to
learn the distribution of inverting the explained forward diffusion process,
which will be used to generate fresh data samples from a Gaussian noise input.
However, a proper inversion of the distribution requires an expressive model,
and therefore we use a deep neural network with learnable parameters
$\bm{\theta}$ to learn the distribution,

$\bm{p}_{\bm{\theta}}\left(\bm{T}_{k-1}|\bm{T}_{k}\right):=\mathcal{N}\left(\bm{T}_{k-1};\bm{\mu}_{\bm{\theta}}\left(\bm{T}_{k},k\right),\bm{\Sigma}_{\bm{\theta}}\left(\bm{T}_{k},k\right)\right).$
(2)

Similar to variational autoencoders (VAEs), the training of diffusion models
aims to maximize the log-likelihood function by optimizing the variational
lower bound.

$L_{\mathrm{VLB}}=D_{\mathrm{KL}}\left(\bm{q}\left(\bm{T}_{K}|\bm{T}_{0}\right)\parallel\bm{p}_{\bm{\theta}}\left(\bm{T}_{K}\right)\right)+\sum_{k=2}^{K}L_{k}-\log\bm{p}_{\bm{\theta}}\left(\bm{T}_{0}|\bm{T}_{1}\right),$
(3)

where
$L_{k}=D_{\mathrm{KL}}\left(\bm{q}\left(\bm{T}_{k-1}|\bm{T}_{k},\bm{T}_{0}\right)\parallel\bm{p}_{\theta}\left(\bm{T}_{k-1}|\bm{T}_{k}\right)\right)$,
$D_{\mathrm{KL}}$ is the KL divergence, and the term
$\bm{q}\left(\bm{T}_{k-1}|\bm{T}_{k},\bm{T}_{0}\right)$ can be derived a
closed form of Gaussian distribution according to Equation 1 and Bayes’
theorem.

After training the diffusion model, we can simply sample from a standard
Gaussian distribution and remove the noise in an iterative fashion according
to Equation 2 that follows the reverse diffusion process, resulting in new
samples that follow the original sample distribution.

###  II-B Squish Pattern Representation

A typical layout pattern consists of a stack of polygons and is information-
sparse, which leads to unnecessary computational costs and additional
overfitting risk for neural network methods. The squish pattern [10] is a
lossless and efficient representation method which encodes a layout into
pattern topology matrix and geometric information $\Delta_{x},\,\Delta_{y}$,
as shown in Fig. 2. The layout is split into grids by a set of scan lines that
walk along the edges of polygons. The interval length of every adjacent scan
line pair is stored in the $\Delta$ vectors. Every entry of the topology
matrix is either zero or one, which indicates shape or zeros respectively.
Every squish pattern is extended to a square with fixed side length by the
method introduced in [14].

Figure 2: Squish Pattern Representation.

###  II-C Problem Formulation

The diversity of generated patterns is a critical metric for the layout
pattern generation task. As introduced in [7], the complexity of a layout
pattern is defined as $(c_{x},c_{y})$, where $c_{x}$ and $c_{y}$ are the
numbers of scan lines subtracted by one along the x-axis and y-axis,
respectively. Then we have,

######  Definition 1.

The diversity of the patterns library, denoted by $H$, is defined as the
Shannon Entropy of the distribution of the pattern complexities as follows:

$H=-\sum_{i}\sum_{j}P(c_{xi},c_{yj})\log{P(c_{xi},c_{yj})},$ (4)

where $P(c_{xi},c_{yj})$ is the probability of a pattern with complexity
$(c_{xi},c_{yj})$ sampled from the library.

In a typical case, a greater pattern diversity $H$ indicates that the library
contains more widely distributed patterns.

Based on the related works [8, 9], the generated patterns should satisfy
several pre-defined design rules of IC layout. As illustrated in Fig. 3,
‘Space’ represents the distance between two adjacent polygons. ‘Width’
measures the size of a shape in one direction. And ‘Area’ denotes the area of
a polygon. Based on these geometric measurements, we have,

######  Definition 2 (Pattern Legality).

We call a layout pattern legal if the layout pattern is DRC-clean, given the
design rules.

Figure 3: Illustration of design rules.

Based on the above evaluation metrics, the pattern generation problem can be
formulated as follows,

######  Problem 1 (Pattern Generation).

Given a set of design rules and existing patterns, the objective of pattern
generation is to synthesize a legal pattern library such that the pattern
diversity of the layout patterns in the library are maximized.

##  III Framework

Figure 4: An illustration of the $\mathsf{Diffpattern}$ framework for reliable
layout pattern generation.

###  III-A Overview of $\mathsf{DiffPattern}$

As illustrated in Fig. 4, our framework consists of three phases: (1) Deep
Squish Pattern Representation. Given a set of layout patterns, we first
extract their deep squish pattern representation in which every layout pattern
is decomposed into a topology tensor $\bm{T}$ and two geometric vectors
$\bm{\Delta}_{x}$ and $\bm{\Delta}_{y}$. (2) Topology Tensor Generation. We
subsequently feed the extracted topology tensors $\bm{T}_{0}$ into a diffusion
model. By gradually adding noise to $\bm{T}$ with fixed probabilities
$q(\bm{T}_{k}|\bm{T}_{k-1})$, the model learns how to reverse this $K$-step
process. To synthesize a new topology tensor $\hat{\bm{T}}$, we randomly
sampled a noise topology $\bm{T}_{K}$, and every entry in $\bm{T}$ jumps
between finite states with estimated probability
$p_{\theta}(\bm{T}_{k-1}|\bm{T}_{k})$ until getting a reasonable topology
tensor $\bm{\hat{T}}_{0}$. (3) 2D Legal Pattern Assessment. Given the
generated topology tensors $\bm{\hat{T}}$, we established an explainable
nonlinear system to figure out the proper geometric vectors for each topology
tensor according to the Design Rules.

###  III-B Deep Squish Pattern Representation

Figure 5: An illustration of Deep Squish Pattern Representation. The Topology
Tensor is a lossless and compact representation of the topology matrix. And
the Naive Concatenating brings unbalanced power to each bit and an
exponentially increasing state space.

As we have discussed in Section II-B, the squish pattern is a lossless
representation of the layout pattern, and the topology matrix can be treated
as a one-channel 2D binary mask, as shown in Fig. 5 (left). However, the
information density of each pixel is still not satisfactory given that the
training/inference efficiency of diffusion methods is more sensitive to the
size of input images but significantly less on the number of states of each
pixel. To address this issue, we propose a novel pattern representation
method, Deep Squish Pattern, to attain a more compact pattern representation.

Here we use a running example, as shown in Fig. 5. There is a topology matrix
with four (2$\times$2) adjacent pixels. Each pixel is assigned with either
zero or one to indicate shape or space, respectively. A simple idea to enlarge
the information density is to encode the bits from multiple pixels into one
pixel. However, directly concatenating every bit from different pixels and
forming a new state number, e.g., using 0-15 to represent 16 different states
of (2$\times$2) adjacent pixels, will bring unbalanced power to each position
and may import numerical instability to the network when the bit count is
large. For example in the 4$\times$4 case, the first bit gets a power of
$2^{15}$ while the last bit only gets a power of 1. Furthermore, the count of
states increases exponentially with the count of bits.

Since a state space with 16 ($2^{4}$) discrete states can be expressed by a
permutation of four subspaces with two states. Instead of encoding different
positions with different power, we assign equivalent weight to each position
by folding the squish topology matrix into a topology tensor $\bm{T}$ with
multiple channels. In the folding step, a patch with the size of
$\sqrt{C}\times\sqrt{C}$ from the topology matrix is transferred to a point
with $C$ channels in the tensor $\bm{T}$. $C$ is a hyperparameter, which is
chosen by considering the trade-off between local information density and the
input size. Deep Squish Pattern representation enlarges the practical
receptive field of the model and is naturally suitable for pixel-based machine
learning methods. Once the generation procedure ends, we can also equivalently
recover the original topology matrix by flattening the topology tensor.

###  III-C Topology Tensor Generation

Once we have encoded the existing layout pattern efficiently by using deep
squish pattern representation, we aim to learn the distribution of existing
topology tensors and generate new ones with reasonable topology attributes.
Let ${\bm{T}_{0}}\in\\{0,1\\}^{C\times M\times M}$ be a topology tensor
extracted from existing patterns. The naive idea is that treat the binary
tensor as a grayscale image, learn the distribution through a diffusion model
introduced in Section II-A and clip the generated topology into a binary one
by setting a threshold on it as previous pixel-based pattern generation
methods [8, 7] do. The problem of learning how to generate discrete values
(zero and one in our case) at every entry is left to the network. However, we
argue that requesting the network learn a discrete output in a continual state
space from the training set is a waste of model representation ability. A more
elegant way is to generate discrete output naturally.

Discrete Diffusion Model. Unlike the traditional diffusion model utilized in
the computer vision domain, we aim to synthesize the topology of layout
pattern, where every entry in the topology belongs to a discrete state. We
have made several key modifications to enhance the diffusion model and
synthesize discrete topology patterns directly. To derive them, we first re-
formulate the problem.

At the $k$-th of $K$ diffusion step, $x_{k}\in\\{0,1\\}$ is an entry in the
topology tensor $\bm{T}$. In the discrete diffusion model, a transition
probability matrix $[\bm{Q}_{k}]_{ij}=q(x_{k}=j|x_{k-1}=i)$ is defined to
describe the state transition probability for each $\bm{x}$ at the $k$-th
diffusion step,

$\bm{q}\left(\bm{x}_{k}\mid\bm{x}_{k-1}\right):=\operatorname{Cat}\left(\bm{x}_{k};\bm{p}=\bm{x}_{k-1}\bm{Q}_{k}\right),$
(5)

where $\bm{x}_{k}$ is the one-hot version of the entry $x_{k}$,
$\operatorname{Cat}(\bm{x}|\bm{p})$ is a categorical distribution over the row
vector $\bm{x}$ with probabilities given by the row vector $\bm{p}$, and
$\bm{x}_{k-1}\bm{Q}_{k}$ can be understood as a row vector-matrix product. The
$\bm{Q}_{k}$ is applied to each entry in the topology tensor independently and
$\bm{q}$ factorizes over these higher dimensions as well. The proposed deep
squish pattern representation is customized for this discrete diffusion
process, since the size of transition matrix $\bm{Q}$ increases with the count
of states of each pixel. Every entry $x$ in the topology tensor owns only two
states. On the other side, in the reverse diffusion process, the neural
network aims to predict the categorical distribution probability
$\bm{p}_{\theta}(\bm{x}_{k-1}|\bm{x}_{k})$ over each entry to recover the
original tensor.

The choice of transition probability matrix $\bm{Q}_{k}$ is critical, which
should ensure the forward process $\bm{q}(\bm{x}_{k}|\bm{x}_{0})$ converging
to a known stationary distribution when $k$ becomes large. A uniform
stationary distribution is a natural choice in topology tensor generation,
which means given any $\bm{x}_{0}$, the distribution of every entry
$\bm{x}_{k}$ should follows,

$\bm{q}(\bm{x}_{k}|\bm{x}_{0})\rightarrow\left[0.5,0.5\right],~{}\text{when}~{}k\rightarrow
K.$ (6)

So we design a doubly stochastic matrix $\bm{Q}_{k}$ with strictly positive
entries for topology denoising diffusion process,

$\bm{Q}_{k}=\begin{bmatrix}1-\beta_{k}&\beta_{k}\\\
\beta_{k}&1-\beta_{k}\end{bmatrix},$ (7)

where ${\beta_{k}}\in(0,1)$ is the hyperparameter controlling the noise level.
In order to ensure that the model can learn the original sample distribution
more finely and quickly reach a stable distribution, we follow the classical
setting in previous works [11, 15]. We set a smaller noise in the early
diffusion step and a larger noise in the later step. Specifically, we use a
linearly increasing schedule for $\beta_{k}$:

$\beta_{k}=\frac{(k-1)\left(\beta_{K}-\beta_{1}\right)}{K-1}+\beta_{1},~{}k=1,...,K,$
(8)

where $\beta_{1}$ and $\beta_{K}$ are hyperparameters.

Training Diffusion Model. To training the discrete diffusion model for
topology tensor generation, the training objective at step $k$ is to minimize
the loss function,

$L=D_{\mathrm{KL}}\left(\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\bm{x}_{0}\right)\parallel\bm{p}_{\theta}\left(\bm{x}_{k-1}|\bm{x}_{k}\right)\right)-\lambda\log\bm{p}_{\bm{\theta}}\left(\bm{x}_{0}|\bm{x}_{k}\right),$
(9)

where $\lambda$ is a hyperparameter to balance the loss terms.

Given a topology tensor $\bm{T}_{0}$, we randomly sample a target step $k$
from $1$ to $K$ firstly, and expect to get the noisy sample $\bm{T}_{k}$.
Fortunately, we can explicitly derive that $\bm{x}_{k}$ obeys the following
categorical distribution:

$\bm{q}\left(\bm{x}_{k}|\bm{x}_{0}\right)=\operatorname{Cat}\left(\bm{x}_{k};\bm{p}=\bm{x}_{0}\overline{\bm{Q}}_{k}\right),$
(10)

where $\overline{\bm{Q}}_{k}=\bm{Q}_{1}\bm{Q}_{2}\ldots\bm{Q}_{k}$. Then, we
can directly sample from the above distribution to obtain $\bm{T}_{k}$,
instead of adding noise $k$ times.

After sampling $\bm{T}_{k}$, we feed it into the neural network with the
embedding of the time step $k$. The neural network will predict the logits of
the posterior distribution
$\bm{p}_{\bm{\theta}}\left(\bm{x}_{0}|\bm{x}_{k}\right)$, and then
$\bm{p}_{\bm{\theta}}\left(\bm{x}_{k-1}|\bm{x}_{k}\right)$ can be calculated
as following:

$\bm{p}_{\bm{\theta}}\left(\bm{x}_{k-1}|\bm{x}_{k}\right)=\sum_{\widetilde{\bm{x}}_{0}}\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\widetilde{\bm{x}}_{0}\right)\bm{p}_{\bm{\theta}}\left(\widetilde{\bm{x}}_{0}|\bm{x}_{k}\right),$
(11)

where the term $\widetilde{\bm{x}}_{0}$ will visit every possible state of
$\bm{x}_{0}$. And
$\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\widetilde{\bm{x}}_{0}\right)$ has a
closed form according to Equation 5 and Bayes’ theorem,

$\bm{q}\left(\bm{x}_{k-1}|\bm{x}_{k},\bm{x}_{0}\right)=\operatorname{Cat}\left(\bm{x}_{k-1};\bm{p}=\frac{\bm{x}_{k}\bm{Q}_{k}^{\top}\odot\bm{x}_{0}\overline{\bm{Q}}_{k-1}}{\bm{x}_{0}\overline{\bm{Q}}_{k}\bm{x}_{k}^{\top}}\right),$
(12)

where $\odot$ is a pixel-wise multiplication.

So far, all items in the loss function have been obtained, and the diffusion
model can be trained by the commonly used gradient descent method.

Generating Deep Squish Pattern. Once the training phase ends, we can
synthesize fresh topology by sampling noise topology $\bm{T}_{K}$ from the
stationary distribution, a random uniform distribution, and then gradually
removing the predicted noise from it in the reverse procedure. The sampling
process can be expressed by,

$p_{\theta}(\hat{\bm{T}}_{0}|\bm{T}_{K})=p_{\theta}(\hat{\bm{T}}_{0}|\bm{T}_{1})\prod_{k=2}^{K}p_{\theta}(\bm{T}_{k-1}|\bm{T}_{k}),$
(13)

where $\bm{T}_{k}$ is the estimated pattern topology at step $k$ and
$\hat{\bm{T}}_{0}$ is the newly sampled topology tensor. The denoising
procedure is illustrated in Fig. 6. The generated topology tensor
$\hat{\bm{T}}_{0}$ is naturally a binary one where each entry equals either
zero or one. When the sampling ends, we flatten the $\hat{\bm{T}}_{0}$ for
Legal Pattern Assessment.

Figure 6: An illustration of the (flattened) samples from our Discrete
Diffusion Model.

Topology Pre-filter. We conduct a rule-based topology pre-processing here to
filter out invalid topology, e.g., Bow-tie, according to domain knowledge.
Thanks to the high-quality topologies generated by our discrete diffusion
model, only less than 0.1% of generated topologies are filter-out by the pre-
filter in our settings.

###  III-D 2D Legal Pattern Assessment

Once the squish pattern generation is finished, we need the legal
$\Delta_{x}$s and $\Delta_{y}$s of all generated topologies to generate DRC-
clean layout patterns. The decomposition of topology generation and legal
pattern assessment brings flexibility to $\mathsf{DiffPattern}$ when the
design rules change, as we further discussed in Section IV-C. Instead of using
a black-box deep-learning-based method as previous works [8, 9] do, we use a
white-box method to solve the problem. We first list all constraints for each
generated topology according to the design rules introduced in Fig. 3 and then
formulate a nonlinear system combining all of them, as in Formula (14),

$\begin{cases}\delta_{xi},\delta_{yj}>0,&\forall\delta_{xi},\delta_{yj};\\\
\sum\delta_{xi}=\sqrt{C}M,\quad\sum\delta_{yj}=\sqrt{C}M;\\\
\sum_{i=a}^{b}\delta_{i}\geq\textit{Space}_{\textit{min}},&\forall(a,b)\in
Set_{S};\\\
\sum_{i=a}^{b}\delta_{i}\geq\textit{Width}_{\textit{min}},&\forall(a,b)\in
Set_{W};\\\
\sum\delta_{xi}\delta_{yj}\in[\textit{Area}_{\textit{min}},\textit{Area}_{\textit{max}}],&\forall\text{
Polygon};\end{cases}$ (14)

where $\textit{Space}_{\textit{min}}$ and $\textit{Width}_{\textit{min}}$ are
the lower bound of ‘Space’ and ‘Width’. $\sqrt{C}M\times\sqrt{C}M$ is the
shape of topology matrix. $\textit{Area}_{\textit{min}}$ and
$\textit{Area}_{\textit{max}}$ define the legal area range of each polygon in
the pattern. All the constants are pattern-independent and given by design
rules. Both $Set_{S}$ and $Set_{W}$ are pattern-dependent and indicate which
pair of scan lines is constrained by design rules on ‘Space’ and ‘Width’,
respectively.

Note that the nonlinear system in Equation 14 can be efficiently solved with
vast nonlinear programming algorithms or numerical methods, and the solution
is usually not unique. Every solution of $\Delta_{x}$ and $\Delta_{y}$
together with the associated topology formulates a complete squish pattern
representation. As further detailed in Section IV-C, $\mathsf{DiffPattern}$
can easily synthesize a large number of legal layout patterns from a single
topology with the given design rules. Theoretically, there are cases where no
legal solution is figured out in a limited time. Although it never happens in
our experiments (more than $1.0\times 10^{8}$ times attempts), we can simply
remove these unsolvable cases from the generated topology set to avoid
synthesizing illegal patterns. In most cases, the choice of the initial value
for the nonlinear programming algorithms may have a minor impact on pattern
diversity and legality. In practice, we randomly choose a pair of existing
geometric vectors from datasets as the start point, which will empirically
accelerate the convergence of nonlinear programming algorithm.

##  IV Experimental Results

TABLE I: Comparison on pattern diversity and legality. All results are copied from [9] and [8]. ‘Real Patterns’ refer to the whole dataset (Training set + Test set). ‘-’ refer to Not Applicable. Set/Method | Generated Topology | Generated Patterns | Legal Patterns
---|---|---|---
Patterns | Diversity ($\uparrow$) | Legality ($\uparrow$) | Diversity ($\uparrow$)
Real Patterns | - | - | - | 13869 | 10.777
CAE[7] | 100000 | 100000 | 4.5875 | 19 | 3.7871
VCAE[8] | 100000 | 100000 | 10.9311 | 2126 | 9.9775
CAE+LegalGAN[8] | 100000 | 100000 | 5.8465 | 3740 | 5.8142
VCAE+LegalGAN[8] | 100000 | 100000 | 9.8692 | 84510 | 9.8669
LayouTransformer[9] | - | 100000 | 10.532 | 89726 | 10.527
$\mathsf{DiffPattern}$-S | 100000 | 100000 | 10.815 | 100000 | 10.815
$\mathsf{DiffPattern}$-L | 100000 | 10000000 | 10.815 | 10000000 | 10.815

###  IV-A Experimental Setup

Datasets. We follow previous work [8, 9] to obtain the dataset of small layout
pattern images with the size of $2048\times 2048$ $nm^{2}$ by splitting a
$400\times 160$ $\mu m^{2}$ layout map from ICCAD contest 2014. The size of
extracted topology tensor is fixed as 16$\times$32$\times$32 with $C=16$ in
Deep Squish Pattern Representation. 3000 images are randomly choosed as test
set, while others are used for training.

((a))  ((b))  ((c))

((d))  ((e))  ((f))

Figure 7: Different layout patterns that are generated from a single topology
with the same design rule.

Diffusion Model Configuration. Following the setting in previous works [11,
15], we use a U-Net [16] as our backbone in the discrete diffusion model to
predict the posterior distribution during the reverse diffusion process. There
are four feature map resolutions in the model, $[32\times 32,16\times
16,8\times 8,4\times 4]$. Each resolution level has two convolutional residual
blocks, where the numbers of convolution channels on the four resolutions are
$\left[128,256,256,256\right]$, respectively. A self-attention block is also
placed between two convolutional blocks at the 16$\times$16 resolution level.
Moreover, the time step $k$ is included in each residual block through the
sinusoidal position embedding [17].

Training Details. We train the diffusion model for $0.5$M iterations with a
batch size of $128$. The learning rate is $2\times 10^{-4}$. And we use the
Adam optimizer. Other hyperparameters are chosen as following: the dropout
rate is set to $0.1$, the grad clip is set to $1$, and the loss coefficient
$\lambda$ is set to $0.001$. We set diffusion timesteps $K=1000$ to ensure
that the forward diffusion process converges to the uniform stationary
distribution within $K$ steps. The noise schedule is: $\beta_{k}$ is linearly
increased from $0.01$ to $0.5$. The training procedure takes about $17$ hours
in total on 8 NVIDIA RTX 3090 GPUs.

###  IV-B Pattern Diversity and Legality

The diversity is calculated by Equation 4, and the legality is checked by a
tool Klayout based on the design rules described in Section II-C.

To have a fair comparison with previous methods, we randomly synthesize 100000
typologies. We denote a version of $\mathsf{DiffPattern}$ as
$\mathsf{DiffPattern}$-S where we only assign one pair of geometric vectors to
each generated topology in the phase of legal pattern assessment. However,
$\mathsf{DiffPattern}$ is able to generate a large amount of legal patterns
for each topology. To show the strong ability of our methodologies, we have
another version denoted as $\mathsf{DiffPattern}$-L, where we figure out one
hundred different legal geometric vectors for each generated topology.
Considering the size of topology and the large search space, the number of
legal solutions for each topology is huge. We ‘only’ randomly take one hundred
from them due to the time limitation.

We compare our $\mathsf{DiffPattern}$ with several learning-based layout
pattern generation methods. CAE [7] denotes a vanilla convolutional auto-
encoder model. VCAE [8] utilizes a variational convolutional auto-encoder
model. Both of them are pixel-based methods. LegalGAN [8] is a learning-based
post-processing method that legalizes a newly generated topology by modifying
it. LayouTransformer [9] is a sequential-based method. LayouTransformer
applies a transformer-based model to synthesize new sequential representations
of layout patterns without topology generation. As shown in Table I, thanks to
the topology pre-filter and rule-based 2D legal pattern assessment, both
$\mathsf{DiffPattern}$-S and $\mathsf{DiffPattern}$-L achieve perfect
performance (i.e. 100%) under the metric of legality in the standard settings.
With the well-designed topology generation method, $\mathsf{DiffPatten}$ also
gets reasonable improvement (10.527$\rightarrow$10.815) on the diversity of
generated pattern compared with the previous best method, LayouTransformer.
Furthermore, different from the previous methods, the legalization of
$\mathsf{DiffPattern}$ mainly relies on the rule-based legal pattern
assessment and topology pre-filter. When design rules change, it is easy for
us to produce another batch of diverse patterns that satisfy the new design
rules, without re-training the topology generation model. We detail the
flexibility of our method in the next subsection.

((a))  ((b))  ((c))

Figure 8:  Layout patterns that are generated from the same topology with
different design rules: (a) Normal rule; (b) Larger
$\textit{space}_{\textit{min}}$; (c) Smaller $\textit{Area}_{\textit{max}}$.

###  IV-C Flexibility

A main advantage of $\mathsf{DiffPattern}$ is that the white-box 2D legal
pattern assessment phase is quite flexible. We show two applications of this
property here.

Generate Different Patterns from Single Topology. Given the design rules and
the topology, the non-linear system in Equation 14 usually has many legal
solutions, i.e., the geometric vector pairs. Every legal solution leads to a
legal layout pattern, and these layout patterns share a common topology, which
are useful in some downstream tasks. We show the examples where several layout
patterns are generated from a single topology with different geometric vectors
in Fig. 7.

Generate Legal Patterns with Different Design Rules. The legalization and
topology generation are decoupled in $\mathsf{DiffPattern}$, which allows us
to generate legal layout patterns under different design rules without re-
training the model. We show the examples where several layout patterns are
generated from the same topology but with different design rules in Fig. 8.

###  IV-D Distribution of Complexity

Diversity is a critical metric of the quality of generated pattern library. As
defined in Section II-C, diversity is the Shannon entropy of the distribution
of pattern complexity, i.e., the number of scan lines subtracted by a pattern
along the x-axis and y-axis. We visualize the distribution of complexity in
Fig. 9. The patterns generated by $\mathsf{DiffPattern}$ share a similar
complexity distribution with real patterns. This visualization further
demonstrates our ability to generate high-quality layout patterns.

Figure 9: An illustration of complexity distribution.

###  IV-E Model Efficiency

Model efficiency is an essential statistic for layout generation methods.
Since the topology generation and layout pattern assessment are decomposed in
our model, we record the average time to sample a new topology and figure out
a legal solution for Equation 14 separately with our implementation. The
results are listed in Table II. We have mentioned in Section III-D that we
randomly select a pair of existing geometric vectors to initialize the non-
linear system for acceleration. We denote the version as Solving-E. We denote
the original version with random initialization as Solving-R. Comparing with
Solving-R, the proposed Solving-E version can achieve an average of
$2.30\times$ acceleration.

###  IV-F Discussion on Validity

There is a metric named pattern validity proposed by previous work [8]. The
evaluation of validity is based on an encoder-decoder model that is pre-
trained on the training set. The basic idea is if the generated patterns share
more similar features with patterns in the training set, these new patterns
will get a better score from the validity metric. However, we argue that the
meaning of the metric of validity is quite limited. One main motivation of the
layout pattern generation task is to synthesize a large amount of diverse but
legal layout patterns for downstream tasks, e.g., hotpot detection or
lithography simulation. In these situations, legal patterns that are
dissimilar from existing patterns are preferred but they get worse scores from
validity. What makes the metric worse is that the measurement of validity
encourages the overfitting of the training set. For example, according to [8,
9], the generated patterns even receive a much higher score
(65%$\rightarrow$84%) than the patterns from the test set, which theoretically
follows the same distribution as the training set. It is unreasonable to
believe the method with the better score in validity is superior in quality.
Therefore, we have not evaluated $\mathsf{DiffPattern}$ with this metric.

TABLE II: Model efficiency of $\mathsf{DiffPattern}$. We record the average processing time for each sample (topology or layout pattern) in our machine. One Nvidia RTX 3090 GPU is used for topology sampling and one Intel(R) Xeon(R) Gold 6326 CPU @ 2.90GHz is used to figure out the non-linear system in this table.  Phase/Method | Cost Time (s) | Acceleration
---|---|---
Sampling | 0.544 | N/A
Solving-R | 0.269 | 1.00$\times$
Solving-E | 0.117 | 2.30$\times$

##  V Conclusion

We aim to synthesize diverse and legal layout patterns, and propose a
practical method named $\mathsf{DiffPattern}$. Based on the given design rules
our approach allows us to stably generate theoretically infinite legal layout
patterns. The experiment results show that $\mathsf{DiffPattern}$ outperforms
previous SOTA methods by a large margin. Meanwhile, $\mathsf{DiffPattern}$ is
easy to extend and can be used on more complex pattern generation scenarios.
In future work, we hope to extend our method to a more generic layout pattern
generation approach.

## References

  * [1] J.-R. Gao, X. Xu, B. Yu, and D. Z. Pan, “Mosaic: Mask optimizing solution with process window aware inverse correction,” in _DAC_. IEEE, 2014, pp. 1–6.
  * [2] J. Kuang and E. F. Young, “An efficient layout decomposition approach for triple patterning lithography,” in _DAC_. IEEE, 2013, pp. 1–6.
  * [3] B. Yu, K. Yuan, D. Ding, and D. Z. Pan, “Layout decomposition for triple patterning lithography,” _TCAD_ , vol. 34, no. 3, pp. 433–446, 2015.
  * [4] R. Chen, W. Zhong, H. Yang, H. Geng, X. Zeng, and B. Yu, “Faster region-based hotspot detection,” in _DAC_ , 2019, pp. 1–6.
  * [5] G. R. Reddy, C. Xanthopoulos, and Y. Makris, “Enhanced hotspot detection through synthetic pattern generation and design of experiments,” in _VTS_. IEEE, 2018, pp. 1–6.
  * [6] W. Ye, Y. Lin, M. Li, Q. Liu, and D. Z. Pan, “Lithoroc: lithography hotspot detection with explicit roc optimization,” in _DAC_ , 2019, pp. 292–298.
  * [7] H. Yang, P. Pathak, F. Gennari, Y.-C. Lai, and B. Yu, “Deepattern: Layout pattern generation with transforming convolutional auto-encoder,” in _DAC_ , 2019, pp. 1–6.
  * [8] X. Zhang, J. Shiely, and E. F. Young, “Layout pattern generation and legalization with generative learning models,” in _ICCAD_. IEEE, 2020, pp. 1–9.
  * [9] L. Wen, Y. Zhu, L. Ye, G. Chen, B. Yu, J. Liu, and C. Xu, “Layoutransformer: Generating layout patterns with transformer via sequential pattern modeling,” in _ICCAD_. IEEE, 2022\.
  * [10] F. E. Gennari and Y.-C. Lai, “Topology design using squish patterns,” Sep. 9 2014, uS Patent 8,832,621.
  * [11] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” _NeurIPS_ , vol. 33, pp. 6840–6851, 2020.
  * [12] J. Song, C. Meng, and S. Ermon, “Denoising diffusion implicit models,” in _ICLR_ , 2020.
  * [13] L. Yang, Z. Zhang, Y. Song, S. Hong, R. Xu, Y. Zhao, Y. Shao, W. Zhang, B. Cui, and M.-H. Yang, “Diffusion models: A comprehensive survey of methods and applications,” _arXiv preprint arXiv:2209.00796_ , 2022.
  * [14] H. Yang, P. Pathak, F. Gennari, Y.-C. Lai, and B. Yu, “Detecting multi-layer layout hotspots with adaptive squish patterns,” in _DAC_ , 2019, pp. 299–304.
  * [15] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg, “Structured denoising diffusion models in discrete state-spaces,” _NeurIPS_ , vol. 34, pp. 17 981–17 993, 2021.
  * [16] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _MICCAI_. Springer, 2015, pp. 234–241.
  * [17] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _NeurIPS_ , vol. 30, 2017.