# Pikachu: Securing PoS Blockchains from Long-Range Attacks by Checkpointing
into Bitcoin PoW using Taproot

Sarah Azouvi  Protocol Labs and  Marko Vukolić  Protocol Labs

(2022)

###### Abstract.

Blockchain systems based on a reusable resource, such as proof-of-stake (PoS),
provide weaker security guarantees than those based on proof-of-work.
Specifically, they are vulnerable to long-range attacks, where an adversary
can corrupt prior participants in order to rewrite the full history of the
chain. To prevent this attack on a PoS chain, we propose a protocol that
checkpoints the state of the PoS chain to a proof-of-work blockchain such as
Bitcoin. Our checkpointing protocol hence does not rely on any central
authority. Our work uses Schnorr signatures and leverages Bitcoin recent
Taproot upgrade, allowing us to create a checkpointing transaction of constant
size. We argue for the security of our protocol and present an open-source
implementation that was tested on the Bitcoin testnet.

Blockchain, proof-of-stake, long-range attack

††journalyear: 2022††copyright: rightsretained††conference: Proceedings of the
2022 ACM Workshop on Developments in Consensus; November 7, 2022; Los Angeles,
CA, USA††booktitle: Proceedings of the 2022 ACM Workshop on Developments in
Consensus (ConsensusDay ’22), November 7, 2022, Los Angeles, CA, USA††doi:
10.1145/3560829.3563563††isbn: 978-1-4503-9879-4/22/11††ccs: Security and
privacy Cryptography

##  1\. Introduction

Long-range attacks (LRA) — also called posterior corruption attacks
(deirmentzoglou2019survey, ) — are one of the major security issues affecting
permissionless proof-of-stake (PoS) blockchains. These attacks rely on the
inability of a user who disconnects from the system at time $t_{1}$ and
reconnects at a later time to tell that validators who were legitimate at time
$t_{1}$ and left the system (by e.g., transferring their stake to other
validators, or to themselves under a different identity) are not to be trusted
anymore. In a PoS system, where the creation of blocks is costless (i.e., does
not cost physical resource such as energy), and timeless (i.e., is not rate-
limited in time), these validators could create a fork that starts from the
past, i.e., at time $t_{1}$, and runs until the present. This is in sharp
contrast to proof-of-work (PoW) systems, where creating blocks requires time
(e.g., due to Bitcoin (nakamoto2008peer, ) difficulty adjustment) and physical
resources (e.g., energy for performing actual computation) and not just using
cryptographic keys. A client of a PoS blockchain would be unable to recognize
the attack as they are presented with a “valid” chain fork. See Figure 1 for a
visual explanation of the attack.

Figure 1. Illustration of the long-range attack. After the green validators
(i.e., validators associated with the green key on the figure) left the
system, the adversary acquired their keys. In a PoS blockchain, having access
to validators’ keys is enough to create new blocks and hence the adversary can
create a chain as long as the honest chain (perhaps even simulating
configuration change in its chain). Any user that trusted the green key and is
presented with both chains cannot differentiate the honest from the
adversarial chain.

Recently, Steinhoff et al. (steinhoff2021bms, ) proposed an approach to deal
with LRA by anchoring (checkpointing) the PoS membership into Ethereum’s
proof-of-work blockchain (Eth 1.0), which is not vulnerable to this type of
attack. The main idea of their work is to have a smart contract on the
Ethereum blockchain that keeps track of the state of the membership of the
underlying PoS system. For a typical Byzantine Fault-Tolerant (BFT) protocol
underlying a PoS blockchain, the smart contract on Ethereum would only be
updated if, e.g., two thirds of the current staking power (or blockchain
members in case of uniform voting rights) instruct the smart contract to do
so. In the approach of Steinhoff et al. each validator will send a transaction
to the smart contract that indicates a vote for a new set of validators. As
soon as two thirds of the votes for the same set have been received, the smart
contract automatically updates its state to the new set. From this moment on,
the members of the new set are in charge of voting for the next set and so
forth. Every user that needs to verify that a set of validators are indeed
legitimate and most recent ones, can do so by simply checking the smart
contract. An adversary cannot change the state of the smart contract, even
with the keys of former validators, without creating a fork on the PoW
blockchain, which is considerably more, if not prohibitively expensive. Any
user can resort to the Ethereum smart contract to verify the correct state of
the checkpointed PoS chain, effectively preventing the LRA attack.

However, as it happens, Ethereum is abandoning PoW and transitions to PoS
(EthereumMovingPoS, ) (Eth 2.0). Hence, the approach of Steinhoff et al. is no
longer viable as PoS of Eth 2.0 cannot be used instead of PoW for anchoring as
it is itself susceptible to the LRA vulnerability. In this paper, we design a
solution to LRA, inspired by Steinhoff et al., using Bitcoin’s PoW, assuming
that Bitcoin will never change its underlying consensus mechanism. The history
of altcoin forks off Bitcoin and the Bitcoin development ethos give very
realistic assurance that this assumption will hold.111The discussion on long-
term viability of energy consumption of Bitcoin is out of scope of this paper
and is available elsewhere (Vukolic21, ).

However, the implementation and design of such a scheme on Bitcoin is more
challenging, compared to the implementation of Steinhoff et al. on Eth 1.0,
because Bitcoin’s scripting language expressivity is considerably more limited
compared to smart contracts on Ethereum. Besides, the approach designed by
Steinhoff et al. leverages multi-signatures for anchoring, which can quickly
bloat the transaction size, making it at worst impossible to anchor PoS
networks with large number of validators, or, at best, very costly to do so.

To address these limitations, our approach is to use the capabilities enabled
by the recent Taproot upgrade (bip341, ) to Bitcoin, which allows for more
efficient Schnorr threshold signatures. Briefly, our protocol, called Pikachu,
works as follows. As Bitcoin does not allow for stateful smart contracts, we
use an aggregated public key to represent the configuration of validators
$C_{i}$ in the PoS system. When the set changes significantly enough to
configuration $C_{i+1}$, the aggregated key must be updated in the Bitcoin
blockchain. This is done by having a transaction transferring the funds
associated with the aggregated key of the previous validators $C_{i}$ to the
new aggregated key controlled by validators in configuration $C_{i+1}$.
Instead of having each validator in $C_{i}$ send a transaction to the Bitcoin
network, this transaction is signed interactively, off-chain, and all the
signatures are aggregated into one constant-size signature. Furthermore, we
store the Merkle root of the state of the checkpointed PoS blockchain in the
Bitcoin $OP\\_{RETURN}$ field of the transaction from $C_{i}$ to $C_{i+1}$. We
store the data pertaining to this checkpoint off Bitcoin blockchain. While the
data pertaining to the checkpoint could be stored anywhere (e.g., IPFS (ipfs,
)) and validated against the state root stored in the Bitcoin transaction —
our implementation uses a content-addressable key-value store implemented on
top of the PoS system to store the actual checkpointed state. Figure 2
illustrates the high-level protocol.

Figure 2. High-level visualization of the Pikachu protocol. Checkpoints from
the PoS chain (in blue) are periodically pushed to the Bitcoin blockchain (in
orange) by the PoS Validators. The checkpoints contain the Taproot address $Q$
(which itself contains the aggregated public key of the configuration and
commitment to the PoS chain ckpt) as well as a content identifier $cid$ that
can be used with any content-addressable storage to retrieve information about
the configuration (IPFS pictured).

We note that since our work is based on Schnorr threshold signatures and uses
Bitcoin’s Taproot, it could be of independent interest to any project looking
to implement threshold signing transactions on Bitcoin (for example,
sidechains (bitcoinpeg, )).

To summarize, our contribution is as follows. Starting from the observation
that PoW gives much stronger security guarantees than PoS, we present a
protocol to protect current PoS blockchains against LRA by anchoring their
state onto Bitcoin’s blockchain. The advantage of using Bitcoin unlike, for
example, a website, is that it is itself decentralized, hence our protocol
does not add any single point-of-failure to a decentralized PoS system. We
implemented our protocol on top of a delegated PoS blockchain and tested it on
Bitcoin testnet storing checkpoints into a key-value store maintained by the
PoS validators (although alternative storage method, such as IPFS could be
used).

The rest of this paper is organized as follows. We start by providing the
necessary background in Section 2 and our model and assumptions in Section 3.
We present our design in Section 4 then a security argument in Section 5.
Section 6 presents the implementation of the protocol. We discuss related work
in Section 7.

##  2\. Background

We use elliptic curve notation for the discrete logarithm problem. Suppose $q$
is a large prime and $G,J$ are generators of a subgroup of order $q$ of an
elliptic curve $\mathbb{E}$. We assume that $\mathbb{E}$ is chosen in such a
way that the discrete logarithm problem in the subgroup generated by $G$ is
hard, so it is infeasible to compute the integer $d$ such that $G=dJ$.

Let $H,H_{1},H_{2},H_{TapTweak}$ be cryptographic hash functions mapping to
$\mathbb{Z}_{q}^{*}$. We denote by $x\xleftarrow{\$}S$ that $x$ is selected
uniformly at random from $S$.

###  2.1. Schnorr signature

The Schnorr signing scheme (Schnorr91, ) works as follows. Let
$(s,Y)\in\mathbb{Z}_{q}^{*}\times\mathbb{E}$ be a user key pair (such that
$Y=sG$) and $m$ a message to be signed. The signer performs the following
steps.

  1. (1)

$k\xleftarrow{\$}\mathbb{Z}_{q}^{*}$

  2. (2)

$R\leftarrow kG$

  3. (3)

$z\leftarrow k+H(m||R||Y)\cdot s\mod q$

The signature is then $(z,R)$ and is verified by checking that
$zG\stackrel{{\scriptstyle?}}{{=}}R+H(m||R||Y)Y$.

###  2.2. Secret sharing schemes

A secret sharing scheme allows one participant (a dealer) to share a secret
with $n$ other participants, such that any $t$ of them can recover the secret
but any set of $t-1$ or less of them cannot. Furthermore, a desirable property
of a secret sharing scheme is to be publicly verifiable, i.e., anyone should
be able to verify that the dealer computed the correct shares and did not
cheat. In this paper, we will use Feldman’s verifiable secret sharing scheme
(feldman1987practical, ) (VSS), which we describe in steps 1-3 of Figure 5.

####  2.2.1. Generating a secret

Unlike Feldman’s VSS scheme, in which only one participant generates a secret
and shares it with their peers, we consider a protocol where everyone
contributes equally to generate a common secret, such that no set of
participants of size strictly smaller than $t$ can recover the secret on their
own. We will use the scheme designed by Gennaro et al. (gennaro2007secure, )
that we define in Figure 5, and we adopt the following notation:

