Skip to content
This repository has been archived by the owner on Jun 11, 2024. It is now read-only.

Latest commit

聽

History

History
162 lines (101 loc) 路 19.8 KB

lip-0035.md

File metadata and controls

162 lines (101 loc) 路 19.8 KB
Raw
LIP: 0035
Title: Define decentralized snapshot and hardfork process
Author: Jan Hackfeld <jan.hackfeld@lightcurve.io>
        Nazar Hussain <nazar@lightcurve.io>
Discussions-To: https://research.lisk.com/t/define-decentralized-snapshot-and-hardfork-process/222
Status: Replaced
Type: Standards Track
Created: 2020-04-08
Updated: 2024-01-04
Requires: 0017, 0018, 0020, 0030, 0031, 0034
Superseded-By: 0063

Abstract

This LIP defines how a unique snapshot block can be computed from the Lisk mainnet blockchain up to a certain height. This block follows the schema introduced in LIP 0034 and, in particular, contains the state of all accounts. This yields a snapshot mechanism that can be used to perform a hardfork on the Lisk mainnet as all Lisk mainnet nodes can independently compute the snapshot block at the same time. The additional benefit of such a snapshot block is that nodes can directly synchronize from this block instead of having to synchronize from the original genesis block of the Lisk blockchain. This enables an implementation that is only partially backwards compatible, i.e., it can apply blocks and transactions following the latest version of the protocol, but cannot apply blocks and transactions from previous protocol versions.

Copyright

This LIP is licensed under the Creative Commons Zero 1.0 Universal.

Motivation

As part of the Lisk roadmap, several fundamental protocol changes are planned for Lisk mainnet: a change of the consensus algorithm, address and ID system as well as the introduction of dynamic fees. Maintaining one implementation that is fully compatible with very different protocols can be complex and error-prone. Moreover, conducting a hardfork to a new very different protocol can be complex. This LIP therefore suggests an approach that simplifies handling such protocol changes.

By defining how to compute a unique snapshot block from the Lisk mainnet blockchain, we define a simple interface between the old and new protocol. The implementation of the new protocol only needs to be able to process the snapshot block, but there are no other dependencies on the old protocol. Similarly, the current Lisk mainnet implementation only needs to be able to compute the correct snapshot block and does not require other changes for the hardfork.

This approach also allows that the implementation of the new protocol is only partially backwards compatible, i.e., cannot verify and apply state transitions (transactions and block headers) following previous versions of the protocol. This implies that a user would need to use two different implementations to verify all state transitions of the Lisk blockchain starting from the genesis block. First, the user has to use one implementation that can apply all blocks from the genesis block up to the snapshot block. Afterwards, the user can use the latest implementation that can apply all state transitions from the snapshot block onwards.

Specification

In this section, we define how the snapshot block is computed and how it can be used to conduct a decentralized snapshot and hardfork on the Lisk mainnet.

Snapshot Block

Let HEIGHT_SNAPSHOT be a constant defining the height at which the snapshot of the state of the Lisk mainnet blockchain is supposed to be performed (to be defined at the time of release). In this section, we describe how to compute a snapshot block b, which obeys the schema defined in LIP 0034, from the state of the Lisk mainnet blockchain after processing the block at height HEIGHT_SNAPSHOT. We assume that the block at height HEIGHT_SNAPSHOT is the last block of a round.

General Block Properties

Let a be the block at height HEIGHT_SNAPSHOT.

  • The value of b.header.timestamp is set by converting a.header.timestamp+7200 to Unix time and rounding down to a multiple of 10.
  • The value of b.header.height is the height of a plus 1.
  • The value of b.header.previousBlockID is computed as follows. For every block from height 1 (genesis block of Lisk mainnet) to height HEIGHT_SNAPSHOT, let blockHash be the 256 bit block hash computed according to LIP 0020. Let blockHashArray be the array of bytes containing the blockHash values of all blocks from height 1 to HEIGHT_SNAPSHOT (inclusive) ordered ascending by height. Then b.header.previousBlockID is the 256 bit Merkle root generated from blockHashArray according to LIP 0031.

