From 0549867239f9b0cec8a384e18c19ea89815a3962 Mon Sep 17 00:00:00 2001 From: Poseidon Date: Wed, 16 Jun 2021 14:36:36 +0800 Subject: [PATCH] fix_duplicate_checkpoint (#1965) * fix_duplicate_checkpoint * simplify code * fix ci --- protocol/apply_block.go | 39 ++++++------------------------------ protocol/state/checkpoint.go | 45 ++++++++++++++++++++++++++++++++++++++++++ protocol/tree_node.go | 20 +++++++++++++------ protocol/tree_node_test.go | 47 ++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 112 insertions(+), 39 deletions(-) create mode 100644 protocol/tree_node_test.go diff --git a/protocol/apply_block.go b/protocol/apply_block.go index 3f53293d..ccd59a83 100644 --- a/protocol/apply_block.go +++ b/protocol/apply_block.go @@ -71,21 +71,7 @@ func (c *Casper) applyBlockToCheckpoint(block *types.Block) (*state.Checkpoint, checkpoint := node.checkpoint if mod := block.Height % state.BlocksOfEpoch; mod == 1 { parent := checkpoint - checkpoint = &state.Checkpoint{ - ParentHash: parent.Hash, - Parent: parent, - Status: state.Growing, - Rewards: make(map[string]uint64), - Votes: make(map[string]uint64), - Guaranties: make(map[string]uint64), - } - - for pubKey, num := range parent.Votes { - checkpoint.Votes[pubKey] = num - } - for pubKey, num := range parent.Guaranties { - checkpoint.Guaranties[pubKey] = num - } + checkpoint = state.NewCheckpoint(parent) node.addChild(&treeNode{checkpoint: checkpoint}) } else if mod == 0 { checkpoint.Status = state.Unjustified @@ -98,10 +84,7 @@ func (c *Casper) applyBlockToCheckpoint(block *types.Block) (*state.Checkpoint, return nil, err } - checkpoint.Height = block.Height - checkpoint.Hash = block.Hash() - checkpoint.Timestamp = block.Timestamp - return checkpoint, nil + return checkpoint, checkpoint.Increase(block) } func (c *Casper) checkpointNodeByHash(blockHash bc.Hash) (*treeNode, error) { @@ -137,17 +120,7 @@ func (c *Casper) replayCheckpoint(hash bc.Hash) (*treeNode, error) { return nil, err } - node := &treeNode{ - checkpoint: &state.Checkpoint{ - ParentHash: parent.checkpoint.Hash, - Parent: parent.checkpoint, - Status: state.Growing, - Rewards: make(map[string]uint64), - Votes: make(map[string]uint64), - Guaranties: make(map[string]uint64), - }, - } - + node := &treeNode{checkpoint: state.NewCheckpoint(parent.checkpoint)} parent.addChild(node) for _, attachBlock := range attachBlocks { if err := applyTransactions(node.checkpoint, attachBlock.Transactions); err != nil { @@ -158,9 +131,9 @@ func (c *Casper) replayCheckpoint(hash bc.Hash) (*treeNode, error) { return nil, err } - node.checkpoint.Hash = attachBlock.Hash() - node.checkpoint.Height = attachBlock.Height - node.checkpoint.Timestamp = attachBlock.Timestamp + if err := node.checkpoint.Increase(attachBlock); err != nil { + return nil, err + } } return node, nil } diff --git a/protocol/state/checkpoint.go b/protocol/state/checkpoint.go index a55700fe..30eda474 100644 --- a/protocol/state/checkpoint.go +++ b/protocol/state/checkpoint.go @@ -5,7 +5,9 @@ import ( "github.com/bytom/bytom/config" "github.com/bytom/bytom/consensus" + "github.com/bytom/bytom/errors" "github.com/bytom/bytom/protocol/bc" + "github.com/bytom/bytom/protocol/bc/types" ) const ( @@ -31,6 +33,8 @@ const ( Finalized ) +var errIncreaseCheckpoint = errors.New("invalid block for increase checkpoint") + // SupLink is an ordered pair of checkpoints (a, b), also written a → b, // such that at least 2/3 of validators have published votes with source a and target b. type SupLink struct { @@ -67,6 +71,28 @@ type Checkpoint struct { Rewards map[string]uint64 // controlProgram -> num of reward Votes map[string]uint64 // pubKey -> num of vote Guaranties map[string]uint64 // pubKey -> num of guaranty + + MergeCheckpoint func(bc.Hash) `json:"-"` +} + +// NewCheckpoint create a new checkpoint instance +func NewCheckpoint(parent *Checkpoint) *Checkpoint { + checkpoint := &Checkpoint{ + ParentHash: parent.Hash, + Parent: parent, + Status: Growing, + Rewards: make(map[string]uint64), + Votes: make(map[string]uint64), + Guaranties: make(map[string]uint64), + } + + for pubKey, num := range parent.Votes { + checkpoint.Votes[pubKey] = num + } + for pubKey, num := range parent.Guaranties { + checkpoint.Guaranties[pubKey] = num + } + return checkpoint } // AddVerification add a valid verification to checkpoint's supLink @@ -97,6 +123,25 @@ func (c *Checkpoint) ContainsVerification(validatorOrder int, sourceHash *bc.Has return false } +// Increase will increase the height of checkpoint +func (c *Checkpoint) Increase(block *types.Block) error { + empty := bc.Hash{} + prevHash := c.Hash + if c.Hash == empty { + prevHash = c.ParentHash + } + + if block.PreviousBlockHash != prevHash { + return errIncreaseCheckpoint + } + + c.Hash = block.Hash() + c.Height = block.Height + c.Timestamp = block.Timestamp + c.MergeCheckpoint(c.Hash) + return nil +} + // Validator represent the participants of the PoS network // Responsible for block generation and verification type Validator struct { diff --git a/protocol/tree_node.go b/protocol/tree_node.go index ac0b7e45..c006ac84 100644 --- a/protocol/tree_node.go +++ b/protocol/tree_node.go @@ -26,7 +26,7 @@ func makeTree(root *state.Checkpoint, successors []*state.Checkpoint) *treeNode for _, successor := range parentToSuccessors[node.checkpoint.Hash] { child := &treeNode{checkpoint: successor} successor.Parent = node.checkpoint - node.children = append(node.children, child) + node.addChild(child) nodes = append(nodes, child) } nodes = nodes[1:] @@ -35,13 +35,21 @@ func makeTree(root *state.Checkpoint, successors []*state.Checkpoint) *treeNode } func (t *treeNode) addChild(child *treeNode) { - for i, n := range t.children { - if n.checkpoint.Hash == child.checkpoint.Hash { - t.children[i] = child - return + child.checkpoint.MergeCheckpoint = t.mergeCheckpoint + t.children = append(t.children, child) +} + +func (t *treeNode) mergeCheckpoint(hash bc.Hash) { + count := 0 + for i, child := range t.children { + if child.checkpoint.Hash == hash { + count++ + if count == 2 { + t.children = append(t.children[0:i], t.children[i+1:]...) + break + } } } - t.children = append(t.children, child) } func (t *treeNode) nodeByHash(blockHash bc.Hash) (*treeNode, error) { diff --git a/protocol/tree_node_test.go b/protocol/tree_node_test.go new file mode 100644 index 00000000..8016cbcf --- /dev/null +++ b/protocol/tree_node_test.go @@ -0,0 +1,47 @@ +package protocol + +import ( + "testing" + + "github.com/bytom/bytom/protocol/bc" + "github.com/bytom/bytom/protocol/bc/types" + "github.com/bytom/bytom/protocol/state" + "github.com/bytom/bytom/testutil" +) + +func TestMergeCheckpoint(t *testing.T) { + parent := &treeNode{ + checkpoint: &state.Checkpoint{ + Height: 0, + Hash: testutil.MustDecodeHash("a4de8b26e4394ebc5f63e9c805cc682ae6fa47df141d4fe2a238d7c11ccbd87f"), + ParentHash: bc.Hash{}, + Parent: nil, + Timestamp: 1563606689, + Status: state.Justified, + }, + } + + block := &types.Block{ + BlockHeader: types.BlockHeader{ + Height: 1, + PreviousBlockHash: testutil.MustDecodeHash("a4de8b26e4394ebc5f63e9c805cc682ae6fa47df141d4fe2a238d7c11ccbd87f"), + Timestamp: 1563606700, + }, + } + + child1 := &treeNode{checkpoint: state.NewCheckpoint(parent.checkpoint)} + parent.addChild(child1) + if err := child1.checkpoint.Increase(block); err != nil { + t.Fatal(err) + } + + child2 := &treeNode{checkpoint: state.NewCheckpoint(parent.checkpoint)} + parent.addChild(child2) + if err := child2.checkpoint.Increase(block); err != nil { + t.Fatal(err) + } + + if len(parent.children) != 1 { + t.Errorf("expect size of children is 1, got %d\n", len(parent.children)) + } +} -- 2.11.0