$(s_{1},\cdots,s_{n})\ext@arrow
9999{\arrowfill@\leftarrow\relbar\rightarrow}{}{(t,n)}(r,Y,a_{k}G,S_{0}),\
k\in\\{1,\cdots,t-1\\}$

to mean that $s_{j}$ is player $j$’s share of the secret $r$ for each $j\in
S_{0}$. The values $a_{k}G$ are the public commitments used to verify the
correctness of the shares and $(r,Y)$ forms a key pair where $r$ is a private
key and $Y$ is the corresponding public key. The set $S_{0}$ denotes the set
of players that have not been detected to be cheating during the execution of
the protocol. This protocol is secure for any $t>\frac{n}{2}$ (i.e., it can
tolerate an adversary that corrupts up to half of the participants).

###  2.3. Threshold signing

A $t$-of-$n$ threshold signing scheme allows any combination of $t$
participants to sign a message while preventing any coalition of $t-1$
participants or less to create a valid signature, i.e., at least $t$
participants must agree to sign the message for the signature to be valid. We
use the threshold signing protocol FROST (komlo2020frost, ), that we define in
Figure 6. This interactive protocol will either output a Schnorr signature
$(z,R)$ on a message $m$ or a abort message, together with a set of
misbehaving participants such that the protocol can be rerun without these
misbehaving participants in the next step. The protocol relies on a signature
aggregator (SA), however, as the main role of the SA is to choose the subset
of participants designated for signing, it can easily be removed. Instead, we
can have each participant compute the set in a deterministic way.
Alternatively, in the case of PoS chain, we could choose this set pseudo-
randomly using some randomness coming from the chain (random numbers are often
created as part of a PoS protocol as they are needed for, e.g., leader
election).

##### Choice of the Schnorr signing protocol.

We chose to use the FROST signing protocol because it is more efficient than
alternative protocols, such as the Stinson and Strobl (stinson2001provably, )
protocol, even though it is not robust, i.e., the protocol cannot complete if
one participant aborts or misbehaves. However, misbehaving participants are
detectable in FROST (each public share is verifiable against a public key), so
the protocol can simply be restarted from scratch without those malicious
participants. We did not use other Schnorr signing protocols (nick2020musig2,
; drijvers2019security, ) as they are not compatible with threshold signing.

Note that we did not implement the key generation algorithm presented by Komlo
and Goldberg (komlo2020frost, ), used originally in FROST, as it does not
allow to detect misbehaving participants, therefore losing the ability to re-
start the protocol without the misbehaving participants. Instead, we will use
the scheme by Gennaro et al. (gennaro1999secure, ) and borrow only the signing
scheme presented in the FROST paper (komlo2020frost, ), as per the authors’
suggestion. The distributed key generation (DKG) algorithm by Gennaro et al.
is also used by Stinson and Strobl (stinson2001provably, ) and has the
advantage of being robust (it will complete despite misbehaving participants,
who are detected through a complaint process). We follow the suggestion in
Gennaro et al. (gennaro2007secure, ) and use the simpler variant of the DKG,
JF-DKG, as this is sufficient for our application of threshold signing.

The main reason for preferring an efficient but non-robust signing algorithm
is that our protocol will eventually be incentivized (financial rewards will
be given out to participants who perform the signature). Therefore, it is
reasonable to expect participants to cooperate, especially when malicious
behavior is detectable and can only delay — not prevent — the signing. Because
both the DKG and the signing part of our protocol are modular, other threshold
signing protocols can be used interchangeably for different threat models
(e.g., including the robust signing protocol in (stinson2001provably, )).

###  2.4. Taproot

Taproot is a recent Bitcoin network upgrade that allows transactions to be
signed using Schnorr signatures and that introduces a new data-structure,
Merkelized Abstract Syntax Trees (MAST), for more advanced scripting in a
privacy-preserving way. The main advantage of Schnorr signatures over the
ECDSA multi-signature is that they enable signature aggregation, saving space
in Bitcoin blocks while also providing more privacy as it is not possible to
distinguish between a “regular” transaction, i.e., sending bitcoins from one
person to another, and a more complex one, e.g., using a threshold signature.
This could help hide identities in the blockchain and thwart clustering
deanonymization (meiklejohn2013fistful, ) although we are not interested in
this property for this work.

A Taproot address has two components: a single public key (the internal key)
and a script tree, identified by its Merkle root. Either component can be used
independently to spend the UTXO. In the case of threshold or multi-signatures,
the internal key can be the aggregated public key of all the signers. The
script tree can contain an arbitrary number of different scripts, each of
which specify a condition that must be satisfied in order for the coins to be
spendable. For example, one condition can be to give the pre-image of a hash.
As the name suggests, in the script tree, the scripts are organized in a tree
(see Figure 3). The transaction can be spent either by using the internal
secret key (key path) or by satisfying one of the conditions in the tree
(script path). In this paper, we are interested in spending a Taproot output
using the key path. It should be noted that it is possible to use the script
tree to define a threshold signature scheme (murch_2020, ), though less
efficient as the size of the tree would grow exponentially with the number of
participants (bitcoinpeg, ).

Figure 3. Taproot Output Composition

We now detail how to spend a Taproot output using the key path.

####  2.4.1. Key path spending

To prevent a potential vulnerability in which one user of a threshold or
multi-signature could steal all the funds (bitcoin_2021, ), the output key
should commit to a (potentially unspendable) script path even if the spending
condition does not require a script path (i.e., if only the key path is going
to be used). There are multiple ways to achieve this with Taproot. The most
natural way is to simply include the internal public key in the “tweak.” The
tweaked public key (i.e., outer key) is then computed as follows:

$Q=P+\text{int}(H_{TapTweak}(bytes(P)))G$

where $P$ is the internal public key and $H_{TapTweak}$ is a hash function.
The associated tweaked private key is then:

$q=p+\text{int}(H_{TapTweak}(bytes(P)))$

where $p$ is the private key associated with $P$. In order to spend the output
using the key path, one must then sign the transaction with the tweaked
private key.

##### Adding a commitment

Alternatively, the script path could be used to add a commitment. For example
in our case this commitment could be the hash of the underlying PoS chain at
regular intervals. Let $c$ denote this commitment. In this case, the tweaked
public key becomes: $Q=P+H_{TapTweak}(P||c)G$ and the tweaked private key
$q=p+H_{TapTweak}(P||c)$. The script path is still unspendable, and the output
is spent by signing using the tweaked private key.

####  2.4.2. Transaction notation

For any Bitcoin transaction, we use the following notation:

$\textsf{input}_{1},\dots,\textsf{input}_{i}\rightarrow((\textsf{amount}_{1},\textsf{output}_{1}),\dots,(\textsf{amount}_{j},\textsf{output}_{j}))$

to say that all the coins associated with
$\textsf{input}_{1}\dots,\textsf{input}_{i}$ are transferred to
$\textsf{output}_{1},\dots,\textsf{output}_{j}$ with, respectively,
$\textsf{amount}_{1}$,$\dots$, $\textsf{amount}_{j}$. As a reminder, since
Bitcoin is UTXO based, all the coins from an input must be transferred during
the transaction, although to potentially multiple addresses. Additionally, it
must be the case that
$\textsf{amount}_{1}+\cdots+\textsf{amount}_{j}\leq\textsf{input}_{1}.\textsf{amount}+\cdots+\textsf{input}_{i}.\textsf{amount}$
where $\textsf{input}_{k}.\textsf{amount}$ represents the total amount
associated with $\textsf{input}_{k}$. The remaining amount (in the case of a
strict inequality) is used as a transaction fee for the miner mining the
block.

##  3\. Model and Assumptions

We assume an underlying blockchain based on a reusable resource such as PoS or
proof-of-space . Each state of the PoS blockchain is associated with a set of
participants, called the configuration and denoted by $C$, and their
corresponding _power_ (e.g., number of coins staked in the case of proof-of-
stake and storage space in the case of proof-of-storage).We call the set of
weighted participants in a configuration the _power table_. The power table is
determined by a set of signing keys and their associated weight:
$C=\\{(PoS.pk_{i},w_{i})\\}_{i=1}^{|C|}$. Each signing private key
$PoS.sk_{i}$ is private to $i$-th participant. For simplicity, we consider a
flat model, i.e., one participant accounts for one unit of power in the PoS
blockchain, hence we omit the weight from our model moving forward. The flat
model could be generalized by considering that one participant with $x$ units
of power possesses $x$ public keys, one for each of their units of power. We
will discuss how this assumption impacts the scalability of our protocol in
Section 8. Furthermore, we assume that there is some similarity between
successive configurations of the system, i.e., the set of participants does
not change completely from one configuration to another. Formally, we define
the difference between two configurations $C_{j}$ and $C_{i}$ as their
symmetric difference ($C_{i}\triangle C_{j}$), which corresponds to the number
of reconfiguration requests that need to be applied to $C_{i}$ in order to
obtain $C_{j}$. We assume that for two consecutive configurations $C_{i}$ and
$C_{i+1}$, their symmetric difference is bounded by some parameter $b$.

Following (azouvi2020winkle, ), we define a _perpetually honest_ participant
as a participant that follows the protocol and maintains the secrecy of their
signing keys in perpetuity (an adversary may never have access to them). This
is opposed to an _eventually compromised_ participant who after some time,
leaks all its previous signature keys to the adversary.

We assume that the PoS is secure, i.e., satisfies the usual security
properties of consistency, chain growth, and chain quality (garay2015bitcoin,
), as long as a sufficient fraction of the participants are perpetually
honest. Let $f$ be the maximum fraction of power that an adversary can control
while the protocol maintains its security when the rest of the power table is
perpetually honest (e.g., $f=1/3$). For simplicity, we assume that this
blockchain provides instant finality, i.e., that there are no forks. This can
be achieved using some variant of a BFT-protocol (gilad2017algorand, ;
buchman2016tendermint, ) or relaxed by using a “lookback” parameter. For
example, if a block is final after $k$ confirmations, then we will use the
state of the chain $k$ blocks in the past instead of the latest state to
ensure consistent views across participants.

For the rest of this paper we will consider the security of the PoS chain
under eventually compromised honest participant as follows. We consider an
adversary $\mathcal{A}$ that, for each state $i$ of the PoS system, controls
all the keys from previous configurations $(C_{j})_{j<i-L}$ where $L\gg 1$ is
a parameter (assumption 1) as well as a fraction of at most $f$ participants
in configurations $(C_{j})_{i-L\leq j\leq i}$ (assumption 2). We quickly note
that $f<\frac{1}{2}$ since there does not exist any protocol that is secure
with $f>\frac{1}{2}$.