The values of the properties in b.header.asset are described in the next sections. All other properties have the value required in LIP 0034.

Account State

This section describes how the array of account states provided in b.header.asset.accounts is computed.

The state of an account on the Lisk mainnet after applying the block at height HEIGHT_SNAPSHOT is specified following the schema defined in LIP 0030 and then serialized accordingly. The required properties of an account are set as follows:

  • The value of the address property of an account is the 20-byte value specified in LIP 0018 if the account has a registered public key. Otherwise, it is the 8-byte value of the legacy address.
  • The value of the balance property is the account balance in Beddows.
  • The value of the nonce property is 0.
  • The values in the keys object are set as described in Section "Converting Existing Accounts" in LIP 0017 if the account performed a second signature registration or a multisignature registration. Otherwise, all properties in the keys object are set to the default values.
  • The properties in the delegate object in the account asset are set to the default values if the account has not registered as delegate. If the account is registered as delegate, then the properties are set as follows:
    • The value of username is the username of the delegate.
    • The value of pomHeights is the empty array.
    • The value of consecutiveMissedBlocks is 0.
    • The value of lastForgedHeight is set to b.header.height.
    • The value of isBanned is false.
    • The value of totalVotesReceived is 0.
  • The array sentVotes in the account asset is set to the empty array.
  • The array unlocking in the account asset is set to the empty array.

In order to ensure the uniqueness of the account state and handle non-unique string representations of Lisk addresses in the past, we additionally perform the following steps:

  • Discard any account without incoming transaction (such accounts cannot have any balance).
  • Discard the so-called Genesis Account with public key d121d3abf5425fdc0f161d9ddb32f89b7750b4bdb0bff7d18b191d4b4bafa6d4 (Lisk address 6566229458323231555L in the old format), which has a negative balance.
  • Migrate every account, except the Genesis Account and any account without incoming transaction, as follows.
    • If the string representation of the account address in Lisk Core 2.0 is standard (The string is 0L or does not start with 0. The decimal number is between 0 and 2^64-1 inclusive), then the account is migrated as defined above. If the account has at least one outgoing transaction, then the migrated account has a 20-byte address and otherwise it has an 8-byte address.
    • If the string representation of the account address in Lisk Core 2.0 is non-standard (it is not OL, but starts with 0. Or the decimal number is larger than 2^64-1), the address corresponds to one unique 8-byte address, denoted by legacyAddress, which are the 8 bytes signed in the transaction creating the account. Note that the account cannot have any outgoing transaction as the string representation is non-standard. The non-standard account acc_non_standard is migrated as follows to ensure that all accounts with the same legacyAddress value are migrated to the same account:
      • If there is an account acc_standard with an address in standard string representation corresponding to the same legacyAddress, then the balance of acc_non_standard is added to the balance of the migrated account acc_standard. Note that the migrated account acc_standard may have an 8-byte address or a 20-byte address.
      • If there is no other account with an address in standard string representation corresponding to legacyAddress, then the balance of acc_non_standard is added to the migrated account with address legacyAddress and all properties set to default. Note that there can be multiple non-standard accounts that need to be merged to the same account (e.g., 04L and 88888888888888888888L).

We define the order of accounts in the array b.header.asset.accounts as follows:

  • Any account with 8-byte address comes before any account with 20-byte address.
  • For any two accounts with 8-byte address, the one with lexicographically smaller address comes first.
  • For any two accounts with 20-byte address, the one with lexicographically smaller address comes first.

Initial Delegates and Rounds

This section describes how the values provided in b.header.asset.initDelegates and b.header.asset.initRounds are computed.

The byte array b.header.asset.initDelegates contains the 20-byte addresses of the 103 delegates with largest delegate weight at height HEIGHT_SNAPSHOT according to the DPoS system active on the Lisk mainnet at that height where ties are broken in favor of lexicographically smaller 20-byte address. The delegates in the array are ordered descending by delegate weight where ties again are broken in favor of lexicographically smaller 20-byte address. The value of b.header.asset.initRounds is 600 (600 rounds are approximately 7 days assuming no missed blocks).

