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

Sarah Azouvi Protocol Labs

ABSTRACT

Blockchain systems based on a reusable resource, such as proof-ofstake (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.

CCS CONCEPTS

• Security and privacy → Cryptography.

KEYWORDS

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

ACM Reference Format:

Sarah Azouvi and Marko Vukolić. 2022. Pikachu: Securing PoS Blockchains from Long-Range Attacks by Checkpointing into Bitcoin PoW using Taproot. In Proceedings of the 2022 ACM Workshop on Developments in Consensus (ConsensusDay ’22), November 7, 2022, Los Angeles, CA, USA. ACM, New York, NY, USA, 13 pages. https://doi.org/10.1145/3560829.3563563

1 INTRODUCTION

Long-range attacks (LRA) — also called posterior corruption attacks [9] — 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 𝑡1and reconnects at a later time to tell that validators who were legitimate at time 𝑡₁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𝑡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 [26] difficulty adjustment) and physical resources (e.g., energy for performing actual computation) and not just using cryptographic

$$ t_{1} $$

$$ t_{1} $$

$$ \mathbf{e}.\mathbf{g} $$

$$ t_{1} $$

Marko Vukolić Protocol Labs

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.

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.

Recently, Steinhoff et al. [30] 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.

This work is licensed under a Creative Commons Attribution International 4.0 License.

ConsensusDay ’22, November 7, 2022, Los Angeles, CA, USA © 2022 Copyright held by the owner/author(s). ACM ISBN 978-1-4503-9879-4/22/11. https://doi.org/10.1145/3560829.3563563

However, as it happens, Ethereum is abandoning PoW and transitions to PoS [11] (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.1

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 [3] 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 𝐶𝑖 in the PoS system. When the set changes significantly enough to configuration 𝐶𝑖₊₁, 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 𝐶𝑖 to the new aggregated key controlled by validators in configuration 𝐶𝑖+1. Instead of having each validator in 𝐶𝑖 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 𝑂𝑃_𝑅𝐸𝑇𝑈𝑅𝑁 field of the transaction from 𝐶𝑖 to 𝐶𝑖+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 [28]) 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. 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 [2]).

$$ C_{i} $$

$$ C_{i+1}. $$

$$ C_{i} $$

$$ C_{i} $$

$$ C_{i+1} $$

$$ C_{i} $$

$$ C_{i+1} $$

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

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 𝑄 (which itself contains the aggregated public key of the configuration and commitment to the PoS chain ckpt) as well as a content identifier 𝑐𝑖𝑑 that can be used with any contentaddressable storage to retrieve information about the configuration (IPFS pictured).

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 𝑞 is a large prime and 𝐺,𝐽 are generators of a subgroup of order𝑞 of an elliptic curve E. We assume that E is chosen in such a way that the discrete logarithm problem in the subgroup generated by𝐺 is hard, so it is infeasible to compute the integer𝑑 such that 𝐺 = 𝑑𝐽.

$$ G,J $$

$$ G=d J $$

Let 𝐻,𝐻1*,𝐻2,𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘* be cryptographic hash functions map- ∗ $ ping to Z . We denote by_𝑞𝑥 ←− 𝑆 that 𝑥 is selected uniformly at random from 𝑆.

$$ H,H_{1},H_{2},H_{T a p T} $$

$$ \mathbb{Z}_{q}^{*}. $$

$$ x\stackrel{\mathfrak{S}}{\longleftarrow}s $$

2.1 Schnorr signature

The Schnorr signing scheme [29] works as follows. Let (𝑠,𝑌) ∈ ∗ Z𝑞× E be a user key pair (such that𝑌 = 𝑠𝐺) and𝑚 a message to be signed. The signer performs the following steps.

$$ (s,Y)\ \in $$

$$ \mathbb{Z}_{q}^{*}\times\mathbb{E} $$

