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