Under this assumption, the adversary is able to mount a LRA as follows. The
adversary starts a fork of the PoS chain at height $j<i-L$, using the keys
from configuration $C_{j}$ and that runs until the current height $i$. Since
the adversary does not hold the keys from configuration $i-L$ and above, this
means that from this height, the configurations on the adversarial fork and on
the honest chain must differ. Note that under this attack, any online
validator is able to differentiate the correct chain from a chain created as
part of a LRA (since they are not part of the configurations in the
adversarial fork). In the rest of the paper we use _correct chain_ to mean the
chain in the view of the online validators. Our protocol will ensure that any
user is also able to distinguish each chain even if they have been offline, by
looking at the Bitcoin blockchain. We discuss the security properties that the
protocol should achieve in Section 5.

We add another, optional, assumption: the existence of a random beacon
$(\text{RB}_{i})_{i\in\mathbb{N}}$ that emits a new randomness for each state
of the database (i.e., at each height of the underlying PoS blockchain). This
is a standard assumption in PoS blockchains as a random beacon is necessary
for the leader election part of the protocol. This randomness will be used by
participants to pseudo-randomly select the set of signers. Another option
would be to select this set in any deterministic manner.

Lastly, participants will use the PoS chain to broadcast the messages relative
to our Pikachu protocol (although another broadcast channel could be
implemented alternatively). We assume that each message is included in the
chain (or broadcast) after a small number of blocks.

##  4\. Protocol

###  4.1. Overview

The intuition behind the protocol is as follows: each configuration $C_{i}$ is
associated with a Taproot public key $Q_{i}$ that consists of an internal key,
in this case an aggregate public key $pk_{i}$, that participants computed with
an interactive DKG protocol (step 1 of the main algorithm protocol in Figure
4) and a tweaked part as defined in Section 2.4.1. We chose to tweak the
internal key using a commitment to the PoS chain (i.e., the hash of the state
of the PoS blockchain). Each player $j$ in the configuration then knows a
share of the secret key associated with $pk_{i}$, $s_{i,j}$, such that $t_{i}$
of the shares are enough to compute a valid signature on any message, but
fewer than $t_{i}$ participants cannot compute a signature. Configuration
$C_{i}$ is responsible for anchoring the state of the PoS chain at this point
in time in the Bitcoin blockchain, which also includes updating the new
configuration. In order to do so, the new configuration $C_{i+1}$ must first
compute their aggregated public key $pk_{i+1}$ using the DKG algorithm. This
key is then tweaked using a commitment ckpt to the PoS chain (i.e., the hash
of the PoS chain at that time). The tweaked key becomes
$Q_{i+1}=pk_{i+1}+H_{TapTweak}(pk_{i+1}||\textsf{ckpt})G$. Note that only the
tweaked key will appear on the blockchain so the hash ckpt will not be visible
by anyone looking at the blockchain without external knowledge. However,
anyone who has access to $pk_{i+1}$ and ckpt can easily reconstruct $Q_{i+1}$
to verify that their view of the PoS chain is correct.

To update the configuration from $C_{i}$ to $C_{i+1}$, a transaction from
$Q_{i}$ to $Q_{i+1}$ must be included in the Bitcoin blockchain (steps 3 and 4
in Figure 4). Leveraging the recent Bitcoin Taproot upgrade (that allows for
Schnorr signatures), the transaction needs to be signed by $t_{i}$
participants from configuration $C_{i}$ where $t_{i}$ is chosen to be strictly
more than $f|C_{i}|$ as this ensures that at least one honest participant
signs, preventing an adversary from signing an illegitimate transaction. As
discussed previously, we will use the FROST algorithm for signing. Note that,
the DKG requires that $t_{i}>0.5|C_{i}|$ to ensure security so our final
constraint on $t_{i}$ is $t_{i}>\max(0.5|C_{i}|,f|C_{i}|)$. Since we assume
that online validators can distinguish a LRA chain, it is enough to have the
transaction signed by $t_{i}$ participants as no honest validators can be
fooled into signing an illegitimate transaction. If forks were allowed even in
the case of perpetually honest validators (i.e., outside of LRA forks), this
would be more problematic, as two conflicting transactions could then be
signed, and we would require at least two thirds of the participants to sign
the transaction, for $f=1/3$ (as previously mentioned, this can also be fixed
by considering a block in the past, i.e., one that has been finalized).

In addition to the transfer of coins from $Q_{i}$ to $Q_{i+1}$, the
transaction spent by configuration $C_{i}$ will have a second output that does
not receive any bitcoins and that is unspendable, but that contains an
identifier $cid$ used to retrieve the full details of the configuration. This
is done using the $OP\\_{RETURN}$ opcode of Bitcoin (opreturn, ) that allows
storing of extra information in the chain, which we use to store $cid$. This
identifier will be useful in the case where a user does not have access to the
right PoS chain (i.e., does not have the correct value for $pk_{i+1}$ and ckpt
due to a LRA). In this case, the content identifier $cid$ can be used,
together with a content-addressable decentralized storage, for example IPFS
(ipfs, ) or Filecoin (filecoin, ) (or a content-addressable storage
implemented on the PoS network validators) to retrieve the identities of the
nodes in the correct configuration. The transaction updating the configuration
will look as follows:

$\textsf{tx}_{i}:Q_{i}\rightarrow((\textsf{amount},Q_{i+1}),(0,OP\\_{RETURN}=cid_{i+1}))$

meaning that amount is transferred to $Q_{i+1}$ and 0 is transferred to
$OP\\_{RETURN}=cid_{i+1}$ (unspendable output). This information is then
publicly available. We discuss in Section 4.3 how any user can then use it to
get the latest PoS configuration.

We add the following assumption (assumption 3): we assume that
$\textsf{tx}_{i}$ is finalized in the Bitcoin blockchain before the
configuration $C_{i+L}$ is formed, where $L\gg 1$ is the parameter defined in
assumption 1 (Section 3).

The high-level description of the protocol is presented in Figure 4 and the
pseudocode in Algorithm 1. The pseudocode for our DKG and signing subroutines
are presented in Algorithms 2 and 3. In all our pseudocode, the notation
$\langle msg\rangle_{i}$ means that message $msg$ was sent by participant $i$
and we use PM($\langle msg\rangle,i$) to denote that a private message $msg$
was sent to participant $i$.

We make the following remarks about our protocol. First, in steps 3b and 5 we
ask that every participant $P_{j}$ in configuration $C_{i}$ publishes the
configuration state to the decentralized storage provider and sends the signed
transaction $\textsf{tx}_{i}$ to the Bitcoin network. We do so out of caution.
In practice only one validator needs to do so, but this validator could be
controlled by the adversary and abort instead.

Second, in step 4 of the protocol, we remark that the final signature on the
transaction, $z^{\prime}$, is “tweaked” using

$H(\textsf{tx}_{i}||R||Q_{i})H_{TapTweak}(pk_{i}||\textsf{ckpt}).$

This is because because the signature computed as part of the FROST signing
algorithm will verify against the key $pk_{i}$, computed during the DKG but
not $Q_{i}=pk_{i}+H_{TapTweak}(pk_{i}||\textsf{ckpt})$. For the signature to
be valid on the taproot output, the signature must verify against the tweaked
key $Q_{i}$. Because Schnorr is additive, it is enough to add the term
$H(\textsf{tx}_{i}||R||Q_{i})H_{TapTweak}(pk_{i}||\textsf{ckpt})$ to the
signature. Indeed one can verify that if
$zG=R+H(\textsf{tx}_{i}||R||Q_{i})pk_{i}$ then

$\displaystyle z^{\prime}G$
$\displaystyle=zG+H(\textsf{tx}_{i}||R||Q_{i})H_{TapTweak}(pk_{i}||\textsf{ckpt})G$
$\displaystyle=R+H(\textsf{tx}_{i}||R||Q_{i})pk_{i}+H(\textsf{tx}_{i}||R||Q_{i})H_{TapTweak}(pk_{i}||\textsf{ckpt})G$
$\displaystyle=R+H(\textsf{tx}_{i}||R||Q_{i})(pk_{i}+H_{TapTweak}(pk_{i}||\textsf{ckpt})G)$
$\displaystyle=R+H(\textsf{tx}_{i}||R||Q_{i})Q_{i}$

We assume that the initial aggregated public key of participants (at genesis)
$pk_{0}$ as well as their tweaked key $Q_{0}$ are trusted and known by
everyone and that it was funded as specified in Section 4.2 such that there
are enough bitcoins to pay for the transaction fees of several transactions.
For each round $i>0$: 1 The protocol starts after a threshold of new
registrations and unregistrations has been monitored (e.g., since the last
configuration, $i$, there has been $u$ new registrations or unregistrations).
We call this event $U_{i+1}$. We note $X_{i+1}$ the height, in the PoS
blockchain, corresponding to this event. As soon as the parties notice event
$U_{i+1}$, they start the distributed key generation algorithm defined in
Figure 5. This algorithm is performed by members of the new configuration,
$C_{i+1}$ in order to compute the new aggregated key $pk_{i+1}$. We denote
$S_{i+1,0}$ the set of members in the new reconfiguration (i.e.,
reconfiguration $i$). (Every member knows who is part of the new configuration
by property of the underlying PoS, using the power table). At the end of the
algorithm, the aggregated public key $pk_{i+1}$ is known by everyone and a
message can be signed by $t_{i+1}$ out of $n_{i+1}$ of the participants using
their secret share $s_{i+1,j}$: $(s_{i+1,1},\cdots,s_{i+1,n})\ext@arrow
9999{\arrowfill@\leftarrow\relbar\rightarrow}{}{(t_{i+1},n_{i+1})}(sk_{i+1},pk_{i+1},a_{i+1k}G,S_{i+1,1}),\
k\in\\{1,\cdots,t_{i+1}-1\\}$. Here
$S_{i+1,1}=S_{i+1,0}\setminus\\{\text{misbehaving participants from the
protocol}\\}.$ We assume that the DKG is finished by block $X_{i+1}+Y$ where
$Y$ is chosen conservatively. The tweaked public key of the taproot address is
then defined to be $Q_{i+1}=pk_{i+1}+H_{TapTweak}(pk_{i+1}||\textsf{ckpt})G$,
where ckpt is the hash of the PoS block at height $X_{i+1}$. 2 Optional:
Remove the misbehaving party from the power table. 3 Signing protocol. Every
participant $P_{j}$ of configuration $C_{i}$ does the following: (a) $P_{j}$
checks that the previous reconfiguration transaction $\textsf{tx}_{i-1}$
(according to the PoS blockchain) is included in the bitcoin blockchain. If
not, they submit it before forming the new transaction. (b) $P_{j}$ first
publishes the list of members in the new configuration $C_{i+1}$ to the
decentralized storage and retrieves the corresponding content identifiers
$cid_{i+1}$. (c) $P_{j}$ computes transaction $\textsf{tx}_{i}$ as follows.
All of the coins associated with $Q_{i}$ are transferred to $Q_{i+1}$ and
another output that receives no coins but contains an $OP\\_{RETURN}$ that
contains $cid_{i+1}$ is added:
$\textsf{tx}_{i}:Q_{i}\rightarrow((\textsf{amt},Q_{i+1}),(0,OP\\_{RETURN}=cid_{i+1}))$
where amount is the amount associated with $Q_{i}$ minus transaction fees. (d)
The members of the current configuration $C_{i}$ (i.e. associated with
$pk_{i}$) perform the interactive signing algorithm. (i) Set $m\leftarrow 0$.
(ii)
$(o,S_{i,m+1})\leftarrow\textsf{SchnorrThresholdSign}(S_{i,m},\textsf{tx}_{i},pk_{i},Q_{i})$
defined in Figure 6 where $S_{i,m+1}$ is the set of non-misbehaving parties
during the execution of the protocol. (iii) If $o=(z,R)$, i.e., a signature
has been successfully produced, continue to step 4. (iv) Else (i.e.,
$o=\textsf{abort}$) set $m=m+1$ and go to step 3(d)ii. 4 The taproot signature
is then computed as
$(z^{\prime},R)\leftarrow(z+H(\textsf{tx}_{i}||R||Q_{i})H(pk_{i}||\textsf{ckpt}),R)$,
where $c$ is the hash of the PoS blockchain at height $X_{i}$. 5 $P_{j}$ sends
$\textsf{tx}_{i}$ to the Bitcoin blockchain to update the configuration. 6
Participants set $i\leftarrow i+1$ and go back to step 1.