Decentralized Snapshot and Hardfork Process

In this section, we describe the process of every node in the Lisk mainnet computing the snapshot block specified above and using this block for performing a hardfork.

  1. After processing the block a at height HEIGHT_SNAPSHOT, the Lisk mainnet node duplicates the account table to have a snapshot of the account state at this height. It also computes and persists the top 103 delegates by total vote weight, where ties are broken in favor of lexicographically smaller 20-byte address.

  2. After 201 subsequent blocks are built on a, the node computes the snapshot block b as specified in the previous section.

  3. A new node can be started running an implementation of the new protocol with the snapshot block b as input. The node processes b as defined in LIP 0034 and afterwards processes new blocks according to the new protocol.

After the hardfork and after the snapshot block b is finalized, the implementation of the new protocol can provide the following two options for new nodes joining the network:

  • Start the node using a snapshot block that is computed with an implementation of the previous protocol (as described above).
  • Request the snapshot block from the network and check that it matches the hardcoded block ID of the snapshot block b.

Rationale

Uniqueness of Snapshot Block

One important requirement for the decentralized snapshot is that every node that has the same blockchain from height 1 to height HEIGHT_SNAPSHOT computes the same snapshot block b. Otherwise, different snapshot blocks would lead to a network split, which could be difficult to resolve.

For all nodes with the same blockchain from height 1 to height HEIGHT_SNAPSHOT clearly the values of b.header.timestamp, b.header.height and b.header.previousBlockID must be the same. If the blockchain up to height HEIGHT_SNAPSHOT is the same, also the balances and votes must be the same. This implies that b.header.asset.initDelegates must be the same as we use uniform tie-breaking by smaller address. Clearly, also b.header.asset.initRounds is the same.

Moreover, LIP 0030 defines a unique way to serialize an account given that all account properties are the same. Hence, if two nodes have an identical set of accounts with identical properties, the value of b.header.asset.accounts must be the same as we define a unique ordering of accounts. In the following, we argue why for two Lisk nodes the set of migrated accounts and their properties must be identical using the migration described in the specification.

First of all, note that for any two Lisk Core 2.0 nodes the serialized blockchain data must be the same as any change of the serialized data would invalidate signatures and block hashes (assuming no hash collision exists). Any transaction affecting an account (because the account is sender or recipient) contains the 8-byte account address in the serialized transaction. This means that the set of 8-byte addresses must be the same for any two nodes as an address only exists if it has at least one incoming balance transfer.

Moreover, for a balance transfer the amount is contained in the serialization, for a delegate registration the delegate name and for second-signature or multi-signature registration the public keys. Additionally, the fee is fixed for every transaction type and the sender public key is also serialized. This means that for any two nodes, the migrated properties associated to an 8-byte address (balance, multisignature keys, delegate username) must be the same. Also the address of the migrated account must be identical for any two nodes, as it is either the original 8-byte address or the 20-byte address computed from the account's public key if the account had a least one outgoing transaction.

However, Lisk Core 2.0 stores 8-byte addresses as strings using decimal representation with appended L. Due to past bugs, this representation was not unique so multiple accounts with different string representation corresponding to the same 8-byte address (e.g., 4L, 04L and 88888888888888888888L) are stored in most Lisk Core 2.0 nodes. The migration given in the specification ensures that in this case these accounts are merged to one account corresponding to the 8-byte address that is part of the serialized blockchain.

As an additional precaution, we suggest to perform at least one off-chain test run where delegates compute the snapshot block for a height smaller than HEIGHT_SNAPSHOT and the block ID of this snapshot block is compared off-chain.

Security Implications

