path: root/simulation/verification.go

// Copyright 2018 The dexon-consensus Authors
// This file is part of the dexon-consensus library.
//
// The dexon-consensus library is free software: you can redistribute it
// and/or modify it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation, either version 3 of the License,
// or (at your option) any later version.
//
// The dexon-consensus library is distributed in the hope that it will be
// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
// General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the dexon-consensus library. If not, see
// <http://www.gnu.org/licenses/>.

package simulation

import (
    "container/heap"
    "log"
    "math"
    "time"

    "github.com/dexon-foundation/dexon-consensus/common"
    "github.com/dexon-foundation/dexon-consensus/core/test"
    "github.com/dexon-foundation/dexon-consensus/core/types"
)

type timeStamp struct {
    time   time.Time
    length int
}

type totalOrderStatus struct {
    blockReceive             []timeStamp
    confirmLatency           []time.Duration
    blockSeen                map[common.Hash]time.Time
    internalTimestampLatency []time.Duration
    externalTimestampLatency []time.Duration
}

// TotalOrderResult is the object maintaining peer's result of
// Total Ordering Algorithm.
type TotalOrderResult struct {
    nodeID           types.NodeID
    hashList         common.Hashes
    curID            int
    pendingBlockList PendingBlockList
    status           totalOrderStatus
}

// PeerTotalOrder stores the TotalOrderResult of each node.
type PeerTotalOrder = map[types.NodeID]*TotalOrderResult

// NewTotalOrderResult returns pointer to a a new TotalOrderResult instance.
func NewTotalOrderResult(nID types.NodeID) *TotalOrderResult {
    totalOrder := &TotalOrderResult{
        nodeID: nID,
        status: totalOrderStatus{
            blockSeen: make(map[common.Hash]time.Time),
        },
    }
    heap.Init(&totalOrder.pendingBlockList)
    return totalOrder
}

func (totalOrder *TotalOrderResult) processStatus(blocks BlockList) {
    totalOrder.status.blockReceive = append(totalOrder.status.blockReceive,
        timeStamp{
            time:   time.Now(),
            length: len(blocks.BlockHash),
        })
    totalOrder.status.confirmLatency = append(totalOrder.status.confirmLatency,
        blocks.ConfirmLatency...)
}

// PushBlocks push a BlockList into the TotalOrderResult and return true if
// there are new blocks ready for verification.
func (totalOrder *TotalOrderResult) PushBlocks(blocks BlockList) (ready bool) {
    totalOrder.processStatus(blocks)
    if blocks.ID != totalOrder.curID {
        heap.Push(&totalOrder.pendingBlockList, &blocks)
        return false
    }

    // Append all of the consecutive blockList in the pendingBlockList.
    for {
        totalOrder.hashList = append(totalOrder.hashList, blocks.BlockHash...)
        totalOrder.curID++
        if len(totalOrder.pendingBlockList) == 0 ||
            totalOrder.pendingBlockList[0].ID != totalOrder.curID {
            break
        }
        blocks = *heap.Pop(&totalOrder.pendingBlockList).(*BlockList)
    }
    return true
}

// PushTimestamp logs the information in the msg.
func (totalOrder *TotalOrderResult) PushTimestamp(msg timestampMessage) bool {
    pushLatency := func(latency *[]time.Duration, t1, t2 time.Time) {
        *latency = append(*latency, t2.Sub(t1))
    }
    switch msg.Event {
    case blockSeen:
        totalOrder.status.blockSeen[msg.BlockHash] = msg.Timestamp
    case timestampConfirm:
        pushLatency(&totalOrder.status.internalTimestampLatency,
            totalOrder.status.blockSeen[msg.BlockHash], msg.Timestamp)
    case timestampAck:
        if seenTime, exist := totalOrder.status.blockSeen[msg.BlockHash]; exist {
            pushLatency(&totalOrder.status.externalTimestampLatency,
                seenTime, msg.Timestamp)
        }
    default:
        return false
    }
    return true
}

// CalculateBlocksPerSecond calculates the result using status.blockReceive
func (totalOrder *TotalOrderResult) CalculateBlocksPerSecond() float64 {
    ts := totalOrder.status.blockReceive
    if len(ts) < 2 {
        return 0
    }

    diffTime := ts[len(ts)-1].time.Sub(ts[0].time).Seconds()
    if diffTime == 0 {
        return 0
    }
    totalBlocks := 0
    for _, blocks := range ts {
        // Blocks received at time zero are confirmed beforehand.
        if blocks.time == ts[0].time {
            continue
        }
        totalBlocks += blocks.length
    }
    return float64(totalBlocks) / diffTime
}

