1, k is the number of the max number of uncles

2, the block is qualified if it is not the ancestor of tips
starcoinorg · Mar 20, 2024 · 99281d9 · 99281d9
1 parent 9b3c74e
commit 99281d9
Show file tree

Hide file tree

Showing 8 changed files with 74 additions and 5 deletions.
diff --git a/chain/src/chain.rs b/chain/src/chain.rs
@@ -1335,7 +1335,9 @@ impl BlockChain {
             for hash in parents {
                 tips.retain(|x| *x != hash);
             }
-            tips.push(new_tip_block.id());
+            if !dag.check_ancestor_of(new_tip_block.id(), tips.clone())? {
+                tips.push(new_tip_block.id());
+            }
         }
         // Caculate the ghostdata of the virutal node created by all tips.
         // And the ghostdata.selected of the tips will be the latest head.

diff --git a/config/src/genesis_config.rs b/config/src/genesis_config.rs
@@ -693,7 +693,7 @@ static G_DEFAULT_BASE_BLOCK_DIFF_WINDOW: u64 = 24;
 static G_BASE_REWARD_PER_UNCLE_PERCENT: u64 = 10;
 static G_MIN_BLOCK_TIME_TARGET: u64 = 5000;
 static G_MAX_BLOCK_TIME_TARGET: u64 = 60000;
-static G_BASE_MAX_UNCLES_PER_BLOCK: u64 = 2;
+pub static G_BASE_MAX_UNCLES_PER_BLOCK: u64 = 2;
 
 pub static G_TOTAL_STC_AMOUNT: Lazy<TokenValue<STCUnit>> =
     Lazy::new(|| STCUnit::STC.value_of(3185136000));

diff --git a/flexidag/dag/src/blockdag.rs b/flexidag/dag/src/blockdag.rs
@@ -77,6 +77,10 @@ impl BlockDAG {
         Ok(self.storage.header_store.has(hash)?)
     }
 
+    pub fn check_ancestor_of(&self, ancestor: Hash, descendant: Vec<Hash>) -> anyhow::Result<bool> {
+        self.ghostdag_manager.check_ancestor_of(ancestor, descendant)
+    } 
+
     pub fn init_with_genesis(&mut self, genesis: BlockHeader) -> anyhow::Result<()> {
         let genesis_id = genesis.id();
         let origin = genesis.parent_hash();

diff --git a/flexidag/dag/src/ghostdag/protocol.rs b/flexidag/dag/src/ghostdag/protocol.rs
@@ -67,6 +67,10 @@ impl<
         ))
     }
 
+    pub fn check_ancestor_of(&self, ancestor: Hash, descendant: Vec<Hash>) -> anyhow::Result<bool> {
+        self.reachability_service.is_dag_ancestor_of_any_result(ancestor, &mut descendant.into_iter()).map_err(|e| e.into())
+    }
+
     pub fn find_selected_parent(
         &self,
         parents: impl IntoIterator<Item = Hash>,

diff --git a/flexidag/dag/src/reachability/reachability_service.rs b/flexidag/dag/src/reachability/reachability_service.rs
@@ -16,6 +16,7 @@ pub trait ReachabilityService {
         list: &mut impl Iterator<Item = Hash>,
         queried: Hash,
     ) -> Result<bool>;
+    fn is_dag_ancestor_of_any_result(&self, this: Hash, queried: &mut impl Iterator<Item = Hash>) -> Result<bool>;
     fn get_next_chain_ancestor(&self, descendant: Hash, ancestor: Hash) -> Hash;
 }
 
@@ -71,6 +72,17 @@ impl<T: ReachabilityStoreReader + ?Sized> ReachabilityService for MTReachability
         queried.any(|hash| inquirer::is_dag_ancestor_of(read_guard.deref(), this, hash).unwrap())
     }
 
