fix: Fix BTCRelay Chain Reorganization to Prioritize Work Over Length #1198

nakul1010 · 2023-09-20T06:58:24Z

Closes #1186.

Code Flow based on discussion in comments

Migrate from v0 to v1 using the migrate_from_v0_to_v1 function:
- This function inserts the chainwork for the latest bitcoin block.
Keep updating the chainwork for historical blocks using the set_chainwork_for_block function:
- The store_block_header extension will take over once it syncs to the latest block, as it will also attempt to update the chainwork.
- Changes on the client side are required for calling the extrinsic set_chainwork_for_block for all the historical bitcoin blocks.
- Retire/Pause the set_chainwork_for_block extension after a successful sync.
The ReOrg will switch from the longest chain to the most work when the chainwork is found for the main chain block as well as the latest block header submitted.

ToDos

Add required methods to switch from the longest chain to the most work
Migration from v0 to v1
Unit Test Cases
Benchmarking

nakul1010 · 2023-09-20T07:00:10Z

The PR 1149 should be merged before merging this PR.

nakul1010 · 2023-09-20T08:39:35Z

@gregdhill for test case store_block_header_simple_fork_succeeds

Problem 1:
When attempting to retrieve the chainwork for the given blockchain:

BlockChain { chain_id: 1, start_height: 1, max_height: 2 }

It emits an error MissingBlockHeight. This error arises because it's trying to obtain the block hash for chain_id: 1, block_height: 0. The problem lies in the design of the storage (ChainHashes), where block 0 is stored with the key chain_id 0 instead of 1. In the Electrum codebase here, the get_hash function only accepts the height parameter and doesn't consider chain_id.

Problem 2:
The same test case will encounter issues when calculating work_in_single_header since the block hash for cached_height 2016 won't be available.

Is the solution to get block_hash irrespective of chain_id by just providing the key as block_height or am i missing out something?

gregdhill · 2023-09-20T12:46:19Z

Problem 1: You can iterate over the previous forks, electrum does that here
Problem 2: You'll have to figure out a good way to test this :) maybe you can mock it or provide some dummy value in the ChainWork storage map

sander2

I'm not sure the current approach is the best, it does a lot of iterating.. Fwiw I initially proposed an iteration-free solution, I think maybe we should consider it @gregdhill :

add a new map of blockhash -> chainwork
add a root-only function, or a function called from a runtime migration, that sets the chainwork of some recent block
add a temporary non-root function that takes a blockheader x, and if x.prev has an associated chainwork, set the chainwork of x. This function will be used to catch up to to the bitcoin chain
in the relay-function: when relaying a block x, if x.prev has associated chainwork, store the new chainwork of x.
add a root-only function that changes chain selection from longest-chain to most-work. We only call this once the chainhead has associated chainwork set

sander2 · 2023-09-22T10:14:28Z

crates/btc-relay/src/lib.rs

