Define decentralized snapshot and hardfork process

Blocks
1

Hello everyone,

In this thread, I want to propose the second LIP for the roadmap objective “Introduce decentralized re-genesis”. This LIP defines how a unique snapshot block can be computed from the Lisk mainnet blockchain up to a certain height. 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.

I’m looking forward to your feedback.

Here is the complete LIP draft:

LIP: <LIP number>
Title: Define decentralized snapshot and hardfork process
Author: Jan Hackfeld <jan.hackfeld@lightcurve.io>
        Nazar Hussain <nazar@lightcurve.io>
Type: Standards Track
Created: <YYYY-MM-DD>
Updated: <YYYY-MM-DD>
Requires: 0017, 0018, 0020, 0030, 0031, 003X

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 “Define genesis block schema and processing” 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 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 “Define genesis block schema and processing”, 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 “Define genesis block schema and processing”.

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 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 publicKey is the 32-byte public key if the account has a registered public key and 0 bytes otherwise.
  • 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 votes 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, we perform the following additional checks:

  • Ensure that an account only has an associated public key if and only if there is at least one outgoing transaction from that account.
  • Ensure that there is no account with no incoming transaction.
  • Ensure that there is at most one account for every 8-byte binary address (legacy address format).
    This means that if two accounts have different string addresses corresponding to the same 8-byte address (e.g., 123L and 0123L), they are merged by adding the respective balances. If one of the accounts has a registered public key, then this is the public key of the merged account.

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.

Additionally, the so-called Genesis Account with public key d121d3abf5425fdc0f161d9ddb32f89b7750b4bdb0bff7d18b191d4b4bafa6d4 (Lisk address 6566229458323231555L in the old format) is removed.

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 vote weight at height HEIGHT_SNAPSHOT according to the DPoS system active on Lisk mainnet at that height. The delegates in the array are ordered descending by the total vote weight, where ties are broken in favor of lexicographically smaller 20-byte address (similarly to LIP 0022). 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 “Define genesis block schema and processing” 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 all rows in the accounts table are the same for two nodes, the value of b.header.asset.accounts must be the same as we define a unique ordering of accounts.

However, due to past bugs or inconsistent database migrations, there could be minor inconsistencies between the account tables of nodes in the network. That is why we perform the additional consistency checks for all accounts as described in the specifications. Moreover, 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 dictacted 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 build 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 Lisk mainnet.

Reference Implementation

TBD.

2

I created the pull request for this proposal with two small modifications compared to the proposal approve:

  • Changed ‘votes’ to ‘sentVotes’ according to the account schema modification.
  • Clarified the tie-breaking used to compute initDelegates.
3

I created the following PR with some minor changes to the LIP as the public key property of accounts was removed.

4

I created the following PR to clarify the migration of accounts in the case of non-standard string representations of addresses.

5

The PR above was merged today.