Assuming that SHA256 is a cryptographic hash function, then the 256 bit block ID of the snapshot block b, computed according to LIP 0020 and denoted by SNAPSHOT_BLOCK_ID, fully authenticates the complete account state at height HEIGHT_SNAPSHOT, the sequence of blocks from height 1 to height HEIGHT_SNAPSHOT and all included transactions. All relevant hash operations used for computing SNAPSHOT_BLOCK_ID utilize 256 bit digests which yield 256 bits preimage resistance. Note that although previous block IDs are only 64 bit long, we use full 256 bit hashes of the block header for the block tree. Similarly, the payload hash of a block also has 256 bit length and is computed from the full serialized transactions in a block (not from the 64 bit transaction IDs). Nodes that do not compute the snapshot block from the whole Lisk blockchain from height 1 to height HEIGHT_SNAPSHOT themselves, have to obtain it or its block ID from a trusted source. That is why we suggest to hardcode the block ID SNAPSHOT_BLOCK_ID once the snapshot block is finalized in order to let new nodes join the network without having to compute the snapshot block.

Choice of Parameters

In this section, we want to justify the choice for some free parameters in the snapshot block that are chosen to ensure a smooth and robust snapshot and hardfork process. Most properties of the snapshot block are simply dictated by the fact that the block is a snapshot of the blockchain state at a certain height.

  • We change timestamps to Unix time in the Lisk protocol to follow a well-known standard. Therefore, b.header.timestamp is set by converting a.header.timestamp+7200 to Unix time and rounding down to a multiple of 10. The rounding ensures that the starting time of a block slot is always divisible by 10. Adding 7200 implies that there is a gap of 2 hours with no blocks between a and b. This is to ensure that nodes can first wait for 201 subsequent blocks to be built on a (this takes about 34 minutes assuming no missed block) and then there is sufficient time for all nodes to compute the snapshot block b. The gap of 2 hours avoids that there is a large number of missed blocks after the hardfork. The offset of 7200 can be adjusted once there is an implementation for computing the snapshot block that can be benchmarked.
  • For a smooth transition from the current voting system in the Lisk mainnet to the new voting system (see LIP 0022 and LIP 0023) we propose to fix the top 103 delegates for around 7 days. This period should be long enough for the majority of stake to vote using the new vote transaction. Having the delegates selected by the new voting system already after a few rounds could imply drastic changes in the delegate set in the first rounds and would increase the risk for long range attacks.

Historic Blocks and Transactions

Nodes running an implementation of the new protocol would only store blocks from height HEIGHT_SNAPSHOT+1 onwards. Blocks from height 1 to HEIGHT_SNAPSHOT and the included transactions could still be provided by nodes running the old protocol. Moreover, it would be easy to provide users with a tool that can verify if a given sequence of blocks from height 1 to HEIGHT_SNAPSHOT belongs to the Lisk blockchain as the same computation is already required for the snapshot block.

Considered Alternatives

In this section, we describe some alternative discarded solutions that would also allow to create a snapshot of the blockchain state and could simplify handling protocol changes.

Centralized Snapshot

One simple solution would be to perform a centralized snapshot at a previously announced height and release an implementation of the new protocol including a new genesis block. Every node in the network would be free to verify the correctness of the genesis block. The advantage would be that it is much less likely that the network could split as only one party computes the genesis block. The centralization is also the main disadvantage as it means that only few entities may actually verify the correctness of the genesis block.

Account Tree

Another possible solution would be to include hashes that authenticate the account states and block history as part of every block. Then a decentralized snapshot could be performed at any height without a specific snapshot block. This would, however, require more complex data structures such as Sparse Merkle Trees and Patricia Tree to be able to quickly compute the updated hash authenticating the new states of the accounts. Such a change would also need to be implemented first as a hardfork before it could be used to simplify the process for future hardforks. Additionally, a different storage layer would likely be necessary for sufficient performance. Due to this overall complexity, this solution was discarded.

Backwards Compatibility

This LIP describes the protocol and process for conducting a hardfork on the Lisk mainnet.

Reference Implementation

Define decentralized snapshot and hardfork process #1