// CalculateAverageConfirmLatency calculates the result using
// status.confirmLatency
func (totalOrder *TotalOrderResult) CalculateAverageConfirmLatency() float64 {
    sum := 0.0
    for _, latency := range totalOrder.status.confirmLatency {
        sum += latency.Seconds()
    }
    return sum / float64(len(totalOrder.status.confirmLatency))
}

// CalculateAverageTimestampLatency calculates the result using
// status.timestampLatency
func (totalOrder *TotalOrderResult) CalculateAverageTimestampLatency() (
    internal float64, external float64) {
    for _, latency := range totalOrder.status.internalTimestampLatency {
        internal += latency.Seconds()
    }
    if internal > 0 {
        internal /= float64(len(totalOrder.status.internalTimestampLatency))
    }
    for _, latency := range totalOrder.status.externalTimestampLatency {
        external += latency.Seconds()
    }
    if external > 0 {
        external /= float64(len(totalOrder.status.externalTimestampLatency))
    }
    return
}

// VerifyTotalOrder verifies if the result of Total Ordering Algorithm
// returned by all nodes are the same. However, the length of result
// of each nodes may not be the same, so only the common part is verified.
func VerifyTotalOrder(id types.NodeID,
    totalOrder PeerTotalOrder) (
    unverifiedMap PeerTotalOrder, correct bool, length int) {

    hasError := false

    // Get the common length from all nodes.
    length = math.MaxInt32
    for _, peerTotalOrder := range totalOrder {
        if len(peerTotalOrder.hashList) < length {
            length = len(peerTotalOrder.hashList)
        }
    }

    // Verify if the order of the blocks are the same by comparing
    // the hash value.
    for i := 0; i < length; i++ {
        hash := totalOrder[id].hashList[i]
        for vid, peerTotalOrder := range totalOrder {
            if peerTotalOrder.hashList[i] != hash {
                log.Printf("[%d] Unexpected hash %v from %v\n", i,
                    peerTotalOrder.hashList[i], vid)
                hasError = true
            }
        }
        if hasError {
            log.Printf("[%d] Hash is %v from %v\n", i, hash, id)
        } else {
            log.Printf("Block %v confirmed\n", hash)
        }
    }

    // Remove verified block from list.
    if length > 0 {
        for vid := range totalOrder {
            totalOrder[vid].hashList =
                totalOrder[vid].hashList[length:]
        }
    }
    return totalOrder, !hasError, length
}

// LogStatus prints all the status to log.
func LogStatus(peerTotalOrder PeerTotalOrder) {
    for nID, totalOrder := range peerTotalOrder {
        log.Printf("[Node %s]\n", nID)
        log.Printf("    BPS: %.6f\n", totalOrder.CalculateBlocksPerSecond())
        log.Printf("    Confirm Latency: %.2fms\n",
            totalOrder.CalculateAverageConfirmLatency()*1000)
        log.Printf("    Confirm Blocks: %v\n", len(totalOrder.status.confirmLatency))
        intLatency, extLatency := totalOrder.CalculateAverageTimestampLatency()
        log.Printf("    Internal Timestamp Latency: %.2fms\n", intLatency*1000)
        log.Printf("    External Timestamp Latency: %.2fms\n", extLatency*1000)
    }
    logOverallLatency(peerTotalOrder)
}

// logOverallLatency prints overall status related to latency.
func logOverallLatency(peerTotalOrder PeerTotalOrder) {
    // Let's use brute-force way since the simulation should be done
    // at this moment.
    var (
        overallConfirmLatency           []time.Duration
        overallInternalTimestampLatency []time.Duration
        overallExternalTimestampLatency []time.Duration
    )
    for _, totalOrder := range peerTotalOrder {
        overallConfirmLatency = append(
            overallConfirmLatency, totalOrder.status.confirmLatency...)
        overallInternalTimestampLatency = append(
            overallInternalTimestampLatency,
            totalOrder.status.internalTimestampLatency...)
        overallExternalTimestampLatency = append(
            overallExternalTimestampLatency,
            totalOrder.status.externalTimestampLatency...)
    }
    log.Print("[Overall]\n")
    avg, dev := test.CalcLatencyStatistics(overallConfirmLatency)
    log.Printf("    Confirm Latency: %v, dev: %v\n", avg, dev)
    avg, dev = test.CalcLatencyStatistics(overallInternalTimestampLatency)
    log.Printf("    Interal Timestamp Latency: %v, dev: %v\n", avg, dev)
    avg, dev = test.CalcLatencyStatistics(overallExternalTimestampLatency)
    log.Printf("    External Timestamp Latency: %v, dev: %v\n", avg, dev)
}