Initial block reorganisation code

4 files changed, 209 insertions, 30 deletions

diff --git a/ethchain/block_chain.go b/ethchain/block_chain.go
index 90ad4516a..6eea14652 100644
--- a/ethchain/block_chain.go
+++ b/ethchain/block_chain.go
@@ -3,6 +3,7 @@ package ethchain
 import (
 	"bytes"
 	"github.com/ethereum/eth-go/ethutil"
+	"github.com/ethereum/eth-go/ethwire"
 	"log"
 	"math"
 	"math/big"
@@ -24,6 +25,7 @@ type BlockChain struct {
 func NewBlockChain(ethereum EthManager) *BlockChain {
 	bc := &BlockChain{}
 	bc.genesisBlock = NewBlockFromData(ethutil.Encode(Genesis))
+	bc.Ethereum = ethereum
 
 	bc.setLastBlock()
 
@@ -77,6 +79,101 @@ func (bc *BlockChain) HasBlock(hash []byte) bool {
 	return len(data) != 0
 }
 
+// TODO: At one point we might want to save a block by prevHash in the db to optimise this...
+func (bc *BlockChain) HasBlockWithPrevHash(hash []byte) bool {
+	block := bc.CurrentBlock
+
+	for ; block != nil; block = bc.GetBlock(block.PrevHash) {
+		if bytes.Compare(hash, block.PrevHash) == 0 {
+			return true
+		}
+	}
+	return false
+}
+
+func (bc *BlockChain) CalculateBlockTD(block *Block) *big.Int {
+	blockDiff := new(big.Int)
+
+	for _, uncle := range block.Uncles {
+		blockDiff = blockDiff.Add(blockDiff, uncle.Difficulty)
+	}
+	blockDiff = blockDiff.Add(blockDiff, block.Difficulty)
+
+	return blockDiff
+}
+
+// Is tasked by finding the CanonicalChain and resetting the chain if we are not the Conical one
+func (bc *BlockChain) FindCanonicalChain(msg *ethwire.Msg, commonBlockHash []byte) {
+	// 1. Calculate TD of the current chain
+	// 2. Calculate TD of the new chain
+	// Reset state to the correct one
+
+	chainDifficulty := new(big.Int)
+
+	// Calculate the entire chain until the block we both have
+	// Start with the newest block we got, all the way back to the common block we both know
+	for i := 0; i < (msg.Data.Len() - 1); i++ {
+		block := NewBlockFromRlpValue(msg.Data.Get(i))
+		if bytes.Compare(block.Hash(), commonBlockHash) == 0 {
+			log.Println("[BCHAIN] We have found the common parent block, breaking")
+			break
+		}
+		chainDifficulty.Add(chainDifficulty, bc.CalculateBlockTD(block))
+	}
+
+	log.Println("[BCHAIN] Incoming chain difficulty:", chainDifficulty)
+
+	curChainDifficulty := new(big.Int)
+	block := bc.CurrentBlock
+
+	for ; block != nil; block = bc.GetBlock(block.PrevHash) {
+		if bytes.Compare(block.Hash(), commonBlockHash) == 0 {
+			log.Println("[BCHAIN] We have found the common parent block, breaking")
+			break
+		}
+		curChainDifficulty.Add(curChainDifficulty, bc.CalculateBlockTD(block))
+	}
+
+	log.Println("[BCHAIN] Current chain difficulty:", curChainDifficulty)
+	if chainDifficulty.Cmp(curChainDifficulty) == 1 {
+		log.Println("[BCHAIN] The incoming Chain beat our asses, resetting")
+		bc.ResetTillBlockHash(commonBlockHash)
+	} else {
+		log.Println("[BCHAIN] Our chain showed the incoming chain who is boss. Ignoring.")
+	}
+}
+func (bc *BlockChain) ResetTillBlockHash(hash []byte) error {
+	lastBlock := bc.CurrentBlock
+	returnTo := bc.GetBlock(hash)
+
+	// TODO: REFACTOR TO FUNCTION, Used multiple times
+	bc.CurrentBlock = returnTo
+	bc.LastBlockHash = returnTo.Hash()
+	info := bc.BlockInfo(returnTo)
+	bc.LastBlockNumber = info.Number
+	// END TODO
+
+	bc.Ethereum.StateManager().PrepareDefault(returnTo)
+	err := ethutil.Config.Db.Delete(lastBlock.Hash())
+	if err != nil {
+		return err
+	}
+
+	var block *Block
+	for ; block != nil; block = bc.GetBlock(block.PrevHash) {
+		if bytes.Compare(block.Hash(), hash) == 0 {
+			log.Println("[CHAIN] We have arrived at the the common parent block, breaking")
+			break
+		}
+		err = ethutil.Config.Db.Delete(block.Hash())
+		if err != nil {
+			return err
+		}
+	}
+	log.Println("[CHAIN] Split chain deleted and reverted to common parent block.")
+	return nil
+}
+
 func (bc *BlockChain) GenesisBlock() *Block {
 	return bc.genesisBlock
 }
diff --git a/ethchain/state_manager.go b/ethchain/state_manager.go
index 46d8228d9..9118db211 100644
--- a/ethchain/state_manager.go
+++ b/ethchain/state_manager.go
@@ -201,7 +201,6 @@ func (sm *StateManager) ProcessBlock(block *Block, dontReact bool) error {
 
 	return nil
 }
-
 func (sm *StateManager) CalculateTD(block *Block) bool {
 	uncleDiff := new(big.Int)
 	for _, uncle := range block.Uncles {
@@ -215,6 +214,9 @@ func (sm *StateManager) CalculateTD(block *Block) bool {
 
 	// The new TD will only be accepted if the new difficulty is
 	// is greater than the previous.
+	fmt.Println("new block td:", td)
+	fmt.Println("cur block td:", sm.bc.TD)
+
 	if td.Cmp(sm.bc.TD) > 0 {
 		// Set the new total difficulty back to the block chain
 		sm.bc.SetTotalDifficulty(td)
diff --git a/ethminer/miner.go b/ethminer/miner.go
index f4f697aba..cb752e3de 100644
--- a/ethminer/miner.go
+++ b/ethminer/miner.go
@@ -61,10 +61,10 @@ func (miner *Miner) listener() {
 		select {
 		case chanMessage := <-miner.reactChan:
 			if block, ok := chanMessage.Resource.(*ethchain.Block); ok {
-				log.Println("[miner] Got new block via Reactor")
+				log.Println("[MINER] Got new block via Reactor")
 				if bytes.Compare(miner.ethereum.BlockChain().CurrentBlock.Hash(), block.Hash()) == 0 {
 					// TODO: Perhaps continue mining to get some uncle rewards
-					log.Println("[miner] New top block found resetting state")
+					log.Println("[MINER] New top block found resetting state")
 
 					// Filter out which Transactions we have that were not in this block
 					var newtxs []*ethchain.Transaction
@@ -86,7 +86,7 @@ func (miner *Miner) listener() {
 
 				} else {
 					if bytes.Compare(block.PrevHash, miner.ethereum.BlockChain().CurrentBlock.PrevHash) == 0 {
-						log.Println("[miner] Adding uncle block")
+						log.Println("[MINER] Adding uncle block")
 						miner.uncles = append(miner.uncles, block)
 						miner.ethereum.StateManager().Prepare(miner.block.State(), miner.block.State())
 					}
@@ -94,7 +94,7 @@ func (miner *Miner) listener() {
 			}
 
 			if tx, ok := chanMessage.Resource.(*ethchain.Transaction); ok {
-				log.Println("[miner] Got new transaction from Reactor", tx)
+				log.Println("[MINER] Got new transaction from Reactor", tx)
 				found := false
 				for _, ctx := range miner.txs {
 					if found = bytes.Compare(ctx.Hash(), tx.Hash()) == 0; found {
@@ -103,15 +103,15 @@ func (miner *Miner) listener() {
 
 				}
 				if found == false {
-					log.Println("[miner] We did not know about this transaction, adding")
+					log.Println("[MINER] We did not know about this transaction, adding")
 					miner.txs = append(miner.txs, tx)
 					miner.block.SetTransactions(miner.txs)
 				} else {
-					log.Println("[miner] We already had this transaction, ignoring")
+					log.Println("[MINER] We already had this transaction, ignoring")
 				}
 			}
 		default:
-			log.Println("[miner] Mining on block. Includes", len(miner.txs), "transactions")
+			log.Println("[MINER] Mining on block. Includes", len(miner.txs), "transactions")
 
 			// Apply uncles
 			if len(miner.uncles) > 0 {
@@ -123,7 +123,7 @@ func (miner *Miner) listener() {
 			miner.ethereum.StateManager().AccumelateRewards(miner.block)
 
 			// Search the nonce
-			log.Println("[miner] Initialision complete, starting mining")
+			log.Println("[MINER] Initialision complete, starting mining")
 			miner.block.Nonce = miner.pow.Search(miner.block, miner.quitChan)
 			if miner.block.Nonce != nil {
 				miner.ethereum.StateManager().PrepareDefault(miner.block)
@@ -137,8 +137,7 @@ func (miner *Miner) listener() {
 						log.Printf("Second stage verification error: Block's nonce is invalid (= %v)\n", ethutil.Hex(miner.block.Nonce))
 					}
 					miner.ethereum.Broadcast(ethwire.MsgBlockTy, []interface{}{miner.block.Value().Val})
-					log.Printf("[miner] 🔨  Mined block %x\n", miner.block.Hash())
-					log.Println(miner.block)
+					log.Printf("[MINER] 🔨  Mined block %x\n", miner.block.Hash())
 
 					miner.txs = []*ethchain.Transaction{} // Move this somewhere neat
 					miner.block = miner.ethereum.BlockChain().NewBlock(miner.coinbase, miner.txs)
diff --git a/peer.go b/peer.go
index 6b914710d..2cc940400 100644
--- a/peer.go
+++ b/peer.go
@@ -126,7 +126,8 @@ type Peer struct {
 	pubkey []byte
 
 	// Indicated whether the node is catching up or not
-	catchingUp bool
+	catchingUp      bool
+	blocksRequested int
 
 	Version string
 }
@@ -136,15 +137,16 @@ func NewPeer(conn net.Conn, ethereum *Ethereum, inbound bool) *Peer {
 	pubkey := ethutil.NewValueFromBytes(data).Get(2).Bytes()
 
 	return &Peer{
-		outputQueue: make(chan *ethwire.Msg, outputBufferSize),
-		quit:        make(chan bool),
-		ethereum:    ethereum,
-		conn:        conn,
-		inbound:     inbound,
-		disconnect:  0,
-		connected:   1,
-		port:        30303,
-		pubkey:      pubkey,
+		outputQueue:     make(chan *ethwire.Msg, outputBufferSize),
+		quit:            make(chan bool),
+		ethereum:        ethereum,
+		conn:            conn,
+		inbound:         inbound,
+		disconnect:      0,
+		connected:       1,
+		port:            30303,
+		pubkey:          pubkey,
+		blocksRequested: 10,
 	}
 }
 
@@ -291,11 +293,62 @@ func (p *Peer) HandleInbound() {
 				// Get all blocks and process them
 				var block, lastBlock *ethchain.Block
 				var err error
+
+				// 1. Compare the first block over the wire's prev-hash with the hash of your last block
+				// 2. If these two values are the same you can just link the chains together.
+				// [1:0,2:1,3:2] <- Current blocks (format block:previous_block)
+				// [1:0,2:1,3:2,4:3,5:4] <- incoming blocks
+				// == [1,2,3,4,5]
+				// 3. If the values are not the same we will have to go back and calculate the chain with the highest total difficulty
+				// [1:0,2:1,3:2,11:3,12:11,13:12]
+				// [1:0,2:1,3:2,4:3,5:4,6:5]
+
+				// [3:2,11:3,12:11,13:12]
+				// [3:2,4:3,5:4,6:5]
+				// Heb ik dit blok?
+				// Nee: heb ik een blok met PrevHash 3?
+				// Ja: DIVERSION
+				// Nee; Adding to chain
+
+				// See if we can find a common ancestor
+				// 1. Get the earliest block in the package.
+				// 2. Do we have this block?
+				//    3. Yes: Let's continue what we are doing
+				//    4. No: Let's request more blocks back.
+
+				if msg.Data.Len()-1 > 1 {
+					lastBlock = ethchain.NewBlockFromRlpValue(msg.Data.Get(msg.Data.Len() - 1))
+					if p.ethereum.StateManager().BlockChain().HasBlock(lastBlock.Hash()) {
+						fmt.Println("[PEER] We found a common ancestor, let's continue.")
+					} else {
+						fmt.Println("[PEER] No common ancestor found, requesting more blocks.")
+						p.blocksRequested = p.blocksRequested * 2
+						p.catchingUp = false
+						p.SyncWithBlocks()
+					}
+
+					for i := msg.Data.Len() - 1; i >= 0; i-- {
+						block = ethchain.NewBlockFromRlpValue(msg.Data.Get(i))
+						// Do we have this block on our chain?
+						if p.ethereum.StateManager().BlockChain().HasBlock(block.Hash()) {
+							fmt.Println("[PEER] Block found, checking next one.")
+						} else {
+							// We don't have this block, but we do have a block with the same prevHash, diversion time!
+							if p.ethereum.StateManager().BlockChain().HasBlockWithPrevHash(block.PrevHash) {
+								fmt.Printf("[PEER] Local and foreign chain have diverted after %x, we are going to get freaky with it!\n", block.PrevHash)
+								p.ethereum.StateManager().BlockChain().FindCanonicalChain(msg, block.PrevHash)
+							} else {
+								fmt.Println("[PEER] Both local and foreign chain have same parent. Continue normally")
+							}
+						}
+					}
+				}
+
 				for i := msg.Data.Len() - 1; i >= 0; i-- {
 					block = ethchain.NewBlockFromRlpValue(msg.Data.Get(i))
 
 					p.ethereum.StateManager().PrepareDefault(block)
-					err = p.ethereum.StateManager().ProcessBlock(block, true)
+					err = p.ethereum.StateManager().ProcessBlock(block, false)
 
 					if err != nil {
 						if ethutil.Config.Debug {
@@ -305,6 +358,7 @@ func (p *Peer) HandleInbound() {
 						}
 						break
 					} else {
+						ethutil.Config.Log.Infof("[PEER] Block %x added\n", block.Hash())
 						lastBlock = block
 					}
 				}
@@ -314,7 +368,7 @@ func (p *Peer) HandleInbound() {
 					if ethchain.IsParentErr(err) {
 						ethutil.Config.Log.Infoln("Attempting to catch up")
 						p.catchingUp = false
-						p.CatchupWithPeer()
+						p.CatchupWithPeer(p.ethereum.BlockChain().CurrentBlock.Hash())
 					} else if ethchain.IsValidationErr(err) {
 						// TODO
 					}
@@ -327,7 +381,7 @@ func (p *Peer) HandleInbound() {
 							ethutil.Config.Log.Infof("Synced to block height #%d %x %x\n", blockInfo.Number, lastBlock.Hash(), blockInfo.Hash)
 						}
 						p.catchingUp = false
-						p.CatchupWithPeer()
+						p.CatchupWithPeer(p.ethereum.BlockChain().CurrentBlock.Hash())
 					}
 				}
 			case ethwire.MsgTxTy:
@@ -374,11 +428,11 @@ func (p *Peer) HandleInbound() {
 				// Amount of parents in the canonical chain
 				//amountOfBlocks := msg.Data.Get(l).AsUint()
 				amountOfBlocks := uint64(100)
+
 				// Check each SHA block hash from the message and determine whether
 				// the SHA is in the database
 				for i := 0; i < l; i++ {
-					if data :=
-						msg.Data.Get(i).Bytes(); p.ethereum.StateManager().BlockChain().HasBlock(data) {
+					if data := msg.Data.Get(i).Bytes(); p.ethereum.StateManager().BlockChain().HasBlock(data) {
 						parent = p.ethereum.BlockChain().GetBlock(data)
 						break
 					}
@@ -386,9 +440,12 @@ func (p *Peer) HandleInbound() {
 
 				// If a parent is found send back a reply
 				if parent != nil {
+					ethutil.Config.Log.Infof("[PEER] Found conical block, returning chain from: %x ", parent.Hash())
 					chain := p.ethereum.BlockChain().GetChainFromHash(parent.Hash(), amountOfBlocks)
+					ethutil.Config.Log.Infof("[PEER] Returning %d blocks: %x ", len(chain), parent.Hash())
 					p.QueueMessage(ethwire.NewMessage(ethwire.MsgBlockTy, chain))
 				} else {
+					ethutil.Config.Log.Infof("[PEER] Could not find a similar block")
 					// If no blocks are found we send back a reply with msg not in chain
 					// and the last hash from get chain
 					lastHash := msg.Data.Get(l - 1)
@@ -527,7 +584,8 @@ func (p *Peer) handleHandshake(msg *ethwire.Msg) {
 	}
 
 	// Catch up with the connected peer
-	p.CatchupWithPeer()
+	// p.CatchupWithPeer(p.ethereum.BlockChain().CurrentBlock.Hash())
+	p.SyncWithBlocks()
 
 	// Set the peer's caps
 	p.caps = Caps(c.Get(3).Byte())
@@ -554,14 +612,37 @@ func (p *Peer) String() string {
 	return fmt.Sprintf("[%s] (%s) %v %s [%s]", strConnectType, strBoundType, p.conn.RemoteAddr(), p.Version, p.caps)
 
 }
+func (p *Peer) SyncWithBlocks() {
+	if !p.catchingUp {
+		p.catchingUp = true
+		// FIXME: THIS SHOULD NOT BE NEEDED
+		if p.blocksRequested == 0 {
+			p.blocksRequested = 10
+		}
+		fmt.Printf("Currenb lock %x\n", p.ethereum.BlockChain().CurrentBlock.Hash())
+		fmt.Println("Amount:", p.blocksRequested)
+		blocks := p.ethereum.BlockChain().GetChain(p.ethereum.BlockChain().CurrentBlock.Hash(), p.blocksRequested)
+
+		var hashes []interface{}
+		for _, block := range blocks {
+			hashes = append(hashes, block.Hash())
+		}
+		fmt.Printf("Requesting hashes from network: %x", hashes)
+
+		msgInfo := append(hashes, uint64(50))
+
+		msg := ethwire.NewMessage(ethwire.MsgGetChainTy, msgInfo)
+		p.QueueMessage(msg)
+	}
+}
 
-func (p *Peer) CatchupWithPeer() {
+func (p *Peer) CatchupWithPeer(blockHash []byte) {
 	if !p.catchingUp {
 		p.catchingUp = true
-		msg := ethwire.NewMessage(ethwire.MsgGetChainTy, []interface{}{p.ethereum.BlockChain().CurrentBlock.Hash(), uint64(50)})
+		msg := ethwire.NewMessage(ethwire.MsgGetChainTy, []interface{}{blockHash, uint64(50)})
 		p.QueueMessage(msg)
 
-		ethutil.Config.Log.Debugf("Requesting blockchain %x...\n", p.ethereum.BlockChain().CurrentBlock.Hash()[:4])
+		ethutil.Config.Log.Debugf("Requesting blockchain %x...\n", blockHash[:4])
 	}
 }