From 48e9b9620ef8858bbecce7dd250b0d06bec05798 Mon Sep 17 00:00:00 2001 From: Poseidon Date: Wed, 7 Apr 2021 12:55:05 +0800 Subject: [PATCH] auth_verification_for_casper (#1858) * auth_verification_for_casper * add todo for auth verification * remove pubkey in encode message * sha3hash for verification message * split verification * refactor * bug fix --- protocol/consensus/casper.go | 130 ++++++++++++++++++++++++++------------ protocol/consensus/checkpoint.go | 10 +++ protocol/consensus/tree_node.go | 50 +++++++++++++++ protocol/consensus/verfication.go | 90 ++++++++++++++++++++++++++ 4 files changed, 238 insertions(+), 42 deletions(-) create mode 100644 protocol/consensus/tree_node.go create mode 100644 protocol/consensus/verfication.go diff --git a/protocol/consensus/casper.go b/protocol/consensus/casper.go index 581f7e69..e3d952f8 100644 --- a/protocol/consensus/casper.go +++ b/protocol/consensus/casper.go @@ -1,7 +1,6 @@ package consensus import ( - "fmt" "sync" "github.com/bytom/bytom/errors" @@ -10,10 +9,12 @@ import ( "github.com/bytom/bytom/protocol/bc/types" ) -type treeNode struct { - checkpoint *checkpoint - children []*treeNode -} +var ( + errVerifySignature = errors.New("signature of verification message is invalid") + errPubKeyIsNotValidator = errors.New("pub key is not in validators of target checkpoint") + errSameHeightInVerification = errors.New("validator publish two distinct votes for the same target height") + errSpanHeightInVerification = errors.New("validator publish vote within the span of its other votes") +) // Casper is BFT based proof of stack consensus algorithm, it provides safety and liveness in theory, // it's design mainly refers to https://github.com/ethereum/research/blob/master/papers/casper-basics/casper_basics.pdf @@ -37,26 +38,20 @@ func (c *Casper) BestChain() (uint64, string) { // Validators return the validators by specified block hash // e.g. if the block num of epoch is 100, and the block height corresponding to the block hash is 130, then will return the voting results of height in 0~100 func (c *Casper) Validators(blockHash *bc.Hash) ([]*Validator, error) { - checkpoint, err := c.prevCheckpoint(blockHash) + hash, err := c.prevCheckpointHash(blockHash) if err != nil { return nil, err } c.mu.RLock() defer c.mu.RUnlock() - return checkpoint.validators(), nil -} -// Verification represent a verification message for the block -// source hash and target hash point to the checkpoint, and the source checkpoint is the target checkpoint's parent(not be directly) -// the vector as the message of signature -type Verification struct { - SourceHash string - TargetHash string - SourceHeight uint64 - TargetHeight uint64 - Signature string - PubKey string + checkpoint, err := c.tree.checkpointByHash(hash.String()) + if err != nil { + return nil, err + } + + return checkpoint.validators(), nil } // AuthVerification verify whether the Verification is legal. @@ -64,6 +59,45 @@ type Verification struct { // ⟨ν,s1,t1,h(s1),h(t1)⟩ and ⟨ν,s2,t2,h(s2),h(t2)⟩, such that either: // h(t1) = h(t2) OR h(s1) < h(s2) < h(t2) < h(t1) func (c *Casper) AuthVerification(v *Verification) error { + if err := v.VerifySignature(); err != nil { + return err + } + + c.mu.Lock() + defer c.mu.Unlock() + + source, err := c.tree.checkpointByHash(v.SourceHash) + if err != nil { + // the following two cases are not handled + // case1: the synchronization block is later than the arrival of the verification message + // case2: the tree node was was pruned + return err + } + + target, err := c.tree.checkpointByHash(v.TargetHash) + if err != nil { + return err + } + + if !target.containsValidator(v.PubKey) { + return errPubKeyIsNotValidator + } + + if err := c.verifySameHeight(v); err != nil { + return err + } + + if err := c.verifySpanHeight(v); err != nil { + return err + } + + supLink := target.addSupLink(v.SourceHeight, v.SourceHash, v.PubKey) + if source.status == justified && supLink.confirmed() { + target.status = justified + source.status = finalized + // must notify chain when rollback + // pruning the tree + } return nil } @@ -74,6 +108,38 @@ func (c *Casper) ProcessBlock(block *types.Block) error { return nil } +// a validator must not publish two distinct votes for the same target height +func (c *Casper) verifySameHeight(v *Verification) error { + nodes := c.tree.checkpointsOfHeight(v.TargetHeight) + for _, node := range nodes { + for _, supLink := range node.supLinks { + if supLink.pubKeys[v.PubKey] { + return errSameHeightInVerification + } + } + } + return nil +} + +// a validator must not vote within the span of its other votes. +func (c *Casper) verifySpanHeight(v *Verification) error { + if c.tree.findOnlyOne(func(c *checkpoint) bool { + if c.height <= v.TargetHeight { + return false + } + + for _, supLink := range c.supLinks { + if supLink.pubKeys[v.PubKey] && supLink.sourceHeight < v.SourceHeight { + return true + } + } + return false + }) != nil { + return errSpanHeightInVerification + } + return nil +} + // justifiedHeight is the max justified height of checkpoint from node to root func chainOfMaxJustifiedHeight(node *treeNode, justifiedHeight uint64) (uint64, string, uint64) { checkpoint := node.checkpoint @@ -90,7 +156,7 @@ func chainOfMaxJustifiedHeight(node *treeNode, justifiedHeight uint64) (uint64, return bestHeight, bestHash, maxJustifiedHeight } -func (c *Casper) prevCheckpoint(blockHash *bc.Hash) (*checkpoint, error) { +func (c *Casper) prevCheckpointHash(blockHash *bc.Hash) (*bc.Hash, error) { for { block, err := c.store.GetBlockHeader(blockHash) if err != nil { @@ -98,29 +164,9 @@ func (c *Casper) prevCheckpoint(blockHash *bc.Hash) (*checkpoint, error) { } height := block.Height - 1 - hash := block.PreviousBlockHash - if height%blocksOfEpoch != 0 { - return c.checkpointOfBlockHash(&hash) + blockHash = &block.PreviousBlockHash + if height%blocksOfEpoch == 0 { + return blockHash, nil } } } - -func (c *Casper) checkpointOfBlockHash(blockHash *bc.Hash) (*checkpoint, error) { - c.mu.RLock() - defer c.mu.RUnlock() - - return findCheckpoint(c.tree, blockHash) -} - -func findCheckpoint(node *treeNode, blockHash *bc.Hash) (*checkpoint, error) { - hash := blockHash.String() - if node.checkpoint.hash == hash { - return node.checkpoint, nil - } - - for _, child := range node.children { - return findCheckpoint(child, blockHash) - } - - return nil, errors.New(fmt.Sprintf("fail to find checkpoint of hash:%s", hash)) -} diff --git a/protocol/consensus/checkpoint.go b/protocol/consensus/checkpoint.go index d6f459c5..fc28e0df 100644 --- a/protocol/consensus/checkpoint.go +++ b/protocol/consensus/checkpoint.go @@ -87,3 +87,13 @@ func (c *checkpoint) validators() []*Validator { } return validators[:end] } + + +func (c *checkpoint) containsValidator(pubKey string) bool { + for _, v := range c.validators() { + if v.PubKey == pubKey { + return true + } + } + return false +} diff --git a/protocol/consensus/tree_node.go b/protocol/consensus/tree_node.go new file mode 100644 index 00000000..f8378fea --- /dev/null +++ b/protocol/consensus/tree_node.go @@ -0,0 +1,50 @@ +package consensus + +import ( + "errors" + "fmt" +) + +type treeNode struct { + checkpoint *checkpoint + children []*treeNode +} + +func (t *treeNode) checkpointByHash(blockHash string) (*checkpoint, error) { + if c := t.findOnlyOne(func(c *checkpoint) bool { + return c.hash == blockHash + }); c != nil { + return c, nil + } + + return nil, errors.New(fmt.Sprintf("fail to find checkpoint of hash:%s", blockHash)) +} + +func (t *treeNode) checkpointsOfHeight(blockHeight uint64) []*checkpoint { + if blockHeight%blocksOfEpoch != 0 { + return nil + } + + var result []*checkpoint + if t.checkpoint.height == blockHeight { + return append(result, t.checkpoint) + } + + for _, child := range t.children { + result = append(result, child.checkpointsOfHeight(blockHeight)...) + } + return result +} + +func (t *treeNode) findOnlyOne(predicate func(*checkpoint) bool) *checkpoint { + if predicate(t.checkpoint) { + return t.checkpoint + } + + for _, child := range t.children { + if c := child.findOnlyOne(predicate); c != nil { + return c + } + } + return nil +} diff --git a/protocol/consensus/verfication.go b/protocol/consensus/verfication.go new file mode 100644 index 00000000..2a020ca7 --- /dev/null +++ b/protocol/consensus/verfication.go @@ -0,0 +1,90 @@ +package consensus + +import ( + "bytes" + "crypto/ed25519" + "encoding/binary" + "encoding/hex" + + "github.com/bytom/bytom/crypto/sha3pool" + "github.com/bytom/bytom/protocol/bc" +) + +// Verification represent a verification message for the block +// source hash and target hash point to the checkpoint, and the source checkpoint is the target checkpoint's parent(not be directly) +// the vector as the message of signature +type Verification struct { + SourceHash string + TargetHash string + SourceHeight uint64 + TargetHeight uint64 + Signature string + PubKey string +} + +// EncodeMessage encode the verification for the validators to sign or verify +func (v *Verification) EncodeMessage() ([]byte, error) { + buff := new(bytes.Buffer) + if _, err := buff.WriteString(v.SourceHash); err != nil { + return nil, err + } + + if _, err := buff.WriteString(v.TargetHash); err != nil { + return nil, err + } + + uint64Buff := make([]byte, 8) + + binary.LittleEndian.PutUint64(uint64Buff, v.SourceHeight) + if _, err := buff.Write(uint64Buff); err != nil { + return nil, err + } + + binary.LittleEndian.PutUint64(uint64Buff, v.TargetHeight) + if _, err := buff.Write(uint64Buff); err != nil { + return nil, err + } + + return sha3Hash(buff.Bytes()) +} + +// VerifySignature verify the signature of encode message of verification +func (v *Verification) VerifySignature() error { + pubKey, err := hex.DecodeString(v.PubKey) + if err != nil { + return err + } + + signature, err := hex.DecodeString(v.Signature) + if err != nil { + return err + } + + message, err := v.EncodeMessage() + if err != nil { + return err + } + + if !ed25519.Verify(pubKey, message, signature) { + return errVerifySignature + } + + return nil +} + +func sha3Hash(message []byte) ([]byte, error) { + sha3 := sha3pool.Get256() + defer sha3pool.Put256(sha3) + + if _, err := sha3.Write(message); err != nil { + return nil, err + } + + hash := &bc.Hash{} + if _, err := hash.ReadFrom(sha3); err != nil { + return nil, err + } + + return hash.Bytes(), nil +} + -- 2.11.0