$$ Y={\mathfrak{s}}G( $$

$ (1) 𝑘 ←− Z∗𝑞

$$ k\overset{\mathfrak{S}}{\longleftarrow}\mathbb{Z}_{a}^{*} $$

(2) 𝑅 ← 𝑘𝐺

$$ R\gets k\bar{G} $$

(3) 𝑧 ← 𝑘 + 𝐻 (𝑚||𝑅||𝑌)·𝑠 mod 𝑞

$$ z\gets k+H(m||R||Y)\cdot s $$

? The signature is then (𝑧,𝑅) and is verified by checking that 𝑧𝐺 = 𝑅 + 𝐻 (𝑚||𝑅||𝑌)𝑌.

$$ z G\overset{?}{=} $$

$$ R+H(m||R||Y)Y $$

2.2 Secret sharing schemes

¹The discussion on long-term viability of energy consumption of Bitcoin is out of scope of this paper and is available elsewhere [33].

A secret sharing scheme allows one participant (a dealer) to share a secret with𝑛 other participants, such that any𝑡 of them can recover the secret but any set of 𝑡 − 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 [12] (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 𝑡 can recover the secret on their own. We will use the scheme designed by Gennaro et al. [17] that we define in Figure 5, and we adopt the following notation:

$$ (s_{1},\cdots,s_{n})\xleftarrow{(t,n)}(r,Y,a_{k}G,S_{0}),:k\in{1,\cdots,t-1} $$

to mean that 𝑠𝑗 is player 𝑗’s share of the secret 𝑟 for each 𝑗 ∈ 𝑆₀. The values 𝑎𝑘𝐺 are the public commitments used to verify the correctness of the shares and (𝑟,𝑌) forms a key pair where 𝑟 is a private key and 𝑌 is the corresponding public key. The set 𝑆₀ 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 𝑡 > (i.e., it can tolerate an adversary that corrupts up to half 2 of the participants).

$$ s_{j} $$

$$ j\in S_{0}. $$

$$ a_{k}G $$

2.3 Threshold signing

A 𝑡-of-𝑛 threshold signing scheme allows any combination of 𝑡 participants to sign a message while preventing any coalition of 𝑡 − 1 participants or less to create a valid signature, i.e., at least 𝑡 participants must agree to sign the message for the signature to be valid. We use the threshold signing protocol FROST [21], that we define in Figure 6. This interactive protocol will either output a Schnorr signature (𝑧,𝑅) on a message𝑚 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 [31] 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 [10, 27] as they are not compatible with threshold signing.

Note that we did not implement the key generation algorithm presented by Komlo and Goldberg [21], 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. [16] and borrow only the signing scheme presented in the FROST paper [21], as per the authors’ suggestion. The distributed key generation (DKG) algorithm by Gennaro et al. is also used by Stinson and Strobl [31] 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. [17] 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 [31]).

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 [24] 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 [25], though less efficient as the size of the tree would grow exponentially with the number of participants [2].

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 [4], the output key should commit to a (potentially unspendable) script path even if the spending condition does not require

Figure 3: Taproot Output Composition

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:

$$ (\mathrm{i.e.} $$

where𝑃 is the internal public key and 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘 is a hash function. The associated tweaked private key is then:

$$ H_{T a p T} $$

$$ q=p+\mathrm{i n t}(H_{T a p T w e a k}(b y t e s(P))) $$

where 𝑝 is the private key associated with 𝑃. 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 𝑐 denote this commitment. In this case, the tweaked public key becomes: 𝑄 = 𝑃 + 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘(𝑃||𝑐)𝐺 and the tweaked private key 𝑞 = 𝑝 + 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘(𝑃||𝑐). The script path is still unspendable, and the output is spent by signing using the tweaked private key.

$$ \mathcal{Q}=\mathcal{P}+H_{T a v T w e a k}(\mathcal{P}||c)\mathcal{G} $$

$$ q=p+H_{T a p T w e a k}(\dot{P||c c}) $$

2.4.2 Transaction notation. For any Bitcoin transaction, we use the following notation:

input1*,...,* input𝑖→((amount1*,output1),...,* (amount𝑗,output𝑗)) to say that all the coins associated with input1*...,* input𝑖are transferred to output1*,...,* output𝑗with, respectively, amount1,..., amount𝑗 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 amount1 +···+ amount𝑗≤ input1*.amount +···+ input𝑖.amount where input𝑘.amount represents the total amount associated with input𝑘*. The remaining amount (in the case of a strict inequality) is used as a transaction fee for the miner mining the block.

$$ \ {sf i i p u u}{1},\ldots,{\sf i n p u t}{i}\xrightarrow{}(({\sf a m o u n t}{1},{\sf o u t p u t}{1}),\ldots,({\sf a m o u n t}{j},{\sf o u t p u t}{j})) $$

$$ \ !{\mathfrak{l}}{1}\ldots,\ \mathsf{i n p u t}{i} $$

$$ {\mathsf{p u t}}_{1},\ldots, $$

$$ {\mathfrak{r t}}_{1},\ldots. $$

$$ \cdot j\leq\mathsf{i n p u t}_{1} $$

$$ +\cdots+{\sf{i n p u t}}_{i} $$

$$ 1\mathbf{t}_{k}. $$

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𝐶, 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 thepower table. The power table is determined by a set |𝐶 | of signing keys and their associated weight: 𝐶 = {(𝑃𝑜𝑆.𝑝𝑘𝑖,𝑤𝑖)}. 𝑖=1 Each signing private key 𝑃𝑜𝑆.𝑠𝑘𝑖is private to 𝑖-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 𝑥 units of power possesses 𝑥 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𝐶 𝑗 and𝐶𝑖 as their symmetric difference (𝐶𝑖△𝐶 𝑗), which corresponds to the number of reconfiguration requests that need to be applied to 𝐶𝑖 in order to obtain 𝐶 𝑗. We assume that for two consecutive configurations 𝐶𝑖 and 𝐶𝑖₊₁, their symmetric difference is bounded by some parameter𝑏.

$$ C={(P o S.p k_{i},w_{i})}_{i=1}^{|C|} $$

$$ s k_{i} $$

$$ C_{j} $$

$$ C_{i} $$

$$ (C_{i}\Delta C_{j}) $$

$$ C_{i} $$

$$ C_{j} $$

$$ C_{i} $$

$$ C_{i+1} $$

Following [1], 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 [14], as long as a sufficient fraction of the participants are perpetually honest. Let 𝑓 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., 𝑓 = 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 [7, 18] or relaxed by using a “lookback” parameter. For example, if a block is final after 𝑘 confirmations, then we will use the state of the chain 𝑘 blocks in the past instead of the latest state to ensure consistent views across participants.

$$ f=1/3) $$

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 A that, for each state𝑖 of the PoS system, controls all the keys from previous configurations (𝐶 𝑗)𝑗 <𝑖−𝐿where 𝐿 ≫ 1 is a parameter (assumption 1) as well as a fraction of at most . 𝑓 participants in configurations (𝐶_𝑗)_{𝑖 −𝐿≤ 𝑗 ≤𝑖}(assumption 2). We 1 quickly note that 𝑓 < since there does not exist any protocol that 2 1 is secure with 𝑓 >. 2

$$ (C_{j})_{j<i-L} $$

$$ L\gg1 $$

$$ (C_{j})_{i-L\leq j\leq i} $$

$$ f<\frac{1}{2} $$

$$ 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 𝑗 < 𝑖 − 𝐿, using the keys from configuration 𝐶 𝑗 and that runs until the current height 𝑖. Since the adversary does not hold the keys from configuration𝑖 −𝐿 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

$$ j<i-L $$

$$ C_{j} $$ 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 (RB_𝑖)_𝑖∈Nthat 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.

$$ (\mathrm{R B}{i}){i\in\mathbb{N}} $$

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 𝐶𝑖 is associated with a Taproot public key 𝑄𝑖 that consists of an internal key, in this case an aggregate public key 𝑝𝑘𝑖, 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 𝑗 in the configuration then knows a share of the secret key associated with 𝑝𝑘𝑖, 𝑠𝑖,𝑗, such that 𝑡𝑖 of the shares are enough to compute a valid signature on any message, but fewer than 𝑡𝑖 participants cannot compute a signature. Configuration 𝐶𝑖 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 𝐶𝑖+1must first compute their aggregated public key 𝑝𝑘𝑖+1using 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 𝑄𝑖+1= 𝑝𝑘𝑖+1+ 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘(𝑝𝑘𝑖+1||ckpt)𝐺. 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 𝑝𝑘𝑖+1and ckpt can easily reconstruct 𝑄𝑖+1to verify that their view of the PoS chain is correct.

$$ Q_{i} $$

$$ C_{i} $$

$$ p k_{i}. $$

$$ p k_{i},s_{i,j} $$

$$ t_{i} $$

$$ t_{i} $$

$$ C_{i} $$

$$ C_{i+1} $$

$$ Q_{i+1},=,p k_{i+1}+H_{T a p T w e a k}(p k_{i+1}||\mathsf{c k p t})G. $$

$$ Q_{i+1} $$

To update the configuration from 𝐶𝑖 to 𝐶𝑖+1, a transaction from 𝑄𝑖 to 𝑄𝑖₊₁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 𝑡𝑖 participants from configuration 𝐶𝑖 where 𝑡𝑖 is chosen to be strictly more than 𝑓 |𝐶𝑖 | 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 𝑡𝑖 > 0*.5|𝐶𝑖 | to ensure security so our final constraint on 𝑡𝑖 is 𝑡𝑖 > max(0.5|𝐶𝑖|,𝑓* |𝐶𝑖 |). Since we assume that online validators can distinguish a LRA chain, it is enough to have the transaction signed by 𝑡𝑖 participants as no honest validators can be fooled into signing an illegitimate transaction. If forks were allowed even in

$$ C_{i} $$

$$ C_{i+1} $$

$$ Q_{i} $$

$$ Q_{i+1} $$

$$ C_{i} $$

$$ t_{i} $$

$$ t_{i} $$

$$ f|C_{i}| $$

$$ t_{i}>0.5|C_{i}| $$

$$ t_{i}>\operatorname*{m a x}(0.5|\mathcal{C}{i}|,f|\mathcal{C}{i}|) $$

$$ t_{i} $$

$$ t_{i} $$

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 𝑓 = 1/3 (as previously mentioned, this can also be fixed by considering a block in the past, i.e., one that has been finalized).

$$ f=1/3 $$

In addition to the transfer of coins from 𝑄𝑖 to 𝑄𝑖+1, the transaction spent by configuration 𝐶𝑖 will have a second output that does not receive any bitcoins and that is unspendable, but that contains an identifier𝑐𝑖𝑑 used to retrieve the full details of the configuration. This is done using the 𝑂𝑃_𝑅𝐸𝑇𝑈𝑅𝑁 opcode of Bitcoin [5] that allows storing of extra information in the chain, which we use to store 𝑐𝑖𝑑. 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 𝑝𝑘𝑖+1and ckpt due to a LRA). In this case, the content identifier 𝑐𝑖𝑑 can be used, together with a content-addressable decentralized storage, for example IPFS [28] or Filecoin [13] (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:

$$ \ \mathrm{i.e.} $$

$$ Q_{i} $$

$$ Q_{i+1} $$

$$ C_{i} $$

$$ p k_{i+1} $$

$$ \mathsf{t x}{i}:Q{i}\to((\mathsf{a m o u n t},Q_{i+1}),(0,O P_R E T U R N=c i d_{i+1})) $$

meaning that amount is transferred to 𝑄𝑖+1and 0 is transferred to 𝑂𝑃_𝑅𝐸𝑇𝑈𝑅𝑁 = 𝑐𝑖𝑑𝑖₊₁(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.

$$ Q_{i+1} $$

$$ O P_R E T U R N=c i d_{i+1} $$

We add the following assumption (assumption 3): we assume that tx_𝑖is finalized in the Bitcoin blockchain before the configuration 𝐶𝑖+𝐿is formed, where𝐿 ≫ 1 is the parameter defined in assumption 1 (Section 3).

$$ C_{i+L} $$

$$ L\gg1 $$

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 ⟨𝑚𝑠𝑔⟩_𝑖means that message 𝑚𝑠𝑔 was sent by participant 𝑖 and we use PM(⟨𝑚𝑠𝑔⟩,𝑖) to denote that a private message 𝑚𝑠𝑔 was sent to participant 𝑖.

We make the following remarks about our protocol. First, in steps 3b and 5 we ask that every participant 𝑃 𝑗 in configuration 𝐶𝑖 publishes the configuration state to the decentralized storage provider and sends the signed transaction tx𝑖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.

$$ C_{i} $$

$$ P_{j} $$

$$ \mathrm {t x} _ {i} $$

Second, in step 4 of the protocol, we remark that the final signa- ′ ture on the transaction, 𝑧, is “tweaked” using

$$ z^{\prime},, $$

$$ H(\mathsf{t x}{i}||R||Q_{i})H{T a p T w e a k}(p k_{i}||\mathsf{c k p t}). $$

This is because because the signature computed as part of the FROST signing algorithm will verify against the key 𝑝𝑘𝑖, computed during the DKG but not 𝑄𝑖 = 𝑝𝑘𝑖 + 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘(𝑝𝑘𝑖 ||ckpt). For the signature to be valid on the taproot output, the signature must verify against the tweaked key 𝑄𝑖. Because Schnorr is additive, it is enough to add the term 𝐻(tx𝑖||𝑅||𝑄𝑖)𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘(𝑝𝑘𝑖 ||ckpt) to the signature. Indeed one can verify that if 𝑧𝐺 = 𝑅 + 𝐻(tx𝑖||𝑅||𝑄𝑖)𝑝𝑘𝑖

$$ p k_{i} $$

$$ Q_{i}=p k_{i}+H_{T a p T w e a k}(p k_{i}||\mathsf{c k p t}. $$

$$ Q_{i} $$

$$ \mathrm {H} \left(\mathrm {t x} _ {i} | | R | | Q _ {i}\right) H _ {T a p T w e a k} \left(p k _ {i} | \mathrm {c k p t}\right) $$

$$ \dot{z\ {dot G}}=dot\cal{R}+H(\ {x x}{i}||R{||Q{i}})p k_{i} $$ then

$$ \begin{array}{r}{z^{\prime}G=z G+H(\mathbf{t x}{i}||R||Q{i})H_{T a P T w e a k}(p k_{i}||\mathbf{c k p t})G}\ {=R+H(\mathbf{t x}{i}||R||Q{i})p k_{i}+H(\mathbf{t x}{i}||R||Q{i})H_{T a p T v e a k}(p k_{i}||\mathbf{c k p t})G}\ {=R+H(\mathbf{t x}{i}||R||Q{i})(p k_{i}+H_{T a p T w e a k}(p k_{i}||\mathbf{c k p t})G)}\ {=R+H(\mathbf{t x}{i}||R||Q{i})Q_{i}}\end{array} $$

4.2 Initialization and funding

The initial key 𝑄0is 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𝐶0to send a small amount of bitcoins to 𝑄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 𝑄₀. Indeed 𝑄₀must be determined before the participants send their transactions, otherwise they do not know where to send their funds. But once 𝑄0is 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𝑄0in 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 𝑘 blocks deep - where 𝑘 is a parameter corresponding to Bitcoin’s settlement time. With this in mind, we propose the following protocol.

$$ Q_{0} $$

$$ C_{0} $$

$$ Q_{0} $$

$$ Q_{0}. $$

$$ Q_{0} $$

$$ Q_{0} $$

We consider the following parameters: a deadlineℎ0(represented as a height in the Bitcoin blockchain); the settlement time 𝑘 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) Each participant 𝑃𝑖 in 𝐶₀ submit a commitment to their Bitcoin public key 𝑏𝑡𝑐.𝑝𝑘𝑖 (e.g. a hash 𝐻1(𝑏𝑡𝑐.𝑝𝑘𝑖)) 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.

$$ P_{i} $$

$$ C_{0} $$

$$ \cdot\boldsymbol{p}\boldsymbol{k}_{i}\left(\mathbf{e}.\mathbf{g}\right. $$

$$ H_{1}(b t c.p k_{i})) $$

(2) Configuration𝐶0interactively performs the DKG to create the key𝑝𝑘0. Each participant in𝐶0holds a share of the secret key associated. The key is then tweaked with a commitment to the PoS genesis block to give 𝑄0.

$$ C_{0} $$

$$ p k_{0} $$

$$ C_{0} $$

$$ Q_{0} $$

(3) Each participant 𝑃𝑖 in𝐶0send a small amout fee from𝑏𝑡𝑐.𝑝𝑘𝑖 to𝑄0. This transaction should be sent several heights before height ℎ₀. They add a timelock [6] such that if the output is not spent after release blocks, 𝑃𝑖 gains control of their bitcoins back. We denote this transaction 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖.

$$ P_{i} $$

$$ Q_{0}. $$

$$ h_{0}. $$

$$ P_{i} $$

(4) Once the Bitcoin chain has reached height at leastℎ0+ 𝑘 the participants can start the interactive signing. They create the transaction by spending all the UTXOs that were received by 𝑄0before block ℎ0(this ensures that everyone will sign the same transaction). We note tx0 this transaction. Every transaction 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖 not included in the initial transaction tx0 (e.g. because it was included too late in the bitcoin blockchain) can be sent back to its original sender due to the timelock.

$$ .t x_{i} $$

$$ h_{0}+k $$

$$ Q_{0} $$

$$ h_{0} $$

$$ .t x_{i} $$

(5) If 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖 was included in the inputs of tx₀, 𝑃𝑖 can submit evidence of this in the Filecoin chain using tx0 (i.e. everyone can verify that𝑖𝑛𝑖𝑡.𝑡𝑥𝑖 is in the list of input of tx0 and that the signature is correct). Since no adversary can forge a signature from𝑄0, due to the security of the threshold signing scheme, no proof can be forged for 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖 inclusion in tx0.

$$ .t x_{i} $$

$$ P_{i} $$

$$ \mathsf{t}\mathbf{x}_{0} $$

$$ .t x_{i} $$

$$ Q_{0}, $$

$$ .t x_{i} $$

(6) If 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖 was not included in the inputs of tx0, then 𝑃𝑖 does not get any reward.

$$ \ \mathrm x{{}}_{0}, $$

$$ .t x_{i} $$

$$ P_{i} $$

(7) Every PoS miner verifies that 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖was indeed included in tx0 (as described above), then verifies that 𝑏𝑡𝑐.𝑝𝑘𝑖 indeed belongs to 𝑃𝑖. If both checks pass, 𝑃𝑖 is awarded an amount of PoS coins proportional to the amount sent by 𝑖𝑛𝑖𝑡.𝑡𝑥𝑖. This amount should be high enough to not only compensate the fee paid by 𝑃𝑖 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.

$$ P_{i} $$

$$ .k_{i} $$

$$ P_{i} $$

$$ P_{i} $$

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 𝑄0, which serves as an identifier of the PoS blockchain on the Bitcoin blockchain, can follow the chain of transactions from 𝑄0to the newest public key 𝑄𝑖. The latest transaction in the chain (i.e., from𝑄𝑖−1to𝑄𝑖) contains an additional output that corresponds to the content identifier of the configuration𝐶_𝑖. 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.

$$ Q_{0}; $$

$$ Q_{0} $$

$$ Q_{i} $$

$$ C_{i} $$

$$ \ {mathrm e.}{\mathrm g}. $$

(1) Synchronize with the Bitcoin blockchain (e.g., by running a 2 Bitcoin full node. )

(2) Look for 𝑄₀and follow the chain of transactions to get tx_𝑖 and 𝑐𝑖𝑑𝑖, i.e.,

$$ Q_{0} $$

$$ c i d_{i},\mathrm{i..}. $$

²Bitcoin 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.

$$ \ {bf e}.{\bf g}. $$

We assume that the initial aggregated public key of participants (at genesis) 𝑝𝑘₀as well as their tweaked key 𝑄₀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 𝑖 > 0: 1 The protocol starts after a threshold of new registrations and unregistrations has been monitored (e.g., since the last configuration, 𝑖, there has been𝑢 new registrations or unregistrations). We call this event𝑈_𝑖+1. We note 𝑋_𝑖+1the height, in the PoS blockchain, corresponding to this event. As soon as the parties notice event 𝑈_𝑖+1, they start the distributed key generation algorithm defined in Figure 5. This algorithm is performed by members of the new configuration, 𝐶_𝑖+1in order to compute the new aggregated key 𝑝𝑘_𝑖+1. We denote 𝑆_𝑖+1,0the set of members in the new reconfiguration (i.e., reconfiguration 𝑖). (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 𝑝𝑘_𝑖+1is known by everyone and a message can be signed by 𝑡_𝑖+1out (𝑡𝑖+1,𝑛𝑖+1) of 𝑛_𝑖+1of the participants using their secret share 𝑠_𝑖+1,𝑗: (𝑠_𝑖+1,₁, ···,𝑠_𝑖+1,𝑛) ←−−−−−−→⁽𝑠𝑘^𝑖+1,𝑝𝑘^𝑖+1,𝑎_𝑖+1𝑘𝐺,𝑆_𝑖+1,1), 𝑘 ∈ {1*,* ···,𝑡_𝑖+1− 1}. Here 𝑆_𝑖+1,1= 𝑆_𝑖+1,0{misbehaving participants from the protocol}. We assume that the DKG is finished by block 𝑋_𝑖+1+ 𝑌 where𝑌 is chosen conservatively. The tweaked public key of the taproot address is then defined to be 𝑄𝑖+1= 𝑝𝑘𝑖+1+ 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘(𝑝𝑘𝑖+1||ckpt)𝐺, where ckpt is the hash of the PoS block at height 𝑋𝑖+1. 2 Optional: Remove the misbehaving party from the power table. 3 Signing protocol. Every participant 𝑃_𝑗of configuration𝐶_𝑖does the following: (a) 𝑃_𝑗checks that the previous reconfiguration transaction tx_𝑖−1(according to the PoS blockchain) is included in the bitcoin blockchain. If not, they submit it before forming the new transaction. (b) 𝑃_𝑗first publishes the list of members in the new configuration𝐶_𝑖+1to the decentralized storage and retrieves the corresponding content identifiers 𝑐𝑖𝑑_𝑖+1. (c) 𝑃_𝑗computes transaction tx_𝑖as follows. All of the coins associated with 𝑄_𝑖are transferred to 𝑄_𝑖+1and another output that receives no coins but contains an 𝑂𝑃𝑅𝐸𝑇𝑈𝑅𝑁 that contains 𝑐𝑖𝑑_𝑖+1is added: tx_𝑖: 𝑄_𝑖→ ((amt*,𝑄*_𝑖+1), (0*,𝑂𝑃*𝑅𝐸𝑇𝑈𝑅𝑁 = 𝑐𝑖𝑑_𝑖+1)) where amount is the amount associated with 𝑄_𝑖minus transaction fees. (d) The members of the current configuration𝐶_𝑖(i.e. associated with 𝑝𝑘_𝑖) perform the interactive signing algorithm. (i) Set𝑚 ← 0. (ii) (𝑜,𝑆_𝑖,𝑚+1) ← SchnorrThresholdSign (𝑆_𝑖,𝑚,tx_𝑖,𝑝𝑘_𝑖,𝑄_𝑖) defined in Figure 6 where 𝑆_𝑖,𝑚+1is the set of non-misbehaving parties during the execution of the protocol. (iii) If 𝑜 = (𝑧,𝑅), i.e., a signature has been successfully produced, continue to step 4. (iv) Else (i.e., 𝑜 = abort) set𝑚 = 𝑚 + 1 and go to step 3(d)ii. 4 The taproot signature is then computed as (𝑧^′,𝑅)←(𝑧 + 𝐻(tx ||𝑅||𝑄)𝐻 (𝑝𝑘 ||ckpt),𝑅), where 𝑐 is the hash of the PoS blockchain at height 𝑋. _𝑖 𝑖 𝑖 𝑖 5 𝑃_𝑗sends tx_𝑖to the Bitcoin blockchain to update the configuration. 6 Participants set 𝑖 ← 𝑖 + 1 and go back to step 1.

$$ p k_{0} $$

$$ X_{i+1} $$

$$ U_{i+1} $$

$$ U_{i+1} $$

$$ pboldsymbol{k}_{i+1} $$

$$ C_{i+1} $$

$$ S_{i+1,0} $$

$$ i)) $$