Figure 4. Main Algorithm

Each participant $P_{i}$ performs the following steps, where $t$ is a
parameter and $n$ is the total number of participants: (1) Choose
$r_{i}\xleftarrow{\$}\mathbb{Z}_{q}^{*}$. Let the sharing polynomial be
$f_{i}(u)=\sum_{k=0}^{t-1}a_{ik}u^{k}$ where $a_{i0}=r_{i}$. Compute
$s_{i}^{j}=f_{i}(j)\mod q$ for each $j\in\\{1,\dots n\\}$ and send $s_{i}^{j}$
privately to $P_{j}$. (2) Expose $Y_{i}=r_{i}G$ as follows. Broadcast
$A_{ik}=a_{ik}G$ for $k\in\\{0,\cdots,t-1\\}$. (3) Verify the values broadcast
by other players:
$f_{j}(i)G\stackrel{{\scriptstyle?}}{{=}}\sum_{k=0}^{t-1}i^{k}A_{jk}$. If the
check fails for an index $j$, complain against $P_{j}$. (4) Answer each
complaint from party $P_{j}$ against $P_{i}$ (if any) by broadcasting
$s_{i}^{j}$. (5) If any of the revealed shares fails this equation, remove
that participant from the set of players $H_{0}$. (6) Extract $Y=\sum_{j\in
S_{0}}r_{j}G$, of which each player’s share of the secret is $s_{i}=\sum_{j\in
S_{0}}s_{j}^{i}$. The secret $r=\sum_{j\in S_{0}}r_{j}\mod q$ is never
computed. The corresponding aggregated private and public keys are $(r,Y)$,
denoted by $(s_{1},\cdots,s_{n})\ext@arrow
9999{\arrowfill@\leftarrow\relbar\rightarrow}{}{(t,n)}(r,Y,a_{k}G,S_{0}),\
k\in\\{1,\cdots,t-1\\}$

Figure 5. Distributed Key Generation Algorithm (JF-DKG by Gennaro et al.
(gennaro2007secure, ))

###  4.2. Initialization and funding

The initial key $Q_{0}$ is created by having the first configuration run the
DKG, and tweak it with a hash of the genesis block of the PoS chain. In order
to fund the initial transaction, we want each participant in $C_{0}$ to send a
small amount of bitcoins to $Q_{0}$. However it is not possible to enforce
this. A participant that does not contribute to the fee would still hold a
share of the secret key associated with $Q_{0}$. Indeed $Q_{0}$ must be
determined before the participants send their transactions, otherwise they do
not know where to send their funds. But once $Q_{0}$ is computed everyone who
participated in the DKG knows a share of the secret regardless of whether they
send some funds to it. We thus need to make sure that participants are
incentivized to contribute to the fees. One way to do so is to have each
participant who sent some funds to $Q_{0}$ in the Bitcoin blockchain be
rewarded, in exchange, with some PoS coins. Verifying the validity of Bitcoin
transactions is, however, not trivial. Verifying the signature only is not
enough as the transaction could be double spending. Hence, additional data is
required by a verifier. More specifically, a verifier would need to verify
that the transaction is included in the Bitcoin blockchain at least $k$ blocks
deep - where $k$ is a parameter corresponding to Bitcoin’s settlement time.
With this in mind, we propose the following protocol.

We consider the following parameters: a deadline $h_{0}$ (represented as a
height in the Bitcoin blockchain); the settlement time $k$ after which a block
is considered ”finalized” in the Bitcoin blockchain (e.g. 6 blocks); release
expressed as a height in the Bitcoin blockchain chain, chosen conservatively
high.

  1. (1)

Each participant $P_{i}$ in $C_{0}$ submit a commitment to their Bitcoin
public key $btc.pk_{i}$ (e.g. a hash $H_{1}(btc.pk_{i})$) to the PoS chain.
This is to prevent participants from later on ”stealing” each other rewards by
pretending to have sent some bitcoins that someone else sent.

  2. (2)

Configuration $C_{0}$ interactively performs the DKG to create the key
$pk_{0}$. Each participant in $C_{0}$ holds a share of the secret key
associated. The key is then tweaked with a commitment to the PoS genesis block
to give $Q_{0}$.

  3. (3)

Each participant $P_{i}$ in $C_{0}$ send a small amout fee from $btc.pk_{i}$
to $Q_{0}$. This transaction should be sent several heights before height
$h_{0}$. They add a timelock (timelock, ) such that if the output is not spent
after release blocks, $P_{i}$ gains control of their bitcoins back. We denote
this transaction $init.tx_{i}$.

  4. (4)

Once the Bitcoin chain has reached height at least $h_{0}+k$ the participants
can start the interactive signing. They create the transaction by spending all
the UTXOs that were received by $Q_{0}$ before block $h_{0}$ (this ensures
that everyone will sign the same transaction). We note $\textsf{tx}_{0}$ this
transaction. Every transaction $init.tx_{i}$ not included in the initial
transaction $\textsf{tx}_{0}$ (e.g. because it was included too late in the
bitcoin blockchain) can be sent back to its original sender due to the
timelock.

  5. (5)

If $init.tx_{i}$ was included in the inputs of $\textsf{tx}_{0}$, $P_{i}$ can
submit evidence of this in the Filecoin chain using $\textsf{tx}_{0}$ (i.e.
everyone can verify that $init.tx_{i}$ is in the list of input of
$\textsf{tx}_{0}$ and that the signature is correct). Since no adversary can
forge a signature from $Q_{0}$, due to the security of the threshold signing
scheme, no proof can be forged for $init.tx_{i}$ inclusion in
$\textsf{tx}_{0}$.

  6. (6)

If $init.tx_{i}$ was not included in the inputs of $\textsf{tx}_{0}$, then
$P_{i}$ does not get any reward.

  7. (7)

Every PoS miner verifies that $init.tx_{i}$ was indeed included in
$\textsf{tx}_{0}$ (as described above), then verifies that $btc.pk_{i}$ indeed
belongs to $P_{i}$. If both checks pass, $P_{i}$ is awarded an amount of PoS
coins proportional to the amount sent by $init.tx_{i}$. This amount should be
high enough to not only compensate the fee paid by $P_{i}$ but also
incentivized them to sent the fee (i.e., the reward must be higher than the
fee, although it is not trivial to compare the value of two cryptocurrencies,
these values can be chosen conservatively). The reward can be taken from the
coins minted, as is usually the case in crypto-currencies reward scheme.

For every checkpointing transaction on the Bitcoin blockchain, we use a
constant fee btc.fee chosen high enough to tolerate potential congestion
period in the Bitcoin blockchain. As a reminder, thanks to the Taproot update,
the size of the transaction in our protocol is constant in the number of
participant hence choosing a constant transaction fee is enough for our
purpose, although we may end up over-paying during non-congested periods. We
also remark that our protocol is assumed to be run at a relatively low pace
(e.g., once a day) hence we can tolerate longer delays in having the
checkpointing transaction included in the Bitcoin chain in periods of short-
term congestion. For reference , as of May 2022, the cost of a checkpointing
transaction on Bitcoin mainnet would be around $0.07 (around 200 sats).

When the funds from the initial transaction run out, a protocol as the one
described above can be used to refill them.

###  4.3. Verification

Once the protocol described in Figure 4 has been run by the participants,
users of the PoS system who went offline for an extended period of time can
use the Bitcoin blockchain to determine the correct configuration and state of
the chain. Informally, the verification protocol works as follows: users, who
are aware of the initial aggregated public key $Q_{0}$, which serves as an
identifier of the PoS blockchain on the Bitcoin blockchain, can follow the
chain of transactions from $Q_{0}$ to the newest public key $Q_{i}$. The
latest transaction in the chain (i.e., from $Q_{i-1}$ to $Q_{i}$) contains an
additional output that corresponds to the content identifier of the
configuration $C_{i}$. The user can then use this identifier to retrieve the
configuration using IPFS (or another content-addressable decentralized
storage, e.g., one implemented on top of the PoS chain). The high-level
protocol is described below and the pseudocode is given in Algorithm 4.

  1. (1)

Synchronize with the Bitcoin blockchain (e.g., by running a Bitcoin full
node.222Bitcoin full nodes can be run on relatively cheap hardware, e.g.,
Raspberry Pi and 1TB disk, in a setup that costs less than $200 USD.)

  2. (2)

Look for $Q_{0}$ and follow the chain of transactions to get $\textsf{tx}_{i}$
and $cid_{i}$, i.e.,

    1. (a)

Inspect the transactions going out from $Q_{0}$

    2. (b)

If there are multiple transactions going out from $Q_{0}$, look for the
initial funding transaction by inspecting the UTXOs spent and verifying that
all of them are included in blocks with height lower than $h_{0}$.

    3. (c)

Once the initial transaction $\textsf{tx}_{0}$ has been found, look for the
transaction that spent $\textsf{tx}_{0}$ (i.e. where $\textsf{tx}_{0}$ is an
input).

    4. (d)

For $i\geq 0$ get $\textsf{tx}_{i+1}$ by looking for the transaction that
spent $\textsf{tx}_{i}$.

    5. (e)

Stop when $\textsf{tx}_{i}$ is unspent and get $cid_{i}$ from the
$OP\\_{RETURN}$ field.

  3. (3)

