From 189a17a6586cd30ac355bd1165c44da6a2a08569 Mon Sep 17 00:00:00 2001 From: Jimmy Hu Date: Thu, 27 Sep 2018 17:33:34 +0800 Subject: types: NodeSet and Selector (#146) --- core/types/nodeset.go | 144 +++++++++++++++++++++++++++++++++++++++++++++ core/types/nodeset_test.go | 59 +++++++++++++++++++ 2 files changed, 203 insertions(+) create mode 100644 core/types/nodeset.go create mode 100644 core/types/nodeset_test.go (limited to 'core') diff --git a/core/types/nodeset.go b/core/types/nodeset.go new file mode 100644 index 0000000..9025cd7 --- /dev/null +++ b/core/types/nodeset.go @@ -0,0 +1,144 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core 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-core 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-core library. If not, see +// . + +package types + +import ( + "container/heap" + "encoding/binary" + "math/big" + + "github.com/dexon-foundation/dexon-consensus-core/core/crypto" +) + +// NodeSet is the node set structure as defined in DEXON consensus core. +type NodeSet struct { + Nodes map[NodeID]struct{} +} + +// SubSetTarget is the sub set target for GetSubSet(). +type SubSetTarget *big.Int + +type subSetTargetType byte + +const ( + targetNotarySet subSetTargetType = iota + targetWitnessSet + targetDKGSet +) + +type nodeRank struct { + ID NodeID + rank *big.Int +} + +// rankHeap is a MaxHeap structure. +type rankHeap []*nodeRank + +func (h rankHeap) Len() int { return len(h) } +func (h rankHeap) Less(i, j int) bool { return h[i].rank.Cmp(h[j].rank) > 0 } +func (h rankHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } +func (h *rankHeap) Push(x interface{}) { + *h = append(*h, x.(*nodeRank)) +} +func (h *rankHeap) Pop() interface{} { + old := *h + n := len(old) + x := old[n-1] + *h = old[0 : n-1] + return x +} + +// NewNodeSet creates a new NodeSet instance. +func NewNodeSet() *NodeSet { + return &NodeSet{ + Nodes: make(map[NodeID]struct{}), + } +} + +// NewNotarySetTarget is the target for getting Notary Set. +func NewNotarySetTarget(crs []byte, shardID, chainID uint32) SubSetTarget { + binaryShardID := make([]byte, 4) + binary.LittleEndian.PutUint32(binaryShardID, shardID) + + binaryChainID := make([]byte, 4) + binary.LittleEndian.PutUint32(binaryChainID, chainID) + + return newTarget(targetNotarySet, crs, binaryShardID, binaryChainID) +} + +// NewWitnessSetTarget is the target for getting DKG Set. +func NewWitnessSetTarget(crs []byte, round uint64) SubSetTarget { + binaryRound := make([]byte, 8) + binary.LittleEndian.PutUint64(binaryRound, round) + + return newTarget(targetWitnessSet, crs, binaryRound) +} + +// NewDKGSetTarget is the target for getting DKG Set. +func NewDKGSetTarget(crs []byte, round uint64) SubSetTarget { + binaryRound := make([]byte, 8) + binary.LittleEndian.PutUint64(binaryRound, round) + + return newTarget(targetDKGSet, crs, binaryRound) +} + +// GetSubSet returns the subset of given target. +func (ns *NodeSet) GetSubSet(size int, target SubSetTarget) NodeIDs { + h := rankHeap{} + idx := 0 + for nID := range ns.Nodes { + if idx < size { + h = append(h, newNodeRank(nID, target)) + } else if idx == size { + heap.Init(&h) + } + if idx >= size { + rank := newNodeRank(nID, target) + if rank.rank.Cmp(h[0].rank) < 0 { + h[0] = rank + heap.Fix(&h, 0) + } + } + idx++ + } + + nIDs := make(NodeIDs, 0, size) + for _, rank := range h { + nIDs = append(nIDs, rank.ID) + } + + return nIDs +} + +func newTarget(targetType subSetTargetType, data ...[]byte) SubSetTarget { + data = append(data, []byte{byte(targetType)}) + h := crypto.Keccak256Hash(data...) + num := big.NewInt(0) + num.SetBytes(h[:]) + return SubSetTarget(num) +} + +func newNodeRank(ID NodeID, target SubSetTarget) *nodeRank { + num := big.NewInt(0) + num.SetBytes(ID.Hash[:]) + num.Abs(num.Sub((*big.Int)(target), num)) + return &nodeRank{ + ID: ID, + rank: num, + } +} diff --git a/core/types/nodeset_test.go b/core/types/nodeset_test.go new file mode 100644 index 0000000..6fe9092 --- /dev/null +++ b/core/types/nodeset_test.go @@ -0,0 +1,59 @@ +// Copyright 2018 The dexon-consensus-core Authors +// This file is part of the dexon-consensus-core library. +// +// The dexon-consensus-core 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-core 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-core library. If not, see +// . + +package types + +import ( + "testing" + + "github.com/dexon-foundation/dexon-consensus-core/common" + "github.com/stretchr/testify/suite" +) + +type NodeSetTestSuite struct { + suite.Suite +} + +func (s *NodeSetTestSuite) TestGetSubSet() { + total := 10 + crs := common.NewRandomHash() + nodes := NewNodeSet() + for len(nodes.Nodes) < total { + nodes.Nodes[NodeID{common.NewRandomHash()}] = struct{}{} + } + target := NewNotarySetTarget(crs[:], 0, 0) + ranks := make(map[NodeID]*nodeRank, len(nodes.Nodes)) + for nID := range nodes.Nodes { + ranks[nID] = newNodeRank(nID, target) + } + size := 4 + notarySet := nodes.GetSubSet(size, target) + for _, notary := range notarySet { + win := 0 + rank := ranks[notary].rank + for node := range nodes.Nodes { + if rank.Cmp(ranks[node].rank) < 0 { + win++ + } + } + s.True(win >= total-size) + } +} + +func TestNodeSet(t *testing.T) { + suite.Run(t, new(NodeSetTestSuite)) +} -- cgit v1.2.3