$$ pboldsymbol{k}_{i+1} $$

$$ n_{i+1} $$

$$ s_{i+1,j}\colon(s_{i+1,1},\cdot\cdot\cdot,s_{i+1,n})\xrightarrow{} $$

$$ t_{i+1} $$

$$ S_{i+1,1}=S_{i+1,0} $$

$$ X_{i+1}+Y $$

$$ Q_{i+1}=p k_{i+1}+H_{T a p T w e a k}(p k_{i+1}||\mathsf{c k p t})G, $$

$$ X_{i+1} $$

$$ P_{j} $$

$$ C_{i} $$

$$ P_{j} $$

$$ \tan_{i-1} $$

$$ P_{j} $$

$$ C_{i+1} $$

$$ c i d _ {i + 1}. $$

$$ {\sf t t}\times_{i} $$

$$ P_{j} $$

$$ Q_{i+1} $$

$$ Q_{i} $$

$$ \ i d_{i+1} $$

$$ \mathsf{t x}{i}:Q{i}\rightarrow((\mathsf{a m t},Q_{i+1}),(0,O P_R E T U R N=c i d_{i+1})) $$

$$ Q_{i} $$

$$ p k_{i}) $$

$$ C_{i} $$

$$ m\leftarrow0. $$

$$ (o,S_{i,m+1}),\leftarrow $$