Use $cid_{i}$ to get the list of current nodes from the external storage
chosen.

  4. (4)

Request the PoS blockchain state from these nodes.

  5. (5)

Verify that the aggregated public key on the PoS blockchain $pk$ and the hash
of the block ckpt are in accordance with the Bitcoin Taproot address $Q$ that
is the output of $\textsf{tx}_{i}$.

  6. (6)

If the checkpoint and aggregated key do not match the Bitcoin checkpoint, roll
back the PoS chain until the previous checkpoint and go back to step 5.

$\textsf{SchnorrThresholdSign}(H,m,Y,Q)$ Input: $H$ is the set of players, $m$
the message.
Y is the aggregated public key. Each participant $P_{i}$ holds a share of the
associated secret key $s_{i}$. $Y_{i}$ is the public verification share of
each participant and is computed as $Y_{i}=\sum_{j\in
S_{0}}\sum_{k=0}^{t-1}i^{k}A_{jk}$ We note $Q$ the tweaked key as defined in
step 1 of Figure 4.
Parameter: timeOut.
PreProcess: Each participant $P_{i}$ performs the following steps. $\pi$ is a
parameter corresponding to the number of signing operations that can be
performed before doing another pre-process step. (1) Create an empty list
$L_{i}$. For $1\leq j\leq\pi$ do: (a) Sample single-use nonces
$(d_{ij},e_{ij})\xleftarrow{\$}\mathbb{Z}_{q}^{*}\times\mathbb{Z}_{q}^{*}$.
(b) Derive commitment shares $(D_{ij},E_{ij})=({d_{ij}G},{e_{ij}}G)$. (c)
Append $(D_{ij},E_{ij})$ to $L_{i}$. Store $((d_{ij},D_{ij}),(e_{ij},E_{ij}))$
for later use in signing operations. (2) Publish $(i,L_{i})$ to the PoS
blockchain. $\textbf{Sign}(m)$ Each participant $P_{i}$ does the following:
(1) Compute S, the set of $t$ participants for signing using $\text{RB}_{i}$
as follows: (a) Compute $H(id||\text{RB})$. (b) The smallest $t$ hashes are
the id selected for signing. (2) Fetch the next available commitment for each
participant $P_{i}\in S$ from $L_{i}$ and construct
$B=\langle(i,D_{i},E_{i})\rangle_{i\in S}$.  (3) Compute the set of binding
values $\rho_{l}=H_{1}(l,m,B),l\in S$ and derives the group commitment
$R=\sum_{l\in S}(D_{l}+{\rho_{l}}E_{l})$ and the challenge $c=H_{2}(m||R||Q)$.
(4) Each $P_{i}\in S$ computes their response using their secret share $s_{i}$
by computing $z_{i}=d_{i}+(e_{i}\cdot\rho_{i})+\lambda_{i}\cdot s_{i}\cdot c$
using $S$ to determine the $i^{th}$ Lagrange coefficient $\lambda_{i}$ as
follows: if $S=\\{P_{i_{1}}\cdots,P_{i_{t}}\\}$ represents the participants
identifiers then $\lambda_{i}=\prod_{j\in\\{i_{1},\dots,i_{t}\\},j\neq
i}\frac{P_{j}}{P_{j}-P_{i}}$. (5) Each $P_{i}$ securely deletes
$(d_{i},e_{i})$ from their local storage and then post $z_{i}$ to the PoS
chain. (6) After all the shares from participants in S are included in the PoS
chain, each participant performs the following steps: (a) Derive $R=\sum_{i\in
S}R_{i}$ and $c=H_{2}(m||R||Q)$. (b) Verify that
${z_{i}}G\stackrel{{\scriptstyle?}}{{=}}R_{i}+({c\cdot\lambda_{i}})\cdot
Y_{i}$ for each signing share $z_{i},i\in S$. If it fails, report the
misbehaving participant(s) by publishing a message on the PoS blockchain with
the proof of misbehaviour(s) (i.e., ${z_{i}}G$ and
$R_{i}+({c\cdot\lambda_{i}})Y_{i}$ for each cheating player) and abort. (c) If
no participants was misbehaving, compute $z=\sum_{i\in S}z_{i}$. (d) Compute
$\sigma=(z,R)$ to the PoS blockchain. (7) If after timeOut blocks since the
begining of the protocol, some shares have not been posted to the PoS chain,
abort the protocol and add the corresponding participants in the list of
misbehaving players. Output: $(\sigma,H)$ if the protocol completed,
$(\textsf{abort},S^{\prime})$ else, where $S^{\prime}$ is the set of players
who have not misbehaved during the execution of the protocol.

Figure 6. Signing Algorithm

1:import PoS

2:import PoS.PowerTable as PT

3:import BTC

4:import PrivateMessage as PM

5:import IPFS

6:import Signing Algorithm (Algorithm 3), Distributed Key Generation Algorithm
(Algorithm 2)

7:Parameters:

8: $id$ $\triangleright$ The node id

9: $u$ $\triangleright$ Tolerated difference between local configuration and
current configuration

10: f $\triangleright$ Fault tolerance of the current configuration

11: $Y$ $\triangleright$ Number of blocks to wait for the DKG to complete

12:Init:

13: $C_{cur}\leftarrow C_{0}$ $\triangleright$ Current configuration

14: $C_{last}\leftarrow C_{0}$ $\triangleright$ Last configuration

15: $pk_{cur}\leftarrow pk_{0}$ $\triangleright$ Initial public key

16: CurrentShares $\leftarrow$ empty dictionary $\triangleright$ Share of the
aggregated public key

17: $S_{0}\leftarrow C_{cur}$ $\triangleright$ Non-misbehaving participants

18: $\text{misbehavingPlayers}\leftarrow\emptyset$$\triangleright$ Set of
misbehaving participants in the DKG

19: $i\leftarrow C_{cur}.members[id].getIndex()$ $\triangleright$ Node’s index

20: $\textsf{tx}_{last}\leftarrow\textsf{tx}_{0}$ $\triangleright$ Initial
transaction as defined in Section 4.2

21:upon event receiving $PT.\text{update}(req)\wedge C_{last}\triangle
C_{cur}<u$ do$\triangleright$ Configuration request received

22: if $req=\langle p,``join"\rangle$ then

23: $C_{cur}.members\leftarrow C_{cur}.members\cup\\{p\\}$

24: if $req=\langle p,``leave"\rangle$ then

25: $C_{cur}.members\leftarrow C_{cur}.members\setminus\\{p\\}$

26:upon event $C_{last}\triangle C_{cur}\geq u$ $\triangleright$ After $u$
(un)registrations do

27: $X\leftarrow$ PoS.CurrentBlock()

28: Do Algorithm 2 (DKG)

29:upon event PoS.CurrentHeight == PoS.Height(X)+Y do$\triangleright$ Give
enough time for the DKG to complete

30: $S_{0}\leftarrow C_{cur}.getIndexes()\setminus$misbehavingPlayers
$\triangleright$ set of indexes of non-cheating players in the DKG

31: $pk_{new}\leftarrow\sum_{j\in S_{0}}\text{CurrentShares}[j]$
$\triangleright$ Compute the aggregated key

32: $s_{i}\leftarrow\sum_{j\in S_{0}}s_{j}^{i}$ $\triangleright$ Compute the
share of the secret key

33: $\textsf{ckpt}\leftarrow PoS.Blockhash(X)$

34: $q\leftarrow pk_{new}+H_{TapTweak}(pk_{new}||\textsf{ckpt})G$
$\triangleright$ Taproot address

35: $o\leftarrow 0$ $\triangleright$ Counter for the pre-process step

36: if BTC.latestCheckpoint.UTXO $\neq\textsf{tx}_{last}$ then
$\triangleright$ Check the Bitcoin blockchain for the previous checkpointing
transaction

37: BTC.Broadcast($\textsf{tx}_{last}$) $\triangleright$ Send latest
checkpoint

38: IPFS.push($C_{cur}$)

39: $cid\leftarrow IPFS.getCid(C_{cur})$

40: if $id\in C_{last}$ then $\triangleright$ Members associated with
$pk_{cur}$ sign tx

41: do Algorithm 3$\triangleright$ Signing protocol with other members

42: $C_{last}\leftarrow C_{cur}$

43: $pk_{cur}\leftarrow q$

44: CurrentShares $\leftarrow\emptyset$

Algorithm 1 Main algorithm

1:import MainAlgorithm

2:Parameters:

3: $t\leftarrow 0.5|C_{cur}|+1$ $\triangleright$ Number of parties controlled
by the adversary

4:if $id\in C_{cur}$ then $\triangleright$ Only member of the new
configuration perform the DKG

5: Timeout.Start() $\triangleright$ We use a timeout to detect aborting
players (this can be in terms of blocks in the PoS chain)

6: $r_{i}\xleftarrow{\$}\mathbb{Z}_{q}$ ; $a_{i0}\leftarrow r_{i}$

7: for $k\in\\{1,\dots,t-1\\}$ do

8: $a_{ik}\xleftarrow{\$}\mathbb{Z}_{q}$

9: $f_{i}(u)\leftarrow\sum_{k=0}^{t-1}a_{ik}u^{k}$

10: for $j\in\\{1,\dots,|C_{cur}.members|\\}$ do

11:
PM($\langle\text{SHARE},s^{j}_{i}=f_{i}(j)\rangle,C_{cur}.members.index[j]$)
$\triangleright$ Send share of secret to each player

12:if id$\in C_{cur}$ then

13: for $k\in\\{0,\dots,t-1\\}$ do $A_{ik}\leftarrow a_{ik}G$

14:
PoS.Broadcast($\langle\text{secretCommitments},A_{i0},\dots,A_{i(t-1)}\rangle_{i}$)

15:upon event $\langle\text{SHARE},s_{j}^{i}\rangle_{j}$ received for all $j$
do

16: Timeout.Restart() $\triangleright$ All secret shares were received

17:upon event TimeOut.Done() do

18: for $j\in\\{1,\dots,|C_{cur}.members|\\}$ do

19: if ($\langle\text{SHARE},s_{j}^{i}\rangle)_{j}$== nil then$\triangleright$
Some party did not send their private share

20: misbehavingPlayers.append$(j)$ $\triangleright$ Add aborting players to
list of misbehaving participants

21: Timeout.Restart()

22:upon event
PoS.Receive($\langle\text{secretCommitments},A_{j0},\dots,A_{j(t-1)}\rangle_{j}$)
do

23: if $j\in\\{1,\dots,|C_{cur}.members|\\}$ and
$s^{j}_{i}\neq\sum_{k=0}^{t-1}i^{k}A_{jk}$ then

24: misbehavingPlayers.append($j$)

25: else

26: CurrentShares.append($j,A_{j0}$)