+    fn is_dag_ancestor_of_any_result(&self, this: Hash, queried: &mut impl Iterator<Item = Hash>) -> Result<bool> {
+        let read_guard = self.store.read();
+        queried.try_fold(false, |acc, descendant| {
+            if acc {
+                Ok(true)
+            } else {
+                inquirer::is_dag_ancestor_of(read_guard.deref(), this, descendant).map(|is_ancestor| acc || is_ancestor)
+            }
+        })
+    }
+
     fn get_next_chain_ancestor(&self, descendant: Hash, ancestor: Hash) -> Hash {
         let read_guard = self.store.read();
         inquirer::get_next_chain_ancestor(read_guard.deref(), descendant, ancestor).unwrap()

diff --git a/flexidag/dag/tests/tests.rs b/flexidag/dag/tests/tests.rs
@@ -4,10 +4,10 @@
 mod tests {
     use anyhow::{bail, Ok};
     use starcoin_config::RocksdbConfig;
-    use starcoin_dag::{blockdag::BlockDAG, consensusdb::{consenses_state::{DagState, DagStateReader, DagStateStore}, prelude::{FlexiDagStorage, FlexiDagStorageConfig}, schemadb::ReachabilityStoreReader}, reachability::{inquirer, ReachabilityError}};
+    use starcoin_dag::{blockdag::BlockDAG, consensusdb::{consenses_state::{DagState, DagStateReader, DagStateStore}, prelude::{FlexiDagStorage, FlexiDagStorageConfig}, schemadb::ReachabilityStoreReader}, reachability::{inquirer, reachability_service::ReachabilityService, ReachabilityError}};
     use starcoin_types::{block::{set_test_flexidag_fork_height, BlockHeader, BlockHeaderBuilder}, blockhash::KType};
     use std::{env, fs};
-    use starcoin_crypto::HashValue as Hash;
+    use starcoin_crypto::{hash, HashValue as Hash};
 
     fn build_block_dag(k: KType) -> BlockDAG {
         let db_path = env::temp_dir().join("smolstc");
@@ -343,4 +343,43 @@ mod tests {
 
       Ok(())
     }
+
+    #[test]
+    fn test_reachability_check_ancestor() -> anyhow::Result<()> {
+      let dag = BlockDAG::create_for_testing().unwrap();
+      let mut reachability_store = dag.storage.reachability_store.clone();
+
+      let mut parent = Hash::random();
+      let origin = parent;
+      let mut child = Hash::random();
+      inquirer::init(&mut reachability_store, parent)?;
+      inquirer::add_block(&mut reachability_store, child, parent, &mut vec![parent].into_iter())?;
+
+      let mut target = child;
+      for i in 0..70 {
+        parent = child;
+        child = Hash::random();
+
+        if i == 47 {
+            inquirer::add_block(&mut reachability_store, child, parent, &mut vec![parent].into_iter())?;
+
+            target = child;
+        } else {
+            inquirer::add_block(&mut reachability_store, child, parent, &mut vec![parent].into_iter())?;
+        }
+      }
+
+      // ancestor
+      assert!(dag.check_ancestor_of(target, vec![parent, child])?, "failed to check target is the ancestor of its descendant");
+      assert!(dag.check_ancestor_of(origin, vec![target, parent, child])?, "failed to check origin is the parent of its child");
+
+      // not ancestor
+      assert!(!dag.check_ancestor_of(child, vec![target])?, "failed to check child is not the ancestor of its descendant");
+      assert!(!dag.check_ancestor_of(parent, vec![target])?, "failed to check child is not the ancestor of its descendant");
+
+      assert!(dag.check_ancestor_of(target, vec![Hash::random(), Hash::random(),]).is_err(), "failed to check not the ancestor of descendants");
+      assert!(dag.check_ancestor_of(Hash::random(), vec![target, parent, child]).is_err(), "failed to check not the descendant of parents");
+
+      Ok(())
+    }
 }
diff --git a/node/src/node.rs b/node/src/node.rs
@@ -16,6 +16,7 @@ use starcoin_account_service::{AccountEventService, AccountService, AccountStora
 use starcoin_block_relayer::BlockRelayer;
 use starcoin_chain_notify::ChainNotifyHandlerService;
 use starcoin_chain_service::ChainReaderService;
+use starcoin_config::genesis_config::G_BASE_MAX_UNCLES_PER_BLOCK;
 use starcoin_config::NodeConfig;
 use starcoin_genesis::{Genesis, GenesisError};
 use starcoin_logger::prelude::*;
@@ -52,6 +53,7 @@ use starcoin_sync::sync::SyncService;
 use starcoin_sync::txn_sync::TxnSyncService;
 use starcoin_sync::verified_rpc_client::VerifiedRpcClient;
 use starcoin_txpool::{TxPoolActorService, TxPoolService};
+use starcoin_types::blockhash::KType;
 use starcoin_types::system_events::{SystemShutdown, SystemStarted};
 use starcoin_vm_runtime::metrics::VMMetrics;
 use std::sync::Arc;
@@ -319,7 +321,7 @@ impl NodeService {
             config.storage.dag_dir(),
             config.storage.clone().into(),
         )?;
-        let dag = starcoin_dag::blockdag::BlockDAG::new(8, dag_storage.clone());
+        let dag = starcoin_dag::blockdag::BlockDAG::new(KType::try_from(G_BASE_MAX_UNCLES_PER_BLOCK)?, dag_storage.clone());
         registry.put_shared(dag.clone()).await?;
         let (chain_info, genesis) =
             Genesis::init_and_check_storage(config.net(), storage.clone(), dag, config.data_dir())?;

diff --git a/sync/src/tasks/block_sync_task.rs b/sync/src/tasks/block_sync_task.rs
@@ -369,8 +369,14 @@ where
         }
         for parent in parents {
             if !self.chain.has_dag_block(parent)? {
+                if absent_blocks.contains(&parent) {
+                    continue;
+                }
                 absent_blocks.push(parent)
             } else {
+                if ancestors.contains(&parent) {
+                    continue;
+                }
                 ancestors.push(parent);
             }
         }