$$ \mathrm {n} \left(S _ {i, m}, \mathrm {t x} _ {i}, p k _ {i}, Q _ {i}\right) $$

$$ S_{i,m+1} $$

$$ {\mathrm{I f}},o=(z,R),{\mathrm{i.e.}} $$

$$ (\mathrm{i.e.},o=\mathrm{a b o r t}) $$

$$ m=m+1 $$

$$ X_{i}. $$

$$ P_{j} $$

$$ \mathrm {t x} _ {i} $$

Figure 4: Main Algorithm

Each participant 𝑃_𝑖performs the following steps, where 𝑡 is a parameter and 𝑛 is the total number of participants: $ ∗Í𝑡 − 𝑘 (1) Choose 𝑟^𝑖←− Z_𝑞. Let the sharing polynomial be 𝑓_𝑖(𝑢) =𝑘₌₁₀𝑎_𝑖𝑘𝑢 where 𝑎_𝑖0= 𝑟_𝑖. Compute 𝑠_𝑖𝑗= 𝑓_𝑖( 𝑗) mod 𝑞 for each 𝑗 ∈{1*,...𝑛*} and send 𝑠_𝑖𝑗 privately to 𝑃_𝑗. (2) Expose 𝑌_𝑖= 𝑟^𝑖𝐺 as follows. Broadcast 𝐴_𝑖𝑘= 𝑎^𝑖𝑘𝐺 for 𝑘 ∈{0*,* ···,𝑡 − 1}. ? Í_{𝑡 − 𝑘} (3) Verify the values broadcast by other players: 𝑓_𝑗(𝑖)𝐺 =𝑘=10𝑖 𝐴_𝑗𝑘. If the check fails for an index 𝑗, complain against 𝑃_𝑗. (4) Answer each complaint from party 𝑃^𝑗against 𝑃_𝑖(if any) by broadcasting 𝑠^𝑖𝑗. (5) If any of the revealed shares fails this equation, remove that participant from the set of players 𝐻⁰.Í Í Í𝑖𝑗 (6) Extract 𝑌 =_{𝑗 ∈𝑆₀}𝑟_𝑗𝐺, of which each player’s share of the secret is 𝑠𝑖=_{𝑗 ∈𝑆₀}𝑠. The secret 𝑟 =_{𝑗 ∈𝑆₀}𝑟_𝑗mod 𝑞 is never computed. The corresponding aggregated private and public keys are (𝑟,𝑌), denoted by (𝑡,𝑛) (𝑠₁, ···,𝑠_𝑛⁾ ←−−→⁽𝑟,𝑌,𝑎_𝑘𝐺,𝑆₀), 𝑘 ∈{1*,* ···,𝑡 − 1}

$$ P_{i} $$

$$ a_{i0}=r_{i} $$

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

$$ r _ {i} \xleftarrow {$} \mathbb {Z} _ {q} ^ {*} $$

$$ s_{i}^{j}=f_{i}(j) $$

$$ j \in {1, \dots n } $$

$$ s_{i}^{j} $$

$$ A_{i k}=a_{i k}G $$

$$ k\in{0,\cdots,t-1} $$

$$ Y_{i}=r_{i}G $$

$$ f_{j}(i)G\stackrel{?}{=}\sum_{k=0}^{t-1}i^{k}A_{j k} $$

$$ P_{j} $$

$$ P_{j} $$

$$ s_{i}^{j}. $$

$$ P_{i} $$

$$ H_{0}. $$

$$ Y=\sum_{j\in S_{0}}r_{j}G $$

$$ \mathfrak{s}{i}=\sum{j\in S_{0}}\mathfrak{s}_{j}^{i}. $$

$$ r=\sum_{j\in S_{0}}r_{j} $$

$$ q $$

$$ (s _ {1}, \dots , s _ {n}) \xleftrightarrow {(t, n)} (r, Y, a _ {k} G, S _ {0}), k \in {1, \dots , t - 1 } $$

Figure 5: Distributed Key Generation Algorithm (JF-DKG by Gennaro et al. [17])

(a) Inspect the transactions going out from 𝑄0

(b) If there are multiple transactions going out from 𝑄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 ℎ0.

$$ Q_{0}, $$

(c) Once the initial transaction tx0 has been found, look for the transaction that spent tx0 (i.e. where tx0 is an input).

(d) For 𝑖 ≥ 0 get tx_𝑖+1by looking for the transaction that spent tx𝑖.

(e) Stop when tx𝑖is unspent and get𝑐𝑖𝑑𝑖 from the𝑂𝑃_𝑅𝐸𝑇𝑈𝑅𝑁 field.

$$ {\sf x}_{i}. $$

(3) Use 𝑐𝑖𝑑𝑖 to get the list of current nodes from the external storage chosen.

$$ i;\geq;0 $$

(4) Request the PoS blockchain state from these nodes.

$$ \ {bf t t}{\bf x}_{i+1} $$

$$ \mathsf{t}\mathsf{x}_{i}. $$

(5) Verify that the aggregated public key on the PoS blockchain 𝑝𝑘 and the hash of the block ckpt are in accordance with the Bitcoin Taproot address 𝑄 that is the output of tx𝑖.

$$ \ \mathrm{t}\times_{i}.} $$

(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.

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 𝑘 ∈ N: An adversary as defined in Section 3 cannot create any incorrect checkpointing transaction tx𝑖𝐴 for any 0 ≤ 𝑖 ≤ 𝑘 such that tx𝑖𝐴 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).