27:upon event
PoS.Receive($\langle\text{secretCommitments},A_{j0},\dots,A_{j(t-1)}\rangle_{j}$)
for all $j$ or Timeout.Done() do$\triangleright$ All commitments were received
or timeout expired

28: if PoS.Read($\langle\text{secretCommitments}\rangle)_{j}$== nil then

29: misbehavingPlayers.append$(j)$ $\triangleright$ Add aborting players to
list of misbehaving participants

30: v = $\emptyset$

31: for $j\in\\{1,\dots,|C_{cur}.members|$ do

32: if $j\in\text{misbehavingPlayers}$ then v.append($f_{j}(i)$)

33: else v.append(NoComplaint)

34: PoS.Broadcast($\langle$complaintSecret, v$\rangle$) $\triangleright$ Send
a list of (potentially empty) complaints

35: Timeout.Restart()

36:upon event PoS.Receive($\langle$complaintSecret,v $\rangle_{k}$) do

37: for $j\in\\{1,\dots,|C_{cur}.members|$ do $\triangleright$ Receive other
parties’ list of complaints

38: if v[j]$\neq$ NoComplaint then
misbehavingPlayers.append$(j)$$\triangleright$ Add complaints against $j$

39: if v[i]$\neq$ NoComplaint then
PoS.Broadcast($\langle\text{complaintAnswer},s^{i}_{j},i\rangle$)
$\triangleright$ Reply to complaint against self

40:upon event PoS.Receive($\langle$complaintAnswer, proof, $j\rangle_{l}$) do
$\triangleright$ $j$ can answer a complaint from $l$

41: $s^{j}_{l}\leftarrow$Parse(proof)

42: $(A_{jk})_{k=0}^{t-1}\leftarrow
PoS.Read(\langle\text{SecretCommitments}\rangle_{j})$ $\triangleright$ Get $j$
commitments

43: if $s^{j}_{l}G==\sum_{k=0}^{t-1}l^{k}A_{jk}$ then

44: misbehavingPlayers.remove$(j)$

45:upon event PoS.Receive($\langle\text{complaintSecret}\rangle_{j}$) for all
$j\wedge$ misbehavingPlayers == $\emptyset$ do$\triangleright$ All complaints
(and potentially answers) were received

46: return $\triangleright$ Finish the protocol

47:upon event Timeout.Done() do $\triangleright$ Leave enough time for answers
to be received

48: return

Algorithm 2 Distributed Key Generation

1:import MainAlgorithm

2:Parameters: $\pi$ $\triangleright$ Number of pre-process steps

3:Timeout.start()

4:$L_{i}\leftarrow\emptyset$

5:$v\leftarrow$ PoS.Height(X)

6:$RB\leftarrow RB_{v}$

7:for $j\in\\{0,\dots,\pi\\}$ do

8: $(d_{ij},e_{ij})\xleftarrow{\$}\mathbb{Z}_{q}^{*}\times\mathbb{Z}_{q}^{*}$

9: $(D_{ij},E_{ij})=({d_{ij}}G,{e_{ij}}G)$

10: $L_{i}.append(D_{ij},E_{ij})$

11:PoS.Broadcast($\langle\text{PreProcess, }i,L_{i}\rangle$)

12:$B\leftarrow\emptyset$

13:$S^{\prime}\leftarrow\emptyset$

14:for $i\in C_{last}$ do

15: $S^{\prime}\leftarrow S^{\prime}\cup(H(RB||i.ID))$ $\triangleright$
Pseudo-randomly choose set of signers

16:$S^{\prime}\leftarrow order(S^{\prime})$

17:$S\leftarrow S^{\prime}[:f|C_{last}|+1]$ $\triangleright$ Choose t+1
participants for signing

18:for $k\in S$ do

19:
$(D_{ko},E_{ko})\leftarrow$PoS.Read($\langle\text{PreProcess},k,L_{k}[o]\rangle)$

20: $B.append((k,D_{ko},E_{ko}))$

21:for $l\in S$ do

22: $\textsf{tx}\leftarrow
BTC.TX(pk_{cur}\rightarrow(all,q),(0,OP_{RETURN}=cid))$ $\triangleright$
Compute the transaction

23: $\rho_{l}\leftarrow H_{1}(l,\textsf{tx},B)$ for $l\in S$

24: $\lambda_{i}\leftarrow\prod_{j\in S,j\neq i}\frac{p_{j}}{p_{j}-p_{i}}$
where $p_{j}$ is the identifier of participant $j$

25: $R\leftarrow\sum_{l\in S}D_{lo}+{\rho_{l}}E_{lo}$, $c\leftarrow
H_{2}(\textsf{tx}||R||q)$

26: $z_{i}\leftarrow d_{io}+(e_{io}\cdot\rho_{i})+\lambda_{i}\cdot s_{i}\cdot
c$

27: delete $((d_{io},D_{io}),(e_{io},E_{io}))$ from local storage

28: PoS.Broadcast($\langle\text{SHARE},z_{i}\rangle$)

29:if $id\in S$ then

30: upon event PoS.Receive($\langle\text{SHARE},z_{k}\rangle$) from all $k\in
S$ do$\triangleright$ All shares were received

31: CheatingPlayers$\leftarrow\emptyset$

32: for $k\in S$ do

33: $Y_{k}=\sum_{j\in S_{0}}\sum_{w=0}^{t-1}k^{w}A_{jw}$

34: $\rho_{k}\leftarrow H_{1}(k,\textsf{tx},B)$, $R_{k}\leftarrow
D_{ko}+{\rho_{k}}E_{ko}$, $R\leftarrow\sum_{k\in S}R_{k}$, $c\leftarrow
H_{2}(\textsf{tx}||R||q)$

35: if $g^{z_{k}}\neq R_{k}+{c\cdot\lambda_{k}}\cdot Y_{k}$ then

36: CheatingPlayers.append($k$)

37: if CheatingPlayers$\neq\emptyset$ then

38: PoS.Broadcast($\langle\text{RESTART SIGNING, CheatingPlayers}\rangle$)

39: restofplayers $\leftarrow C_{cur}.getIndexes()\setminus S$

40: $S\leftarrow S\setminus$CheatingPlayers

41: S.append(restofplayers[:$|\text{CheatingPlayers}|$]) $\triangleright$ add
as many players as were removed

42: $o\leftarrow o+1$

43: Timeout.Restart()

44: go to line 18

45: else

46: $z\leftarrow\sum_{i\in S}z_{i}$

47: $c\leftarrow PoS.Blockhash(X)$ $\triangleright$ Commitment to the
blockchain

48: $\sigma^{\prime}\leftarrow\sigma+H(\textsf{tx}||R||q)H(pk_{cur}||c)$
$\triangleright$ compute taproot signature

49: BTC.Broadcast(tx, $\sigma^{\prime}$)

50: PoS.Broadcast(tx,$\sigma^{\prime}$)

51: return

52: upon event Timeout.done() do$\triangleright$ We implement a timeout to
deal with aborting participants

53: for $p\in S$ do

54: if PoS.Read$(\langle\text{SHARE}\rangle_{p})==nil$ then$\triangleright$ p
hasn’t submitted its share

55: CheatingPlayers.append(p)

56: else

57: $\rho_{k}\leftarrow H_{1}(k,m,B)$, $R_{k}\leftarrow
D_{kj}+{\rho_{k}}E_{kj}$, $R\leftarrow\sum_{k\in S}R_{k}$, $c\leftarrow
H_{2}(\textsf{tx}||R||q)$

58: if $g^{z_{k}}\neq R_{k}+{c\cdot\lambda_{k}}\cdot Y_{k}$ then

59: CheatingPlayers.append(p)

60: PoS.Broadcast($\langle\text{RESTART SIGNING, CheatingPlayers}\rangle$)

61: restofplayers $\leftarrow C_{cur}.getIndexes\setminus S$

62: $S\leftarrow S\setminus$CheatingPlayers

63: S.append(restofplayers[:$|\text{CheatingPlayers}|$]) $\triangleright$ add
as many players as were removed

64: $o\leftarrow o+1$

65: go to line 18

Algorithm 3 Signing algorithm

1:import BTC

2:import IPFS

3:import PoS

4:Parameters: $pk_{0}$ $\triangleright$ Initial public key

5:$\textsf{tx}_{0}\leftarrow$ BTC.output($pk_{0}$) $\triangleright$ In the
case of multiple transactions spent by $pk_{0}$, choose the first one

6:$i\leftarrow 0$

7:while output is unspent do

8: output$\leftarrow$BTC.getOutput($\textsf{tx}_{i}$) $\triangleright$ Get
chain of transactions

9: $i\leftarrow i+1$

10:cid $\leftarrow$ output.$OP_{RETURN}$

11:$Q\leftarrow$ output.TaprootAddress

12:$members\leftarrow$ IPFS.getData(cid) $\triangleright$ Get the
configuration from IPFS

13:for m in $members$ do

14: PoS$\leftarrow$query(m,PoS) $\triangleright$ get the latest PoS state from
the current members

15:$c\leftarrow$ PoS.getLatetsCheckpoint $\triangleright$ verify checkpoint

16:$pk\leftarrow$ PoS.getLatestAggregatedKey

17:if $Q==pk+H_{Taproot}(pk||c)G$ then$\triangleright$ Verify that the state
of the database is consistent with the Bitcoin checkpoint

18: return 1

19:else

20: PoS $\leftarrow$ PoS.RemoveBlocks(after c) $\triangleright$ Roll back the
PoS chain to the previous checkpoint

21: $c\leftarrow$PoS.getLatetsCheckpoint

22: $pk\leftarrow$ PoS.getLatestAggregatedKey

23: Go to step 17

Algorithm 4 Verification

##  5\. Security argument

In this section we present the arguments for why our protocol is secure. We
need to prove two things: (1) that any checkpoint pushed onto the Bitcoin
blockchain is _correct_ , i.e., that it corresponds to the valid state of the
PoS (according to honest online validators); (2) that checkpoints will be
pushed regularly. These two properties correspond, loosely, to the safety and
liveness properties of our scheme.

###  5.1. Safety

We consider the following statement, which we prove by induction, for
$k\in\mathbb{N}$: An adversary as defined in Section 3 cannot create any
incorrect checkpointing transaction $\textsf{tx}^{A}_{i}$ for any $0\leq i\leq
k$ such that $\textsf{tx}^{A}_{i}$ will be accepted by an honest verifier that
follows the verification algorithm as defined in Section 4.3. An incorrect
checkpoint transaction is a transaction that contains a commitment to an
incorrect chain (i.e., a chain created as part of a LRA).

##### Base Case

First, we show that the adversary cannot create an alternative initial
transaction $\textsf{tx}_{0}$. At the time where the initial transaction is
created, the adversary controls at most $t_{0}$ participants (assumption 2)
and hence, by security of the DKG and signing algorithms, cannot unilaterally
sign a transaction coming from $Q_{0}$. After $L$ configurations, the
adversary do obtain all the keys from $C_{0}$ and is able to create
transaction coming out from this address, however, this happens after height
$h_{0}$ on the Bitcoin blockchain by assumption 3 and hence any transaction
sent by the adversary from $Q_{0}$ will not be accepted by any verifier
according to our verification algorithm presented in Section 4.3 step 2b.
Hence the adversary cannot create an initial checkpoint transaction that will
be accepted by any verifier.

##### Induction step

Let’s assume that our statement is true for $k-1$, i.e., the adversary cannot
create any incorrect checkpointing transaction up to $k-1$ (i.e.,
$\textsf{tx}^{A}_{0},\dots,\textsf{tx}^{A}_{k-1}$). We show that our statement
is then also true for $k$. It is enough to show that the adversary cannot
create any incorrect checkpointing transaction $\textsf{tx}^{A}_{k}$. Let’s
denote $i$ the current configuration number (i.e., according to online
validators). There are two cases to consider. The first case is the case where
$k<i-L$. Then by assumptions the adversary has all the keys associated with
$Q_{k}$ (assumption 1) and a transaction $\textsf{tx}_{k}$ that spent
$\textsf{tx}_{k-1}$ has already been included in the blockchain (assumption
3). Because $\textsf{tx}_{k-1}$ has already been spent, $\textsf{tx}^{A}_{k}$
cannot include $\textsf{tx}_{k-1}$ in its inputs (as an input can only be
spent once according to Bitcoin’s rules). Moreover by induction assumption
there is no other transaction $\textsf{tx}^{A}_{k-1}$ to be included as an
input to $\textsf{tx}^{A}_{k}$ that the adversary could create that would be
accepted by any verifier. Hence, according to our verification algorithm step
2d $\textsf{tx}^{A}_{k}$ will not be accepted by any verifier.

The second case is the case where $k\geq i-L$. In this scenario, it could be
the case that transaction $\textsf{tx}_{k-1}$ is still unspent. By design the
only spendable outputs of $\textsf{tx}_{k-1}$ is $Q_{k}$. However, according
to assumption 2, the adversary only holds a fraction $f$ of configuration $k$
and hence cannot create a transaction that is spent by $Q_{k}$ and cannot
spent transaction $\textsf{tx}_{k-1}$.

###  5.2. Liveness

The reasons why an adversary cannot stop the signing from going ahead and the
checkpoints from happening are as follows. (1) The robustness of the DKG
ensures that an adversary cannot stop the rest of the players from computing
an aggregated public key. (2) The adversary could delay the signing process by
aborting; however, aborting or misbehaving players will be detected and
excluded from the signing in the next iteration. (3) The assumption about the
stability across configurations ensures that enough honest participants will
be able to perform the signing, i.e., we assume that enough participants from
each configuration will remain available in the system long enough to sign and
give the signer power to the next configuration.

(a) DKG with every participants honest.

(b) Signing with every participants honest.

Figure 7. Execution time of our DKG and Signing Implementation. Each vertical
bar represent the confidence interval of the execution time as seen by each
different node.

##  6\. Implementation and Evaluation

We implement the protocol from Section 4 using the Go Programming Language.
For the underlying PoS chain, we forked the open-source Eudico
framework,333https://github.com/filecoin-project/eudico developed by Protocol
Labs, that provides a delegated Proof-of-stake consensus protocol option. We
used a simplified version of this, where only one PoS miners creates blocks,
as this does not impact our experiments. We used an open-source library
developed by the Taurus group444https://github.com/taurusgroup/multi-party-sig
for the DKG and signing, that we adapted for our needs and used both Bitcoin
regtest and testnet for our experiments. For storing the data associated with
each configuration, we implemented a key-value database, maintained by the PoS
validators on top of the PoS chain.

The code is open source.555https://github.com/filecoin-
project/eudico/tree/B2-bitcoin-checkpointing We run the experiments on a
single virtual machine (32 GB RAM, 8 vCPUs, 640 GB SSD) on Amazon Lightsail
using a Kubernetes deployment.

We implemented the verification process, however we did not include any
metrics in this paper as this was tested only on the Bitcoin Testnet and may
not be representative of the mainnet.

We measure the execution times of the DKG and the signing protocol in Figure
8. We only included the case where everyone cooperates in our graphs as in the
case of failures our protocol relies on a timeout (to detect aborts) hence the
execution time of the protocol with failures is constant and only depends on
the timeout chosen. We included the graphs of the execution time in the event
of failures in the Appendix for reference.While the number of validators in a
PoS protocol varies depending on a particular blockchain system, we show
results with up to 21 validators, which corresponds to the number of
validators in a delegated PoS such as EOSIO (eosio, ), where 21 validators are
elected on a rotating basis to run the consensus protocol. In Figure 8, we
plot the confidence interval of the execution time of the DKG and signing
protocol sampled over all the participating nodes and repeated a dozen times.

We notice in our graph that the signing scales better than the DKG as it
increases from less than 0.1 second with 3 participants to around 0.6 second
with 21 participants whereas the DKG goes up to above 2.5 seconds with 21
participants. This is expected as the signing only requires 2 broadcast
messages per participants (the pre-process and the share of the signature)
whereas the DKG requires private messages between every participants as well
as broadcast messages.

##  7\. Related Work

LRA have long been studied in the field of PoS and other types of
checkpointing have been proposed that either rely on some sort of central
authority (ppcoin, ) or on additional assumptions (azouvi2020winkle, ). Like
the solution from Steinhoff et al. (steinhoff2021bms, ), this paper offers a
fully decentralized solution without additional security assumptions (as in
(azouvi2020winkle, )) other than the ones needed for the security of the
underlying PoS.

Kuznetsov and Tolkih propose an alternative solution to addressing long-range
attacks in BFT/PoS (KuznetsovT20, ), using forward-secure digital signatures.
However, this solution is inapplicable in the rational adversary model, in
which rational nodes might simply not follow the assumptions of forward-secure
digital signatures, retaining their old private keys to mount attacks in the
future.

Babylon (tas2022babylon, ) was proposed concurrently to our work and is a
defense against LRA that is also based on leveraging the security guarantees
provided from Bitcoin’s Proof-of-work. In this work, every PoS miner can post
a checkpointing transaction into the Bitcoin blockchain which then acts as a
timestamping mechanism and thus thwarts LRA. Whenever a block is mined on the
PoS chain, PoS validators can submit a commitment for this block, and this
commitment is included in the Bitcoin PoW chain. In the case of two
conflicting blocks in the PoS chain, the one whose commitment was submitted
first in the Bitcoin chain is chosen by the fork-choice rule. Babylon goes
further and also protects the underlying PoS chain against super-majority and
censorship attacks. Their scheme is more scalable than Pikachu, as it does not
require any additional threshold signing. On the other hand, since the
checkpointing transactions on the Bitcoin blockchain are not linked together,
as is the case in Pikachu, the verification algorithm is much less efficient
as one would need to search exhaustively through all the Bitcoin transactions
to find all the possible PoS checkpoints and ensure that they have the correct
PoS chain.

Lastly, on the topic of Stake-based Threshold Multisignatures, Mithril
(chaidos2021mithril, ) and Dfinity (groth2021non, ) both propose scalable and
efficient schemes that are however not compatible with Bitcoin and could thus
not be used in the context of checkpointing onto Bitcoin.

##  8\. Conclusion

We presented a checkpointing mechanism designed to secure PoS blockchains by
leveraging the security guarantees provided by Bitcoin’s PoW. Our protocol
uses Taproot, allowing for the checkpoints to be constant in the size of PoS
validators and indistinguishable from any other Taproot’s transaction. We
implemented a PoC for our protocol and measured its efficiency. The main issue
of our approach is that it does not scale well. This is especially true if we
consider a flat model where each unit of power corresponds to a different
public key; we could easily end up dealing with tens of thousands of keys,
even when the number of actual participants is much smaller, greatly
increasing the latency of the protocol. Although some techniques such as
sampling (chaidos2021mithril, ) or ad-hoc threshold multi-signature schemes
(gavzi2019proof, ) have been proposed to help scale weighted threshold
signature schemes, those techniques are not currently compatible with
Bitcoin’s spending rules.

Another problem left for future work is that of fully incentivising the
participation in the protocol, which we started doing in Section 4.2.

## Acknowledgments

The authors would like to thank Nicolas Gailly and Rosario Gennaro for very
useful discussions about this paper.

## References

  * [1] S. Azouvi, G. Danezis, and V. Nikolaenko.  Winkle: Foiling long-range attacks in proof-of-stake systems.  In Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, pages 189–201, 2020.
  * [2] M. Bell.  Proof-of-stake bitcoin sidechains.  https://gist.github.com/mappum/da11e37f4e90891642a52621594d03f6, June 2021\.
  * [3] Bitcoin.  Bips/bip-0341.mediawiki at master · bitcoin/bips, Jul 2021.
  * [4] Bitcoin.  Bips/bip-0341.mediawiki at master · bitcoin/bips, Jul 2021.
  * [5] Bitcoin Wiki.  OP_RETURN.  https://en.bitcoin.it/wiki/OP_RETURN, June 2020.
  * [6] Bitcoin Wiki.  Timelock.  https://en.bitcoin.it/wiki/Timelock, June 2020.
  * [7] E. Buchman.  Tendermint: Byzantine fault tolerance in the age of blockchains.  PhD thesis, 2016.
  * [8] P. Chaidos and A. Kiayias.  Mithril: Stake-based threshold multisignatures.  Cryptology ePrint Archive, 2021.
  * [9] E. Deirmentzoglou, G. Papakyriakopoulos, and C. Patsakis.  A survey on long-range attacks for proof of stake protocols.  IEEE Access, 7:28712–28725, 2019.
  * [10] M. Drijvers, K. Edalatnejad, B. Ford, E. Kiltz, J. Loss, G. Neven, and I. Stepanovs.  On the security of two-round multi-signatures.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 1084–1101. IEEE, 2019.
  * [11] Ethereum Foundation.  Proof-of-stake (PoS).  https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/, July 2021\.
  * [12] P. Feldman.  A practical scheme for non-interactive verifiable secret sharing.  In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 427–438. IEEE, 1987.
  * [13] Filecoin.  Filecoin.  https://spec.filecoin.io/, November 2021.
  * [14] J. Garay, A. Kiayias, and N. 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.
  * [15] P. Gaži, A. Kiayias, and D. Zindros.  Proof-of-stake sidechains.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 139–156. IEEE, 2019.
  * [16] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin.  Secure distributed key generation for discrete-log based cryptosystems.  In Proceedings of the 17th International Conference on the Theory and Applications of Cryptographic Techniques, pages 295–310. Springer, 1999.
  * [17] R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin.  Secure distributed key generation for discrete-log based cryptosystems.  Journal of Cryptology, 20(1):51–83, 2007.
  * [18] 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, 2017.
  * [19] J. Groth.  Non-interactive distributed key generation and key resharing.  Cryptology ePrint Archive, 2021.
  * [20] S. King and S. Nadal.  PPCoin: Peer-to-peer crypto-currency with proof-of-stake.  https://www.peercoin.net/whitepapers/peercoin-paper.pdf, 2012.
  * [21] C. Komlo and I. Goldberg.  FROST: Flexible Round-Optimized Schnorr Threshold Signatures.  IACR Cryptology ePrint Archive, 2020:852, 2020.
  * [22] P. Kuznetsov and A. Tonkikh.  Asynchronous reconfiguration with byzantine failures.  In H. Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 27:1–27:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [23] J. Liu, W. Zheng, D. Lu, J. Wu, and Z. Zheng.  Understanding the decentralization of dpos: Perspectives from data-driven analysis on eosio, 2022.
  * [24] S. Meiklejohn, M. Pomarole, G. Jordan, K. Levchenko, D. McCoy, G. M. Voelker, and S. Savage.  A fistful of bitcoins: characterizing payments among men with no names.  In Proceedings of the 2013 conference on Internet measurement conference, pages 127–140, 2013.
  * [25] Murch.  2-of-3 multisig inputs using Pay-to-Taproot.  https://murchandamus.medium.com/2-of-3-multisig-inputs-using-pay-to-taproot-d5faf2312ba3, December 2020.
  * [26] S. Nakamoto and A. Bitcoin.  A peer-to-peer electronic cash system.  Bitcoin.–URL: https://bitcoin. org/bitcoin. pdf, 4, 2008.
  * [27] J. Nick, T. Ruffing, and Y. Seurin.  MuSig2: Simple two-round Schnorr multi-signatures.  Cryptology ePrint Archive, 2020:1261, 2020.
  * [28] Protocol Labs.  IPFS powers the distributed web.  https://ipfs.io/.
  * [29] C. Schnorr.  Efficient signature generation by smart cards.  J. Cryptol., 4(3):161–174, 1991.
  * [30] S. Steinhoff, C. Stathakopoulou, M. Pavlovic, and M. Vukolić.  BMS: Secure decentralized reconfiguration for blockchain and BFT systems.  arXiv preprint arXiv:2109.03913, 2021.
  * [31] D. R. Stinson and R. Strobl.  Provably secure distributed Schnorr signatures and a (t, n) threshold scheme for implicit certificates.  In 6th Australasian Conference on Information Security and Privacy, pages 417–434. Springer, 2001.
  * [32] E. N. Tas, D. Tse, F. Yu, and S. Kannan.  Babylon: Reusing bitcoin mining to enhance proof-of-stake security.  arXiv preprint arXiv:2201.07946, 2022.
  * [33] M. Vukolić.  On the future of decentralized computing.  Bulletin of the EATCS, 2021.

##  Appendix A Extra Figure

(a) DKG.

(b) Signing.

Figure 8. Execution time of our protocols with failures (here an aborting
participant). A (conservative) timeout of 12 seconds was chosen. In the DKG
case, the timeout is repeated over the different rounds (waiting for shares of
the secrets, for public commitments, for complaints, for complaint answers).
This explains the much longer execution time.


# Training on test data:
Removing near-duplicates in Fashion-MNIST

Christopher Geier
University of Virginia
School of Engineering and Applied Science
<EMAIL_ADDRESS>
###### Abstract

Fashion-MNIST is a popular machine learning benchmark task that improves on
MNIST by introducing a harder problem, increasing the diversity of testing
sets, and more accurately representing a modern computer vision task. In order
to increase the data quality of Fashion-MNIST, this paper investigates near
duplicate images between training and testing sets. Near-duplicates between
testing and training sets artificially increase the testing accuracy of
machine learning models. This paper identifies near-duplicate images in
Fashion-MNIST and proposes a dataset with near-duplicates removed.

##  1 Introduction

MNIST is a common benchmarking data set in the machine learning for the
classification task of recognizing handwritten digits. The simplicity of the
problem results in very high testing accuracy (LeCun & Cortes, 2010). Modern
machine learning approaches can easily achieve 97% testing accuracy on MNIST.
This high testing accuracy makes comparisons between machine learning
algorithms less useful. Fashion-MNIST was proposed as a better alternative to
MNIST to solve this problem (Xiao et al., 2017). The Fashion-MNIST dataset
consists of labeled clothing images retrieved from an online shopping site.
Because the images more diverse, Fashion-MNIST makes the problem of
distinguishing classes more difficult for algorithms. Fashion-MNIST hopes to
more accurately give feedback on the performance of models.

Figure 1: Very similar images sample.

Several authors have shown that popular machine learning datasets are often of
poor quality in ways that can distort model evaluations. (Barz & Denzler,
2019) estimated that 3.3% of images in the CIFAR-10 dataset are shared between
the training and testing sets . Radford et al. (2019) showed that this problem
goes beyond images. Popular natural language processing data-sets were found
to have overlap of 1.63% and 13.19% between training and testing sets. By
having samples shared between training and testing sets, models that over-fit
the training set and memorize examples will also have an artificially high
testing accuracy. A sample of very similar images found in Fashion-MNIST is
shown in Figure 1. In this paper, very similar images appearing both in the
training and test of Fashion-MNIST are identified and removed to provide an
improved test set.

##  2 Sorting by similarity

To identify pairs of similar images, the pairs were ranked by similarity and
then classified by a human analyst. Similarity of image pairs were calculated
using feature vectors from a trained model. Using this measure of similarity,
the image pairs were sorted. The most similar pairs were classified as very
similar or different by a human analyst. Without using this method to rank
similarity of image pairs, the number of image pairs to classify using a human
analyst would have been impractical.

###  2.1 Feature vectors

As in Barz & Denzler (2019), we use a convolutional neural network to identify
similar images in the training and testing set. This was done by removing the
last few layers of a trained neural network. At later layers convolutional
neural networks identify higher level features present in images (Zeiler &
Fergus, 2013). This can be used to identify images that have similar features,
not just similar pixel values. We used a sequential neural network with three
convolutional layers, batch normalization, max pooling and dropout. The target
model architecture was referenced from TensorFlow Hub (2018). After the
feature vectors were extracted from the trained neural network, the distances
between vectors were computed and ranked. Images that are similar have closer
feature vectors, and this was used to rank the image pairs from most similar
to most distinct.

###  2.2 Identifying very similar versus distinct

The process of selecting very similar images is very subjective task. The goal
of this process is to remove images that the trained algorithm has already
been trained on in the training set. Because algorithms being tested have been
trained on very similar images, the likelihood that they will identify
correctly should be increased. However there are issues with removing images
from the testing set. The testing set is meant to represent the performance on
a real-world problem. By removing images the distribution of real-world images
is changed.

This may be a problem for testing sets that are actually applied to real-world
problems, however it is not as important for the testing accuracy on
benchmarking sets like MNIST and Fashion-MNIST to mimic the real-world, but
more important to show algorithms are learning features from the training
dataset. Removing very similar images present in both the training and testing
set may improve the intended purpose of these datasets to benchmark the
generalization of algorithms beyond images in the training set. This also
means that the very-similar image identification can be less conservative in
identifying very similar images.

The following characteristics were used to identify images that were
considered ”very similar”:

  * •

Size and Shape: Overall figure must match by 10 pixels or less

  * •

Outline: Aliasing around the clothing article is 90% similar

  * •

Tone: Difference of color is indistinguishable at a glance

  * •

Features: Vary by 1 feature such as buttons, zippers, patterns, or text

Figure 2: User interface used to label images as distinct versus similar

To collect the data, a human analyst can be used to mark images as very
similar versus distinct. The image in Figure 2 showcases the user interface
used to classify image pairs. Future work could involve improving this
interface to allow for answers on a scale from distinct to identical.

Using this interface the analyst looked at pairs of images and determined
their similarity using the characteristics above. Once the analyst identified
20 images in a class as different, a different class of images were presented.
The images that were identified as being very similar were then removed from
the testing set to create the new Fair-Fashion-MNIST dataset.

Figure 3: Number of images removed from the testing set for each class

##  3 Results

Table 1: Testing accuracy on benchmark datasets Model | MNIST | Fashion-MNIST | Fair-Fashion-MNIST
---|---|---|---
SGD Classifier | 0.913 | 0.829 | 0.820
Perceptron | 0.845 | 0.759 | 0.754
Decision Tree | 0.877 | 0.789 | 0.783
Random Forest | 0.949 | 0.844 | 0.840

The number of images removed from the testing set for each class is shown in
Figure 3. In total, 5.98% of the 10,000 original images in the testing set
were removed. An accuracy comparison of trained algorithms is presented in
Table 1. Although not as significant of an improvement as Fashion-MNIST made
to MNIST, the near-similar removal process in this paper did reduced testing
accuracy by a small amount. The Fair-Fashion-MNIST dataset and full
benchmarking results can be found at https://github.com/cpgeier/fair-fashion-
mnist. The resulting dataset is compatible with existing MNIST and Fashion-
MNIST scripts using the IDX file format.

##  4 Conclusion

In this paper, a new dataset is introduced that limits the overlap of images
between testing and training set to give more meaningful feedback to machine
learning researchers. By removing overlapping images between testing and
training sets, we produce a more fair testing set that should better predict
the classifier’s performance. The testing accuracy of common machine learning
algorithms on our Fair-Fashion-MNIST dataset was slightly lower than on the
original Fasion-MNIST. This likely shows an improvement in the testing set as
the models will have an expected higher accuracy on images very similar to
images in the training set. The resulting dataset is public and can be used
for future Fashion-MNIST work.

## Acknowledgments

I would like to thank my research advisor, David Evans, for guiding this
research and helping me throughout conducting this research.

## References

  * Barz & Denzler (2019) Björn Barz and Joachim Denzler.  Do we train on test data? purging CIFAR of near-duplicates, 2019.
  * LeCun & Cortes (2010) Yann LeCun and Corinna Cortes.  MNIST handwritten digit database.  2010\.  URL http://yann.lecun.com/exdb/mnist/.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  _URL https://openai.com/blog/better-language-models_ , 2019.
  * TensorFlow Hub (2018) TensorFlow Hub.  Fashion MNIST with Keras and TPUs, 2018.  URL https://colab.research.google.com/github/tensorflow/tpu/blob/master/tools/colab/fashion_mnist.ipynb.
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms, 2017.
  * Zeiler & Fergus (2013) Matthew D Zeiler and Rob Fergus.  Visualizing and understanding convolutional networks, 2013.