protocol/apply_block.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5
   6         "github.com/sirupsen/logrus"
   7
   8         "github.com/bytom/bytom/config"
   9         "github.com/bytom/bytom/errors"
  10         "github.com/bytom/bytom/math/checked"
  11         "github.com/bytom/bytom/protocol/bc"
  12         "github.com/bytom/bytom/protocol/bc/types"
  13         "github.com/bytom/bytom/protocol/state"
  14 )
  15
  16 type applyBlockReply struct {
  17         verification *Verification
  18         isRollback   bool
  19         newBestHash  bc.Hash
  20 }
  21
  22 // ApplyBlock used to receive a new block from upper layer, it provides idempotence
  23 // and parse the vote and mortgage from the transactions, then save to the checkpoint
  24 // the tree of checkpoint will grow with the arrival of new blocks
  25 // it will return verification when an epoch is reached and the current node is the validator, otherwise return nil
  26 // the chain module must broadcast the verification
  27 func (c *Casper) ApplyBlock(block *types.Block) (*applyBlockReply, error) {
  28         if block.Height%state.BlocksOfEpoch == 1 {
  29                 c.newEpochCh <- block.PreviousBlockHash
  30         }
  31
  32         c.mu.Lock()
  33         defer c.mu.Unlock()
  34
  35         if _, err := c.tree.nodeByHash(block.Hash()); err == nil {
  36                 return nil, errAlreadyProcessedBlock
  37         }
  38
  39         _, oldBestHash := c.bestChain()
  40         target, err := c.applyBlockToCheckpoint(block)
  41         if err != nil {
  42                 return nil, errors.Wrap(err, "apply block to checkpoint")
  43         }
  44
  45         if err := applyTransactions(target, block.Transactions); err != nil {
  46                 return nil, err
  47         }
  48
  49         validators, err := c.Validators(&target.Hash)
  50         if err != nil {
  51                 return nil, err
  52         }
  53
  54         verification, err := c.applyMyVerification(target, block, validators)
  55         if err != nil {
  56                 return nil, err
  57         }
  58
  59         affectedCheckpoints, err := c.applySupLinks(target, block.SupLinks, validators)
  60         if err != nil {
  61                 return nil, err
  62         }
  63
  64         reply := &applyBlockReply{verification: verification}
  65         if c.isRollback(oldBestHash, block) {
  66                 reply.isRollback = true
  67                 reply.newBestHash = block.Hash()
  68         }
  69         return reply, c.saveCheckpoints(affectedCheckpoints)
  70 }
  71
  72 func (c *Casper) applyBlockToCheckpoint(block *types.Block) (*state.Checkpoint, error) {
  73         node, err := c.checkpointByHash(block.PreviousBlockHash)
  74         if err != nil {
  75                 return nil, err
  76         }
  77
  78         checkpoint := node.checkpoint
  79         if mod := block.Height % state.BlocksOfEpoch; mod == 1 {
  80                 parent := checkpoint
  81                 checkpoint = &state.Checkpoint{
  82                         ParentHash: parent.Hash,
  83                         Parent:     parent,
  84                         Status:     state.Growing,
  85                         Votes:      make(map[string]uint64),
  86                         Guaranties: make(map[string]uint64),
  87                 }
  88
  89                 for pubKey, num := range parent.Votes {
  90                         checkpoint.Votes[pubKey] = num
  91                 }
  92                 for pubKey, num := range parent.Guaranties {
  93                         checkpoint.Guaranties[pubKey] = num
  94                 }
  95                 node.addChild(&treeNode{checkpoint: checkpoint})
  96         } else if mod == 0 {
  97                 checkpoint.Status = state.Unjustified
  98         }
  99
 100         checkpoint.Height = block.Height
 101         checkpoint.Hash = block.Hash()
 102         checkpoint.Timestamp = block.Timestamp
 103         return checkpoint, nil
 104 }
 105
 106 func (c *Casper) checkpointByHash(blockHash bc.Hash) (*treeNode, error) {
 107         node, err := c.tree.nodeByHash(blockHash)
 108         if err != nil {
 109                 logrus.WithField("err", err).Error("fail find checkpoint, start to reorganize checkpoint")
 110
 111                 return c.reorganizeCheckpoint(blockHash)
 112         }
 113
 114         return node, nil
 115 }
 116
 117 func (c *Casper) isRollback(oldBestHash bc.Hash, block *types.Block) bool {
 118         _, newBestHash := c.bestChain()
 119         return block.Hash() == newBestHash && block.PreviousBlockHash != oldBestHash
 120 }
 121
 122 func (c *Casper) reorganizeCheckpoint(hash bc.Hash) (*treeNode, error) {
 123         prevHash := hash
 124         var attachBlocks []*types.Block
 125         for {
 126                 prevBlock, err := c.store.GetBlock(&prevHash)
 127                 if err != nil {
 128                         return nil, err
 129                 }
 130
 131                 if prevBlock.Height%state.BlocksOfEpoch == 0 {
 132                         break
 133                 }
 134
 135                 attachBlocks = append([]*types.Block{prevBlock}, attachBlocks...)
 136                 prevHash = prevBlock.PreviousBlockHash
 137         }
 138
 139         parent, err := c.tree.nodeByHash(prevHash)
 140         if err != nil {
 141                 return nil, err
 142         }
 143
 144         node := &treeNode{
 145                 checkpoint: &state.Checkpoint{
 146                         ParentHash: parent.checkpoint.Hash,
 147                         Parent:     parent.checkpoint,
 148                         Status:     state.Growing,
 149                         Votes:      make(map[string]uint64),
 150                         Guaranties: make(map[string]uint64),
 151                 },
 152         }
 153
 154         parent.addChild(node)
 155         for _, attachBlock := range attachBlocks {
 156                 if err := applyTransactions(node.checkpoint, attachBlock.Transactions); err != nil {
 157                         return nil, err
 158                 }
 159
 160                 node.checkpoint.Hash = attachBlock.Hash()
 161                 node.checkpoint.Height = attachBlock.Height
 162                 node.checkpoint.Timestamp = attachBlock.Timestamp
 163         }
 164         return node, nil
 165 }
 166
 167 func applyTransactions(target *state.Checkpoint, transactions []*types.Tx) error {
 168         for _, tx := range transactions {
 169                 for _, input := range tx.Inputs {
 170                         if vetoInput, ok := input.TypedInput.(*types.VetoInput); ok {
 171                                 if err := processVeto(vetoInput, target); err != nil {
 172                                         return err
 173                                 }
 174                         }
 175
 176                         if isGuarantyProgram(input.ControlProgram()) {
 177                                 if err := processWithdrawal(decodeGuarantyArgs(input.ControlProgram()), target); err != nil {
 178                                         return err
 179                                 }
 180                         }
 181                 }
 182
 183                 for _, output := range tx.Outputs {
 184                         if _, ok := output.TypedOutput.(*types.VoteOutput); ok {
 185                                 if err := processVote(output, target); err != nil {
 186                                         return err
 187                                 }
 188                         }
 189
 190                         if isGuarantyProgram(output.ControlProgram) {
 191                                 if err := processGuaranty(decodeGuarantyArgs(output.ControlProgram), target); err != nil {
 192                                         return err
 193                                 }
 194                         }
 195                 }
 196         }
 197         return nil
 198 }
 199
 200 // applySupLinks copy the block's supLink to the checkpoint
 201 func (c *Casper) applySupLinks(target *state.Checkpoint, supLinks []*types.SupLink, validators map[string]*state.Validator) ([]*state.Checkpoint, error) {
 202         affectedCheckpoints := []*state.Checkpoint{target}
 203         if target.Height%state.BlocksOfEpoch != 0 {
 204                 return nil, nil
 205         }
 206
 207         for _, supLink := range supLinks {
 208                 var validVerifications []*Verification
 209                 for _, v := range supLinkToVerifications(supLink, validators, target.Hash, target.Height) {
 210                         if validate(v) == nil && c.verifyVerification(v, validators[v.PubKey].Order, true) == nil {
 211                                 validVerifications = append(validVerifications, v)
 212                         }
 213                 }
 214
 215                 checkpoints, err := c.addVerificationToCheckpoint(target, validators, validVerifications...)
 216                 if err != nil {
 217                         return nil, err
 218                 }
 219
 220                 affectedCheckpoints = append(affectedCheckpoints, checkpoints...)
 221         }
 222         return affectedCheckpoints, nil
 223 }
 224
 225 func (c *Casper) applyMyVerification(target *state.Checkpoint, block *types.Block, validators map[string]*state.Validator) (*Verification, error) {
 226         v, err := c.myVerification(target, validators)
 227         if err != nil {
 228                 return nil, err
 229         }
 230
 231         if v == nil {
 232                 return nil, nil
 233         }
 234
 235         signature, err := hex.DecodeString(v.Signature)
 236         if err != nil {
 237                 return nil, err
 238         }
 239
 240         block.SupLinks.AddSupLink(v.SourceHeight, v.SourceHash, signature, validators[v.PubKey].Order)
 241         return v, c.store.SaveBlockHeader(&block.BlockHeader)
 242 }
 243
 244 func (c *Casper) myVerification(target *state.Checkpoint, validators map[string]*state.Validator) (*Verification, error) {
 245         if target.Height%state.BlocksOfEpoch != 0 {
 246                 return nil, nil
 247         }
 248
 249         pubKey := config.CommonConfig.PrivateKey().XPub().String()
 250         if _, ok := validators[pubKey]; !ok {
 251                 return nil, nil
 252         }
 253
 254         validatorOrder := validators[pubKey].Order
 255         if target.ContainsVerification(validatorOrder, nil) {
 256                 return nil, nil
 257         }
 258
 259         if source := c.lastJustifiedCheckpointOfBranch(target); source != nil {
 260                 v := &Verification{
 261                         SourceHash:   source.Hash,
 262                         TargetHash:   target.Hash,
 263                         SourceHeight: source.Height,
 264                         TargetHeight: target.Height,
 265                         PubKey:       pubKey,
 266                 }
 267
 268                 prvKey := config.CommonConfig.PrivateKey()
 269                 if err := v.Sign(*prvKey); err != nil {
 270                         return nil, err
 271                 }
 272
 273                 if err := c.verifyVerification(v, validatorOrder, false); err != nil {
 274                         return nil, nil
 275                 }
 276
 277                 return v, nil
 278         }
 279         return nil, nil
 280 }
 281
 282 type guarantyArgs struct {
 283         Amount uint64
 284         PubKey []byte
 285 }
 286
 287 func isGuarantyProgram(program []byte) bool {
 288         return false
 289 }
 290
 291 func decodeGuarantyArgs(program []byte) *guarantyArgs {
 292         return nil
 293 }
 294
 295 func processWithdrawal(guarantyArgs *guarantyArgs, checkpoint *state.Checkpoint) error {
 296         pubKey := hex.EncodeToString(guarantyArgs.PubKey)
 297         guarantyNum := checkpoint.Guaranties[pubKey]
 298         guarantyNum, ok := checked.SubUint64(guarantyNum, guarantyArgs.Amount)
 299         if !ok {
 300                 return errOverflow
 301         }
 302
 303         checkpoint.Guaranties[pubKey] = guarantyNum
 304         // TODO delete the evil validator when receive the confiscate transaction
 305         return nil
 306 }
 307
 308 func processGuaranty(guarantyArgs *guarantyArgs, checkpoint *state.Checkpoint) error {
 309         if guarantyArgs.Amount < minGuaranty {
 310                 return errGuarantyLessThanMinimum
 311         }
 312
 313         pubKey := hex.EncodeToString(guarantyArgs.PubKey)
 314         guarantyNum := checkpoint.Guaranties[pubKey]
 315         guarantyNum, ok := checked.AddUint64(guarantyNum, guarantyArgs.Amount)
 316         if !ok {
 317                 return errOverflow
 318         }
 319
 320         checkpoint.Guaranties[pubKey] = guarantyNum
 321         return nil
 322 }
 323
 324 func processVeto(input *types.VetoInput, checkpoint *state.Checkpoint) error {
 325         pubKey := hex.EncodeToString(input.Vote)
 326         voteNum := checkpoint.Votes[pubKey]
 327         voteNum, ok := checked.SubUint64(voteNum, input.Amount)
 328         if !ok {
 329                 return errOverflow
 330         }
 331
 332         checkpoint.Votes[pubKey] = voteNum
 333         return nil
 334 }
 335
 336 func processVote(output *types.TxOutput, checkpoint *state.Checkpoint) error {
 337         voteOutput := output.TypedOutput.(*types.VoteOutput)
 338         pubKey := hex.EncodeToString(voteOutput.Vote)
 339         if checkpoint.Guaranties[pubKey] < minGuaranty {
 340                 return errVoteToNonValidator
 341         }
 342
 343         voteNum := checkpoint.Votes[pubKey]
 344         voteNum, ok := checked.AddUint64(voteNum, output.Amount)
 345         if !ok {
 346                 return errOverflow
 347         }
 348
 349         checkpoint.Votes[pubKey] = voteNum
 350         return nil
 351 }
 352
 353 func (c *Casper) lastJustifiedCheckpointOfBranch(branch *state.Checkpoint) *state.Checkpoint {
 354         parent := branch.Parent
 355         for parent != nil {
 356                 switch parent.Status {
 357                 case state.Finalized:
 358                         return nil
 359                 case state.Justified:
 360                         return parent
 361                 }
 362                 parent = parent.Parent
 363         }
 364         return nil
 365 }
 366
 367 func (c *Casper) saveCheckpoints(checkpoints []*state.Checkpoint) error {
 368         checkpointSet := make(map[bc.Hash]*state.Checkpoint)
 369         for _, c := range checkpoints {
 370                 checkpointSet[c.Hash] = c
 371         }
 372
 373         var result []*state.Checkpoint
 374         for _, c := range checkpointSet {
 375                 result = append(result, c)
 376         }
 377
 378         return c.store.SaveCheckpoints(result)
 379 }
 380
 381 func supLinkToVerifications(supLink *types.SupLink, validators map[string]*state.Validator, targetHash bc.Hash, targetHeight uint64) []*Verification {
 382         validatorList := make([]*state.Validator, len(validators))
 383         for _, validator := range validators {
 384                 validatorList[validator.Order] = validator
 385         }
 386
 387         var result []*Verification
 388         for i := 0; i < len(validators); i++ {
 389                 signature := supLink.Signatures[i]
 390                 if len(signature) == 0 {
 391                         continue
 392                 }
 393
 394                 result = append(result, &Verification{
 395                         SourceHash:   supLink.SourceHash,
 396                         TargetHash:   targetHash,
 397                         SourceHeight: supLink.SourceHeight,
 398                         TargetHeight: targetHeight,
 399                         Signature:    hex.EncodeToString(signature),
 400                         PubKey:       validatorList[i].PubKey,
 401                 })
 402         }
 403         return result
 404 }