$$ k\in\mathbb{N};\iota $$

$$ t x_{i}^{A} $$

$$ 0\leq i\leq k $$

$$ t x_{i}^{A} $$

Base Case. First, we show that the adversary cannot create an alternative initial transaction tx₀. At the time where the initial transaction is created, the adversary controls at most𝑡0participants (assumption 2) and hence, by security of the DKG and signing algorithms, cannot unilaterally sign a transaction coming from 𝑄0. After 𝐿 configurations, the adversary do obtain all the keys from 𝐶₀and is able to create transaction coming out from this address, however, this happens after height ℎ0on the Bitcoin blockchain by assumption 3 and hence any transaction sent by the adversary from 𝑄0will 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.

$$ C_{0} $$

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

$$ k- $$

$$ k\mathrm{-}1;(\mathrm{i.e.,,},\mathsf{t x}{0}^{A},\dots,,\mathsf{t x}{k-1}^{A}) $$

$$ \mathbf{t}\mathbf{x}_{k}^{A} $$

$$ k<i-L $$

$$ Q_{k} $$

$$ \mathrm{\ t}times{}_{k}} $$

$$ \mathsf{t x}_{k-1} $$

$$ \tan_{k-1} $$

$$ \mathbf{t}\mathbf{x}_{k}^{A} $$

$$ \tan_{k-1} $$

$$ \mathsf{t x}_{k-1}^{A} $$

$$ \mathbf{t}\mathbf{x}_{k}^{A} $$

$$ k\geq i-L $$

$$ \mathsf{t X}_{k}^{A} $$

The second case is the case where 𝑘 ≥ 𝑖 − 𝐿. In this scenario, it could be the case that transaction tx𝑘−1is still unspent. By design the only spendable outputs of tx𝑘−1is 𝑄𝑘. However, according to

$$ \tan_{k-1} $$

$$ \mathsf{t x}_{k-1} $$

$$ Q_{k} $$

assumption 2, the adversary only holds a fraction 𝑓 of configuration 𝑘 and hence cannot create a transaction that is spent by 𝑄𝑘 and cannot spent transaction tx𝑘−1.

$$ Q_{k} $$