+    ///
+    /// * `Result<u32, DispatchError>`: A `Result` containing the calculated cumulative chainwork as a `u32` if
+    ///   successful, or a `DispatchError` if an error occurs during the calculation.
+    fn get_chainwork(chain: BlockChain) -> Result<u32, DispatchError> {


I'm not sure it's a good idea to use the electrum function unchanged. In fact, I don't think it'll work, because

(1) it's super expensive - it iterates all the way from block zero. We might exceed the block time because of all the iteration

(2) We didn't initialize the relay at height 0. The chainwork_of_header_at_height function would fail.

This is a pretty high-risk change, and I would ask you to test it thoroughly. If I'm right and this doesn't work, it could've been caught with a chopsticks test.

yes, reviewing the code back again even if the loop over the target it would still take btc_best_block/2016 ie 808,849 /2016 = 402 iterations. Ideally, the code should have been added from parachain genesis block to avoid iterations. I will still do the chopsticks test and put the results in another comment.

nakul1010 · 2023-09-22T13:54:18Z

add a temporary non-root function that takes a blockheader x, and if x.prev has an associated chainwork, set the chainwork of x. This function will be used to catch up to to the bitcoin chain

@sander2 This approach sounds good. I have a question about the non-root function mentioned in the comment:

I expect the work done formula to remain the same as here, but then the target is a U256 value, and converting it to u32 doesn't make sense, as explained in this fixme. So, can the new mapping be blockhash(H256Le) -> chainwork(U512) type instead of blockhash(H256Le) -> chainwork(u32) which is currently being coded out?

nakul1010 · 2023-09-25T18:47:10Z

Based on the above comments was found that the electrum/summa relay code cannot be imported directly.

New Code Flow:

Migrate from v0 to v1 using the migrate_from_v0_to_v1 function:
- This function inserts the chainwork for the latest block.
Keep updating the chainwork for historical blocks using the set_chainwork_for_block function:
- The store_block_header extension will take over once it syncs to the latest block, as it will also attempt to update the chainwork. However, if it fails, it will not return an error.
- Changes on the client side are required for calling the extrinsic set_chainwork_for_block for all the historical bitcoin blocks.
- Retire/Pause the set_chainwork_for_block extension after a successful sync.
Call the set_most_work_parameter function through governance:
- This will make a switch from the longest chain to the chain with the most work.
- Retire/Pause the set_most_work_parameter extension after a successful sync.

Limitations:

Switching from the longest chain to the chain with the most work using set_most_work_parameter is slightly tricky.
- Since it is a governance call and will be executed in a future block 'n' after migration has been applied to block 'm', Bitcoin blocks mined between 'm' to 'n' para chain blocks need to have chainwork. After executing set_most_work_parameter, the longest chain reorg will be completely skipped, and it will work according to the flow mentioned above, as the store_block_header also attempts to apply chainwork. However, in the case of failure to set chainwork for previous blocks by the client, a safety net should be ideal. This would require adding one more storage to store the latest block, which can be used by the set_most_work_parameter extension, as the parameter can only be set if the latest Bitcoin block has chainwork. What are your thoughts on this @gregdhill and @sander2.
Stored ChainWork as U512 instead of u32 required based on mathematical value 2^256 needed during calculation here.

sander2

Based on the above comments was found that the electrum/summa relay code cannot be imported directly.

New Code Flow:

1. Migrate from v0 to v1 using the `migrate_from_v0_to_v1` function:
   
   * This function inserts the chainwork for the latest block.

2. Keep updating the chainwork for historical blocks using the `set_chainwork_for_block` function:
   
   * The `store_block_header` extension will take over once it syncs to the latest block, as it will also attempt to update the chainwork. However, if it fails, it will not return an error.
   * Changes on the client side are required for calling the extrinsic `set_chainwork_for_block` for all the historical bitcoin blocks.
   * Retire/Pause the `set_chainwork_for_block` extension after a successful sync.

3. Call the `set_most_work_parameter` function through governance:
   
   * This will make a switch from the longest chain to the chain with the most work.
   * Retire/Pause the `set_most_work_parameter` extension after a successful sync.

Limitations:

* Switching from the longest chain to the chain with the most work using `set_most_work_parameter` is slightly tricky.
  
  * Since it is a governance call and will be executed in a future block 'n' after migration has been applied to block 'm', Bitcoin blocks mined between 'm' to 'n' para chain blocks need to have chainwork. After executing `set_most_work_parameter`, the longest chain reorg will be completely skipped, and it will work according to the flow mentioned above, as the `store_block_header` also attempts to apply chainwork. However, in the case of failure to set chainwork for previous blocks by the client, a safety net should be ideal. This would require adding one more storage to store the latest block, which can be used by the `set_most_work_parameter` extension, as the parameter can only be set if the latest Bitcoin block has chainwork. What are your thoughts on this @gregdhill and @sander2.

I think we can do away with set_most_work_parameter and ReOrgAccordingToChainWork. Instead, we can automatically switch over when the mainchain has a known chainwork. The only edge case I can see is if there's an on-going fork at the moment we submit the latest chainwork but that's pretty unlikely so idk if we have to account for that.

* Stored ChainWork as `U512` instead of `u32` required based on mathematical value `2^256` needed during calculation [here](https://github.com/spesmilo/electrum/blob/cee22abcb5544c5a6fa7f8a8108ccda9c32c2e29/electrum/blockchain.py#L586C1-L587C1).

That shouldn't be required, since the formula is work = ((2 ** 256 - target - 1) // (target + 1)) + 1, which is the same as rust's (U256::MAX - target - 1) / (target + 1) + 1 which fits in U256 just fine

sander2 · 2023-09-25T19:27:02Z

crates/btc-relay/src/lib.rs

+        let chain_work = Self::calculate_chainwork(block_header.hash)?;
+
+        //set chain work for the block
+        Self::set_block_chainwork(block_header.hash, chain_work);


nit: I personally don't like getter/setter functions around storage variables if it literally on a wrapper around the get/insert since when reading the code, you have to check the function to see if any logic is hidden there.

nakul1010 · 2023-09-27T05:07:46Z

crates/btc-relay/src/migration.rs

+            ChainWork::<T>::insert(
+                H256Le::from_bytes_le(&[
+                    177, 89, 206, 70, 83, 47, 12, 29, 30, 21, 192, 96, 38, 114, 155, 10, 5, 77, 59, 247, 14, 99, 150,
+                    79, 228, 250, 72, 71, 124, 92, 197, 19,
+                ]),
+                U256::zero(),
+            );


This adds a headache since different hash and chainwork need to be provided when updating the testnet and mainnet. Is there any smart way to do this?
Require for doing chopsticks migration test as well

nakul1010 · 2023-09-27T05:11:01Z

crates/btc-relay/src/lib.rs

@@ -903,6 +962,11 @@ impl<T: Config> Pallet<T> {

        Self::store_rich_header(basic_block_header.clone(), block_height, blockchain.chain_id);

+        // Add chainwork for block if prev block contains chainwork
+        if Self::contains_chainwork(basic_block_header.hash_prev_block) {
+            Self::_set_chainwork_for_block(basic_block_header)?;


the if condition is required as after migration there will be bitcoin blocks that will not have a chainwork, the relayer would require some block time to successfully sync the chainwork for the latest BTC block.

nakul1010 added the inProgress The PR is still in progress label Sep 20, 2023

nakul1010 self-assigned this Sep 20, 2023

nakul1010 changed the base branch from master to nakul/feat_update_to_v1 September 20, 2023 06:59

Base automatically changed from nakul/feat_update_to_v1 to master September 20, 2023 09:58

fix: BTCRelay Chain Reorganization to Prioritize Work Over Length

d5794fe

nakul1010 force-pushed the nakul/fix_btc_relay branch from 74fc174 to d5794fe Compare September 22, 2023 08:59

nakul1010 changed the title ~~fix(wip): Fix BTCRelay Chain Reorganization to Prioritize Work Over Length~~ fix: Fix BTCRelay Chain Reorganization to Prioritize Work Over Length Sep 22, 2023

nakul1010 added ReviewNeeded The PR can be reviewed by peers and removed inProgress The PR is still in progress labels Sep 22, 2023

nakul1010 requested review from gregdhill and sander2 September 22, 2023 09:04

sander2 reviewed Sep 22, 2023

View reviewed changes

sander2 reviewed Sep 25, 2023

View reviewed changes

fix: changed approach, remove looping

b651ab3

nakul1010 force-pushed the nakul/fix_btc_relay branch from d1e245c to b651ab3 Compare September 27, 2023 04:59

nakul1010 commented Sep 27, 2023

View reviewed changes

nakul1010 requested a review from sander2 September 27, 2023 05:13

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix: Fix BTCRelay Chain Reorganization to Prioritize Work Over Length #1198

fix: Fix BTCRelay Chain Reorganization to Prioritize Work Over Length #1198

nakul1010 commented Sep 20, 2023 •

edited

nakul1010 commented Sep 20, 2023 •

edited

nakul1010 commented Sep 20, 2023 •

edited

gregdhill commented Sep 20, 2023

sander2 left a comment

sander2 Sep 22, 2023 •

edited

nakul1010 Sep 22, 2023 •

edited

nakul1010 commented Sep 22, 2023 •

edited

nakul1010 commented Sep 25, 2023 •

edited

sander2 left a comment

sander2 Sep 25, 2023

nakul1010 Sep 26, 2023

nakul1010 Sep 27, 2023 •

edited

nakul1010 Sep 27, 2023

fix: Fix BTCRelay Chain Reorganization to Prioritize Work Over Length #1198

Are you sure you want to change the base?

fix: Fix BTCRelay Chain Reorganization to Prioritize Work Over Length #1198

Conversation

nakul1010 commented Sep 20, 2023 • edited

Code Flow based on discussion in comments

ToDos

nakul1010 commented Sep 20, 2023 • edited

nakul1010 commented Sep 20, 2023 • edited

gregdhill commented Sep 20, 2023

sander2 left a comment

Choose a reason for hiding this comment

sander2 Sep 22, 2023 • edited

Choose a reason for hiding this comment

nakul1010 Sep 22, 2023 • edited

Choose a reason for hiding this comment

nakul1010 commented Sep 22, 2023 • edited

nakul1010 commented Sep 25, 2023 • edited

sander2 left a comment

Choose a reason for hiding this comment

sander2 Sep 25, 2023

Choose a reason for hiding this comment

nakul1010 Sep 26, 2023

Choose a reason for hiding this comment

nakul1010 Sep 27, 2023 • edited

Choose a reason for hiding this comment

nakul1010 Sep 27, 2023

Choose a reason for hiding this comment

nakul1010 commented Sep 20, 2023 •

edited

nakul1010 commented Sep 20, 2023 •

edited

nakul1010 commented Sep 20, 2023 •

edited

sander2 Sep 22, 2023 •

edited

nakul1010 Sep 22, 2023 •

edited

nakul1010 commented Sep 22, 2023 •

edited

nakul1010 commented Sep 25, 2023 •

edited

nakul1010 Sep 27, 2023 •

edited