protocol/auth_verification.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5         "fmt"
   6
   7         log "github.com/sirupsen/logrus"
   8
   9         "github.com/bytom/bytom/consensus"
  10         "github.com/bytom/bytom/protocol/bc"
  11         "github.com/bytom/bytom/protocol/state"
  12 )
  13
  14 // AuthVerification verify whether the Verification is legal.
  15 // the status of source checkpoint must justified, and an individual validator ν must not publish two distinct Verification
  16 // ⟨ν,s1,t1,h(s1),h(t1)⟩ and ⟨ν,s2,t2,h(s2),h(t2)⟩, such that either:
  17 // h(t1) = h(t2) OR h(s1) < h(s2) < h(t2) < h(t1)
  18 func (c *Casper) AuthVerification(v *Verification) error {
  19         if err := validate(v); err != nil {
  20                 return err
  21         }
  22
  23         c.mu.Lock()
  24         defer c.mu.Unlock()
  25
  26         // root of tree is the last finalized checkpoint
  27         if v.TargetHeight < c.tree.checkpoint.Height {
  28                 // discard the verification message which height of target less than height of last finalized checkpoint
  29                 // is for simplify check the vote within the span of its other votes
  30                 return nil
  31         }
  32
  33         targetNode, err := c.tree.nodeByHash(v.TargetHash)
  34         if err != nil {
  35                 c.verificationCache.Add(verificationCacheKey(v.TargetHash, v.PubKey), v)
  36                 return nil
  37         }
  38
  39         validators, err := c.Validators(&v.TargetHash)
  40         if err != nil {
  41                 return err
  42         }
  43
  44         if _, ok := validators[v.PubKey]; !ok {
  45                 return errPubKeyIsNotValidator
  46         }
  47
  48         if targetNode.checkpoint.ContainsVerification(validators[v.PubKey].Order, &v.SourceHash) {
  49                 return nil
  50         }
  51
  52         oldBestHash := c.bestChain()
  53         if err := c.authVerification(v, targetNode.checkpoint, validators); err != nil {
  54                 return err
  55         }
  56
  57         return c.tryRollback(oldBestHash)
  58 }
  59
  60 func (c *Casper) authVerification(v *Verification, target *state.Checkpoint, validators map[string]*state.Validator) error {
  61         validator := validators[v.PubKey]
  62         if err := c.verifyVerification(v, validator.Order, true); err != nil {
  63                 return err
  64         }
  65
  66         checkpoints, err := c.addVerificationToCheckpoint(target, validators, v)
  67         if err != nil {
  68                 return err
  69         }
  70
  71         if err := c.store.SaveCheckpoints(checkpoints); err != nil {
  72                 return err
  73         }
  74
  75         return c.saveVerificationToHeader(v, validator.Order)
  76 }
  77
  78 func (c *Casper) addVerificationToCheckpoint(target *state.Checkpoint, validators map[string]*state.Validator, verifications ...*Verification) ([]*state.Checkpoint, error) {
  79         affectedCheckpoints := []*state.Checkpoint{target}
  80         for _, v := range verifications {
  81                 source, err := c.store.GetCheckpoint(&v.SourceHash)
  82                 if err != nil {
  83                         return nil, err
  84                 }
  85
  86                 supLink := target.AddVerification(v.SourceHash, v.SourceHeight, validators[v.PubKey].Order, v.Signature)
  87                 if target.Status != state.Unjustified || !supLink.IsMajority(len(validators)) || source.Status == state.Finalized {
  88                         continue
  89                 }
  90
  91                 c.setJustified(source, target)
  92                 affectedCheckpoints = append(affectedCheckpoints, source)
  93         }
  94         return affectedCheckpoints, nil
  95 }
  96
  97 func (c *Casper) saveVerificationToHeader(v *Verification, validatorOrder int) error {
  98         blockHeader, err := c.store.GetBlockHeader(&v.TargetHash)
  99         if err != nil {
 100                 return err
 101         }
 102
 103         signature, err := hex.DecodeString(v.Signature)
 104         if err != nil {
 105                 return err
 106         }
 107
 108         blockHeader.SupLinks.AddSupLink(v.SourceHeight, v.SourceHash, signature, validatorOrder)
 109         return c.store.SaveBlockHeader(blockHeader)
 110 }
 111
 112 // source status is justified, and exist a super majority link from source to target
 113 func (c *Casper) setJustified(source, target *state.Checkpoint) {
 114         target.Status = state.Justified
 115         // must direct child
 116         if target.ParentHash == source.Hash {
 117                 c.setFinalized(source)
 118         }
 119 }
 120
 121 func (c *Casper) setFinalized(checkpoint *state.Checkpoint) {
 122         checkpoint.Status = state.Finalized
 123         newRoot, err := c.tree.nodeByHash(checkpoint.Hash)
 124         if err != nil {
 125                 log.WithField("err", err).Error("source checkpoint before the last finalized checkpoint")
 126                 return
 127         }
 128
 129         // update the checkpoint state in memory
 130         newRoot.checkpoint.Status = state.Finalized
 131         c.tree = newRoot
 132 }
 133
 134 func (c *Casper) tryRollback(oldBestHash bc.Hash) error {
 135         if newBestHash := c.bestChain(); oldBestHash != newBestHash {
 136                 msg := &rollbackMsg{bestHash: newBestHash, reply: make(chan error)}
 137                 c.rollbackCh <- msg
 138                 return <-msg.reply
 139         }
 140         return nil
 141 }
 142
 143 func (c *Casper) authVerificationLoop() {
 144         for blockHash := range c.newEpochCh {
 145                 validators, err := c.Validators(&blockHash)
 146                 if err != nil {
 147                         log.WithField("err", err).Error("get validators when auth verification")
 148                         continue
 149                 }
 150
 151                 for _, validator := range validators {
 152                         key := verificationCacheKey(blockHash, validator.PubKey)
 153                         verification, ok := c.verificationCache.Get(key)
 154                         if !ok {
 155                                 continue
 156                         }
 157
 158                         v := verification.(*Verification)
 159                         target, err := c.store.GetCheckpoint(&v.TargetHash)
 160                         if err != nil {
 161                                 log.WithField("err", err).Error("get target checkpoint")
 162                                 c.verificationCache.Remove(key)
 163                                 continue
 164                         }
 165
 166                         c.mu.Lock()
 167                         if err := c.authVerification(v, target, validators); err != nil {
 168                                 log.WithField("err", err).Error("auth verification in cache")
 169                         }
 170                         c.mu.Unlock()
 171
 172                         c.verificationCache.Remove(key)
 173                 }
 174         }
 175 }
 176
 177 func (c *Casper) verifyVerification(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 178         if err := c.verifySameHeight(v, validatorOrder, trackEvilValidator); err != nil {
 179                 return err
 180         }
 181
 182         return c.verifySpanHeight(v, validatorOrder, trackEvilValidator)
 183 }
 184
 185 // a validator must not publish two distinct votes for the same target height
 186 func (c *Casper) verifySameHeight(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 187         checkpoints, err := c.store.GetCheckpointsByHeight(v.TargetHeight)
 188         if err != nil {
 189                 return err
 190         }
 191
 192         for _, checkpoint := range checkpoints {
 193                 for _, supLink := range checkpoint.SupLinks {
 194                         if supLink.Signatures[validatorOrder] != "" && checkpoint.Hash != v.TargetHash {
 195                                 if trackEvilValidator {
 196                                         c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, v.PubKey, validatorOrder)}
 197                                 }
 198                                 return errSameHeightInVerification
 199                         }
 200                 }
 201         }
 202         return nil
 203 }
 204
 205 // a validator must not vote within the span of its other votes.
 206 func (c *Casper) verifySpanHeight(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 207         if c.tree.findOnlyOne(func(checkpoint *state.Checkpoint) bool {
 208                 if checkpoint.Height == v.TargetHeight {
 209                         return false
 210                 }
 211
 212                 for _, supLink := range checkpoint.SupLinks {
 213                         if supLink.Signatures[validatorOrder] != "" {
 214                                 if (checkpoint.Height < v.TargetHeight && supLink.SourceHeight > v.SourceHeight) ||
 215                                         (checkpoint.Height > v.TargetHeight && supLink.SourceHeight < v.SourceHeight) {
 216                                         if trackEvilValidator {
 217                                                 c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, v.PubKey, validatorOrder)}
 218                                         }
 219                                         return true
 220                                 }
 221                         }
 222                 }
 223                 return false
 224         }) != nil {
 225                 return errSpanHeightInVerification
 226         }
 227         return nil
 228 }
 229
 230 func makeVerification(supLink *state.SupLink, checkpoint *state.Checkpoint, pubKey string, validatorOrder int) *Verification {
 231         return &Verification{
 232                 SourceHash:   supLink.SourceHash,
 233                 TargetHash:   checkpoint.Hash,
 234                 SourceHeight: supLink.SourceHeight,
 235                 TargetHeight: checkpoint.Height,
 236                 Signature:    supLink.Signatures[validatorOrder],
 237                 PubKey:       pubKey,
 238         }
 239 }
 240
 241 func validate(v *Verification) error {
 242         blocksOfEpoch := consensus.ActiveNetParams.BlocksOfEpoch
 243         if v.SourceHeight%blocksOfEpoch != 0 || v.TargetHeight%blocksOfEpoch != 0 {
 244                 return errVoteToGrowingCheckpoint
 245         }
 246
 247         if v.SourceHeight == v.TargetHeight {
 248                 return errVoteToSameCheckpoint
 249         }
 250
 251         return v.VerifySignature()
 252 }
 253
 254 func verificationCacheKey(blockHash bc.Hash, pubKey string) string {
 255         return fmt.Sprintf("%s:%s", blockHash.String(), pubKey)
 256 }