$$ {\mathrm{t x}}_{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.

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- 3 source Eudico framework, 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- 4 source library developed by the Taurus group 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.

5 The code is open source. 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 7. 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. 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 [23], where 21 validators are elected on a rotating basis to run the consensus protocol. In Figure 7, 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

³https://github.com/filecoin-project/eudico

⁴https://github.com/taurusgroup/multi-party-sig

⁵https://github.com/filecoin-project/eudico/tree/B2-bitcoin-checkpointing

SchnorrThresholdSign (𝐻,𝑚,𝑌,𝑄) Input: 𝐻 is the set of players,𝑚 the message. Y is the aggregated public key. Each participant 𝑃_𝑖holds a share of the associated secret key 𝑠^𝑖. 𝑌_𝑖is the public verification share of each participant and is Í Í𝑡 − 𝑘 computed as 𝑌_𝑖=_{𝑗 ∈𝑆₀ 𝑘=10}𝑖 𝐴_𝑗𝑘We note 𝑄 the tweaked key as defined in step 1 of Figure 4. Parameter: timeOut. PreProcess: Each participant 𝑃_𝑖performs the following steps. 𝜋 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 𝐿_𝑖. For 1 ≤ 𝑗 ≤ 𝜋 do: $ ∗ ∗ (a) Sample single-use nonces (𝑑_𝑖𝑗,𝑒_𝑖𝑗) ←− Z_𝑞× Z_𝑞. (b) Derive commitment shares (𝐷_𝑖𝑗,𝐸_𝑖𝑗)=(𝑑_𝑖𝑗𝐺,𝑒_𝑖𝑗𝐺). (c) Append (𝐷_𝑖𝑗,𝐸_𝑖𝑗) to 𝐿_𝑖. Store ((𝑑_𝑖𝑗,𝐷_𝑖𝑗), (𝑒_𝑖𝑗,𝐸_𝑖𝑗)) for later use in signing operations. (2) Publish (𝑖,𝐿_𝑖) to the PoS blockchain. Sign (𝑚) Each participant 𝑃_𝑖does the following: (1) Compute S, the set of 𝑡 participants for signing using RB_𝑖as follows: (a) Compute 𝐻 (𝑖𝑑 ||RB). (b) The smallest 𝑡 hashes are the id selected for signing. (2) Fetch the next available commitment for each participant 𝑃_𝑖∈ 𝑆 from 𝐿_𝑖and construct 𝐵 = ⟨(𝑖,𝐷𝑖,𝐸𝑖)⟩𝑖 ∈𝑆. Í (3) Compute the set of binding values𝜌_𝑙= 𝐻₁(𝑙,𝑚,𝐵),𝑙 ∈ 𝑆 and derives the group commitment𝑅 =_{𝑙 ∈𝑆}(𝐷_𝑙+𝜌_𝑙𝐸_𝑙) and the challenge𝑐 = 𝐻₂(𝑚||𝑅||𝑄). (4) Each 𝑃 ∈ 𝑆 computes their response using their secret share 𝑠 by computing 𝑧 = 𝑑 +(𝑒 · 𝜌)+ 𝜆 · 𝑠 · 𝑐 using 𝑆 to determine the 𝑖_𝑡ℎLagrange 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 𝑖 Î 𝑃 𝑗 coefficient 𝜆𝑖as follows: if 𝑆 = {𝑃𝑖₁···,𝑃𝑖𝑡} represents the participants identifiers then 𝜆𝑖=𝑗∈{𝑖₁*,...,𝑖𝑡*},_𝑗≠𝑖 𝑃 𝑗 −𝑃𝑖. (5) Each 𝑃_𝑖securely deletes (𝑑_𝑖,𝑒_𝑖) from their local storage and then post 𝑧_𝑖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 𝑅 =_{𝑖 ∈𝑆}𝑅_𝑖and 𝑐 = 𝐻₂(𝑚||𝑅||𝑄). ? (b) Verify that 𝑧_𝑖𝐺 = 𝑅_𝑖+(𝑐 · 𝜆_𝑖)· 𝑌_𝑖for each signing share 𝑧_𝑖,𝑖 ∈ 𝑆. If it fails, report the misbehaving participant(s) by publishing a message on the PoS blockchain with the proof of misbehaviour(s) (i.e., 𝑧_𝑖𝐺 and 𝑅_𝑖+(𝑐 · 𝜆_𝑖)𝑌_𝑖for each cheating player) and abort.Í (c) If no participants was misbehaving, compute 𝑧 =_{𝑖 ∈𝑆}𝑧_𝑖. (d) Compute 𝜎 = (𝑧,𝑅) 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: (𝜎,𝐻) if the protocol completed, (abort,𝑆^′) else, where 𝑆^′is the set of players who have not misbehaved during the execution of the protocol.

$$ s_{i}. $$

$$ \stackrel{\cdot}{Y_{i}}=\stackrel{\cdot}{\sum_{j\in S_{0}}}\sum_{k=0}^{t-1}i^{k}A_{j k}^{\cdot} $$

$$ P_{i} $$

$$ L_{i}. $$

$$ P_{i} $$

$$ 1\leq j\leq\pi $$

$$ \left(d _ {i j}, e _ {i j}\right) \xleftarrow {$} \mathbb {Z} _ {q} ^ {} \times \mathbb {Z} _ {q} ^ {}. $$

$$ \overset{\cdot}{(D_{i j},E_{i j})}=\overset{\cdot}{(d_{i j}G,e_{i j}G)} $$

$$ (D_{i j},E_{i j}) $$

$$ ((d_{i j},D_{i j}),(e_{i j},E_{i j})) $$

$$ L_{i}. $$

$$ (i,L_{i}) $$

$$ P_{i} $$

$$ \mathrm{R B}_{i} $$

$$ P_{i}\in S\operatorname{f r o m}L_{i} $$

$$ B=\langle\big(i,D_{i},E_{i}\big)\rangle_{i\in S}. $$

$$ \rho_{l}=H_{1}(l,m,B),l\in S $$

$$ \textstyle{R=\sum_{l\in S}(D_{l}{+}\rho_{l}E_{l})} $$

$$ c=H_{2}(m||R||Q) $$

$$ P_{i}\in S $$

$$ s_{i} $$

$$ z_{i}=dot\sigma{{{i}}}+\left(e{i}\cdot\rho_{i}\right)+\lambda_{i}\cdot s_{i}\cdot $$

$$ i^{t h} $$

$$ \lambda_{i} $$

$$ {S={P_{i_{1}}\cdot\cdot\cdot\ P_{i_{t}}} $$

$$ \lambda_{i}=\prod_{j\in{i_{1},\ldots,i_{t}},j\neq i}\frac{P_{j}}{P_{j}-P_{i}}. $$

$$ P_{i} $$

$$ (d_{i},e_{i}) $$

$$ z_{i} $$

$$ \textstyle{}=\sum_{i\in S}R_{i} $$

$$ c=H_{2}(m||R||Q) $$

$$ z_{i},i\in S. $$

$$ z_{i}G\stackrel{?}{=}R_{i}+(c\cdot\lambda_{i})\cdot Y_{i} $$

$$ (\mathbf{i}.\mathbf{e}.,z_{i}G $$

$$ R_{i}+(c\cdot\lambda_{i})Y_{i} $$

$$ z=\sum_{i\in S}z_{i}. $$

$$ \sigma=(z,R) $$

$$ ,S^{\prime}) $$

$$ S^{\prime} $$

Figure 6: Signing Algorithm

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 [20] or on additional assumptions [1]. Like the solution from Steinhoff et al. [30], this paper offers a fully decentralized solution without additional security assumptions (as in [1]) 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 [22], 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 [32] 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 [8] and Dfinity [19] 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.

Algorithm 1 Main 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: 𝑖𝑑 9: 𝑢 10: f 11: 𝑌 12: Init: 13: 𝐶𝑐𝑢𝑟 ← 𝐶0 14: 𝐶𝑙𝑎𝑠𝑡 ← 𝐶0 15: 𝑝𝑘𝑐𝑢𝑟 ← 𝑝𝑘0 16: CurrentShares ← empty dictionary 17: 𝑆0 ←𝐶𝑐𝑢𝑟 18: misbehavingPlayers ←∅ 19: 𝑖 ← 𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠[𝑖𝑑].𝑔𝑒𝑡𝐼𝑛𝑑𝑒𝑥 () 20: tx𝑙𝑎𝑠𝑡← tx0 21: upon event receiving 𝑃𝑇.update (𝑟𝑒𝑞)∧ 𝐶𝑙𝑎𝑠𝑡 △𝐶𝑐𝑢𝑟 < 𝑢 do 22: if 𝑟𝑒𝑞 = ⟨𝑝,“𝑗𝑜𝑖𝑛”⟩ then 23: 𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠 ← 𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠 ∪{𝑝} 24: if 𝑟𝑒𝑞 = ⟨𝑝,“𝑙𝑒𝑎𝑣𝑒”⟩ then 25: 𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠 ← 𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠 {𝑝} 26: upon event 𝐶𝑙𝑎𝑠𝑡 △𝐶𝑐𝑢𝑟 ≥ 𝑢 27: 𝑋 ← PoS.CurrentBlock() 28: Do Algorithm 2 (DKG) 29: upon event PoS.CurrentHeight == PoS.Height(X)+Y do 30: 𝑆0 ←𝐶𝑐𝑢𝑟Í*.𝑔𝑒𝑡𝐼𝑛𝑑𝑒𝑥𝑒𝑠* ()\misbehavingPlayers 31: 𝑝𝑘𝑛𝑒𝑤 ←𝑗 ∈𝑆0 CurrentShares[𝑗] 32: 𝑠𝑖 ← Í𝑗 ∈𝑆0𝑠𝑖𝑗 33: ckpt ← 𝑃𝑜𝑆.𝐵𝑙𝑜𝑐𝑘ℎ𝑎𝑠ℎ(𝑋) 34: 𝑞 ← 𝑝𝑘𝑛𝑒𝑤 + 𝐻𝑇𝑎𝑝𝑇𝑤𝑒𝑎𝑘 (𝑝𝑘𝑛𝑒𝑤 ||ckpt)𝐺 35: 𝑜 ← 0 36: if BTC.latestCheckpoint.UTXO ≠ tx𝑙𝑎𝑠𝑡 then 37: BTC.Broadcast(tx𝑙𝑎𝑠𝑡) 38: IPFS.push(𝐶𝑐𝑢𝑟) 39: 𝑐𝑖𝑑 ← 𝐼𝑃𝐹𝑆.𝑔𝑒𝑡𝐶𝑖𝑑(𝐶𝑐𝑢𝑟) 40: if 𝑖𝑑 ∈ 𝐶𝑙𝑎𝑠𝑡 then 41: do Algorithm 3 42: 𝐶𝑙𝑎𝑠𝑡 ← 𝐶𝑐𝑢𝑟 43: 𝑝𝑘𝑐𝑢𝑟 ← 𝑞 44: CurrentShares ←∅

⊲ The node id ⊲ Tolerated difference between local configuration and current configuration ⊲ Fault tolerance of the current configuration ⊲ Number of blocks to wait for the DKG to complete ⊲ Current configuration ⊲ Last configuration ⊲ Initial public key ⊲ Share of the aggregated public key ⊲ Non-misbehaving participants ⊲ Set of misbehaving participants in the DKG ⊲ Node’s index ⊲ Initial transaction as defined in Section 4.2 ⊲ Configuration request received ⊲ After𝑢 (un)registrations do ⊲ Give enough time for the DKG to complete ⊲ set of indexes of non-cheating players in the DKG ⊲ Compute the aggregated key ⊲ Compute the share of the secret key ⊲ Taproot address ⊲ Counter for the pre-process step ⊲ Check the Bitcoin blockchain for the previous checkpointing transaction ⊲ Send latest checkpoint ⊲ Members associated with 𝑝𝑘𝑐𝑢𝑟 sign tx ⊲ Signing protocol with other members

$$ C_{c u r}\leftarrow C_{0} $$

$$ \ {l a s t}\leftarrow C{0}, $$

$$ \mathsf{t x}{l a s t}\leftarrow\mathsf{t x}{0} $$

$$ i\gets C_{c u l} $$

$$ S_{0}\leftarrow C_{c u r} $$

$$ \mathbf{\cdot}\mathfrak{e}(r e q)\wedge C_{l a s t}\triangle C_{c u r}<u,\mathsf{d o} $$

$$ r e q=\langle{p,{\bar{{o i i n}}}^{*}}\rangle $$

$$ r e q = \langle p, " l e a v e" \rangle \mathrm {t h e n} $$

$$ \ {}C_{l a s t}\triangle{}C_{c u r}\geq $$

$$ p k_{n e w}\gets\Sigma_{j\in S_{0}} $$

$$ s_{i}\leftarrow\Sigma_{j\in S_{0}}s_{j}^{i} $$

$$ \mathsf{c k p t}\leftarrow\mathsf{P o S.}\dot{B l o c k h a s h}(X) $$

$$ q\gets p k_{n e w}+H_{T a p T} $$

$$ \ varepsilon\mathrm{t x}_{l a s t} $$

$$ \mathrm {P F S . p u s h} \left(C _ {c u r}\right) $$

$$ c i d\stackrel{\cdot}{\leftarrow}I P F S.g e t C i d(C_{c u r}) $$

$$ \mathbf{i f};i d\in C_{l a s t} $$

$$ C_{l a s t}\gets C_{c u r} $$

$$ p k_{c u r}\leftarrow q $$

$$ \cdot p k_{c u r} $$

$$ \begin{array}{l}{\overset{\mathrm{}{\ r v u u}}{\operatorname{C u r r e n t S h a r e s}}\leftarrow\emptyset}\ \end{array} $$

(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.

Pikachu: Securing PoS Blockchains from Long-Range Attacks by Checkpointing into Bitcoin PoW using Taproot ConsensusDay ’22, November 7, 2022, Los Angeles, CA, USA

Algorithm 2 Distributed Key Generation 1: import MainAlgorithm 2: Parameters: 3: 𝑡 ← 0*.5|𝐶𝑐𝑢𝑟 |+ 1 4: if 𝑖𝑑 ∈ 𝐶𝑐𝑢𝑟 then 5: Timeout.Start() $ 6: 𝑟𝑖 ←− Z𝑞*; 𝑎𝑖0 ←𝑟𝑖 7: for 𝑘 ∈{1*,...,𝑡* − 1} do $ÍZ 8: 𝑎𝑖𝑘 ←− 𝑞 9: 𝑓𝑖 (𝑢)←𝑡 −𝑎𝑖𝑘𝑢𝑘 𝑘=10 10: for 𝑗 ∈{1*,...,* |𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠|} do 11: PM(⟨SHARE*,𝑠𝑖𝑗* = 𝑓𝑖 ( 𝑗)⟩,𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠.𝑖𝑛𝑑𝑒𝑥[ 𝑗]) 12: if id∈ 𝐶𝑐𝑢𝑟 then 13: for 𝑘 ∈{0*,...,𝑡* − 1} do 𝐴𝑖𝑘 ← 𝑎𝑖𝑘 𝐺 14: PoS.Broadcast(⟨secretCommitments*,𝐴𝑖0,...,𝐴𝑖*(𝑡−1) ⟩𝑖) 15: upon event ⟨SHARE*,𝑠𝑖𝑗* ⟩𝑗 received for all 𝑗 do 16: Timeout.Restart() 17: upon event TimeOut.Done() do 18: for 𝑗 ∈{1*,...,* |𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠|} do 19: if (⟨SHARE*,𝑠𝑖𝑗* ⟩)𝑗== nil then 20: misbehavingPlayers.append (𝑗) 21: Timeout.Restart() 22: upon event PoS.Receive(⟨secretCommitments*,𝐴 𝑗0,...,𝐴 𝑗*(𝑡−1) ⟩𝑗) do 23: if 𝑗 ∈{1*,...,* |𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠|} and 𝑠𝑖𝑗 ≠ Í𝑡 −𝑖𝑘 𝐴 𝑗𝑘 then 𝑘=10 24: misbehavingPlayers.append(𝑗) 25: else

⊲ Number of parties controlled by the adversary ⊲ Only member of the new configuration perform the DKG ⊲ We use a timeout to detect aborting players (this can be in terms of blocks in the PoS chain) ⊲ Send share of secret to each player ⊲ All secret shares were received ⊲ Some party did not send their private share ⊲ Add aborting players to list of misbehaving participants

26: CurrentShares.append(𝑗,𝐴 𝑗0) 27: upon event PoS.Receive(⟨secretCommitments*,𝐴 𝑗0,...,𝐴 𝑗*(𝑡−1) ⟩𝑗) for all 𝑗 or Timeout.Done() do ⊲ All commitments were received or timeout expired 28: if PoS.Read(⟨secretCommitments⟩) == nil then

𝑗 29: misbehavingPlayers.append (𝑗) 30: v = ∅ 31: for 𝑗 ∈{1*,...,* |𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠| do 32: if 𝑗 ∈ misbehavingPlayers then v.append(𝑓𝑗 (𝑖)) 33: else v.append(NoComplaint) 34: PoS.Broadcast(⟨complaintSecret, v⟩) 35: Timeout.Restart() 36: upon event PoS.Receive(⟨complaintSecret,v ⟩𝑘) do 37: for 𝑗 ∈{1*,...,* |𝐶𝑐𝑢𝑟.𝑚𝑒𝑚𝑏𝑒𝑟𝑠| do 38: if v[j]≠ NoComplaint then misbehavingPlayers.append (𝑗) 39: if v[i]≠ NoComplaint then PoS.Broadcast(⟨complaintAnswer*,𝑠𝑖𝑗,𝑖*⟩) 40: upon event PoS.Receive(⟨complaintAnswer, proof, 𝑗 ⟩𝑙) do 41: 𝑠𝑙𝑗 ←Parse(proof) 42: (𝐴 𝑗𝑘)𝑡 −𝑃𝑜𝑆.𝑅𝑒𝑎𝑑 (⟨SecretCommitments⟩) 𝑘=01 ← 𝑗 43: if 𝑠𝑙𝑗 𝐺 == Í𝑡 −𝑙𝑘 𝐴 𝑗𝑘 then 𝑘=10 44: misbehavingPlayers.remove (𝑗) 45: upon event PoS.Receive(⟨complaintSecret⟩𝑗) for all 𝑗∧ misbehavingPlayers == ∅ do 46: return 47: upon event Timeout.Done() do 48: return

⊲ Add aborting players to list of misbehaving participants ⊲ Send a list of (potentially empty) complaints ⊲ Receive other parties’ list of complaints ⊲ Add complaints against 𝑗 ⊲ Reply to complaint against self ⊲ 𝑗 can answer a complaint from𝑙 ⊲ Get 𝑗 commitments ⊲ All complaints (and potentially answers) were received ⊲ Finish the protocol ⊲ Leave enough time for answers to be received

$$ t\gets0.5|C_{c u r}|+1 $$

$$ i d\in C_{c u r} $$

$$ \in{1,\ldots,t-1} $$

$$ r _ {i} \leftarrow \stackrel {$} {\leftrightarrow} \mathbb {Z} _ {q}; a _ {i 0} \leftarrow r _ {i} $$

$$ a _ {i k} \leftarrow^ {$} \mathbb {Z} _ {q} $$

$$ f _ {i} (u) \leftarrow \sum_ {k = 0} ^ {t - 1} a _ {i k} u ^ {k} $$

$$ s_{i}^{j}=f_{i}(j)\rangle,C_{c u r} $$

$$ \mathbf{r};j\in{1,\dots,|C_{c u r} $$

$$ C_{c u r} $$

$$ :cdot k\in{0,\ldots,t-1} $$

$$ A_{i k}\leftarrow\alpha_{i k}G $$

$$ A_{i0},\ldots,A_{i(t-1)}\rangle_{i}) $$

$$ \langle\mathtt{S H A R E},\mathfrak{s}{j}^{i}\rangle{j} $$

$$ j\in{1,\dots,|C_{c u n}} $$

$$ \mathbf {i f} \left(\langle \mathrm {S H A R E}, s _ {j} ^ {i} \rangle\right) _ {j} = = $$

$$ A_{j0},\ldots,A_{j(t-1)}\rangle_{j}) $$

$$ \Xi\ {1,\ldots,|C_{c u r} $$

$$ s_{i}^{j}\neq\sum_{k=0}^{t-1}i^{k}A_{j k} $$

$$ A_{j0}) $$

$$ A_{j0},\ldots,A_{j(t-1)}\rangle_{j} $$

$$ j\in{1,\ldots,|C_{c u r} $$

$$ (f_{j}(i)) $$

$$ j\in{1,\ldots, $$

$$ s_{j}^{i},i\rangle) $$

$$ \dot{(A_{j k})}_{k=0}^{t-1}\leftarrow P o S $$

$$ \dot{\mathbf{i f}\ s_{l}^{j}G}=\overset{\cdot}{\sum}{k=0}^{t-1}l^{k}A{j k} $$

$$ j\Lambda $$

$$ :=\emptyset\ \mathbf{d o} $$

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 [8] or ad-hoc threshold multi-signature schemes [15] 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.

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 [4] Bitcoin. Bips/bip-0341.mediawiki at master ·· bitcoin/bips, Jul 2021. 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. Cryp- tology ePrint Archive, 2021. [9] E. Deirmentzoglou, G. Papakyriakopoulos, and C. Patsakis. A survey on longrange attacks for proof of stake protocols. IEEE Access, 7:28712–28725, 2019.

Algorithm 3 Signing algorithm

1: import MainAlgorithm 2: Parameters: 𝜋 ⊲ Number of pre-process steps 3: Timeout.start() 4: 𝐿𝑖 ←∅ 5: 𝑣 ← PoS.Height(X) 6: 𝑅𝐵 ← 𝑅𝐵𝑣 7: for 𝑗 ∈{0*,...,𝜋*} do $ ∗ ∗ 8: (𝑑𝑖𝑗,𝑒𝑖𝑗) ←− Z𝑞× Z𝑞 9: (𝐷𝑖𝑗,𝐸𝑖𝑗)=(𝑑𝑖𝑗 𝐺,𝑒𝑖𝑗 𝐺) 10: 𝐿𝑖.𝑎𝑝𝑝𝑒𝑛𝑑(𝐷𝑖𝑗,𝐸𝑖𝑗) 11: PoS.Broadcast(⟨PreProcess, 𝑖,𝐿𝑖 ⟩) 12: 𝐵 13: 𝑆_′←∅←∅ 14: for 𝑖 𝐶𝑙𝑎𝑠𝑡 do 15: 𝑆′∈← 𝑆′∪(𝐻 (𝑅𝐵||𝑖.𝐼𝐷)) ⊲ Pseudo-randomly choose set of signers 16: 𝑆′ ←𝑜𝑟𝑑𝑒𝑟(𝑆′) 17: 𝑆 ← 𝑆′[: 𝑓 |𝐶𝑙𝑎𝑠𝑡 |+ 1] ⊲ Choose t+1 participants for signing 18: for 𝑘 ∈ 𝑆 do 19: (𝐷𝑘𝑜,𝐸𝑘𝑜)←PoS.Read(⟨PreProcess*,𝑘,𝐿𝑘* [𝑜]⟩) 20: 𝐵.𝑎𝑝𝑝𝑒𝑛𝑑 ((𝑘,𝐷𝑘𝑜,𝐸𝑘𝑜)) 21: for 𝑙 ∈ 𝑆 do 22: tx ← 𝐵𝑇𝐶.𝑇𝑋 (𝑝𝑘𝑐𝑢𝑟 →(𝑎𝑙𝑙,𝑞), (0*,𝑂𝑃𝑅𝐸𝑇𝑈𝑅𝑁* = 𝑐𝑖𝑑)) ⊲ Compute the transaction 23: 𝜌𝑙 ← 𝐻1 (𝑙, tx*,𝐵*) for𝑙 ∈ 𝑆 𝑝 𝑗 24: 𝜆𝑖 ← Î𝑗 ∈𝑆,𝑗≠𝑖 𝑝𝑗 −𝑝𝑖 where 𝑝𝑗 is the identifier of participant 𝑗 25: 𝑅 ← Í𝑙 ∈𝑆 𝐷𝑙𝑜+ 𝜌𝑙 𝐸𝑙𝑜, 𝑐 ← 𝐻2 (tx ||𝑅||𝑞) 26: 𝑧𝑖 ← 𝑑𝑖𝑜 +(𝑒𝑖𝑜 · 𝜌𝑖)+ 𝜆𝑖 · 𝑠𝑖 · 𝑐 27: delete ((𝑑𝑖𝑜,𝐷𝑖𝑜), (𝑒𝑖𝑜,𝐸𝑖𝑜)) from local storage 28: PoS.Broadcast(⟨SHARE*,𝑧𝑖* ⟩) 29: if 𝑖𝑑 ∈ 𝑆 then 30: upon event PoS.Receive(⟨SHARE*,𝑧𝑘* ⟩) from all𝑘 ∈ 𝑆 do ⊲ All shares were received 31: CheatingPlayers←∅ 32: for 𝑘 ∈ 𝑆Ído Í 33: 𝑌𝑘 =𝑡−1𝑘𝑤𝐴 𝑗𝑤 𝑗 ∈𝑆0 𝑤=0Í 34: 𝜌𝑘 ← 𝐻1 (𝑘, tx*,𝐵*), 𝑅𝑘 ← 𝐷𝑘𝑜 + 𝜌𝑘 𝐸𝑘𝑜, 𝑅 ←𝑘 ∈𝑆 𝑅𝑘, 𝑐 ← 𝐻2 (tx ||𝑅||𝑞) 35: if 𝑔 𝑘𝑧≠ 𝑅𝑘 + 𝑐 · 𝜆𝑘 · 𝑌𝑘 then 36: CheatingPlayers.append(𝑘) 37: if CheatingPlayers≠ ∅ then 38: PoS.Broadcast(⟨RESTART SIGNING, CheatingPlayers⟩) 39: restofplayers ← 𝐶𝑐𝑢𝑟.𝑔𝑒𝑡𝐼𝑛𝑑𝑒𝑥𝑒𝑠 ()*𝑆* 40: 𝑆 ← 𝑆\CheatingPlayers 41: S.append(restofplayers[:|CheatingPlayers|]) ⊲ add as many players as were removed 42: 𝑜 ← 𝑜 + 1 43: Timeout.Restart() 44: go to line 18 45: else Í 46: 𝑧 ←𝑖 ∈𝑆 𝑧𝑖 47: 𝑐 𝑃𝑜𝑆.𝐵𝑙𝑜𝑐𝑘ℎ𝑎𝑠ℎ(𝑋) ⊲ Commitment to the blockchain 48: 𝜎′←← 𝜎 + 𝐻(tx||𝑅||𝑞)𝐻 (𝑝𝑘𝑐𝑢𝑟 ||𝑐) ⊲ compute taproot signature 49: BTC.Broadcast(tx, 𝜎 50: PoS.Broadcast(tx,𝜎′ ′)) 51: return 52: upon event Timeout.done() do ⊲ We implement a timeout to deal with aborting participants 53: for 𝑝 ∈ 𝑆 do 54: if PoS.Read (⟨SHARE⟩𝑝) == 𝑛𝑖𝑙 then ⊲ p hasn’t submitted its share 55: CheatingPlayers.append(p) 56: else Í 57: 𝜌𝑘 ← 𝐻1 (𝑘,𝑚,𝐵), 𝑅𝑘 ← 𝐷𝑘𝑗 + 𝜌𝑘 𝐸𝑘𝑗, 𝑅 ←𝑘 ∈𝑆 𝑅𝑘, 𝑐 ← 𝐻2 (tx ||𝑅||𝑞) 58: if 𝑔𝑧𝑘 ≠ 𝑅𝑘 + 𝑐 · 𝜆𝑘 · 𝑌𝑘 then 59: CheatingPlayers.append(p) 60: PoS.Broadcast(⟨RESTART SIGNING, CheatingPlayers⟩) 61: restofplayers ← 𝐶𝑐𝑢𝑟.𝑔𝑒𝑡𝐼𝑛𝑑𝑒𝑥𝑒𝑠 \ 𝑆 62: 𝑆 ← 𝑆\CheatingPlayers 63: S.append(restofplayers[:|CheatingPlayers|]) ⊲ add as many players as were removed 64: 𝑜 ← 𝑜 + 1 65: go to line 18

$$ L_{i}\gets\emptyset $$

$$ :j\in{0,\ldots,\pi} $$

$$ \left(d _ {i j}, e _ {i j}\right) \xleftarrow {$} \mathbb {Z} _ {q} ^ {} \times \mathbb {Z} _ {q} ^ {} $$

$$ (\ddot{D_{i j}},\ddot{E_{i j}})=(\overset{\iota}{d_{i j}}G,\overset{\iota}{e_{i j}}G) $$

$$ B\leftarrow\emptyset $$

$$ \ overset..L_{i}.a\ poverset{f\ }{p p p e n d}(\overset{...}L_{i j}) $$

$$ i,L_{i}\rangle) $$

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

$$ \mathbf{f o r},i\in C_{I a s t};\mathbf{d o} $$

$$ S ^ {\prime} \leftarrow S ^ {\prime} \cup (H (R B | | i. I D)) $$

$$ S\leftarrow S^{\prime}[:f|C_{l a s t}|+1] $$

$$ S^{\prime}\leftarrow o r d e r(S^{\prime}) $$

$$ k,L_{k}[o]\rangle) $$

$$ (D_{k0},E_{k0}) $$

$$ l\in S,\mathbf{d o} $$

$$ \overset{\cdot}{B.a p p e n d}((k,D_{k o},E_{k o})) $$

$$ \ {sf t t x}\leftarrow B T C.T X(p k_{c u r}\rightarrow(a l l,q),(0,O P_{R E T U R N}=c i d)) $$

$$ \lambda_{i}\leftarrow\prod_{j\in S,j\neq i}\frac{p_{j}}{p_{j}-p_{i}} $$

$$ p_{j} $$

$$ R\gets\sum_{l\in S}D_{l0}+\rho_{l}bar E{}{l0},c\gets H{2}(\mathsf{t x}\big|\big|R\big||q) $$

$$ z_{i}\leftarrow\overset{\cdot}{d_{i0}}+\overset{\cdot}cdot{eoverset cdot}cdot\cdot\cdot\rho_{i}\overset{\cdot}{}+\lambda_{i}\cdot s overset{\cdot}\cdot{s_{i}}\cdot c $$

$$ ,z_{k}\rangle) $$

$$ \in S $$

$$ k\in\mathsf{S},\mathbf{d0} $$

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

$$ \ddot{\rho_{k}}\gets\overset{\cdot}{H_{1}((k,\ \ {mathsf t t x},B)},R_{k}\gets{\hat{\ {mathsf T}}}\ D_{k o}+\rho_{k}E_{k o},R\gets\sum_{k\in S}R_{k},c\gets H_{2}({\mathsf{t x}}||R||q) $$

$$ \cdot g^{z}k\neq R_{k}+c\cdot\lambda_{k}\cdot Y_{k} $$

$$ \cdot\ C{_{c u r}} $$

$$ o\leftarrow o+1 $$

$$ c\gets\overrightarrow{P o}S.B l o c k h a s h(X) $$

$$ z\leftarrow\Sigma_{i\in S}z_{i} $$

$$ \sigma^{\prime}\gets\sigma\ H(\mathtt{t x}||R||q)H(p k_{c u r}||c) $$

$$ ,\sigma^{\ ^{\prime}}) $$

$$ v \in S \mathrm {d o} $$

$$ \rho_{k}\gets H_{1}(k,m,B),R_{k}\gets D_{k j}+\rho_{k}E_{k j},R\gets\sum_{k\in S}R_{k},c\gets H_{2}(\mathsf{t r}||R||q) $$

$$ o \leftarrow o + 1 $$

$$ \mathbf{f}\ g^{z}k\neq R_{k}+c\cdot\lambda_{k}\cdot Y_{k} $$

$$ \textsf{-}r r_{c u r} $$

[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.

[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.

[11] Ethereum Foundation. Proof-of-stake (PoS). https://ethereum.org/en/developers/ docs/consensus-mechanisms/pos/, July 2021.

[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.

[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.

Algorithm 4 Verification

[19] J. Groth. Non-interactive distributed key generation and key resharing. Cryptol- ogy 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 Com- puting, 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 multisignatures. 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.